Основы теории информации и кодирования. Лабораторный практикум: Учебно-методическое пособие

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

____________________________________________

Е.Ф. Березкин

ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ И КОДИРОВАНИЯ Лабораторный практикум Учебно-методическое пособие 2-е издание, переработанное и дополненное

Москва 2009

УДК 519.72(076.5) ББК 22.18я 7 Б48 Березкин Е.Ф. Основы теории информации и кодирования. Лабораторный практикум: Учебно-методическое пособие. – 2-е изд., перераб. и доп. – М.: МИФИ, 2009. – 84 с. Приведены описания восьми лабораторных работ. Первые четыре работы посвящены исследованию математических моделей непрерывных сигналов, следующие четыре – исследованию информационных моделей дискретных сигналов. Все работы выполняются в дисплейном классе на IBM совместных ПЭВМ с использованием специализированного компьютерного учебника ОТИК 4.15. Лабораторный практикум предназначен для студентов, обучающихся по специальности 230102 «Автоматизированные системы обработки информации и управления» и направлению подготовки бакалавров и магистров 230100 «Информатика и вычислительная техника». Рецензент д-р техн. наук, проф. Ю.Г. Древс Рекомендовано редсоветом МИФИ в качестве учебно-методического пособия ISBN 978-5-7262-1120-6

© Московский инженерно-физический институт (государственный университет), 2009

Редактор Е.Е. Шумакова Оригинал-макет изготовлен Е.Ф. Березкиным Подписано в печать 16.02.2009. Формат 60х84 1/16. Печ.л. 5,25. Уч.-изд.л. 5,25. Тираж 150 экз. Изд. № 030-1. Заказ № _______________________________________________________________________ Московский инженерно-физический институт (государственный университет), 115409, Москва, Каширское шоссе, д.31. Типография МИФИ.

ОГЛАВЛЕНИЕ _______________________________________________________________ Предисловие ........................................…………………………….......... Лабораторная работа 1. Математические модели детерминированных периодических сигналов .............……………….………....... Лабораторная работа 2. Математические модели детерминированных непериодических сигналов .......…………………………...... Лабораторная работа 3. Дискретизация непрерывных сигналов …….. Лабораторная работа 4. Математические модели случайных сигналов и элементы теории оптимального приема .….…….……....... Лабораторная работа 5. Рациональное кодирование двоичного источника .…………………………………………………...... Лабораторная работа 6. Исследование информационной пропускной способности двоичного канала .……..………............……..... Лабораторная работа 7. Корректирующие коды Боуза–Чоудхури–Хоквингема .…………………………….… Лабораторная работа 8. Построение кодирующих и декодирующих устройств циклического кода Хэмминга ………………........ Список рекомендуемой литературы ..........……………........……......... Приложение ………………………………………………………………

4 5 13 23 36 44 54 62 71 82 83

_______________________________________________________________

3

ПРЕДИСЛОВИЕ

Курс «Основы теории информации и кодирования» читается студентам III курса (5-й и 6-й семестры) кафедры «Управляющие интеллектуальные системы». Лабораторный практикум по курсу выполняется в дисплейных классах кафедры с использованием специализированного компьютерного учебника ОТИК 4.15 нового поколения, который состоит из единого программного комплекса и предназначен для самостоятельного выполнения практических заданий и решения задач, охватывающих все разделы курса. Первое издание учебного пособия (Березкин Е.Ф., Федосеев Ю.Н. Лабораторный практикум по курсу "Основы теории информации и кодирования". – М.: МИФИ, 1997), базировавшегося на компьютерном учебнике ОТИК предыдущего поколения, существенно переработано и дополнено новыми работами. Программный комплекс – диалоговая программа с оверлейной структурой, позволяющая детальнее и глубже изучить соответствующий материал и содержащая специальные средства, с помощью которых можно провести достаточно интересные и серьезные исследования. Как правило, специальные средства обеспечивают автоматизацию наиболее трудоемких процедур проектирования информационной техники. Практические задания разработаны для изучения: математических моделей детерминированных периодических сигналов; математических моделей детерминированных непериодических сигналов; дискретизации непрерывных сигналов по времени; математических моделей случайных сигналов и элементов теории оптимального приема; рационального кодирования двоичного источника; информационной пропускной способности двоичного канала; корректирующих кодов Боуза–Чоудхури–Хоквингема; кодирующих и декодирующих устройств циклического кода Хэмминга заданной канальности. Программный комплекс разработан на алгоритмическом языке Delphi 7.0 с использованием HTML Help Workshop 1.3 и занимает на HDD порядка 30 Mb. Дистрибутив комплекса реализован с помощью InstallShield Express 2.12.

4

Лабораторная работа 1 МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДЕТЕРМИНИРОВАННЫХ ПЕРИОДИЧЕСКИХ СИГНАЛОВ Цель: изучение и исследование спектральных характеристик детерминированных периодических сигналов. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Теория анализа и обработки физических данных базируется на математических моделях соответствующих физических полей и физических процессов, на основе которых создаются математические модели сигналов. Математические модели сигналов дают возможность обобщенно, абстрагируясь от физической природы, судить о свойствах сигналов, предсказывать изменения сигналов в изменяющихся условиях, заменять физическое моделирование процессов математическим. С помощью математических моделей имеется возможность описывать свойства сигналов, которые являются главными, определяющими в изучаемых процессах, и игнорировать большое число второстепенных признаков. Знание математических моделей сигналов дает возможность классифицировать их по различным признакам, характерным для того или иного типа моделей. Сигнал – изменяющаяся физическая величина, обеспечивающая передачу информации по линии связи. Сигналы, используемые в информационных системах, можно разделить на две группы: детерминированные и случайные сигналы. Детерминированные сигналы характеризуются тем, что в любые моменты времени их значения являются известными величинами, а случайные – тем, что их значения в любые моменты времени – случайные величины. Деление сигналов на детерминированные и случайные условно, так как детерминированных сигналов в точном их понимании в природе нет. На практике нельзя точно предсказать значение сигнала в любые моменты времени, в противном случае сигнал не нес бы полезной информации. Кроме того, любой реальный сигнал 5

случаен в силу воздействия на него многочисленных случайных факторов. Несмотря на это, исследование детерминированных сигналов весьма важно, так как выводы, полученные в результате анализа периодических и непериодических детерминированных сигналов, во многих случаях можно использовать для анализа случайных сигналов. Важнейшая характеристика сигнала – его частотные свойства. Для исследования используется частотное представление функции в виде спектра, являющегося преобразованием Фурье временной формы. В процессе переработки и передачи сигналов эта характеристика играет особую роль, так как определяет параметры используемой аппаратуры. При разложении периодического колебания x ( t ) в ряд Фурье по тригонометрическим функциям в качестве ортогональной системы берут 1, cosω0t, sin ω0t, cos2ω0t, sin 2ω0t,...,coskω0t, sin kω0t,... (1.1) или

..., e − j 2 ω 0 t , e − jω 0 t ,1, e jω 0 t , e j 2 ω 0 t ,... .

(1.2) Интервал ортогональности в обоих случаях совпадает с периодом T = 2π / ω0 функции x ( t ) . Система функций (1.1) приводит к тригонометрической форме ряда Фурье, а система (1.2) – к комплексной форме. Между этими двумя формами существует простая связь. Тригонометрическая форма ряда Фурье имеет вид:

A0 ∞ + ∑ Ak cos(kω0t + Θ k ) = x (t ) = 2 k =1 ∞ A = 0 + ∑ (ak cos kω0t − bk sin kω0t ) , 2 k =1

где

A0 2

–

постоянная

Ak cos( kω 0 t + Θ k )

–

составляющая

k -я

функции

(1.3)

x (t ) ;

гармоническая составляющая;

Ak , kω 0 , Θ k – амплитуда, частота и начальная фаза k-й гармони6

ческой составляющей; ω 0 =

2π – частота основной гармоники T

(T – период колебаний). Ряд Фурье (1.3) с учетом свойств периодической функции x ( t ) приобретает еще более простой вид: ∞

x (t ) = ∑ bk sin kω 0 t

– нечетная функция;

k =1

∞ A0 + ∑ a k cos kω 0 t – четная функция. 2 k =1 Коэффициенты a k и bk вычисляются в соответствии с выраже-

x (t ) =

ниями T /2

2 a k = Ak cos Θ k = x(t ) cos( kω0t ) dt , T −T∫/ 2 T /2

2 bk = Ak sin Θ k = x (t ) sin( kω0 t ) dt T −T∫/ 2 и связаны между собой формулой A k =

a k2 + b k2 .

Комплексная форма ряда Фурье имеет вид

x (t ) = где

Ak = Ak e jΘ k

1 2

∞

∑

k = −∞

A k e jk ω 0 t ,

(1.4)

– комплексная амплитуда гармонической со-

ставляющей частоты kω0 , вычисляемая по формуле T /2

2 Ak = x(t )e − jkω0t dt = T −T∫/ 2 T /2

=

T /2

2 2 x(t ) cos(kω0t )dt − j x(t ) sin(kω0t )dt = ak − jbk ; ∫ T −T / 2 T −T∫/ 2

Θk = −arctg

bk – начальная фаза. ak 7

Совокупность модулей амплитуд и соответствующих частот гармоник называют спектром амплитуд – Ak (ω) , совокупность начальных фаз и соответствующих частот гармоник – спектром фаз Θk (ω) . Спектр амплитуд и спектр фаз однозначно определяют сигнал. На рис. 1.1 даны графические изображения спектра амплитуд и спектра фаз периодического сигнала. Характерной особенностью спектров периодического сигнала является его дискретность. Ak (ω) A0 2

A1

Θ k (ω )

A3

Θ3

A5

Θ1

Θ5 ω

ω 0 ω 0 2 ω 0 3ω 0 4 ω 0 5ω 0 0 ω 0 2 ω 0 3ω 0 4 ω 0 5ω 0

Рис. 1.1. Спектральные характеристики периодического сигнала

Дискретный спектр не обязательно означает периодичность функции x ( t ) . Последнее имеет место лишь в случае, когда расстояние между спектральными линиями кратны основной частоте ω0 . При невыполнении этого условия спектр описывает так называемую почти периодическую функцию. Примером такой функции может служить спектр амплитудно-модулированного сигнала с гармонической модулирующей функцией, частота которой несоизмерима с частотой несущей. При рассмотрении спектров основных видов сигналов главное внимание уделяется определению их ширины, поскольку в основном этот фактор используется для согласования сигнала с аппаратурой обработки информации (каналом): для исключения потери 8

информации ширина спектра не должна превышать полосы пропускания канала. Ширина спектра, как правило, определяется через его энергетическую характеристику – среднюю мощность. Средняя мощность периодического колебания и распределение этой мощности между отдельными гармониками имеет вид 2

1 ∞ ⎛A ⎞ x (t ) = ⎜ 0 ⎟ + ∑ Ak ⎝ 2⎠ 2 k =1 2

2

.

Пример. Найти спектр последовательности прямоугольных импульсов (рис. 1.2)

T ⎧ ⎪⎪+ h, iT ≤ t < 2 + iT ; x(t ) = ⎨ ⎪− h, − T + iT ≤ t < iT , i = 0,±1,±2,..., ⎪⎩ 2 называемой меандром.

x(t) h

t T/2

-T/2

Рис. 1.2. Меандр

Поскольку функция x ( t ) нечетная, разложение будем искать в виде ( ak = 0) ∞

x (t ) = ∑ bk sin kω0 t . k =1

Спектр амплитуд вычисляется следующим образом: 9

bk = =−

2 T

T /2

∫

x (t ) sin( k ω 0 t ) dt =

−T / 2

4h T

T /2

∫ sin( kω t ) dt = 0

0

T /2 4h 1 2h =− cos k ω 0 t (cos k π − 1) = 0 T kω 0 kπ

⎧ 4h ⎪ , k = 1,3,5,...; = ⎨ kπ ⎪⎩ 0 , k = 2, 4 ,6 ,... . Спектр фаз имеет вид

Θ k = − arctg

bk π =− 0 2

.

Спектральные характеристики меандра приведены на рис. 1.3. Окончательно тригонометрический ряд Фурье будет иметь вид:

x(t ) =

4h 1 1 (sin ω0 t + sin 3ω0t + sin 5ω0 t + ...) . π 3 5

Ak (ω)

Θk (ω)

4h/ π 4h/3 π

4h/5 π 4h/7 π

ω0 3ω0 5ω0 7ω0

ω

- π /2

ω

ω0 3ω0 5ω0 7ω0 Рис. 1.3. Спектр амплитуд и спектр фаз меандра

Модель одного периода сигнала задана с тремя разрывами первого рода (скачками). Любой скачок функции содержит все частоты диапазона до бесконечности, в связи с чем ряд Фурье также бесконечен и очень медленно затухает. Однако одним из важных достоинств преобразования Фурье является то, что при ограничении (усечении) ряда Фурье до любого конечного числа его членов 10

обеспечивается наилучшее по среднеквадратической погрешности приближение к исходной функции. ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Вычислить спектральные характеристики последовательности униполярных треугольных импульсов (рис. 1.4) 2h T T x(t ) = t − iT , − + iT ≤ t < + iT , i = 0 , ± 1, ± 2 , ... . T 2 2

h

x(t)

t T/2

-T/2

Рис. 1.4. Периодическая последовательность униполярных треугольных импульсов

3. Вычислить спектральные характеристики периодического колебания пилообразной формы (рис. 1.5) 2h T T x(t ) = t − i 2 h ,− + iT ≤ t < + iT , i = 0, ± 1,± 2 , ... . T 2 2

h

x(t)

T/2

-T/2

t

Рис. 1.5. Периодическое колебание пилообразной формы 11

4. Подготовить таблицы для обоих спектров, произвольно выбрав параметры h и T, в следующем виде

k Ak

0

1

2

3

4

5

6

7

8

9

10

Θk 5. Изучить свойства преобразования Фурье применительно к периодическим сигналам. 6. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, изучить принципы разложения периодического сигнала в ряд Фурье. 2. Ввести спектральные характеристики сигнала с постоянным уровнем x(t) = a . Убедиться в правильности его формирования. 3. Ввести спектральные характеристики гармонического сигнала x (t ) = A cos( kω0 t + Θ k ) . Убедиться в правильности его формирования. 4. Ввести спектральные характеристики последовательности униполярных треугольных импульсов. Убедиться в правильности их формирования. 5. Ввести спектральные характеристики периодического колебания пилообразной формы. Убедиться в правильности его формирования. 6. Ввести спектральные характеристики, позволяющие воспроизвести на экране периодическую последовательность прямоугольных импульсов с заданными преподавателем параметрами. 7. Задать произвольные спектральные характеристики и получить периодический сигнал, которому они соответствуют. 8. Результаты отразить в лабораторном отчете.

