Коды Рида-Маллера: алгоритмы кодирования и декодирования

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

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

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

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

,

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

,

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

В соответствии с определением порождающей матрицы (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. Кодовые слова кода Рида-Маллера

Информационные символы	Кодовое слово	Информационные символы	Кодовое слово

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

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

, ,…, .

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

.

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

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

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

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

,

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

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

,

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

.

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

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

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

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

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