close

Вход

Забыли?

вход по аккаунту

?

Goryachkin Teoriya informacii i kodirovaniya Ch2 uchebnoe posobiei

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»
Кафедра теоретических основ радиотехники и связи
О.В. Горячкин
Теория информации и
кодирования
(Часть 2)
Учебное пособие
Самара 2017
УДК 621.391
БКК 3.32.81
Г19
Рекомендовано к изданию методическим советом ПГУТИ, протокол №78 ,
от 15.05.2017 г.
Рецензенты:
Заведующий кафедрой систем связи ПГУТИ,
д.т.н., профессор, Васин Н.Н.,
Заведующий кафедрой суперкомпьютеров и общей информатики
Самарского университета, д.т.н., профессор Фурсов В.А.
Г19
Горячкин, О. В.
Теория информации и кодирования (Часть 2): учебное пособие
/О.В. Горячкин. – Самара: ПГУТИ, 2017. –138 с.
Учебное пособие «Теория информации и кодирования (Часть 2)» в форме
лекций содержит основы теории информации и кодирования, разработано
в соответствии с ФГОС ВО по направлению подготовки дипломированных
специалистов
10.05.02
Информационная
безопасность
телекоммуникационных
систем,
утвержденного
16.11.2016
Министерством образования Российской Федерации и предназначено для
студентов соответствующей специальности, обучающихся на 3-м курсе, на
Факультете телекоммуникаций и радиотехники для самостоятельной
подготовки к практическим и лабораторным занятиям, экзамену по курсу.
ISBN
©, Горячкин О.В., 2017
2
СОДЕРЖАНИЕ
Введение…………………………………………………………………
Лекция №10. ……………………………………………………………
1. Теория информации…………………………………………………..
1.1. Энтропия дискретного источника информации ………………….
1.1.1. Частное количество информации…………………………………
1.1.2. Энтропия дискретного источника……………………………….
Лекция №11. ……………………………………………………………
1.1.3. Теорема Шеннона о кодировании источника без памяти………
1.2. Кодирование дискретного источника……………………………...
1.2.1. Код Хаффмана……………………………………………………..
1.2.2. Код Шеннона-Фано………………………………………………..
1.2.3. Код Лемпеля-Зива………………………………………………….
1.2.4. Расширение алфавита……………………………………………...
Лекция №12………………………………………………………………
1.3.Теорема Шеннона о кодировании источника………………………
1.3.1. Теорема об асимптотической равновероятности…………….......
1.4. Информационные характеристики дискретного канала связи……
Лекция №13. ……………………………………………………………..
1.5. Теорема Шеннона о пропускной способности дискретного
канала связи……………………………………………………………….
1.6. Информационные характеристики Реальных каналов связи……..
Лекция №14. …………………………………………………………….
1.7. Информационные характеристики непрерывного канала связи…
Лекция №15………………………………………………………………
2. Теория кодирования…………………………………………………...
2.1.Общая характеристика помехоустойчивых кодов…………………
2.2. Основные понятия абстрактной алгебры…………………………..
Лекция №16………………………………………………………………
2.3. Элементы теории линейных блоковых кодов……………………...
2.4. Коды Хэмминга………………………………………………………
Лекция №17………………………………………………………………
2.5. Декодирование линейных блоковых кодов………………………...
2.6. Простые преобразования линейного кода………………………….
2.7. Коды Рида-Маллера………………………………………………….
Лекция №18………………………………………………………………
2.8. Арифметика полей Галуа……………………………………………
2.9. Циклические коды…………………………………………………...
Лекция №19................................................................................................
2.9.1. Синдромное декодирование циклических кодов………………...
Лекция №20………………………………………………………………
2.9.2. Циклические коды Хэмминга……………………………………..
2.9.3. Двоичные циклические коды, исправляющие две ошибки……..
5
6
6
6
7
8
12
12
15
15
18
18
19
21
21
21
24
27
30
32
34
34
41
41
41
43
48
48
53
57
57
61
62
67
67
71
74
78
79
79
82
3
2.9.4. Коды Голея…………………………………………………………
Лекция №21................................................................................................
2.9.5. Коды Боуза-Чоудхури-Хоквингема (БЧХ)……………………….
Лекция №22………………………………………………………………
2.9.6. Коды Рида-Соломона………………………………………………
2.9.7. Двоичные квадратично-вычетные коды………………………….
2.10. Границы для кодов………………………………………………….
2.11. Коды Адамара………………………………………………………
2.12. Коды Гоппы…………………………………………………………
Лекция №23………………………………………………………………
2.13. Сверточные коды…………………………………………………...
2.13.1. Полиномиальное описание сверточных кодов…………………
Лекция №24................................................................................................
2.13.2. Примеры двоичных сверточных кодов…………………………
2.13.3. Декодирование сверточных кодов………………………………
Лекция №25………………………………………………………………
2.14. Каскадные коды…………………………………………………….
2.15. Мягкое декодирование блоковых кодов………………………….
Лекция №26................................................................................................
2.16. Мягкое декодирование сверточных кодов………………………..
2.17. Кодированная модуляция………………………………………….
Список литературы………………………………………………..........
84
85
85
93
93
94
96
98
100
104
104
108
111
111
113
119
119
123
130
130
131
135
4
ВВЕДЕНИЕ
Целью преподавания дисциплины «Теория информации и
кодирования» является знакомство студента с теоретическими основами
инженерной деятельности в области информационной безопасности
телекоммуникационных систем, в частности с теорией основных методов,
способов и средств передачи, хранения, переработки и получения
информации.
Основное внимание уделяется изложению классической теории
информации, разработанной К. Шенноном и его последователями. Кроме
этого в курсе
излагаются основы теории потенциальной
помехоустойчивости телекоммуникационных систем и основы теории
экономного и помехоустойчивого кодирования. Показывается взаимосвязь
данных теорий.
Пособие разделено на две части, в соответствии с учебным планом.
В первой части учебного пособия излагаются основы теории
потенциальной помехоустойчивости.
Во второй части учебного пособия представлены классическая
теория информации и элементы теории кодирования. Материал оформлен
в виде лекций. Содержит примеры задач, список основной и
дополнительной литературы для самостоятельного изучения.
Материал пособия содержит классический материал и полностью
основан на монографиях и учебных пособиях указанных в списке
литературы, поэтому в тексте нет конкретных ссылок на первоисточники.
Задачей автора пособия было компактное изложение курса, с учетом
специфики
взаимодействия
связанных
курсов
специальности
«Информационная безопасность телекоммуникационных систем».
Пособие содержит краткие сведения об отечественных и зарубежных
ученых (почерпнутые в основном из Википедии), создававших своими
трудами данную область знания.
5
ЛЕКЦИЯ №10
1. ТЕОРИЯ ИНФОРМАЦИИ
Теория информации (математическая теория связи) — раздел
прикладной математики, теории связи, радиотехники, теории обработки
сигналов и информатики, относящийся к измерению количества
информации, её свойств и устанавливающий предельные соотношения для
систем передачи данных, а также основные принципы их проектирования
и технической реализации.
Клод Э́лвуд Ше́ннон (Claude Elwood
Shannon); (30 апреля 1916, Петоцки,
Мичиган, США — 24 февраля 2001,
Медфорд, Массачусетс, США) —
американский инженер и математик,
создатель теории информации.
1.1. ЭНТРОПИЯ ДИСКРЕТНОГО ИСТОЧНИКА
ИНФОРМАЦИИ.
Источник сообщений A в теории информации представляется
«черным ящиком» на выходе, которого, последовательно, появляются
символы a  ,..., a1 ,...a k ,...a  , принимающие значения из алфавита
A1,..., AM  и отображающие передаваемою информацию. Различают
источники дискретных сообщений (ИДС), если M   , и источники
непрерывных сообщений (ИНС), если M   .
ИДС
А
a  ,..., a1 ,..., a k ,...a 
6
ИДС
полностью
описывается
совместной
вероятностью
последовательностей символов на своем выходе Pa  ,..., a1 ,...a k ,...a   ,

или для n символов Pa1 ,..., a n   Pa n .
ИДС называют стационарным, если для любых n , k
Pa1 k ,..., an  k   Pa1 ,..., a n .
(1)
ИДС называют источником без памяти, если для любого n
n
Pa1 ,..., a n  
 Pai .
(2)
i 1
1.1.1. Частное количество информации
В соответствии с подходом, который предложил К.Шеннон, частное
количество информации   , содержащиеся в некотором сообщении а,
должно зависеть от вероятности этого сообщения Pa. При этом
желательно, чтобы достоверное сообщение не несло никакой информации,
а если имеется два независимых статистически сообщения, то информация,
содержащиеся в каждом из них, складывалась бы.
Этим соображениям соответствуют следующие условия
1) i a    Pa ;
2) i a   0 , если Pa  1 .
3) ia, b   i a   i b  , если Pa, b  PaPb.
Пусть справедливо 3-е условие
 Pa, b   Pb aPa   Pb a   Pa .
(3)
Продифференцируем левую и правую часть последнего равенства по
Pa, получим
 Pb aPaPb a   Pa .
(4)
Умножим левую и правую части равенства на Pa, получим
 Pb aPaPaPb a  Pa Pa .
(5)
Последнее равенство эквивалентно следующему
  x x    y  y ,
(6)
для любых x, y , а это означает, что   x x  const ,
  x   const ln  x   c .
(7)
Из 2-го условия следует, что  1  c , и c  0 .
1
Пусть
, тогда получим частное количество
const  
ln 2 
информации по Шеннону
 1 
i a   log 2 
(8)
 , [бит/символ]
P

a



7
1.1.2. Энтропия дискретного источника
Энтропией дискретного источника H  A называют среднее
количество информации, приходящиеся на один символ источника
 1 
1 
1

H  A  lim Mi an = lim M log 2    =
n  n 
n n
 Pan 
 1 
1

= lim
Pa n log 2    .
(9)
P

a

n  n 

n 

an 
§ Свойства энтропии дискретного источника:
1. H ( A)  0 энтропия положительная величина.

Доказательство. Это сразу следует из определения и Pa n   0 .
2. Если A – источник без памяти, то справедлива формула
Больцмана-Шеннона
M
 1 
 .
PAk log 2 
(10)


P
A
k 

k 1
Доказательство. Из определения энтропии и предположения о
стационарности источника следует
 1 
1

H  A  lim
Pan log 2    
n n 
 Pan 
H  A 


a n 




n


1
1

 lim
Pai log 2 
n


n
n 
a n i 1

Pai 


 i 1



1
 lim
n n 
n
n
 1 
 
log 2 
P

a


i 
i 1
 Pai 
a n i 1

 1 
 1 
1
 Pa1log 2 


   (11)

...

P

a

log
n
2
 Pa 

P

a

n   n  

i 

n 
a n 
 lim
M



1

 PAk log 2  PAk .
k 1
3. Для любого стационарного ИДС
удовлетворяет неравенству
H  A  log 2 M .
без
памяти
энтропия
(12)
8
Доказательство.
M
H  A  log 2 M  
 1 
  log 2 M  
PAk log 2 


P
A

k 
k 1

M
M


 1 


PAk log 2 
PAk log 2 M  
PAk 

k 1
k 1
1

ln 2 
M

1

 PAk ln MPAk  
k 1
M
M



1 
1
 
 ln  x   x  1 
PAk 
PAk  


ln 2 
 MPAk  k 1
 k 1

1
1  1  0.

ln 2 
4. Для любого стационарного ИДС энтропия удовлетворяет
неравенству

M
H  A 


1

 PAk log 2  PAk  .
(13)
k 1
Доказательство. Пусть память источника распространяется на два
соседних символа.
Pa1 ,..., an   Pa1 a2 Pa2 a3 Pa3 a4 ...Pan  2 an 1Pan .
(14)
Подставим последнее выражение в определение энтропии и
воспользуемся стационарностью источника
9
 1 
1

Pan log 2    
n n 
 Pan 

H  A  lim
a n 




 1  
1
1
1
 
  log 2 
  ...  log 2 
Pa n  log 2 
 Pa    

 Pa a 

P

a
a

n  n 
1 2 
2 3 

n 



a n 

 lim





1
1
1



 lim 
Pa1 , a 2 log 2 
P

a
,
a

log
2
3
2

 Pa a   ...
P

a
a

n  n 
1 2  a a 
2 3 


2, 3
 a1, a 2 



 1 
  
...
Pan log 2 
P

a


n 
a n 


M M


1
1
 lim  n  1
P Ai , A j log 2 
P A A
n  n 
i j
i

1
j

1


 



 M
 1 

 .
PAk log 2 

P

A

k 

 k 1

(15)
 
Перейдем к разности
M
H  A 

1

 PAk log 2  PAk  ,
k 1
M
H  A 
 1 

PAk log 2 
PAk  

k 1

M M



 M
 1 
1
1


  
 lim  n  1
P Ai , A j log 2

PAk log 2 
P A A 
P

A

n n 

k

i j  k 1
i 1 j 1



M
 1  
n 
 
 lim
PAk log 2 

P

A

n n 

k 
 k 1
M M


 M M
 1 
n  1
1


  
 lim
P Ai , A j log 2

P Ai , A j log 2 



n
P

A

n
P Ai A j
 i 1 j 1

i 

 i 1 j 1


 


 

 


  

10
   
   
M M
 PA     M M
 PAi P A j

i  


P Ai , A j log 2 
P
A
,
A
log
i j
2




 i 1 j 1
 P Ai , A j
 P Ai A j    i 1 j 1

M M
 PAi P A j   M M
1 
 
 ln  x   x  1 
P Ai , A j 
P Ai , A j




ln 2  
P
A
,
A

i j 

 i 1 j 1
 i 1 j 1
1

1  1  0.
ln 2 
 



 
 

   
 

5. Максимальную энтропию имеет ИДС без памяти и
равновероятным распределением символов, т.е. на выходе которого
символы A1 ,..., AM  появляются с вероятностью 1\М.
Доказательство.
M
M


 1 
1
 
H  A 
PAk log 2 
log 2 M   log 2 M .
(16)


P
A
M
k

 k 1
k 1
6. Для любых дискретных вероятностных распределений
m
m
 xi  1;  yi  1 справедливо неравенство
i 1
i 1
m

i 1
y
xi log 2 i  0 .
xi
(17)
Доказательство.
m

i 1
y
1
xi log 2 i  ln  x   x  1 
xi
ln 2 
m
  yi 

 xi    xi   0 .
 x 


i 1   i 

11
ЛЕКЦИЯ №11
1.1.3. Теорема Шеннона о кодировании источника без памяти.
Теорема 1. Существует способ кодирования и декодирования
символов дискретного источника информации без памяти, при котором
средняя длина кодовых комбинаций удовлетворяют следующему
неравенству
H ( A)
l
,
(18)
log 2 m
где l - средняя длина кодовой комбинации неравномерного кода, mоснование кода, H  A – энтропия источника.
Доказательство. В несколько этапов докажем данную теорему.
1. Код, длины комбинаций которого различны, называются
неравномерным. При кодировании символов источника для снижения
средней длины кодовой комбинации при неравномерном кодировании,
часто встречающимся символам приписываются короткие комбинации, а
редко встречающимся соответственно длинные комбинации.
В этом случае кажется, что для разделения потока символов кода в
декодере необходимо использовать некий разделитель символов, однако
это не так, если кодовая комбинация удовлетворяет специальному
условию префиксности, которое состоит в том, что ни одна кодовая
комбинация не должна являться началом другой кодовой
комбинации.
Код, удовлетворяющий этому условию, называется префиксным
кодом.
Для описания префиксного кода удобно использовать т.н. кодовое
дерево.
Двоичное кодовое дерево показано на рисунке 1. Каждый узел
дерева это кодовая комбинация неравномерного кода. Путь к узлу это
соответствующая кодовая комбинация (последовательность 0 и 1 в данном
случае).
Выбирая кодовые комбинации для префиксного кода, мы должны
следовать специальному правилу и выбрав комбинацию, отсеивать все
дальнейшее дерево.
12
1
1
0
1
1
1
0
1
0
0
1
1
0
0
1
0
0
0
l=1
l=2
l=3
l=4
l=5
Рисунок 1 - Двоичное кодовое дерево
Лемма 1. Необходимым и достаточным условием существования mичного префиксного кода с длинами l1…lM является неравенство Крафта
M
1
 m li  1.
(19)
i 1
Т.о. пусть существует префиксный код с длинами l1,…,lM . Для него
выполняется неравенство Крафта, которое можно записать в виде
M
1
 am li  1,
(20)
i 1
M
где a  1 =>
1
 qi  1, где qi  amli .
i 1
2. Воспользуемся свойством энтропии №6.
Пусть
M
q
 pi log 2 pii  0 ,
(21)
i 1
где pi – распределение, описывающее статистику символов a1…aM,
M
 pi  1 , q – задает некое дискретное распределение вероятностей.
i
i 1
Воспользуемся свойствами функции логарифма.
M
M
 pi log 2 qi   pi log 2 pi  0 ,
i 1
i 1



Энтропия ИДС
13
M
 pi log 2 qi  H ( A) .
i 1
3. Пусть qi – задает дискретное распределение вероятностей,
полученное ранее в неравенстве Крафта, тогда получим
M

i 1
pi log 2
1
am
li
 H ( A) ,
M

pi  log 2 a   
pi li  log 2 m  H ( A) ,


i 1
 i 1

 log 2 a  l log 2 m  H ( A) ,
H ( A)
Т.к. a  1  log 2 a  0   log 2 a  0  l 
.
log 2 m
Теорема 1 доказана.
(22)
M


(23)
(24)
Докажем лемму 1. При выборе на кодовом дереве кодовой
комбинации префиксного кода с длиной l1 мы отсекаем mlmax l1
оставшихся «не у дел» кодовых комбинаций, при выборе следующей
l2  m lmax l2 , итого получим
M
 mlmax li  mlmax .
(25)
i 1
Разделим обе части неравенства на mlmax , получим неравенство
Крафта. Обратно, если неравенство
выполняется, то можно повторить
рассуждения, сформулировав правило
формирования префиксного кода.
Роланд Львович Добрушин (20 июля
1929, Ленинград — 12 ноября 1995,
Москва)
—
советский
учёныйматематик, специалист в области
математической
физики,
теории
вероятностей и теории информации.
Специализировался на изучении цепей
Маркова и теорем Шеннона.
14
1.2. КОДИРОВАНИЕ ДИСКРЕТНОГО ИСТОЧНИКА
Избыточностью ИДС называют величину
log 2 M   H  A

100% .
(26)
log 2 M 
Производительность ИДС это
H  A
H  A 
,
(27)
t
где t - время выдачи 1-го символа на выход стационарного
источника.
Эксперимент академика Р.Л. Добрушина по компьютерной
генерации текстов на русском языке с учетом многомерных распределений
символов алфавита.
№ Фраза
H  A 
1
5
0%
4.35
13%
2.9
42%
1.37
72%
2
3
4
Условия
эксперимента
сухерробъдш
Равномерное
яыхвщинюайжтлфвнзагфоенвштир распределение букв
пхгбкучтжюряпчьйхрыс
алфавита источника
без памяти
еынт цияба оерв однг буемлолйкзбя Реальное
евнтша
распределение букв
алфавита источника
без памяти
весел враться не сухом и непо и
Учтены
корко
вероятности
четырехбуквенных
сочетаний
Теория информации «полезная»
Реальный текст
наука
1.2.1. Код Хаффмана
Кодирование символов ИДС префиксным кодом с основанием m с
целью достижения минимального значения средней длины называется
кодом Хаффмана. Если известны вероятности PAk  , k  1,..., M и
символы пронумерованы так, что PAk   PAk 1, то длины кода
Хаффмана должны удовлетворять условию
l k  l k 1 .
(28)
15
Дэ́вид Ха́ффман (9 августа 1925,
Альянс, Огайо — 7 октября 1999, СантаКруз, Калифорния) — ученый в области
теории информации и кодирования. В
1952 году создал алгоритм префиксного
кодирования
с
минимальной
избыточностью
(известный
как
алгоритм или код Хаффмана).
Докажем оптимальность кода Хаффмана по средней длине.
Пусть l - средняя длина кода Хаффмана. Пусть у нового кода
условие (28) не выполняется для k -го символа, т.е. в сумме lновый код
появляются слагаемые вида PAk l k 1  PAk 1l k .
Легко заметить, что
l  lновый код  PAk 1  PAk lk 1  lk   0  l  lновый код .
Алгоритм нахождения кода Хаффмана иллюстрирует рисунок 2.
Код Хаффмана находится с помощью последовательности
одинаковых действий.
На первом шаге объединяются самые маловероятные символы в
один с суммированием вероятностей. Т.о. число символов уменьшается на
1.
На втором шаге все повторяется и так до последнего символа.
Полученное дерево объединяющихся символов и есть дерево кода
Хаффмана.
16
ИДС выдает 5
символов с известными
упорядоченными
вероятностями
появления PAk 
PA1
PA2 
0
0
PA3   PA4   PA5 
PA4   PA5   PA3 
0
PA4   PA5 
1
1
PA2   PA3   PA4   PA5 
PA3   PA4   PA5   PA2 
0
PA5 
PA4 
PA3 
PA1   PA2   PA3   PA4   PA5 
1
Рисунок 2 - Алгоритм нахождения кода Хаффмана
A1 =0
А2 =10
А3 =110
А4 =1110
А5 =1111
1
1.2.2. Код Шеннона-Фано
Считается, что кодирование Шеннона-Фано не столь эффективно по
средней длине, чем оптимальный код Хаффмана, во многих реальных
случаях, однако при увеличении объема алфавита оба кода стремятся к
одному результату.
Преимуществом кода Шеннона-Фано является возможность сразу
выбрать длины кодовых слов в соответствии со следующими
неравенствами
 1 
 1 
  l k  log 2 
  1 .
log 2 
(29)
 PAk  
 PAk 
Непосредственный выбор кодовых слов произволен. Так
перебираются все кодовые комбинации длиной 1,2,3 и т.д. Неравенство
Крафта гарантирует, что соответствующих комбинаций хватит и будет
соблюдено условие префиксности.
Абрахам Лемпель (10 февраля 1936,
Львов, Польша — н.в.) д.т.н., профессор,
израильский
ученый
в
области
компьютерных наук, изобретатель
словарных
алгоритмов
сжатия
информации (LZ77, LZ78).
1.2.3. Код Лемпеля-Зива
Способ сжатия без потерь, известный как алгоритм LZ77 (словарный
алгоритм), опубликованный в статьях израильских математиков Авраама
Лемпеля и Якова Зива в 1977-1978 годах. Алгоритм применяется тогда,
когда вероятности PAk , k  1,..., M неизвестны. При увеличении числа
кодируемых символов до бесконечности средняя длина двоичных
символов кода Лемпеля-Зива стремиться к H  A , т.е. к пределу Шеннона,
установленного 1-й теоремой.
Суть алгоритма в использовании текущего словаря символов, взятых
непосредственно из кодируемого текста.
Рассмотрим алгоритм на примере сжатия конкретного текста: А В
АВ АА ВА ААВ ВВ ВАВ ВВА ВВАА ААА АВА АААА ААААВ.
Текущий словарь символов формируется из впервые встречающихся
сочетаний и имеет вид
№
1 2 3
4
5
Символ А В АВ АА ВА
№
6
7
8
9
10
Символ ААВ ВВ ВАВ ВВА ВВАА
№
11
12
13
14
Символ ААА АВА АААА ААААВ
Кодированная последовательность имеет вид: 0А 0В 1В 1А 2А 4В 2В
5В 7А 9А 4А 3А 11А 13В.
Якоб Зив (1931, Палестина —
н.в.)
д.т.н.,
профессор,
израильский ученый и инженер в
области
телекоммуникаций,
соизобретатель
словарных
алгоритмов сжатия информации
(LZ77, LZ78) вместе с А.
Лемпелем.
1.2.4. Расширение алфавита
Пусть ИДС без памяти с объемом символов M имеет энтропию
H  A  . Расширим алфавит источника на N соседних символов, т.е.
рассмотрим источник без памяти с символами Ai ... A j , i  1, M , j  1, M с
объемом M N . Энтропия такого источника H  A    NH  A  .
Расширение алфавита, однако, может повысить эффективность
кодирования Шеннона-Фано, за счет более точного приближения к
границе Шеннона.
Действительно преобразуем (29) к виду
19
M
M
M



 1 
 1 
 
  1. (30)
PAk log 2 
PAk lk 
PAk log 2 




P
A
P
A
k  k 1
k 


