5. Метод Мюллера

В работах [130, 147] был предложен и исследован метод построения бинарных кодов с параметрами

(IX.5.1)

где и — целые числа, причем порядок кода Табл. IX.3 дает наглядное представление о связи этими величинами для .

Как легко заметить, для всех значений существует код Рида—Мюллера, совпадающий по своим параметрам с кодами, рассмотренными в предыдущем параграфе при и .

Весьма интересен код (32, 16, 8); аналогичный код, не совпадающий ни с одним из рассмотренных ранее, можно найти для .

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

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

Таблица IX.3

(IX.5.2)

Базис кода Рида — Мюллера порядка s образуется совокупностью комбинаций (IX.5.2), дополненной комбинациями, полученными в результате «покоординатного» перемножения двух, трех и т. д. s комбинаций

Совокупность комбинаций (IX.5.2) образует базис кода Рида — Мюллера первого порядка с параметрами . Для того чтобы образовать базис кода Рида — Мюллера второго порядка с параметрами , надо дописать к (IX.5.2) всевозможные попарные произведения векторов

(IX.5.3)

Множество (IX.5.3) не содержит произведений вида и так как согласно правилу покоординатного умножения

(IX.5.2)

Базис кода Рида—Мюллера третьего порядка с параметрами образуется в результате добавления к (IX.5.2) помимо множества (IX.5.3) еще всех возможных произведений трех векторов (IX.5.4)-(IX.5.5):

(IX.5.6)

В соответствии с общими положениями любая комбинация кода Рида — Мюллера может быть представлена как

(IX.5.7)

где символы комбинации исходного кода.

Короче говоря, соотношение (IX.5.7), как и ранее, задает преобразование -значной комбинации исходного кода в -значную комбинацию кода с избыточностью. Указанное преобразование нетрудно записать в виде системы линейных форм. Для этого следует умножить первую строку (IX.5.2) на , вторую — на и т.д, пятую — на а затем просуммировать элементы -го столбца и записать результат в виде :

(IX.5.8)

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

На рис. IX.1 представлена блок-схема кодера для случая кода с базисом (IX.5.2). Он состоит из генератора последовательности (генератор единиц), линии задержки тактового импульса на один такт, четырехкаскадного бинарного счетчика, сумматора но модулю два и набора ключей .

Рис. IX.1. Кодирующее устройство для кода Рида—Мюллера первого порядка при и .

Положение ключа выбирается в соответствии со значениями информационных символов: если , то ключ замкнут, если же , то ключ разомкнут.

Заметим, что замыкание ключа соответствует умножению последовательности на 1, а его размыкание - умножению на 0 (IX.5.7). Процесс формирования комбинации начинается с замыкания ключа . Первый тактовый импульс фиксируется в линии задержки и одновременно поступает на вход ключа (входы остальных ключей по-прежнему характеризуются нулевым состоянием).

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

Легко видеть, что после второго такта работы кодера состояние входов ключей описывается вторым столбцом (IX.5.2) и на выходе кодера образуется символ , после третьего , после четвертого и т. д.

Короче говоря, на выходе кодера последовательно формируются символы, соответствующие системе линейных форм, полностью совпадающей с той, которая представляет данный код Рида—Мюллера (IX.5.8).

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

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

При этом необходимо учитывать, что на основании (IX.5.8) и (IX.5.2)

(IX.5.9)

для всех нечетных

(IX.5.10)

где

(IX.5.11)

для

(IX.5.12)

Отмеченная закономерность является следствием особенностей базисных матриц кодов Рида — Мюллера.