12

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие способы представления моделей сигналов известны? 2. В чем заключаются преимущества частотного метода представления сигналов? 3. При каких условиях периодическая функция может быть представлена рядом Фурье? 4. Что понимается под спектром амплитуд и спектром фаз? 5. Каковы характерные особенности спектра периодического сигнала? 6. Как в спектре амплитуд отображается постоянная составляющая периодического сигнала? 8. Каков спектр гармонического сигнала? 9. Как можно энергетически истолковать спектр периодического сигнала? 10.Что понимается под практической шириной спектра периодического сигнала? 11.В чем состоит критерий выбора практической шириной спектра периодического сигнала? 12.Как выглядит спектр периодической последовательности прямоугольных импульсов? 13.Какой физический смысл имеет огибающая спектра амплитуд периодического сигнала? Лабораторная работа 2 МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДЕТЕРМИНИРОВАННЫХ НЕПЕРИОДИЧЕСКИХ СИГНАЛОВ Цель: изучить и исследовать спектральные характеристики детерминированных непериодических сигналов. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Гармонический анализ периодических колебаний можно распространить на непериодические колебания. Пусть такое колеба13

ние x ( t ) задано в виде некоторой функции, отличной от нуля в промежутке (t 1 , t 2 ) (рис. 2.1). Выделив произвольный отрезок времени T, включающий в себя промежуток (t 1 , t 2 ) , можно представить заданное колебание в виде ряда Фурье

x (t ) =

∞

∑C e k

k = −∞

jk ω 0 t

,0 < t < T ,

(2.1)

где ω 0 = 2π / T , а коэффициенты

1 Ck = T

t2

∫ x (t ) e

− jk ω 0 t

dt .

(2.2)

t1

x(t)

T t

t1

t2

Рис. 2.1. Одиночный непериодический сигнал

Вне отрезка (0, T) ряд (2.1) определяет функцию x (t ) = x (t ± kT ) , где k – целое число, т.е. периодическую функцию, полученную повторением x ( t ) вправо и влево с периодом T. Для того чтобы вне отрезка (0, T) функция равнялась нулю, величина T должна быть бесконечно большой. Но чем больше отрезок T , тем меньше коэффициенты C k . Устремляя T к бесконечности, в пределе получаем бесконечно малые амплитуды гармонических составляющих, сумма которых изображает исходную непериодическую функцию x ( t ) , заданную в интервале t 1 < t < t 2 . Число гармонических составляющих, входящих в ряд Фурье, будет при этом бесконечно большим, так как при T → ∞ основная частота ω0 → 0 . 14

Иными словами, расстояние между спектральными линиями, равное основной частоте ω0 , становится бесконечно малым, а спектр сплошным. В общем случае, когда пределы t 1 и t 2 в (2.2) не уточнены, непериодический сигнал x ( t ) можно представить в виде ∞

1 x (t ) = S ( j ω) e j ω t d ω , ∫ 2π −∞

(2.3)

где S ( jω ) – спектральная плотность, записываемая в форме ∞

S ( jω) =

∫ x(t )e

− jωt

dt .

(2.4)

−∞

Выражения (2.3) и (2.4) называются соответственно обратным и прямым преобразованиями Фурье. Спектральная плотность S ( jω) обладает всеми основными свойствами коэффициентов Ck комплексного ряда Фурье. Следовательно, по аналогии можно написать

S ( jω) =

∞

∞

−∞

−∞

∫ x (t ) cos( ωt )dt − j ∫ x (t ) sin( ωt )dt =

= A(ω) − jB (ω) = S (ω)e jΘ (ω ) . Модуль и аргумент спектральной плотности определяется выражениями:

S (ω) = [ A(ω)] 2 + [ B (ω)] 2 ,

Θ ( ω) = − arctg

B ( ω) . A ( ω)

(2.5а) (2.5б)

Выражение (2.5а) можно рассматривать как амплитудночастотную характеристику (АЧХ), (2.5б) — как фазочастотную характеристику (ФЧХ) сплошного спектра непериодического колебания. Как и в случае ряда Фурье, S (ω) является четной [S (ω) = S (−ω)] , а Θ(ω) – нечетной [Θ(ω) = −Θ(−ω)] функциями частоты. 15

Интегральное преобразование (2.3) можно привести к тригонометрической форме ∞ ∞ 1 1 x(t ) = S ( ω ) cos( ω t + Θ ) d ω = S (ω) cos(ωt + Θ)dω . (2.6) 2π −∫∞ π ∫0 Из сопоставления выражений (1.3) и (2.6) видно, что величина

1 S (ω)dω = 2S (ω)df π имеет смысл модуля амплитуды Ak (бесконечно малой) гармонической составляющей частоты ω = 2 π f . Следовательно, смысл термина "спектральная плотность" можно трактовать следующим образом: 2 S (ω) есть амплитуда колебания, приходящаяся на 1 Гц в бесконечно узкой полосе частот, включающей в себя рассматриваемую частоту ω = 2 π f . С энергетической точки зрения практическая ширина спектра непериодического сигнала определяется как область частот, в пределах которой сосредоточена подавляющая часть всей энергии сигнала. Выражение ∞

Э=

∞

1 1 2 [ ( ω )] ω = [ S (ω)]2 dω , S d ∫ ∫ 2π − ∞ π0

получившее название равенства Парсеваля, показывает, что энергия сигнала может быть представлена в виде суммы бесконечно малых слагаемых

1 [ S (ω)]2 dω , соответствующих бесконечно π

малым участкам частотного спектра. Относительная величина энергии одиночного сигнала, сосредоточенная в полосе частот от 0 до ω 1 :

λ (ω1 ) =

Э( ω1 ) , Э

называется интегральной кривой распределения энергии сигнала в спектре частот. Ряд Котельникова 16

x(t ) =

∞

∑ x(kΔt )

k = −∞

sin[ωc (t − kΔt )] ωc (t − kΔt )

(2.7)

представляет собой разложение сигнала с ограниченным спектром координатными детерминированными ( S ( jω) = 0, ω > ω c ) функциями времени с весовыми коэффициентами x ( kΔt ) , являющимися величинами, равными мгновенным значениям сигнала в точках kΔt . Другими словами, выражение (2.7) показывает, что реализация x ( t ) полностью определяется совокупностью отсчетов, взятых в моменты времени kΔt и отстоящих друг от друга на величину Δt =

π 1 . = ωc 2 f c

sin [ωc (t − kΔt )] представляет собой ωc (t − kΔt ) реакцию фильтра нижних частот с ограниченной частотой ωc на Как известно, функция

дельта-импульс. Следовательно, если в приемном устройстве поместить такой фильтр и пропустить через него дискретизированный сигнал, представляющий собой последовательность с частотой Δt кратковременных импульсов, амплитуды которых пропорциональны отсчетам исходной непрерывной функции, то, суммируя выходные сигналы фильтра, можно воспроизвести с достаточно высокой степенью точности исходный непрерывный сигнал. На практике реализовать это достаточно трудно, так как мы имеем дело с процессами, имеющими начало и конец, т. е. с функциями ограниченной длительности T . Ограниченные во времени функции не могут иметь ограниченный спектр (т. е. спектральную плотность, равную нулю вне конечного интервала) – эти условия противоречивы. Однако можно построить рассуждение на более общей основе, определив ширину спектра как интервал частот, вне которого спектральная плотность меньше некоторой заданной величины. Пример. Найти спектральную плотность одиночного импульса высокочастотных колебаний (рис. 2.2)

17

τ τ ⎧ ⎪h cos ω 0 t , − 2 ≤ t ≤ 2 ; x (t ) = ⎨ τ ⎪ 0, t > . 2 ⎩

x(t) h

t τ/2 Рис. 2.2. Одиночный импульс высокочастотных колебаний

Спектральные характеристики такого сигнала достаточно просто можно найти с использованием известного свойства преобразования Фурье – сдвиг спектра колебания по частоте, когда прямое преобразование Фурье применяется к произведению x(t ) = x1 (t ) cos ω0 t , где x1 (t ) рассматривается как одиночный прямоугольный импульс амплитуды h и длительности τ . Тем не менее, в целях иллюстрации применения прямого преобразования Фурье, выполним вычисления непосредственным образом: τ 2

S ( jω) = ∫ h cos(ω0t )e− jωt dt = −

⎡ h ⎢e = 2⎢ ⎢⎣

τ 2

( ω−ω0 ) τ −j 2

h − j (ω−ω0 )t h e dt + ∫ e− j (ω+ω0 )t dt = ∫ 2 τ 2 τ −

(ω−ω0 ) τ j 2

−e − j(ω − ω0 )

+

−

2

( ω+ω0 ) τ −j 2

e

τ 2

τ 2

(ω+ω0 ) τ j 2

−e − j(ω + ω0 )

18

2

⎤ ⎥= ⎥ ⎥⎦

=

(ω − ω 0 ) τ (ω + ω 0 ) τ h h sin sin + = 2 2 ω − ω0 ω + ω0

(ω − ω 0 ) τ (ω + ω 0 ) τ sin h τ 2 2 . + (ω − ω 0 ) τ (ω + ω 0 )τ 2 2 2 Сравнив полученное выражение с выражением ωτ ωτ ω sin sin 2 = hτ 2 e − jΕ ( 2 π / τ ) π S1 ( jω) = hτ ωτ ωτ 2 2 для спектра одиночного прямоугольного импульса такой же длительности и величины h, но без высокочастотного заполнения, видим, что по отношению к спектру прямоугольного импульса спектр импульса высокочастотных колебаний смещен на величину несущей ω0 и расширен в два раза за счет появления зеркального отображения спектра (рис. 2.3). Другими словами, расщепление спектра S1 ( jω) на две части, смещенные соответственно на + ω0 и − ω0 , эквивалентно умножеτh = 2

sin

нию функции x1 (t ) на гармоническое колебание cos ω0 t . То есть

S ( jω) =

1 {S1[ j (ω − ω0 )] + S1[ j (ω + ω0 )]} . 2 S(jω) hτ/2

ω0

ω

ω0 + 2π / τ

ω0 − 2π / τ Рис. 2.3. Комплексная форма спектральной плотности одиночного импульса высокочастотных колебаний 19

Графики модуля спектральной плотности импульса высокочастотных колебаний S (ω) = h τ

(ω − ω0 ) τ 2 (ω − ω0 )τ 2

sin

и аргумента спектральной плотности ⎛ ω − ω0 ⎞ Θ (ω ) = − Ε ⎜ ⎟π ⎝ 2π / τ ⎠ приведены на рис. 2.4. hτ

S(ω)

Θ(ω)

π

ω

ω0

ω0 + 2π/ τ

ω0 −2π/ τ ω

-π

Рис. 2.4. АЧХ и ФЧХ одиночного импульса высокочастотных колебаний

ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Вывести формулы модуля S (ω) и аргумента Θ(ω) спектральной плотности одиночного экспоненциального импульса, представленного на рис. 2.5, 20

⎧ he − β ( t − t 0 ) , t ≥ t 0 ; x (t ) = ⎨ t < t0 . ⎩ 0,

x(t) h t

t0

Рис. 2.5. Экспоненциальный импульс

3. Подготовить набор значений h , β и t0 для построения семейств зависимостей F1 ( ω ) = S ( ω ) h ,β ,t , 0

F2 (ω ) = Θ (ω )

h ,β ,t 0

,

определяющих АЧХ и ФЧХ одиночного импульса. 4. Выявить значения параметров h , β и t0 , при которых одиночный экспоненциальный импульс превращается в сигнал включения. 5. Разобраться с энергетическим толкованием спектра сигнала. 6. Изучить частотный критерий дискретизации Котельникова. 7. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, изучить принципы построения спектральных характеристик детерминированных непериодических сигналов. 2. Используя инструментальные средства диалоговой программы, построить семейство кривых F 1 ( ω ) = S ( ω ) h ,β ,t 0

и установить влияние каждого из параметров на АЧХ одиночного экспоненциального импульса. 21

3. Построить семейство кривых F2 (ω ) = Θ (ω )

h ,β , t 0

и установить влияние каждого из параметров на ФЧХ одиночного экспоненциального импульса. 4. Задать значения параметров, при которых исследуемый импульс превращается в сигнал включения. Получить АЧХ и ФЧХ сигнала включения. 5. Построить и исследовать интегральную кривую распределения энергии сигнала в спектре частот. 6. Исследовать представление сигнала в виде ряда Котельникова. 7. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. При каких условиях непериодическая функция может быть представлена интегралом Фурье? 2. Что понимается под прямым и обратным преобразованиями Фурье? 3. Каковы характерные особенности спектра непериодического сигнала? 4. Каковы свойства спектральной плотности сигнала? 5. Каков спектр одиночного прямоугольного импульса? 6. Как можно энергетически истолковать спектр непериодического сигнала? 7. Что понимается под практической шириной спектра непериодического сигнала? 8. В чем состоит критерий выбора практической шириной спектра непериодического сигнала? 9. Как можно получить спектр импульса высокочастотных колебаний, используя свойства преобразования Фурье? 10. Каким образом можно получить спектр непериодического сигнала непосредственно из спектра соответствующего периодического сигнала? 11. В чем состоит практическая ценность равенства Парсеваля? 12. Каков физический смысл ряда Котельникова? 22

Лабораторная работа 3 ДИСКРЕТИЗАЦИЯ НЕПРЕРЫВНЫХ СИГНАЛОВ Цель: изучение и исследование основ дискретизации непрерывных сигналов по времени и принципов построения их спектральных и корреляционных характеристик. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Для производственных задач обработки данных обычно требуется значительно меньше информации, чем ее поступает от измерительных датчиков в виде непрерывного аналогового сигнала. Рациональное выполнение дискретизации и квантования исходных данных дает возможность снизить затраты на хранение и обработку информации. Использование цифровых сигналов позволяет применять методы кодирования информации с возможностью последующего обнаружения и исправления ошибок при обращении информации. Цифровая форма сигналов облегчает также унификацию операций преобразования информации на всех этапах ее обращения. В технике связи при передаче различных сигналов мы имеем обычно дело с функциями времени, спектр которых ограничен, т.е. в спектре которых не содержатся частоты выше некоторой граничной. Такие функции обладают замечательным свойством, установленным впервые в 1933 г. В. А. Котельниковом и выраженным им в теореме, играющей фундаментальную роль в теории связи и, в частности, в импульсной связи. Теорема в формулировке автора гласит: «Любую функцию x (t ) , состоящую из частот от 0 до f c , можно передавать с любой точностью при помощи чисел, следующих друг за другом через

1 секунд». 2 fc

Свойство это состоит в том, что тогда как в общем случае функция времени вполне определяется бессчетным множеством своих значений (т.е. бесконечным числом значений на протяжении конечного интервала), функция с ограниченным спектром вполне определяется счетным множеством своих значений (т.е. конечным 23

числом значений на протяжении конечного интервала). С геометрической точки зрения это означает, что если задать на протяжении конечного интервала вполне определенное количество точек, изображающих мгновенные значения функции с ограниченным спектром, то непрерывная кривая, представляющая график функции, может быть проведена через эти точки единственным образом. Это положение объясняется тем, что отсутствие высоких частот в составе функции накладывает серьезное ограничение на способы, которыми могут быть соединены каждые две соседние точки, и смысл теоремы Котельникова состоит именно в утверждении, что при достаточно частом расположении точек эти ограничения приводят к тому, что кривая определяется этими точками полностью. Итак, функция с ограниченным спектром может быть представлена рядом

