8. Циклические коды.

Любая комбинация, полученная путем сдвига, является комбинацией циклического кода.

а₁, а₂,а₃…а_n-1,a_n,=> a_n ,а₁, а₂,а₃…а_n-1. Все разрешенные кодовые комбинации делятся на образующий полином без остатка. Эти свойства используются для кодирующих/ декодирующих устройств, для обнаружения/исправления ошибок.

В циклическом кодировании КК записывается в виде многочлена: Аn-1(x)=a_n-1x^n-1+ a_n-2x^n-2+…+a₁x+a₀

a_i=1-не нулевой член, a_i=0 – нулевой член. Например 1010→х³+ х¹.

Алгоритмы построения циклического кода.

Пусть есть комбинация, соответствующая простому коду (Q(x)). И есть образующий полином, определяющий корректирующую способность циклического кода (Р(х)). Преобразуем простой код в циклический.

1. Q(x)х^r, где r –максимальная степень образующего полинома Р(х) = а_r-1х^r+ а_r-2х^r-1+…1;

2. Разделим , где G(х) – многочлен, определяющий простой код;

3. Q(x)х^r= G(х) Р(х)+R(х), =>,G(х) Р(х)= Q(x)х^r+ R(х) (знак не учитывается, т.к.сложение по модулю 2) Полученное равенство позволяет увидеть 2 способа формирования циклического кода.

1 способ: получение G(х) Р(х). (в результате способа получается неразделимый код, в нем нельзя увидеть исходную комбинацию)

2 способ: - получение произведения Q(x)х^r; - деление на Р(х); - получение остатка и приписывание этого остатка к произведению Q(x)х^r. (получаем разрешенную комбинацию)

Построение кодера циклического кода.

1. Число ячеек памяти равно максимальной степени образующего полинома, т.е. r

2. Число сумматоров на 1 меньше веса образующего полинома

3. Сумматор ставится после каждой ячейки, начиная с нулевой (ее на схеме нет), для которой существует соответствующий член в полиноме. После ячейки, соответствующей старшему разряду, сумматор не ставится

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

Рассмотрим на примере кода (9;5). Р(х) = х⁴+х+1, Q(х) = х⁴+х²+1 = 10101.

такт	вход	ячейки
5	1	0	1	1	0
6	0	0	0	1	1
7	0	1	1	0	1
8	0	1	0	1	0
9	0	0	1	0	1

Первые 4 такта заполняются одновременно РЗ и ФПГ. После 4-го такта ключи меняют свое положение, следующие пять тактов информационные разряды покидают кодер и одновременно с эти в ФПГ идет процесс деления на образующий полином. Вслед за информационными уходят проверочные разряды и одновременно с этим идет заполнение ячеек регистров следующей информационной комбинацией.

Еще один вариант кодера для данного кода.

такт	вход	ячейки
1	1	1	1	0	0
2	0	0	1	1	0
3	1	1	1	1	1
4	0	1	1	1	1
5	1	1	1	0	0

Ячейки вначале работы д.б. обнулены. Первые 5 тактов - информационные разряды уходят на выход, тем временем в ячейке кодера формируются проверочные разряды. После 5-го такта ключи меняют свое положение и вслед за информационными кодер покидают проверочные разряды.