Духин А.А. Теория информации

Подождите немного. Документ загружается.

121

ЗАДАЧИ

14.

Указать наименьшее т, при котором существует распреде-

( т Л

ленив вероятностей (р(а

),...,р(а

)} ^р(а

) =

такое, что

U=i >

код,

построенный по методу Шеннона, не является оптималь-

ным.

15.

Задан

ИСТОЧНИК

без памяти [A,p(s)] С энтропией <оо. Символы ал-

фавита А закодированы троичным префиксным кодом так, что

9 -

°°

Доказать, что вероятностное распределение на символах

источника задается равенствами р; = A- i =

1,2,...

16.

Доказать, что если п не является степенью двойки, то в оп-

тимальном двоичном коде найдутся два слова, имеющие раз-

ную длину.

17.

Объясните, почему двоичные коды

(ООО

1 =

001

0001

Р(а,) = 0,6

р(а

) = 0,2

р(а

) = 0,15

р(а

) = 0,05

, G

001

010

011

100

) = 0,2,

i =

1,2,...,5.

не являются оптимальными.

18.

Найти такое наименьшее n е N и распределение вероятностей

(Pi,...,p

при которых существуют оптимальные коды, разли-

чающиеся наборами длин кодовых слов.

19.

В условиях задачи 2.2.7 построить оптимальные двоичные коды

для символов, биграмм, триграмм, порождённых источниками

сообщений.

122

ГЛАВА

III. ОПТИМАЛЬНОЕ К о Д и Р о ВА НИЕ

20.

условиях задачи

2.2.8

построить оптимальные двоичные коды

для символов

биграмм, порождённых источником сообщений.

21.

Задан источник

без

памяти [A,p(s)j

= [(а,,...,а

pj =

0,3,

0,25,

0,15,

=0,1, р

=0,1,

=0,05, р

=0,05].

1) Построить двоичные коды, используя алгоритмы Фано,

Шеннона, Хаффмана.

2) Подсчитать среднюю длину

ср

для

каждого

из

построен-

ных кодов.

3) Построить троичные коды указанными методами.

22.

Задан источник

без

памяти [A,p(s)]

= [(a

..,a

р, =0,2,

=0,15,

= 0,15,

=0,1, р

=0,1,

=0,l].

1) Используя алгоритм Хаффмана, построить троичный пре-

фиксный

код.

2) Возможно

ли

построение другого троичного префиксного

ко-

да

такой

же

средней длиной

23.

Заданы источники

без

памяти [A,p(s)]:

А =

{а,,...,а

}

р,

0,34,р

0,18,р

0,17,р

0,16,р

0,15;

A =

..,a

}

<М>,р

0,1,р

0,09,р

0,08,р

0,07,р

= 0,06;

С)

А =

{а,,...,а

}

0,3,р

0,2,р

0,1,р

0,05,р

= 0,05;

A =

..,a

}

0,4,р

0,1,р

0,03,р

0,02,р

= 0,02.

1) Построить двоичные коды

для

этих источников, используя

алгоритмы Фано, Шеннона, Хаффмана.

2) Сравнить средние длины

для

полученных кодов.

ГЛАВА ЧЕТВЕРТАЯ

ЛИНЕЙНЫЕ

КОДЫ,

ИСПРАВЛЯЮЩИЕ

ОШИБКИ

§1

Обобщённая схема цифровой

аналоговой связи может быть представлена

следующим образом:

Источник

Кодер

для

канала

Канал

или

среда,

где хранится

информация

Декодер

канала

Адресат

Кодер

для

канала

Канал

или

среда,

где хранится

информация

Декодер

канала

Рис.

1.1

Под кодером понимается устройство преобразования информации, предназ-

наченной

для

передачи

по

каналу связи. Декодер преобразует сигналы, полу-

ченные

на

выходе канала связи

информацию, предназначенную

для

адреса-

та. Типичный канал

системе связи

телефонный, телеграфный, радиоре-

лейный. Для хранения информации используются магнитные элементы, ленты,

диски. Функционирование системы передачи информации осуществляется

такой последовательности. Источник порождает информацию,

после кодиро-

вания

её

кодером

для

источника преобразованная информация

виде двоич-

