Лабораторная работа №5. «Циклические коды».

Теоретическая часть

 

Определение 5.1. Блочное (n, k)-кодирование называется циклическим, если при любой циклической перестановке символов кодовой комбинации получается также кодовая комбинация.

 

Теорема 5.1. Блочное (n, k)-кодирование является циклическим тогда и только тогда, когда оно порождено многочленом степени r = n – k , являющимся делителем двучлена хn + 1.

Определение 5.2.Частное от деления двучлена хn + 1 на порождающий многочлен называется проверочным многочленом.

 

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

 

Теорема 5.2. Для того, чтобы циклическое кодирование позволяло исправлять не менее одной ошибки необходимо и достаточно, чтобы остатки от деления одночленов хi (i = 0, 1, …,n – 1 ) на соответствующий порождающий многочлен были различны.

 

Построение и декодирование циклических кодов, исправляющих одиночную ошибку, осуществляется следующим образом.

1) Производится расчет количества контрольных символов. Если задано число информационных разрядов, то можем воспользоваться эмпирической формулой

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

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

4) Значения корректирующих разрядов находятся в результате деления многочлена, полученного в пункте 3) на образующий многочлен. Остаток от деления складывается по модулю 2 с многочленом, полученным в пункте 3).

 

Обнаружение и исправление ошибки также производится с помощью остатка от деления полученной комбинации на образующий многочлен.

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

Если остаток не равен нулю, то в коде присутствует ошибка. Для исправления ошибки необходимо выполнить ряд действий.

1) Подсчитать вес (весом двоичного вектора называется величина расстояния Хемминга от него до нулевого вектора) остатка. Если он не больше корректирующей способности кода, то принятую комбинацию складывают с по модулю 2 с полученным остатком. Результат дает исправленную комбинацию.

2) Если вес остатка больше корректирующей способности кода, то необходимо циклически сдвинуть кодовую комбинацию на один разряд влево и результат поделить на образующий многочлен. Если вес остатка не больше корректирующей способности кода, то делимое складывают с остатком, а затем производят циклический сдвиг вправо на один разряд. Полученная комбинация является исправленной.

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

ПРИМЕР

Задание. Закодировать комбинацию α=1101, построив порождающий и проверочный многочлен. Внести ошибку в один из разрядов кодового многочлена; проверить полученное сообщение; найти и исправить ошибку.

 

Очевидно, что число информационных разрядов k=4, определим кодовое расстояние r и порождающий многочлен.

 

Так как d0=3, то для расчета r можем использовать формулу , r=3. По таблице 1 найдем образующий многочлен – х3 + х + 1 или 1011 ( в дальнейшем все многочлены мы записываем, как последовательность коэффициентов в порядке убывания степеней).

 

Умножив его на одночлен 1000, получим 1101000.

 

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

 

             
             
             
             
             
             
             
               

 

Сложим комбинацию 1101000 с остатком 001:

 

       

 

Кодовая комбинация β имеет вид β =1101001,

Внесем ошибку во второй разряд =1001001. Для обнаружения и исправления ошибки произведем деление:

 

       
             
             
               

 

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

           
               

 

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

 

       
             
             
                   

 

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

 

           

 

Исправленная комбинация βисп =1101001.

 

практическая часть

 

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

 

 

Вариант Информационные комбинации
Вариант Информационные комбинации

 

 

Вопросы

5. Линейное кодирование. Основные понятия.

6. Порождающая и проверочная матрицы; синдром.

7. Помехоустойчивое кодирование. Основные понятия. Расстояние Хемминга; кодовое расстояние.

8. Коды, порождённые многочленами. Основные понятия.

9. Циклические коды. Основные понятия и свойства.