- •Лекции Методы повышения достоверности передачи и приема
- •2.Применение помехоустойчивых видов модуляции
- •3.Применение помехоустойчивого кодирования
- •3.5. Разделение линий связи
- •3.5.1. Постановка задачи
- •3.5.2. Частотное разделение
- •3.5.3. Временное разделение
- •3.5.4. Фазовое разделение
- •3.5.5. Разделение по форме
- •3.5.7 Кодовое разделение
- •3.5.8. Комбинированные методы разделения.
- •5. Применение каналов с обратной связью.
- •Оптические линии связи
- •Сжатие данных Основные понятия
- •Характеристики алгоритмов сжатия данных
- •Алгоритмы сжатия без потерь
- •Статистические алгоритмы сжатия
- •Алгоритм Хаффмена
- •Алгоритм арифметического кодирования
- •Алгоритмы сжатия, использующие исключение повторов
- •Алгоритмы kwe
- •Словарные и словарно-статистические алгоритмы сжатия
- •Алгоритмы сжатия с потерями
- •Алгоритмы сжатия растровых статических изображений
- •Источники, рекомендуемые для углубленного изучения
- •Циклические коды некоторые обозначения и определения
- •Арифметика по модулю два
- •Двоичные циклические коды
- •Кодирование
- •Декодирование
Декодирование
Главным инструментов процесса декодирования в обнаружении и/или исправлении ошибок в принятом кодовом слове является остаток от деления кодового слова на образующий полином. Этот остаток называют синдромом ошибки.
Как и в случае кодирования, декодирование можно производить двумя основными способами:
табличный;
циклическим способом.
Для табличного декодирования предварительно должны быть подготовлена таблица декодирования циклическим кодом (ДЦК) для каждого конкретного случая такая таблица будет своя. Таблица ДЦК строится с учётом корректирующей способности кода: количество обнаруживаемых ошибок, количество исправляемых ошибок. В такую таблицу закладывается информация о каждом синдроме ошибки, начиная с 0 (кодовая комбинация принята без ошибок) и заканчивая комбинациями, сигнализирующими о возникновении неисправимой ошибки.
Процесс табличного декодирования состоит из нескольких этапов (рис. 3):
деление принятого кодового слова на образующий полином g(x);
выборка из таблицы ДЦК значения по адресу получившегося остатка;
анализ выбранного значения из таблицы;
подача информационного блока D на выход или сигнала о неисправимой ошибке.
Рис. 3. Декодирование табличным методом
Таблица ДЦК – таблица декодирования циклического кода;
БАР – блок анализатора результата таблицы ДЦК.
Алгоритм циклического декодирования:
принятое кодовое слово делится на образующий полином;
вычисляется вес остатка. Если вес остатка w ≤ s, то принятая комбинация складывается по модулю два с остатком. Сумма даст исправленную комбинацию. Если w > s, то
производим циклический сдвиг влево (можно и вправо, так как направление не влияет, но если двигаем в одну сторону, то направление сдвига необходимо сохранять) принятой комбинации, делим полученную в результате циклического сдвига комбинацию на образующий полином g(x). Если в остатке w ≤ s, то складываем делимое с остатком. Затем производим циклический сдвиг в обратную сторону полученной комбинации. Результат сдвига уже не содержит ошибок. Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес w > s, то
повторяется процедура пункта 3 до тех пор, пока не будет w ≤ s, либо произведём n – 1 сдвигов. В этом случае
производится циклический сдвиг вправо (или влево, если двигали вправо) на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию,
из неё извлекаются старшие m разрядов – информационный блок (рис. 4).
Данный алгоритм декодирования легко реализуется на схемах с регистрами с обратной связью.
Рис. 4. Декодирование циклическим методом
~cW – принятое кодовое слово;
БЦС – блок циклического сдвига;
БАВ – блок анализатора веса;
D – исправленный информационный блок.
ЛИТЕРАТУРА
Мак-Вильямс Ф.Дж., Слоэн М.Дж. Теория кодов, исправляющих ошибки, 1979.
Питерсон У. Коды исправляющие ошибки. - пер. с англ. М.: «Мир», 1976.
Осокин А.Н., Каплинский К.В. Теория информации: лабораторный практикум для студентов специальности 220100 «Вычислительные машины, системы, комплексы и сети» Центра дистанционного образования. – Томск: Изд. ТПУ, 2000.
Темников Ф.Е. и др. Теоретические основы информационной техники, – М.: «Энергия», 1971.
Блейхут Р. Теория и практика кодов, контролирующих ошибки./Пер. с англ. – М.: «Мир», 1986.
Харкевич А. А. Борьба с помехами.– М.: Наука, 1965г. – 275 с.