k 1
k 1
Получим для ИДС без памяти
H  A  l  H  A  1 .
(31)
Применяя расширение алфавита на N соседних символов, получим
H  A  l   H  A  1 .
(32)
Новый источник A имеет алфавит объемом M N , и если поделить
на число символов в последовательности N соседних символов, то
получим более точное неравенство для средней длины неравномерного
кода Шеннона-Фано.
1
H  A   l  H  A  .
(33)
N
20
ЛЕКЦИЯ №12
1.3.ТЕОРЕМА ШЕННОНА О КОДИРОВАНИИ ИСТОЧНИКА
1.3.1. Теорема об асимптотической равновероятности
Последовательность дискретных случайных величин называется
энтропийно устойчивой, если
 1 

i

a



n
P n
1      ,
(34)
1



 M  i a n 

  n


каковы бы ни были  ,  0 , найдется N  ,  , такое, что n  N  ,  .
Теорема 2. «Об асимптотической равновероятности».

Если a n - энтропийно устойчива, то множество реализаций можно
разбить на два подмножества An - нетипичных последовательностей и Bn
- типичных последовательностей так, что
1) Суммарная вероятность реализаций из An исчезает, т.е.
PAn   0 при n   .
2) Реализации из Bn становятся равновероятными в смысле
соотношения


ln Pa n   ln Pa n 
 
 0 , при n   , a n , a n  Bn .

ln Pa n 
3) Число реализаций Bn - N тип n  удовлетворяет соотношению
log 2  N тип n 
 1.
(35)

nH a n 
Доказательство теоремы 2.
1
1
1. Пусть   ,   .
m
m
2. В соответствии с определением энтропийной устойчивости имеем
 1 

i

a


n
1  1

P n
1    ,
(36)
1

m
m


 M  i a n 

  n


3. Множество An определим как множество реализации
удовлетворяющих неравенству

i a n 
1 
1
1 1
 1
при N  ,   n  N 
,
 . (37)
 1  ,
Mi a n 
m
m m
 m  1 m  1
21
4. Тогда в силу (36) PAn   0 при n   .
5. Множество Bn определим как множество реализаций,
удовлетворяющих неравенству
1
1





(38)
1  Mian   ia n   1  Mian 
 m
 m


i a n   ia n   
6. Найдем
, a n , a n  Bn ,

i a n 
1
1





т.к. 1  Mi a n   i a n   1  Mi a n , то вычитая наибольшее
 m
 m
из наименьшего, получим
1
1






1  Mi an   1  Mi an 
i an   i an   m 
 m




i an 
i an 
.


2Mi an 
2Mi an 
2



0

1

i an m

m 1
1  Mi an m
 m
 1 

7. Т.к. i a n   log 2    , то
 Pa n 

 1
 1 Mi a n 

2  m
 Pa

 1
  1  Mi a n 

 m
, a n  Bn
n 2
(39)
8. Т.к. в соответствии с определением множества Bn в п.5
доказательства и в силу (11), имеем
 1
(40)
1    PBn   1.
 m
9. В соответствии с п. 6 доказательства, из которого следует
равновероятность последовательностей, запишем
PB  
N тип n    n , a n  Bn .
Pan 
Тогда из (39), (40) получим неравенство, в левой части которого
наименьшее двух неравенств делится на наибольшее, а в правой части
наибольшее делится на наименьшее


 1
 1
 1 Mi a n 
 1 Mi a n 
1

 N тип n   2  m 
.
1  2  m 

m
(41)
22
Последнее утверждение теоремы следует
логарифмирования и перехода m   .
При n   получим следующее соотношение
из
N тип n   2 nH  A .
(41)
после
(42)
Теорема 3. «Теорема Шеннона о кодировании источника с
памятью». Существует способ кодирования и декодирования символов
источника дискретных сообщений, при котором средняя длина кодовой
последовательности символов с основанием m удовлетворяет неравенству
H ( A)
l
,
log 2 m
и вероятность ошибки декодирования может быть сделана сколь
угодно малой величиной.
Доказательство. Рассматривая ИДС с памятью для кодирования
последовательностей символов на выходе можно использовать теорему об
асимптотической равновероятности (Теорема 2) в соответствии с которой
все последовательности на выходе такого источника можно разделить на
типичные, вероятность появления которых, примерно одинакова, а их
число N тип n   2 nH  A , где n-число символов в последовательности и
нетипичные, вероятность появления которых  0.
Границу Шеннона можно достичь, если обеспечить кодирование (т. е
передачу) только типичных последовательностей и отбрасывание
нетипичных. При таком способе кодирования естественно часть
информации теряется, но в соответствии с теоремой 2 вероятность ошибки
0. В соответствии с вышеизложенным, закодируем типичные
последовательности равномерным кодом с основанием m , тогда
m nk  N тип n   2 nH  A ,
где n k - длина последовательности кодовых символов.
Т.о. получим
n
H  A
l k 
.
n log 2 m 
23
1.4. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ
ДИСКРЕТНОГО КАНАЛА СВЯЗИ
n 

...x1 , x 2 ,..., xn ,...

 
xn
Дискретн
ый канал
связи
xi  X  { X 1,..., X M }

Pxn 
H(X )
yn
yi  Y  {Y1 ,..., YM }
Совместная вероятность
 
Pxn , yn 
Условные вероятности
H(X Y)
n 

... y1, y2 ,..., yn ,...

 
 
Pxn yn 
 
Pyn xn 

Py n 
H (Y )
H (Y X )
Рисунок 3 – Информационные характеристики
дискретного канала связи
Используя условные распределения последовательностей символов
на входе и выходе можно определить среднее количество информации,
содержащиеся во входных символах при фиксированной выходной
последовательности – условную энтропию входа при фиксированном
выходе
1
 
1
H ( X Y )  lim
Pxn , y n log 2   .
(43)
Pxn yn 
n n  

xn yn 
Полученная величина H ( X Y ) называется ненадёжностью канала
связи и характеризует неопределенность в значении передаваемых
символов, возникающую в канале вследствие воздействия помех.
Аналогично можно получить условную энтропию выхода при
фиксированном входе
 
1
1
H (Y X )  lim
Pxn , y n log 2   .
(44)
Pyn xn 
n n  

xn yn 
Полученная величина H (Y X ) называется энтропией шума канала
связи и характеризует среднее количество информации, создаваемое на
выходе канала связи источником помех.
§ Свойства условной энтропии:
1. H ( X | Y )  0 , H (Y | X )  0 следует прямо из определения.
24
2. Если вход и выход канала связи однозначно связаны, то
H ( X | Y )  0 , H (Y | X )  0 .
Доказательство. Если вход канала связи однозначно связан с
 

выходом, то для любой последовательности xn , yn  xn , то






Pxn , yn  xn
Pyn , y n  xn
 
 
Pxn , yn   

 , Pxn , yn   

 .
0
,
y

x
0
,
y

x
n
n
n
n


Условные вероятности


 
yn  xn
Pxn , yn  1,
 
Pyn xn  


 ,

y n  xn
Pxn 
0,


 
yn  xn
Pxn , yn  1,
 
Pxn y n  


 .

y n  xn
Pyn 
0,
Подставляя полученные выражения в (43) и (44), учитывая, что
1
lim x log 2    0 , получим H ( X Y )  0 , H (Y | X )  0 .
x 0
 x
3. Если вход и выход статистически независимы, то H ( X Y )  H ( X ) ,
H Y X   H Y  . Это прямо следует из формул (43) и (44).
4. Условные энтропии H  X Y  , H Y X  удовлетворяют неравенствам
H Y X   H Y  , H  X Y   H  X  .
Доказательство.

1
Pxn 
 
H ( X Y )  H ( X )  lim
Pxn , yn  log 2   
Pxn yn 
n  n  
xn yn 
.


1
   Pxn Pyn  
 lim
Pxn , yn 
 1  0
 
P

x
,
y

n  n  
n n


x y 


n
n
Если H Y  это общая хаотичность выхода дискретного канала,
H Y X  это хаотичность выхода, создаваемая источником шума в канале,
то количество передаваемой информации по каналу связи можно
определить
I  X , Y   H Y   H Y X  ,
и аналогично рассуждая, можно записать
I  X , Y   H  X   H  X Y   H Y   H Y X  .
(45)
Полученная величина равна среднему количеству информации,
приходящемуся на один символ, передаваемому по дискретному каналу
связи. Величину I  X , Y  называют также взаимной информацией входа и
выхода канала.
Выражение (45) можно переписать в виде
25
I X , Y   H ( X )  H ( X Y ) 


1
1
1
 
 

 lim 
Pxn , yn  log 2  
Pxn , yn  log 2    
Pxn   
Pxn yn 
n  n   
xn yn 
 xn yn 

  

Pxn yn 
1
 
 lim 
Pxn , yn  log 2


Pxn  
n  n   
 xn yn 


  
1
Pxn , yn  
 
 lim 
Pxn , yn  log 2 
 ,
Pxn Pyn 
n  n   
 xn yn 


 

Pxn , yn  
1
 
I  X , Y   lim 
Pxn , y n log 2 
.
(46)

Pxn Pyn  
n n   
 xn yn 






26
ЛЕКЦИЯ №13
§ Свойства взаимной информации:
1. I ( X ,Y )  I (Y , X ) , следует прямо из (46).
2. I ( X ,Y )  0 , следует из (45) и 4-го свойства условной энтропии.
3. Если X и Y независимые дискретные случайные величины, то
I ( X ,Y )  0 , следует из (45) и 3-го свойства условной энтропии.
4. При отсутствии помех в канале I ( X ,Y )  H ( X )  H (Y ) , следует из
(45) и 2-го свойства условной энтропии.
5.
Справедливы
неравенства
I ( X , Y )  H ( X )  log 2 М
и
I ( X , Y )  H (Y )  log 2 М , следует из (45), 4-го свойства условной энтропии
и 3-го свойства энтропии.
n
Если для дискретного канала задана скорость передачи vk 
t
число передаваемых символов в единицу времени, то скорость передачи
информации по каналу можно определить в виде
I ( X , Y )  vk I ( X , Y ) , бит с  .
(47)
Пропускная способность канала это максимальное количество
информации, которое можно передать по дискретному каналу связи,
подключая к входу все возможные источники дискретных сообщений
С  max I ( X , Y ) , или С   max I ( X , Y ) .
X
(48)
X
Если вход и выход канала статистически независимы, то из 3-го
свойства взаимной информации следует, что С  0 .
Если вход и выход канала связи однозначно связаны, то из 2-го
свойства условной энтропии и 5-го свойства энтропии следует
С  max H ( X )  log 2 M  , и С   log 2 M  t .
(49)
X
Из последнего соотношения следует очевидный факт, что
пропускная способность дискретного канала связи без помех равна
технической скорости передачи.
§ Пропускная способность симметричного q-ичного канала без
памяти (qСК):
Модель дискретного канала qСК без памяти предполагает, что
 p
n
, yi  xi
 

Pxn , yn  
Pxi , yi , Pyi xi    M  1
,
(50)

yi  xi
i 1
 1  p,
где p - вероятность ошибки в канале.

27
Для дискретного канала без памяти можно записать
С  max I ( X , Y )  max H Y   H Y X   max H Y   H Y X  ,
X
X
X

1
n  n 

1
Pxn , yn  log 2   

Pyn xn 

H (Y X )  lim
xn yn 
n
1
 lim
n  n 
Pxi , yi  log 2
 

xn yn  i 1
1

n
 Pyi xi 
i 1
n
1
 lim
n  n 
n
 


Pxi , yi 
xn yn  i 1


k 1
Pxk , yk  log 2
xk yk 


Pxk 
xk 


log 2
Pyk xk 
Pyk xk log 2
p
Pyk xk 
1
yk 

1


1
Pyk xk 

p

 Pxk   M  1 M  1 log 2  M  1   1  p log 2 1  p  
xk 
 p 
  p log 2 
  1  p log 2 1  p ,
 M 1
 p 
maxH Y   H Y X   maxH Y   p log 2 
  1  p  log 2 1  p  .
X
X
 M 1

n

n
 1 
1

  
max H Y   max  lim
Pyi 
log 2 
P

y

X
X  n  n 
i 

yn  i 1
i 1


.


 1 

 
 max 
Pyi  log 2 


P
y
X 
i 

 yi 

1
Пусть Pxi  
, тогда
M



Pyi  
1
1 
p

1
 Pyi xi Pxi   M  Pyi xi   M  M  1 M  1  1  p   M .
xi 
xi 
28
В соответствии с 5-м свойством энтропии maxH Y   log 2 M  .
X
Окончательно получим для qСК
 p 
C  log 2 M   p log 2 
  1  p  log 2 1  p  .
 M 1
Для двоичного канала 2СК
C  1  p log 2  p   1  p log 2 1  p  .
(51)
(52)
1
0.8
0.6
cc( p )
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
p
Рисунок 4 - Зависимость пропускной способности двоичного
симметричного канала без памяти от вероятности ошибки
Рассмотрим помехоустойчивость когерентного приемника для
противоположенных сигналов. В соответствии с материалом лекции №5,
см. выражение (16), получим
 1  r E s
p  1  erf 
N0

Подставляя в (52), получим

  r  1  1  erf q  .


29
1
0.8
0.6
c( q)
0.4
0.2
0
0
1
2
3
4
q
Рисунок 5 - Зависимость пропускной способности двоичного
симметричного канала без памяти от отношения сигнал-шум для
когерентного приема противоположенных сигналов
1.5. ТЕОРЕМА ШЕННОНА О ПРОПУСКНОЙ СПОСОБНОСТИ
ДИСКРЕТНОГО КАНАЛА СВЯЗИ
Теорема 4. «Теорема Шеннона о пропускной способности канала
связи». Если производительность источника Н  A  C  , то найдется такой
способ кодирования и декодирования символов в канале, при котором
вероятность ошибки может быть сделана сколь угодно малой величиной,
при не соблюдении этого условия такого способа кодирования не
существует.
Доказательство.
Доказательство теоремы основано на идее случайного кодирования и
теореме об асимптотической равновероятности.
30
Пусть выполняется условие теоремы, т.е. Н  A  C  , соответственно
Н  A  C . В соответствии с определением пропускной способности,
очевидно, что в этом случае
Н  A  Н  X  .
(53)
Пусть в соответствии с теоремой 2 об асимптотической
равновероятности в канал связи передаются только типичные
последовательности так, что кодер случайным образом сопоставляет
типичные последовательности на выходе источника, типичным
последовательностям на входе канала. В соответствии с (42), очевидно, что
N тип  A  N тип  X  .
(54)
При равновероятном выборе типичной последовательности для
кодирования в канале вероятность того, что одна из типичных
последовательностей не используется при кодировании
N тип  X   N тип  A 
N
 A  .
 1  тип
(55)

N тип  X 
N

X


тип

На выходе при приеме некоторой кодовой комбинации вследствие
воздействия шумов возникает неопределенность в значении символов
входной последовательности. Число типичных последовательностей среди
них N тип  X Y .
Если среди них только одна использована для кодирования, то ее
идентификация происходит без ошибки. Если среди них две и более
типичных последовательностей использовались для кодирования, то на
приеме их нельзя различить и возникает ошибка при декодировании. Т.о.
вероятность безошибочного приема, это произведение N тип  X Y   1
вероятностей того, что одна из типичных последовательностей не
используется при кодировании
 X Y 1
N

N тип  A  тип

Pпр.дек.  1 
.
N

X


тип

Т.к. N тип  X Y   1 , то
N
(56)
X Y 

N тип  A  тип


Pпр.дек.  1 
.
(57)
N

X


тип

В соответствии с формулой бинома Ньютона

N
 A N X Y  .
Pпр.дек.  1  тип
(58)
тип

N

X


тип

В соответствии с выражением (42), получим следующее выражение
nH  A H  X Y  H  X  
1  Pош  Pпр.дек.  1  2
(59)
.


31
Для вероятности ошибки декодирования, получим экспоненту
вероятности ошибки
Pош  2 nС  H  A .
(60)
Полная вероятность ошибки должна учитывать случай, когда на
приеме появляется нетипичная последовательность, что автоматически
означает ошибку при приеме. Если вероятность этого события Pнетип ,
тогда полная вероятность ошибки имеет вид
P  Pнетип  1  Pнетип Pош .
(61)
Используя теорему об асимптотической вероятности, при n  
Pнетип  0 , в соответствии с (60) Pош  0 , и соответственно P  0 .
Докажем вторую часть теоремы. Если условия теоремы Шеннона не
выполняются, то при n   Pнетип  0 Pош - неограниченна, и
соответственно P также неограниченна. Кроме этого, если найдется такой
способ кодирования, при котором Н  A  C  , то в полученном канале
I  X , Y   H  X   H  X Y   C  ,
что
противоречит
определению
пропускной способности.
1.6. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ РЕАЛЬНЫХ
КАНАЛОВ СВЯЗИ
Реальный канал связи предполагает объединение непрерывного
канала связи, модулятора и демодулятора в дискретный канал связи.
Т.о. оказывается зафиксированной не только модель канала, помехи,
но и вид модуляции, способ или алгоритм демодуляции. В тоже время из
первой части курса мы убедились, что оптимизация сигнальной
конструкции и алгоритмов приема при фиксированной модели канала
имеет огромное значение!
Ранее мы для двоичного канала 2СК получили значение пропускной
способности в виде (52).
При фиксированном непрерывном канале, например, канале в
котором осуществляется когерентный прием на фоне БГШ и
зафиксированном алгоритме демодуляции, получим
C r , v k   v k 1  pr , v k , SNR  log 2  p r , v k , SNR  
,
(61)
 1  pr , v k , SNR  log 2 1  p r , v k , SNR 
где
 1  r   SNR  

  ,
pr , v k , SNR   1  erf 
(62)

2  vk  


32
2 Ps
- отношение сигнал-шум, приведенное к 1 Гц полосы
N0
частот сигнала, т.е. q  SNRf .
Максимум пропускной способности в таком канале достигается при
v k   , r  1 и равен

C max
 0.46  SNR бит с .
(63)
При некогерентном приеме максимум пропускной способности
достигается при использовании ортогональных сигналов r  0 , v k   и
равен

C max
 0.0825  SNR бит с .
(64)
SNR 
33
ЛЕКЦИЯ №14
1.7. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ НЕПРЕРЫВНОГО
КАНАЛА СВЯЗИ
Пусть источник непрерывных сообщений (ИНС) выдает
последовательность вещественных отсчетов случайного сигнала,
1
ограниченного полосой частот 2 F , с интервалом дискретизации t 
.
2F
Будем считать полученные отсчеты статистически независимыми.
Непрерывный канал связи (НКС), на входе и выходе которого
наблюдаются такие отсчеты, является каналом без памяти.
x(t)
x2
x1
y(t)
xn
y1
y2
yn
НКС
t
t
t
t
Рисунок 6 – Непрерывный канал связи
Для изучения информационных характеристик такого канала
воспользуемся методом «от известного». Для этого рассмотрим
дискретный канал связи (ДКС) без памяти, который получится, если
подвергнуть процедуре квантования отсчетов вход и выход непрерывного
канала.
n 
n 


... y1, y2 ,..., yn ,...
...x1, x2 ,..., xn ,...
Дискретн


 
 
ый канал
связи
xn
yn
xi  X  { X 1,..., X M }
yi  Y  {Y1 ,..., YM }
Совместная вероятность
PX i 
H(X )

P X i ,Y j
 
P Yj
H (Y )
Условные вероятности




P Xi Yj
H(X Y)

P Yj Xi
H (Y X )
Рисунок 7 – Информационные характеристики
непрерывного канала связи
В этом канале справедливы следующие обозначения:
34
X i  xmin  ix , Y j  y min  jy - символы ДКС;
P X i , Y j  p X i , Y j  x  y , P X i   p  X i  x , P Y j  p Y j  y
- вероятности появления символов;
p  x , y  , p  x  , p  y  - плотности вероятности, описывающие
статистику НКС без памяти.




 
 
Тогда взаимную информацию входа и выхода полученного ДКС
можно определить по формуле (21), для канала без памяти, получим
  

1
Pxn , yn  
 
I д  X , Y   lim 
Pxn , yn  log 2 


Pxn Pyn  
n  n   
 xn yn 


n



Pxi , yi  
n


1
i

1

 lim
Pxi , yi  log 2
n
n

n  n   
 xn yn  i 1
Pxi 
Pyi 



i 1
i 1


 



n

n
1
Pxi , yi  
 lim 
Pxi , yi  log 2

Pxi Pyi  
n  n   
i 1
 xn yn  i 1

n


PX i , Yi  


PX i , Yi  log 2
,
PX i PYi 
 i j
i 1


 



Т.о.
n
I д  X ,Y  

i

PX i , Yi 
j
i 1
log 2
PX i , Yi 
.
PX i PYi 
(65)
Переходя к пределу, если он существует, получим количество
информации, передаваемое по НКС
n


PX i , Yi  

I  X , Y   lim I д  X , Y   lim 
PX i , Yi  log 2

PX i PYi 
x  0
 x  0
i 1

y  0
y 0 i j



 lim 
x 0
y 0 i

pX i , Yi xy 
pX i , Yi xy log 2

pX i xpYi y 
j
i 1





n

 p  x, y  
p  x, y  log 2 
dxdy,
 px  p y  
35
Т.о.
 p x , y  
dxdy.
p  x, y  log 2 
p

x

p

y



Последнее выражение можно переписать в виде
 p  x, y  
I  X ,Y  
p x, y  log 2 
dxdy 
p

x

p

y



I  X ,Y  

(66)

 1 
 1 
dxdy.
p  x  log 2 
dx  p  x, y  log 2 

p

x

p

x
y





Назовем первый интеграл дифференциальной энтропией входа НКС




h ( x) 


 1 
dx ,
p ( x) log 2 
p
(
x
)


(67)
второй интеграл дифференциальной условной энтропией входа НКС
  
h( x | y)  
  p( x, y) log 2 px | y dxdy .
(68)
 
Тогда получим
I  X , Y   h x   hx y   h y   h y x .
(69)
§ Свойства дифференциальной энтропии:
1. h(x)   ,   .
Доказательство. Определим энтропию источника непрерывных
сообщений без памяти. Для этого проквантуем символы на выходе
источника и перейдем к пределу

1 
H  X   lim H д  X   lim 
PX i log 2

PX i  
x0
x0
 i



1

  h x   lim log x.
 lim
pX i x log 2
2

pX i x 
x0
x 0
 i

Т.о. количество информации, содержащиеся в непрерывном
сообщении, может быть равно бесконечности, а дифференциальная
энтропия является некоторой ограниченной добавкой к бесконечности.
Так, в теории информации функционал дифференциальной энтропии
интерпретируется как средняя информация непрерывного источника. В
теории
вероятностей
функционал
дифференциальной
энтропии


36
интерпретируется
как
мера
неопределённости
непрерывного
распределения.
Измерение дифференциальной энтропии в битах условно, т.к.
дифференциальная энтропия не являются абсолютной шкалой, и по этой
причине может быть отрицательной.
Действительно
определим
дифференциальную
энтропию
равномерной случайной величины, получим

h x  


 1 
dx 
p ( x) log 2 
p
(
x
)


b

a
1
log b  a dx  log 2 b  a 
b  a  2
(70)
Если b  a   1 , то h x   0 .
2. Если X – источник непрерывных сообщений без памяти, и каждое
сообщение x - гауссовская случайная величина с
математическим
ожиданием m и дисперсией  x2 , то
p x  
1
2 x2

e
 x m 2
2 x2
,

 x m 2 

2 

h ( x) 
p ( x ) log 2  2 x2 e 2 x dx 








 

1
 log 2 2 x2   p ( x)dx  log 2 e 
p ( x ) x  m 2 dx 
2
2 x
 



1
 log 2 2 x2  log 2
 e   log 2
2e x2 .
Т.о.
h( x )  log 2 2e x2 .
(71)
3. Если X – источник непрерывных сообщений без памяти, и каждое
сообщение x - случайная величина с математическим ожиданием m и
дисперсией  x2 , то справедливо неравенство h( x )  log 2 e 2 x2 .
Доказательство. Рассмотрим разность дифференциальных энтропий
произвольной случайной величины h (x ) и дифференциальной энтропии
гауссовской случайной величины hg  x 
37


 1 
dx .
p g ( x) log 2 
 p g ( x) 




Используя ранее полученное соотношение

 x m 2 


2
h( x) 
p ( x ) log 2  2 x2 e 2 x dx  log 2 2e x2 ,





для любого p  x  , получим
h x   hg  x  
h x   hg  x  

 1 
dx 
p ( x) log 2 
 p( x) 








 1 
p ( x) log 2 
dx 
p
(
x
)



 1 