x(t ) =

2 f cTи

∑ x(kΔt ) k =1

sin [ωc (t − kΔt )] , ωc (t − kΔt )

называемым интерполяционным рядом Котельникова–Шеннона, коэффициенты которого представляют собой отсчеты значений функции, взятые через

Δt =

π 1 , = ωc 2 f c

где Tи – длительность сигнала. При дискретном представлении сигналов аргумент t k обычно проставляется номерами отсчетов k = 0,1,... N − 1 , а преобразования Фурье выполняются по аргументу n (номер шага по частоте) на главных периодах

2 Ak = N

N −1

∑ x ( nT ) e n=0

− jk

2π

2π n N

jk n 1 N −1 x ( nT ) = ∑ Ak e N 2 k =0

⎫ ,⎪ ⎪ ⎬ .⎪ ⎪⎭

(3.1)

Преобразования (3.1) называют дискретными преобразованиями Фурье (ДПФ). Для ДПФ, в принципе, справедливы все свойства 24

интегральных преобразований Фурье, однако при этом следует учитывать периодичность дискретных функций и спектров. Из выражений ДПФ можно видеть, что для вычисления каждой гармоники нужно N операций комплексного умножения и сложения и соответственно N 2 операций на полное выполнение ДПФ. При больших объемах массивов данных это может приводить к существенным временным затратам. Ускорение вычислений достигается при использовании быстрого преобразования Фурье (БПФ). БПФ базируется на том, что при вычислениях среди множителей (синусов и косинусов) есть много периодически повторяющихся значений (в силу периодичности функций). Алгоритм БПФ группирует слагаемые с одинаковыми множителями в пирамидальный алгоритм, значительно сокращая число умножений за счет исключения повторных вычислений. В результате быстродействие БПФ в зависимости от N может в сотни раз превосходить быстродействие стандартного алгоритма. При этом следует подчеркнуть, что алгоритм БПФ даже точнее стандартного, так как, сокращая число операций, он приводит к меньшим ошибкам округления. Алгоритмы БПФ основываются на свойствах комплексной экспоненты e − j ( 2 π / N ) kn = W Nkn : ее симметрии WNkn = WN− ( N − k ) n = WN− ( N − n ) k и периодичности WNkn = WN( k + lN )( n + mN ) с периодом, равным длине обрабатываемой реализации сигнала N (числу точек БПФ). С учетом последнего свойства экспоненте WNpkn = WNkn/ p соответствует период N / p , где p – целые числа, на которые делится N . Использование данных свойств в алгоритмах БПФ исключает большое число повторяющихся при вычислении ДПФ операций. Алгоритм БПФ заключается в разбиении ДПФ исходной последовательности на ДПФ подпоследовательностей меньшей длины, вплоть до минимально возможной (равной основанию БПФ), через которые и вычисляется ДПФ исходной последовательности. Разбиение означает прореживание последовательностей во временной или в частотной области. В связи с этим различают БПФ с прореживанием по времени и БПФ с прореживанием по частоте. В отличие от ДПФ, БПФ может вычисляться только по определенному числу точек N , соответствующему целой степени его 25

основания m : N = mL , где L – это число этапов прореживания, L = log m N . К наиболее используемым относятся БПФ по основаниям m = 2,4,8. В данной работе реализован алгоритм БПФ с прореживанием по времени по основанию 2. Пусть задана последовательность x(nT ) = x(n) N конечной длины n = 0,1,... N − 1 . Нужно найти ее ДПФ: X ( jk ) =

N −1

∑ x(n)W n =0

kn N

для

k = 0,1,...N − 1 (номера бинов ДПФ) с минимальным объемом вычислений. Решение этой задачи в данном алгоритме БПФ находится следующим образом. Исходную последовательность x(n) длиной N разобьем на 2 подпоследовательности длиной N / 2 (рис. 3.1) – четную (включающую отсчеты x(n) с четными индексами n : x1 (n) = x(2n) ) и нечетную: x 2 (n) = x(2n + 1) , n = 0,1,... N − 1 . Это соответствует первому прореживанию сигнала по времени.

x(nT )

0 1 2 3 4 5 6 … (N-1)

n

0 2 3 4 5 Рис. 3.1. Иллюстрация прореживания сигнала по времени

Обозначим их ДПФ, как X 1 ( jk ) N / 2 и X 2 ( jk ) N / 2 . Выразим ДПФ исходной последовательности x(nT ) = x(n) N через ДПФ подпоследовательностей x1 (n) N / 2 , x 2 (n) N / 2 :

26

X ( jk ) =

N / 2 −1

∑

n=0

x1 ( n ) e

−j

2π kn N /2

= X 1 ( jk ) − W Nk X 2 ( jk ),

+

N / 2 −1

∑

n=0

x 2 ( n )e

−j

2π kn N /2

N k = 0,1,..., − 1 2

e

−j

2π kn N

= (3.2)

.

Это первые N / 2 частотных выборок ДПФ. Вторую половину частотных выборок X ( jk ) k = N / 2,..., N − 1 найдем с учетом свойства периодичности:

N ⎤ ⎡ X ⎢ j (k + )⎥ = X 1 ( jk ) + WN( k + N / 2 ) X 2 ( jk ) = 2 ⎦ ⎣ N = X 1 ( jk ) − WNk X 2 ( jk ), k = 0 ,1,..., − 1 . 2

для

(3.3)

Выражения (3.2), (3.3) определяют базовую операцию БПФ (операцию объединения):

X ( jk ) = X 1 ( jk ) + WNk X 2 ( jk ), X ( j (k + N / 2)) = X 1 ( jk ) − WNk X 2 ( jk ), k = 0,1,...,

N − 1. 2

(3.4)

Входящий в (3.4) множитель WNk , равный по модулю единице, называют поворачивающим. Вычисления в соответствии с (3.4) включают одно комплексное умножение и пару сложения– вычитания. Базовую операцию представляют графически с помощью сигнального графа (бабочки БПФ), рис. 3.2.

X 1 ( jk )

X ( jk )

W

k N

X 2 ( jk )

X ( j (k + N / 2))

Рис. 3.2. Сигнальный граф базовой операции БПФ 27

На нем символ означает операцию сложения (верхний выход) и вычитания (нижний выход), а стрелка → соответствует умножению на поворачивающий множитель WNk . Дальше каждую из последовательностей x1 (n) и x 2 (n) можно разбить еще на две подпоследовательности вдвое меньшей длины: x11 (n), x12 (n) и x21 (n), x22 (n) (четную и нечетную) и повторить вышеприведенные операции объединения их ДПФ с помощью базовых операций. Такое прореживание выполняем L раз до получения N / 2 двухточечных последовательностей xl (0), xl (1) , ДПФ которых вычисляется тривиально: X l ( j 0) = xl (0) + W20 xl (1), X l ( j1) = xl (0) − W20 xl (1) . В результате получаем полный граф БПФ, показанный на рис. 3.3 для N = 8 . x p (0) = x(0) X ( j 0) x p (1) = x( 4)

W N0

x p (2) = x(2) x p (3) = x(6)

X ( j1)

W N0

WN0

X ( j 2)

WN1

X ( j 3)

W

x p (4) = x(1) x p (5) = x(5)

x p ( 7 ) = x (7 )

WN1

WN0

x p (6) = x(3)

WN2

W N0

WN0

0 N

WN3

WN1

X ( j 4) X ( j 5) X ( j 6) X ( j 7)

Рис. 3.3. Полный граф БПФ для

N =8

В соответствии с графом на каждом из L этапов вычисления – объединения ДПФ выполняются N / 2 базовых операций, а общий 28

объем вычислений для комплексных операций умножения и сложения – вычитания составляет: K умн = ( NL ) / 2 = ( N log 2 N ) / 2, K слож = NL = N log 2 N . Особенностью алгоритма БПФ с прореживанием по времени является требуемый им неестественный порядок отсчетов входного сигнала, обусловленный его многократными разбиениями на четные и нечетные подпоследовательности ( n = 0, 4, 2, 6, 1, 5, 3, 7 для N = 8 ). Такой порядок следования называют двоично-инверсным. Это приводит к необходимости предварительной перестановки отсчетов исходной последовательности до начала вычислений. Для этого естественные номера отсчетов последовательности x(n) представляются в L -разрядном двоичном коде, коды эти прочитываются в обратном порядке, то есть справа налево, и преобразуются затем снова в десятичную форму, соответствующую номеру отсчета переставленной последовательности. Корреляционный анализ дает возможность установить в рядах цифровых данных сигналов наличие определенной связи изменения значений сигналов по независимой переменной. То есть, когда большие значения одного сигнала связаны с большими значениями другого сигнала (положительная корреляция), или, наоборот, малые значения одного сигнала связаны с большими значениями другого (отрицательная корреляция), или данные двух сигналов никак не связаны (нулевая корреляция). В функциональном пространстве сигналов эта степень связи может выражаться в нормированных единицах коэффициента корреляции, который принимает значения от 1 (полное совпадение сигналов) до -1 (полная противоположность) и не зависит от значения единиц измерений. Особое значение методы корреляции имеют при анализе случайных процессов для выявления неслучайных составляющих и оценки неслучайных параметров этих процессов. Автокорреляционная функция (АКФ) сигнала x(t ) , конечного по энергии, является количественной интегральной характеристикой формы сигнала и определяется интегралом от произведения двух копий заданного сигнала x(t ) , сдвинутых относительно друг друга на время τ : 29

∞

K XX (τ) =

∫ x(t ) x(t + τ)dt.

−∞

АКФ может быть вычислена и для слабозатухающих сигналов с бесконечной энергией как среднее значение скалярного произведения сигнала и его копии при устремлении интервала задания сигнала к бесконечности: T /2 1 K XX ( τ) = lim ' ∫ x (t ) x (t + τ) dt . T →∞ T −T / 2 '

'

'

Энергия периодических сигналов бесконечна, поэтому АКФ периодических сигналов вычисляется по одному периоду T , с усреднением скалярного произведения сигнала и его сдвинутой копии в пределах этого периода: T /2 1 K XX ( τ) = x(t ) x (t + τ)dt. T −T∫/ 2 Понятия мощности и энергии в теории сигналов не относятся к характеристикам каких-либо физических величин сигналов, а являются их количественными характеристиками, отражающими определенные свойства сигналов и динамику изменения их значений во времени, в пространстве или по любым другим аргументам. Спектральной плотностью мощности или энергетическим спектром принято называть функцию G XX (ω ) , в строгом математическом смысле определяемой как 2⎤ ⎡1 G XX ( ω ) = lim m ⎢ S k' ( j ω ) ⎥ . T →∞ ⎦ ⎣T Из теоремы Хинчина–Винера энергетический спектр и корреляционная функция являются парой преобразования Фурье: ∞

GXX (ω) =

∫K

XX

(τ)e − jωτ dτ,

−∞

∞

1 GXX (ω)e jωτ dω. 2π −∫∞ Это говорит о том, что спектральная плотность мощности стационарного случайного процесса является амплитудным спектром автокорреляционной функции. K XX (τ) =

30

Для реализации модели исследовательского стенда необходим определенный набор технических средств. На рис. 3.4 представлена обобщенная структура стенда для исследования характеристик сигналов. На обобщенной схеме показаны: • генератор, воспроизводящий гармонические сигналы, импульсные сигнал и гауссов шум, а также их комбинацию; • аналого-цифровой преобразователь (АЦП), дискретизирующий сигнал по времени и квантующий по уровню; • идеальный фильтр низких частот, который необходим для восстановления сигнала после дискретизации;

Рис. 3.4. Обобщенная структура технических средств, предназначенных для исследования сигналов

•

•

электронные вычислительные машины, реализующие алгоритмы оценки и визуализации спектра сигнала, корреляционной функции и спектральной плотности средней мощности; осциллограф, который используется как средство отображения исходного непрерывного сигнала, дискретизированного сигнала и сигнала восстановленного после идеального фильтра низких частот. 31

Для генератора задаются: длина сигнала как количество точек дискретизации; тип сигнала (выбор из списка – гармонический сигнал, прямоугольные импульсы, шум и смешанный); параметры сигнала (в зависимости от типа). Для гармонического сигнала вводятся амплитуда, частота и фаза сигнала. Для импульсов – амплитуда, период и длительность прямоугольного импульса. Для гауссова шума – математическое ожидание и среднеквадратическое отклонение случайной величины. В случае если выбран смешанный сигнал, то задаются все выше описанные параметры. Для аналого-цифрового преобразователя вводятся интервал дискретизации и размер одного кванта. Они необходимы для выполнения операций дискретизации сигнала по времени и по уровню. Для фильтра низких частот (ФНЧ) вводится частота среза. Кроме того, для ФНЧ задается параметр «Показывать составляющие». При его установке осциллограф будет отображать координатные детерминированные функции времени, сложение которых и восстанавливает исходный сигнал. Это необходимо для более ясного понимания формулировки теоремы Котельникова. Блок «Параметры процесса» не заполняется пользователем. В нем высвечиваются оптимальные значения, при которых восстановленный сигнал должен максимально походить на исходный. После ввода необходимых данных и параметров нажимаем кнопку «Моделировать». Если необходимы дополнительные вычисления, можно воспользоваться кнопкой «Калькулятор», нажатие на которую вызовет стандартный калькулятор Windows. После окончания моделирования на вкладках «Осциллограф», «Спектр амплитуд», «Корреляционная функция» и «Спектральная плотность мощности» будут построены смоделированный сигнал и спектральные характеристики заданного сигнала. На виртуальном осциллографе можно наблюдать сигнал на каждом этапе его обработки. А именно, непрерывный, дискретный и восстановленный сигнал. На форме отображения спектральных характеристик предусмотрены размерная сетка с подписанными значениями отсчетов по горизонтали и вертикали. Имеются инструменты для удобного просмотра графиков: передвижение графиков в любом направлении, увеличение определенного участка графика, масштабирование графика по области видимости. 32

На рис. 3.5 приведена функциональная модель программы, в которой представлено 10 объектов, каждый из которых имеет свои свойства и задаваемые параметры. Для каждого объекта работают свои алгоритмы в зависимости от выполняемых им функций. Они либо преобразуют сигнал по заданным правилам, либо выводят его в интерфейс отображения. Между соответствующими блоками отрабатываются специальные процедуры обмена данными. Реализованная программная модель максимально правильно реагирует на моделируемые ситуации и теоретические предсказания совпадают с практически полученными результатами.

Рис. 3.5. Функциональная модель работы программы

ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Дать графическое и математическое представление детерминированных x(t ) и случайных сигналов X (t ) следующего вида: а) гармонический сигнал; б) импульс высокочастотных колебаний; 33

