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

1.2. Линейные коды

В кодах, содержащих несколько информационных и несколько проверочных символов, каждый проверочный символ является некоторой функцией от информационных символов. В простейшем случае кода с одной проверкой на четность единственный проверочный символ является двоичной суммой всех информационных символов. Если имеется несколько проверочных символов, то для задания кода представляется целесообразным каждый из них определить как двоичную сумму соответствующего подмножества информационных символов. Построим, например, двоичный код с блоковой длиной п = 6, имеющий А; = 3 информационных символов и г = 3 проверочных символов. Обозначим через С, и Сд информационные символы, а через С, и - проверочные символы, где

С4 = Cj 2»

или в матричных обозначениях

Полное кодовое слово содержит символы Сц С, С3, удовлетворяющие проверочным уравнениям

с, + с, + С, = о,

с, +Сз +С, =0,

с, + с, +с, = о,

или в матричной записи

Е, =

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

С = [Ci, С2, Cg, С4, С5, Cg], О - нулевой вектор-столбец длины три, а - проверочная матрица

Г1 1 О 1 О 0-10 10 10 ,011001.

2 = 8 кодовых слов, очевидно, исчерпываются последовательностями 000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000.

После того как информационная последовательность закодирована в полное кодовое слово, оно передается по зашумленному каналу. Канал прибавляет к кодовому слову шумовое слово )

Е = 1Е„ Е„ Е„ Е„ Е„ Е,],

0, если канал не изменяет i-то символа,

1, если канал изменяет t-й символ. Полученное слово описывается последовательностью

R = i?2> -4) Jsi Jel, где Ri = Cfi- Ei, или в векторной записи R = С -f Е. Декодер начинает с вычисления символов синдрома, определяемого уравнением

Для данного примера это уравнение имеет вид

sj-j Г1 1 О 1 О ОТ

82 = 10 10 10

.8з J Lo 1 1 О О 1

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

Для того чтобы декодировать, декодер должен в конце концов ответить на вопрос: «Какое слово С передавалось?» Легче, однако, оказывается, ответить сначала на промежуточный вопрос: «Каков вектор Е ошибок, происшедших в канале?» Если декодер сможет правильно определить вектор ошибок Е, то С может быть найдено по формуле С = R - Е. (Б двоичном случае, конечно, + = -, разность равна сумме и С = R - Е означает, что С = R + Е.)

Если R - полученное слово, то множество возможных векторов ошибок в точности совпадает с множеством векторов, имеющих тот

) Мы используем термины «слово» и «вектор» в одном и том же смысле.

же синдром, что и R. Действительно, если МЯ <ШЕ, то Ф?? (R - Е) О, так что R - Е не является переданным кодовым словом. Наоборот, если S6R = <й?Е, то d? (R - Е)= О, и вектор ошибок может совпадать с Е, если передавалось слово С = R -• Е.

Предположим, например, что принятое слово является кодовым. Тогда SSB. = О VL <E =0, так что вектор ошибок также должен быть кодовым словом.

Множество п-мерных двоичных векторов с нулевым синдромом в точности совпадает с множеством кодовых слов. Если х и у - два кодовых слова, то J5?x = iy = О, так что J5?x - dy = О и X - у - также кодовое слово. Таким образом, разность любой пары кодовых слов является кодовым словом. Поэтому говорят, что множество кодовых слов образует линейный код, или групповой код В общем случае, если х и у имеют один и тот же синдром (не обязательно нулевой), то SSx = djy, (х - у) = О, и х - у является кодовым словом. Множество всех векторов, имеющих один и тот же синдром, называется смежным классом по подгруппе кодовых слов. Как только что показано, разность между любыми двумя векторами из одного и того же смежного класса является кодовым словом. Обратно, сумма некоторого вектора х и любого кодового слова лежит в том же смежном классе, что и х. Следовательно, число векторов в любом смежном" классе равно числу 2 кодовых слов. Возможными векторами ошибок являются слова из того смежного класса, которому принадлежит полученное слово.

Таким образом, декодер может сразу исключить из рассмотрения все векторы ошибок, которые не лежат в одном смежном классе с принятым словом, т. е. векторы, которые имеют другие синдромы. Однако все векторы ошибок, лежащие в одном смежном классе с принятым словом, возможны. Ни одна из этих возможностей не может быть с полной определенностью исключена из рассмотрения. Но так как ошибки в канале относительно редки, то некоторые из векторов ошибок в пределах данного смежного класса гораздо менее вероятны, чем другие. Обычно более вероятно, что вектором ошибок будет вектор с малым числом единиц, чем вектор с большим числом единиц. Более точно, определим вес некоторого га-мерного двоичного вектора как число единиц в данном векторе. Вектор наименьшего веса в пределах данного смежного класса выберем в качестве лидера смежного класса.

Наиболее вероятный вектор ошибок - это лидер смежного класса, содержащего принятое слово.

Смежные классы для рассмотренного выше примера выписаны в виде строк таблицы 1.1. Первая строка есть смежный класс с нуле-

Таблица 1.1

Стандартное расположение по Слепяну

) В недвоичном случае не всякий групповой код является линейным.- Прим. перев.

Синдром

Слова

