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→х³+ х¹.

Определение ошибочного разряда в циклических кодах.

Многочлен ошибки – это сумма многочлена соответствующей переданной и принятой кодовой комбинации. А(х) – многочлен, соответствующий переданной комбинации, Н(х) – многочлен, соответствующий принятой комбинации, Е(х) – многочлен ошибки.

Е (х) = А(х)+ Н(х). Для кода (9;5), Е(х) = 100000000.

Свойства циклического кода:

1. Остаток, полученный от деления принятого многочлена на производящий полином = остатку, полученному при делении соответствующего многочлена ошибок на производящий полином Р(х): Н(х1)/ Р(х)= Е(х1)/ Р(х)

2. Синдром ошибок в циклическом коде не зависит от передаваемой комбинации и определяется только местом ошибки.

Алгоритм определения ошибки:

1. Получаем остаток от деления многочлена ошибок, соответствующего ошибки в старшем разряде, на образующий полином. Е(х1)/ Р(х)=R₀(х)

2. Делим полученный полином на производящий, в результате получаем текущий остаток Н(х1)/ Р(х)=R(х).

3. Сравниваем R₀(х) и R(х): - если они равны, то ошибка произошла в старшем разряде; - Если не равны, то увеличиваем степень принятого полинома на х и снова проводим деление.

Н(х)*х/ Р(х)=R(х).

Если на этом шаге R₀(х) =R(х), то ошибка во втором разряде после старшего.

Если нет, то опять домножаем принятый многочлен на х. Повторяем шаги 1,2 до тех пор, пока R₀(х) =R(х). Ошибка будет в разряде, соответствующем, соответствующем числу, на которое повысится степень полученного полинома +1.

Д екодер с обнаружением ошибок. 010110101.

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

Т.к получили 0+0+0+0, то на выходе схемы 1 будет 0, т.е. ошибки нет. Если будет 1- ошибка есть!

Декодер с исправлением ошибки. Схема & сравнивает текущий остаток с эталонным . Когда они совпадают, на выходе будет ошибочный элемент. Схема & подает управляющий сигнал и инвертирует элемент, находящийся в данный момент времени на

выходе. Т.о. кодовая комбинация приходит исправленная.