Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Слово «синдром» означает обычно совокупность признаков, характерных для того или иного явления. Такой же примерно смысл имеет понятие «синдром» и в теории кодирования. Синдром вектора, содержащего, быть может, ошибки, дает возможность распознать наиболее вероятный характер этих ошибок. Правда, определение, которое мы приводим ниже, не сразу позволяет это увидеть.
Синдромом вектора и называется вектор s(U), определяемый равенством:
s (и) = иНт.
Из правила перемножения матриц следует, что синдром есть вектор длины т, где т — число строк проверочной матрицы. В силу определения синдрома вектор и тогда и только тогда является кодовым (и g V), когда его синдром равен нулевому вектору. В самом деле, равенство
IlH1 = О
равносильно тому, что координаты X1, X2,... , хп вектора и удовлетворяют проверочным соотношениям (1) из § 11.
Пусть теперь вектор и не является кодовым, тогда этот вектор обязательно содержит ошибочные символы. Вектор и можно представить тогда в виде суммы посланного кодового вектора V (который пока не известен) и вектора ошибки е:
U = V +е. (1)
Ясно, что вектор е=(єь S2, ... , е„) содержит ненулевые символы в тех позициях, в которых вектор а содержит искаженные символы.
Важным обстоятельством является то, что синдромы принятого вектора и и вектора ошибки совпадают. Действительно,
S (M) = (V + е) tfT = VHt + <?ЯТ = eHr = S (е). (2)
Рассмотрим теперь множество U всех векторов и', имеющих тот же синдром, что и вектор и. Пусть а=и'—и. Тогда
S (а) == {и' — и) H1 = и'Ht— аНТ = s (и') — s (и) = 0.
Так как s(a)=0, то а — кодовый вектор. Обратно, если и'—и — кодовый вектор, то &(u')=s(u), Таким образом, для интересующего нас множества U имеем;
U = {u + a\a?V).
ei На языке теории групп это означает, что U есть смежный класс по подгруппе V (пространство Ln и его кодовое подпространство V можно рассматривать соответственно как группу и ее подгруппу относительно операции сложения векторов).
Сказанное позволяет сделать следующие выводы:
1. Два вектора имеют одинаковый синдром тогда и только тогда, когда они принадлежат одному смежному классу по кодовому подпространству. Таким образом, синдром вектора однозначно определяет тот смежный класс, которому этот вектор принадлежит.
2. Вектор ошибки едля вектора и нужно искать в силу равенства (2) в том же смежном классе, которому принадлежит и сам вектор и.
Разумеется, указание смежного класса, которому принадлежит вектор е, еще не определяет самого этого вектора. Естественно выбрать в качестве е тот вектор смежного класса, для которого вероятность совпадения с е наибольшая. Такой вектор называют лидером смежного класса. Если предположить, что большее число ошибок совершается с меньшей вероятностью, то в качестве лидера следует взять вектор наименьшего веса данного класса и в дальнейшем лидер бч^дет пониматься именно в этом смысле.
При реализации алгоритма декодирования по синдрому составляют таблицу, в которой указываются синдромы Si и лидеры Єі соответствующих им смежных классов. Алгоритм декодирования заключается тогда в следующем:
1. Вычисляем синдром S (и) принятого вектора а.
2. По синдрому S (и)=Sj определяем из таблицы лидер et соответствующего смежного класса.
3. Определяем посланный кодовый вектор V как разность
V = U-Bi.
Может случиться, что в некоторых смежных классах окажется более одного лидера. Если искаженный вектор и попал в один из таких смежных классов, то разумнее отказаться от исправления ошибки, ограничившись ее обнаружением.
При всей своей простоте и прозрачности алгоритм син-дромного декодирования обладает серьезным недостатком. Заключается он в том, что устройство, реализующее этот способ декодирования, должно хранить информацию о лидерах и синдромах. Объем же этой информации может оказаться очень большим даже при умеренных длинах кодовых слов (порядка нескольких десятков). В этом нетрудно
02 убедиться — ведь число лидеров и синдромов совпадает с числом смежных классов, которое по теореме Лагранжа равно qn : qk=qn~k. Так что, например, для двоичного (50, 40)-кода получится 1024 лидеров и столько же синдромов, а для (50,30)-кода число их превзойдет миллион.
Таким образом, мы либо придем к чрезмерному усложнению аппаратуры для синдромного декодирования, либо практически вообще не сможем ее построить. К счастью, имеются коды, декодирование которых не требует обращения к таблице лидеров и синдромов. Простейшие из них — это код Хемминга и его расширенный вариант, рассмотренные в § 9.
Как мы уже знаем, двоичный код Хемминга является линейным, в общем случае имеет длину п=2т—1, исправляет одиночные ошибки и обходится минимально возможным для этой цели числом проверок (это число равно т). Таким образом, проверочная матрица кода Хемминга имеет порядок т X (2т—1). При этом все столбцы этой матрицы должны быть ненулевыми и различными (см. § 11, задача 5). Каждый столбец есть двоичный вектор длины т; всего имеется 2т таких векторов, поэтому для построения проверочной матрицы кода Хемминга длины 2'"—1 нужно выписать (в качестве столбцов этой матрицы) все ненулевые двоичные векторы длины т. Порядок столбцов безразличен, но чаще всего их упорядочивают так, чтобы содержимое каждого столбца являлось двоичной записью его номера (сравни с матрицей (2) из § 11). Вот как выглядит проверочная матрица кода Хемминга длины 15 (т=4):
