Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Совершенно аналогично происходит исправление ошибки в любой другой позиции.
Задачи и дополнения
!. Построить кодеры для двоичных циклических кодов длины 15 с порождающими многочленами
a) X4+X+1; б) Х8+Х7+Х6+Х4-Ы.
2. Всякий циклический (п, /г)-код с порождающим многочленом g(x) можно представить в систематической форме следующим образом. Пусть г і (х) — остаток от деления х' на порождающий многочлен g (х), т.е
Xi = Qi (х) g (X)jTri (х).
Рассмотрим многочлены
Xі —г і (x) = qj(x) g (*)
при i=m, m+1, . . ., п—1, где т=п—k — степень порождающего многочлена g(x). Все эти многочлены кодовые, так как они кратны g(x). Кодовый вектор, соответствующий многочлену Xі—Ti (х), имеет вид:
(—По, —Гц.....— Ti,m-1, о, 1, ,..,0),
где Ti0, Tii, Tit т_ї— коэффициенты остатка ?і(х), а символ 1 стоит в позиции с номером І.
Мы получили п—m=k векторов, которые, как нетрудно видеть, линейно независимы. Если составить матрицу G, строками которой являются указанные векторы, то она и будет порождающей (ее строки образуют базис кодового подпространства). Если через R обозначить матрицу, строками которой являются коэффициенты многочленов /";(*), то матрица G получается приписыванием к матрице — R справа единичной матрицы Еь порядка k и ее можно условно записать в виде:
G = -RlEk. (4)
Отсюда легко следует (ср. §11, задача 10), что в качестве проверочной можно взять матрицу
,91 По столбцам матрицы H стоят коэффициенты остатков от деления мно-
гочленов Xu
на g(x).
изложенный в дополнении 2, многочленом I+*2+*3.
3. Чтобы проиллюстрировать метод рассмотрим снова (7,4)-код с порождающим Имеем: „
Л:5= (Л:3+*2+ D (*2+*+1)+Х+1,
Строками порождающей матрицы являются, следовательно, коэффициенты многочленов:
1+ +X2-I-X3,
I+* + *2+ +**,
I + *+ + *5,
X + X2 + +Л
1 1 0 0 0\ 10 10 0 0 0 0 1 0 іоооь
и Я =
I о о 0 10 0 VO о
I 1
1 1 10 1/
4. Метод, рассмотренный в дополнении 2, можно использовать для построения кодера систематического циклического кода.
При кодировании с помощью матрицы (4) кодовое слово получается умножением информационного слова на эту матрицу (см. (6), § 11). В этом случае последние k символов ат, ani + v . . ., ап_х кодового слова совпадают с информационными символами, а все кодовое слово является линейной комбинацией строк порождающей матрицы (4) с коэффициентами ат, ат +,, . . ., а t, Учитывая, что по строкам матрицы R
X
ZrHZ "^©^
T чл
O3^aSaS Л
Информационные \
Кодовое слобэ
сипВолы
В і
Рис. 23.
стоят коэффициенты остатков от деления многочленов Xі на порождающий многочлен g(x), мы убеждаемся, что величины о0, O1, . , ., аи_! являются коэффициентами остатка от деления многочлена -{атх" + ат + 1х« + * + .,.
на многочлен g(x) (в случае двоичных многочленов знак минус перед скобкой можно опустить).
Следовательно, схемы деления могут быть использованы для нахождения проверочных символов кодовых слов циклического кода в систематической форме и, в конечном итоге, для построения его кодера. На рис. 23 приведена схема кодера двоичного (7, 4)-кода с порождающим многочленом 1+х2+х3, основанная на указанном принципе.
,92 Проследим вкратце работу этой схемы в течение семи тактов. Первые четыре такта переключатели схемы находятся в положении А, следующие три — в положении В. В первые четыре такта информационные символы поступают (без изменений) на выход всей схемы и на выход схемы деления. В течение этих четырех тактов в последовательных ячейках схемы деления получаются коэффициенты остатка а0, Cj, аг от деления многочлена а6*6Н-а5л:5+04л:4+аз.ї3 на порождающий многочлен 1+.1:2+.?3, т. е. проверочные символы (в схеме на рис. 18 на это ушло бы семь тактов, но в данной схеме три такта «экономятся», так как последовательность коэффициентов о6, о5, о.,, а3 подается не из вход, а сразу на выход схемы деления). В последующие три такта проверочные символы — сначала а2, затем аі, затем й0— поступают из схемы деления на выход всей схемы. Таким образом, по истечении семи тактов на выходе всей схемы получаем целиком кодовое слово. .
Рекомендуем читателю проследить по тактам работу рассматриваемой СХеМЫ ДЛЯ Случая Q3=O, C4=A5=G6= 1.
17. ГОЛОСОВАНИЕ
Хотя в процедуре принятия решения большинством голосов нет для нас ничего необычного, может все же показаться неожиданным, что метод голосования используется при декодировании помехоустойчивых кодов. Отчасти мы уже коснулись этого вопроса в § 8, когда рассказывали о коде с повторением,— решение о посланном символе принималось там как раз большинством голосов. Теперь же мы покажем, как применяется голосование в случае произвольного линейного кода.
Обратимся сначала к примеру. Здесь нам поможет неоднократно упоминавшийся ранее (7,3)-код, получающийся из (7,4)-кода Хемминга добавлением общей проверки на четность. Его проверочная матрица имеет вид;
л і і і 1 1 к н__( OOOl і і Л
Ioi 1001 1 \1 0 1 0 1 0 1
Удобнее, однако, рассмотреть эквивалентный циклический код с порождающим многочленом g(x) = (x+l) (х3+х+1) и с проверочной матрицей