ных, десятичных цифр или

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

кодер

для канала. Кодер

для

канала преобразует

эти

сигналы

электрические,

электромагнитные

и др.

Сигналы поступают

канал

искажаются шумом.

Искажённые сигналы поступают

декодер, который восстанавливает пос-

ланное сообщение

направляет

его

получателю. Основная задача

технике

связи заключается

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

декодера

для

надёжной передачи

информации.

Для введения необходимых понятий детализируем схему, приведённую

на

рис.

1.1.

Источник

Рис 1.2

ЗАДАЧИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

ПОНЯТИЯ

125

Кодер, кодирующий входную информацию в двоичные сигналы.

Кодер, кодирующий двоичные сигналы.

Кодер, кодирующий двоичные сигналы в сигналы на входе в канал (мо-

дулятор).

Канал связи или память.

Декодер, декодирующий сигналы на выходе канала в двоичные симво-

лы

(демодулятор).

6. Декодер - устройство, предназначенное для исправления ошибок в

двоичных символах.

Декодер, декодирующий двоичные символы в сообщение.

Мы не рассматриваем инженерные вопросы, связанные с передачей сигна-

лов по каналу связи. Предметом нашего рассмотрения является математичес-

кое описание функционирования кодера 2 и декодера 6, обеспечивающих за-

данный уровень надёжности передачи информации. Таким образом, изучение

функционирования блоков 3, 4, 5 схемы, изображённой на рис. 1.2, выходит

за рамки настоящей работы.

В идеальной системе связи при отсутствии искажений в канале символы,

которые появляются на выходе устройства, декодирующего сигналы на выходе

канала, должны совпадать с символами, которые поступают на вход кодера ка-

нала. Однако в реальной системе всегда имеются случайные ошибки, поэтому

назначение корректирующих кодов состоит в том, чтобы обнаруживать или

исправлять такие ошибки. Коды, которые будут построены, не могут исправ-

лять любую возможную комбинацию ошибок. Основная их задача - исп-

равлять наиболее правдоподобные комбинации ошибок. В основу построения

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

независимо от остальных искажений и, следовательно, вероятность данной

комбинации ошибок зависит только от числа ошибок. Это предположение но-

сит искусственный характер, так как в реальных ситуациях дело обстоит сле-

дующим образом. На магнитной ленте, в телефонной связи, в телеграфной

связи время действия помехи (брак на ленте, молния, сварка, контактная иск-

ра и т.д.) превышает продолжительность передачи одного символа. Следова-

тельно, необходимы коды для исправления серий (пакетов, пачек) ошибок. Се-

рии ошибок и методы их исправления в настоящей книге не рассматриваются.

этой главе рассмотрены коды, корректирующие изолированные ошибки.

Говорят, что код обнаруживает ошибку, если декодер сигнализирует об

отличии принятого вектора от переданного кодового слова. Говорят, что код

исправляет ошибку, если декодер указывает позицию и значение искажён-

ной координаты.

Ниже будут рассмотрены блоковые коды. В кодере, предназначенном для

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

разбивается на отрезки, содержащие по к символов, или на к -значные блоки.

дальнейшем операции проводятся над каждым блоком отдельно, независимо

§ t.

ЗАДАЧИ

ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ.

ОСНОВНЫЕ

ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

126

ГЛАВА

IV.

ЛИНЕЙНЫЕ

КОДЫ, ИСПРАВЛЯЮЩИЕ

ОШИБКИ

от других в соответствии с выбранным кодом. Каждому возможному информа-

ционному блоку из к символов сопоставляется набор из n-к символов

канала

(n>k),

называемых проверочными. Набор п символов, составленный

из к информационных и (n-к) проверочных, называемый кодовым словом,

передаётся по каналу связи, искажается шумом, а затем декодируется неза-

висимо от других кодовых слов. Величина п называется длиной блока.

Совокупность всех кодовых слов будем называть кодом. Мощность кодового

алфавита равна q = р

. Компоненты кодовых слов - суть элементы поля

GF(g).

Очень часто рассматриваются двоичные коды, то есть q = 2. Рассмот-

рим двоичный симметричный канал

(ДСК),

предназначенный для передачи

двоичной информации.

