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т~г.
В настоящее время открыто достаточно много кодов, для которых применимы подобные алгоритмы декодирования. Их описание и способы построения ортогональных проверок базируются на различных комбинаторных и геометрических конструкциях.