18. МНОГОСТУПЕНЧАТОЕ ГОЛОСОВАНИЕ И КОДЫ РИДА — МАЛЛЕРА

 

Мы расскажем здесь о кодах, для которых най­ден замечательный алгоритм исправления ошибок, сыграв­ший важнейшую роль в развитии методов мажоритарного декодирования.

Проще всего начать с расширенного (8,4)-кода Хеммин­га. Нетрудно убедиться, что этот код дуален самому себе, т е. что его проверочная матрица служит для него и по­рождающей:

 

 

Этот код не является полностью ортогонализуемым (см. § 17, задача 2). Значит ли это, что голосование для этого кода невозможно? Оказывается, нет.

Идея, которую мы проиллюстрируем на данном при­мере, состоит в следующем. Если нельзя составить нужной системы ортогональных проверок для каждого символа в отдельности, то, может быть, это удастся сделать для опре­деленных линейных комбинаций этих символов.

Пусть г»=(а0, с^, а2, а3, а4, ав, а„, а,) — произвольное кодовое слово. Оно, как обычно, может быть записано в виде:

 

 

Выясним, как связаны координаты а,- вектора V с коэф­фициентами равенства (1). Заметим, что сумма первых двух координат каждого из векторов §-0, и §-2 равна О, тогда как для вектора^ она равна 1. Поэтому сумма соот- сетствующих координат вектора г> равна а3, т. е.

 

 

Совершенно так же убеждаемся, что верны равенства:

 

 

 

 

 

 

Нетрудно понять, что соотношения (2) и (6) представляют систему ортогональных проверок для коэффициента а3. Для коэффициентов а2 и ^ дело обстоит аналогично и ортого­нальные проверки для них таковы:

 

 

 

 

 

 

 

 

 

 

 

 

 

Применяя к полученным проверкам принцип большин­ства, мы найдем верные значения коэффициентов сч, а2, а3, если произошло не более одной ошибки. В случае двой­ной ошибки при определении хотя бы одного из коэффици­ентов голоса распределятся поровну и ошибка будет толь­ко обнаружена.

Предположим, что верные значения коэффициентов а1, й2, а8 найдены. Тогда еще один этап голосования позволяет определить также и верное значение коэффициента а0. Сде­лать это совсем несложно. В самом деле, рассмотрим раз ность

 

 

В случае безошибочной передачи, в силу равенства (1), ©1=с0§'0, т. е. все координаты вектора равны а0 Значит, либо все они равны нулю, либо все равны единице. Поэтому в качестве верного значения а0 выбираем то, ко­торое преобладает среди координат вектора ч>у.

Определив значения коэффициентов ай, а2, а3, мы без труда восстанавливаем кодовое слово согласно равен­ству (1).

Пример. Пусть принято слово 01110110, содержа­щее одиночную ошибку. Для декодирования обращаемся к равенствам (2), (3) и (4), которые в данном случае дают следующие результаты:

 

 

 

Тогда

 

По большинству значений находим:

 

откуда о0=0. Следовательно,

 

 

 

Этот изящный метод декодирования может быть приме­нен к так называемым кодам Рида — Маллера (сокращен­но— РМ-коды), которые мы и хотим сейчас рассмотреть.

РМ-код первого порядка определяется как код, дуаль­ный к расширенному коду Хемминга, т. е. как код, порож­дающая матрица которого совпадает с проверочной матри­цей расширенного кода Хемминга. Таким образом, расши­ренному (п, к)-коду Хемминга («=2т, к=2т—т—1) отвечает (п, п—/г)-код Рида — Маллера. При т=3 оба кода сов-падают: расширенный (8,4)-код Хемминга дуален самому себе. При т—4 получаем (16,5)-код Рида — Маллера пер-1 кто пооядка с порождающей матрицей

 

 

Алгоритм декодирования для этого кода практически не отличается от рассмотренного выше алгоритма для (8,4)- кода. Действительно, если

 

 

 

