7.8. КОДИРОВАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

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

Примеры. -код Хэмминга — циклический код с порождающим многочленом

(Е2). -код БЧХ, исправляющий две ошибки, — циклический код с порождающим многочленом

Предположим, что сообщение кодируется кодом и соответствующее кодовое слово равно:

(см. рис. 7.5).

Рис. 7.5, Кодирование сообщения систематическим кодом

Кодер . В первой схеме кодера требуется элементов задержки. Вектор с принадлежит коду тогда и только тогда, когда делится на Следовательно, мы

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

на и нахождение остатка Полагая затем получаем делящийся на

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

Частное равно и остаток равен

Ключевое замечание состоит в том, что каждый раз, когда в частном появляется 1, делимое меняет содержимое третьей и четвертой позиции на противоположное.

Устройство, выполняющее это вычисление, показано на рис 7.6.

Остаток равен тому, что оказывается записанным в регистре (слева направо), когда делимое полностью введено.

Рис. 7.6. Схема деления на

Итак, наша первая попытка закодировать данные состоит в том, чтобы ввести делимое (информационные символы, за которыми следуют нули)

После ввода всех 15 символов в регистре получаем остаток Полная схема кодера, выполняющего эту операцию, показана на рис. 7.7.

Рис. 7.7. Предварительный вариант кодера

Каждый из ключей имеет три позиции: в положении А ключ находится 11 тактов, в течение которых сообщение вводится в канал и регистр; в положении В ключ находится четыре такта, в течение которых в регистр вводятся четыре нуля; в положении С ключ находится четыре такта, в течение которых в канал подается остаток.

Недостатки этой схемы очевидны: канал простаивает, когда ключи находятся в положении В.

Для устранения этого недостатка будем подавать информацию в правый конец регистра сдвига. Это эквивалентно предварительному умножению на Поэтому вместо схемы деления, приведенной на рис. 7.6, будем использовать схему, показанную на рис. 7.8. Остаток теперь формируется в регистре сдвига, как только символ введен в него.

Рис. 7.8. Схема деления с предварительным умножением на

Окончательный вариант кодера представлен на рис. 7.9. Ключи находятся в положении А в течение 11 тактов работы и в положении В — в течение четырех тактов.

Ясно, что кодер такою типа годится для любого циклического кода, и необходимый регистр сдвига содержит элементов задержки. На рис. 7.10 показан кодер для примера

Кодер Для второго кодера требуется элементов задержки. Мы отмечали ранее, что проверочные символы определяются уравнениями (7.11).

Для примера

Таким образом, кодовое слово удовлетворяет уравнениям

Рис. 7.9 Окончательный вариант кодера

Рис. 7.10 Кодер для кода БЧХ

Если информационные символы, то эти уравнения определяют проверочные символы Соответствующее кодирующее устройство показано на рис. 7.11. Ключ находится в положении А в течение семи тактов работы и в положении В — в течение восьми тактов.

Рис. 7.11 Кодер для кода БЧХ

Устройство показано в момент, когда только что введен последний информационный символ и вычисляется первый проверочный символ

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

Упражнения. (34). Построить кодер для примера

(35). (а). Показать, что кодер соответствует порождающей матрице вида

в том смысле, что если на вход кодера подается сообщение то на его выходе формируется кодовое слово Здесь многочлен — остаток является остатком от деления на при Таким образом, (7.26) получается из (7.1) путем диагонализации последних столбцов. Если записать (7.26) в виде ], то соответствующая проверочная матрица будет иметь вид:

Аналогично показать, что кодер соответствует проверочной матрице вида

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

Вычисление синдрома. Техника декодирования циклических кодов будет рассматриваться в § 9.6 (коды (альтер-нантные коды), 13.7 (РМ-коды) и 16.6 (циклические коды общего вида и, в частности, квадратично-вычетные коды). Во всех случаях первый шаг алгоритма декодирования состоит в вычислении синдрома, которое по существу представляет свбой перекодирование полученного вектора (см. § 1.4). Если код используется только для обнаружения (не для исправления) ошибок, то этим работа приемного устройства и ограничивается.

Упражнения. (36). (а). Предположим, что полученный вектор вводится в кодер Пусть содержимое регистра сдвига в момент, когда все символов у уже введены. Показать, что удовлетворяет условию следовательно, является синдромом вектора у. [Указание. Записать у в виде

тогда и т. д.].

(b). Показать, что после одного дополнительного такта работы регистр сдвига содержит синдром, соответствующий вектору циклическому сдвигу вектора у.

(c). Если для вычисления синдрома использовать кодер то схема рис. 7.11 должна быть немного изменена так, как это показано на рис. 7.12. Показать, что схема рис. 7.12 действительно вычисляет синдром . В положении А ключи находятся четыре такта работы, в течение которых в регистр сдвигов вводятся (возможно искаженные) информационные символы.

Рис. 7.12. Модифицированный кодер предназначенный для вычисления синдрома

Затем ключи перебрасываются в положение В, где они остаются в течение трех тактов работы устройства, и на выход подается синдром

ЗАМЕЧАНИЯ К ГЛ. 7

(см. скан)

(см. скан)