dx 
p ( x ) log 2 
 pg ( x) 




 p g ( x) 
dx 
p ( x) log 2 
p
(
x
)








 p g ( x) 
 p g ( x) 
1
dx 
p ( x) ln 
p ( x)
 1dx  0.
p
(
x
)
ln

2

p
(
x
)






Т.о. среди всех случайных величин с равной дисперсией
максимальной дифференциальной энтропией обладает гауссовская
случайная величина.
1

ln 2 
Количество информации, передаваемое по непрерывному каналу в
единицу времени можно найти в виде
I  X ,Y 
I  X , Y   vk I  X , Y  
 2 FI  X , Y .
(72)
t
Пропускная способность непрерывного канала связи может быть
определена как
C   max I  X , Y   max vk I  X , Y  
X
X

max
p  x , x2  Px
vk I  X , Y .

(73)
Рассмотрим НКС с аддитивным гауссовским шумом
38
x
y
+
n
Рисунок 8 – НКС с аддитивным гауссовским шумом
Пусть x - случайная величина с нулевым мат. ожиданием и
дисперсией  x2  Px , n - гаусовская случайная величина с нулевым мат.
ожиданием и дисперсией  n2  Pn , y - гаусовская случайная величина с
нулевым мат. ожиданием и дисперсией  2y   x2   n2 .
В соответствии со свойством дифференциальной энтропии №3,
получим
C 
max
I ( X , Y ) 
max
vk h( y )  h( y | x)  
px , x2  Px 
px, x2  Px 


2
2

 vk log 2 2e( x   n ) 
max

h( y | x ) 


p  x , x2  Px


Зафиксируем х. Тогда распределение на котором максимальна
дифференциальная энтропия у является гаусовским с дисперсией  n2 и
математическим ожиданием равным х.
Т.о.




max
p  x , x2  Px
h( y | x )  

 pn ( y  x) log pn ( y  x)dy 


  y'  y  x  
.
 pn ( y' ) log pn ( y' )dy'  h(n)

Тогда
  x2   n2  vk
  x2  vk
vk


  log 1  Px , бит ,
C   log 2
 log 2 1 
2

с
 2  2
 2 2
2
 Pn 

n


n
или в виде, который известен как формула Шеннона
 Px 
.

(74)
C  F log 2 1 
 P 

n 
Рх – средняя мощность полезного сигнала, Рn– средняя мощность
шума.


39
При фиксированном отношении сигнал-шум и полосе пропускания
канала, увеличивающейся до бесконечности ( F   ), существует предел
пропускной способности непрерывного канала в виде

 P 

Cmax
 lim  F log 2 1  x   
 P 
F 

n 



Px   Px


 lim F log 2 1 

log 2 e   log 2 e SNR
 N0 F   N0
F  



 
(75)
При увеличении отношении сигнал-шум до бесконечности и
фиксированной полосе пропускания канала пропускная способность
непрерывного канала связи стремиться к бесконечности со скоростью
логарифмической функции.
Формулы (63), (64) и (75) позволяют сформулировать главный вывод
теории информации: наличие случайных помех в канале связи является
единственным принципиальным фактором, ограничивающим скорость
передачи информации.
40
ЛЕКЦИЯ №15
2. ТЕОРИЯ КОДИРОВАНИЯ
2.1. ОБЩАЯ ХАРАКТЕРИСТИКА И КЛАССИФИКАЦИЯ
ПОМЕХОУСТОЙЧИВЫХ КОДОВ
Задача помехоустойчивого кода – защита информации от помех в
канале. В соответствии с основной теоремой К.Шеннона, если пропускная
способность дискретного канала больше производительности источника,
то при увеличении длины помехоустойчивого кода будет обеспечена
любая заданная вероятность ошибки при передаче информации. При
малых вероятностях ошибки требуемая длина кода может составить
значительную величину, что означает увеличение задержки в принятии
решения о приеме символа.
На практике задачи теории кодирования это поиск наилучших
кодов при заданной конечной скорости, поиск эффективных процедур
кодирования и декодирования.
Помехоустойчивые коды
Каскадные коды
Свёрточные коды
Турбо-коды
Линейные
Циклические
Коды макс. длины
Коды Голея
Блочные коды
Рида-Маллера
БЧХ коды
Квадратичновычетные коды
Коды РидаСоломона
Нелинейные
Коды Адамара
Коды Гоппы
Коды Хэмминга
Рисунок 9 - Классификация помехоустойчивых кодов
и наиболее важные коды
Блочное
кодирование
происходит
следующим
образом.
Информационные символы на входе кодера разбивается на блоки длины k.
Каждому блоку в кодере ставится в соответствие блок символов кода
длины n, n  k .
41
k
БК
n
Рисунок 10 - Схема блокового кодирования
Так формируется блочный (или блоковый) n, k  код. Основные
характеристики блокового кода это скорость R и избыточность Q .
k
n 1
R ,
Q 
(76)
n
k R
Сверточное кодирование схематично можно описать следующим
образом.
k
l
СК
n
Рисунок 11 - Схема сверточного кодирования
Информационные символы на входе сверточного кодера разбивается
на блоки длины l с перекрытием l  k  символов. Каждому блоку l
символов в кодере ставится в соответствие блок символов на выходе
длины n, l- длина кодового ограничения.
Давид
Форни
(David
"Dave" Forney, Jr.) (6,
1940) американский
инженер - исследователь в
области теории и техники
связи.
Изобретатель
каскадных кодов (1966) и
одного из алгоритмов
декодирования БЧХ кодов
– алгоритма Форни.
Каскадным кодом называется код, полученный последовательным
применением к потоку информационных символов нескольких
помехоустойчивых кодов. Это могут быть и сверточные, и блоковые коды,
и их комбинации. Комбинирование может быть как последовательным, так
42
и параллельным (гнездовые коды). В последнем случае получают
эффективные коды с большими длинами.
Принцип помехоустойчивого кодирования иллюстрирует следующий
рисунок.
Пространство
кодовых комбинаций
Ошибка при передаче
кодовой комбинации
Разрешенные
кодовые комбинации
Запрещенные
кодовые комбинации
Рисунок 12 - Принцип помехоустойчивого кодирования
Суть в том, что передаются только разрешенные комбинации кода.
Появление на приемной стороне запрещенной означает, что в канале
произошла ошибка.
Исправление ошибки может быть выполнено перезапросом (при
наличии информационной обратной связи) или за счет «окружения »
разрешенных кодовых комбинаций запрещенными так, что при появлении
ошибки можно понять какая кодовая комбинация передавалась. Например,
на рисунке 4 ошибочная кодовая комбинация получена переходом из
ближайшей разрешенной, то исправляя по принципу ближайшей
разрешенной, можно гарантировано исправить данную ошибку без
перезапроса.
Блоковый код называется линейным, если множество его
разрешенных кодовых комбинаций замкнуто относительно линейных
операций, т.е. поразрядного сложения, вычитания и умножения на
константу.
Линейный блоковый код называется циклическим, если множество
его разрешенных кодовых комбинаций замкнуто относительно операции
циклического сдвига разрядов.
2.2. ОСНОВНЫЕ ПОНЯТИЯ АБСТРАКТНОЙ АЛГЕБРЫ
1. Группой G называют множество элементов (чисел) с определенной
для них операцией *, обладающее следующими свойствами:
a) замкнутость: для a, b  G , c  a * b  G .
b) ассоциативность: для a, b, c  G , a * b * c   a * b  * c .
43
c) существование единицы: существует элемент e  G , такой, что
a  G, e * a  a * e  a .
d) существование
обратного
элемента:
для
a  G , b : a * b  b * a  e .
2. Группа, содержащая конечное число элементов называется
конечной группой, число элементов, называется порядком группы.
3. Группа, в которой операция * коммутативна, называется абелевой
группой.
4. Некоторое подмножество H группы G называется подгруппой
группы G, если элементы H
образуют группу относительно
операции *.
5. Каждый элемент h группы G образует циклическую подгруппу вида
h, h * h, h * h * h,..., e . Число элементов в циклической подгруппе
называется порядком элемента h.
6. Порядок конечной группы делится на порядок любого из ее
элементов.
7. Кольцом R называется множество (чисел) с двумя определенными
на нем операциями – сложением (+) и умножением (),обладающее
следующими свойствами:
a) относительно операции сложения кольцо является абелевой
группой.
b) замкнутость: для a, b  R, c  ab  R .
c) ассоциативность: для a, b, c  R, abc   ab c .
d) дистрибутивность:
существует
элемент
a, b, c  R, ab  c   ab  ac , b  c a  ba  ca  .
8. Коммутативным кольцом называют кольцо с коммутативной
операцией умножения.
9. Кольцо, обладающее единственным элементом относительно
операции умножения, называют кольцом с единицей.
10. Примерами колец являются Z - коммутативное кольцо с единицей,
множество квадратных матриц – некоммутативное кольцо с
единицей, множество многочленов от одной переменной –
коммутативное кольцо с единицей.
11. Полем F называется множество (чисел) с двумя определенными на
нем операциями – сложением (+) и умножением (),обладающее
следующими свойствами:
a) относительно операции сложения поле является абелевой
группой.
b) относительно операции умножения поле является абелевой
группой.
c) дистрибутивность:
существует
элемент
a, b, c  F , a b  c   ab  ac , b  c a  ba  ca  .
44
12. Примерами полей являются множества R, C, Q .
13. Поле, имеющее конечное число элементов, называется полем Галуа
или конечным полем, обозначается GF q  , где q - число элементов
поля.
14. Наименьшее поле Галуа GF 2  образуют числа 0,1 с операциями
сложения и умножения по модулю 2, определенными следующим
образом
 0 1
0 0 1,
1 1 0
* 0 1
0 0 0
1 0 1
15. Поле Галуа GF 3 образуют числа 0,1,2 с операциями с
операциями сложения и умножения по модулю 3, определенными
следующим образом

0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
*
0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
16. Множество целых чисел с операциями сложения и умножения по
модулю q образует коммутативное кольцо с единицей и обозначается
Zq .
17. Кольцо Z q является полем GF q  , если q – простое число.
Эвари́ст Галуа́ (25 октября 1811,
Бур-ля-Рене
(фр.),
О-де-Сен,
Франция — 31 мая 1832, Париж,
Франция)
—
французский
математик,
основатель
современной
высшей
алгебры.
Радикальный
революционерреспубликанец, был застрелен на
дуэли в возрасте двадцати лет. За
20 лет жизни и 4 года увлечения
математикой Галуа успел сделать
открытия, ставящие его на уровень
крупнейших математиков XIX века.
Галуа
исследовал
проблему
нахождения
общего
решения
уравнения произвольной степени, то
есть задачу, как выразить его корни
через коэффициенты, используя
только арифметические действия и радикалы. Но наиболее ценным
45
был даже не этот результат, а те методы, с помощью которых Галуа
удалось его получить. Решая эти задачи, он заложил основы
современной алгебры, вышел на такие фундаментальные понятия, как
группа (Галуа первым использовал этот термин, активно изучая
симметрические группы) и поле (конечные поля носят название полей
Галуа). Работы Галуа, немногочисленные и написанные сжато,
поначалу остались непоняты современниками. Огюст Шевалье и
младший брат Галуа, Альфред, послали последние работы Галуа Гауссу
и Якоби, но ответа не дождались. Только в 1843 году открытия Галуа
заинтересовали Лиувилля, который опубликовал и прокомментировал
их (1846). Открытия Галуа произвели огромное впечатление и
положили начало новому направлению — теории абстрактных
алгебраических структур. Следующие 20 лет Кэли и Жордан развивали
и обобщали идеи Галуа, которые совершенно преобразили облик всей
математики.
18. Векторное пространство над полем F (обозначается Fn) называется
линейным пространством, если вектора в этом пространстве
можно складывать и вычитать, а также умножать на скаляр (элемент
поля F), т.е.:
1) Для любых двух элементов x, y  Fn однозначно определен 3-й
элемент z , называемый их суммой, причем
x  y  y  x ; x  (y  z)  (x  y)  z ; x  0  x ; x  (  x)  0 .
2) Для любых  ,   F и x, y  Fn справедливы следующие свойства:
 ( x )  ( )x ; 1x  x ; (   )x  x  x ;
 ( x  y )   x  y .
19. Непустое подмножество векторного пространства называется
подпространством, если оно является векторным пространством
относительно исходных операций сложения векторов и умножения
их на скаляр.
20. Скалярным произведением векторов в линейном пространстве
называется скалярная функция 2-х аргументов ,  такая, что
x, y   y, x  ; x1  x 2 , y   x1 , y   x 2 , y ; x, y    x, y  ; где
x, x1 , x 2 , y  Fn,   F, определяемая как скалярное произведение
векторов x  ( x1 ,..., xn )T и y  ( y1 ,..., y n )T с помощью функции
n
х,у    хi уi .
(77)
i 1
21. Ненулевые вектора линейного пространства Fn
x1 , x 2 ,, x s
называются
линейно
независимыми,
если
равенство
1x1   2 x 2     s x s  0 выполняется только в случае, когда
1 ,  2 ,  ,  s  F одновременно равны нулю. Это свойство системы
46
векторов x1 , x 2 ,, x s означает, что ни один из них нельзя
представить линейной комбинацией оставшихся.
22. В линейном пространстве Fn всегда найдется не более чем n –
линейно независимых векторов, которые называются базисом
пространства Fn.
23. Пусть e1 , e 2 ,, e n – базис в Fn. Базис называется ортогональным,
если попарное скалярное произведение этих векторов
i j
0,
ei , e j  
.
(78)
σ

0
,
i

j
,
σ

F
 i
i
24. В линейном пространстве любой элемент может быть разложен по
базису (по координатам) и представлен в следующем виде


n
x
 i ei ,
(79)
i 1
где e1 , e 2 ,  , e n  - базис, 1 ,  2 ,  ,  n - координаты элемента x по
этому базису вычисляются по формуле проектирования i  x, e i  .
47
ЛЕКЦИЯ №16
2.3. ЭЛЕМЕНТЫ ТЕОРИИ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
Определим GF (q ) n - линейное пространство, определенное над
множеством n-мерных векторов с коэффициентами из поля Галуа GF (q) и
скаляров из GF (q ) . Будем считать кодовые комбинации n, k  кода
векторами линейного (векторного) пространства GF (q ) n .
Линейный блоковый код  (множество разрешенных комбинаций)
является подпространством пространства GF (q ) n . Это означает, что
множество разрешенных кодовых комбинаций замкнуто относительно
операции сложения, умножения на скаляр и содержит нулевую
комбинацию.
Расстоянием
Хемминга
между
любыми
двумя
кодовыми
комбинациями a, b из линейного пространства GF (q ) n называется число
не совпадающих разрядов этих кодовых комбинаций, и обозначается
 H a, b  .
Весом Хемминга любой кодовой комбинации a из линейного
пространства GF (q ) n называется число ненулевых разрядов этой кодовой
комбинации, и обозначается  H a  .
Минимальным кодовым расстоянием линейного блокового кода 
называется минимальное расстояние по Хеммингу между любыми двумя
разрешенными ненулевыми разрешенными комбинациями
d min  min  H a, b  , a, b   .
(80)
a b
a0
b0
dmin – исчерпывающее характеризует исправляющую способность
кода.
Теорема 5. «Об исправляющей способности линейного блокового
кода». Если линейный блоковый код имеет минимальное кодовое
48
расстояние dmin , то он обнаруживает ошибку кратности dmin-1, и
 1
d
гарантировано исправляет ошибку кратности  min
.
2


Доказательство.
Рассмотрим две самые близкие по расстоянию Хемминга
разрешенные кодовые комбинации линейного блокового кода. Выстроим
ближайшие запрещенные кодовые комбинации так, что можно
последовательно меняя только один несовпадающий разряд этих кодовых
комбинаций перейти за наименьшее число изменений, от одной
разрешенной кодовой комбинации к другой. Очевидно, что dmin равно
числу ошибок, число которых необходимо, чтобы перейти от одной
разрешенной кодовой комбинации к другой. Т.о. d min  1 - наименьшее
число обнаруживаемых ошибок.
Если для декодирования используется алгоритм поиска ближайшей
разрешенной кодовой комбинации,
aˆ  arg min H a, v  , a   , v  GF (q ) n ,
(81)
a
то наименьшее
 d min  1

.
2


число
гарантировано
исправляемых
ошибок
Утверждение 1. Для линейного блокового кода минимальный вес
ненулевых кодовых комбинаций dmin.
Доказательство.
d min  min  H a, b   min   H 0, b  a   min  H a  , a, b   . (82)
ab
a0
b 0
a b
a 0
b 0
a 0
Пусть g1 , g 2 ,  , g n – ортогональный базис в GF q n . Т.е. попарное
скалярное произведение этих векторов
i j
0,
gi , g j  
.
(83)
σ

0
,
i

j
,
σ

GF

q

 i
i
Пусть c - разрешенная кодовая комбинация линейного кода  . Т.е.


c  GF q n и одновременно c   , где   GF q n - подпространство в
GF q n . Так как  множество разрешенных кодовых комбинаций, то их
число должно быть равным q k . Т.о. все разрешенные кодовые комбинации
49
могут быть порождены как линейные комбинации базисных векторов
g1 , g 2 ,  , g k .
Т.к.  - линейное пространство, то c может быть представлена в
следующем виде
 g1,1 g1,2 ... g1,n 


k
g
g
...
g
 2,1
2,2
2,n 
c
il g l  i1 ... i k 
 iG ,
(84)

 


l 1
 g k ,1 g k ,2
g k ,n 

В полученном матричном представлении алгоритма кодирования
прямоугольная матрица G называется порождающей матрицей, векторстрока i - информационным вектором.
Оставшиеся базисные вектора g k 1 , g k  2 ,  , g n можно использовать
для построения линейного кода   , отличающегося от  тем, что он
имеет размерность n, n  k  и все его разрешенные кодовые комбинации
ортогональны всем разрешенным кодовым комбинациям кода  .
Линейный блоковый код   называют дуальным.
Пусть H - порождающая матрица дуального кода. Тогда в силу
вышеизложенного справедливо соотношение
GH T  0 .
(85)
Пусть c - разрешенная кодовая комбинация линейного кода  ,
тогда

сH T  0 .
(86)
Последнее выражение позволяет использовать порождающую
матрицу дуального кода для проверки принадлежности кодовой
комбинации к разрешенным комбинациям кода  . В этом смысле H
называют проверочной матрицей линейного кода  .
Теорема 6. «О проверочной матрице».
Линейный код  содержит ненулевую кодовую комбинацию веса
Хемминга не более w , тогда и только тогда, когда H содержит множество
из w линейно зависимых столбцов.
Доказательство.
Пусть c - разрешенная кодовая комбинация линейного кода  .
Тогда сH T  0 . Обозначим h1 , h 2 ,..., h n - столбцы матрицы H . Пусть c
имеет вес w , тогда w коэффициентов вектора строки c ненулевые. Пусть
это коэффициенты c1 , c 2 ,..., c w , тогда имеет место равенство
c1h1  c 2 h 2  ...  c w h w  0 .
(87)
Полученное равенство описывает линейную зависимость w
столбцов матрицы H .
50
Обратно, если H имеет w линейно зависимых столбцов, то можно
записать выражение (87) и из ненулевых одновременно коэффициентов
c1 , c 2 ,..., c w составить вектор-строку c , для которой сH T  0 .
Следствие 1 теоремы «О проверочной матрице».
Линейный код  имеет минимальное кодовое расстояние d min тогда
и только тогда, когда любое множество d min  1 столбцов матрицы H
линейно независимо.
Доказательство. В соответствии с утверждением 1 для линейного
блокового кода минимальный вес ненулевых разрешенных кодовых
комбинаций равен w=dmin. Тогда в силу теоремы 6 H содержит множество
из d min линейно зависимых столбцов. При этом любая линейная
комбинация d min  1 столбцов линейна независима. Действительно, если
это не так, то возможно равенство c1h1  c 2 h 2  ...  c w 1h w 1  0 , тогда
вес разрешенной кодовой комбинации будет w=dmin-1, что противоречит
исходному положению. Т.о. c1h1  c 2 h 2  ...  c w1h w1  0 .
Вывод из Следствия 1.
Для того, чтобы найти n, k  линейный код, гарантировано
исправляющий t ошибок достаточно найти n  k   n матрицу H с
коэффициентами из поля GF q  2t столбцов которой линейно
независимы.
Ричард Э. Блейхут (родился 9
июня 1937 года в Ориндже, НьюДжерси) инженер, преподаватель и
писатель, известный своей работой в
области
теории
информации,
помехоустойчивого
кодирования,
обработки сигналов и цифровых систем
связи. Получил степень бакалавра наук в
области
электротехники
Массачусетского
технологического
института, M.S. в области физики из
Технологического института Стивенса
и кандидата технических наук по
электротехнике
Корнельского
университета. Д-р Блейхут является
системным
консультантом
Ioptics
Corporation, внося свой вклад в
разработку оптических систем хранения
51
данных и работу над прототипом проигрывателя для оптического
компакт-диска размером один дюйм. В течение 30 лет д-р Блейхут
работал в Федеральном системном подразделении IBM, где он отвечал за
анализ и проектирование систем для когерентной обработки сигналов,
цифровой связи и обработки статистической информации. Автор книги
«Теория и практика кодов, контролирующих ошибки» / М.Мир.-1986г.
Линейные n, k  коды, имеющие одинаковую размерность,
отличающиеся очередностью разрядов и/или выбором базисных векторов
одного и того же подпространства  называются эквивалентными
кодами.
Обратно линейные n, k  коды эквивалентны тогда и только тогда,
когда их порождающие матрицы получаются одна из другой
перестановкой столбцов и линейными операциями над строками.
Линейный n, k  код называется систематическим, если каждая его
разрешенная кодовая комбинация содержит первые k информационных
символов и затем m проверочных.
Порождающие и проверочные матрицы такого кода имеют блочную
структуру вида
G  E  P  ,
(88)
где E - k  k единичная матрица, P - k  n  k  прямоугольная
матрица с коэффициентами из поля GF q  . Из условия (10) получим
 P 
GH T  E  P    P  P  0 .
(89)
E 
Тогда проверочная матрица систематического кода имеет вид


H   PT  E ,
где E - m  m единичная матрица.
(90)
Теорема 7. «Об эквивалентности систематическому коду».
Любой линейный блоковый код эквивалентен систематическому.
Доказательство.
Пусть G - порождающая матрица линейного блокового кода. Тогда
ее строки линейно независимы. Т.е. по крайней мере, они ненулевые и
различные.
Очевидно, что среди ненулевых и различных всегда будут такие,
какие порождаются матрицей вида (13), т.е. строки, у которых первые k
коэффициентов 1 и 0 формируют единичную матрицу.
Умножим полученные таким образом k строк матрицы (13) с
неизвестными k  т коэффициентами матрицы P на m строк проверочной
матрицы H .
52
Из условия ортогональности
строк (10) получим k  т
неоднородных уравнений, и определим P решая полученные уравнения.
Поскольку мы имеем два ортогональных базиса подпространства кода,
один из которых имеет систематический вид, то линейными операциями
можно перейти от одного к другому.
Теорема 8. «Граница Синглтона».
Минимальное кодовое расстояние линейного
n, k  кода
удовлетворяет неравенству
d min  1  n  k .
(91)
Доказательство.
В соответствии с утверждением 1 для линейного блокового кода
минимальный вес ненулевых разрешенных кодовых комбинаций равен
dmin. Строки порождающей матрицы линейного кода в систематическом
виде не могут иметь вес больше чем 1  n  k  . Отсюда и из теоремы 7
получаем (91).
Вывод из теоремы 8.
Граница Синглтона показывает, что на исправление t ошибок нужно,
по крайней мере, 2t проверочных разряда.
Ричард Уэсли Хэмминг (11 февраля 1915,
Чикаго — 7 января 1998, Монтерей) —
американский математик.
2.4. КОДЫ ХЭММИНГА
Код, гарантировано исправляющий ошибку одиночной кратности и
имеющий максимально возможную скорость, называется кодом
Хэмминга.
53
В соответствии с теоремой 5 код Хэмминга имеет минимальное
кодовое расстояние d min  3 .
Рассмотрим поле GF 2  .
В соответствии с теоремой 2 и следствием 1 проверочная матрица
n, k  кода Хемминга должна иметь любые два столбца линейно
независимыми. В поле GF 2  это означает, что выполняются следующие
соотношения
hi  h j , hi  0 , h j  0 , i  j ,
(92)
где h i - столбцы проверочной матрицы кода Хемминга.
Если m - число проверочных разрядов кода Хэмминга, то число
различных ненулевых столбцов в проверочной матрице кода Хэмминга
должно быть равным n  2 m  1 .


