5.7. Коды Рида-Маллера

5.7.1. Задание и декодирование кодов Рида-Маллера

Коды Рида-Маллера относятся к линейным двоичным кодам, имеющим большие кодовые расстояния и исправляющим благодаря этому много ошибок. Они пригодны для каналов с малым отношением сигнал/помеха. Этот класс кодов интересен и потому, что с ним связаны многие другие сигналы, применяемые в радиотехнических системах: ортогональные и биортогональные сигналы, симплексные коды, -последовательности и коды Хэмминга.

Будем рассматривать простейшие коды Рида-Маллера, слова которых являются линейными комбинациями некоторых двоичных функций  обладающих полезными для практики свойствами. Сразу укажем, что эти функции выбраны такими, что их отображение в поле действительных чисел дает систему ортогональных функций. Это свойство используется при декодировании.

Данное ограничение означает, что в базис кода не входят произведения двоичных функций, т.е. рассматривается код Рида-Маллера 1-го порядка. Некоторые сведения о кодах Рида-Маллера более высоких порядков имеются в [30].

Кодовое слово длины  обычно рассматривается как булева функция (или ее инверсия), заданная в  точках, т.е. на наборах из  двоичных элементов. Можно многими способами нумеровать позиции кодового слова -разрядными двоичными векторами. Ясно, что, как в случае кодов Хэмминга, такая перестановка не влияет на помехоустойчивость получаемых кодов. Будем нумеровать позиции кодового слова числами в двоичной системе счисления , где  для . Ввиду линейности кодов Рида-Маллера каждый символ кодового слова  представим линейной комбинацией

,

или ее инверсией

,

где    – известные информационные символы.

В соответствии с определением порождающей матрицы (5.16) и правилом покомпонентного сложения векторов элементы  являются столбцами матрицы . Для  порождающая матрица размера  на  имеет вид:

.

Столбцы матрицы  без верхней строки представляют собой последовательность чисел, записанных в двоичной системе счисления (младшие разряды внизу). Таким образом, столбцы матрицы можно рассматривать как последовательность состояний двоичного суммирующего счетчика:

,

(5.34)

где    1 – последовательность из единиц;  – последовательность состояний последнего (старшего) разряда счетчика;  – последовательность состояний первого (младшего) разряда. Отметим, что перестановка столбцов и строк порождающей матрицы приводит к эквивалентным кодам.

Кодовое слово есть линейная комбинация базисных векторов (строк матрицы ):

.

(5.35)

Вид матрицы (5.34) указывает простой способ формирования базисных векторов и получения кодового слова. Схема кодирующего устройства для  (рис. 5.5) содержит трехразрядный двоичный счетчик, вырабатывающий функции , и комбинационную схему, реализующую булеву функцию (5.35). Естественно, длительность информационных символов, подаваемых в этот кодер, предполагается равной длительности кодового слова, т.е. в данной случае 8 длительностям символов канала.

Двоичный вектор  с компонентами  может быть отображен в вектор  с действительными компонентами . Для этого надо «0» в двоичном векторе заменить на (+1), а «1» – на (–1). Такое отображение можно определить формулами:

, .

(5.36)

В табл. 5.8 приведены все 16 кодируемых информационных последовательностей и соответствующие им кодовые слова. Обратим внимание, что кодовые слова правой половины таблицы являются инверсией слов левой половины.

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

Таблица 5.8. Кодовые слова кода Рида-Маллера

Информационные символы	Кодовое слово	Информационные символы	Кодовое слово
0000	00000000	1000	11111111
0001	01010101	1001	10101010
0010	00110011	1010	11001100
0011	01100110	1011	10011001
0100	00001111	1100	11110000
0101	01011010	1101	10100101
0110	00111100	1110	11000011
0111	01101001	1111	10010110

мысленно и связано с разной трактовкой одних и тех же уровней напряжений (высоких и низких) в технических устройствах.

Если применить отображение (5.36) к строкам матрицы (5.34), по определению получим известные функции Радемахера [10]:

, ,…,.

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

.

т.е. число позиций, на которых символы последовательностей совпадают, равно числу позиций, на которых последовательности отличаются, и равно поэтому . Из определения расстояния Хэмминга (см. 5.4.1) заключаем, что кодовое расстояние кода Рида-Маллера равно . Отметим, что для пар слов, являющихся инверсией друг друга, расстояние равно .

Таким образом, коды Рида-Маллера имеют длину ,  информационный символ, кодовое расстояние . Отображение двоичных кодовых слов в область действительных чисел  дает множество функций Уолша, включающее  функций Уолша , , и  противоположных функций , . Множество сигналов, составленных из функций Уолша и противоположных им, называется системой биортогональных сигналов. Если в систему не включать противоположные сигналы, то получим систему ортогональных сигналов, которые используются в качестве адресов абонентов в системах множественного доступа с кодовым разделением каналов. Применение ортогональных сигналов в качестве канальных позволяет разделять их в таких системах без взаимных помех [20].

Для кодов Рида-Маллера разработаны достаточно эффективные алгоритмы порогового (мажоритарного) декодирования, изложенные в [30]. Здесь рассмотрим декодирование кодов Рида-Маллера по принципу максимума правдоподобия. Для симметричного канала это совпадает с декодированием по минимуму расстояния между векторами, при котором в качестве оценки переданного вектора  берется слово, ближайшее к принятому вектору .

Имея в виду преобразование (5.36), рассмотрим коэффициент корреляции  между принятым вектором  и функцией Уолша . При

,

где    и  принимают значения .

Поскольку при совпадении знаков  и  их произведение равно 1, а при несовпадении – (–1), то

,

где    и  – соответственно числа совпадающих и несовпадающих символов в  и , а . При , очевидно, получим

.

Таким образом, оптимальный алгоритм декодирования предполагает следующие этапы:

1. Вычисление  коэффициентов корреляции  между  и функциями Уолша , .

2. Поиск максимального по абсолютной величине коэффициента .

3. Принятие решения по правилу: , если , и , если .

Следовательно, данная процедура представляет собой многоканальный корреляционный прием. Ее сложность пропорциональна числу  операций сложения и вычитания. Разработаны быстрые алгоритмы декодирования кодов Рида-Маллера, по своей сути аналогичные алгоритмам быстрого преобразования Фурье [30].