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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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