Т.о. Код Хэмминга в поле GF 2  имеет размер 2 m  1,2 m  1  m .
Пример 1.
Приведем пример кода Хэмминга в поле GF 2  имеющего размер
7,4.
Проверочная матрица кода Хэмминга в поле GF 2  имеет размер
3 7 . Все столбцы этой матрицы должны быть ненулевые и различные.
1 0 1 1 1 0 0


H  1 1 0 1 0 1 0.
0 1 1 1 0 0 1


Используя (15) и (13) запишем порождающую матрицу в виде
1

0
G 
0

0
0 0 0 1 1 0

1 0 0 0 1 1
.
0 1 0 1 0 1

0 0 1 1 1 1 
(93)
(94)
Рассмотрим произвольное поле GF q  .
В произвольном поле условие линейной независимости столбцов
проверочной матрицы имеет вид
h i   h j .
(95)
где h i
 ,   GF q  .
-
столбцы
проверочной
матрицы
кода
Хемминга,
54
Пусть     0 , то h i  h j  0 .
Если    , то даже если h i  h j может быть так, что h i  h j .
Чтобы этого избежать, положим, что первый ненулевой компонент столбца
равен 1, тогда если у двух векторов совпадают единичные компоненты, то
так как    , получим h i   h j .
Всего
q m  1
существует
ненулевых
различных

столбцов

проверочной матрицы. Из них, начинающихся с 1 = q m 1 , из них,


начинающихся с 1 = q m 2 и т.д.
Т.о. число столбцов проверочной матрицы, у которых первый
ненулевой элемент начинается с 1 равно сумме геометрической прогрессии
nq
m 1
q
m 2
qm 1
 ...  1 
.
q 1
(96)
Т.о. код Хэмминга в произвольном поле GF q  имеет размерность
 qm 1 qm 1


,
 m .
 q 1 q 1



Параметры некоторых кодов Хэмминга
GF 2 
7,4
15,11
31,26
GF 4 
5,3
21,18
85,81
(97)
GF 8 
9,7 
73,70
585,581
Пример 2.
Код Хэмминга 13,10  в поле GF 3 . Проверочная матрица имеет вид
1 1 1 1 1 1 1 1 1 0 0 0 0


H  0 0 0 1 1 1 2 2 2 1 1 1 0 .
0 1 2 0 1 2 0 1 2 0 1 2 1


В систематическом виде
1 1 1 1 1 1 1 1 1 1 1 0 0


H  0 0 1 1 1 1 2 2 2 1 0 1 0 .
1 2 0 1 2 2 0 1 2 1 0 0 1


Порождающая матрица
(98)
(99)
55
1

0
0

0
0
G 
0

0
0

0
0

0 0 0 0 0 0 0 0 0 2 0 2

1 0 0 0 0 0 0 0 0 2 0 1
0 1 0 0 0 0 0 0 0 2 2 0

0 0 1 0 0 0 0 0 0 2 2 2
0 0 0 1 0 0 0 0 0 2 2 1
.
0 0 0 0 1 0 0 0 0 2 2 1

0 0 0 0 0 1 0 0 0 2 1 0
0 0 0 0 0 0 1 0 0 2 1 2

0 0 0 0 0 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 1 0 2 2 
(100)
56
ЛЕКЦИЯ №17
2.5. ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
Рассмотрим внутреннею структуру линейного блокового кода,
представив его в виде таблицы стандартного расположения кодовых
комбинаций.
Таблица представляет собой разложение группы по сложению
линейного пространства GF q n на смежные классы по подгруппе по
сложению  . Элементы  - разрешенные кодовые комбинации записаны
в первой строке таблицы. Следующие строки – смежные классы. В первом
столбце – лидеры смежных классов.
В абстрактной алгебре различают понятие левого и правого
смежного класса, в зависимости от порядка элементов в суммах, если
операция сложения некоммутативна. В нашем случае группа кодовых
комбинаций абелева, т.е. операция сложения коммутативна.
Разложение на
смежные
классы
абелевой
группы по
сложению
линейного
пространства
GF q n
Разрешенные
кодовые
комбинации
Сферы
декодирования
радиуса  H  1
Сферы
декодирования
радиуса  H  t
Межсферные
кодовые
комбинации
Таблица 1 - Таблица стандартного расположения
Лидеры смежных
Смежные классы
классов
c1  0
c2
…
c k
q
c1  v 2  v 2
c2  v 2
…
c k  v2
q
…
c1  v j1  v j1
…
c 2  v j1
…
…
…
c k  v j1
…
c1  v jt  v jt
…
c 2  v jt
…
…
…
c k  v jt
…
c1  v m  v m
q
q
…
c2  v m
q
…
…
…
c k v m
q
q
q
q
57
Таблица стандартного расположения формируется следующим
образом. К нулевой кодовой комбинации c1 добавляем
кодовую
комбинацию v 2 так, чтобы расстояние по Хэммингу  H c1 , v 2   1 .
Повторяем аналогичную операцию для всех элементов строки. Затем к
нулевой кодовой комбинации c1 добавляем следующую кодовую
комбинацию v 3 так, чтобы расстояние по Хэммингу  H c1 , v 3   1 и
повторяем аналогичную операцию для всех элементов 3-й строки. Т.о.
заполняем сферы радиуса 1 вокруг разрешенных кодовых комбинаций.
Далее по этому правилу заполняем сферы радиуса t . Эти сферы,
состоящие из запрещенных кодовых комбинаций и одной разрешенной в
центре, называются сферами декодирования соответствующего радиуса.
Оставшихся элементов недостаточно для формирования сфер
радиуса t  1 и среди них имеются элементы находящиеся на одинаковом
расстоянии до нескольких разрешенных кодовых комбинаций. Эти
элементы образуют т.н. межсферное пространство.
В соответствии с известной из алгебры теоремы о разложении
группы на смежные классы, каждый элемент группы встречается в таблице
смежных классов только один раз.
Таблицу стандартного расположения можно использовать в
алгоритмах декодирования линейного блокового кода. Различают два
алгоритма декодирования:
 Полный декодер, алгоритм декодирования при котором принятую
кодовую комбинацию находят в таблице стандартного расположения
и декодируют в первый элемент соответствующего столбца.
 Неполный декодер, алгоритм декодирования при котором
принятую кодовую комбинацию находят в таблице стандартного
расположения и декодируют в первый элемент соответствующего
столбца, если она принадлежит сфере декодирования, или
формируют сигнал «ошибка», если она принадлежит межсферному
пространству.
Пример 3.
Приведем пример построения таблицы стандартного расположения кода
Хэмминга в поле GF 2  имеющего размер 7,4  . Используем
порождающую матрицу (19), получим таблицу в следующем виде.
1
2
3
4
5
6
1
0000000
0000001
0000010
0000100
0001000
0010000
2
0001111
0001110
0001101
0001011
0000111
0011111
3
0010101
0010100
0010111
0010001
0011101
0000101
4
0011010
0011011
0011000
0011110
0010010
0001010
5
0100011
0100010
0100001
0100111
0101011
0110011
6
0101100
0101101
0101110
0101000
0100100
0111100
7
0110110
0110111
0110100
0110010
0111110
0100110
8
0111001
0111000
0111011
0111101
0110001
0101001
58
7 0100000 0101111 0110101 0111010 0000011 0001100 0010110 0011001
8 1000000 1001111 1010101 1011010 1100011 1101100 1110110 1111001
1
2
3
4
5
6
7
8
9
1000110
1000111
1000100
1000010
1001110
1010110
1100110
0000110
10
1001001
1001000
1001011
1001101
1000001
1011001
1101001
0001001
11
1010011
1010010
1010001
1010111
1011011
1000011
1110011
0010011
12
1011110
1011111
1011100
1011010
1010110
1001110
1111110
0011110
13
1100101
1100100
1100111
1100001
1101101
1110101
1000101
0100101
14
1101010
1101011
1101000
1101110
1100010
1111010
1001010
0101010
15
1110000
1110001
1110010
1110100
1111000
1100000
1010000
0110000
16
1111111
1111110
1111101
1111011
1110111
1101111
1011111
0111111
Анализируя таблицу стандартного расположения кода Хэмминга
можно заметить, что у кода 16 сфер декодирования радиуса 1 и нет
межсферных элементов. Код гарантировано исправляет ошибку одиночной
кратности и не имеет ни одной «лишней» запрещенной кодовой
комбинации. В этом смысле код Хэмминга называют совершенным кодом.
Совершенный код это код, у которого сферы одинакового радиуса
вокруг разрешенных кодовых комбинаций, не пересекаясь, покрывают все
пространство.
На практике для декодирования линейных блоковых кодов
применяют алгоритм синдромного декодирования.
Для любого принятого вектора v определим синдром ошибки в виде
вектора s
s  vHT .
(101)
Теорема 9 «О синдроме ошибки линейного блокового кода».
Все кодовые комбинации одного смежного класса имеют
одинаковый синдром, присущий только этому смежному классу.
Доказательство.
Пусть v и v имеют разный синдром и принадлежат одному
смежному классу, тогда s  vHT и s  vHT . Вычислим разность
s  s  vHT  vHT  ci  w HT  c j  w HT  wHT  wH T  0 ,
что


противоречит исходному.
В алгоритме синдромного декодирования используют таблицу
синдромов. В таблице синдромов два столбца в первом – лидеры смежных
классов, во втором соответствующие этим классам синдромы.
59
Таблица 2 - Таблица синдромов
Лидеры
Синдромы
c1  0
s1  0
v2
s2
…
…
v j1
s j1
…
v jt
…
s jt
…
v m
…
s m
q
q
Алгоритм синдромного декодирования сводится к следующей
последовательности действий:
1. По принятой кодовой комбинации вычисляется соответствующий ей
синдром s  vHT ;
2. По таблице синдромов находится соответствующий лидер смежного
класса w .
3. Переданная кодовая комбинация вычисляется в виде c  v  w .
Пример 4.
Приведем пример синдромного декодирования кода Хэмминга в поле
GF 2  имеющего размер 7,4  . Используем порождающую матрицу (19) и
проверочную (18), получим таблицу синдромов в следующем виде.
Лидеры Синдромы
0000000
000
0000001
001
0000010
010
0000100
100
0001000
111
0010000
101
0100000
011
1000000
110
Пусть передается кодовая комбинация 0001111 в канале происходит
ошибка, и принятая кодовая комбинация имеет вид 0101111, синдром
ошибки = 011, лидер = 0100000, исправленная кодовая комбинация
(0001111)=( 0101111)-( 0100000).
60
2.6. ПРОСТЫЕ ПРЕОБРАЗОВАНИЯ ЛИНЕЙНОГО КОДА
Некоторые простые преобразования исходного линейного кода позволяют
получать новые линейные коды. Таких преобразований шесть:
1. Расширение кода – добавление
проверочных разрядов
n, k   n  1, k ;
2. Удлинение кода – добавление информационных разрядов
n, k   n  1, k  1 ;
3. Выкалывание кодовых координат – удаление проверочных
символов n, k   n  1, k  ;
4. Укорочение кода – удаление информационных символов
n, k   n  1, k  1 ;
5. Пополнение кода – увеличение числа информационных разрядов
без увеличения длины кода n, k   n, k  1 ;
6. Код с выбрасыванием – уменьшение числа информационных
символов без изменения длины кода n, k   n, k  1 .
Любой двоичный n, k  код с нечетным значением минимального кодового
расстояния можно расширить до n  1, k  кода добавлением к
разрешенным кодовым комбинациям проверки на четность. Минимальное
кодовое расстояние полученного кода увеличивается на единицу. Если H проверочная матрица исходного кода, то проверочная матрица
расширенного кода H  имеет вид
 1 1 ... 1 


0


H  
.
(102)

H 


0




Например, расширение двоичного кода Хемминга 2 m  1,2 m  m  1 до


кода 2 m ,2 m  m  1 называют расширенным кодом Хэмминга.
Расширенный код Хэмминга с d min  4 исправляет ошибки одиночной
кратности и обнаруживает 3 ошибки.


Код максимальной длины 2 m  1, m или код M-последовательности
является кодом, дуальным коду Хэмминга. Расширение двоичного кода
максимальной длины до кода
2m , m
дает ортогональный код.
Минимальное кодовое расстояние ортогонального кода d min  2 m 1 .
61
2.7. КОДЫ РИДА-МАЛЛЕРА
Коды Рида-Маллера порядка r  m это линейные двоичные коды с
r
m
длиной n  2 , k 
 Cmi , d min  2m  r , Cmi - число сочетаний из i по m .
i 0
Порождающая матрица кода
матрицы
Рида-Маллера имеет вид блочной
G0 


G


G  1 ,



G
 r
(103)
где G 0 - вектор размерности n  2 m , состоящий из одних единиц, G1 m  n матрица, содержащая в качестве столбцов все двоичные mпоследовательности. Нулевой столбец слева, единичный крайний справа,
остальные по возрастанию, младший бит в нижней строке. Строки
матрицы G i получаются из строк G1 как все возможные поразрядные
i
произведения i строк из m. Существует Cm
вариантов выбора i строк из
m.
Дэвид Юджин Маллер (2 ноября 1924
года - 27 апреля 2008 года) американский
математик.
Был
профессором
математики
и
информатики
в
Университете
Иллинойса
(1953-92).
Маллер получил степень бакалавра в 1947
году, а докторскую степень - в 1951 году
по
физике
в
Калифорнийском
технологическом институте. Он изобрел
коды Рида-Маллера, а Ирвинг Рид
предложил алгоритм декодирования. Его
отец Герман Джозеф Мюллер получил Нобелевскую премию по физиологии
и медицине в 1946 году, работал в СССР в 30-е годы, сочувствовал
коммунистам. Его мать Джесси Мари Джейкобс была одной из первых
женщин, которые получили докторскую степень по математике в
Соединенных Штатах.
Пример 5.
Приведем примеры кодов Рида-Маллера для m  4 , n  2 4  16 .
62
1. Пусть r  0 , тогда получим код с повторением 16,1
G  g 0   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .
(104)
Для кода с повторением применяется мажоритарный алгоритм
декодирования. Например, пусть передается символ «1», тогда
разрешенная
кодовая
комбинация
имеет
вид
c  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 , если v - принятая
кодовая комбинация, то восстановленный переданный символ равен
n
 vi , mod 2 .
Если число ошибок меньше 7, то символ «1» будет
i 0
восстановлен.
2. Пусть r  1 , получим код Рида-Маллера 16,5
 g0   1
  
 g1   0
G  g2   0
  
 g3   0
g  0
 4 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 . (105)

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
3. Пусть r  2 , получим код Рида-Маллера 16,11 , который является
расширенным кодом Хэмминга
 g0   1 1 1 1 1

 
 g1   0 0 0 0 0
g
 0 0 0 0 1
2

 
 g3   0 0 1 1 0
g
 
 4  0 1 0 1 0
G   g1g 2    0 0 0 0 0

 
 g1g 3   0 0 0 0 0
 g1g 4   0 0 0 0 0

 
 g 2g3   0 0 0 0 0
 g 2g 4   0 0 0 0 0

 
g
g
 3 4  0 0 0 1 0
4. Пусть r  3 , получим код
кодом проверки на четность
1 1 1 1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 1 1 1
1 1 1 0 0 0 0 1 1 1 1

0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 1 1 1 1 . (106)

0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 1 0 1

0 1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1

0 0 1 0 0 0 1 0 0 0 1
Рида-Маллера 16,15 , который является
63
1
 g0
 

 0
g
 1
 0
g
 
 2
 0
g
 3
 
g
 0
4

 0
 g1g 2  

 0
g
g
 1 3  0
G   g1g 4   

 0
g
g
 2 3  0
 g 2g 4  
g g
 0
3
4

 
 g1g 2 g 3   0

 0
 g1g 2 g 4  
 g1g 3g 4   0

  0
 g 2 g 3g 4  

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 1 0 1 0 1 0 1

0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 1 0 1 0 0 0 0 0 1 0 1

0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
.
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1


(107)
Т.о. код Рида-Маллера r -го порядка получается пополнением кода
Рида-Маллера r  1 -го порядка, а код Рида-Маллера r  1 -го порядка
получен с помощью выбрасывания из кода Рида-Маллера r -го порядка.
Для декодирования кода Рида-Маллера эффективен алгоритм Рида,
который позволяет декодировать принятую кодовую комбинацию,
восстанавливая разряды мажоритарным алгоритмом непосредственно из
принятых битов, без промежуточных синдромов.
Рассмотрим алгоритм Рида на примере декодирования кода РидаМаллера 16,11 .
В соответствии с (106) алгоритм кодирования можно представить в
виде
64
c 0  i0 ,
c1  i 0  i 4 ,
c 2  i0  i3 ,
c3  i0  i3  i 4  i10 ,
c 4  i0  i 2 ,
c 5  i 0  i 2  i 4  i9 ,
c6  i0  i 2  i3  i8 ,
c7  i0  i 2  i3  i 4  i8  i9  i10 ,
c8  i0  i1 ,
c9  i 0  i1  i 4  i7 ,
c10  i 0  i1  i3  i6 ,
c11  i 0  i1  i3  i 4  i 6  i 7  i10 ,
c12  i 0  i1  i 2  i5 ,
c13  i0  i1  i 2  i 4  i5  i 7  i9 ,
c14  i 0  i1  i 2  i3  i5  i6  i8 ,
(108)
c15  i 0  i1  i 2  i3  i 4  i5  i 6  i 7  i8  i9  i10 ,
где i  i0 i1 ... i10  - информационный вектор.
Рассмотрим декодирование символа i k 1  i10 . Заметим, что i10


входит однократно в каждый блок из 4-х символов 2 mr , в тоже время
как другие символы входят четное число раз (2 или 4). Тогда четыре
проверки четности дают точное значение символа i10 , суммирование в
(108) осуществляется по модулю 2.
r1  c 0  c1  c 2  c3  i10 ,
r2  c 4  c5  c6  c 7  i10 ,
r3  c8  c9  c10  c11  i10 ,
(109)
r4  c12  c13  c14  c15  i10 .
Если число ошибок равно 1, то одна из проверок четности будет
отличаться от других, декодируя мажоритарным способом, исправляем
ошибку. Если число ошибок равно 2, то две из проверок четности будут
отличаться от 2-х других. Исправить две ошибки нельзя, но обнаружить
можно. Тоже можно сказать о случае 3-х ошибок.
Для восстановления символа i k 2  i9 нужно переставить столбцы
матрицы (106) так, чтобы последняя строка стала предпоследней, и
применить тот же алгоритм декодирования. Так выполняется
65
декодирование
i  i 0 i1 ...
Далее из
символы
6-ти информационных символов в блоке i r  i 2 вектора
ir  .
принятой кодовой комбинации v вычитаются найденные
v  v  i r G r .
(110)
Получаем кодовое слово кода Рида-Маллера 16,5  . Повторяем
алгоритм восстановления блока символов i r 1  i1 , и т.д.
66
ЛЕКЦИЯ №18
2.8. АРИФМЕТИКА ПОЛЕЙ ГАЛУА
всех многочленов одной переменной x с
коэффициентами из поля F является кольцом с единицей и
обозначается F x .
Многочлен одной переменной называется приведённым, если его
старший коэффициент равен единице.
Наименьшим общим кратным (НОК) двух многочленов
называется приведенный многочлен, делящийся на оба из них.
Для произвольного приведенного многочлена p  x  ненулевой
степени над полем F кольцом многочленов по модулю p  x 
называется множество всех многочленов над полем F , степень
которых не превосходит степени многочлена p  x  , с операциями
сложения и умножения многочленов по модулю p  x  . Это кольцо
обозначают F x  / p x  .
Кольцо многочленов F x  / p x  является полем тогда и только
тогда, когда многочлен p  x  - прост, т.е. не имеет делителей кроме 1
и самого себя.
Теорема об однозначном разложении. Любой ненулевой
многочлен g  x   F x  с точностью до порядка сомножителей
разлагается в произведение элемента поля F и простых многочленов
над этим полем.
Для любого простого числа q и целого m существует поле Галуа
1. Множество
2.
3.
4.
5.
6.
7.
 
GF q m .
Простые многочлены над полем GF 2 
Степень многочлена Простые многочлены
2
x2  x 1
3
x3  x  1
4
x4  x 1
5
x5  x 2  1
6
x6  x  1
7
x7  x3  1
8
x8  x 4  x 3  x 2  1
9
x9  x4  1
67
8. Для любого целого m над каждым полем Галуа GF q  существует
хотя бы один простой многочлен степени m .
 
9. Поле Галуа GF q m состоит из многочленов кольца GF q x  / p  x  ,
где p  x  - простой многочлен степени m .
10. Поле Галуа GF 4  образуют многочлены степени < 2 с
коэффициентами из поля GF 2  с операциями сложения и
умножения по модулю простого многочлена p x   x 2  x  1 .

0
0
1
x
0
1
x
x 1 x 1
x 1
*
0 1
1
x
x 1
0
x 1
x ,
x 1
0
1
0
1
x
0 0
0
0 1
x
0 x x 1
1
x
x
1
0
Многочлены Двоичные
обозначения
0
00
1
01
x 1 0 x
x
1
Целочисленные
обозначения
0
1
x 1
0
x
1
x
Степенные
обозначения
0
x0
x
10
2
x1
x 1
11
3
x2
11. Примитивным элементом поля Галуа GF q  называется такой
элемент  , что все элементы поля кроме нуля могут быть
представлены как степени элемента  . Например, в поле GF 4 
  x , в поле GF 5   2 .
12. В каждом поле Галуа имеется хотя бы один примитивный элемент.
13. Теорема о примитивном разложении. Пусть 1 ,  2 ,...,  q 1 ненулевые элементы поля GF q  , тогда, вследствие того, что
порядок элемента в группе по умножению поля GF q  делит q  1 ,
справедливо равенство


x q 1  1   x  1  x   2 ... x   q 1 .
(111)
14. В поле Галуа GF 8  порядок каждого ненулевого элемента делит 7.
Так как 7 – простое число, то все ненулевые элементы поля GF 8 
примитивные. Пусть   x , p x   x 3  x  1 , элементы поля имеют
вид
68
  x,
 2  x2 ,
 3  x  1,
 4  x 2  x,
(112)
 5  x 2  x  1,
 6  x 2  1,
 7  1.
15. Подмножество K  F поля F , замкнутое относительно операций
сложения и умножения называется подполем поля F .
16. Число элементов наименьшего подполя поля GF q  называется
характеристикой поля GF q  .
17. Каждое поле Галуа содержит единственное наименьшее подполе,
число элементов которого равно простому числу. Характеристика
любого поля Галуа является простым числом.
18. Для любого q , являющегося степенью простого числа и любого
 
положительного целого m поле GF q  является подполем в GF q m ,
 
а GF q m является расширением поля GF q  .
19. Для любого q , являющегося простым числом
и
любого
  имеют вид
положительного целого m , все подполя поля GF q m
 


 
GF q   GF q 2  ...  GF q m 1  GF q m .
20. Два поля, различающиеся только представлениями называются
изоморфными.
 
 
21. Пусть GF q m - расширение поля GF q  . Пусть   GF q m элемент из расширения. Простой многочлен
f  x  наименьшей
степени с коэффициентами из поля GF q  для которого f    0 ,
называется
минимальным
многочленом
элемента
.
Минимальный многочлен всегда существует и единственен.
22. Пусть g  x  - произвольный многочлен над полем GF q  , т.е.
g  x   GF q x  . Тогда существует расширение поля GF q  в
котором g  x  распадается на произведение линейных множителей.
Это поле называется полем разложения многочлена g  x  .
 
23. Пусть  - примитивный элемент поля GF q m , являющегося
расширением поля GF q  , и пусть m - степень минимального
69
 
многочлена f  x  элемента  . Тогда каждый элемент поля GF q m
может быть представлен в виде
  a m1 m1  a m2 m2  ...  a1  a 0 , где a m 1 ,..., a 0  GF q  .
(113)
24. Пусть GF q m - расширение поля GF q  . Тогда в соответствии с
теоремой о примитивном разложении
 q m 1 
 x
 1   x  1  x   2 ... x   m  ,
(114)
q

1




где 1 ,  2 ,...,  q 1 - ненулевые элементы поля GF q m . В
 
 
соответствии с теоремой об однозначном разложении
 q m 1 
 x
 1  f1  x  f 2  x ... f r  x  ,
(115)


где f1  x  f 2  x ... f r  x  простые многочлены с коэффициентами из
 
