14.4. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ КОДА R(1, m)

В гл 13 были описаны общие методы кодирования и декодирования кодов Рида — Маллера. К кодам первого порядка, однако, применим особый метод, который будет описан в этом параграфе. является -кодом и, следовательно, имеет низкую скорость и позволяет исправлять много ошибок. Практически он чрезвычайно пригоден для очень зашумленных каналов Например, код успешно применялся на космическом корабле «Маринер-9» для передачи изображений с Марса, одно из которых показано на рис 14 7. (Каждая точка на рисунке соответствует одному из 64 уровней градаций яркости черного цвета и кодировалась двоичным словом длины

Рис. 14.7 Часть большого каньона на Марсе Эта фото графия была передана косми ческим кораблем «Маринер-9» 19 января 1972 г. для пере дачи использовался код Рида-Маллера первого порядка Служба фотографии

Кодирование является особенно простым. Мы опишем этот метод на примере кодера для Сообщение кодируется словом

Такое кодирование реализуется схемой, показанной на рис. 14.8. Часы в этой схеме проходят через последовательные состояния (т. е. считают от 0 до 7). Схема формирует вектор который согласно уравнению (14.18) равен кодовому слову Вряд ли существует что-либо проще.

Рис. 14.8. Кодер для кода

Декодирование. Как мы видели в § 1.3, декодирование по максимуму правдоподобия сводится к сравнению полученного вектора с каждым словом (14.7) кода и выбору ближайшего из них в качестве результата декодирования. Согласно уравнениям (14.13) и (14.14) это равносильно нахождению наибольшего значения где преобразование Адамара вектора задаваемое формулой (14.8). Предположим, что это наибольшее значение равно Если то по декодируется в вектор

если же то декодируется в

Непосредственное вычисление вектора путем умножения требует примерно сложений и

вычитаний. К счастью, имеется более быстрый способ вычисления вектора основанный на дискретном варианте так называемого быстрого преобразования Фурье. Этот способ применим благодаря возможности представления в виде произведения матриц размерности каждая из которых содержит только два ненулевых элемента в каждом столбце. При таком вычислении требуется только сложений и вычитаний.

Чтобы объяснить это разложение матрицы нужно ввести кронекеровское произведение матриц.

Кронекеровское произведение матриц. Определение. Если некоторая -матрица над любым полем некоторая -матрица над тем же полем, то кронекеровским произведением матриц называется -матрица, получающаяся при замене каждого элемента матрицы А на матрицу Это произведение обозначается через и символически записывается в виде

Например, если

то

Отсюда видно, что в общем случае

Упражнение. (10). Доказать следующие свойства кронекеровского произведения:

(i). Ассоциативный закон:

(ii). Дистрибутивный закон:

Матрицы Адамара. Определим матрицу Адамара порядка индуктивно равенством

Матрица представляет собой матрицу Адамара типа Сильвестра из гл. 2 (см. рис. 2.3; она также является матрицей, задаваемой уравнением (14.9) при условии, что принимают значения из в нужном порядке).

Теорема 5. (Теорема о быстром преобразовании Адамара.)

единичная -матрица.

Доказательство. Воспользуемся индукцией по Для результат очевиден. Предположим, что результат справедлив для Тогда для

и

Таким образом, учитывая (14.21) и предположение индукции, получаем:

Пример. Для имеем:

(см. (14.19) и (14.20), и, очевидно,

Для

Схема декодирования Грина. Опишем теперь схему декодирования кода основанную на теореме 5. Эта схема была предложена Р. Р. Грином, поэтому она называется схемой Грина. Описание метода проведем на примере кода Предположим, что получен вектор и положим

Нам надо найти или, согласно (14.22),

Так как

то

Схема, приведенная на рис. 14.9, вычисляет координаты век тора парами. Ключи управляются таким образом, что после считывания символов в двух двухъячеечных регистрах, изображенных справа, содержатся соответственно числа

Рис. 14.9. Первый этап схемы Грина

Эти четыре величины используются (см. рис. 14.10) на втором этапе. Затем считываются символы и в той же паре двухъячеечных регистров формируются величины На втором этапе вычисляется вектор

где

Таким образом, произведение (14.23) равно Это произведение формируется схемой, изображенной на рис. 14.10. На третьем этапе вычисляется вектор

где

Рис. 14.10. Второй этап схемы Грина

Таким образом, произведение (14.24) равно

и дает нам искомое преобразование Адамара. Схема, реализующая эти вычисления, показана на рис. 14.11.

Все схемы, приведенные на рис. представляют собой схему декодирования Грина. Последний этап декодирования состоит в определении для которого значение максимально. После этого декодируется в слово кода если и в дополнение слова, если

Отметим, что схема Грина обладает тем полезным свойством что схема декодирования для кода получается из схемы декодирования для кода добавлением еще одного этапа и одного дополнительного регистра на этапе.

Упражнение. (11). Доказать, что (Это означает, что порядок этапов может быть изменен без изменения окончательного результата.)

Рис. 14.11. Третий этап схемы Грина