2.3. Двоичные коды Рида-Маллера

Двоичные коды Рида-Маллера (РМ) составляют семейство кодов, исправляющих ошибки, с простым декодированием, основанным на мажоритарной логике. Кроме того, известно, что коды этого семейства имеют очень простые и хорошо структурированные решетки.

Известно элегантное определение двоичных РМ кодов, основанное на двоичных полиномах (или Булевых функциях). Согласно этому определению, РМ коды становятся близкими к кодам БЧХ и PC, которые входят в класс полиномиальных кодов.

2.3.1. Булевы полиномы и рм коды

Обозначим f(x₁, х₂,..., х_т) Булеву функцию от т двоичных переменных x₁, х₂,..., х_т. Известно, что такие функции легко представить с помощью таблицы истинности. Таблица истинности содержит список значений функции f для всех 2^т комбинаций значений ее аргументов. Все обычные Булевы операции (такие как «и», «или») могут быть представлены как Булевы функции.

Пример 15. Рассмотрим функцию f(х_1,х₂), заданную следующей таблицей истинности:

Тогда

Ассоциируем с каждой Булевой функцией f двоичный вектор f длины 2^т, составленный из значений данной функции для всех возможных комбинаций значений т ее аргументов. В последнем примере f=(0110), где принято соглашение о лексикографическом (иначе, арифметическом) упорядочении значений аргументов функции, таком, что x₁ представляет младший разряд, a x_m- старший разряд.

Заметим, что Булева функция может быть записана прямо по таблице истинности с помощью дизъюнктивной нормальной формы (ДНФ). В терминах ДНФ любая Булева функция может быть записана как сумма 2^m элементарных функций: 1, х₁, х₂, …x_m, x₁ х₂,..., х₁х_m,..., х₁х₂..х_m такой что

(2.4)

где вектор 1 добавлен для того, чтобы учесть свободный член (степени 0). В примере 15 f=x₁+x₂.

Двоичный (2^т, k, 2^т-r) РМ код, обозначенный РМ_r,m, определяется как множество векторов, ассоциированных со всеми Булевыми функциями степени до r, включительно, от m переменных. Код PM_r,m называют также кодом РМ r-ого порядка длины 2^т. Размерность РМ_r,m кода, как легко может быть показано, равна

Это число равно числу способов, которыми могут быть построены полиномы степени r или меньше от m переменных.

С учетом уравнения (2.4) строками порождающей матрицы РМ_r,m кода являются вектора, ассоциированные с k Булевыми функциями, которые могут быть записаны как полиномы степени r или меньше от m переменных.

Пример 16. Код РМ первого порядка длины 8, PM_1,3, является двоичным (8,4,4) кодом, который может быть построен из Булевых функций степени 1 от 3 переменных: {1, х₁, х₂, х₃}. Таким образом,

Порождающая матрица РМ_1,3 кода имеет, следовательно, вид

(2.5)

Заметим, что код PM_1,3 может быть построен также и из кода Хемминга (7,4,3) добавлением общей проверки на четность. Расширенный код Хемминга и РМ_1,3 код могут отличаться только порядком позиций (столбцов).

Дуальные коды кодов РМ также являются кодами РМ

Можно показать, что РМ_m-r-1, _т код дуален коду PM _r,m. Другими словами, порождающая матрица РМ_m-r-1,т кода может быть использована как проверочная матрица PM _r,m кода.