поля GF q  . Тогда каждый из 1 ,  2 ,...,  q 1 элементов поля GF q m
является корнем одного из многочленов f1  x  f 2  x ... f r  x  , являющихся
соответственно минимальными многочленами этих элементов.
 
25. Пусть f  x  - минимальный многочлен элемента   GF q m , тогда
 
f  x  - минимальный многочлен также и для элемента  q  GF q m .
26. Все корни
минимального многочлена f  x  , являющиеся
 
элементами
поля
GF q m ,
относительно поля GF q  .
называются
сопряженными
 
27. Пусть f  x  - минимальный многочлен элемента   GF q m , тогда
множество сопряженных корней f  x 

q
q2
q3
q r 1 

,

,

,

,...,


,


(116)
r
где r - наименьшее целое число, такое, что  q   , r  m и
минимальный многочлен можно представить в виде
2 
r 1 

f  x    x    x   q  x   q ... x   q  .
(117)

 

28. Построим поле Галуа GF 16  , q  2 , m  4 , неприводимый в поле


Галуа GF 2  многочлен степени m : x 4  x  1 .
70
Элементы Представление
поля
в виде
многочлена
GF 16 
0
0
1
2
3
4
5
6
7
8
9
 10
 11
 12
 13
 14
Представление Представление Минимальный
в двоичном
в десятичном
многочлен
виде
виде
0
1
0000
0001
0
1
x 1
x
0010
2
x4  x 1
x2
0100
4
x4  x 1
x3
x 1
1000
8
x 4  x3  x2  x  1
0011
3
x4  x 1
x2  x
0110
6
x2  x 1
x3  x 2
1100
12
x 4  x3  x2  x  1
x3  x  1
1011
11
x 4  x3  1
x2 1
0101
5
x4  x 1
x3  x
1010
10
x 4  x3  x2  x  1
x2  x 1
0111
7
x2  x 1
x3  x2  x
1110
14
x 4  x3  1
x3  x 2  x  1
1111
15
x 4  x3  x2  x  1
x3  x 2  1
1101
13
x 4  x3  1
x3  1
1001
9
x 4  x3  1
Найдем
минимальный
многочлен
f x  ,
соответствующий
примитивному элементу. Множество сопряженных корней имеет вид

2 22
23 
 ,  ,  ,   . Минимальный многочлен получим в виде




 
 x 4  x 3  4   8     2  x 2  12   5   3   6   10   9  
 x 13   11   14   7   15  x 4  x 3 0   x 2 0   x1  1  x 4  x  1.
f x   x    x   2 x   4 . x   8 
(118)
2.9. ЦИКЛИЧЕСКИЕ КОДЫ
Циклические коды являются важным подклассом линейных кодов,
которые имеют эффективные алгоритмы кодирования и декодирования,
основаны на применении идей алгебраической теории полей Галуа,
включают в себя практически значимые коды Хэмминга, БЧХ-коды, коды
Рида-Соломона.
71
В 1957 году американец Евгений Прейндж, первый ввел понятие
циклического кода и указал на его связь с идеалами алгебр. Значительный
вклад в разработку теории этих кодов внесли американские ученые
Питерсон, Берлекамп и Касами.
Уильям Уэсли Петерсон (22 апреля 1924 6 мая 2009) американский математик,
известен благодаря открытию кода
циклической
проверки
избыточности
(CRC), который широко используется в
качестве хеш-функции. Он автор и
соавтор ряда книг по теории кодов для
исправления ошибок.
Линейный
блоковый
код

является
подпространством
пространства GF (q ) n . Рассмотрим подкласс линейных блоковых кодов
удовлетворяющих специальному циклическому свойству.
Циклическое свойство: Пусть мы имеем кодовую комбинацию
c  c1 , c 2 ,..., c n     GF q n . Мы будем говорить, что эта комбинация
обладает циклическими свойством, когда при циклическом сдвиге ее
разрядов полученная кодовая комбинация опять принадлежит к
разрешенным кодовым комбинациям. Т.е. кодовые комбинации
c1  c n , c1 ,..., c n 1 ,..., c n1  c 2 , c3 ,..., c1     GF q n .
Циклический код – линейный блоковый код, комбинации которого
удовлетворяет циклическому свойству.
Для описания и анализа циклических кодов используется
полиноминальное представление кодовых комбинаций. Каждый вектор
пространства GF (q ) n можно представить полиномом, степень которого не
превышает n  1 с коэффициентами из поля GF q  . Например,
c x   c n x n 1  c n 1 x n 2  ...  c 2 x  c1 .
(119)
72
Тогда кодовые комбинации c1  c n , c1 ,..., c n 1 ,..., c n 1  c 2 , c3 ,..., c1 
можно получить следующим образом

Важным

ci  x   x i c x , mod x n  1 .
является то обстоятельство
что
(120)
подпространство
циклического кода линейного пространства   GF q n изоморфно
подмножеству кольца полиномов над полем GF q  от формальной
переменной x с операцией сложения и умножения многочленов по




модулю специального многочлена x n  1 . Т.е.   GF (q )[ x ] / x n  1 .


Подмножество   GF (q )[ x ] / x n  1
является циклическим
кодом тогда и только тогда, когда оно обладает двумя свойствами:


1.  – образует подгруппу кольца GF (q )[ x] / x n  1 по
сложению.




2. Если c x     GF (q )[ x] / x n  1 и a  x   GF q x  / x n  1 , то


a  x c x  mod x n  1   .
Некоторое подмножество I многочленов кольца F x  называется
идеалом этого кольца, если оно состоит из многочленов следующего вида
s
 f i ( x)ai ( x),
f i  x   F [ x] ,
(121)
i 1
где многочлены a i  x  – называются полиноминальным базисом
идеала I .
Идеал называют главным идеалом, если он порожден одним
базисным полиномом.
73
ЛЕКЦИЯ №19
Циклический

n
является
код

главным
идеалом
кольца
GF (q )[ x] / x  1 . Любой элемент кольца порождает главный идеал,
обратно каждый главный идеал порождается элементами порождающего
полинома g  x  .
Т.о. циклический n, k  код состоит из всех произведений
порождающего полинома g  x  степени m  n  k на все информационные
многочлены i  x  степени  k  1 .


c x   i  x g  x , mod x n  1
(122)
Теорема 10. «О порождающем многочлене». Циклический n, k  код
с порождающим многочленом g  x  существует тогда и только тогда, когда


g  x  делит x n  1 .
Доказательство. Пусть g  x  - порождающий многочлен степени
m  n  k . В любом случае можно записать
x n  1 Qxg x  sx ,
где degs  x   m . Вычислим остаток от деления правой и левой


части на многочлен x n  1 , получим






0  Q x g  x , mod x n  1  s x , mod x n  1  Q x g  x , mod x n  1  s  x 
Отсюда


s  x   Q x g  x , mod x n  1 ,
является разрешенной кодовой
комбинацией, степень которой  m , что
противоречит исходному положению.


Т.о. s  x   0 , и g  x  делит x n  1 .
Элвин
Ральф
Берлекамп
(родился 6 сентября 1940 года) американский математик. Он является
почетным профессором математики в
Калифорнийском
университете
в
Беркли. Berlekamp известен своей
работой в теории кодирования и
комбинаторной теории игр. В 1962
74
году он получил степень бакалавра и магистра электротехники.
Продолжая учебу в Массачусетском технологическом институте,
закончил аспирантуру по электротехнике в 1964 году. Его советниками
были Роберт Г. Галлагер, Питер Элиас, Клод Шеннон и Джон
Возенкрафт. Берлекамп преподавал электротехнику в Калифорнийском
университете в Беркли с 1964 по 1966 год, когда он стал математиком в
Bell Labs. Berlekamp является изобретателем алгоритма факторизации
многочленов и является одним из изобретателей алгоритма ВельшаБерлекампа и алгоритмов Berlekamp-Massey, которые используются для
реализации алгоритма коррекции ошибок Рида-Соломона. Помимо
математики и информатики, Berlekamp также активно занимался
управлением капиталом. В 1986 году он начал теоретикоинформационные исследования товарных и финансовых фьючерсов.
Пример 6.
Приведем примеры
простых
двоичных


циклических
кодов,
порождающий многочлен которых, делит x 7  1 .
В соответствии с теоремой об однозначном разложении в поле
GF 2  получим
x 7  1  x  1x 3  x 2  1x 3  x  1.
(123)
Данное представление позволяет найти порождающие многочлены
для следующих циклических кодов:
1) g  x    x  1 - код с проверкой на четность 7,6  ;


2) g  x   x 3  x 2  1 - код Хэмминга 7,4  ;


3) g  x    x  1 x 3  x  1 - код последовательности максимальной
длины 7,3 ;



4) g  x   x 3  x 2  1 x 3  x  1 код с повторением 7,1 .
Тадао Касами (12 апреля 1930г. - 18
марта 2007г.) был известным японским
ученым
теоретиком
в
области
информации, внесшим значительный
вклад в теорию помехоустойчивого
кодирования. Касами родился в Кобе
(Япония), изучал электротехнику в
75
Университете Осаки, где он получил степень бакалавра в 1958г., M.E. в
1960 г. и Ph.D. в 1963, преподавал до 1994. Впоследствии он был
профессором в Высшей школе информатики в Институте науки и
технологии Нара в 1992-1998 годах и профессором информатики в
Городском университете Хиросимы в 1998-2004 годах.
Следствие теоремы №10. «О проверочном многочлене». В
соответствии с теоремой №6, если g  x  - порождающий многочлен
циклического n, k  кода, то найдется многочлен h x  , degh x   k , такой,




что h x g  x   x n  1 и для любого c x     GF (q )[ x] / x n  1 ,


c x h x , mod x n  1  0 .
(124)
 
тогда
c x h x , mod x n  1  i  x g  x h x , mod x n  1  i  x x n  1, mod x n  1  0 .
Доказательство. Пусть c x    , тогда c x h x , mod x n  1   ,
Представление циклического кода в систематическом виде.
Пусть имеем порождающий многочлен n, k  кода g  x  . Код состоит
из всех произведений порождающего полинома g  x  степени m  n  k на
все информационные многочлены i  x  степени  k  1
c x   i  x g  x  .
(125)
Кодовое слово систематического кода можно записать в виде
c x   x n  k i  x   t  x  ,
где t  x  - многочлен степени  m  1 , тогда
c x , mod g  x   0,
x nk ix   t x, mod g x  0, .
x nk ix , mod g x  t x  0,
t  x   x nk i  x , mod g  x .
(126)
(127)
Порождающая матрица циклического кода может быть получена
циклическим сдвигом порождающего многочлена по следующей формуле


ci  x   x i g  x , mod x n  1 , i  0,..., k  1 ,
в виде
 0

 0
G 
0

g
 0
... 0
... g 0
...
g0
g1
...
0
0
... g m1 

...
0 
.
...
0 

0 
76
Далее применяя формулу (51) матрицу G можно привести к
систематическому виду.
Циклический код называется примитивным, если его длина
nq
m
 1.
Примитивный циклический код является главным идеалом кольца
 m

GF (q )[ x] /  x q 1  1  . Тогда в соответствии с теоремой о примитивном


разложении
 q m 1 
 x
 1   x  1  x   2 ... x   m  ,
(128)
q 1 



тогда в соответствии с теоремой о порождающем многочлене, если
 
1 ,  2 ,...,  r элементы поля GF q m , являющиеся корнями порождающего
многочлена, являются корнями многочлена любой разрешенной кодовой
комбинации c x  .
Теорема 11. «Определение циклического кода в расширении поля
Галуа». Примитивный циклический n, k  код задан порождающим
 
многочленом g  x  . Пусть 1 ,  2 ,...,  r , элементы поля GF q m , являются
корнями многочлена g  x  . Многочлен c x  над полем GF q  является
разрешенным тогда и только тогда, когда
c1   c 2   ...  c r   0 ,
(129)
 
где c i  вычисляется в поле GF q m .
Доказательство.
Если c x    , то c x   i  x g  x  , отсюда c i   i  i g  i   0 .
Обратно, если c i   0 . Пусть f i  x  - минимальный многочлен
 
элемента  i  GF q m , тогда можно записать
c x   Q x  f i  x   s  x  ,
где degs  x   deg  f i  x  . Запишем
c i   Q i  f i  i   s  i   0 .
Из определения минимального многочлена следует, что тогда из
последнего соотношения s  x   0 . Тогда c x   Q  x  f i  x  . Поскольку
последнее соотношение верно для всех 1 ,  2 ,...,  r , то
g  x   НОК  f1  x , f 2  x ,..., f r  x  .
(130)
77
2.9.1. Синдромное декодирование циклических кодов


Пусть c x    , и v x   GF (q )[ x] / x n  1 - многочлен принятой
кодовой комбинации, тогда многочлен e x   v x   c x  называют
многочленом ошибок.
Многочлен s  x  называется синдромным многочленом если он


определен как остаток от деления v x  на g  x  по модулю x n  1 .
Теорема 12.
«О синдромном многочлене». Пусть d min минимальное кодовое расстояние циклического кода  . Каждому
многочлену ошибок веса Хемминга меньше чем d min 2 соответствует
единственный синдромный многочлен.
Доказательство.
Пусть синдромному многочлену s  x  соответствуют два многочлена
ошибок e1  x  и e2  x  с весом меньше чем d min 2 . Тогда
e1  x   Q1  x g  x   s x ,
e2  x   Q2  x g  x   s x ,
e1  x   e2  x   Q1  x   Q2  x g  x .
Т.к. веса многочленов ошибок меньше чем d min 2 , то вес разности
меньше чем d min . Однако в правой части последнего равенства
разрешенная кодовая комбинация, вес которой, больше или равен d min .
Это может быть только если e1  x   e2  x   0 .
Алгоритм синдромного декодирования циклического кода:
1)
По принятому кодовому слову v x  вычисляют синдром
sx .
2)
По синдромному многочлену s  x  в таблице синдромов
находят e x  .
3)
Принятую
кодовую
комбинацию
исправляют
c x   v  x   e x  .
78
ЛЕКЦИЯ №20
2.9.2. Циклические коды Хэмминга
Т.о. мы показали, что циклические коды требуют меньшей памяти,
легче порождаются и проще декодируются, чем линейные нециклические
коды.
Ранее мы показали, что в произвольном поле GF q  существуют
 qm 1 qm 1

коды Хэмминга размерности 
,
 m .
 q 1 q 1



В данном разделе мы найдем условия, при выполнении которых,
существуют циклические коды Хэмминга.
Рассмотрим примитивные двоичные коды Хемминга. Для того
чтобы получить код Хэмминга с примитивной длиной 2 m  1 , выберем
порождающий полином g  x  так, чтобы примитивный элемент
 
 поля GF 2 m был его корнем. Положим, чтобы g x  являлся
минимальным многочленом примитивного элемента.
Тогда в соответствии с теоремой №7 об определении циклического
кода, любая разрешенная комбинация c x    , порождает равенство
c i   0 ,
1



c0 ...cn1   ..   0
 n 1 


или
cH T  0 , где H   0 ... n1 .


Пример 7.
Рассмотрим код Хэмминга 7,4  в поле GF 2  . В поле Галуа GF 8 
порядок каждого ненулевого элемента делит 7. Так как 7 – простое число,
то все ненулевые элементы поля GF 8  примитивные. Пусть   x ,
g  x   x 3  x  1, проверочная матрица имеет вид
79


H   0 ... 6 

1 x
x2
x  1 x2  x

x2  x  1 x2  1 
1 0 0 1 0 1 1


  0 1 0 1 1 1 0 .
 0 0 1 0 1 1 1


Рассмотрим недвоичные циклические коды Хэмминга. Ранее мы
qm 1
определили длину кода Хемминга n 
.
q 1
 
Пусть  – примитивный элемент поля GF q m . Выберем некий
элемент    q 1 , тогда
q m 1
 q 1 
n 1
 q m 1



n
q

1

  1  0 ,  - является корнем многочлена x
 1 .








Поскольку порождающий многочлен является делителем x n  1 в
поле GF(q), то можно в качестве порождающего многочлена кода
Хэмминга взять минимальный многочлен элемента  , тогда проверочную
матрицу можно представить в виде


H   0 ... n1 .
80
 
GF q m
 m

GF ( q )[ x ] /  x q 1  1 


 q m 1 
 x
 1  x  1  x   2 ... x   m 
q 1 



 q m 1 
 x
 1  f1  x  f 2  x ... f r  x 


Циклический код 
- главный идеал.
Примитивному элементу 
соответствует минимальный
многочлен f i  x 
Порождающий
многочлен
циклического кода
Хэмминга g  x   f i  x 
Примитивному элементу  q 1
соответствует минимальный
многочлен f j  x 
Порождающий многочлен
циклического кода,
исправляющего 2
ошибки g  x   f i  x  f j  x 
Рисунок 13 – Схема синтеза примитивного циклического кода
Теорема 13. «О циклических кодах Хэмминга». Минимальное
кодовое расстояние кода с проверочной матрицей следующего вида
qm 1
H   ...
, где   
и n
, равно, по меньшей мере 3
q 1
тогда и только тогда, когда n и q  1 взаимно просты, что возможно тогда и
только тогда, когда m и q  1 взаимно просты.

0
n1

q 1
2.9.3. Двоичные циклические коды, исправляющие две ошибки
В разделе о циклических кодах Хэмминга мы использовали стратегию
определения порождающего многочлена, показанную на рисунке. Для
построения примитивного кода Хэмминга можно использовать связь
 m

кольца GF ( q )[ x ] /  x q 1  1  и

 
поля Галуа GF q m , взяв в качестве

порождающего многочлена минимальный многочлен, соответствующий
примитивному элементу поля GF q m . Выше мы доказали, что данная
стратегия привела к успеху. В данном разделе мы синтезируем код,
исправляющий 2 ошибки повторив использованный подход.
 
Рассмотрим случай q  2 . Используем примитивный элемент поля
 
GF 2 m
 для получения минимального многочлена f i  x  , получим код
Хэмминга в виде g  x   f i  x  , исправляющий 1 ошибку.
Для исправления 2-х ошибок нужно увеличить число проверочных
разрядов, т.е. степень многочлена g  x  . Если мы используем элемент  2 ,
то степень g  x  не возрастет, так как  2 - сопряженный корень f i  x  в
поле GF 2 m . Поэтому используем  3 и получим соответствующий этому
многочлен g  x   f i  x  f j  x  .
 
Докажем, что полученный код гарантированно исправляет
ошибки двойной кратности.
Пусть любая принятая кодовая комбинация имеет вид
v x   i  x g  x   e x  .
При двойной ошибке e x  содержит не более 2-х ненулевых
разрядов. Пусть x1   i , где i - позиция 1-й ошибки, x 2   i  , где i  позиция 2-й ошибки. Пусть s1  v  и s 2  v  3 , тогда s1   i   i и
 
 
s 2   3i   3i и получим систему уравнений в поле GF 2 m
 s1  x1  x 2
.
(131)

3
3
s

x

x
 2
1
2
Если система (131) имеет единственное решение, то код
гарантировано исправляет ошибки 2-й кратности и имеет d min  5 .
Рассмотрим решение системы (131) в виде квадратного уравнения над
полем GF 2 m и s1  0 .
 
 x  x1  x  x2   x
2
  x1  x 2 x  x1 x 2  x
2

s13  s 2 
s x
,
1
s1
(132)
где
s 2   x 2  s1 3  x 23  x 23  3s1 x 22  3 x 2 s12  s13  x 23  s1 x 22  x 2 s12  s13 ,
s13  s3  s1 x 22  x 2 s12  x1 x 22  x 2 x12  x1 x 2 s1 .
 
При вычислениях в поле GF 2 m
 
мы использовали соотношение,
если a  GF 2 m , то  a  a , 2a  0 , 3a  a .
Решения этого уравнения – координаты ошибок можно получить
перебором ненулевых элементов поля GF 2 m .
 
Марсель Дж. Э. Голей (3 мая,
1902 - 27 апреля 1989)
математик, физик и теоретик в
области
информатики
из
Швейцарии.
Голей
изучал
электротехнику в Швейцарском
федеральном технологическом
институте в Цюрихе. Он
присоединился к лабораториям
Белла в Нью-Йорке в 1924 году,
проведя там четыре года.
Получил
степень
доктора
философии
по
физике
в
Чикагском университете в 1931
году. Голей присоединился к
корпусу связи армии США, и в
итоге он занял пост главного
научного
сотрудника.
Он
разработал радарные системы и
изобрел
детектор
Голея,
83
который идентифицирует инфракрасное излучение самолетов.
2.9.4. Коды Голея
Ранее мы показали, что коды Хэмминга являются совершенными. Т.е.
структура пространства кодовых комбинаций у этих кодов идеальная,
состоит только из сфер декодирования и не содержит межсферных
элементов. Существуют и другие совершенные коды, к которым относятся
коды Голея.
Двоичные коды Голея это совершенные циклические 23,12  коды,
гарантировано исправляющие ошибки тройной кратности. Порождающие
многочлены двоичного кода Голея можно определить из соотношений
g  x   x11  x10  x 6  x 5  x 4  x 2  1,
g  x   x11  x 9  x 7  x 6  x 5  x  1,
(133)
x 23  1   x  1g  x g  x .
На практике используют расширенные коды Голея 23,11 порождающие
многочлены, которых имеют вид


g  x    x  1x11  x 9  x 7  x 6  x 5  x  1.
g  x    x  1 x11  x10  x 6  x 5  x 4  x 2  1 ,
(134)
Существует совершенный троичный 11,6  код Голея и соответственно
расширенный троичный код Голея.
84
ЛЕКЦИЯ №21
2.9.5. Коды Боуза-Чоудхури-Хоквингема (БЧХ)
Ранее мы показали, что коды Хэмминга являются совершенными
кодами, но обладают небольшой исправляющей способностью. Первым
большим достижением в исследованиях, направленных на поиск длинных
кодов, исправляющих ошибки большой кратности, стали коды БоузаЧоудхури(1960)-Хоквингема(1959).
БЧХ-коды это широкий класс циклических кодов, который
выделяется возможностью синтеза кода, с заранее известным
минимальным кодовым расстоянием. Частным случаем БЧХ-кодов
являются коды Хэмминга и коды Рида-Соломона (1960).
Техника построения БЧХ-кодов обобщает технику, использованную
нами в п. 2.9.2 при синтезе циклических кодов Хэмминга и в п. 2.9.3. при
синтезе циклических кодов, исправляющих 2 ошибки.


Пусть c x    , и v x   GF (q )[ x] / x n  1 - многочлен принятой
кодовой комбинации, тогда многочлен e x   v x   c x  - многочлен
 
ошибок. Если 1 ,  2 ,...,  r - элементы поля GF q m , являющиеся корнями
порождающего многочлена g  x  , то c i   0 и
n 1
v i   e i  
 e j i j .
(135)
j 0
 
Если система r  2t линейных уравнений в поле GF q m (59) имеет
единственное решение при числе ошибок не более или равном t , то код,
заданный элементами 1 ,  2 ,...,  2t гарантировано исправляет t ошибок.
Ответ на этот вопрос дает следующая теорема.
Теорема 14. «О кодах БЧХ». Пусть БЧХ код задан элементами
1   ,  2   2 ,...,  2t   2t , которым соответствует порождающий
многочлен g  x  , тогда, если число ошибок не превосходит t , то синдромы
ошибок s1  v1 , s2  v 2 ,..., s2t  v 2t  однозначно определяют их
координаты (локаторы ошибок) xl   jl , где jl - положение l -й ошибки
и значения yl  e jl ошибок.
85
 m

GF ( q )[ x ] /  x q 1  1 


Циклический код 
- главный идеал.
Порождающий многочлен циклического кода,
исправляющего t ошибок
g  x   НОК  f1  x , f 2  x ,..., f 2t  x 
 
GF q m
 q m 1 
 x
 1  x  1  x   2 ... x   m 
q 1 



 q m 1 
 x
 1  f1  x  f 2  x ... f r  x 


Степеням примитивного


элемента  , 2 , 3 ,..., 2t соответствуют
минимальные многочлены
 f1 x , f 2 x , f 3 x ,..., f 2t x 
Рисунок 14 – Схема синтеза примитивного БЧХ-кода
Доказательство.
Из (135) прямо следует
s1  y1 x1  y 2 x2  ...  y q xq ,
s2  y1 x12  y 2 x22  ...  yq xq2 ,
(136)
...
s2t  y1 x12t  y 2 x22t  ...  y q xq2t ,
где q - фактическое число ошибок.
Рассмотрим многочлен локаторов ошибок
  x   1  xx1 1  xx2 ... 1  xxq ,

где x 