в) периодическая последовательность прямоугольных импульсов; г) одиночный прямоугольный импульс; д) пачка N прямоугольных импульсов; шум с нормальным распределением е) белый

f (ξ k ) =

1 σ ξ 2π

−

e

( ξ k − mξ ) 2 2 σ 2ξ

(Гауссов шум).

3. Освоить основные принципы превращения непрерывного сигнала в цифровой и дискретного в непрерывный. 4. Осмыслить общую структуру технических средств, предназначенных для исследования процесса передачи сигнала и построения его спектральных характеристик. 5. Научиться выбирать параметры, такие как «Интервал дискретизации», «Частота дискретизации» и «Частота среза идеального ФНЧ» для восстановления сигнала без искажений и потери информации. 6. Продумать применение теоремы Котельникова для вычисления выше упомянутых параметров. 7. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, изучить принципы передачи сигналов в цифровой форме и основы построения их спектральных характеристик. 2. Ввести параметры гармонического сигнала

x ( t ) = A cos( ω t + θ ) .

3. Используя инструментальные средства диалоговой программы, снять показания на входе и выходе дискретизатора. 4. Оценить качество восстановления сигнала на выходе идеального ФНЧ в двух режимах его работы. 5. Сравнить амплитудный спектр и автокорреляционную функцию с теоретическими результатами. 6. Проанализировать влияние количества точек дискретизированного сигнала и интервала дискретизации на форму сигнала, качество его восстановления и вид спектральных характеристик. 34

7. Задать значения параметров, при которых гармонический сигнал превращается в импульс высокочастотных колебаний. Повторить пункты 3–6. 8. Пункты 3–6 последовательно выполнить для периодической последовательности прямоугольных импульсов, одиночного импульса и пачки из N импульсов. 9. Ввести параметры Гауссова шума. 10. Выполнить пункты 3–6 и дополнительно провести анализ спектральной плотности средней мощности. 11. Задать параметры смешанного случайного и детерминированного сигналов. Повторить пункт 10. 12. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. В чем состоит физический смысл теоремы Котельникова? 2. Что такое функция отсчетов и каков ее вид? 3. В чем заключаются противоречия частотного критерия Котельникова? 4. Что собой представляет дискретное преобразование Фурье? 5. В чем состоит роль алгоритмов быстрого преобразования Фурье? 6. Какова реакция идеального фильтра нижних частот с граничной частотой ωc на дельта-импульс? 7. Что такое координатная детерминированная функция времени? 8. Почему невозможно непосредственное приложение классического гармонического анализа к случайным процессам? 9. Каковы основные свойства корреляционной функции стационарного случайного процесса? 10. Каковы основные свойства спектральной плотности мощности стационарного случайного процесса? 11. Какой случайный процесс называется белым шумом? 12. Какова связь между спектральной плотностью мощности и корреляционной функцией случайного процесса? 13. Что такое интервал корреляции случайного процесса? 14. Можно ли дискретные отсчеты по частотному критерию Котельникова считать статистически независимыми? 35

Лабораторная работа 4 МАТЕМАТИЧЕСКИЕ МОДЕЛИ СЛУЧАЙНЫХ СИГНАЛОВ И ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМАЛЬНОГО ПРИЕМА Цель: изучить спектральные характеристики случайных сигналов и освоить основные принципы решения задач приема сигналов при наличии помех. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

К случайным относят сигналы, значения которых заранее не известны и могут быть предсказаны лишь с некоторой вероятностью. По существу любой сигнал, несущий в себе информацию, должен рассматриваться как случайный. До приема сообщения сигнал следует рассматривать как случайный процесс X(t), представляющий собой совокупность функций времени (рис. 4.1), подчиняющихся некоторой общей для них статистической закономерности. Одна из этих функций x k ( t ) , ставшая полностью известной после приема сообщения, называется реализацией случайного процесса. Эта реализация является уже не случайной, а детерминированной функцией времени. При изучении детерминированных сигналов весьма удобным оказался гармонический анализ. В связи с этим, как правило, используется аппарат преобразований Фурье и к случайным процессам. Однако необходимо иметь в виду, что отдельным реализациям случайного процесса, обладающим различной формой, соответствуют различные спектральные характеристики. Усреднение комплексной спектральной плотности по всем реализациям приводит к нулевому спектру процесса вследствие случайности и независимости фаз спектральных составляющих в различных реализациях.

36

X(t)

x1(t) x2 (t) ... xk (t) ... txN (t)

Рис. 4.1. Реализации случайного процесса X(t)

Тем не менее, можно ввести понятие спектральной плотности среднего квадрата случайной функции, поскольку величина среднего квадрата не зависит от соотношения фаз суммируемых гармоник. Спектральная плотность мощности G XX (ω) , являющаяся усредненной характеристикой совокупности реализаций случайного процесса X(t), представляет собой прямое преобразование Фурье для корреляционной функции: ∞

GXX (ω) =

∫K

−∞

∞

dτ = 2∫ KXX (τ) cos(ωτ)dτ .

− jωτ

XX

(τ)e

(4.1)

0

Обратное преобразование Фурье имеет вид: ∞ ∞ 1 1 jωτ KXX (τ) = G ( ω ) e d ω = GXX (ω) cos(ωτ)dω. XX 2π −∫∞ π ∫0

(4.2)

Преобразования (4.1) и (4.2), связывающие функции G XX (ω) и K XX (τ ) , носят название преобразований Хинчина–Винера. Для установления физического смысла функции G XX (ω) примем в (4.2) τ = 0, тогда ∞ 1 K XX (0) = ∫ G XX (ω)dω . π0 Так как K XX ( 0) выражает среднюю мощность сигнала, то

G XX (ω) дает усредненную энергетическую картину распределения мощности сигнала по частотному спектру, а элементарная состав1 ляющая G XX ( ω ) d ω представляет собой долю средней мощности, π приходящуюся на диапазон частот dω . 37

Задача оптимального приема состоит в рациональном использовании избыточности, а также имеющихся сведений о свойствах полезного сигнала, помехи и канала для увеличения вероятности правильного приема. Результатом воздействия помех является частичная или полная потеря информации, переносимой полезным сигналом. Приемное устройство, осуществляя обработку входного сигнала, должно обеспечить извлечение из принятого сигнала возможно большего количества необходимой информации. Вследствие того, что на вход приемника поступает сумма полезного сигнала и помехи, вероятность правильного приема будет определяться отношением полезного сигнала к помехе. Для повышения вероятности правильного приема и принятия решения должна быть произведена обработка принятого сигнала по схеме, представленной на рис. 4.2. Фильтр обеспечивает улучшение отношения сигнал/помеха, а решающее устройство выполняет главные функции приема (обнаружение, различение или восстановление сигналов). Y(t)=X(t)+ξ(t)

X *(t)

Решающее устройство

Фильтр

Используемые характеристики :

X(t)

GXX (ω) , Gξξ (ω) , P(ai ) , f ( X / ai ) , K XX (τ) , K ξξ (τ) , r12 , r21 .

Рис. 4.2. Блок-схема предварительной обработки принятого сигнала

Рассмотрим задачу обнаружения сигналов. Для обеспечения возможности обнаружения m-мерное пространство признаков должно быть разбито на две области: X 1 и X 2 . Граница этих областей называется решающей поверхностью. В процессе обнаружения решающее устройство определяет, какой области принадлежит вектор-реализация X, и делает заключение о состоянии a i 38

источника. Если X ∈ X

2

, значит источник находится в состоя-

нии a 2 , то есть в принятом сигнале содержится полезный сигнал. Поскольку решающая поверхность многомерна, ее задание и хранение могут встретить значительные трудности. Поэтому многомерный случай приводится к одномерному путем перехода к новой переменной, функционально связанной с вектором X. Эта переменная носит название отношения функций правдоподобия: L(a2 ) f ( X / a2 ) , λ= = L ( a1 ) f ( X / a1 ) где f (X / ai ) = f (x1, x2 ,..., xm / ai ) – многомерная условная плотность распределения вероятностей. Вместо уравнения решающей поверхности в этом случае достаточно запомнить одно число λ 0 , с которым сравнивается текущее значение коэффициента правдоподобия λ . Неравенству λ ≤ λ 0 соответствует X ∈ X 1 и наличие состояния a1 , когда в принятом сигнале отсутствует полезный сигнал. Основными характеристиками качества распознавания являются ошибки распознавания и средние потери. Предположим, что при X ∈ X i принимается гипотеза о наличии состояния a i . Вероятность правильного решения составляет при этом P (a i / X i ) , а вероятность ошибки Piош = 1− P(ai / X i ) . Средняя вероятность ошибки распознавания для всех возможных состояний источника равна

Pош =

∑ P( X i

i

) Piош = 1 − ∑ P ( a i ) ∫ f ( X / a i ) dX , i

Xi

где P( X i ) означает P {X ∈ X i } . Если ошибки распознавания отдельных состояний неравноценны, то для характеристики качества могут быть приняты средние потери (риск). Обозначим через r i j положительное число, определяющее коэффициент потерь от ошибки в результате заключения о состоянии a i , в то время как источник информации находится в

39

некотором другом состоянии a j . При попадании вектора в область

X i условные потери составят

ri = ∑ P(a j / X i )rij , j

а средние потери

r = ∑ P(X i )ri = ∑ P(a j )∑ rij i

j

i

∫ f(X/a

j

)dX .

Xi

При

r ij

этом предполагается, что коэффициенты потерь (i = j ) , связанные с правильными решениями, равны нулю.

Для того чтобы выбрать то или иное правило принятия решения, используют, например, следующие критерии: 1) максимум правдоподобия (критерий Фишера)

λ0 = 1; 2) идеального наблюдателя (критерий Зигерта-Котельникова)

λ0 =

P (a1 ) ; P (a2 )

3) минимального риска (критерий Байеса)

λ0 =

r21 P ( a1 ) . r12 P ( a 2 )

Пример. Необходимо обнаружить постоянный сигнал величиной A на фоне аддитивной помехи с нормальным распределением и средним значением, равным нулю. Метод приема – однократный отсчет. Произвести синтез приемного устройства, работающего на основе критерия максимума правдоподобия, и определить пороговый уровень измерения сигнала X п1 . Так как по условию задачи помеха аддитивна и выборка X представляет одномерную величину, то функции правдоподобия L ( a 2 ) и L ( a 1 ) определяются законом распределения помехи:

40

L(a2 ) = f ( X / a2 ) = L ( a1 ) = f ( X / a 1 ) =

−

1 σ ξ 2π σ ξ 2π

2σξ2

e −

1

( X − A)2

e

X

, (4.3)

2

2σξ

2

.

Отношение правдоподобия при этом

λ = e

−

( X − A )2 + X 2 σ ξ2 2

A

= e

σ

ξ

2

2

= (4.4)

1 ⎤ ⎡ X ⎢ A − 2 ⎥ ⎣ ⎦

.

Графики функций L ( a 2 ), L ( a 1 ) и λ приведены на рис. 4.3. При использовании критерия максимума правдоподобия пороговое значение λ 0 = 1 . Тогда условие для порогового значения входного

сигнала будет иметь вид

e

A2 ⎡ X 1П 1 ⎤ − ⎥ ⎢ σ ξ 2 ⎢⎣ A 2 ⎥⎦

= 1 . Полученное уравне-

1 п

ние имеет единственное решение X − 1 = 0 . A

2

Таким образом, приемное устройство – это устройство сравнения, сопоставляющее входной сигнал с пороговым уровнем A 1 X п1 = . Если амплитуда входного сигнала больше уровня X п , в 2 принятом сигнале содержится полезный сигнал. В данном примере рассматривался частный случай, когда mξ = 0 . В процессе домашней подготовки предстоит решить ряд аналогичных задач, в которых mξ ≠ 0 , а это потребует переосмысления выражений (4.3) и (4.4).

41

L ( ai ) L ( a2 )

L ( a1 )

X

A λ

λ0 = 1 X

X

1 п

Рис. 4.3. Графики функций правдоподобия

L ( ai )

и отношения

функций правдоподобия λ

ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. Вывести выражения порогового уровня измерения сигнала для трех решающих правил. 2. Произвольным образом задать значения отличных от нуля параметров в едином формате (табл. 4.1). Параметры P(ai ) и rij должны отражать существо решаемой задачи и используемого решающего правила. Таблица 4.1 Решающее правило

A

mξ

σξ

P( a1 )

1 2 3

42

P( a2 )

r12

r21

3. Вычислить пороговый уровень X п1 для обнаружения постоянного сигнала величиной A на фоне аддитивной помехи с нормальным распределением и параметрами m ξ , σ ξ . Метод приема – однократный отсчет. Решающее правило 1 – критерий максимума правдоподобия. 4. Вычислить X п2 при условии, что используется решающее правило 2 – критерий идеального наблюдателя. 5. Вычислить X п3 при условии, что используется решающее правило 3 – критерий минимального риска. 6. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, изучить особенности спектральных характеристик случайных сигналов. 2. Внимательно ознакомиться с элементами теории оптимального приема, используя предоставленные программные средства. 3. Проверить правильность вычислений пороговых уровней i X п , i = 1,3 по формулам, выведенным при решении задач в процессе домашней подготовки. Исходные параметры вводятся по мере запроса. В случае неудачи изучить предлагаемые диалоговой программой подсказки и скорректировать входные данные либо значения пороговых уровней. Выход из каждой задачи возможен только при правильном ее решении. 4. Провести исследование влияния априорных данных на процесс принятия решения, используя вычислительные средства задачи № 3. 5. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие трудности возникают при использовании n -мерных плотностей распределения вероятностей случайного процесса для анализа систем передачи информации? 43

2. Какими усредненными характеристиками описываются обычно случайные процессы? 3. Что понимается под математическим ожиданием и дисперсией случайного процесса? 4. Что понимается под корреляционной функцией случайного процесса? 5. Какие случайные процессы называются стационарными? 6. Как обеспечивается улучшение отношения сигнал/помеха ? 7. В чем сущность основной задачи приема сигналов при наличии помех? 8. Что такое функция правдоподобия? 9. Что такое ошибки первого и второго рода? 10. Чему равна вероятность принятия правильного решения? 11. Как оценивается средняя ошибка распознавания? 12. Как оценивается средний риск распознавания? 13. В чем сущность основных критериев распознавания и их достоинства? Лабораторная работа 5 РАЦИОНАЛЬНОЕ КОДИРОВАНИЕ ДВОИЧНОГО ИСТОЧНИКА Цель: изучить практические методы сжатия двоичной информации в условиях частично известной статистики источника и исследовать области их применимости. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Энтропия сообщений q-ных источников при одинаковом количестве n элементов может быть различной в зависимости от статистических характеристик сообщений. Энтропия максимальна, если элементы сообщений равновероятны и взаимно независимы H = nH ( X ) = n log 2 q . Если поступление элементов сообщений не равновероятно, то энтропия снижается 44