p + q

= l, р£0, q£0

q - вероятность совпадения принятого и переданного

символа,

р - вероятность искажения передаваемого символа. Для

реального канала q > р, причём для хорошего канала:

q»p.

Будем предполагать, что сигналы передаются по каналу независимо. Шум

также независимо накладывается на передаваемую информацию.

На примере ДСК покажем основной принцип декодирования. Вероятность

того,

что при передаче по ДСК кодового слова не произойдёт ни одной ошиб-

ки,

равна q

. Вероятность того, что в заданной позиции произойдёт одна ошиб-

ка, равна pq""

и т.д. Поскольку q>p, то получение на выходе канала блока

без ошибок более вероятно, чем получение блока с одной ошибкой, а эта ве-

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

ошибками и т.д.

В предположении, что все слова кода имеют одинаковую вероятность быть

переданными по каналу, наилучшим решением на приемнике будет деко-

дирование в такое кодовое слово, которое отличается от полученного в наи-

меньшем числе компонент, то есть декодирование в "ближайшее" кодовое сло-

во.

Такое декодирование называется декодированием по методу максималь-

ного правдоподобия.

I q I

Рис.

1.3

127

§ 1.

ЗАДАЧИ

ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ.

ОСНОВНЫЕ

ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

Определение

1.1.

Расстояние Хемминга между двумя кодовы-

ми словами определяется как число компо-

нент,

в которых эти слова отличаются

друг от друга:

d(g,h)

w(g-h),

где W(g) - вес вектора g, число ненулевых

компонент вектора.

(4.1.1)

При искажении t компонент у некоторого кодового слова, полученное на

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

есть будет удалено на расстояние t.

Лемма

1.1.

Для того чтобы обнаружить все комбинации из (d-l) или

меньшего числа ошибок, необходимо и достаточно, чтобы

минимальное расстояние Хемминга между кодовыми слова-

ми было равно d.

Достаточность.

Если минимальное расстояние между кодовыми словами

равно d, то никакая комбинация из (d-l) ошибки не может перевести одно

кодовое слово в другое.

Необходимость.

Если минимальное расстояние менее или равно

(d-l),

то

существует пара кодовых слов, отстоящих друг от друга на расстояние меньше

d, и поэтому существует комбинация из соответствующего числа ошибок, ко-

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

слово,

которое получилось из отправленного кодового слова в результате искажений,

декодер не обнаружит наличие ошибок. •

Лемма

1.2. Для того чтобы исправить все комбинации из t или мень-

шего числа ошибок, необходимо и достаточно, чтобы ми-

нимальное расстояние между кодовыми словами было равно

Достаточность.

Любое полученное слово с t'<t ошибками отличается от

переданного кодового слова в t' компонентах, а от каждого другого

кодового

слова самое меньшее в 2t +

l-t'>t'

компонентах. Согласно принципу

макси-

мума правдоподобия декодер осуществит правильное декодирование.

Необходимость.

Если минимальное расстояние меньше, чем 2t + l, напри-

мер:

d = 2t, то, по крайней мере, в одном случае t-кратная ошибка приведёт к

ГЛАВА

128

ЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ

ОШИБКИ

такому слову на выходе, которое, по крайней мере, столь же близко к одному

из не передававшихся кодовых слов, как и к переданному кодовому слову.

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

передавалось. А

Ниже будут рассмотрены коды, для которых можно доказать, что они

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

уровень надёжности. Такие коды должны обладать особой математической

структурой, например, это могут быть линейные коды. Изучению различных

свойств линейных кодов посвящена настоящая глава.

Определение 1.2. Пусть V

-мерное векторное простран-

ство над GF(q). Подпространство Gc= V

называется линейным блоковым кодом.

Определение

1.3.

Величина