(137)
1
1
1
, x
,…, x 
- корни многочлена локаторов ошибок.
x1
x2
xq
Пусть
  x   1  1 x   2 x 2  ...   q x q ,
(138)
1
умножим обе части равенства (138) на yl xlj  q и положим x  ,
xl
получим
2
q

1
 1  
1
j q 
yl xl 1  1   2    ...   q    
xl
 xl 
 xl  
,
(139)



 yl xlj  q  1 xlj  q 1   2 xlj  q  2  ...   q xlj  0
Просуммируем полученное равенство по l , получим
q
 yl xlj  q  1xlj  q 1   2 xlj  q  2  ...   q xlj  
l 1
q
q
q
 q


jq
j  q 1
j q 2

yl xl
 1
yl xl
 2
yl xl
 ...   q
yl xlj   0


l 1
l 1
l 1
 l 1

,
(140)
в соответствии с обозначениями в (60) получим
s j  q  1s j  q 1   2 s j  q  2  ...   q s j  0 .
(141)






Т.о. получена система уравнений для значений коэффициентов   x  ,
которую, при q  t можно представить в матричном виде,
s2 ... s q 1
sq   q    sq 1 
 s1



 
s
s
...
s
s

s

 2
3
q
q 1  q 1  
q2 
s




s4 ... sq 1 s q  2  q  2   sq  3 
(142)
 3


 
...
...  ...   ... 
 ...
s


 
 q sq 1 ... s 2q  2 s2 q 1  1    s2 q 
Если матрица синдромов невырождена, то по значениям синдромов
можно найти вектор значений коэффициентов   x  , по ним локаторы
ошибок, из уравнения (136) значения ошибок.
Покажем, что ганкелева матрица синдромов в левой части (142)
удовлетворяет следующему свойству
Утверждение 2. Матрица синдромов вида
s2 ... s p 1
sp 
 s1


s3 ...
sp
s p 1 
 s2
s4 ... s p 1 s p  2 
S   s3


...
... 
 ...
s

 p s p 1 ... s2 p  2 s2 p 1 
(143)
невырождена, если p  q (числу фактически произошедших
ошибок). Матрица вырождена, если p  q .
Доказательство утверждения 2.
В соответствии с (136) матрицу синдромов S можно представить в
виде
S  ABAT ,
(144)
где
 1

 x1
A
...
 p 1
x
 1
1 
 y1 x1


xp 

, B

...
...
..
...


 0
x2p 1 ... x pp 1 

1
x2
...
...
0
...
y 2 x2 ...
...
0
0
0



...
.. 

... y p x p 
1) Если p  q , то det B   0 , т.к. в матрице B появляются нулевые
строки и столбцы.
Т.к. det S   det A det B  det A  , то det S   0 .
2) Если p  q , то det B   0 , так как равен произведению ненулевых
диагональных элементов.
det A   0 т.к. A - матрица Вандермонда, определитель которой не
равен нулю, если x1, x2 ,..., x p различны.
88
Т.о. det S   0 .
В соответствии с вышесказанным матрица синдромов невырождена,
если p равно числу фактически произошедших ошибок. Теорема 14
доказана.
Доказательство теоремы 10 дает основу для алгоритма
декодирования БЧХ кода, известного как алгоритм ПитерсонаГоренстейна-Цирлера, показанного на рисунке 15.
Процедура Ченя предполагает нахождение корней многочлена   x 
 
простым перебором по всем элементам поля GF q m , затем к найденным
корням находят элементы, обратные по умножению - это локаторы ошибок
x1, x2 ,..., x p .
Пример 8. Двоичные примитивные БЧХ коды длины n  15 .
Рассмотрим поле Галуа GF 16  , q  2 , m  4 , неприводимый в поле
Галуа GF 2  многочлен степени 4 - x 4  x  1 .
Найдем примитивные коды БЧХ, с длиной n  15 .
1) Пусть
t  1 , тогда минимальный многочлен
соответствующий
минимальный
примитивному
многочлен
f 2 x   x 4  x  1 ,
f1  x  ,
равен x 4  x  1,
,
соответствующий элементу  2 ,
элементу
f 2  x ,
порождающий
многочлен
БЧХ
кода
g  x   НОК  f1  x , f 2  x   x 4  x  1 .
Мы получили циклический код 15,11 , d min  3 , гарантировано
исправляющий 1 ошибку, т.е. код Хэмминга.
2) Пусть t  2 , тогда множество корней порождающего многочлена
 , 2 , 3 , 4 ,
f1  x   x 4  x  1 ,
f 3 x   x 4  x3  x 2  x  1 , f 4 x   x 4  x  1 .
Порождающий
многочлен

f 2 x   x 4  x  1 ,

БЧХ

кода
g  x   НОК  f1  x , f 2  x  f 3  x , f 4  x   x 4  x  1 x 4  x 3  x 2  x  1 .
Мы получили циклический код 15,7  , d min  5 , гарантировано
исправляющий 2 ошибки.
89
Вычисление синдромов
 
Вычисление коэффициентов многочлена
локаторов ошибок
 
2
s1  v , s 2  v  ,..., s 2t  v 
2t
  sq 1 
 q 





s


q2 
 q 1 


  S 1   s
 q3 
 q 2 
 ... 
 ... 
 s 
  
2q 
 1 

pt
Формирование матрицы синдромов
 s1

 s2
S   s3

 ...
s
 p
s2
s3
...
...
s p 1
sp
s4
...
...
s p 1
s p 1 ... s2 p  2
sp 

s p 1 
s p2 

... 
s2 p 1 
Вычисление локаторов ошибок
x1, x2 ,..., x p , используя алгоритм вычисления
корней полинома, например, процедура Ченя
Вычисление значений ошибок
detS   0
Да
p  p 1
 y1 
   x1
 y 2   ...
 y 
 3   ...
 ...   x p
 y   1
 p
x2
...
...
xp
Рисунок 15 - Декодер Питерсона-Горенстейна-Цирлера
2
xp 

... ... 
... ... 

... x p 
p
...
1  s1 
 
 s2 
s 
 3
 ... 
s 
 p
3) Пусть t  3 , тогда множество корней порождающего многочлена
 , 2 , 3 , 4 , 5 , 6 ,
f1  x   x 4  x  1 ,
f 3 x   x 4  x3  x 2  x  1 ,
f 2 x   x 4  x  1 ,
f 4 x   x 4  x  1 ,
f 5 x   x 2  x  1,
f 6  x   x 4  x3  x 2  x  1 .
Порождающий многочлен БЧХ кода
g  x   НОК  f1  x , f 2  x , f 3  x , f 4  x , f 5  x , f 6  x  
.
 x4  x 1 x4  x3  x 2  x 1 x 2  x 1
Мы получили циклический код 15,5 , d min  7 , гарантировано
исправляющий 3 ошибки.




4) Пусть t  4 , тогда множество корней порождающего многочлена
 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , f1x  x 4  x  1 , f 2 x  x 4  x  1 ,
f 3 x   x 4  x3  x 2  x  1 , f 4 x   x 4  x  1 , f 5 x   x 2  x  1,
f 6  x   x 4  x3  x 2  x  1 , f 7 x   x 4  x 3  1, f8 x   x 4  x  1 .
Порождающий многочлен БЧХ кода
g  x   НОК  f1  x , f 2  x , f 3  x , f 4  x , f 5  x , f 6  x , f 7  x , f 8  x  
.
 x4  x 1 x4  x3  x 2  x 1 x2  x 1 x4  x3 1
Мы получили циклический код с повторением 15,1 , d min  15 ,
гарантировано исправляющий 7 ошибок.





4) Пусть t  5,6,7 , тогда порождающий многочлен БЧХ кода не меняется и
g  x   НОК  f1  x , f 2  x , f 3  x , f 4  x , f 5  x , f 6  x , f 7  x , f 8  x  
имеет вид
.
 x4  x 1 x4  x3  x 2  x 1 x2  x 1 x4  x3 1
Т.о. мы получаем каждый раз циклический код с повторением
15,1 , d min  15 , гарантировано исправляющий 7 ошибок.





Р. Боуз (Raj Chandra Bose) (19 июня 1901 - 31 октября 1987) индийский и
американский математик и статистик, известен благодаря работам в
области геометрии конечных полей и теории кодов с исправлением
ошибок, в которой класс кодов БЧХ отчасти назван в его честь. Бозе
родился в Хошангабаде, Индия, он был первым из пяти детей. Его отец
был врачом, и жизнь была хорошей до 1918 года, когда его мать умерла
от пандемии гриппа. Его отец умер от инсульта в следующем году.
Несмотря на трудные обстоятельства, Боуз продолжал учиться чистой
математике в Университете Калькутты. В 1947 году Боуз отправился в
Соединенные Штаты в качестве приглашенного профессора в
Колумбийском
университете
и
Университете Северной Каролины в
Чапел-Хилл. В годы на Чапел-Хилл Боуз
сделал важные открытия по теории
кодирования и построил (с С.
Шрикханде и Э.Т. Паркером) латинский
квадрат размером 10, что является
контрпримером к гипотезе Эйлера 1782
года о том, что никакой латинский
квадрат размера 4k+2 не существует.
(Лати́нский квадрат n-го порядка —
таблица размеров n × n, заполненная n
элементами множества M таким
образом, что в каждой строке и в
каждом столбце таблицы каждый
элемент из M встречается в точности
один раз).
Д.К. Чоудхури (Dwijendra Kumar RayChaudhuri) (родился 1 ноября 1933 года)
является почетным профессором в
Университете штата Огайо. Он получил
степень магистра. (1956) по математике
в Университете Калькутты и Ph.D. по
комбинаторике (1959) в Университета
Северной Каролины в Чапел-Хилле. Он
наиболее известен своей работой в
области теории кодов с исправлением
ошибок, в которых класс кодов БЧХ
назван в честь него и его научного
руководителя Боуза.
Алексис Хоквингем (1908 - 1990) французский математик, известен тем,
что открыл коды Боуза-Чоудхури-Хоквингема, которые сегодня известны
под сокращенным названием БЧХ. Этот класс кодов для исправления
ошибок был опубликован Хоквингемом в 1959 году. В наименовании кодов
также указаны имена R. C. Bose и D.K. Ray-Chaudhuri, которые
независимо обнаружили эти коды и опубликовали этот результат вскоре
после этого, в 1960 году.
92
ЛЕКЦИЯ №22
2.9.6. Коды Рида-Соломона
Коды Рида-Соломона это недвоичные БЧХ-коды, которые
получаются при m  1 , n  q  1 . Порождающий многочлен кода РидаСоломона имеет вид




g  x    x    x   2 x   3 ... x   2t ,
(145)
где t - число исправляемых ошибок,  - примитивный элемент поля
GF q  .
Число проверочных разрядов кода равно степени порождающего
многочлена, т.о. k  n  2t .
Гюстав Соломон (27 октября 1930 г. - 31
января 1996 г.) был математиком и
инженером-электриком, который был одним
из основоположников алгебраической теории
обнаружения и исправления ошибок. Он
закончил аспирантуру по математике
Массачусетского
технологического
института в 1956 году. Соломон был
известен за разработку наряду с Ирвином С.
Ридом алгебраических кодов для исправления
ошибок, названных кодами Рида-Соломона.
Соломон также был одним из соавторов
полинома Маттсона-Соломона и весовых
формул Соломона-Мак-Элиса. В поздние годы Соломон консультировал в
Лаборатории реактивного движения, штат Калифорния. Он очень
интересовался оперой и театром, и даже хотел получить
незначительные актерские роли, возможно, в телевизионных рекламных
роликах. Он верил в улучшение здоровья и чувство благополучия через
дыхательные упражнения, и он был практиком метода Фельденкрайза.
Он очень любил музыку и был композитором.
Пример 9. Код Рида-Соломона 15,11 .
Рассмотрим поле GF 16  , если t  2 , то




g  x    x    x   2 x   3 x   4  x 4   13 x 3   6 x 2   3 x   10 ,
и k  15  4  11 . Т.о. код кодирует 4*11=44 информационных бита в
кодовое слово длины 4*15=60 бит, используя 4*4=16 проверочных
разрядов.
93
Теорема 15. «О кодах Рида-Соломона». Код Рида-Соломона имеет
минимальное кодовое расстояние d min  2t  1  n  k  1 .
Доказательство.
Минимальное кодовое расстояние линейного блокового кода
удовлетворяет неравенству Синглтона
d min  n  k  1 .
С другой стороны код гарантировано исправляет ошибки кратности
t , т.е. в соответствии с теоремой об исправляющей способности линейного
кода
d min  2t  1  n  k  1 .
Т.о. d min  2t  1  n  k  1 .
При фиксированной исправляющей способности, коды РидаСоломона самые «быстрые».
Ирвинг Рид (12 ноября 1923 - 11 сентября
2012 г.) - математик и инженер. Он
известен, прежде всего, как изобретатель
класса кодов для коррекции и обнаружения
ошибок, известных как коды РидаСоломона в сотрудничестве с Густавом
Соломоном. Он также изобрел алгоритм
декодирования кода Рида-Маллера.
2.9.7. Двоичные квадратично-вычетные коды
Класс квадратично-вычетных кодов является частью циклических
кодов, среди которых найдены хорошие коды, например, коды Голея.
Теорема 16. «О квадратных корнях в полях Галуа».
 
1)
Каждый элемент поля GF 2 m имеет квадратный корень.
2)
Для
нечетных
 
простых
q,
q m  1 2
ненулевых
элементов поля GF q m имеют квадратный корень в этом поле.
94
Квадратично-вычетным кодом называется циклический код над


GF 2  , длина которого равна простому числу q , делящему 2 m  1 , т.е.
2m  1  q  p
при некотором m , а корнями порождающего полинома
 
являются все элементы  j из GF 2 m , такие, что j - квадратичные
вычеты поля GF q  , т.е.




j2
j q 1 2
g x   
x j1x


....
x
 .
(146)
множество всех квадратичных вычетов
Утверждение. Если многочлен
g x 
имеет недвоичные
коэффициенты, то для выбранного q двоичного кода не существует.
Условием существования двоичного квадратично-вычетного кода является
соотношение q  8k  1 , где k  Z .
Из (146) следует, что
x q  1  x  1g xg~x ,
 
что j - квадратичные невычеты поля GF q  , число которых q m  1 2 .
где g~  x  - многочлен, состоящий из элементов  j из GF 2 m , таких,
Теорема 17. «О квадратично-вычетных кодах». Минимальное
кодовое расстояние квадратично-вычетного кода длины q удовлетворяет
неравенству
d min  q .
(147)
Таблица 3 - Параметры некоторых квадратично-вычетных кодов.
Длина кода Число
Минимальное
Примечание
информационных
кодовое
n
разрядов k
расстояние d min
7
4
3
Код Хэмминга,
«самый
быстрый»
17
9
5
«самый
быстрый»
23
12
7
Код Голея,
«самый
быстрый»
31
16
7
«самый
быстрый»
41
21
9
«самый
95
47
24
11
71
73
79
36
37
40
11
13
15
89
45
17
быстрый»
«самый
быстрый»
«самый
быстрый»
«самый
быстрый»
2.10. ГРАНИЦЫ ДЛЯ КОДОВ
1. Граница Хэмминга
 t

i
i

n  k   log q  Cn q  1  .
 i0

2. Граница Плоткина (1960)

d min 
nq  1q k 1
q k  1
, или k  n 
(148)
qd min  1
 1  log q d min
q 1
(149)
нижняя оценка для кодового расстояния «наилучшего» кода.
3. Граница Варшамова-Гильберта (1952-1957)
q
nk
d min  2

C ni 1 q  1i ,
i 0

(150)
верхняя оценка для кодового расстояния. Если неравенство выполняется,
то код с параметрами в правой части, существует.
Варшамов Ром Рубенович, (09.04.1927, Тифлис,
Грузия-24.08.1999) Окончил Тбилисский ун-т
(1952). Будучи еще аспирантом Ром Варшамов,
приехал в Москву и встретился с легендарным
математиком, директором Математического
института АН СССР им. В. А. Стеклова
академиком И. М. Виноградовым. Ознакомившись
со
студенческими
работами
Варшамова,
академик настолько увлекся, что продержал его
у себя 5 часов. Тут же была оговорена
диссертационная тема, и Ром Рубенович был
представлен члену-корреспонденту АН СССР,
96
другому классику теории чисел - А. С. Гельфонду. Узнав о получении им
конечной формулы чисел Бернулли, Гельфонд был краток: "Автора этой
работы я беру к себе. Материала здесь больше, чем на диссертацию.
Переезжайте в Москву. Вы уже переросли аспирантуру". Так Ром
Варшамов переехал в Москву и стал работать в НИИ Министерства
радиотехнической промышленности СССР, где, в частности, занимались
криптографией. После решения задачи, которая теперь известна как
"граница Варшамова-Гильберта", академик А. Н. Колмогоров пригласил Р.
Варшамова сделать доклад на своем семинаре, а затем рекомендовал эту
работу, ставшую в дальнейшем классической, для опубликования в
Докладах АН СССР. В 1968 году Ром Рубенович Варшамов по
приглашению президиума АН Армении переехал в Ереван и стал работать
в Вычислительном центре Академии наук. Зам. директора по научной
работе (1968), директор (1970), зав. лаб. (1971), зав. отделом (с 1984) ВЦ
АН АрмССР и ЕГУ. Председатель Научного совета по кибернетике и
радиоэлектронике АН АрмССР.
Для двоичных кодов неравенство (73) имеет вид
2d min  log q d min  n1  R  ,
где R – скорость кода, для больших n и d min 
n
, получим верхнюю
2
границу Плоткина в виде
d min 1
 1  R  .
n
2
Для двоичных кодов неравенство (74) имеет вид
2
n 1 R 
d min  2

C ni 1 ,
i 0

(151)
(152)
используя формулу энтропийной оценки суммы биномиальных
коэффициентов
r

r
nH  
Cni  2  n  ,
(153)
i0
при r 
n
, H  x    x log 2  x   1  x  log 2 1  x  , заметим, что
2
97
r
r
nH  
C ni 1  C ni 11  2  n  , 


i0
r
r
 Cni 1   
i0
r
 Cni 1 
r
nH  
C ni 11  2  n  , 
i 0
r
nH  
 2 n.
(154)
i0
Полагая в (76) равенство для нижней грацицы, получим из (78)
неравенство
2 
d
d
nH  min
nH  min

2 n 1 R   2  n   2  n

d
nH  min

 ,  2 n 1 R   2  n


,
окончательно, получим
1  R   H  d min  .
(155)
 n 
0.6
Область хороших кодов
Верхняя граница Плоткина
0.4
Нижняя граница
Варшамова-Гильберта
0.2
0
0
0.2
0.4
0.6
0.8
1
Рисунок 16 – Границы существования для двоичных кодов большой длины
2.11. КОДЫ АДАМАРА
Коды Адамара это нелинейные двоичные блочные коды, которые
получаются путем выбора в качестве разрешенных кодовых комбинаций
строк матрицы Адамара.
98
Матрица Адамара M r , это квадратная r  r матрица, состоящая из
+1 и −1, удовлетворяющая условию, в соответствии с которым каждый
столбец отличается от другого столбца ровно в r 2 позиций. Один столбец
и одна строка матрицы Адамара состоит из одних 1 (нормализованная
матрица Адамара). Строки матрицы Адамара ортогональны, т.е.
M r M Tr  rE .
Матрица Адамара 2  2 имеет вид
1 1 
M 2  
 .
1  1
Матрица Адамара r  r имеет вид
Mr 
M
 .
M 2 r   r
M

M
 r
r
Т.о. можно найти матрицы Адамара, порядок которых имеет степень
двойки, делящуюся на 4, т.е. r  2,4,16,... .
Матрицы Адамара порядка 8, 12 и других целых, делящихся на 4, не
являющихся степенями 2, до числа 262 включительно, также найдены.
Считается, что существуют матрицы Адамара для всех порядков,
делящихся на 4, но это пока не доказано.
Для построения помехоустойчивого кода матрицу Адамара M r
превращают в двоичную заменой 1  0 ,  1  1 .
Коды Адамара формируется следующими тремя способами:
1) Код Адамара  1 имеет размер n  2 m  1 , k  m , d min  2 m 1 . Код
получается выбрасыванием первого столбца, содержащего нули, и
использованием оставшихся строк матрицы M m в качестве
2
разрешенных кодовых комбинаций;
2) Код
Адамара
2
имеет
размер
n  2 m 1,
k  m  1,
d min  2 m 1  1. Код получается дополнением кода  1
инвертированными разрешенными кодовыми комбинациями;
его
3) Код Адамара  3 имеет размер n  2 m , k  m  1 , d min  2 m 1 . Код
получается использованием строк матрицы M m и их инверсий
2
(замена 1 на 0 и наоборот) в качестве разрешенных кодовых
комбинаций. Данный нелинейный код называют также
биортогональным кодом.
99
Валерий Денисович Гоппа (родился 13
июня 1939 года в городе Кировоград, на
Украине) — советский и российский
математик, д.ф.-м.н., профессор, окончил
МГТУ
им.
Баумана,
занимался
исследованиями
связей
между
алгебраической геометрией и теорией
кодирования и описал новый класс
линейных кодов. Сейчас эти коды
называются кодами Гоппы.
2.12. КОДЫ ГОППЫ
Коды Гоппы (1969) представляют собой очень широкий подкласс
линейных кодов, не являющихся, вообще говоря, циклическими, но
включающий в себя БЧХ-коды. Известно, что среди этих кодов есть коды,
лежащие на границе Варшамова — Гилберта. Для кодов Гоппы известны
алгоритмы декодирования, подобные алгоритмам декодирования БЧХкодов, в частности алгоритму Питерсона-Горенстейна-Цирлера. Приведем
описание кода, следуя статье В. Д. Гоппы «Новый класс линейных
корректирующих кодов. — Журнал «Проблемы передачи информации»,
1970».
 
 
1. Пусть имеем поле Галуа GF 2 m , подмножество L  GF 2 m ,
элементов L  1 ,..., n  и n  2 m .
 
2. Пусть многочлен g  z   GF 2 m z , не имеет корней в L , т.е.
g  i   0 . Этот многочлен называется порождающим многочленом кода
Гоппы.
3. Пусть   GF 2 n - линейный код в пространстве двоичных
кодовых комбинаций GF 2 n .
4. Каждому вектору a  a1 ,..., a n   GF 2 n ставится в соответствие
рациональная функция
n
Ra  z  
a
 z ii .
i 1
100
Кодом Гоппы  называют такое множество a  a1 ,..., a n   GF 2 n ,
для которых
Ra  z   0, mod g  z .
Проверочную матрицу кода Гоппы находят следующим образом.
Для разрешенной кодовой комбинации a  a1 ,..., a n  имеет место
равенство
n
a
 z i i  0, mod g z .
i 1
 
Элемент  z   i  кольца многочленов g  z   GF 2 m z  / g  z  имеет
обратный элемент в этом кольце, который может быть найден из
определения порождающего многочлена. Т.к.  i - корень многочлена
 g z   g  i 
 
в кольце GF 2 m z / g  z  , то обратный элемент
 z   i 1
имеет вид
 z   i 1 
g  z   g  i  1
g  i  .
z   i 
Тогда
n

i 1
ai
g  z   g  i  1
g  i   0, mod g  z .
z   i 
Последнее соотношение позволяет записать проверочную матрицу с
 
коэффициентами в кольце GF 2 m z  в виде
Ha  0 ,
 g  z   g 1  1

g z   g  n  1
H  
g 1  ...
g  n  .
z   n 
  z  1 

r
Пусть
g z  
 gi z i ,
тогда, используя формулу разности n-х
i 0
степеней
a n  b n   a  ba n 1  a n 2b  ...  abn  2  b n 1 ,
для каждой степени, получим

g r g 1 1 
...

  g r 1  g r1 g 1 1  ...



H 
 r

i 1  1

g i1 g 1  ...



  i 1

g r g 1  n 



1
g r 1  g r n g  n 


.
r



i 1  1

g i n g  n  



 i 1



101
В полученной матрице строки являются линейными комбинациями
строк следующей матрицы
 g 1 1 
...
g 1  n  

  g 1 1  ...
 n g 1  n  
H  1






r

1

1
r

1
1

 n g  n 
 1 g 1  ...
...
 1

...
 
 1


 r 1
...
 1

1  g 1 1  ...
0


 n  0


0

.
 






r 1 

1
 n  0
...
g  n 
Если взять n  2 m  1 , в качестве L  1 ,..., n  - все ненулевые
 
