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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра РЭС

реферат на тему:

«Особенности практического применения способов кодирования. Способы декодирования с обнаружением ошибок»

МИНСК, 2009

Задача кодирования заключается в формировании по информационным словам a(x) кодовых слов (x) циклического (n,k)-кода, который по своей структуре может быть несистематическим и систематическим.

Формирование кодовых слов несистематического кода заключается в умножении многочлена a(x), отображающего информационную последовательность длины k, на порождающий многочлен, т.е. (x)=a(x)(g(x). Формирование кодовых слов систематического кода заключается в преобразовании информационной последовательности a(x) в соответствии с выражением (x)=a(x)x^r +r(x).

Проверочная последовательность r(x) определяется двумя способами:
при использовании "классического" способа кодирования ;
при использовании способа кодирования, рекомендованного МККТТ ,
где x(1)^r-1 - единичный многочлен степени (r-1).

Указанные выше математические операции выполняют кодеры несистематического и систематического кодов.

Способы декодирования с обнаружением ошибок

Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два способа:
- при кодировании "классическим" способом декодирование основано на использовании свойства делимости без остатка кодового многочлена (x) циклического (n,k)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом на g(x), вычисление и анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается неискаженным. Если r(x)0, то принятое кодовое слово стирается и формируется сигнал "ошибка".
- при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка R₀ (x) при делении принятого кодового многочлена (x) на порождающий многочлен. Поэтому, если полученный при делении остаток , то принятое кодовое слово считается неискаженным. Если остаток , то принятое кодовое слово стирается и формируется сигнал "ошибка". Значение контрольного остатка определяется из выражения .

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

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

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

В состав декодера входят: вычислитель синдрома (ВС), два регистра сдвига RG1 и RG2, постоянное запоминающее устройство (ПЗУ), которое содержит слова длины n, соответствующие многочленам ошибок e_i (x).
Принятое кодовое слово поступает на вход вычислителя синдрома, где осуществляется деление его на g(x) и формирование S_i (x), и одновременно - на вход RG2, где накапливается. Синдром S_i (x) используется в качестве адреса, по которому из ПЗУ в регистр RG1 записывается e_i (x), соответствующий синдрому S_i (x). Перечисленные операции завершаются за n тактов. В течение последующих n тактов происходит поэлементное суммирование содержимого RG2 и RG1, т.е. операция , и исправление. ошибок.

В основе второго способа исправления ошибок, позволяющего значительно сократить объем используемых табличных синдромов и существенно упростить схему декодера, лежат следующие положения:

1. Синдром S_i (x), соответствующий принятому кодовому слову равен остатку от деления на g(x), а также остатку от деления соответствующего многочлена ошибок ei(x) на g(x), т.е. .

2. Если S_i (x) соответствует и e_i (x), то x( S_i (x) является синдромом, который соответствует и или .

3. При исправлении ошибок используются синдромы образцов ошибок только с ненулевым коэффициентом в старшем разряде.

Поэтому при реализации этого способа множество всех образцов ошибок разбивается на классы эквивалентности. Каждый класс представляет циклический сдвиг одного образца ошибок, а синдром этого класса соответствует образцу ошибок с ненулевым старшим разрядом. Если вычисленный синдром принадлежит одному из классов эквивалентности образцов исправляемых ошибок, то старший символ кодового слова исправляется. Затем принятое слово и синдром циклически сдвигается, а процесс нахождения в предыдущей по старшинству позиции повторяется.

Для исправления ошибок, принадлежащих данному классу эквивалентности, нужно произвести n циклических сдвигов.

Простейшим является декодер Меггитта. В состав декодера входят: вычислитель синдрома, осуществляющий деление кодового слова