Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
9. В предыдущем примере код Vi эквивалентен систематическому коду V3. Это не исключение, а правило, поскольку справедливо следующее утверждение:
Всякий линейный код эквивалентен систематическому коду.
Доказательство, которое рекомендуется продумать читателю, основывается, в сущности, на известном современному школьнику методе Гаусса исключения неизвестных.
Последовательность действий, приводящих произвольный код к систематическому, продемонстрируем на примере матрицы (11) (задача 7).
Вычитая из четвертой строки матрицы (11) первую, получим:
далее, вычитая из первой строки вторую, приходим к матрице
C1= и G2 =
Получающиеся при этих преобразованиях матрицы также порождают
M "исходный код. Осуществим теперь перестановку столбцов, чтобы слева получить единичную матрицу — пятый столбец поставим на место второго, восьмой — на место третьего, седьмой — на место четвертого столбца. В итоге получим порождающую матрицу систематического кода
1 0 0 0 0 1 1 ON
0 10 0 10 11
0 0 1 0 0 1 1 1
0 О О 1 1 1 1 Qy
10. Показать, используя соотношения (7), что для систематического Кода с порождающей матрицей (9) в качестве проверочной можно взять следующую матрицу:
/-Pii -Pti -Pki 1 0 ... 0\
H ( -Pii — Ргг —Ркг 0 1 ••• 0\
V-Pim -Ргт ••• -Pkm 0 0 ••• 1/
11. Пусть V — произвольный линейный (п, й)-код. Рассмотрим множество Vh всех векторов пространства Ln, ортогональных каждому из кодовых векторов v?V. Нетрудно проверить, что V' является подпространством в Ln и, следовательно, может рассматриваться как линейный код. Код Vr называется дуальным к исходному коду V.
Убедиться, что если Ci и H — порождающая и проверочная матрицы кода V, то они служат соответственно проверочной и порождающей матрицей дуального кода V''.
Простейший пример кодов, дуальных друг к другу,— это код с повторением и код с общей проверкой на четность.
12. Одним из способов получения кодов, обладающих большим кодовым расстоянием, а значит, и высокой корректирующей способностью* является комбинирование двух или нескольких кодов. Примером такого комбинирования является рассматриваемая здесь конструкция. Она дает код, который является обобщением матричного кода из § 8 с проверками на четность по строкам и столбцам.
Пусть дано слово, содержащее U=U-Jt2 информационных символов. Разобьем множество этих символов на U2 блоков по символов в каждом и запишем результат в виде квадратной матрицы порядка U2Xk1:
/Ct11 CC12 ... Ctlftl \ ос21 C22 ... Ot2J1 \
¦аЫ aU1I ¦¦¦ akikJ В первой строке этой матрицы выписаны по порядку символы первого блока, во второй — символы второго и т. д.
Рассмотрим теперь произвольный систематический линейный код V1 длины U1 с ^1 информационными символами и с тем же самым кодовым алфавитом. Строки матрицы (12) закодируем указанным кодом — для этого к каждой строке припишем U1—A1 проверочных символов таким образом, чтобы выполнялись проверочные соотношения кода V1.
Далее каждый столбец получившейся матрицы порядка U2Xn1,
I
\
\ак-Л «Ай • ¦ • aIhk1 > . • a«,в, /
K11 K1J ... Hlftl ... я1п. ^ aSl «22 • ' • «2A, • ¦ • «21», !
ізакодируем точно таким же способом с помощью линейного (п2, k2)-кода V2.
В результате получим матрицу порядка n2Xrii:
' «11 а 12 • • • aIft1 • • aIfli
а2І «22 • • а2Пі
a M afca2 • • С ft.Jfi aSlfil
ат 1 апг2 ¦ aOjftl aOjf!,
Выписывая элементы этой матрицы «по строкам», мы и составим кодовое слово, отвечающее исходному слову. Оно, очевидно, однозначно определяется матрицей (12).
Построенный код называется произведением кодов Vi и V2 и обозначается K1^K2.
Пусть теперь ky k\, k2— числа информационных символов кодов Vi и K2 а п, пі, rt2— длины этих кодов. Из построения кода сразу же вытекает, что
k=kik2 И П= Il1Il2.
Менее очевидно аналогичное соотношение между кодовыми расстояниями d, di, d2 тех же кодов: d=d1 •d2. Доказательство этого факта предоставляем читателю.
Предлагаем читателю также выяснить, какова связь между количеством ошибок, исправляемых кодами K1-, V2 и V1(X)V2.
Проиллюстрируем сказанное примером. Пусть fe=8, ^1= 4, А3=2. В качестве кода Vi возьмем (7,4)-код Хемминга, записав предварительно его порождающую матрицу в систематической форме:
/10 0 0 1 1 0\ " / 0 1 0 0 1 0 1 I 0 0 1 0 0 1 I і \0 О О 1 1 1 1/
в качестве V2— (3,2)-код с общей проверкой на четность. Составим кодовое слово кода K1(^)K2. соответствующее исходному слову 00101110 с восемью информационными символами. Запишем его в виде матрицы порядка 2X4:
/0 0 1 0\ U 1 1 0}'
В результате кодирования строк (7,4)-кодом Хемминга (см. правило (6)) получим матрицу порядка 2X7:
/001001 IN
U 1 1 0 0 о oj'
Кодирование столбцов этой матрицы сводится к добавлению в каждом столбце символа общей проверки на четность. Получившейся в итоге матрице порядка 3X7
/0 0 1 0 0 1 1\ (1110 0 0 0) Vl 10 0 0 1 1/ соответствует следующее кодовое слово кода V1(^)V2: 001001111100001100011,
6012. ДЕКОДИРОВАНИЕ ПО СИНДРОМУ И ЕЩЕ РАЗ О КОДЕ ХЕММИНГА