элементы поля GF 2 m , g  z   z 2 r , то получим код БЧХ.
Число проверочных разрядов кода Гоппы не больше m  deg  g  z 
разрядов. Минимальное кодовое расстояние удовлетворяет неравенству
d min  2 deg g  z   1 .
Пример 10. Код Гоппы 16,8 , гарантированно исправляющий 2
 
качестве g  z  используем неприводимый в поле GF 2 4  многочлен
z 2  z   3 . Найдем проверочную матрицу в поле GF 24  в виде
ошибки. В данном случае рассматривается поле GF 2 4 , n  2 4  16 . В
 g 1 1  ... g 1  n 

1

 , g 1   
H
.
1
2
3


1
1
z

z






1 g 1 ...  n g  n 


 
Подставляя в данное выражение элементы поля GF 2 4 , используя
обозначение  для примитивного элемента, таблицу элементов поля
 
GF 2 4 и порядок 1  1 ,  2   ,  3   2 ,…, 15   14 , 16  0 .
12 4 3 9 4  8 6 3 6  2 2 8 9 12

H =  12 5 5 12 8 6 14 13 11
11 13 14 6 8
        
1     
0 

 
Используя двоичную форму представления элементов поля Галуа GF 2 4 ,
получим проверочную матрицу в виде.
102
1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 


1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
1


1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1 


1
1
0
0
1
0
1
0
0
0
0
0
0
1
0
1


H 
.
1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0


1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 


1
1
1
1
0
0
0
0
1
0
1
0
0
0
0
0


1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 


Данную матрицу можно привести к систематическому виду, затем
найти порождающую матрицу и завершить строительство кода.
103
ЛЕКЦИЯ №23
2.13. СВЕРТОЧНЫЕ КОДЫ
Сверточный код является частным случаем древовидного кодера,
который схематично можно описать следующим образом.
k
l*k
…
ДК
n
Рисунок 17 - Схема древовидного кодирования
Информационные символы из поля GF q  на входе древовидного
кодера разбивается на блоки длины k с перекрытием l блоков. Каждому
блоку l*k символов в кодере ставится в соответствие блок символов на
выходе длины n. Параметр l называют длиной кодового ограничения (в
общем случае длина кодового ограничения может быть бесконечной).
Древовидный код с конечной длиной кодового ограничения
называют решетчатым кодом.
Стационарность решетчатого кодера означает, что если две
входные последовательность совпадают, но сдвинуты во времени на
некоторое число тактов, то соответствующие им выходные
последовательности также совпадают и сдвинуты на тоже число тактов.
Линейность решетчатого кодера означает, что линейной
комбинации входных последовательностей соответствует линейная
комбинация выходных.
Линейные,
стационарные
сверточными кодами.
древовидные
коды
Сверточный код называется систематическим,
информационных символов является частью выходных.
называются
если
блок
Двоичный свёрточный код создаётся прохождением передаваемой
двоичной информационной последовательности через линейный
сдвиговый регистр с конечным числом состояний. В общем, регистр
сдвига состоит из l* k битовых ячеек.
Входные данные продвигаются вдоль регистра сдвига на k бит за
один такт. Число выходных битов за один такт равно n. Следовательно,
скорость сверточного кода по-прежнему R  k n .
104
1
1
l
2
2
…
k
1
2
…
k
…
1
2
…
регистр сдвига из l*k ячеек
n сумматоров по модулю 2
1
n
2
коммутатор
Рисунок 18 - Свёрточный кодер
D 1954 году Питер Эйлас (Peter Elias) предложил сверточные коды
как альтернативу блоковым кодам.
В 1955 году независимо Л. М. Финком был предложен вариант
сверточного кода, который известен в литературе как рекуррентный код.
В 1959 году Хегельбергер (Hegelbeger), не имевший представления о
работе советских ученых в области кодирования, «переоткрыл»
рекуррентный код, который теперь известен под его именем.
Рекуррентный код строится следующим образом. Обозначая
информационные символы через ai, а проверочные через bi, получаем
последовательность символов
a1b1a2b2a3b3 …… akbkak+1bk+1…..
Информационные символы определяются переданным сообщением,
а проверочные формируются следующим образом
bi = (ai-s + ai+s+1), mod 2,
(156)
где s - произвольное целое число, называемое шагом кода (s =
0,1,2…).
В 1957 году Дж. Возенкрафтом был разработан метод
последовательного
декодирования
сверточных
кодов,
который
впоследствии был усовершенствован А.М. Фано.
Вайнер и Эш в 1963 году предложили семейство сверточных кодов,
исправляющих одну ошибку, Месси, Сайн, Форни к 1970 году создали
алгебраическую теорию сверточных кодов. В 1967 году был открыт
эффективный алгоритм декодирования сверточного кода – алгоритм
Витерби.
105
k
Пример 11. Двоичный сверточный кодер со скоростью R  1 2 ,
l  3.
Схема кодера имеет вид, показанный на рисунке 18.
1
2
1
3
2
Рисунок 19 - Свёрточный кодер со скоростью R  1 2
Проанализируем работу кодера следующим образом
Вход 1
Выход
1
Вход 2
Выход
2
0
0
1
11
0
01
0
11
0
00
1
11
1
10
0
10
0
11
0
00
0
0
1
11
0
01
1
00
0
01
1
00
1
10
0
10
0
11
0
00
При изменении входной последовательности в одном бите,
выходные меняются в 5-ти битах. Это означает, что число ошибок, которое
должно произойти, что бы одна разрешенная комбинация перешла в
другую равно 5-ти. Эта величина называется кодовым (свободным)
расстоянием сверточного кода и аналогична понятию минимального
кодового расстояния блоковых кодов если она наименьшая среди всех
возможных.
Иногда работу сверточного кода можно проанализировать и более
традиционным способом.
Вход 1
Выход
1
0
0
0
00
0
00
1
11
0
01
0
11
0
00
0
00
0
00
0
00
106
В этом случае на выходе кодера мы наблюдаем последовательность
символов, которую называют импульсной характеристикой сверточного
кода.
Пример 12. Двоичный сверточный кодер со скоростью R  1 3 , l  3 .
Схема кодера имеет вид, показанный на рисунке 19.
1
1
2
2
3
3
Рисунок 20 - Свёрточный кодер со скоростью R  1 3
Таблица 4 - Состояния регистра сдвига
Состояние регистра сдвига Выход кодера
000
000
001
011
010
001
011
010
100
111
101
101
110
110
111
100
107
a
b
000
000
111
000
111
111
100
001
010
001
c
110
000
111
100
001
010
110
110
d
101
101
Рисунок 21 – Решетчатая диаграмма свёрточного кодера
со скоростью R  1 3
Решетчатая диаграмма произвольного двоичного сверточного кода
со скоростью R  1 n имеет 2 l 1 состояний.
2.13.1. Полиномиальное описание сверточных кодов
Представим двоичный кодер со скоростью R  1 n в следующем
виде
1
2
ячейка памяти
ячейка памяти
g11
…
g12
…
g21
l
…
ячейка памяти
g1l
…
g22
g21
gn2
1
gnl
n
2
коммутатор
Рисунок 22 - Свёрточный кодер со скоростью R  1 n
108
Нетрудно заметить, что n входов коммутатора можно описать
дискретными свертками входной двоичной последовательности с
импульсными характеристиками g i,r , где r  1,..., l , i  1,.., n
l
zi , j 
 s j r 1gi,r ,
(157)
r 1
где zi, j - i -й вход коммутатора на j -м такте, s j r 1 - двоичная
входная последовательность.
Свертку
(80)
всегда
можно
описать
соответствующим
произведением полиномов в кольце GF 2 x 
zi  x   s  x g i  x  ,
(158)
где g i  x  - порождающие полиномы сверточного кода с
коэффициентами из поля GF 2  .
Рассмотрим сверточный код с произвольной скоростью. Соединим k
сверточных кодеров со скоростью R  1 n по схеме, показанной на
следующем рисунке
Регистр длиной k двоичных ячеек памяти (заполняется за один такт)
Сверточный кодер
Сверточный кодер
Сверточный кодер
R 1 n
R 1 n
R 1 n
n сумматоров по модулю 2
1
n
2
коммутатор
Рисунок 23 - Свёрточный кодер со скоростью R  k n
Работу сверточного кодера со скоростью R  k n можно описать
следующим произведением полиномов в кольце GF 2 x 
k
zi  x  
 sv xgi,v x .
(159)
v 1
109
Операцию кодирования можно компактно описать с помощью
матричного произведения в кольце GF 2 x 
z  x   s x G  x  ,
(160)
где
z  x    z1  x  z 2  x  ... z n  x 
вектор-строка
с
полиномиальными коэффициентами, s x   s1  x  s2  x  ... sk  x  информационный вектор-строка с полиномиальными коэффициентами,
G  x  - порождающая матрица сверточного кода с полиномиальными
коэффициентами g i, v  x  .
Проверочная матрица сверточного кода определяется из условия
G  x HT  x   0 .
Вектор синдромных многочленов можно определить
(161)
q x   v  x HT  x  .
Систематический кодер для сверточного кодера
G  x   I  P x .
Проверочная матрица систематического кодера имеет вид
(162)


H x    PT  x I .
(163)
(164)
В отличии от блоковых кодов не каждый сверточный код
эквивалентен систематическому сверточному коду.
Сверточный код со скоростью R  1 n , порождающие многочлены
которого удовлетворяют условию
НОД g1  x , g 2  x ,..., g n  x   x d ,
(165)
при
некотором
d Z ,
называется
некатастрофическим
сверточным кодом, где НОД g1  x , g 2  x ,..., g n  x  - наибольший общий
делитель многочленов g1  x , g 2  x ,..., g n  x  . В противном случае он
называется катастрофическим сверточным кодом.
Систематические сверточные коды всегда некатострофические.
Некатострофический сверточный код при отсутствии ошибок
можно декодировать, используя алгоритм Евклида для многочленов
(алгоритм нахождения наибольшего общего делителя (НОД) многочленов).
В соответствии с алгоритмом Евклида существуют многочлены
a1  x , a 2  x ,..., a n  x  , такие, что
n
 ai xgi x  1 .
(166)
i 1
Тогда в соответствии (81) получим алгоритм декодирования в виде
n
n
n
 ai xzi x   ai xsxgi x  sx ai xgi x  sx .
i 1
i 1
(167)
i 1
110
ЛЕКЦИЯ №24
2.13.2. Примеры двоичных сверточных кодов
Задача нахождения хорошего сверточного кода является задачей
поиска хорошего множества взаимно простых порождающих многочленов.
Рассмотренная теория легко обобщается на случай недвоичных
сверточных кодов.
Минимальным кодовым расстоянием для любых j начальных
сегментов кода длины n называется j -м минимальное расстояние по
Хэммингу d j между всеми разрешенными кодовыми комбинациями,
отличающимися информационными символами. d l *k называется просто
минимальным кодовым расстоянием сверточного кода.
Свободным расстоянием сверточного кода называется величина
d св  max d j .
(168)
j
Для прогноза исправляющей способности сверточного кода можно
использовать верхнюю границу для свободного расстояния, известную как
граница Хеллера (1968)
 2i 1


d св  min 
l  i  1 ,
i  2 i 1  1

(169)
где x  - наибольшее целое.
Мэ́сси Дже́ймс (англ. James Lee
Massey; 11 февраля 1934, Ваузен, Огайо
— 16 июня 2013) — американский
учёный, внесший значительный вклад в
теорию информации и криптографию.
Являлся
профессором
цифровых
технологий в Швейцарской высшей
технической школе Цюриха. Наиболее
значительными результатами является
алгоритм декодирования БЧХ кодовалгоритм
Берлекэмпа
—
Мэсси,
разработка эффективных сверточных
кодов, разработка блочных алгоритмов
шифрования. Так в 1956 году Мэсси
получил степень бакалавра наук в
области электротехники. После трех лет военной службы, в 1959 году
Мэсси поступил в Массачусетский технологический институт, где
111
сосредоточился на теории кодирования. В 1962 году он получает степень
доктора философии. На втором курсе аспирантуры Мэсси решил, что
хотел бы пойти в область, связанную с информацией. Там он
познакомился с такими людьми, как Фано и Шеннон. В качестве темы для
диссертации Мэсси выбрал свёрточный код. После получения степени,
Мэсси решил вернуться в университет Нотр-Дам, где он продолжал
изучать радиотехнику вплоть до 1977 года. Здесь он устроился
преподавателем на электротехническом факультете. Так же Мэсси
работал вместе с лучшим другом Галлагером, которому он помог
закончит книгу по теории информации. В 1980 году Мэсси возвращается в
Швейцарскую высшую техническую школу Цюриха. В это время он
работал в области безопасности с криптографией и секретности
кодирования и исследование связи с произвольным доступом. Мэсси
совместно с одним из его лучших друзей Омурой сделали пару изобретений
и подали заявки на их патенты. В дальнейшем одно из них получило
название алгоритм Мэсси - Омура. Также Мэсси разработал шифр
SAFER. Спустя некоторое время этот шифр был доработан и принят в
качестве основы протокола аутентификации в bluetooth. В 1982 году
Мэсси попросили прочитать фундаментальные лекции в области
криптографии в одном из университетов Китая. В это время он
совместно с докторантом Лай Сюэцзя разработали новый блочный
шифр, который они запатентовали как IDEA (англ. International Data
Encryption Algorythm). В 1998 году Мэсси уходит на пенсию и переезжает
в Копенгаген, где живёт там до своей смерти. Скончался от рака 16 июня
2013 года в своём доме в Копенгагене, Дания.
Большинство хороших сверточных кодов найдены компьютерным
моделированием. В следующей таблице приведены некоторые хорошие
двоичные сверточные коды для случая R  1 n .
R
l
12
12
12
13
13
13
13
14
3
5
8
3
6
7
9
3
Таблица 5 - Некоторые двоичные сверточные коды
Порождающие многочлены в
dсв
Граница
восьмеричной записи
Хеллера
5
7
5
5
23
35
7
8
247
371
10
11
5
7
7
8
8
47
53
75
13
13
133
145
175
15
15
557
663
711
18
18
5
7
7
7
10
10
112
14 5
14 8
14 9
25
235
463
33
331
663
33
331
663
33
331
663
16
22
24
16
22
24
Пример 13. Двоичный сверточный кодер со скоростью R  1 4 , l  3 .
Порождающие полиномы заданы в таблице в виде восьмеричной
записи. Декодируем эти данные, получим
g1  x   x 2 , g 2  x   x 2  x , g 3  x   x 2  x , g 4  x   x 2  x .
В соответствии с таблицей такой кодер имеет свободное кодовое
расстояние 10, т.е. исправляет 4 ошибки при приеме не менее 12 бит
кодированной информации или передачи не менее 3-х бит информации.
Схема кодера имеет вид, показанный на рисунке.
1
2
2
1
3
4
3
Рисунок 24 – Сверточный кодер со скоростью R  1 4 , l  3
2.13.3. Декодирование сверточных кодов
В сверточном кодере память о текущем символе распространяется на
целую цепочку принимаемых символов, что создает некоторую сложность
для декодирования.
Если блок n кодовых символов принят успешно, то его можно
исключить из дальнейшего рассмотрения.
Например, пусть в (80) первый zi,1 блок декодирован успешно, тогда
l
zi, j  zi ,1 
l
l
 s j  r 1gi, r   s1 r 1gi,r   s j  r gi, r .
r 1
r 1
(170)
r 1
Процедуру исключения правильно декодированных символов можно
продолжить на любое число шагов. Декодеры, использующие данный
прием называют декодерами с обратной связью.
Если блок первых n кодовых символов декодирован с ошибкой, то
обратная связь может привести к введению дополнительных ошибок в
113
декодируемую
последовательность.
Этот
процесс
называют
распространением ошибок.
Если процесс распространения ошибок вызывается только
алгоритмом декодирования, то говорят об обычном распространении
ошибок,
если распространение
ошибок связано с
выбором
катастрофического
кодера,
то
говорят
о
катастрофическом
распространении ошибок.
Оптимальным алгоритмом декодирования сверточного кода
является алгоритм полного перебора всех разрешенных кодовых
комбинаций кода с целью поиска ближайшей из них к принятой кодовой
комбинации.
Если критерием близости является расстояние Хэмминга, то говорят
о жестком декодере.
Если демодулятор (детектор) формирует мягкие решения (т.е. выдает
на выход не двоичные символы, а вещественные значения
корреляционного интеграла), а критерием близости выступает расстояние
Евклида, то говорят о мягком декодере.
Рассмотрим некоторые алгоритмы декодирования сверточного кода
на примере двоичного сверточного кодера со скоростью R  1 3 , l  3 из
примера 12.
Пример 14. Декодирование сверточного кода со скоростью R  1 3 ,
l  3.
Решетчатая диаграмма данного свёрточного кодера имеет вид
a
000
000
000
000
011
b
111
111
111
100
001
010
001
c
110
011
111
100
001
010
110
110
d
101
101
Рисунок 25 - Решетчатая диаграмма сверточного кода
со скоростью R  1 3 , l  3 .
Таблица 6 – Пример декодирования сверточного кода,
3-такт работы декодера
Принятая кодовая комбинация 001 100 000
Состояния
d3
114
Разрешенные кодовые
комбинации на
3-м такте
000
111
000
111
111
000
111
000
000
001
111
110
001
000
110
111
000
011
001
010
100
111
101
110
решетки
a
b
c
d
2
6
5
4
5
5
6
5
В таблице показан пример полного перебора всех разрешенных
кодовых комбинаций на 3-м такте работы сверточного декодера после
приема кодовой комбинации 001 100 000 101. Если бы работа декодера на
этом заканчивалась, то результат декодирования по минимуму d 3 был бы
000 000 000. Т.о. для принятия решения на 3-м такте нужно перебрать 2 3
разрешенных комбинаций. Очевидно, что на 4-м такте число разрешенных
комбинаций было бы 2 4 и т.д. на j -м 2 j . При этом длины перебираемых
комбинаций на 3-м такте 9 бит, а на 4-м 12 бит и далее на j -м j  n бит.
Т.о. алгоритм полного перебора характеризуется полиномиальным
ростом числа альтернатив и линейным ростом требуемой памяти для их
хранения при увеличении числа тактов.
Рассмотрим
возможности
для
сокращения
описанных
вычислительных затрат. Уберем из перебираемых на четвертом такте
разрешенных кодовых комбинаций те из них, которые приходят на 3-м
такте в один узел решетки и уже имеют большие значения d 3 , оставшиеся
кодовые комбинации называются «выжившими» их число равно 4-м. На 4м такте вычисляем d 4 по 8-ми кодовым комбинациям, используя только
выжившие пути на 3-м шаге.
a
b
000
000
000
111
100
001
c
010
110
d
101
Рисунок 26 - Выжившие кодовые комбинации (пути по решетке)
на 3-м шаге.
115
Если бы работа декодера на этом заканчивалась, то результат
декодирования по минимуму d 4 был бы 000 000 000 111.
Таблица 7 – Пример декодирования сверточного кода, 4-такт работы
декодера
Принятая кодовая комбинация 001 100 000 101
Разрешенные кодовые
комбинации на
3-м такте
000
111
111
000
000
111
111
111
000
110
001
111
000
110
001
110
000
010
100
110
000
010
100
101
000
011
001
010
111
100
110
101
Состояния
решетки
a
b
c
d
d4
4
6
6
9
3
5
7
6
Для декодирования на 5-м такте опять отбракуем избыточные для
сравнения кодовые комбинации. Выжившие на 4-м шаге показаны на
рисунке.
a
b
000
000
000
111
000
111
100
001
001
c
010
110
d
101
101
Рисунок 27 - Выжившие кодовые комбинации (пути по решетке)
на 4-м шаге
Т.о. если проводить отбраковку бесперспективных кодовых
комбинаций на каждом шаге работы декодера, то на j -м такте достаточно
перебрать только 2 l 1 альтернатив. Данный вариант полного перебора
называют алгоритмом Витерби декодирования сверточного кода.
Несмотря на существенное сокращение альтернатив в алгоритме
Витерби, для практической реализации требуется более существенное
снижение сложности алгоритма декодирования. В этой связи актуальны
116
декодеры, имеющие более скромную исправляющую способность, но
требующие меньших вычислительных затрат. К их числу можно отнести
алгоритм Возенкрафта, алгоритм Фано, квазиоптимальный (усеченный)
алгоритм Витерби, в котором поиск по решетке осуществляется только на
длину кодового ограничения.
Ро́берт Ма́рио Фа́но (Robert Mario Fano,
11 ноября 1917[2], Турин, Италия — 13
июля 2016, Нейплс, Флорида, США) —
итальяно-американский
учёный
в
области
информатики,
профессор
факультетов
электротехники
и
компьютерных наук в Массачусетском
технологическом
институте.
Фано
известен по работам в области теории
информации, он независимо от Клода
Шеннона изобрел алгоритм сжатия
информации и алгоритм декодирования
сверточных кодов. Отец, Джино Фано,
был профессором геометрии Туринского
университета. Мать, Роза Кассин,
происходила из семьи инженеров и была
талантливой художницей и музыкантом.
Его старший брат Уго Фано (1912—2001) впоследствии стал известным
физиком-теоретиком. Роберт Фано поступил в Политехнический
университет Турина, но после принятия в Италии антиеврейских законов
в 1939 году эмигрировал в США. Здесь он продолжил обучение в
Массачусетском технологическом институте (МИТ), получив степень
бакалавра в 1941 году, а в 1947 году защитил докторскую.
117
Эндрю Джеймс Витерби (9 марта
1935,Бергамо, Италия — в н.вр. живет и
работает в США)
— американский
инженер и бизнесмен, основавший
Qualcomm. В 1967 году предложил
использовать алгоритм Витерби для
декодирования свёрточного кода. Э.
Витерби также принял участие в
разработке стандарта CDMA, является
автором книг по теории информации и
связи.
118
ЛЕКЦИЯ №25
2.14. КАСКАДНЫЕ КОДЫ
Объединение нескольких кодеров путем укрупнения алфавита
кодируемых символов является одним из способов построения кодов с
большими длинами (способ предложен Д. Форни в 1966 году).
GF q 
1
1
2
…
k
…
n
2
1
2
…
k
…
n
3
1
2
…
k
…
n
 
GF q k
…
K
1
2
…
k
…
n
K+1
1
2
…
k
…
n
…
k
…
n
…
N
1
2
Рисунок 28 – Каскадный код, полученный объединением блочного  N, K 
 
кода над GF q k и блочного n, k  кода над GF q 
Например, если взять внутренний кодер Рида-Соломона 7,3 над
 
GF 8 , а внешний код Рида-Соломона 511,505 над GF 83 , то получим
код 511 * 7,3577  505 * 4  7 * 6   3577,1515 над GF 8 , гарантировано
исправляющий 11 ошибок. Т.е. последовательность из K блоков по k qичных символов кодируется внешним  N, K  кодером, затем каждый блок
по k q-ичных символов кодируется внутренним n, k  кодером.
Используя каскадный метод можно комбинировать сверточные и
блоковые коды, например, весьма эффективна комбинация «слабого»
двоичного сверточного кода и кода Рида-Соломона. Данный каскадный
код широко используется в спутниковых каналах связи.
Часто в данных схемах между внешним и внутренним кодером
включают перемежитель символов, осуществляющий «случайную»
перестановку символов внешнего кода. Цель использования перемежителя
это борьба с пакетами ошибок, появляющихся при декодировании
119
сверточного кода, что позволяет существенно улучшить эффективность
каскадной конструкции в целом.
Перемежитель
N символов
Внешний
блоковый
 N, K  кодер
 
поля GF q k
 
GF q k
символы
Внутренний
блоковый или
сверточный
n, k  кодер
GF q 
символы
Рисунок 29 – Каскадный код, полученный объединением блочного  N, K 
 
