12. ДЕКОДИРОВАНИЕ ПО СИНДРОМУ И ЕЩЕ РАЗ О КОДЕ ХЕММИНГА

Слово «синдром» означает обычно совокуп­ность признаков, характерных для того или иного явления. Такой же примерно смысл имеет понятие «синдром» и в тео­рии кодирования. Синдром вектора, содержащего, быть мо­жет, ошибки, дает возможность распознать наиболее веро­ятный характер этих ошибок. Правда, определение, кото­рое мы приводим ниже, не сразу позволяет это увидеть.

Синдромом вектора и называется вектор 5 (и), опреде­ляемый равенством:

 

 

Из правила перемножения матриц следует, что синдром есть вектор длины т, где т — число строк проверочной матри­цы. В силу определения синдрома вектор и тогда и только тогда является кодовым (и ^ V7), когда его синдром равен нулевому вектору. В самом деле, равенство равносильно тому, что координаты хх, х2, . . . ,хп вектора и удовлетворяют проверочным соотношениям (1) из § 11.

 

Рассмотрим теперь множество V всех векторов и , имею­щих тот же синдром, что и вектор и. Пусть а=и'—и. Тогда

 

Так как 5(а)=0, то а — кодовый вектор. Обратно, ес.<-и г*'—и — кодовый вектор, то 8(и')=&(и) Таким образом, "ля интрпегуюшего нас множества V имеем:

 

Пусть теперь вектор и не является кодовым, тогда это! вектор обязательно содержит ошибочные символы. Вектор и можно представить тогда в виде суммы посланного кодо­вого вектора V (который пока не известен) и вектора ошиб­ки е:

 

 

Ясно, что вектор     е2, ... , еп) содержит ненулевые символы в тех позициях, в которых вектор и содержит иска­женные символы.

Важным обстоятельством является то, что синдромы принятого вектора и и вектора ошибки совпадают. Дейст­вительно,

На языке теории групп это означает, что V есть смежней класс по подгруппе V (пространство Ьп и его кодовое под­пространство V можно рассматривать соответственно как группу и ее подгруппу относительно операции сложения векторов).

Сказанное позволяет сделать следующие выводы:

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

Вектор ошибки е для вектора и нужно искать в силу равенства (2) в том же смежном классе, которому принадле­жит и сам вектор и.

Разумеется, указание смежного класса, которому при­надлежит вектор е, еще не определяет самого этого вектора. Естественно выбрать в качестве е тот вектор смежного клас­са, для которого вероятность совпадения с е наибольшая. Такой вектор называют лидером смежного класса. Если предположить, что большее число ошибок совершается с меньшей вероятностью, то в качестве лидера следует взять вектор наименьшего веса данного класса и в дальнейшем лидер б/дет пониматься именно в этом смысле.

При реализации алгоритма декодирования по синдрому составляют таблицу, в которой указываются синдромы 5г и лидеры е* соответствующих им смежных классов. Алго­ритм декодирования заключается тогда в следующем:

Вычисляем синдром ${и) принятого вектора и.

По синдрому 5(?/)=«г определяем из таблицы лидер е« соответствующего смежного класса.

Оппеяеляем посланный кодовый вектоп я как пазность

 

 

Может случиться, что в некоторых смежных классах окажется более одного лидера. Если искаженный вектор и попал в один из таких смежных классов, то разумнее от­казаться от исправления ошибки, ограничившись ее обна­ружением.

При всей своей простоте и прозрачности алгоритм син- дромного декодирования обладает серьезным недостатком. Заключается он в том, что устройство, реализующее этот способ декодирования, должно хранить информацию о ли­дерах и синдромах. Объем же этой информации может ока­заться очень большим даже при умеренных длинах кодо­вых слов (порядка нескольких десятков). В этом нетрудноубедиться — ведь число лидеров и синдромов совпадает с числом смежных классов, которое по теореме Лагранжа равно цп : цк=цп~к. Так что, например, для двоичного (50, 40)-кода получится 1024 лидеров и столько же синдро­мов, а для (50,30)-кода число их превзойдет миллион.

Таким образом, мы либо придем к чрезмерному усложне­нию аппаратуры для синдромного декодирования, либо практически вообще не сможем ее построить. К счастью, имеются коды, декодирование которых не требует обраще­ния к таблице лидеров и синдромов. Простейшие из них — это код Хемминга и его расширенный вариант, рассмотрен­ные в § 9.

Как мы уже знаем, двоичный код Хемминга является линейным, в общем случае имеет длину п=2т—I, исправ­ляет одиночные ошибки и обходится минимально возмож­ным для этой цели числом проверок (это число равно т). Таким образом, проверочная матрица кода Хемминга имеет порядок тХ(2т—1). При этом все столбцы этой матрицы должны быть ненулевыми и различными (см. §11, задача 5). Каждый столбец есть двоичный вектор длины т\ всего име­ется 2т таких векторов, поэтому для построения провероч­ной матрицы кода Хемминга длины 2т—1 нужно выписать (в качестве столбцов этой матрицы) все ненулевые двоичные векторы длины т. Порядок столбцов безразличен, но чаще всего их упорядочивают так, чтобы содержимое каждого столбца являлось двоичной записью его номера (сравни с матрицей (2) из § 11). Вот как выглядит проверочная мат­рица кода Хемминга длины 15 (т=4):

 

 

Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор и содержит ошибочный символ в 1-й позиции, то синдром 8(и) этого вектора совпа­дает с 1-м столбцом проверочной матрицы, Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.

Код Хемминга и в общем случае допускает усовершенст­вование того же рода, что и (7,4)-код из § 9. Добавление проверочного символа а0, осуществляющего общую провер­ку на четность, приводит, как и там, к расширенному коду Хемминга с дополнительной способностью обнаруживать двойные ошибки. Его проверочная матрица легко может быть получена из матрицы кода Хемминга: к каждой строке последней следует впереди приписать нулевой символ, а к получившимся строкам — строку из единиц, соответст­вующую общей проверке на четность:

 

 

Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая про­верочная матрица для расширенного (16,11)-кода:

 

 

При вычислении синдрома искаженного вектора возмож­ны две основные ситуации: либо синдром совпадает с одним из столбцов проверочной матрицы, либо это не так. Чита­тель легко проверит, что первая ситуация соответствует нечетному числу ошибок в слове, а вторая — четному.

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

Во втором случае считаем, что допущены две или любое большее четное число ошибок, если 5 (и) 0. Если же з(и)=0, то, как обычно, полагаем, что ошибок при передаче не было.

Задачи и дополнения

5. Построить таблицу синдромов и соответствующих лилепов лля С7..Т)-коля с попожпаюшей матпипей

 

2. Доказать, что алгоритм синдромного декодирования позволяет исправить любое количество ошибок, не превосходящее ^ 2 ^, где

 

а -—кодовое расстояние.

Указание. Достаточно проверить, что все векторы веса ^ ^

и меньше попадают в различные смежные классы и, следовательно, явля­ются лидерами в своих смежных классах,

3. Код с проверочной матрицей

 

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

4. Проверить, что для обычного (нерасширенного) кода Хемминга лидеры ненулевых смежных классов исчерпываются всеми векторами веса 1. Верно ли это для расширенного кода Хемминга?