Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
,68 ходам значительно упрощены; более того, для циклических кодов существуют свои особые методы декодирования, не-приложимые к другим линейным кодам. Наконец, по своей структуре эти коды идеально приспособлены к реализации в современных технических устройствах.
Простые в реализации, они, однако, не столь просты в теории. Для полного разъяснения большинства вопросов, связанных с построением и методами декодирования циклических кодов, требуется довольно сложный алгебраический аппарат. Поэтому наше предстоящее знакомство с циклическими кодами будет далеко не полным.
Начнем с понятия циклического сдвига вектора. Пусть задан произвольный «-мерный єектор а=(а0> Ci1, а2, . .., ап~і) с координатами из любого поля F (нумерацию координат в случае циклических кодов удобно начинать с нуля). Циклическим сдвигом этого вектора назовем вектор а'=* = (ап-ь cf-o, Ci1, а2, . . . , а„_2). Например, для вектора (01101) последовательными циклическими сдвигами являются такие вектора:
Циклическим кодом называется линейный код, который вместе с любым своим вектором содержит также и его циклический сдвиг. Иными словами, циклический код обладает следующим свойством: циклический сдвиг любого кодового вектора снова является кодовым вектором.
Циклическим является, например, код с порождающей матрицей
Менее тривиальным примером циклического кода (проверка предоставляется читателю) является код, эквивалентный (7,4)-коду Хемминга, с проверочной матрицей
При рассмотрении циклических кодов кроме обычных действий над векторами мы имеем дело фактически еще с одной операцией, сопоставляющей каждому вектору его циклический сдвиг. Удобным алгебраическим средством для ее описания являются многочлены. С каждым вектором а= —(а0, oi, . . . , ап-і) свяжем многочлен а(х)=а0+а1х+. . . I-+<2,i-і*™-1, коэффициенты которого совпадают с соответ-
(10110), (01011), (10101), (11010).
(О
,69 ствующими координатами вектора. В дальнейшем будем отождествлять вектор а с соответствующим ему многочленом а(х), свободно переходя от векторной записи к записи в виде многочлена. Циклическому сдвигу a' = (an_i, а0, аи , а„_ 2) вектора а соответствует тогда многочлен а'(х)~ = ап_1+аоХ+а1х2+. . .+ап_1хп~1. Сравним многочлены а(х) и а'(х). Если сумму первых п—1 слагаемых а(х) умножить на X, мы получим сумму последних п—1 слагаемых многочлена а'(х). Вообще, нетрудно заметить, что
а'(х) = ха(х)~ап_1(х"-\). (2)
Будем теперь считать, что х — образующий элемент циклической группы порядка п. Тогда /2-я степень х равна единице:
xn=l, (3)
а все меньшие степени, 1, х, х2, ... , х"-1, являются различными элементами. При этом правило умножения степеней х следующее:
xkxm = хг, (4)
где r = k+m (mod п) и 0 =^r < л. С учетом (3) равенство (2) дает:
а'(х) = ха(х),
т. е. циклический сдвиг любого вектора получается умножением этого вектора на х.
Из равенств (3) и (4) вытекает следующее правило умножения любых двух многочленов от л: степени — 1. Если
а (х) = ?0 + O1X + ... + A^1X"-1
и
b(x) = b0 + blX+ ...+Ь^х»'*
— два таких многочлена, то чтобы найти их произведение, сначала обычным образом раскрываем скобки, умножая степени Xk и хт по правилу (4), а коэффициенты ak и Ьт — по правилу умножения в поле F1 после чего приводим подобные члены.
Пример 1. Пусть п=Ъ и a(x) = l+x+x2.+xi и Ь(х) = \+х3+х*— двоичные многочлены. Тогда
а (х)Ь (х) = (1 +х+х»+х*)( 1 +X3+Xі) =
— 1 +х+х2+хі+х3+хх3+х2х3+хіх3+хі'+хх'к+х2хі+хіхі -
= 1 +х+х2.+х*+х3+х*+1 +X2.+Xі+! +х+х3=1 +х*.
,70 Пример 2. Пусть п=4, а(х) = 1+2х+хг- и Ь(х)=¦ =2+х+х3 — многочлены над полем Z3. Имеем:
а (х)Ь (х) = (1 +2х+хг)(2+х+х3) =
=2+2-2х+2х?+х+2хг+;е3+х3+2;и:3+л;2А'3=
=2+л:+2Л:2+Л:+2Л:*+2Л;3+2+Л:= 1 +X?+2JC3.
Итак, для многочленов кроме операции сложения определена также и операция умножения (напомним, что сложение многочленов не нуждалось в специальном определении, поскольку многочлены понимаются нами как векторы). При этом, очевидно, операция умножения многочленов коммутативна, ассоциативна и дистрибутивна относительно операции сложения. Поэтому множество Fn всех многочленов степени ^n образует относительно указанных операций кольцо. Но тогда циклический код может быть описан в чисто алгебраических терминах следующим образом:
Линейный код V является циклическим тогда и только тогда, когда V является идеалом в кольце Fn.
В самом деле, если V — идеал, то для всякого кодового вектора (многочлена) а(х) ? V имеем ха(х) ? V, т.е. циклический сдвиг снова является кодовым вектором.
Обратно, если V— циклический код, то для всякого кодового вектора а(х) его последовательные циклические сдвиги ха(х), х2а(х), . . ., х"~1а(х) также являются кодовыми векторами.
Остается показать, что для всякого многочлена b (X) = bn + Ьхх + btx2 + . .. + Ьп_ххп~г
произведение Ь(х)а(х) является кодовым вектором. Мы имеем:
b (х) а (х) =
= Ь,а (х) -f O1Xa (х) + b2x*a (х) + . . . + Ьп_1х"~1а (х). (5)
Согласно сказанному выше, каждое слагаемое в (5) принадлежит кодовому пространству, но тогда и вся сумма обладает этим свойством. Итак, V— идеал.
