17. Циклические коды. Особенности и принцип построения кодовой комбинации циклического кода. Обнаружение и исправление ошибок при циклическом кодировании. Синдром циклического кода и его свойства.

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

1. любая из разрешенных кодовых комбинаций циклического кода делится по модулю два без остатка на некоторое, так называемое «образующее двоичное число», определяющее помехоустойчивые свойства кода, т.е. расстояние d;

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

Например: 01011 и 10110 – две разрешенные кодовые комбинации некоторого циклического кода с образующим числом 1011 (d=3). Поэтому они делятся по модулю два без остатка на образующее число:

01011 1011 10110 1011

0000 01 1011 10

1011 0000

1011 0000

000 000

При этом d=4 >d=3.

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

01011 => 10110

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

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

Идея построения циклического кода (n,k) сводится к тому, что информационную часть кодовой комбинации G(x) нужно преобразовать в комбинацию F(x), которая без остатка делится на порождающий полином Р(х) степени r=n-k. Рассмотрим последовательность операций построения циклического кода:

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

2. Умножаем G(x) на одночлен ( старшую степень порождающего полинома Р(х) ) и получаем.

Пусть у нас порождающий полином 1011, тогда .

3. Делим на порождающий полином Р(х), при этом получаем остаток от деленияR(x).

Добавим полученный остаток R (x) к комбинации и получим комбинацию, которая будет передана в линию. Данная комбинацияF(x) делится без остатка на образующий полином и представляет собой разрешенную кодовую комбинацию циклического (n,k) кода. На приеме производится деление полученной кодовой комбинации на образующий полином. Если ошибок нет, то деление пройдет без остатка. Если при делении получен остаток, то комбинация принята с ошибками.

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

Построение кодеров, декодеров.

Пример:

Кодер строится на основе полинома P(x).

=> 1011 – веса

При построении устройства число ячеек регистров сдвига берется по высшей степени образующего полинома => 3 регистра сдвига; число регистров задержки берется также по высшей степени образующего полинома; число сумматоров по модулю два берется по весовой части образующего полинома минус единица => 3-1=2m.

Состояния регистров (1,2,3 – регистры; m – сумматоры)

На вход подается 110101000

Декодер – правила построения такие же, как у кодера, но количество регистров задержки определяется по высшей степени информационной комбинации плюс 1  5+1=6

Деление на образующий полином происходит за 9 тактов. Пока идет деление на образующий полином К2 разомкнут, а К1 замкнут в течении 6 тактов пока идет запись информационных импульсов. После 6 такта К1 размыкается. После 10 такта К2 замыкается и формируется сигнал:

1. Если хотя бы в одной ячейке регистра будет «1», то значит произошла ошибка. Формируется сигнал «1» и информация из регистров сдвигов будет удаляться.

2. Если во всех ячейках регистров сдвига будут «0», то формируется сигнал «0» и информация будет выдана потребителю.

Состояния регистров

Если хотя бы в одной ячейке регистра будет «1», то значит произошла ошибка.

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

Выбор образующего полинома.

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

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

=1 если n=7, то

tи.ош – число ошибок, исправляемых циклическим кодом.

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

В частности, если r=3, t_и.ош=1, j=2*1-1=1, образующий полином будет представлять собой единственный минимальный многочлен P(x)= x³+x+1 (первая строка, второй столбец таблицы ). Соответственно образующее число равно 1011.

Синдром циклического кода.

Синдром циклического кода определяется суммой по модулю 2 принятых проверочных элементов и элементов проверочной группы, сформированных из принятых элементов информационной группы. В циклическом коде для определения синдрома следует разделить принятую кодовую комбинацию на кодовую комбинацию порождающего полинома. Если все элементы приняты без ошибок, то остаток от деления R(х) равен нулю. Если есть ошибки, то остаток не будет равен нулю. Следовательно, синдромом циклического кода является многочлен R(x). Обнаружение и исправление ошибок производится только на основе анализа синдрома. В зависимости от остатка определяется элемент в котором произошла ошибка. Для исправления ошибок необходимо чтобы количество ненулевых остатков равнялось количеству элементов n ( при исправлении одной ошибки ) или числу комбинаций из n.