d = mm{d(g,h) :g,h(=G}

называется кодовым расстоянием.

(4.1.2)

Расстояние между двумя кодовыми словами линейного кода равно весу не-

которого ненулевого кодового слова в силу того, что

Vg,he6, g-h =f eG, d - min W(f), g*h.

f€G

Следовательно, кодовое расстояние для линейного кода равно минималь-

ному весу его ненулевых кодовых слов.

Пример 1.1. Пусть q = 2, п = 5. Рассмотрим код G, состоящий из двух кодо-

вых слов g

=(00000), gj =(11111). Этот код предназначен для

кодирования двоичной информации. Он обладает большой поме-

хозащищенностью, но очень малой скоростью передачи информа-

ции. На один информационный - полезный символ в кодовом

слове приходится 4 проверочных символа. Введённый код назы-

вается кодом кратных повторений.

Пример 1.2. Пусть q = 2, п = 5.

Г (00000)(00101)

(10011) (10110)

(01010)(01111)

[(11001) (11100)J

129

§ 1.

ЗАДАЧИ

ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ.

ОСНОВНЫЕ

ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

'1001Г 'lOOlf

G,=

01010

. G

11001

^00101,

JU100,

Известно, что подпространство векторного пространства может быть задано

различными базисами, что обусловливает неоднозначность выбора порождаю-

щей матрицы кода.

Рассмотрим иную форму задания линейного (п,к)-кода. Для векторов

а = (ot| ,...»a

), b = (P

..,p

) € V

вводится скалярное произведение:

(a,b) = Zajpj(m<>tfp).

i=l

Векторы a,b называются ортогональными, если (a,b) s Q(modp).

Пусть

- векторное подпространство размерности к. Множество всех век-

торов из V

ортогональных к G образует ортогональное векторное подпрост-

ранство G

, размерности п - к.

Существует матрица H =

||hjj|J,

i~l,...,n~k, j =

l,...,n

ранга n-к, строка-

ми которой является базис подпространства G

, пространство строк которой

совпадает с G

Очевидно, что код G - подпространство V

(GF(2)). Ненулевое

слово минимального веса - (00101). Кодовое расстояние кода G

равно 2.

Определение

1.4.

Пусть Gc V

- линейный код размерности к. Мат-

рица G(kxn), составленная из базисных векторов

подпространства G, называется порождающей

матрицей кода G.

Для линейного кода G размерности к с кодовым расстоянием d будем ис-

пользовать обозначение

(n,k,d)-KOA.

Этот код содержит q

векторов. Задание

его с помощью порождающей матрицы G более компактно, чем перечисление

всех кодовых слов. Так двоичный (50,30)-код описывается матрицей, порядка

(30 х 50), составленной из нулей и единиц. Однако, код имеет более чем 10

кодовых векторов.

Код из примера 1.2 является пространством строк любой из матриц G

которые можно рассматривать в качестве порождающих

130

л л

IV.

ЛИНЕЙНЫЕ

КОДЫ,

ИСПРАВЛЯЮЩИЕ

ОШИБКИ

Вектор

a = (a,

..,a

)eG

тогда

только тогда, когда

ортогонален каж-

дой строке матрицы

Н, то

есть

аН

= 0. (4.1.3)

В координатной записи

это

соотношение принимает

вид

1>».,п-к.

(4.1.3')

Таким образом, соотношения

(4.1.3')

означают,

что

компоненты кодового

слова

должны удовлетворять совокупности

и-к

линейно-независимых

уравнений.

Эти

уравнения называются

обобщенными проверками на чёт-

ность.

Определение 1.5. Порождающая матрица Н для подпространст-

ва 0

называется проверочной матрицей

кода G.

Соотношения проверок

на

чётность должны выполняться

и для

базисных

векторов подпространства

G. То

есть:

=j|0|,

(4-1-4)

где

jj0j|

нулевая матрица размеракх(п-к).

Для примера

1.2

ортогональным пространством будет:

= {(00000),(11010),(10101),(ОШ1)}.

Соответствующая порождающая матрица

для G

имеет

вид:

11010^1

l^ioioij

Матрица

является проверочной

для

линейного кода

Определение 1.6. Ортогональное подпространство Q

порождающей матрицей Н называется

линейным

(п>п-к)-кодом,

двойственным

к линейному (п,к)-коду G.

В свою очередь,

(п

к)-код

G является двойственным

для (n,n

-k)-/coda

Лемма 1.3: Пусть G - линейный (п,к) -код с проверочной матрицей Н.

Тогда

каждому кодовому слову aeG, W(a) = d соответст-

вует соотношение линейной зависимости, связывающее d