ЛЕКЦИЯ 4: «ЦИКЛИЧЕСКИЕ КОДЫ»

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

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

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

Пример 4.1:

.

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

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

,

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

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

Пример 4.2:

.

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

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

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

,

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

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

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

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

.

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

,

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

Пример 4.3:

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

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

.

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

.

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

,

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

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

.

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

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

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

.

ДОМАШНЕЕ ЗАДАНИЕ:

2. Найти полином для задачи из примера 4.3. Записать матрицу .

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

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

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

,

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

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

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

,

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

Пример 4.3:

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

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

.

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

1) ;

2) ;

3) .

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

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

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

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

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

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

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

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

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

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

Пример 4.4:

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

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

ДОМАШНЕЕ ЗАДАНИЕ:

2. Схему кодера систематического кода построить самостоятельно.

ДОМАШНЕЕ ЗАДАНИЕ:

1. [3.1.2] с.315…318;

[3.1.3] с.200…204;

[3.1.5] с.149…150;

[3.1.14] с.263…270, 282…286.

Не нашли, что искали? Воспользуйтесь поиском по сайту: