Изучение декодера циклического кода

Лабораторная работа

«Изучение декодера циклического кода»

Теоретические сведения Циклические коды относятся к классу линейных систематических кодов и обладают всеми их свойствами. Удобно рассматривать кодовые комбинации циклического кода не в виде последовательности нулей и единиц, а в виде полинома некоторой степени:

(1)

где x — основание системы счисления; - цифры данной системы счисления; n-1, n-2,… — показатель степени, в которую возводится основание, и одновременно порядковые номера, которые занимают разряды, начиная от старшего и заканчивая нулевым.

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

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

Таблица № 1

Построение разрешенной кодовой комбинации циклического кода сводится к следующему:

1. Представляем информационную часть кодовой комбинации длиной k в виде полинома Q (x).

2. Производим сдвиг kразрядной кодовой комбинации на r разрядов, путём умножения Q (x) на одночлен x^r.

3. Делим многочлен Q (x) x^r на образующий полином Р (x), степень которого равна r. В результате деления образуется остаток R (x).

4. Разрешенная кодовая комбинация циклического кода имеет следующий вид:

(2)

Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же образующий полином Р (х), который использовался при кодировании. Если ошибок в принятой кодовой комбинации нет, то деление на образующий полином производится без остатка. Если при делении получится остаток, то это свидетельствует о наличии ошибки. Остаток от деления в циклических кодах играет роль «синдрома».

Для определения местоположения ошибки в циклическом коде существует ряд методов, основанных на анализе «синдрома» R (x).

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

В состав схемы деления входят сдвигающий регистр (ячейки 1 — 4), сумматоры по модулю 2 (М2) и ключ (Кл). Число ячеек сдвигающего регистра выбирается равным степени образующего полинома, а число сумматоров по модулю 2 на единицу меньше его веса. Таким образом, на рис. 4 приведена схема деления на полином Р (х) = x⁴+x+1 так как его степень равна четырем, а его вес (число членов в полиноме) трём. Делимое в виде двоичного кода подается на вход сдвигающего регистра, а полином Р (х) вводится в регистр в виде соответствующим образом подобранной структуры обратных связей через сумматоры по модулю 2. Ключ замыкает обратную связь, что обеспечивает работу схемы деления.

Рис. 1. Схема деления на Р (х) Задание 1. Ввести ошибку в циклический код (7,4) и выполнить декодирование циклический код декодирование Кодовая посылка: 1 001 110

Введем ошибку: 1 011 110

Представим кодовую посылку в виде полинома:

Найдем остаток от деления старшего одночлена на порождающий полином:

Поделим кодовую комбинацию на порождающий полином:

Число сдвигов, следовательно, ошибка в .

Задание 2. Подать исходную кодовую комбинацию на схему деления Рис 2. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 2.

Таблица № 2

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

Задание 3. Подать на схему деления кодовую комбинацию с ошибкой Рис 3. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 3.

Таблица № 3

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

Задание 4. Построить декодер циклического кода (7,4), обнаруживающий и исправляющий одну ошибку Структура декодера циклического кода (7,4), обнаруживающего и исправляющего одну ошибку представлена на рис. 4.

Рис 4. Структура декодера циклического кода (7,4), обнаруживающего и исправляющего одну ошибку Работа декодера циклического кода (7,4), обнаруживающего и исправляющего одну ошибку, представлена в таблице № 4.

Таблица № 4

Задание 5. Ввести ошибку в циклический код (9,5) и выполнить декодирование Кодовая посылка: 10 101 101

Введем ошибку: 101 101

Представим кодовую посылку в виде полинома:

Найдем остаток от деления старшего одночлена на порождающий полином:

Поделим кодовую комбинацию на порождающий полином:

Число сдвигов, следовательно, ошибка в .

Задание 6. Подать исходную кодовую комбинацию на схему деления Рис 5. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 5.

Таблица № 5

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

Задание 7. Подать на схему деления кодовую комбинацию с ошибкой Рис 6. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 6.

Таблица № 6

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

Задание 8. Построить декодер циклического кода (9,5), обнаруживающий и исправляющий одну ошибку.

Структура декодера циклического кода (9,5), обнаруживающего и исправляющего одну ошибку представлена на рис. 4.

Рис 7. Структура декодера циклического кода (9,5), обнаруживающего и исправляющего одну ошибку Работа декодера циклического кода (9,5), обнаруживающего и исправляющего одну ошибку, представлена в таблице № 7.

Таблица № 7

Задание 9. Ввести ошибку в циклический код (11,7) и выполнить декодирование Кодовая посылка:1 010 100 111

Введем ошибку: 1 110 100 111

Представим кодовую посылку в виде полинома:

Найдем остаток от деления старшего одночлена на порождающий полином:

Поделим кодовую комбинацию на порождающий полином:

Число сдвигов, следовательно, ошибка в .

Задание 10. Подать исходную кодовую комбинацию на схему деления Рис 8. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 8.

Таблица № 8

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

Задание 11. Подать на схему деления кодовую комбинацию с ошибкой Рис 9. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 9.

Таблица № 9

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

Задание 12. Построить декодер циклического кода (11,7), обнаруживающий и исправляющий одну ошибку Структура декодера циклического кода (11,7), обнаруживающего и исправляющего одну ошибку представлена на рис. 10.

Рис 10. Структура декодера циклического кода (11,7), обнаруживающего и исправляющего одну ошибку Работа декодера циклического кода (11,7), обнаруживающего и исправляющего одну ошибку, представлена в таблице № 10.

Таблица № 10

Задание 13. Ввести ошибку в циклический код (15,11) и выполнить декодирование Кодовая посылка: 10 101 010 100 100

Введем ошибку: 10 001 010 100 100

Представим кодовую посылку в виде полинома:

Найдем остаток от деления старшего одночлена на порождающий полином:

Поделим кодовую комбинацию на порождающий полином:

Число сдвигов, следовательно, ошибка в .

Задание 14. Подать исходную кодовую комбинацию на схему деления Рис 11. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 11.

Таблица № 11

Задание 15. Подать на схему деления кодовую комбинацию с ошибкой Рис 12. Схема деления на порождающий полином

Работа схемы деления представлена в таблице № 12

Таблица № 12

Задание 16. Построить декодер циклического кода (15,11), обнаруживающий и исправляющий одну ошибку Структура декодера циклического кода (15,11), обнаруживающего и исправляющего одну ошибку представлена на рис. 13.

Рис 13. Структура декодера циклического кода (15,11), обнаруживающего и исправляющего одну ошибку.

Работа декодера циклического кода (15,11), обнаруживающего и исправляющего одну ошибку, представлена в таблице № 13.

Таблица № 13

Задание 17. Моделирование работы декодера циклического кода (7,4) обнаруживающего и исправляющего одну ошибку Рис 13. Модель декодера циклического кода (7,4), обнаруживающего и исправляющего одну ошибку Рис 14. Диаграмма состояний декодера циклического кода (7,4), обнаруживающего и исправляющего одну ошибку.(U1 — входная последовательность, U2- выходная последовательность, U3 — последовательность с выхода схемы деления, U4 — тактовые импульсы) Выводы: при подаче на схему деления кодовой комбинации без ошибки на выходе схемы деления образуется нулевой остаток. При подаче на схему деления кодовой комбинации с ошибкой на выходе схемы деления при обнаружении ошибки образуется остаток, равный остатку от деления старшего одночлена на порождающий полином.