Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 21

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 50 >> Следующая


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,

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

Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed