18. Многоступенчатое голосование и коды Рида - Маллера

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

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

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

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

Пусть υ = (α₀, α₁, α₂, α₃, α₄, α₅, α₆, α₇) - произвольное кодовое слово. Оно, как обычно, может быть записано в виде:

Выясним, как связаны координаты α_i вектора υ с коэффициентами равенства (1). Заметим, что сумма первых двух координат каждого из векторов g₀, g₁ и g₂ равна 0, тогда как для вектора g₃ она равна 1. Поэтому сумма соответствующих координат вектора υ равна а₃, т. е.

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

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

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

Предположим, что верные значения коэффициентов а₁, a₂, а₃ найдены. Тогда еще один этап голосования позволяет определить также и верное значение коэффициента а₀. Сделать это совсем несложно. В самом деле, рассмотрим разность

В случае безошибочной передачи, в силу равенства (1), υ₁ = a₀g₀, т. е. все координаты вектора υ₁ равны а₀. Значит, либо все они равны нулю, либо все равны единице. Поэтому в качестве верного значения а₀ выбираем то, которое преобладает среди координат вектора υ₁.

Определив значения коэффициентов а₀, a₁, a₂, а₃, мы без труда восстанавливаем кодовое слово согласно равенству (1).

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

По большинству значений находим: а₁ = 0; а₂ = а₃ = 1. Тогда

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

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

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

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

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

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

Следовательно, если произошло не более трех ошибок, то в первом "туре" голосования удается восстановить верные значения коэффициентов а₁, а₂, а₃, а₄. Во втором "туре", действуя совершенно так же, как и в случае (8,4)-кода, получаем верное значение для а₀. После этого по найденным значениям коэффициентов целиком восстанавливаем кодовое слово. Итак, (16,5)-код Рида - Маллера исправляет любые ошибки, если они имеются не более чем в трех символах, и обнаруживает ошибки в четырех символах. Можно убедиться, что двух этапов голосования достаточно для любого РМ-кода первого порядка.

При построении кодов Рида - Маллера более высоких порядков используется покомпонентное умножение векторов, определяемое следующим образом: если υ = (α₁, α₂, ..., α_n), u = (β₁, β₂, ..., β_n), то

Покажем теперь, как по произвольному РМ-коду первого порядка строятся РМ-коды r-го порядка (r > 1). Пусть строками порождающей матрицы РМ-кода первого порядка являются векторы g₀, g₁, ...,g_m. Составим из этих векторов всевозможные произведения, содержащие не более r сомножителей. Добавим эти произведения в качестве дополнительных строк к строкам g₀, g₁, ...,g_m. Полученную в результате матрицу и будем считать порождающей матрицей РМ-кода r-го порядка. Например, для РМ-кода второго порядка, соответствующего (16,5)-коду Рида - Маллера первого порядка, эта матрица имеет вид

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

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

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

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

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

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

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

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

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