⎛ q ⎞ H = n ⎜ − ∑ p i log 2 p i ⎟ . ⎝ i=1 ⎠ Еще меньшей будет энтропия при наличии коррелятивных связей между элементами H = H ( X 1 X 2 ... X n ) = H ( X n ) = n

= ∑ H(X j / X

j −1

).

j =1

Сообщения, энтропия которых максимальна, являются оптимальными с точки зрения наибольшего количества передаваемой информации. Мерой количественной оценки того, насколько данные реальные сообщения по своей энтропии отличаются от соответствующих оптимальных сообщений, является коэффициент сжатия – K сж . Если неоптимальные и оптимальные сообщения характеризуются одинаковой общей энтропией, то справедливы следующие соотношения: nH ( X ) = n " H ( X ) max ,

H ( X ) max n , = H (X ) n" где n – число элементов неоптимальных сообщений, а n " – среднее число элементов оптимальных сообщений. Таким образом, реальные сообщения обладают определенной избыточностью. Избыточность приводит к увеличению времени передачи сообщений, излишней загрузке аппаратуры обработки информации (канала связи). Пусть имеется двоичный источник, который порождает последовательность статистически независимых символов 1 и 0 с вероятностями p и 1 − p (рис. 5.1). Разобьем всю последовательность двоичных символов, порожденных источником, на блоки длиной n (n-блоки). Каждому блоку поставим в соответствие кодовое слово, содержащее некоторое число ni двоичных символов (D=2), это отображение называется кодированием. K сж =

45

Под избыточностью, приходящейся на символ исходной последовательности, будем понимать величину

nn −H , n

Rn (p) =

– средняя длина кодового где nn H = − p log 2 p − (1 − p ) log 2 (1 − p ) – энтропия источника.

ИИ

слова;

010…1100 011…01… n n

000…00 → 000…01 → … 111…11 →

n1 ⎫ n2 ⎪⎪ ⎬nn ⎪ n2 n ⎪⎭

Рис. 5.1. Процесс кодирования для двоичного источника информации

Качество кодирования определяется эффективностью кодирования H H Э= = = HK сж n log 2 D nn / n или, более строго, избыточностью кодирования

R n = sup R n ( p ) . 0 < p <1

Сокращение избыточности Rn позволяет выделять наиболее существенные данные, т.е. только ту часть информации, которая необходима адресату. Такое техническое решение получило название сжатие данных. Существует большое количество различных методов сокращения объемов передаваемых и хранимых данных. Эти методы различаются по ряду признаков: они могут быть необратимыми, обратимыми и квазиобратимыми; ориентированными на аналоговый или дискретный источник; адаптивными или неадаптивными; ра46

ботать в условиях известных или неизвестных статистических характеристик источника сообщений. Классификация обратимых методов сжатия по статистике источника (к обратимому сжатию данных относятся методы, позволяющие восстановить на приемном конце исходную последовательность с абсолютной точностью) приведена на рис. 5.2. Методы сжатия дискретной информации

Статистика не известна

Статистика известна частично

Универсальное кодирование

Статистика известна полностью

Кодирование длин серий

Кодирование по методу Шеннона-Фано

Адреснопозиционное кодирование

Оптимальное кодирование (код Хаффмана)

Итерации простых подстановок Адаптивное кодирование в разрядной плоскости Рис. 5.2. Классификация обратимых методов сжатия дискретной информации

Если источник двоичных сообщений имеет низкую энтропию (H<<1), это означает, что сообщение состоит из последовательности частых символов (например, нулей), вероятность появления которых близка к единице, и редких символов (например, единиц) с небольшой вероятностью появления. В таких случаях обычно используется способ кодирования исходной последовательности, 47

заключающийся в представлении кодом длины серии входящих в нее последовательностей высоковероятных однотипных символов (рис. 5.3). Такой способ получил название метод кодирования длин серий (КДС).

ИИ

n

n

1010...01

0101...11 №

Серии

1 01 001 ... 000...001 000...000

1 2 3

1 2 3

... n n n+1 0

0100... Код k

k

