Функциональная схема декодирующего устройства циклического кода

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

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

В исходном состоянии триггеры сдвигового регистра обнулены. Принимаемая n-разрядная кодовая комбинация символ за символом вводится в регистр. В течение первых m тактов обратная связь не действует, так как триггер – в нулевом состоянии. В течение последующих k=n-m тактов происходит деление: делимое суммируется по модулю два с делителем, поступающим через обратные связи. С поступлением последнего символа деление завершается. К этому моменту в регистре записан остаток, по виду которого принимается решение о наличии ошибки.

В разделе кодирования посылки вызова было определено что общая длина посылки вызова равна n_в=9, где k_в= 5, m_в=4.

Для режима вызова выбрали следующий образующий полином:

Построим декодирующее устройство для кода (5,4), при получении комбинаций которого используется образующий полином G₄(x)=x⁴+x+1.

Коэффициенты этого полинома g₀=1, g₁=1, g₂=0, g₃=0, (g₄=1). Число триггеров, равно степени полинома m=4. Сумматоры перед вторым и третьим триггерами и обратные связи на эти сумматоры должны отсутствовать, т.к. g₂=0 и g₃=0. Схема выглядит следующим образом (рис. 10):

Рис.10.

Алгоритм работы устройства сводится к следующему:

· на первых m тактах принимаемая комбинация последовательно вводится в регистр;

· на последующих k=n-m тактах ввод в регистр продолжается, причем вступают в действие обратные связи – происходит деление на образующий полином.

Работу на последних k=n-m тактах можно описать следующими уравнениями:

где

T_j[i] - состояние j-ого триггера на i-ом такте;

C_i, - i-ый информационный символ.

В КП декодер решает задачу обнаружения ошибок.

Процедура обнаружения ошибки сводится к делению принятой комбинации на образующий полином G_m(x) и анализу остатку от деления R(x):

- если R(x)=0, то ошибок нет (разрешенные кодовые комбинации делятся на образующий полином без остатка) или произошел прием с необнаруживаемой ошибкой (под действием искажений одна разрешенная комбинация перешла в другую разрешенную комбинацию).

- если R(x)≠0, то произошел прием с ошибкой (обнаруживаемой).

Остаток R(x) играет роль синдрома в коде Хэмминга.

Декодирующее устройство (ДКУ) для обнаружения ошибок представляет собой схему деления на образующий полином. Такой схемой является сдвиговый регистр, охваченный обратными связями через сумматоры по модулю два.

Пример:

Для режима вызова выбрали следующий образующий полином

G₄(x)=x⁴+x²+1.

Пусть комбинация имеет вид 10101. Ей соответствует полином C₅(x)= x⁴+x²+1.

Полином С₅(x) умножается на x⁴, что эквивалентно сдвигу безызбыточной кодовой комбинации влево (в сторону старших разрядов) на 4 разрядов или добавлению 4 нулей справа:

;

Или в двоичном эквиваленте: .

1. Полученный полином делим на образующий:

X⁸+x⁶+x⁴ x⁴+x+1

X⁸+x⁵+x⁴

X⁶+x⁵ x⁴+ x²+x

X⁶+x³+x²

X⁵+x³+ x²

x⁵+x²+x

x³+ x

Получаем остаток от деления R(x)= x³+ x, которому соответствует двоичная комбинация 1010.

2. Формируем 9-разрядную разрешенную комбинацию CRC-кода, для чего в освободившиеся при сдвиге разряды запишем комбинацию, соответствующую остатку R(x):

Соответствующая кодовая комбинация: 101011010.

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

х⁸+х⁶+х⁴+х³+х х⁴+х+1

х⁸+x⁵+x⁴ x⁴+x²+x+x⁵+x⁴+x³

x⁶+x⁵+х³+x

x⁶+x³+x²

x⁵+x²+x

x⁵+x²+x

После завершения приема кодовой комбинации все триггеры находятся в нулевом состоянии. Остаток R(x)=0, следовательно, комбинация принята без ошибок (либо с необнаруживаемой ошибкой).

Пусть в передаваемой кодовой комбинации искажен 3-й разряд: 100011010. Вновь проведем операцию деления:

х⁸+х⁴+х³+х х⁴+х+1

х⁸+x⁵+x⁴ x⁴+x+1

x⁵+х⁴+x³+x

x⁵+x²+x

x⁴+x³+x²

x⁴+x+1

x³+x²+1

Как видим, остаток R(x)≠0, что свидетельствует об ошибке в принятой комбинации. Следовательно, принимается решение о приеме с ошибкой.