Лекция 4: «циклические коды»

4.1 ОСНОВНЫЕ ПОНЯТИЯ

Поиск более простых процедур кодирования и декодирования привел к появлению циклических кодов.

Циклические коды – линейные блочные коды, обладающие свойством цикличности: если - кодовое слово циклического кода, то его циклическая перестановкатакже является кодовым словом.

Пример 4.1:

.

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

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

,

где - коэффициенты полинома;

- символическая переменная.

Пример 4.2:

.

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

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

Любой полином степени, который делит без остатка полином вида, называетсяпорождающим полиномом:

,

где - коэффициенты полинома.

Полиномы всех кодовых слов делятся без остатка на порождающий полином.

Порождающая матрица строится на основе полинома .

Для несистематического циклического кода:

.

Для систематического циклического кода:

,

где - прямоугольная подматрица, строками которой являются коэффициенты полинома остатка от деленияна полином, где- номер строки.

Пример 4.3:

Показать, что полином является порождающим для 7-разрядного циклического кода. Записать матрицу.

Для несистематического кода:

.

Для систематического кода:

.

Результат деления полинома вида на порождающий полином называетсяпроверочным полиномом:

,

где - коэффициенты полинома.

При отсутствии ошибок в принятом кодовом слове остаток от деления произведенияна полином видаравен нулю:

.

Проверочная матрица строится на основе полинома .

Для несистематического циклического кода:

Для систематического циклического кода:

.

4.2 КОДИРОВАНИЕ ИНФОРМАЦИИ

Существует два способа кодирования:

- несистематическое кодирование:

,

где - полином информационного слова,

- полином кодового слова;

- систематическое кодирование:

,

где - остаток от деления произведенияна полином.

Пример 4.3:

Закодировать слово циклическим кодом из примера 4.3.

Несистематическое кодирование:

.

Систематическое кодирование:

1) ;

2);

3) .

4.3 КОДИРУЮЩИЕ УСТРОЙСТВА

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

Правила построения схем умножения и деления:

- число ячеек памяти равно старшей степени полинома . Ячейка для старшей степени отсутствует;

- число сумматоров на единицу меньше веса полинома : при умножении отбрасывается сумматор для младшей степени; при делении – для старшей. Сумматоры устанавливают перед ячейками памяти для соответствующих степеней;

- при умножении множимое подается одновременно на вход и на все сумматоры, при делении делимое подается только на первый сумматор, а частное на выход и на все сумматоры. Множимое и делимое поступает на вход, начиная со старшего разряда.

Рисунок 4.1 – Кодер несистематического циклического кода.

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

2

Рисунок 4.2 – Кодер систематического циклического кода.

Кодер реализует алгоритм . Вначале ключнаходится в положении 1, а ключзамкнут. Информационные символы, подаваемые на вход, через ключпоступают на выход, а через ключ- в кодирующее устройство, где черезтактов образуетсяпроверочных символов, представляющих собой остаток от деления произведенияна полином. Затем ключпереводится в положение 2, а ключразмыкается. Регистр делаеттактов, выдавая проверочные символы на выход.

Пример 4.4:

Построить схему кодера циклического кода из примера 4.3.

Рисунок 4.3 – Кодер несистематического кода.