Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
,99 падают! расширенный (8,4)-код Хемминга дуален самому себе. При т=4 получаем (16,5)-код Рида — Маллера первого порядка с порождающей матрицей
/1 1 1 1 11 11 1 1 I I I 1 ! Iv Zg0K /00000000111 IllllX І Єї \ G = I 0000111100001111 ]=( g, 1. Ioo 1 I 00 I 1 00 1 I 00 1 ! J \gs I \0 101010101010101/ \gj
Алгоритм декодирования для этого кода практически не отличается от рассмотренного выше алгоритма для (8,4)-кода. Действительно, если
« = aogo + ^g, + ^g а + a3gs + &igi,
то, например,
?4 = ctc-ftz) = tz2-l-a, = a4 + a6 = tze+a, = ae + a9 = a10-fan =
=а)а+а13=а 14+а16.
Таким образом, для коэффициента а4 имеем 8 ортогональных проверочных соотношений. Такое же число ортогональных проверок получается и для каждого из коэффициентов аи
Следовательно, если произошло не более трех ошибок, то в первом «туре» голосования удается восстановить верные значения коэффициентов аъ а2, аа, а4. Во втором «туре», действуя совершенно так же, как и в случае (8,4)-кода, получаем верное значение для а0. После этого по найденным значениям коэффициентов целиком восстанавливаем кодовое слово. Итак, (16,5)-код Рида — Маллера исправляет любые ошибки, если они имеются не более чем в трех символах, и обнаруживает ошибки в четырех символах. Можно убедиться, что двух этапов голосования достаточно для любого РМ-кода первого порядка.
При построении кодов Рида — Маллера более высоких порядков используется покомпонентное умножение векторов, определяемое следующим образом: если u=(ai, ait . . ., an), a=(?f> -?a». . M ?n)> TO
©oa=(ai?i, a2?u>. • • , a„?j-
Покажем теперь, как по произвольному РМ-коду первого порядка строятся PM-коды г-го порядка (г>1). Пусть строками порождающей матрицы РМ-кода первого порядка являются векторыg„,gi,. . Составим из этих векторов всевозможные произведения, содержащие не более г сомножителей. Добавим эти произведения в качестве допол-
,100 нительных строк к строкам g0, gi.....gm. Полученную в
результате матрицу и будем считать порождающей матрицей РМ-кода г-го порядка. Например, для РМ-кода второго порядка, соответствующего (16,б)-коду Рида — Маллера первого порядка, эта матрица имеет вид
'11111111111111 1 1 ( go
00000000111111 1 1 84
00001 1 1 10000 11 1 1 Sa
001 1001 1001 100 1 1 Ss
01010101010101 0 1 gi
0000000000001 1 1 1 SBS ffl°g2
00000000001100 1 1 gl°gs
00000000010101 0 1 gl ° gi
0000001 1000000 1 1 gt°ga
00000101000001 0 1 gi°gi
1.000 1 000 1000 1-0 00 1) gt>°gi J
Этот код исправляет любые одиночные и обнаруживает двойные ошибки, а мажоритарное декодирование для него может быть осуществлено в три этапа. Если v кодовое слово, то
+ai3gi°g3+- ¦ -+Ougt0Si- (б)
На первом этапе определяем верные значения коэффициентов a,j, для каждого из которых имеем четыре ортогональных проверочных соотношения. Например, для коэффициента аЗІ они таковы:
Оз4=ао+аі+а2+аз. азі=аі+аь+ав+ат
°34—а8 + а9 + аіО+«І1>
а34=а12 + а13 + а14+а15<
После определения коэффициентов а,у составляем разность
V1-V-Q1^g1Og2-. . .—a3ig3og4z=(aZ, а'и. . .,«,[,).
Поскольку при безошибочной передаче
= a0g0 + ^g1 + a2g2 + a3g3 + ^gi,
то проверочные соотношения для определения ait ait сц* а4 (это второй этап голосования) таковы же, как для РМ-кода первого порядка. К примеру,
а« — «о + «і = «2 + «з = «4 + а'ъ = аё + а?0 «в + «в
= «io+ aIi=1 аі2 + а« "я a\t + а|в.
,101 Наконец, на третьем этапе составляем разность
Vi-^igi-aSffa-flSgr8-^igr1 =* («0. aI. •••• а1б)
и по большинству значений координат а1 определяем значение а0. После завершения третьего этапа кодовое слово восстанавливается по формуле (5).
Подобная процедура декодирования распространяется на РМ-коды произвольных порядков; при этом для кода г-го порядка число этапов голосования равно г+1 и для кода длины 2т число ортогональных проверок на первом этапе равно 2т~г (на каждом последующем этапе число проверок удваивается). Таким образом, может быть исправлено 2т~г~1—1 ошибок, а 2т~г~1 ошибок всегда обнаруживается.
В настоящее время открыто достаточно много кодов, для которых применимы подобные алгоритмы декодирования. Их описание и способы построения ортогональных проверок базируются на различных комбинаторных и геометрических конструкциях.
Задачи и дополнения
1. Для (8,4)-кода Рида — Маллера первого порядка исправить или обнаружить ошибки в следующих словах:
11010110, 11100001.
2. Анализируя соотношения (2), (3), (4), найти число обнаруживаемых и число необнаруживаемых тройных ошибок в (8,4)-коде Рида— Маллера. Имеются ли исправимые тройные ошибки? Решить те же вопросы для ошибок в четырех символах. -
3. Для (16,5)-кода Рида — Маллера первого порядка исправить или обнаружить ошибки в следующих словах:
1110010100100111, 1010010110101010, 1001001001001001.
4. Считая, что используется РМ-код второго порядка длины 16, исправить или обнаружить ошибки в тех же словах, что и в задаче 3. Чем объясняются расхождения с результатами задачи 3?
5. Доказать, что код Рида — Маллера г-го порядка длины п=2т имеет 1+Cm+- • -+Crm информационных символов, l+C^+- . .+Сш~г_1 проверочных символов, а его кодовое расстояние равно 2т~г.
