Файл: прикладная теория информации.pdf

166
Имеем [8, 4, 4, ]-код. В общем случае кодовое расстояние РМ – кода первого порядка равно ???? = ???? ∕ 2. Код Рида – Маллера первого порядка задается порождающей матрицей ????, первая строка которой состоит из ???? единиц. В каче- стве столбцов остальных ???? строк используются все двоичные числа длиной ????.
Порождающая матрица РМ-кода первого порядка при ???? = 3 имеет вид
???? = [
????
0
????
1
????
2
????
3
] ⟺ [
1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1
]. (9.11)
Векторы ????
0
, ????
1
, ????
2
, ????
3
линейно независимы.
Пример 9 .6 . Записать матрицу ???? РМ-кода второго порядка для ???? = 3.
Решение. Код характеризуется следующими параметрами:
1)
???? = 8;
2)
???? = 1 + ∑
????
3
????
2
????=1
= 1 + ????
3 1
+????
3 2
= 1 + 3 + 3 = 7;
3)
???? = 2
????−????
= 2.
Порождающая матрица [8, 7, 2] РМ-кода 2-го порядка имеет вид
???? =
[
????
0
????
1
????
2
????
3
????
4
= ????
1
∙ ????
2
????
5
= ????
1
∙ ????
3
????
6
= ????
2
∙ ????
3
]
⟺
[
1 1 1 1 1 1 1 1 0
1 0 1 0 1 0 1 0
0 1 1 0 0 1 1 0
0 0 0 1 1 1 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 1 1]
Пример 9.7 . Закодировать сообщение ???? = (1001) несистематическим
[8, 4, 4] РМ-кодом.
Решение. Кодовое слово ???? = ???????? = (1 1 1 1 0000).
Пример 9 .8 . Закодировать сообщение ???? = (1001) систематическим
[8, 4, 4] РМ-кодом.
Решение. Получим порождающую матрицу. Для этого:
– просуммируем все строки матрицы (9.11) и запишем суммарный вектор вместо 1-й строки матрицы (9.11). В результате получим матрицу
[
1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1
] ;(9.12)
– переставим столбцы единичного веса матрицы (9.12), приведя их к еди- ничной матрице:

167
????
8,4
= [????
????
|????
∗
] = [
1 0 0 0 1 1 1 0 0
1 0 0 1 1 0 1 0
0 1 0 1 0 1 1 0
0 0 1 0 1 1 1
]. (9.13
Проверочная матрица систематического [8, 4, 4] РМ-кода имеет вид:
????
8,4
= [????
∗????
|????
????
] = [
1 1 1 0 1 0 0 0
1 1 0 1 0 1 0 0
1 0 1 1 0 0 1 0
0 1 1 1 0 0 0 1
]. (9.14)
Из (9.14) запишем уравнения для вычисления проверочных символов:
????
4
= ????
0
+ ????
1
+ ????
2
,
????
5
= ????
0
+ ????
1
+ ????
3
,
????
6
= ????
0
+ ????
2
+ ????
3
,
????
7
= ????
1
+ ????
2
+ ????
3
Кодовое слово, соответствующее сообщению ???? = (1001), есть
???? = (10011001).
Пример 9 .9 . Удовлетворяют ли матрицы канонического вида ???? (9.13) и
???? (9.14) основному уравнению кодирования?
Решение. Для ответа на этот вопрос найдем произведение матриц ???? и ????
????
:
[
1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 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 0 0
0 1 0 0
0 0 1]
= [
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
].
Матрицы удовлетворяют основному уравнению кодирования.

168
– длина 2
????
− 1, ???? = 2, 3, … ;
– размерность ???? = 2
????
− 1 − ????;
– кодовое расcтояние ???? = 3;
– распределение лидеров смежных классов веса ????
????=0
= 1, ????
????=1
= ????.
В табл. 9.2 приведены значения некоторых параметров кодов Хэмминга.
Таблица 9.2
Параметры кодов Хэмминга
????
3 4
5 6
7 8
????
7 15 31 63 127 255
????
4 11 26 57 120 247
9.6.1. Формы представления проверочной матрицы кода Хэмминга
Выделяют следующие формы представления проверочной матрицы кода
Хэмминга:
1. Классическая форма (несистематический код Хэмминга).
В матрице ???? каждый i -й столбец равен двоичному представлению числа
???? ∈ {1, 2, … , ????}. Например, матрица [7, 4, 3]-кода Хэмминга имеет вид
???? = [
1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1
]. (9.15)
2. Систематическая форма матрицы ???? кода Хэмминга.
Например, матрица[7, 4, 3]-кода Хэмминга имеет вид
???? = [
1 1 0 1 1 0 0
1 0 1 1 0 1 0
0 1 1 1 0 0 1
].
Из этой матрицы легко можно получить порождающую матрицу
[7, 4, 3]-кода Хэмминга:
???? = [
1 0 0 0 1 1 0 0
1 0 0 1 0 1 0
0 1 0 0 1 1 0
0 0 1 1 1 1
].
9.6.2. Задание проверочной матрицы кода Хэмминга с помощью
элементов расширенного поля Галуа ????????(2
????
)
Если α

примитивный элемент поля
????????(2
????
), то все элементы различны и представляются ненулевыми двоичными векторами. Это свойство используется для построения проверочной матрицы кода Хэмминга в форме

169
???? = [1 α α
2
. . . α
2
????
−2
].
Пример 9 .10 . Пусть α ∈ ????????(2 3
) – корень уравнения α
3
+ α + 1 = 0. То- гда проверочная матрица будет иметь вид
???? = [1 α α
2
α
3
α
4
α
5
α
6
].
Все элементы поля могут быть представлены как различные ненулевые двоичные m-векторы. Проверочная матрица в виде векторов двоичного
[7, 3, 4]-кода Хэмминга записывается как
1 α α
2
α
3
α
4
α
5
α
6
???? = [
1 0 0 1 0 1 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
].
9.7. Совершенные и квазисовершенные коды
Определение 9.4. Код, исправляющий все конфигурации ошибок веса не более ????, называется совершенным.
Для такого кода нет ни одной конфигурации ошибок веса большего, чем кратность исправляемых. Для совершенного кода число лидеров смежных клас- сов веса ???? равно ????
????
= 0 при условии
???? > ???? = ⌈
???? − 1 2
⌉.
Определение 9.5. Если число лидеров смежных классов веса веса ???? равно
????
????
= 0 при условии
???? > ???? + 1, то код называется квазисовершенным.
Квазисовершенный код может исправлять:
– все ошибки веса не более ????;
– некоторые ошибки веса ???? + 1.
Квазисовершенный код не может исправлять ни одной ошибки веса больше, чем ???? + 1.
Теорема 9.1. Коды Хэмминга являются совершенными кодами.
9.8. Вычисление минимального веса кода по проверочной матрице

170
кода
Теорема 3.2. Блоковый код с порождающей матрицей???? имеет минималь- ный вес min wt(????), и, следовательно, кодовое расстояние
???? = min wt(????), ???? ∈ ????
тогда и только тогда, когда любые ???? − 1 столбцов матрицы????будут линейно не- зависимы, но найдутся ???? линейно зависимых столбцов.
Пример. 9 .11 . Пусть основному уравнению кодирования (9.2) соответ- ствуют матрицы
???? = [
1 0 0 1 0 0 1 0 1 1 0 0 1 1 1
] и ???? = [
1 1 1 1 0 0
1 1 0 1
].
Очевидно, имеются совокупности, состоящие из 2-х линейно зависимых столбцов матрицы ????. Отсюда, min wt(????) = 2, ???? = 2. Все множество {????} ненуле- вых кодовых слов кода [5, 3, 2]-кода представляется в виде
????
+
=
(
1 0 0 1 0
0 1 0 1 1
0 0 1 1 1
1 1 0 0 1
1 0 1 0 1
0 1 1 0 0)
9.9. Задания для самостоятельного выполнения
1. Построить в канонической форме матрицы
???? и ???? кода с проверкой на четность [????, (???? − 1), 2], ???? = 8.
2. Показать, что матрицы
???? и ????
′
порождают эквивалентные коды
???? = [
1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
] , ????
′
= [
1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1
].
3. Построить канонические матрицы
???? и ???? кода с повторением [????, 1, ????], ???? =
6.
4. Построить порождающую
???? и проверочную ???? матрицы линейного груп- пового кода с параметрами [6, 3, 3].
5. Используя порождающую матрицу
???? (п. 4) кода, записать все слова кода.

171
10. МЕТОДЫ ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ КОДОВ
Известны и применяются четыре основных метода декодирования:
1. Декодирование по синдрому.
2. Декодирование на основе принципа максимального правдоподобия.
3. Спектральное декодирование.
4. Мажоритарное декодирование, или декодирование по большинству про- верок.
Первый и четвертый методы применяются для коррекции независимых, модульных и пакетных ошибок кратностью ???? равной 1 – 4 . Второй и четвертый методы декодирования используются, как правило, в радиоэлектронных систе- мах, работающих при низких отношениях сигнал/помеха на входе декодера, сложной помеховой обстановке.
10.1. Декодирование кода на основе принципа максимального правдо-
подобия
Определение 10.1. Декодирование кода на основе вычисления вектора ошибки ????с наименьшим весом называется декодированием на основе принципа максимального правдоподобия, или декодированием в ближайшее кодовое слово.
10.1.1. Декодирование кода по таблице смежных классов
Если на вход декодера поступил вектор
???? = (????
????
+ ????), ???? ∈ ????, то он должен принадлежать некоторому смежному классу (????
????
+ ????). Если было передано кодовое слово ????
′
, то вектор ошибок ???? равен
???? = ???? − ????
′
= (????
????
+ ???? − ????
′
) = (????
????
+ ????
′′
), ????
′′
∈ ????. (10.1)
Из (10.1) следует, что возможными векторами ошибок
???? = (????
????
+ ????
′′
) ∈ (????
????
+ ????) являются все векторы из смежного класса, содержащего ????.
Стратегия декодирования кодов будет следующей:
– необходимо выбрать из смежного класса, содержащего ????, вектор ???? с наименьшим весом;
– декодировать ???? как ???? = ???? − ????.
Замечания:

172 1. Вектор из смежного класса, имеющий минимальный вес, называется лидером смежного класса. Лидер смежного класса есть вектор ошибок ????.
2. Если имеется более одного вектора с минимальным весом, то в качестве лидера смежных классов выбирается любой из таких векторов.
3. В формуле (10.1) лидерами смежных классов являются векторы ????
????
Пример 10.1 . Декодировать входной вектор ???? = [0110] по табл. 8.9.
Решение. Вектор [0110] принадлежит смежному классу – второй строке табл. 8.9. Этому классу соответствует лидер смежного класса ???? = [1000]. Тогда переданным кодовым словом является
????
????
= ????
????
− ????
????
= [
0 1
1 0
] − [
1 0
0 0
] = [
1 1
1 0
].
Из табл. 8.9 также видно, что векторы [0100] и [0001] принадлежат одному и тому же смежному классу (третья строка табл. 8.9) поскольку их разность
[
0 1
0 0
] − [
0 0
0 1
] = [
0 1
0 1
] = ????
2
∈ ???? есть кодовый вектор кода. Если рассматривать эти векторы в качестве векторов ошибок, то соответствующие им конфигурации ошибок (с минимальным одина- ковым весом) не могут быть исправленными. Обе конфигурации можно выбрать в качестве лидеров своего смежного класса. Ввиду неоднозначного определения лидера смежного класса невозможно исправление ошибок этих конфигураций.
О корректирующей способности рассмотренного кода говорят, что он исправ- ляет не все ошибки веса 1, а только однократные определенной конфигурации.
Это справедливо во всех случаях, когда используются кодовые слова веса 2. По- скольку только минимальный вес minwt(????) = ???? = 3 является необходимым и достаточным условием для исправления всех конфигураций одиночных ошибок.
10.2. Декодирование по синдрому
Определение 10.2. Вектор ???? = ????????
????
называется синдромом вектора
????, где ????
– вектор на входе декодера.
Свойства синдрома:
1. Синдром ???? представляет собой вектор-столбец размером (???? − ????) × 1.
2. Cиндром
???? равен нулю, если и только если ???? – кодовое слово кода.
Пусть ???? = ???? + ????, где ???? ∈ ????, тогда
???? = ????????
????
= ????(???? + ????)
????
= ????????
????
+ ????????
????
= ????????
????
. (10.2)

173 3. Если в кодовом слове имеются ошибки на позициях с номерами ????, ????, ????, … так, что ???? = [0 … 1
⏞
????
… 1
⏞
????
00 … 1
⏞
????
… 00], то из (10.2) получаем, что
???? = ∑ ????
????
????
????
= ????????
????
+
????
????????
????
+ ????????
????
+ ⋯, где ????
????
– это i-й столбец матрицы
????.
Вычисление синдрома можно рассматривать как линейное преобразование вектора ошибок. В качестве ядра преобразования выступает матрица ????.
Теорема 10.1. Для двоичного кода синдром равен сумме тех столбцов мат- рицы ????, где произошли ошибки.
Замечание. Вектор ???? называется синдромом, т. к. выделяет совокупность ошибок. Синдром кодового слова является индикатором вектора ошибок.
Теорема 4.2. Имеется взаимно однозначное соответствие между синдро- мами и смежными классами, а именно: два вектора находятся в одном и том же смежном классе кода ????, если и только если имеют один и тот же синдром ????.
Ранее (см. теорему 8.8) было показано, что если векторы ????и ???? находятся в одном смежном классе, то разность этих векторов всегда дает вектор принадле- жащий коду, т. е.
???? − ???? = ???? ∈ ????.
Умножая (слева) это равенство на транспонированную проверочную мат- рицу кода ????
????
и используя основное уравнение кодирования
????
????
???? = ????, можно за- писать
????
????
(???? − ????) = ????
????
???? = ???? = ????,
????
????
???? = ????
????
???? = ????.
Пусть имеется код мощностью ???? = ????
????
. Кодовые слова множества
{????} = {????
1
, ????
2
, … , ????
????
} передаются по каналу с шумами. На вход декодера поступает множество векто- ров
{
????} = {???? + ????}.
Таблица стандартного расположения для кода {????} вместе со столбцом син- дромов будет иметь вид, представленный в табл. 10.1.

174
Таблица 10.1
Таблица стандартного расположения для кода
????
1
…
????
????
…
????
????
????
0
????
1
+
????
1
…
????
1
+ ????
????
…
????
1
+
????
????
????
1
⋮
⋮
⋮
⋮
⋮
⋮
????
????
+
????
1
…
????
????
+ ????
????
…
????
????
+
????
????
????
????
⋮
⋮
⋮
⋮
⋮
⋮
????
????
+
????
1
…
????
????
+ ????
????
…
????
????
+
????
????
????
????
В табл. 10.1 обозначены:
– ????
1
и
????
????
– векторы соответственно однократных и t-кратных ошибок;
– ????
1
и
????
????
– синдромы соответственно однократных и t-кратных ошибок.
Если принимаются векторы одного смежного класса, т. е.
????
????
= ????
????
+ ????
????
и
????
????
= ????
????
+ ????
????
, то соответствующие им синдромы, равны
????
????
????
= ????????
????
????
= ????(????
????
+ ????
????
)
????
= ????????
????
????
+ ????????
????
????
= ????????
????
????
,
????
????
????
= ????????
????
????
= ????(????
????
+ ????
????
)
????
= ????????
????
????
+ ????????
????
????
= ????????
????
????
Таким образом, ????
????
????
= ????
????
????
Пример 10 .2 . Найти соответствие между синдромами и смежными клас- сами [4, 2, 2]-кода (см. пример 10.1). После вычисления синдромов, таблица стан- дартного расположения для кода примет вид, представленный в табл. 10.2.
Таблица 10.2
Таблица стандартного расположения для кода к примеру 10.2
Алгоритм декодирования по синдрому состоит в следующем:
1. Синдром определяет, в каком смежном классе находится принятый вектор ????.
0000 1011 0101 1110
????
0
= [
0 0
]
1000 0011 1101 0110
????
1
= [
1 1
]
0100 1111 0001 1010
????
2
= [
0 1
]
0010 1001 0111 1100
????
3
= [
1 0
]

175 2. Зная смежный класс, определяется вектор ошибок
????.
3. Определяется искомое кодовое слово.
4. Определяется передаваемое сообщение.
Алгоритм декодирования включает в себя выполнение следующих опера- ций:
1)
????
????
????
= ????????
????
????
;
2)
????
????
????
→ ????
????
(лидер смежного класса);
3)
????
????
= ????
????
− ????
????
;
4)
????
????
→ ????
????
(сообщение).
По второму свойству 2синдрома декодирование состоит в сравнении син- дромов с нулем. Для этого: а) вычисляются проверочные символы, используя принятые информацион- ные; б) сравниваются полученные проверочные символы с принятыми провероч- ными.
Замечание. Следствием а) является то, что синдромный декодер содержит кодирующее устройство.
Вывод. Если в качестве образующих смежных классов выбраны векторы, имеющие минимальный вес в своем смежном классе, то декодирование по син- дрому совпадает с декодированием по минимуму расстояния Хэмминга. В этом случае обеспечивается минимальная вероятность ошибки декодирования в ДСК.
Пример 10 .3 . Задан код ???? = [
1 0 0 1 0 1
0 1 0 1 1 0
0 0 1 0 1 1
]. На вход декодера поступил вектор ???? = ???? + ???? = [1 0 1 1 0 1]. Выполнить синдромное декодирова- ние входного процесса.
Решение. По формуле (10.2) вычисляем синдром.
s = Hy
T
= He
T
= [
1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1
][1 0 1 1 0 1]
T
= [0 1 1]
T
По теореме 10.1 синдром равен сумме тех столбцов матрицы ????, где про- изошли ошибки. Вектор ???? = [0 1 1 ]
????
находится в третьем столбце матрицы
????.
Вектор ошибок из (10.2) равен ???? = [0 0 1 0 0 0]
????
. По каналу передавалось кодо- вое слово
???? = y − ???? = (1 0 0 1 0 1).
Этому слову соответствует сообщение ???? → ???? = (100).