Декодирование

Главным инструментов процесса декодирования в обнаружении и/или исправлении ошибок в принятом кодовом слове является остаток от деления кодового слова на образующий полином. Этот остаток называют синдром ом ошибки.

Как и в случае кодирования, декодирование можно производить двумя основными способами:

1. табличный;

2. циклическим способом.

Для табличного декодирования предварительно должны быть подготовлена таблица декодирования циклическим кодом (ДЦК) для каждого конкретного случая такая таблица будет своя. Таблица ДЦК строится с учётом корректирующей способности кода: количество обнаруживаемых ошибок, количество исправляемых ошибок. В такую таблицу закладывается информация о каждом синдроме ошибки, начиная с 0 (кодовая комбинация принята без ошибок) и заканчивая комбинациями, сигнализирующими о возникновении неисправимой ошибки.

Процесс табличного декодирования состоит из нескольких этапов (рис. 3):

1. деление принятого кодового слова на образующий полином g (x);

2. выборка из таблицы ДЦК значения по адресу получившегося остатка;

3. анализ выбранного значения из таблицы;

4. подача информационного блока D на выход или сигнала о неисправимой ошибке.

Рис. 3. Декодирование табличным методом

Таблица ДЦК – таблица декодирования циклического кода;

БАР – блок анализатора результата таблицы ДЦК.

Алгоритм циклического декодирования:

1. принятое кодовое слово делится на образующий полином;

2. вычисляется вес остатка. Если вес остатка w ≤ s, то принятая комбинация складывается по модулю два с остатком. Сумма даст исправленную комбинацию. Если w > s, то

3. производим циклический сдвиг влево (можно и вправо, так как направление не влияет, но если двигаем в одну сторону, то направление сдвига необходимо сохранять) принятой комбинации, делим полученную в результате циклического сдвига комбинацию на образующий полином g (x). Если в остатке w ≤ s, то складываем делимое с остатком. Затем производим циклический сдвиг в обратную сторону полученной комбинации. Результат сдвига уже не содержит ошибок. Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес w > s, то

4. повторяется процедура пункта 3 до тех пор, пока не будет w ≤ s, либо произведём n – 1 сдвигов. В этом случае

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

6. из неё извлекаются старшие m разрядов – информационный блок (рис. 4).

Данный алгоритм декодирования легко реализуется на схемах с регистрами с обратной связью.

Рис. 4. Декодирование циклическим методом

~ cW – принятое кодовое слово;

БЦС – блок циклического сдвига;

БАВ – блок анализатора веса;

D – исправленный информационный блок.

ЛИТЕРАТУРА

1. Мак-Вильямс Ф.Дж., Слоэн М.Дж. Теория кодов, исправляющих ошибки, 1979.

2. Питерсон У. Коды исправляющие ошибки. - пер. с англ. М.: «Мир», 1976.

3. Осокин А.Н., Каплинский К.В. Теория информации: лабораторный практикум для студентов специальности 220100 «Вычислительные машины, системы, комплексы и сети» Центра дистанционного образования. – Томск: Изд. ТПУ, 2000.

4. Темников Ф.Е. и др. Теоретические основы информационной техники, – М.: «Энергия», 1971.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки./Пер. с англ. – М.: «Мир», 1986.

6. Харкевич А. А. Борьба с помехами.– М.: Наука, 1965г. – 275 с.