то, например,

 

 

Таким образом, для коэффициента а4 имеем 8 ортогональных проверочных соотношений. Такое же число ортогональных проверок получается и для каждого из коэффициентов а.

Следовательно, если произошло не более трех ошибок, то в первом «туре» голосования удается восстановить вер­ные значения коэффициентов аг, а2, а8, с4. Во втором «туре», действуя совершенно так же, как и в случае (8,4)-кода, по­лучаем верное значение для а0. После этого по найденным значениям коэффициентов целиком восстанавливаем кодо­вое слово. Итак, (16,5)-код Рида — Маллера исправляет любые ошибки, если они имеются не более чем в трех сим­волах, и обнаруживает ошибки в четырех символах. хМожно убедиться, что двух этапов голосования достаточно для любого РМ-кода первого порядка.

 

Покажем теперь, как по произвольному РМ-коду пер­вого порядка строятся РМ-коды г-го порядке (г>1). Пусть строками порождающей матрицы РМ-кодо первого порядка являются векторы           . -,8т- Составим из этих векторов

всевозможные произведения, содержащие, не более г со­множителей. Добавим эти произведения в качестве допол-

При построении кодов Рида — Маллера более высоких попялков используется покомпонентное умножение вектора

нительных строк к строкам          . .         Полученную в

 

 

 

 

После определения коэффициентов о,7 составляем разность

 

Поскольку при безошибочной передаче

 

результате матрицу и будем считать порождающей матри­цей РМ-кода г-го порядка. Например, для РМ-кода второго порядка, соответствующего (16,5)-коду Рида — Маллера первого порядка, эта матрица имеет вид

 

 

Этот код исправляет любые одиночные и обнаруживает двойные ошибки, а мажоритарное декодирование для него может быть осуществлено в три этапа. Если V кодовое сло­во, то

 

 

На первом этапе определяем верные значения коэффици­ентов аи, для каждого из которых имеем четыре ортого­нальных проверочных соотношения. Например, для коэф­фициента й34 они таковы:

то проверочные соотношения для определения а1г аг, а3, (это второй этап голосования) таковы же, как для РМ- кода первого порядка. К примеру,

 

Наконец, на третьем этапе составляем разность

 

 

и по большинству значении координат а( определяем зна­чение а0. После завершения третьего этапа кодовое слово восстанавливается по формуле (5).

Подобная процедура декодирования распространяется на РМ-коды произвольных порядков; при этом для кода г-го порядка число этапов голосования равно г+1 и для кода длины 2т число ортогональных проверок на первом этапе равно 2т~г (на каждом последующем этапе число проверок удваивается). Таким образом, может быть исправ­лено 2т~г~1—1 ошибок, а 2т~г~1 ошибок всегда обнаружи­вается.

Задачи и дополнения

1. Для (8,4)-кода Рида — Маллера первого порядка исправить или обнаружить ошибки в следующих словах:

 

Анализируя соотношения (2), (3), (4), найти число обнаруживае­мых и число иеобнаруживаемых тройных ошибок в (8,4)-коде Рида— Маллера. Имеются ли исправимые тройные ошибки? Решить те же во­просы для ошибок в четырех символах.

Для (16,5)-кода Рида — Маллера первого порядка исправить или обнаружить ошибки в следующих словах:

 

Считая, что используется РМ-код второго порядка длины 16, исправить или обнаружить ошибки в тех же словах, что и в задаче 3. Чем объясняются расхождения с результатами задачи 3?

Доказать, что код Рида — Маллера г-го порядка длины п=2т имеет 1+Ст+.. ,+Ст информационных символов, Н-С,1,,-!-- . ■+Сш_г~1 проверочных символов, а его кодовое расстояние равно 2т~г.

В настоящее время открыто достаточно много кодов, для которых применимы подобные алгоритмы декодирова­ния. Их описание и способы построения ортогональных проверок базируются на различных комбинаторных и гео­метрических конструкциях.