кода над GF q k и сверточного n, k  кода над GF q 
Следующим важным этапом в развитии схем каскадного
кодирования стали турбо-коды. Турбо-коды были опубликованы К.
Берроу (C. Berrou), А. Главьё (A. Glavieux) и П. Ситимашимой (P.
Thitimajshima) в 1993 году в статье «Near Shannon Limit Error-Correcting
Coding and Decoding: Turbo-Codes, Proceedings of ICC 93, Geneva,
Switzerland, pp. 1064-1070, May, 1993».
Турбокод состоит из каскада параллельно соединённых
систематических кодов. Эти составляющие называются компонентными
кодами. В качестве компонентных кодов могут использоваться свёрточные
коды, коды Хемминга, Рида -Соломона, БЧХ и другие. В зависимости от
выбора компонентного кода турбо-коды делятся на свёрточные
турбокоды (Turbo Convolutional Codes) и блоковые коды-произведения
(Turbo Product Codes).
Клод Берро (родился 23 сентября 1951 года
в
Пенмарке)
является
профессором
электротехники в Высшей национальной
школе телекоммуникаций Бретани. Он
является изобретателем Turbo-кодов. Берро
также разработал турбо выравнивание.
Турбо-коды использовались во всех основных
стандартах сотовой связи, начиная с 3G, и
в настоящее время являются частью
протокола сотовой связи LTE. Они также
используются в протоколе спутниковой
связи Inmarsat, а также в протоколах связи
DVB-RCS и DVB-RCS2.
120
Многочисленные экспериментальные исследования турбо-кодов,
показали, что структура перемежителя практически не влияет на эффективность кодирования, которая растет с ростом длины кодового ограничения сверточного кода и размера перемежителя.
Информационные
символы
Систематическ
ий кодер
Проверочные
символы
Информационные
символы
Перемежитель
Систематически
й кодер
Проверочные
символы
Рисунок 30 - Схема простейшего турбокодера
Пример 15. Рассмотрим двоичный рекурсивный сверточный кодер
со скоростью R  1 2 , l  3 . Схема кодера имеет вид (см. для сравнения
пример 10)
1
1
2
3
2
Рисунок 31 – Рекурсивный свёрточный кодер со скоростью R  1 2
Проанализируем работу кодера следующим образом
121
Вход 1 0
0
1
0
0
0
1
1
0
0
0
Выход
11
01
01
00
10
11
00
00
00
1
Вход 2 0
0
1
0
1
0
1
1
0
0
0
Выход
11
01
11
01
11
11
01
01
00
2
При изменении входной последовательности в одном бите,
выходные меняются в 5-ти битах, однако выходные последовательности
отличаются от выходных последовательностей из примера 10. Проверим
импульсную характеристику кодера.
Вход 1
Выход
1
0
0
0
00
0
00
1
11
0
01
0
01
0
00
0
01
0
01
0
00
В этом случае на выходе кодера после прохождения 1 мы наблюдаем
бесконечную последовательность символов. Т.е. рекурсивный сверточный
кодер имеет бесконечную импульсную характеристику, однако
исправляющая способность кодера только за счет рекурсивности не растет.
Считается, что при построении турбо-кодов, использовать
рекурсивные сверточные коды предпочтительнее. Поэтому построим
простейший сверточный турбо-код со скоростью R  1 3 в следующем
виде.
Перемежитель
1
1
2
2
3
1
2
3
3
Рисунок 32 – Свёрточный турбо-кодер со скоростью R  1 3
122
При декодировании из общего потока символов выделяют два
потока кодовых символов, причем информационные части этих двух
потоков в силу систематического кодирования идентичны. Это
обстоятельство позволяет использовать два декодера, каждый из которых
производит декодирование своего кодового блока. Поскольку
информационные части каждого из двух кодовых блоков идентичны,
декодированную информацию первого декодера можно использовать в
качестве априорной информации для второго декодера с целью уточнения
результата декодирования. Подобную операцию можно производить
многократно. В этом состоит принцип итеративного декодирования турбокода.
2.15. МЯГКОЕ ДЕКОДИРОВАНИЕ БЛОКОВЫХ КОДОВ
Рассмотрим, источник двоичных сообщений, вся информация
которого кодируется блочным помехоустойчивым двоичным n, k  кодом
и передается в канал связи в виде сигнала ФМ-2, модулированного
амплитудными коэффициентами, соответствующими символам 0,1.
Схема «жесткого» декодирования предполагает, что на каждом
интервале времени iT , i  1T  демодулятор принимает решения в пользу
âi , затем декодер декодирует блок из n символов в блок k двоичных
информационных символов, обычно по минимуму расстояния Хэмминга.
Схема «мягкого» декодирования предполагает, что на интервале
времени 0, nT  демодулятор принимает решения в пользу вектора
aˆ i  a1 a2 ... an  , где i  1,...,2 k , и тем самым декодирует блок k
двоичных информационных символов, обычно по минимуму расстояния
Евклида.
С целью сравнения данных схем рассмотрим случай оптимального
приема на фоне БГШ полностью известных сигналов (когерентный
прием).
Вероятность
ошибки
при
когерентном
приеме
противоположенных двоичных сигналов с равной энергией на фоне БГШ
получена нами на лекции №4
 2 E0 
  1  erf q  .
pош  1  erf 
(171)

N
0 

Будем предполагать, что вероятность ошибки в блоке из n символов
не зависит от номера символа. Т.о. имеем двоичный симметричный канал
без памяти, в котором вероятность ошибки при приеме k двоичных
информационных символов можно получить в виде
123
a1s0 t 
…01…
K
ИДС
a1s0 t  T  a n s0 t  nT 
…
М
T
0

ДМ
…01…
ДK
nT
2T
Помехи
Рисунок 33 - Пример построения системы передачи и приема двоичных
символов по схеме «жесткого» декодера
n
si t  
…01…
ИДС
K
 a j s0 t   j  1T 
iˆ
j 1
…
М
0
T
2T

ДМ
nT
Помехи
Рисунок 34 - Пример построения системы передачи и приема двоичных
символов по схеме «мягкого» декодера
j  d min 1 2
pk  1 
C nj pош j 1  pош n  j .
j 0

(172)
Рассмотрим схему «мягкого» декодирования как задачу различения
M полностью известных на приемной стороне сигналов, наблюдаемых на
фоне аддитивного белого гауссовского шума.
Модель сигнала
xt   si t   nt  ,
(173)
где nt  - реализация белого гауссовского шума, i  1,..., M , M  2 k .
В соответствии с критерием идеального наблюдателя и в случае,
1
когда PH i  
получаем алгоритм МП. Функционал правдоподобия
M
px H i , x  L 2 0, nT  можно записать в виде
 1 T

2 






(174)
p x H i   c  exp 
x
t

s
t
dt
.
i

N


0 0
Тогда алгоритм приема (декодирования)
nT




1

2 
ˆ
 xt   si t  dt   
k  arg max p x H i   arg max  c  exp 
N
i
i 
0

 
0

 nT


2 
 arg min  xt   si t  dt   arg min  2 x, s i  .
i 
i

 0

(175)
где  x, si  расстояние Евклида между сигналами xt  и si t  в
пространстве L 2 0, nT .
Т.о. оптимальный алгоритм различения сводится к выбору наиболее
близкого к принятому одного из M передаваемых сигналов по евклидовой
метрике гильбертова пространства L 2 0, nT . Перепишем (97) в виде




 nT

 nT





2
2
2
ˆ
k  arg min  xt   si t  dt   arg min  x t   2 xt si t   si t  dt  
i 
i 


 0

 0

E 

 arg min E x  2 Z i  Ei   arg max  Z i  i ,
2 
i
i 
(176)



где
Ex
- энергия реализации наблюдаемого сигнала
xt  ;
nT
Zi 
 xt si t dt
- корреляционный интеграл, соответствующий сигналу
0
si t  ; Ei - энергия сигнала si t  .
Определим помехоустойчивость когерентного различителя для
системы сигналов равной энергии. В этом случае алгоритм принятия
решений можно записать в виде
(177)
iˆ  arg max Z i ,
i
В общем случае точное выражение для полной вероятности ошибки
для M>2 получить затруднительно. В этом случае пользуются
аддитивной верхней границей для вероятности ошибки, которая для
сигналов с одинаковой энергией может быть определена на основе
неравенства для вероятности ошибки при приеме l -го сигнала, которое
можно записать в виде неравенства Буля


M

 M 1


pl  P  Dlk  
PDlk .
(178)
k 1
 k 1
k  l

В этом выражении Dlk  Z l  Z k  - событие, заключающееся в том,
что значение корреляционного интеграла Z l меньше чем значение
интеграла Z k , т.е. различитель принимает решение в пользу приема k-го
сигнала. Смысл неравенства Буля в том, что вероятность объединения
совместных событий не превышает вероятности объединения
несовместных событий. Найдем вероятность ошибки PDlk  при приеме
сигнала sl t 


0
PDlk  
 pZ H l dZ .
(179)

Если справедлива гипотеза H l , то
nT
Z
 sl t   nt sl t   sk t dt ,
0
где Z - гауссовская случайная величина, математическое ожидание
которой можно найти в виде
126
nT
MZ  
nT
 sl t sl t   sk t dt Es   sk t sl t dt  1  rkl Es ,
0
0
(180)
T
1
где rkl 
sl t sk t dt .
Es

0
Найдем дисперсию корреляционного интеграла:
2
 nT
 

 
DZ   M Z  MZ 2  M  nt sl t   sk t dt   
 
 0
 




nT nT

  Mnt1 nt2 sl t1   sk t1 sl t2   sk t1 dt1dt2 
0 0
nT nT
N0

 t2  t1 sl t1   sk t1 sl t2   sk t2 dt1dt 2 
2
N
 0
2

0 0
nT
2
 sl t   sk t  dt 
0
2
N 0 d kl
2
,
(181)
nT
2
где d kl

2
 sl t   sk t  dt
- квадрат расстояния между сигналами
0
sk t  и sl t  в пространстве сигналов L 2 0, nT .
Т.о. получим
 Z  1  r E 2 
1
kl s
p Z H l  
exp 
.
2
2
N 0 d kl


N 0 d kl
(182)
Подставляя (104) в (101) получим




0
2


1  rkl E s 
1
 Z  1  rkl E s  
PDlk  
exp 
dZ

1

erf



2
2
2 
N
d



N 0 d kl
0 kl


  N 0 d kl


2


.
(183)

127
2
Учитывая, что d kl
 2 E s  2rkl E s  21  rkl E s (105) можно
переписать в виде
 d

 1  rkl E s 
  1  erf  kl  .
PDlk   1  erf 
(184)

 2N 
N0
0




При использовании ФМ-2 и двоичного n, k  кода вероятность
ошибки можно оценить следующим образом
M 1
M 1 
 d kl   M 1 



1  erf  2d min E0   
 
pl 
PDlk  
1  erf 


 2N 


N0
0   k 1 



k 1
k 1 



 2d min E0
 M  11  erf 

N0




   2 nR  1 1  erf






d min q .
(185)
информационных символов
В силу равновероятности блока
pk  pl .
На рисунке показаны результаты расчетов помехоустойчивости
двоичного когерентного приема для некоторых блоковых кодов в канале с
БГШ для случаев «мягкого» и «жесткого» декодера. Как видно по
графикам энергетический выигрыш «мягкого» декодера составляет
примерно 3Дб.
128
1
pk
Без кодирования
0.1
Код Хэмминга 7,4  ,
«жесткий» декодер
0.01
110
110
110
110
110
110
110
Код Хэмминга 7,4  ,
«мягкий» декодер
3
4
5
Код Голея 23,12  ,
«мягкий» декодер
6
7
8
9
q, dB
 10
110
0
2
4
6
8
10
Рисунок 35 – Сравнение схем «жесткого» и «мягкого» декодирования
двоичных сигналов в канале с АБГШ в условиях когерентного приема.
129
ЛЕКЦИЯ №26
2.16. МЯГКОЕ ДЕКОДИРОВАНИЕ СВЕРТОЧНЫХ КОДОВ
Использование
«мягких»
решений
может
повысить
помехоустойчивость систем связи, использующих сверточные коды. Для
прояснения ситуации рассмотрим пример.
Пример 15. Мягкое декодирование сверточного кода со скоростью
R  1 3, l  3.
Решетчатая диаграмма данного свёрточного кодера имеет вид,
показанный на рисунке 24.
Таблица 8 – Пример мягкого декодирования сверточного кода, 3-такт
работы декодера
Принятый
Состояния Евклидово
x3 t 
сигнал на
решетки
расстояние
интервале
0,9T 
Разрешенные 000 000 000 s1 t 
a
1
кодовые
111 001 011 s2 t 
2
комбинации на 000 111 001
b
s3 t 
3
3-м такте
111 110 010 s4 t 
4
111 001 100 s5 t 
c
5
000 000 111 s6 t 
6
111 110 101 s7 t 
d
7
000 111 110 s8 t 
8
Пусть демодулятор формирует значения евклидова расстояния, для
каждого сочетания символов разрешенных кодовых комбинаций на 3-м
такте
9
si t  
 a j s0 t   j  1T ,
(186)
j 1
где a1 ,...,a9 - одна из разрешенных
соответствующих строчкам таблицы.
последовательностей,
9T
i 
2

x

t


s

t


dt .
i

(187)
0
130
Декодированная последовательность определяется в соответствии со
следующим алгоритмом
iˆ  arg min i  . i  1,...,8.
(188)
i
Кажется вполне очевидным, что алгоритм Витерби также применим
в данном случае, с учетом вычисления евклидова расстояния вместо
расстояния Хэмминга.
Полученные ранее доказательства энергетической эффективности
«мягкого» способа декодирования блоковых кодов применимы и для
сверточных кодов.
2.17. КОДИРОВАННАЯ МОДУЛЯЦИЯ
Объединение процедур демодуляции и декодирования открывает
возможности для оптимизации сочетания вида цифровой модуляции и
используемого помехоустойчивого кода.
В начале 80 х гг. Унгербоек (Ungerboeck G.) опубликовал статью, в
которой, анализируя сигнальные созвездия на базе ансамбля ФМ-8 и
сверточного кода, сформулировал ряд новых правил построения
сигнально-кодовых конструкций, названных его именем, которые
оптимальны в условиях «мягкого» декодирования.
Рассмотрим цифровую модуляцию ФМ в канале с АБГШ и в
условиях когерентного приема. Вероятность ошибки в таком канале
M 1 





1  erf  d kl    M  11  erf   min   ,
(189)
 2N  
 2N  


0 
0 



k 1 
где  min - минимальное евклидово расстояние между сигналами.
Пусть имеем случай передачи ФМ-4. Созвездие вида модуляции
показано на рисунке.
Пусть  min соответствует данному случаю.
pош 

01
00
11
10
M=4
Рисунок 36 – Созвездие ФМ-4
131
Пусть мы имеем модулятор ФМ-8, который генерирует созвездия
следующего типа.
011
001
010
110
000
111
100
101
M=8
Рисунок 37 – Созвездие ФМ-8
Представим созвездие ФМ-8 комбинацией «созвездий» ФМ-2 вида
011
001
010
111
100
101
110
000
Рисунок 38 – Созвездие ФМ-8 как комбинация созвездий ФМ-2
Представим для передачи ФМ-4 комбинацию систематического
сверточного кодера со скоростью R  2 3 и модулятора ФМ-8 следующим
образом.
132
Информационный
символ a1
Информационный
символ a2
Систематически
й кодер
Проверочные
символы с1,с2
Информационный
символ с3=a2
Схема выбора
комбинации
ФМ2
Модулятор ФМ2
Выход
модулятора
Рисунок 39 – Созвездие ФМ-8 как комбинация созвездий ФМ-2
Предложенная система работает как передатчик ФМ4, однако
помехоустойчивость полученной системы выше на 3дБ.
Доказательство. На каждом такте на вход систематического кодера
поступают 2 информационных разряда a1, a2 . a1 используется для
формирования проверочных символов с1 ,с2 , которые выбирают одну из
4-х комбинаций ФМ2. a 2 используется для модуляции ФМ2. Т.о. в канал
передаются всегда сигналы ФМ2, евклидово расстояние между которыми
теперь 2 min , что дает энергетический выигрыш 3дБ.
Для модулятора ФМ8 Унгербоек нашел оптимизированные
сверточные коды, некоторые из которых показаны в таблице.
Длина
кодового
ограничения
2
3
Таблица 9 - Коды Унгербоека со скоростью R  2 3 .
Выигрыш
g1  x 
g 2 x 
g 3 x 
относительно
ФМ4, дБ
2
0
3
x
x 1
x3  1
4
x4  x  1
5
x5  x 2  1
x
x2
3.6
x2
x3  x 2  x
4.1
x3  x 2  x
x 4  x3  x 2
4.6
133
Готфрид Унгербоек (род. 15
марта 1940 года, Вена) является
австрийским ученым и инженером
в области связи. Ungerboeck
получил
степень
бакалавра
электротехники
от
Венского
технологического университета в
1964 году и степень доктора
философии
в
Швейцарском
федеральном
технологическом
институте в Цюрихе в 1970 году.
Он присоединился к IBM Austria в
качестве системного инженера в
1965 году и к исследовательской
лаборатории IBM в Цюрихе в 1967
году. В Цюрихе он работал над
системами цифровой обработки
сигналов и коммутации, теорией
коммуникации
и
информации.
Среди многих вкладов в теорию
передачи данных он изобрел
кодированную
решетчатую
модуляцию. Ungerboeck присоединился к Broadcom в 1998 году в качестве
технического директора по коммуникационной бизнес-линии.
134
СПИСОК ЛИТЕРАТУРЫ
Основная литература
1. Белов В.М. Теория информации: курс лекций: учебное пособие
для вузов. - М.: Горячая линия-Телеком, 2012. - 143 с.
2. Блейхут Р. Теория и практика кодов, контролирующих
ошибки. — М.: Мир, 1986. — 576 с.
3. Васильев К. К., Новосельцев Л. Я., Смирнов В. Н. Основы
теории помехоустойчивых кодов: Учеб. пособие. – Ульяновск:
УлГТУ, 2000. – 91с.
4. Вернер М. Основы кодирования. Учебник для ВУЗов. – М.:
Техносфера, 2004. - 288 с.
5. Духин А. А. Теория информации. – М.: Гелиос АРВ, 2007.
6. Зюко А.Г., Кловский Д.Д., Коржик В.И., Назаров М.В. Теория
электрической связи. Учебник для вузов. / Под ред. Д.Д.
Кловского. – М.: Радио и связь, 1999. – 432с.
7. Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в
примерах и задачах. Т.3: Теория информации и кодирования.
М.: МЦНМО, 2014. – 568с.
8. Кловский Д.Д. Теория электрической связи. – М.:
Радиотехника, 2009. – 648с.
9. Колесник В. Д., Полтырев Г. Ш. Курс теории информации. М.: Наука, 1982.-416 с.
10. Кудряшов Б. Д. Теория информации. Учебник для вузов. –
СПБ.: Питер, 2009.
11. Никитин Г.И. Сверточные коды. Учебное пособие / СПбГУАП.
СПб., 2001. - 80 с.
12. Панин В.В. Основы теории информации. - М.: БИНОМ, 2012.438 с.
13. Сойфер В.А. Прикладная теория информации. Учебное
пособие. Куйбышев: КуАИ, 1985. - 93 с.
14. Фурсов В.А. Лекции по теории информации: Учебное пособие
/ Под редакцией Н.А. Кузнецова. - Самара: Изд-во Самар. гос.
аэрокосм. ун-та, 2006. - 148 с.
15. Хохлов, Г. И. Основы теории информации : учеб. пособие для
студ. вузов. - М.: Академия, 2008. - 172 с.
16. Шеннон К. Работы по теории информации и кибернетике. –
М.: Изд. Иностранной Литературы. – 1963г. – 784с.
Дополнительная литература
1. Берлекэмп Э. Р. Алгебраическая теория кодирования: Пер. с
англ.-М.: Мир, 1971. - 478 с.
135
2. Бородин Л.Ф. Введение в теорию помехоустойчивого
кодирования. - М.: Советское радио, 1968, 408с.
3. Бураченко Д.Л., Клюев Н.Н., Коржик В.И., Финк Л.М. и др.
Общая теория связи. / Под ред. Л.М.Финка. – Л.: ВАС, 1970. –
412с.
4. Витерби А.Д., Омура Дж.К. Принципы цифровой связи и
кодирования: Пер. с англ./ Под ред. К.Ш. Зигангирова. - М.:
Радио и связь, 1982. - 536 с.
5. Возенкрафт
Дж.,
Рейффен
Б.
Последовательное
декодирование. Пер. с англ. Под ред. P.JI. Добрушина. М., ИЛ,
1963.
6. Габидулин
Э.М.,
Афанасьев
В.Б.
Кодирование
в
радиоэлектронике. - М.: Радио и связь, 1986. - 176 с.
7. Галлагер Р. Теория информации и надежная связь. –М. Сов.
Радио. – 1974. – 720с.
8. Гладких А.А., Климов Р.В., Чилихин Н.Ю. Методы
эффективного декодирования избыточных кодов и их
современные приложения. - Ульяновск: УлГТУ, 2016. – 258 с.
9. Гольдман С. Теория информации. Пер. с англ. М., ИЛ, 1957.
10. Гоппа В. Д. Новый класс линейных корректирующих кодов //
Пробл. передачи информ., 6:3 (1970), 24–30с.
11. Гоппа В.Д. Введение в алгебраическую теорию информации. М.: Наука, Физматлит, 1995. -112 с.
12. Золотарев В.В., Овечкин Г.В. Помехоустойчивое кодирование.
Методы и алгоритмы. Справочник. - М.: Горячая линия Телеком, 2004.-126с.
13. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М.. Теория
передачи сигналов. – М.: Радио и связь, 1986. – 304с.
14. Зяблов В.В. Шавгулидзе С.А. Обобщённые каскадные
помехоустойчивые конструкции на базе свёрточных кодов. М.: Наука, 1991. - 207 с.
15. Игнатов В. А. Теория информации и передачи сигналов:
Учебник для вузов. – М.: Радио и связь, 1991. – 280с.
16. Игнатов В.А. Теория информации и передачи сигналов.
Учебник для ВУЗов. — Москва: Советское радио, 1979. —
280с.
17. Кассами Т., Токура Н., Ивадари Е., Инагаки Я. Теория
кодирования/ Пер. с япон. под ред. Б. С. Цыбакова и С. И.
Гельфанда. – М.: Мир, 1978. – 576с.
18. Кларк Дж. мл., Кейн Дж. Кодирование с исправлением
ошибок в системах цифровой связи / Пер. с англ. под ред. Б.С.
Цыбакова. – М.: Радио и связь, 1987. – 392с.
136
19. Кловский Д.Д. Теория передачи сигналов. М., "Сов. радио",
1973.
20. Кловский Д.Д., Шилкин В. А. Теория передачи сигналов в
задачах. - М.: Связь, 1978. - 352 с.
21. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. - М.:
Наука, 1982. — 416 с.
22. Королев А.И., Конопелько В.К. Турбокоды и итеративное
декодирование. Учебно-методическое пособие. - Минск:
БГУИР, 2015. — 74 с.
23. Кульбак С. Теория информации и статистика. - M.: Наука,
1967. - 408 с.
24. Месси Дж. Пороговое декодирование. - М.: Мир, 1966.
25. Морелос-Сарагоса
Р.
Искусство
помехоустойчивого
кодирования. Методы, алгоритмы, применение. - М.:
Техносфера, 2005. - 320 с.
26. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки / Пер. с
англ. под ред. РЛ. Добрушина и С.И. Самойленко. – М.: Мир,
1976. – 596с.
27. Сагалович Ю.Л. Введение в алгебраические коды. Учебное
пособие. - 2-е изд., перераб. и доп. - М.: ИППИ РАН, 2010. 302 с.
28. Сидельников В.М. Теория кодирования. - М.: Физматлит,
2008.-300с.
29. Солодов А.В. Теория информации н ее применение к задачам
автоматического управления и контроля. М., "Наука", 1967.
30. Стратанович Р.Л. Теория информации. М.: «Сов. радио», 1975.
– 424с.
31. Теория информации и ее приложения. Под ред. А.А.
Харкевича, М., Физматгиз, 1959.
32. Фано Р. Передача информации. Статистическая теория связи:
Пер. с англ. под ред. Р. Л. Добрушина. – М.: Мир, 1965. – 438с.
33. Финк Л. М. Сигналы, помехи, ошибки... - М.: Радио и связь,
1984. - 256 с.
34. Финк Л.М. Теория передачи дискретных сообщений. - М.:
Изд-во "Советское радио", 1970. - 728с.
35. Форни Д. Каскадные коды. Пер. с англ. под ред. С.И.
Самойленко. М., "Мир", 1070.
36. Холево А.С. Введение в квантовую теорию информации.-М.:
МЦНМО, 2002 - 128с.
37. Хэмминг Р.В. Теория кодирования и теория информации: Пер.
с англ. - М.: Радио и связь, 1983. - 176с.
38. Чисар И., Кернер Я. Теория информации.- М.: Мир. 1985. 400с.
137
39. Яглом А.М., Яглом И.М. Вероятность и информация. - М.:
Изд-во "Наука", 1973. - 512с.
138
Документ
Категория
Без категории
Просмотров
0
Размер файла
6 344 Кб
Теги
posobie, teoriya, kodirovanie, informacii, goryachkin, ch2, uchebnoy
1/--страниц
Пожаловаться на содержимое документа