вым синдромом, т. е. множество кодовых слов. Лидер каждого из последующих смежных классов выписан в первом столбце. Элемент, расположенный в i-й строке и /-м столбце, равен сумме у-го кодового слова и г-го лидера.

Обычно используется терминология определений 1.21.

1.21. Определения. Код называется линейным или групповым ), если он состоит из всех векторов С, удовлетворяющих уравнению dJC = О, Матрица S6 называется проверочной матрицей. Блоковая длина п кода равна числу столбцов матрицы SB. Синдром s любого слова R определяется уравнением s = dR. Смежный класс состоит из всех слов с одним и тем же синдромом. Весом слова называется число его единичных координат. Слово наименьшего веса в данном смежном классе называется его лидером.

Важные свойства линейных кодов дает следующая теорема:

1.22. Теорема. Если R - принятое слово, то множество возможных векторов ошибок совпадает со смежным классом, содержащим R. Наиболее вероятным вектором ошибок является лидер этого смежного класса. Линейный код может быть декодирован следующим образом: вычисляем синдром, находим лидер смежного класса, которому соответствует этот синдром, и, вычитая найденный лидер из принятого слова, получаем наиболее вероятное кодовое слово.

Сразу возникают две основные задачи: (1) как надо выбирать матрицу сШ и (2) как по заданному синдрому находить лидер смежного класса?

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

См. примечание на стр. 16.-Прим. ред.

2-656

МЫ в общем случае не решены. Однако известно много «хороших» методов построения проверочных матриц и выбора лидеров смежных классов по заданному синдрому. В последующих главах книги мы приведем наиболее перспективные из этих методов.

Самыми простыми примерами линейных кодов являются коды с повторением и коды с одной проверкой на четность, описанные в разд. 1.1. Проверочная матрица кода с одной проверкой имеет вид

= [1 1 1 ... 1],

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

-1 1 О О От 10 10 0 10 0 10

Li О О О и

1.3. Коды Хэмминга )

При очень малых или очень больших скоростях хорошие линейные коды строятся сравнительно легко. Интерполяцию между этими крайними случаями можно проводить одним из двух способов: (1) отталкиваясь от кодов с низкой скоростью передачи, постепенно увеличивать к, добавляя все новые и новые кодовые слова и пытаясь сохранить большие корректирующие возможности кода; (2) отталкиваясь от хороших кодов с большой скоростью передачи, постепенно увеличивать корректирующие возможности кода, пытаясь добавлять лишь малое число дополнительных проверочных ограничений. Исторически второй метод оказался более успешным. Мы также пойдем по этому пути. Начнем с построения одного специального класса кодов, исправляющих одиночные ошибки,- кодов Хэмминга.

Синдром линейного кода связан с вектором ошибок уравнением s = JE. Правая часть этого уравнения может быть записана в виде суммы, содержащей раз первый столбец матрицы J, Е раз второй столбец матрицы (Ш, Eg раз третий столбец матрицы сШ, ... . Например, если

110 10 0-10 10 10 0 110 0 1

[El, Ez, Es, Ei, Ef, E],

1 Bee совершенные двоичные коды с исправлением одиночных ошибок были построены Хэммингом. Код Хэмминга с длиной 7 был впервые опубликован в качестве примера в статье Шеннона [1948]. Еще до появления работы Хэмминга [1950] этот пример был обобщен Голеем [1949]. Коды Хэмминга в ином контексте содержатся в работе Фишера [1942].

Таким образом, синдром является суммой тех столбцов матрицы которым соответствуют ошибки в канале связи. Если некоторый столбец матрицы нулевой, то ошибка в этой позиции не окажет на синдром никакого влияния. Код не позволяет даже обнаружить ошибку в такой позиции. Если два столбца матрицы S6 совпадают, то одиночные ошибки в каждой из этих позиций дают один и тот же синдром, т. е. векторы этих одиночных ошибок лежат в одном смежном классе. Так как только один из них можно выбрать в качестве лидера смежного класса, то только одна из ошибок может быть исправлена. Другая одиночная ошибка будет декодирована неправильно. Таким образом, если SB содержит нулевые или совпадающие между собой столбцы, то соответствующий линейный код не позволяет исправлять все одиночные искажения в канале.

Наоборот, предположим, что все столбцы матрицы Si отличны от нулевого и друг от друга. Тогда одиночная ошибка в одной произвольной позиции приводит к синдрому, отличному от синдрома для ошибки в любой другой позиции. Каждый вектор одиночной ошибки является лидером смежного класса, и код позволяет исправлять все одиночные ошибки.

1.31. Теорема. Линейный код позволяет исправлять все одиночные ошибки тогда и только тогда, когда все столбцы его матрицы Si отличны от нуля и друг от друга.

Для декодирования одиночных ошибок декодер вычисляет синдром полученного слова. Если синдром равен нулю, то декодер полагает, что ошибок не произошло. Если синдром отличен от нуля и равен некоторому столбцу матрицы Si, то декодер полагает, что произошла ошибка в соответствующей позиции. Если синдром оказывается ненулевым и отличным от любого столбца матрицы «й?, то фиксируется отказ от декодирования. Отказ или ошибка декодирования происходят только в том случае, когда в канале искажаются два или более символов. Например, предположим, что

гО О О 1 1 1 1 1 От 0 0 1110 10 1 0 1110 0 110 L1 1 1 О О О 1 О iJ