k = ]log 2 ( n + 1)[

Рис. 5.3. Процесс кодирования по методу КДС

Метод адресно-позиционного кодирования (АПК) заключается в переходе от передачи высоковероятных символов сообщения к передаче маловероятных символов и их местоположения в фиксированном интервале. Исходное сообщение, представляющее собой последовательность двоичных символов, разбивается на фиксированные интервалы-отрезки по n символов в каждом. Внутри отрезка символы можно пронумеровать, обозначив тем самым позицию (или адрес) каждого из них. При монотонно возрастающем порядке нумерации адрес маловероятного символа сообщения указывает на "расстояние" его от начала отрезка, т.е. является координатой. Поэтому рассматриваемый способ рационального кодирования сообщений иногда называется координатным (рис. 5.4). Отличие передачи позиций маловероятных символов от передачи кодов длин серий высоковероятных символов сообщения в том, что если в КДС положение очередного маловероятного символа определяется по отношению к предыдущему, то в АПК – относительно некоторых фиксированных элементов последовательности (например, начала отрезка). 48

n ИИ

n

0101... 0... 1

0100...11

k

0010...

k

k = ]log 2 ( n + 1)[ Рис. 5.4. Процесс кодирования по методу АПК

Метод итерации простых подстановок (ИПП – метод Блоха) заключается в многократном повторении простейшего алгоритма кодирования (1-p >> p) 00 → 0 01 → 11 1 → 10 .

Эта операция рекуррентно повторяется до тех пор, пока она приносит желаемый эффект – уменьшается общее число символов в данной последовательности (рис. 5.5). 0 0 0 0 0 1 0 0 0 0 - 10 0 0 11 0 0

-6

0 10 10 0

-6

1 1 1 1 0 •

-5

10 10 10 10 0

Результат сжатия

-9

Рис. 5.5. Процесс кодирования по методу ИПП

Если последовательность двоичных разрядов передаваемого сообщения разбить на группы, а затем к одноименным разрядам 49

всех групп в зависимости от статистики входящих в нее символов применить какой-либо из описанных выше методов статистического кодирования, то можно получить более компактное описание некоторых из этих совокупностей разрядов. Такая адаптивная операция сокращения первоначального объема сообщения называется кодированием в плоскости разряда. Для случая статистической неизвестности было предложено кодирование, названное впоследствии универсальным, такое, что Rn → 0 при n → ∞ . Рассмотрим один из методов универсального кодирования (УК – метод Бабкина). Пусть в n-блоке имеется k единиц и (n-k) нулей. Пронумеруем последовательно нули и единицы, встречающиеся в n-блоке. Пусть Положим

i1 , i 2 , . . . , i k

— номера позиций единиц.

⎛ i − 1⎞ ⎛ i − 1⎞ ⎛ i − 1⎞ b k = ⎜ 1 ⎟ + ⎜ 2 ⎟ + ...+ ⎜ k ⎟, ⎝ 1 ⎠ ⎝ 2 ⎠ ⎝ k ⎠ где ⎛⎜ ν ⎞⎟ – биномиальный коэффициент, причем полагаем ⎜ ⎟ ⎝μ⎠

⎛ν⎞ = 0 ⎜⎜ ⎟⎟ ⎝μ⎠

при ν < μ. В этом случае справедливы следующие утверждения: ⎛ n ⎞ 1. 0 ≤ b k ≤ ⎜⎜ ⎟⎟ − 1 . ⎝ k ⎠

2. Соответствие между n-блоками и парами чисел ( k , b k ) взаимно однозначно. Тогда кодовое слово, соответствующее n-блоку, определяется

(

как упорядоченная пара двоичных наборов k , b k

) . При этом

длина кодового слова

⎤ ⎛ n⎞ ⎡ l n , k = ]log 2 ( n + 1)[ + ⎥ log 2 ⎜ ⎟ ⎢ ⎝ k⎠ ⎣ ⎦ где ]x[ – наименьшее большое целое.

,

Пример. Пусть n = 8 и последовательность, порожденная источником, имеет вид: 50

k = 5,

i1

i2

1

2

3

0

1

1

i3

i4

i5

4

5

6

7

8

0

1

1

0

1

,

i1 = 2 i2 = 3 i3 = 5 i4 = 6 i5 = 8 ,

ln ,k

= 4 + 6 .

Построим для этого случая таблицу вычисления биномиальных коэффициентов (табл. 5.1). Таблица 5.1

n

i5 i4

i3 i2

i1

8 7 6

⎛ n − 1⎞ ⎜ ⎟ ⎝ 1 ⎠

⎛ n − 1⎞ ⎜ ⎟ ⎝ 2 ⎠

⎛ n − 1⎞ ⎜ ⎟ ⎝ 3 ⎠

⎛ n − 1⎞ ⎜ ⎟ ⎝ 4 ⎠

⎛ n − 1⎞ ⎜ ⎟ ⎝ 5 ⎠

21 6 1

7

21

35

35

6 5

15 10

20 10 4 1 0

15 5 1

5 4 3

4

6

3 2

2 1

1 0

3 1 0 0

0

0 0

0 0

0

0

0

0

0

0

В таблице слагаемые, соответствующие искомым биномиальным коэффициентам, обведены, bk = 32 , ( k , bk ) → ( 0101,100000) . Декодирование производится в обратном порядке; так как k = 5 , ищем в пятом столбце наибольшее число, меньшее или равное 32. Вычисляем разность 32-21=11. В четвертом столбце имеем наибольшее число, меньшее или равное 11, и т.д. Таким же образом декодирование производится при любом n. 51

Пример. Пусть n=100. Дадим оценку (табл. 5.2).

ln ,k

для различных k

Таблица 5.2

k

ln ,k

1 2 3 4 ... 10 ... 20

7+ 7 7+13 7+18 7+23 ... 7+45 ... 7+70

Kсж = n / ln,k 7,14 5 4 3,33 ... 1,92 ... 1,30

В условиях полной статистики источника применяют методы кодирования Шеннона-Фано и Хаффмана. Множество известных коммерческих архиваторов в той или иной степени используют идеи, положенные в основу метода оптимального кодирования Хаффмана. ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Выбрать произвольный n-блок небольшой длины и провести его сжатие с использованием методов КДС, АПК, ИПП и УК. 3. Вычислить основные количественные характеристики и сопоставить их между собой. 4. Продумать последовательность действий для получения семейства кривых K сж = F ( p ) АПК, КДС, ИПП, УК

при фиксированном значении параметра n, используя программную реализацию четырех методов сжатия. 5. Заготовить оси координат для нанесения семейства кривых для двух различных значений n. 6. Отразить подготовку в лабораторном отчете.

52

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, детально разобраться в основных принципах сжатия данных. 2. Проверить правильность результатов кодирования, полученных при домашней подготовке. 3. Исследовать методы сжатия путем построения семейства кривых K сж = F ( p ) АПК, КДС, ИПП, УК для двух различных, но фиксированных значений параметров n. Параметры n задаются преподавателем. 4. Исследовать чувствительность методов сжатия к расположению единиц в n-блоке при фиксированной частоте появления "1". 5. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Поясните сущность понятия энтропии. 2. В каких единицах измеряется энтропия? 3. Как определяется энтропия дискретной системы с равновероятными и неравновероятными состояниями? 4. Чему равна энтропия при неравновероятном и взаимозависимом распределении элементов системы? 5. Что понимается под избыточностью сообщений? 6. Что понимается под операцией кодирования? 7. Что является мерой количественной оценки избыточности? 8. Какой метод кодирования наиболее предпочтителен при полностью известной статистике? 9. Как можно оценить длину кодового слова при использовании универсального метода кодирования? 10. Какие методы кодирования, изучаемые в данной работе, чувствительны к расположению единиц в блоке? 11. Какой метод кодирования дает наилучший результат в условиях полностью неизвестной статистики? 12. Как длина исходного блока влияет на K сж ? 53

Лабораторная работа 6 ИССЛЕДОВАНИЕ ИНФОРМАЦИОННОЙ ПРОПУСКНОЙ СПОСОБНОСТИ ДВОИЧНОГО КАНАЛА Цель: изучить принципы вычисления информационной пропускной способности двоичного канала и исследовать зависимость ее от характеристик канала. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Для анализа информационных возможностей удобно пользоваться обобщенной информационной моделью канала связи, представленной на рис. 6.1. Если канал используется для передачи кодоимпульсных сигналов, он называется дискретным. Под каналом связи (или передачи информации) принято понимать совокупность аппаратных средств, предназначенных для передачи сигналов. Канал связи преобразует последовательность входных событий ξ 1 , ξ 2 ,..., ξ j ,... , каждое из которых представляется точкой

ξ j = xk ∈ X

входного пространства X, в выходные события

η 1 , η 2 ,..., η j ,... , каждое из которых представляется точкой η j ( ξ j ) = y i ∈ Y выходного

пространства Y. Преобразование

управляется условным распределением вероятностей p ( y i / x k ) . Канал, в котором p ( y i / x k ) одно и то же для всех последовательных входных и выходных событий, называется стационарным каналом без памяти. В теории информации доказывается, что информационная пропускная способность дискретного стационарного канала может быть вычислена по формуле:

C = max H ( X ; Y ) , { p ( x k )}

где H ( X ; Y ) – взаимная энтропия. В свою очередь, 54

(6.1)

H ( X ; Y ) = H (Y ) − H (Y / X ) , H (Y ) = − ∑ p ( y i ) log 2 p ( y i ) , Y

H (Y / X ) = − ∑ ∑ p ( x k ) p ( yi / x k ) log 2 p ( yi / x k ) , X

(6.2)

Y

p ( yi ) = ∑ p ( x k ) p ( y i / x k ) . X

ξ j → xk ∈ X

•••• ИИ

η j → yi ∈ Y

••••

p(yi / x k )

КД

ДК

ПИ

Y = LY

X = LX

p ( y 1 / x1 ) p ( yi / x k ) = ... p ( y1 / x L X )

... ... ...

p ( y L Y / x1 ) ... p ( y LY / x L X )

Рис. 6.1. Структура дискретного канала: ИИ – источник информации; КД – кодер; ДК – декодер; ПИ – потребитель информации

Под пропускной способностью канала понимается максимальное среднее значение информации на символ, которое можно передать по данному каналу. Пропускную способность канала С при передаче можно достичь надлежащим выбором источника информации и способа кодирования, которые в общем случае и определяют вероятности p(xk ) посылки сообщений. Дискретный двоичный канал (ДК) без памяти задается матрицей условных (переходных) вероятностей 1 − p1 p1 . p( y / x ) = i k p2 1 − p2 55

Матрице соответствует граф переходных вероятностей, приведенный на рис. 6.2.

1− p (0) x1

(0) y1 p

p

(1) x2

(1) y2

1− p Рис. 6.2. Граф-схема ДК

Вычислим пропускную способность ДК. Пусть

p( x1 ) = z, p( x2 ) = 1 − z . Тогда p ( y1 ) = z (1 − p1 ) + (1 − z ) p 2 = α z + p 2 ,

p ( y 2 ) = zp1 + (1 − z )(1 − p 2 ) = (1 − p 2 ) − α z , где α = 1 − p1 − p 2 . Подставляя эти значения в (6.2), получаем H (Y ) = −(αz + p2 ) log2 (αz + p2 ) − [(1 − p2 ) − αz ]log2 [(1 − p2 ) − αz ], H (Y / X ) = − z (1 − p1 ) log2 (1 − p1 ) − zp1 log2 p1 − (1 − z) p2 log2 p2 − − (1 − z )(1 − p2 ) log2 (1 − p2 ). Находим экстремум, приравнивая нулю производную,

∂H ( X ; Y ) = 0. ∂z

После несложных преобразований находим

z0 = где

1 − p2 D , αD

D = 1 + exp( − B / α ); B = p1 ln p1 + (1 − p1 ) ln(1 − p1 ) − p 2 ln p 2 − (1 − p 2 ) ln(1 − p 2 ). 56

Итак, информационная пропускная способность канала вычисляется по формуле

C = H (X ;Y )

z= z0

.

Дадим физическую интерпретацию переходных вероятностей: 0 p (0 / 0) = 1 − p1 = pпп

– правильный прием "0";

p (1 / 1) = 1 − p2 = p1пп

– правильный прием "1";

0 p (1 / 0) = p1 = pнп

– неправильный прием "0";

p (0 / 1) = p2 = p

– неправильный прием "1".

1 нп

Вероятность того, что при передаче одного канального символа возникает ошибка, будет иметь вид

p ош = p ( x1 ) p 1 + p ( x 2 ) p 2 . Двоичный симметричный канал (ДСК) является частным случаем ДК, когда для переходных вероятностей выполняется условие p 1 = p 2 = p . Пропускная способность ДСК вычисляется по формуле LY

C = log 2 Y + ∑ p j log 2 p j = 1+ p log 2 p + (1− p) log 2 (1− p) . j =1

Дискретный двоичный симметричный канал со стиранием (ДСКС) без памяти задается матрицей условных вероятностей

p(yi / xk ) =

1− p − q p q . p 1− p − q q

Матрице соответствует граф переходных вероятностей, приведенный на рис. 6.3. Информационная пропускная способность ДСКС, который является каналом симметричным по входу, вычисляется по хорошо известной формуле:

57

LY

C = max H (Y ) + ∑ p j log2 p j = { p ( xk )}

j =1

= (1 − q)[1 − log2 (1 − q)] + (1 − p − q) log2 (1 − p − q) + p log2 p . Дискретный канал называется симметричным по входу, если все строки матрицы переходных вероятностей образованы перестановками элементов первой строки. Физическая интерпретация переходных вероятностей состоит в следующем:

p (0 / 0) = p (1 / 1) = 1 − p − q = pпп – правильный прием ; p (0 / 1) = p (1 / 0) = p = pно

– необнаружение ошибки;

p (c / 1) = p (c / 0) = q = pоо

– обнаружение ошибки.

При этом выполняются условия

pош = pно + pоо ; pпп + pно + pоо = 1.

(6.3) Из соотношений (6.3) видно, что ДСКС соответствует реализации ДСК с контролем. При известных значениях длины кода N и числе информационных разрядов k можно найти p и q, а следовательно, и пропускную способность канала ДСКС, по которому передается, например, циклический код (N, k). 1− p − q (0)

x1

p

q

y1 ( 0 ) y 3 (C )

(1)

x2

p

q

y 2 (1)

1− p − q Рис. 6.3. Граф-схема ДСКС

Для такого канала (с учетом процесса коррекции ошибок) справедливы следующие соотношения: 58

2 −( N − k )

– условная вероятность необнаружения ошибки при условии, что она имеет место;

pно = 2 − ( N − k ) pош

– вероятность возникновения необнаруживаемой ошибки;

pоо = [1− 2 −( N −k ) ]pош

– вероятность возникновения обнаруживаемой ошибки;

1− (2 − k − 2 − N )

[1− 2 − ( N −k ) ]pош [1− (2 − k

– условная вероятность неправильной коррекции ошибки при условии, что она имеет место и обнаруживается; − 2 − N )] – вероятность неправильной коррекции.

Пропускную способность дискретного канала с шумом определяют как максимально возможную скорость передачи информации. Формула (6.1) показывает, что дискретный канал может быть охарактеризован вполне определенной пропускной способностью. На первый взгляд может показаться, что пропускная способность канала принципиально снижается с повышением требований к верности передачи информации. При введении избыточности, например, передачей несколько раз одного и того же сообщения, очевидно, увеличивается помехоустойчивость (уменьшается число ошибок), но одновременно и понижается скорость передачи информации. Иными словами, задаваясь допустимым процентом ошибок, мы тем самым как бы определяем верхний предел скорости. На самом деле это не так. Основная теорема для дискретного канала, впервые сформулированная Шенноном, утверждает, что если дискретный источник создает сообщения со скоростью H ( X ) и если H ( X ) ≤ C , то существует такая система кодирования, что сообщения источника могут быть переданы по каналу с произвольно малой частотой ошибок. Если H ( X ) > C , то можно закодировать сообщения таким образом, что потери информации в канале станут меньше, чем H ( X ) − C + ε , где ε > 0 сколь угодно мало. 59

Не существует способа кодирования, обеспечивающего потери в канале, меньше чем H ( X ) − C . Теорема не дает конкретного метода построения кода, обеспечивающего передачу со скоростью, равной пропускной способности канала. Однако это не уменьшает фундаментального значения теоремы, которая в области помехоустойчивого кодирования стимулирует поиск новых оптимальных корректирующих кодов и дает оценку их эффективности. ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Выбрать произвольные условные вероятности p1 , p 2 , p , q и рассчитать информационные пропускные способности ДСК и ДСКС. 3. Продумать последовательность действий при построении поверхности C = F ( p1 , p 2 ) для ДК и поверхности C = F ( p , q ) для ДСКС, используя инструментальные средства диалоговой программы. 4. Подготовить два "куба", выполненных по единому образцу и представленных на рис. 6.4, в пределах которых будут сосредоточены обе поверхности. C = F ( p1 , p2 ) 1

C = F ( p, q )

1

p1 p

p2

1

q Рис. 6.4. Границы существования информационной пропускной способности каналов 60

5. Вывести аналитические выражения для p и q ДСКС, реализующего обнаруживающую и корректирующую способности. 6. Продумать последовательность действий при вычислении C двоичного канала, реализующего заданный циклический код (N, k). 7. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие и графические средства диалоговой программы, изучить принципы оценки информационной пропускной способности двоичных каналов. 2. Проверить расчеты, выполненные при подготовке, используя программную реализацию алгоритмов вычисления пропускной способности. 3. Исследовать ДК путем построения поверхности C = F ( p1 , p 2 ) *. 4. Исследовать ДСКС путем построения поверхности C = F ( p , q ) *. 5. Вычислить С ДСКС при реализации заданного циклического кода (N, k), обладающего только обнаруживающими способностями. Варианты приведены в табл. 6.1. 6. Вычислить C ДСКС при реализации заданного циклического кода (N, k), обладающего обнаруживающими и корректирующими способностями. Таблица 6.1

(N, k)

pош

(7,4) (15,11) (31,26)

0.05 0.05 0.05

2

− ( N −k )

1− 2

0.125 0.063 0.031

− ( N −k )

0.875 0.937 0.969

1 − (2

−k

− 2−N )

0.94532 0.99954 0.99999

7. Сопоставить полученные C ДСКС с пропускной способностью канала без контроля ДСК при тех же исходных данных. 8. Результаты отразить в лабораторном отчете. ______________________________________________________________ * Для более быстрого достижения цели оценки C производить на боковых гранях "куба". 61

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Чем вызвана необходимость согласования сигнала с каналом передачи информации? 2. Что понимается под скоростью передачи информации и пропускной способностью канала? 3. Что характеризует матрица переходных вероятностей? 4. Каким образом вычисляется пропускная способность дискретного канала с помехами? 5. Что понимается под стационарным каналом без памяти? 6. В чем сущность теоремы Шеннона для дискретного канала с помехами? 7. Какими свойствами обладают каналы, симметричные по входу и выходу? 8. Каким образом можно оценить ненадежность передачи? 9. Как можно оценить условную вероятность обнаружения ошибки при заданной избыточности? 10. Как можно оценить условную вероятность правильной коррекции ошибки при заданной избыточности? Лабораторная работа 7 КОРРЕКТИРУЮЩИЕ КОДЫ БОУЗА–ЧОУДХУРИ–ХОКВИНГЕМА Цель: изучить принципы построения наиболее эффективных циклических кодов, исправляющих ошибки произвольной кратности. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Из основной теоремы Шеннона следует, что если по каналу передавать информацию со скоростью, не превышающей его информационную пропускную способность, то существует такой способ кодирования, при котором сообщения могут быть переданы с произвольно малой ненадежностью. В теореме не затрагивается вопрос о путях построения кода, обеспечивающего указанную идеальную передачу. Тем не менее, значение ее огромно, поскольку, обосновав принципиальную воз62

можность такого кодирования, она мобилизовала усилия специалистов на разработку конкретных кодов. Способность кода обнаруживать и исправлять ошибки, обусловлена наличием избыточных символов. На вход кодирующего устройства канала поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из N двоичных символов, причем N > k (рис. 7.1). E ( x) N

k

ИИ

КДии

КДк

N

ДКк

Канал A ( x)

k

ДКии

ПИ

A*(x)

Рис. 7.1. Средства помехоустойчивого кодирования k

Всего может быть 2 различных входных последовательностей и 2 N различных выходных последовательностей. Из общего числа 2 N выходных последовательностей только 2 k соответствует входным (назовем их разрешенными кодовыми комбинациями). Остальные 2 N − 2 k возможных выходных последовательностей для передачи не используются (назовем их запрещенными кодовыми комбинациями). Возможные трансформации разрешенных кодовых комбинаций при прохождении по каналу с помехами представлены на рис. 7.2. Число возможных последовательностей длины N, очевидно, больше, чем число возможных последовательностей длины k. Следовательно, множество всех последовательностей длины N может быть разбито на k непустых классов, и каждому классу сопоставлена одна из входных последовательностей длины k. Можно так закодировать последовательность длины k (выбрать представителя соответствующего класса последовательностей длины N), что воздействие ошибок на выбранную последовательность длины N в канале выводит ее из соответствующего ей класса с вероятностью сколь угодно малой. Это позволяет определить на приемной стороне канала, к какому классу принадлежит искаженная ошибками 63

принятая последовательность длины N, тем самым точно восстановить исходную последовательность символов длины k.

A1 A2 A3 ... A2 k

A1* ⎫ ⎪ A2* ⎪ ⎪ A3* ⎬ ... ⎪ ⎪ A2*k ⎪⎭

Разрешенные комбинации

... ⎫ ⎬ A2*N ⎭

Запрещенные комбинации

Рис. 7.2. Комбинации возможных переходов вследствие ошибок

Коды Боуза–Чоудхури–Хоквингема (БЧХ), как одни из самых эффективных кодов, исправляющих ошибки произвольной кратности, нашли широкое применение в практике помехоустойчивого кодирования. Однако процедура их построения для заданной длины кода N и максимальной кратности исправляемых ошибок T достаточно трудоемкая. Изложим кратко принципы, лежащие в основе построения корректирующих кодов БЧХ. Эти коды – разновидность циклических кодов, которые определяются через элементы расширенного поля Галуа. Полем называется множество с двумя определенными на нем операциями – сложением и умножением. Поле с q элементами, если оно существует, называется конечным полем или полем Галуа и обозначается через GF(q). Примитивный элемент поля GF(q) – это такой элемент α поля, все элементы которого, за исключением нуля, могут быть представлены в виде степени элемента α. Подмножество GF(e) в GF(q) называется подполем, если оно само является полем относительно наследуемых из GF(q) операций. В этом случае исходное поле GF(q) называется расширением поля GF(e). Пусть GF(e) – некоторое поле, GF(q) – расширение поля GF(e), построенное по примитивному многочлену p(z), и β – элемент 64

GF(q). Тогда простой многочлен F(x) наименьшей степени над GF(e), для которого F (β) mod p ( z ) ≡ 0 , называется минимальным многочленом элемента β над GF(e).

В табл. 7.1 задано представление поля GF (2 4 ) как расширение поля GF(2), построенное по примитивному многочлену p (z ) = z 4 + z + 1 . Таблица 7.1 4

Поле GF ( 2 ) в виде Степени Многочлена Кода

0 α α

1

0 1 z

0000 0001 0010

2

α

2

z

α

3

α

4

z3 z +1

α

5

z2 + z

α

6

z +z

α

7

z3 + z + 1

3

2

α8

z2 + 1

α

z +z

9

3

α 10

z2 + z + 1

α 11

z3 + z2 + z

α 12

z3 + z2 + z + 1

α 13

z3 + z2 + 1

α 14

z3 + 1

0011 0100 0011 0110 1100 1011 0101 1010 0111 1110 1111 1101 1001

Минимальные многочлены при

αi

x +1 F1 (x) = x4 + x + 1 x4 + x + 1 F3 (x) = x4 + x3 + x2 + x + 1 x4 + x + 1 F5 (x) = x2 + x + 1 x4 + x3 + x2 + x + 1 F7 (x) = x4 + x3 + 1 x4 + x + 1 x4 + x3 + x2 + x + 1 x2 + x + 1 x4 + x3 + 1 x4 + x3 + x2 + x + 1 x4 + x3 + 1 x4 + x3 + 1

В нее включены также минимальные многочлены над GF(2) для всех элементов из поля GF ( 2 4 ) , где α = z – примитивный элемент

GF ( 2 4 ) . Пусть β = z 3 65

– элемент

GF (2 4 ) . Тогда

F (x) = x 4 + x 3 + x 2 + x + 1 – минимальный многочлен элемента z 3 над GF(2), так как F (β) mod p ( z ) = = [( z 3 ) 4 + ( z 3 )3 + ( z 3 ) 2 + ( z 3 ) + 1] mod( z 4 + z + 1) ≡ 0 . Коды БЧХ строятся по заданным N и T. Значение k (число информационных разрядов) неизвестно, пока не найден порождающий многочлен кода G(x). В общем случае

G ( x ) = НОК [ F1*C 0 ( x ), F3*C 0 ( x ),..., Fi*C 0 ( x ),..., FФ *С0 ( x )] , где Ф ≤ D − 2 , D ≥ 2T + 1 ( D – минимальное расстояние Хэмминга кода БЧХ). Отметим, что минимальные многочлены для любой четной степени всегда уже содержатся в одной из предыдущих строк табл. 7.1. Длина кода БЧХ, как правило, определяется из выражения N = 2 − 1 , где m – любое целое число. Иногда возникает ситуация, когда вычисленное по формуле m = log 2 ( N + 1) получается не целым. Тогда необходимо пользоваться формулой m = log 2 ( NC 0 + 1) , подбирая минимальное C 0 такое, чтобы результат оказался целочисленным. Число проверочных разрядов кода БЧХ r ≤ mT , отсюда число информационных разрядов 2m − 1 k≥ − mT . C0 m

Если r >

2m −1 , то код БЧХ не определен, так как число провеC0

рочных разрядов не может быть больше длины кода. Например, порождающий многочлен кода длины N=21, служащий для исправления двукратных ошибок T=2, получается следующим образом. Формула m = log 2 ( N + 1) к положительным результатам не приводит, а формула m = log 2 ( NC 0 + 1) при C0 дает m=6. Далее обращаемся к таблице минимальных многочленов (табл. 7.2), которая строится из таблиц, аналогичных табл. 7.1, но при разных значениях m. Выбираем из табл. 7.2 минимальные мно66

гочлены F1 ( x) и F3 ( x) , так как D − 2 = 3 . Умножаем индексы выбранных многочленов на C0 и окончательно получаем G ( x) = НОК[ F3 ( x), F9 ( x)] =

= НОК[ x6 + x 4 + x 2 + x + 1, x3 + x 2 + 1] = = x 9 + x8 + x 7 + x 5 + x 4 + x + 1 . Следовательно, r = deg G (x ) = 9 и k = 12 . Строки образующей матрицы кода (21,12) находятся как остаток от деления произведения x j G ( x ) на двучлен x N + 1 (рис. 7.3). Таблица 7.2

m

i

1 3 5 7 9 11 13 15 17 19

M 21,12 =

2 111 (1)

3 1011 (1) 1101 (3) 1

4 10011 (1) 11111 (2) 111 (3) 11001 (7) 1 1 1

000000000001:110110011 000000000010:011010101 000000000100:110101010 000000001000:011100111 000000010000:111001110 000000100000:000101111 000001000000:001011110 000010000000:010111100 000100000000:101111000 001000000000:101000011 010000000000:100110101 100000000000:111011001

67

5 100101 (1) 111101 (2) 110111 (3) 101111 (5) 101001 (7) 111011 (15) 1 1

6 (T) 1000011 (1) 1010111 (2) 1100111 (3) 1001001 (4) 1101 (5) 1101101 (6) 1011011 (7) 1110101 (10) 1100111 (10) 1011011 (10)

Рис. 7.3. Образующая матрица кода БЧХ (21,12)

Традиционный подход исправления ошибок достаточно трудоемкий, так как получить

T

⎛ N ⎞ опознавателей не представляется

∑ ⎜⎝ i ⎟⎠ i=1

целесообразным. Воспользуемся следующим алгоритмом декодирования. Допустим, что передавалась кодовая комбинация A(x), построенная на основе образующей матрицы кода БЧХ (N, k) с порождающим многочленом G(x), способным исправлять ошибки кратности T включительно. В результате воздействия помех в канале связи в приемнике получена комбинация A*(x)=A(x)+E(x), где E(x) – многочлен ошибки. Делим A*(x) на G(x) и вычисляем вес W полученного остатка. Если W>T, производим циклический сдвиг предыдущего делимого влево на один разряд и опять выполняем деление на многочлен G(x). Эта процедура повторяется до получения остатка с весом не больше T. Если W≤T, складываем последнее делимое с полученным остатком и производим циклический сдвиг полученной комбинации вправо на столько разрядов, на сколько осуществлялся сдвиг влево. Получаем истинную переданную комбинацию. Процесс исправления ошибок для кода (21,12) представлен на рис. 7.4. Программные средства построения кодов БЧХ реализуют вышеприведенные процедуры и предназначены для проектирования кодов БЧХ умеренных длин, так как при больших длинах они становятся не лучшими из известных кодов. Целесообразность создания программных средств следует, главным образом, из того, что полное понимание кодов БЧХ, по всей видимости, является наилучшей отправной точкой для изучения многих других классов кодов. ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Построить порождающий многочлен

G ( x ) = НОК [ F1*C 0 ( x ), F3*C 0 ( x ),..., Fi*C 0 ( x ),..., FФ *С 0 ( x )] и образующую матрицу 68

M N ,k = I kT,k

: : BN − k ,k :

кода БЧХ со следующими параметрами: N=7, T=2. 3. Продемонстрировать процесс исправления построенным кодом произвольной двукратной ошибки, задаваемой вектором E(x). 4. Отразить подготовку в лабораторном отчете. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие средства диалоговой программы, изучить принципы построения кодов БЧХ. 2. Построить порождающие многочлены Передаваемое сообщение: A(X)= 110000000000011101100. Кратность ошибки: T= 2. Вектор ошибки: E(X)= 110000000000000000000. В результате действия помех в канале связи на приемном конце была принята комбинация: A"(X)=000000000000011101100. Проводим деление принятой комбинации на G(X) . Цикл N 1 Остаток : 11101100 с весом W = 5. Т.к. W>T ,то надо произвести циклический сдвиг A"(X) влево на 1 разряд и снова произвести деление на G(X) . Цикл N 2 Остаток : 111011000 с весом W = 5. Т.к. W>T ,то надо произвести циклический сдвиг A"(X) влево на 1 разряд и снова произвести деление на G(X) . Цикл N 3 Остаток : 11 с весом W = 2. Теперь, когда W ≤ T , можно произвести сложение по модулю 2 циклически сдвинутой комбинации A"(X) и полученного остатка. Комбинация A"(Х) ,циклически сдвинутая влево на 2 разряда: 000000000001110110000. Сумма циклически сдвинутой комбинации A"(X) и полученного остатка: 000000000001110110011. Наконец, проведем обратный циклический сдвиг этой суммы вправо на 2 разряда. Вы получили переданное сообщение: 110000000000011101100.

Рис.7.4. Процесс исправления ошибок 69

G ( x ) = НОК [ F1*C 0 ( x ), F3*C 0 ( x ),..., Fi*C 0 ( x ),..., FФ *С 0 ( x )] и образующие матрицы

M N ,k = I

T k ,k

: : BN − k ,k :

ряда кодов БЧХ. Значения длин кодов N задаются преподавателем, параметр T выбирается произвольно. 3. Для каждого кода БЧХ длиной N определить максимальную кратность исправляемых ошибок T. 4. Выполнить основные этапы процесса исправления ошибок. Исходные коды A(x) и векторы ошибок E(x) выбираются произвольно. 5. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие коды называются корректирующими? 2. В чем сущность помехоустойчивого кодирования? 3. Как определяется минимальное расстояние Хэмминга между кодовыми комбинациями? 4. Какова связь обнаруживающей способности кода с минимальным расстоянием Хэмминга? 5. Какова связь корректирующей способности кода с минимальным расстоянием Хэмминга? 6. Каким образом строится образующая матрица циклического кода? 7. Какие требования предъявляются к порождающему многочлену циклического кода БЧХ? 8. Сколько разрешенных комбинаций имеет циклический код с образующей матрицей |1:111111|? 9. Какова максимальная кратность исправляемой ошибки циклического кода (7,1)? 10. Дайте определение минимального многочлена. 11. Покажите связь числа проверочных разрядов кода БЧХ с числом информационных разрядов. 70

12. Какими показателями можно оценивать качество корректирующих кодов? Лабораторная работа 8 ПОСТРОЕНИЕ КОДИРУЮЩИХ И ДЕКОДИРУЮЩИХ УСТРОЙСТВ ЦИКЛИЧЕСКОГО КОДА ХЭММИНГА Цель: изучение и исследование принципов построения структур многоканальных кодеров и декодеров циклического кода Хэмминга, исправляющего однократные ошибки. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Для кодирования и декодирования циклических кодов применяются многотактные линейные схемы, называемые часто фильтрами или сдвигающими регистрами с обратными связями. Основными компонентами этих схем являются элемент задержки на один такт и сумматор по модулю 2. Структура фильтра описывается матрицей связей между его элементами

M = m ij , где

i , j = 1, r ,

r – количество элементов задержки в фильтре, а m ij = 1 ,

если выход j -го элемента задержки связан со входом i -го элемента задержки, в противном случае mij = 0 . Вектор-столбцам матрицы M поставим в соответствие полиномы r

μ j ( x) = ∑ mij x i −1 ,

j = 1, r .

i =1

Тогда матрицу M можно записать в виде

M = μ1 ( x), μ 2 ( x ),..., μ r ( x) . Полиномы μ j (x) выберем таким образом, чтобы 71

μ 1 ( x ) ≡ g 1 + g 2 x + ... + g r x r −1 ≡ x − 1 , ⎫ ⎪ μ 2 ( x ) ≡ xμ1 ( x ) ≡ 1 , ⎪ ⎪ 2 μ 3 ( x ) ≡ x μ1 ( x) ≡ x , ⎬ mod g ( x ) , ⎪ ... ⎪ ⎪ μ r ( x ) ≡ x r −1μ 1 ( x ) ≡ x r − 2 ⎭ 2 r где g ( x) = 1 + g1 x + g 2 x + ... + g r x – порождающий многочлен. Тогда схема, описываемая матрицей связей

g1 g2

1 0

0 1

0 0

... 0 0

M = x − 1 ,1 , x ,..., x r − 2 = g r −1 gr

... ...

0 0 ,

... ...

1 0

позволяет выполнять деление на полином g ( x ) . Действительно, если исходному состоянию

фильтра

Ω

(0)

полином

Ω

(0)

= ( ω1 , ω 2 ,..., ω r )

поставить

( x ) = ω1 + ω 2 x + ... + ω r x

в

соответствие

r −1

, то состояние фильтра в следующем такте (на вход схемы информация не поступает) равно

Ω (1) ( x ) ≡ Ω ( 0 ) M t = ω1 x − 1 + ω 2 + ω 3 x + ... + ω r x r − 2 ≡ ≡ ( ω1 + ω 2 x + ... + ω r x r −1 ) x −1 = Ω ( 0 ) ( x ) x −1 mod g ( x ), где M t – транспонированная матрица связей. Входную цепь фильтра построим таким образом, чтобы Ω ( i ) ( x ) ≡ [ Ω ( i − 1 ) ( x ) + s i − 1 ] x − 1 mod g ( x ) , т.е. последующее состояние вычисляется прибавлением входного символа к содержимому фильтра и однократным сдвигом его содержимого. ( 0) Если начальное состояние Ω ( x) = 0 и на вход фильтра поступает последовательность символов 72

s 0 , s1 ,..., s n −1 , а эта по-

следовательность соответствует коэффициентам произвольного n −1 полинома степени n − 1 : S ( x) = s0 + s1 x + ... + s n −1 x , то фильтр будет последовательно принимать состояния

⎫ ⎪ Ω ( 2 ) ( x) ≡ ( s0 x −1 + s1 ) x −1 = s0 x −2 + s1 x −1 ,⎪ ⎬ mod g ( x) . ... ⎪ (n) −n −( n −1) n −1 ⎪ Ω ( x) ≡ s0 x + s1 x + ... + sn−1 x ⎭ Ω (1) ( x) ≡ s0 x −1 ,

Следовательно, Ω

(n)

( x ) ≡ s 0 + s1 x + ... + s n −1 x n −1 mod g(x) ,

так как x ≡ 1 mod g (x) . n

После поступления последнего символа

sn−1 содержимое

фильтра будет равно остатку от деления полинома S (x) на g (x ) . Структура рассмотренного фильтра, описываемого матрицей связи, приведена на рис. 8.1, которая может быть использована для вычисления контрольных разрядов разделимого циклического кода. Кодер работает следующим образом. Сначала ключ находится в 1-м положении, и информационные разряды поступают на вход фильтра, который вначале находится в нулевом состоянии, и непосредственно в линию связи. Затем ключ переключается во 2-е положение. В этом случае обратная связь в фильтре размыкается и контрольные разряды последовательно "выдвигаются" в линию. Таким образом, к концу передачи кодового слова фильтр оказывается в нулевом состоянии. Формально работа кодера описывается следующим образом. После поступления k информационных символов содержимое фильтра равно

Ω ( k ) ( x) ≡ s 0 x − k + s1 x − k +1 + ... + s k −1 x −1 ≡ ≡ x − k ( s 0 + s1 x + ... + s k −1 x k −1 ) ≡ x −k S ( x ) ≡ x n − k S ( x) mod g ( x), которое совпадает с контрольным вектором. 73

Рассмотренные одноканальные кодеры применяются в системах последовательного действия, где передача символов осуществляется последовательно во времени. В ряде устройств современных управляющих систем используется параллельно-последовательный принцип передачи информации. При параллельнопоследовательной передаче информационное слово разбивается на части длиной ν разрядов, эти ν -разрядные части передаются последовательно. В этом случае необходимо уметь строить линейные фильтры (кодеры), содержащие ν входов и ν выходов. Последовательные состояния и значения выхода рассмотренных одноканальных линейных фильтров описываются матричными уравнениями

Ω( i ) = Ω( i−1) ⋅ Mt + si ⋅ F , y i = Ω ( i −1) ⋅ B + si ⋅ Ψ , Ω ( i ) = ( ω1( i ) ,..., ω (ri ) ) – вектор состояния фильтра в момент времени ( i ) ; M t – транспонированная матрица связей; si ( y i ) –

где

значение входного (выходного) символа в момент времени ( i ) ; F – матрица связей (1× r ) между входом и элементами задержки фильтра; B – матрица связей (r × 1) между элементами задержки и выходом фильтра; Ψ – матрица связей (1× 1) между входом и выходом фильтра. Если известны M t , F , B и Ψ , то соответствующие уравнения для ν -канального аналога фильтра, содержащего ν входов и ν выходов, имеют следующий вид (известный результат из математического аппарата линейных последовательностных машин):

Ω( i ) = Ω( i −1) ⋅ M tν + S ( i ) ⋅ F ∗ , Y ( i ) = Ω( i −1) ⋅ B∗ + S ( i ) ⋅ Ψ∗ , = ( s1(i ) ,..., sν( i ) ) – входной вектор в момент времени ( i ) ; = ( y1( i ) ,..., y ν(i ) ) – выходной вектор в момент времени ( i ) ;

где S

Y (i )

(i )

74

B∗ = B Mt ⋅ B ... Mtν −1 ⋅ B – матрица связей ( r × ν ) между элементами задержки и

F∗ =

F ⋅M F ⋅M

ν −1 t ν −2 t

...

ν выходами фильтра;

– матрица связей ( ν × r ) между входами фильтра

F и элементами задержки;

Ψ F ⋅ B F ⋅ M t ⋅ B ... F ⋅ M tν −2 ⋅ B F⋅B 0 Ψ ... F ⋅ M tν −3 ⋅ B ∗ Ψ = – матрица связей ... 0 0 0 ... Ψ ( ν × ν ) между входами фильтра и его выходами. В качестве примера рассмотрим построение одноканального (ν = 1) и двухканального кодера (ν = 2) для разделимого циклического кода (7,4), порождаемого многочленом g ( x ) = 1 + x + x . Структура одноканального кодера задается матрицами 2

0 1 0 M=1 0 1, 1 0 0

3

0 1 1 Mt = 1 0 0 , 0 1 0 1

F = g1

g2

... g r = 0 1 1 , B = 0 , Ψ = 1 . 0

и имеет вид, представленный на рис. 8.1. При известных схемотехнических решениях матрицы B ( B ∗ ) и Ψ ( Ψ * ) , в принципе, можно и не строить. В большей степени они приводятся лишь для того, чтобы сохранить общую полноту картины построения ν -канального аналога одноканальной линейной последовательностной машины. 75

D1

Выход

D2

D3

2 Вход

1

Рис. 8.1. Структура одноканального кодера

Матричное описание двухканального аналога имеет вид

0 1 1 0 1 1

1 1 0

M = 1 0 0 1 0 0 = 0 1 1 , F∗ = 0 1 0 0 1 0 1 0 0 2 t

F ⋅ Mt 1 1 0 = , F 0 1 1

1 0 1 0 1 1 M = 1 1 0 , F ⋅ Mt = 0 1 1 1 0 0 = 1 1 0 , 2

0 1 0

0 1 0

а его структура представлена на рис. 8.2. В рассмотренном примере количество информационных разрядов k кратно ν . В общем случае это условие не выполняется и

⎡k ⎤

после выполнения z = ⎢ ⎥ тактов (квадратные скобки означают ⎣ν ⎦ ближайшее целое большее число), содержимое ν -канального кодера будет равно: R∗ ( x) = R( x) ⋅ x − ( z⋅ν−k ) mod g ( x) , где R( x ) соответствует контрольному коду. Поэтому требуется коррекция содержимого фильтра, если ( z ⋅ ν − k ) ≠ 0 . Однако коррекции можно избежать, если полином S ( x ) , соответствующий информационным разрядам, умножить на

x ( z⋅ν −k ) .

В этом случае

R ∗ ( x ) ≡ R ( x ) ⋅ x − ( z⋅ν −k ) ⋅ x ( z⋅ν − k ) ≡ R ( x ) mod g ( x ) . Известно, что умножение равносильно операции сдвига. Реализация сдвига заключается в том, что перед младшим информационным разрядом 76

s0

приписывается ( z ⋅ ν − k ) фиктивных нулей. При этом разряд

s0

s1 –

на

поступает на ( z ⋅ ν − k ) + 1 вход (канал) кодера, разряд

[( z ⋅ ν − k ) + 2] -й канал и т.д. =

D1

D3

Выход 1 Вход 1

=

D2

Выход 2 Вход 2 Рис. 8.2. Структура двухканального кодера

Блок-схема одноканального декодирующего устройства представлена на рис. 8.3. Коэффициенты s0 , s1 ,..., s n −1 полинома S (x ) последовательно поступают на вход буферного ЗУ и одновременно на вход многотактного фильтра, с помощью которого S (x) делится на g (x ) . Если ошибка отсутствует, то после поступления s n −1 содержимое фильтра будет равно нулю. Получение ненулевого результата свидетельствует о наличии обнаруживаемой ошибки E ( x) = x i e( x) . Если продолжить работу декодирующего устройства (синхронно производить сдвиги БЗУ и блока деления в автономном режиме), то последовательные состояния фильтра будут равны 77

⎫ ⎪ C ( x ) ≡ x e( x ) , ⎪ ⎬ mod g ( x) , ... ⎪ i i C ( x) ≡ x e( x) = e( x) ⎪⎭ C 0 ( x ) ≡ x i e( x ) , i −1

1

т. е. вычет вида ошибки будет воспроизведен точно через i тактов. В простейшем случае, когда возникла одиночная ошибка E ( x ) = x i , т.е. e( x) = 1 , то на i -м такте C i ( x) ≡ 1 или C i = 00...01 . При появлении такой комбинации на выходе логической схемы должен появиться сигнал, который инвертирует ошибочный символ. ЛС … ФИЛЬТР

Выход

Вход БЗУ

Рис. 8.3. Структура декодирующего устройства

Блок-схема ν-канального декодирующего устройства представлена на рис. 8.4. Принцип построения ЛС заключается в следующем. Для приема всего слова длиной

n разрядов требуется z ′ = ⎡⎢ ⎤⎥ тактов. Поэто⎣ν ⎦

му при наличии ошибки вида кодового слова будет равно

n

x i состояние фильтра после приема 78

C 0 ( x) = x i −( z ′⋅ν − n ) mod g ( x) , а последующие состояния при автономной работе будут равны:

C 1 ( x ) = x i − ( z ′⋅ν − n ) − ν ,

C 2 ( x ) = x i − ( z ′⋅ν − n ) − 2⋅ν , mod g ( x ) .

...

C j ( x ) ≡ x i −( z ′⋅ν − n ) − j⋅ν , ...

1 2

ФИЛЬТР

...

ЛС

… n-k

1 2

1 2 БЗУ

...

... ν

ν

Рис. 8.4. Структура декодирующего устройства

Пусть i = j ⋅ ν + β (β < ν ) , т.е. ошибка должна быть исправлена в такте j . Тогда на j -м такте автономной работы состояние j ⋅ν + β − ( z ′⋅ν − n ) − j ⋅ν

β − ( z ′⋅ν − n )

≡x фильтра равно C ( x ) ≡ x , т. е. логическая схема должна распознавать следующие вычеты: j

79

при β = 0

x − ( z ′⋅ν − n ) ,

при β = 1

x 1− ( z ′⋅ν − n )

,

mod

g( x ) .

... при β = ν − 1

x ν −1−( z′⋅ν −n )

Таким образом, ЛС в ν -канальном декодере содержит ν выходов. Например, пусть n = 7 , ν = 2 , g ( x ) = 1 + x + x , тогда z ′ = 4 и логическая схема будет представлять собой две схемы совпадения на следующие коды: 2

при β = 0 x при β = 1

−1

3

≡ x 7−1 ≡ x 6 ≡ x + x 2 , то есть 0 1 1; x1−1 ≡ x 0 ≡ 1 , то есть 1 0 0 .

ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ

1. Изучить теоретический материал. 2. Построить одноканальное кодирующее устройство циклического кода Хэмминга (7,4) с порождающим многочленом g ( x) = 1 + x + x 3 . 3. Построить трехканальное кодирующее устройство циклического кода Хэмминга (7,4) с порождающим многочленом g ( x) = 1 + x + x 3 . 4. Продемонстрировать процесс формирования проверочных разрядов. 5. Построить структуру трехканального декодирующего устройства циклического кода Хэмминга (7,4) с порождающим много3 членом g ( x ) = 1 + x + x . 6. Продемонстрировать процесс исправления произвольной однократной ошибки. 7. Продумать действия, когда количество информационных разрядов k или длина кода n не кратны канальности ν . 8. Отразить подготовку в лабораторном отчете. 80

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Используя обучающие средства диалоговой программы, изучить принципы построения кодирующих и декодирующих устройств циклического кода Хэмминга произвольной канальности. 2. Построить кодирующее и декодирующее устройства циклического кода Хэмминга с параметрами, заданными в подготовке к выполнению работы. Убедиться в правильности построения кодера и декодера. 3. Для заданного преподавателем циклического кода Хэмминга ( n, k ) построить кодирующие устройства всех допустимых канальностей ν . Исследовать принципы формирования проверочных разрядов, когда количество информационных разрядов k не кратно ν . 4. Для того же циклического кода Хэмминга ( n, k ) построить декодирующие устройства всех допустимых канальностей ν . Исследовать процесс исправления однократных ошибок, когда длина кода n не кратна ν . 5. Результаты отразить в лабораторном отчете. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дать общую характеристику циклического кода Хэмминга. 2. Что понимается под разделимым циклическим кодом? 3. Какие требования предъявляются к порождающему многочлену циклического кода Хэмминга? 4. В чем состоит особенность операции деления многочленов от фиктивной переменной? 5. Объясните последовательность переключения ключей в процессе функционирования кодера. 6. В чем заключается методика декодирования циклических кодов? 7. Что произойдет, если в линии связи возникнет ошибка кратности ≥ 2 ? 8. Чем отличается процесс функционирования фильтра в кодере от процесса в декодере? 81

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ (жирным шрифтом выделена основная литература)

1. Котоусов А.С. Теория информации. Учебное пособие для вузов. – М.: Радио и связь, 2003. 2. Липкин И.А. Статистическая радиотехника. Теория информации и кодирования. – М.: Вузовская книга, 2002. 3. Гоноровский И.С. Радиотехнические цепи и сигналы. – М.: Советское радио, 1986. 4. Темников Ф.Е. и др. Теоретические основы информационной технки. – М.: Энергия, 1979. 5. Федосеев Ю.Н. Элементы теории передачи и кодирования дискретной информации в АСУ. – М.: МИФИ, 1981. 6. Древс Ю.Г., Реутов В.Ф. Ортогональные преобразования сигналов и их применение в технике. – М.: МИФИ, 1988. 7. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. – М.: Мир, 1986. 8. Абдуллаев Д.А., Арипов Н.Н. Передача дискретных сообщений в задачах и упражнениях. Учебное пособие для вузов. – М.: Радио и связь, 1985. 9. Березкин Е.Ф., Федосеев Ю.Н. Лабораторный практикум по курсу "Основы теории информации и кодирования". – М.: МИФИ, 1997. 10. Фано Р. Передача информации. Статистическая теория связи. – М.: Мир, 1965. 11. Дмитриев В.И. Прикладная теория информации. Учебник для вузов по специальности "Автоматизированные системы обработки информации и управления". – М.: Высшая школа, 1989. 12. Хэмминг Р.В. Теория кодирования и теория информации. – М.: Радио и связь, 1989. 13. Березкин Е.Ф. Сборник задач по курсу "Основы теории информации и кодирования". – М.: МИФИ, 2002.

82

ПРИЛОЖЕНИЕ x

z2

− 1 Таблица значений интеграла вероятности F ( x) = e 2 dz ∫ 2π 0

x

F (x)

x

F (x)

x

F (x)

x

F (x)

0,00

0,0000

0,26

0,1026

0,52

0,1985

0,78

0,2823

0,01

0,0040

0,27

0,1064

0,53

0,2019

0,79

0,2852

0,02

0,0080

0,28

0,1103

0,54

0,2054

0,80

0,2881

0,03

0,0120

0,29

0,1141

0,55

0,2088

0,81

0,2910

0,04

0,0160

0,30

0,1179

0,56

0,2123

0,82

0,2939

0,05

0,0199

0,31

0,1217

0,57

0,2157

0,83

0,2967

0,06

0,0239

0,32

0,1255

0,58

0,2190

0,84

0,2995

0,07

0,0279

0,33

0,1293

0,59

0,2224

0,85

0,3023

0,08

0,0319

0,34

0,1331

0,60

0,2257

0,86

0,3051

0,09

0,0359

0,35

0,1368

0,61

0,2291

0,87

0,3078

0,10

0,0398

0,36

0,1406

0,62

0,2324

0,88

0,3106

0,11

0,0438

0,37

0,1443

0,63

0,2357

0,89

0,3133

0,12

0,0478

0,38

0,1480

0,64

0,2389

0,90

0,3159

0,13

0,0517

0,39

0,1517

0,65

0,2422

0,91

0,3186

0,14

0,0557

0,40

0,1554

0,66

0,2457

0,92

0,3212

0,15

0,0596

0,41

0,1591

0,67

0,2486

0,93

0,3238

0,16

0,0636

0,42

0,1628

0,68

0,2517

0,94

0,3264

0,17

0,0675

0,43

0,1664

0,69

0,2549

0,95

0,3289

0,18

0,0714

0,44

0,1700

0,70

0,2580

0,96

0,3315

0,19

0,0753

0,45

0,1736

0,71

0,2611

0,97

0,3340

0,20

0,0793

0,46

0,1772

0,72

0,2642

0,98

0,3365

0,21

0,0832

0,47

0,1808

0,73

0,2673

0,99

0,3389

0,22

0,0871

0,48

0,1844

0,74

0,2703

1,00

0,3413

0,23

0,0910

0,49

0,1879

0,75

0,2734

1,01

0,3438

0,24

0,0948

0,50

0,1915

0,76

0,2764

1,02

0,3461

0,25

0,0987

0,51

0,1950

0,77

0,2794

1,03

0,3485

83

x

F (x)

x

F (x)

x

F (x)

x

F (x)

1,04

0,3508

1,32

0,4066

1,60

0,4452

1,88

0,4699

1,05

0,3531

1,33

0,4082

1,61

0,4463

1,89

0,4706

1,06

0,3554

1,34

0,4099

1,62

0,4474

1,90

0,4713

1,07

0,3577

1,35

0,4115

1,63

0,4484

1,91

0,4719

1,08

0,3599

1,36

0,4131

1,64

0,4495

1,92

0,4726

1,09

0,3621

1,37

0,4147

1,65

0,4505

1,93

0,4732

1,10

0,3643

1,38

0,4162

1,66

0,4515

1,94

0,4738

1,11

0,3665

1,39

0,4177

1,67

0,4525

1,95

0,4744

1,12

0,3686

1,40

0,4192

1,68

0,4535

1,96

0,4750

1,13

0,3708

1,41

0,4207

1,69

0,4545

1,97

0,4756

1,14

0,3729

1,42

0,4222

1,70

0,4554

1,98

0,4761

1,15

0,3749

1,43

0,4236

1,71

0,4564

1,99

0,4767

1,16

0,3770

1,44

0,4251

1,72

0,4573

2,00

0,4772

1,17

0,3790

1,45

0,4265

1,73

0,4582

2,10

0,4821

1,18

0,3810

1,46

0,4279

1,74

0,4591

2,20

0,4861

1,19

0,3830

1,47

0,4292

1,75

0,4599

2,30

0,4893

1,20

0,3849

1,48

0,4306

1,76

0,4608

2,40

0,4918

1,21

0,3869

1,49

0,4319

1,77

0,4616

2,50

0,4938

1,22

0,3888

1,50

0,4332

1,78

0,4625

2,60

0,4953

1,23

0,3907

1,51

0,4345

1,79

0,4633

2,70

0,4965

1,24

0,3925

1,52

0,4357

1,80

0,4641

2,80

0,4974

1,25

0,3944

1,53

0,4370

1,81

0,4649

2,90

0,4981

1,26

0,3962

1,54

0,4382

1,82

0,4656

3,00

0,4986

1,27

0,3980

1,55

0,4394

1,83

0,4664

3,20

0,4993

1,28

0,3997

1,56

0,4406

1,84

0,4671

3,40

0,4996

1,29

0,4015

1,57

0,4418

1,85

0,4678

3,60

0,4998

1,30

0,4032

1,58

0,4429

1,86

0,4686

3,80

0,49993

1,31

0,4049

1,59

0,4441

1,87

0,4693

4,00

0,49997

84