Основные принципы помехоустойчивого кодирования. – ЧАСТЬ 1

Коды, об­ладающие способностью к обнаружению и исправлению ошибок, называют по­мехоустойчивыми. Более узкой их категорией являются корректирующие коды, позволяющие исправлять ошибки.

Основная идея обнаружения ошибок по своей сути тождественна принципу обнаружения орфографических ошибок в тексте естественного языка. Ошибка, имевшая место в некотором слове, устраняется, если замена символов или букв превратила это слово в запись, отсутствующую в списке «разрешенных» слов (т.е. в словаре) данного языка. То же самое можно сказать об идее исправления ошибок. Руководствуясь интуицией, мы заменяем неправильно написанное сло­во тем словом из словаря этого языка, которое отличается от рассматриваемой записи в минимальном числе знаков. Так, встретив в некотором тексте запись «кодуляция», мы скорее заменим его на слово «модуляция» (отличие в одной позиции), нежели на «популяция» (две позиции), и уж наверняка не на «федера­ция» (отличие в шести позициях).

В реальности человек воспринимает содержание разного рода сообщений руководствуясь своей интуицией, лингвистическими знаниями и семантиче­скими соображениями. В технике кодирования целесообразно применять более простые, формализуемые математически правила. На практике, они сводятся к добавлению в последовательность передаваемых символов избыточных симво­лов с тем, чтобы те удовлетворяли некоторым дополнительным условиям, про­верка которых на приемной стороне позволит обнаружить и исправить ошибки. Такие возможности у большинства известных кодов обусловлены их алгебраи­ческой структурой, в связи с чем эти конструкции часто называют алгебраиче­скими кодами.

Рассмотрим базовые принципы и понятия помехоустойчивого кодирования.

Термином код обозначают множество всех разрешенных кодовых слов или правило их построения. Слова кода состоят из информационных и проверочных символов, в простейшем случае различаемых по позициям (такие коды назы­вают разделимыми или систематическими). Информационные символы – это символы последовательности, поступающей на вход кодера канала. Собственно говоря, они и представляют передаваемое сообщение. Проверочные символы формируются из информационных символов в соответствии с правилами по­строения кода. По этим же правилам при декодировании из полученного прием­ником кодового слова образуются проверочные символы, сравниваемые с при­нятыми проверочными (идентифицируемыми по их позициям). Если те и другие не совпадают, то это означает, что при передаче произошла ошибка.

В качестве меры различия кодовых слов используют кодовое расстояние d (число позиций, в которых символы кодовых слов отличаются – т.н. расстояние по Хеммингу). Для определения кодового расстояния между словами двоичного кода надо подсчитать число единиц в векторе, образуемом их суммированием по модулю 2. Наименьшее расстояние, взятое по всем парам разрешенных кодовых слов коДа, называют его минимальным кодовым расстоянием.

Как следует из сказанного выше, при декодировании в качестве оценки приня­того кодового слова целесообразно выбирать разрешенное слово кода с наименьшим расстоянием относительно полученного слова. Такое декодирование является опти­мальным и называется декодированием по принципу максимума правдоподобия.

Чтобы код мог обнаружить не менее 5 ошибок одновременно, он должен иметь минимальное расстояние между разрешенными словами, по крайней мере, на единицу большее: Jmin>j,+1. Код позволяет исправлять все конфигура­ции ошибок, содержащие до t ошибок включительно, если каждая из них приво­дит к запрещенному слову, остающемуся к искаженному кодовому слову «бли­же», чем к любому другому разрешенному слову этого же кода.

Всевозможные слова, образуемые искажением p<t символов некоторого разрешенного кодового слова е., образуют подмножества, на рис. 2.28 показан­ные в виде концентрических окружностей (описанных вокруг точки, соответ­ствующей этому слову). В каждом из таких подмножеств количество разрешен­ных слов кода длиной п равняется (т.е. числу сочетаний из п по р).

Из рис. 2.28 легко видеть: чтобы указанные подмножества не пересекались, минимальное расстояние по Хэммингу между разрешенными кодовыми слова­ми должно удовлетворять соотношению dmJ> 2t+\. Если из-за воздействия по­мехи кодовое слово перейдет в некоторую точку на одной из «своих» окружно­стей с номером ре {1,2,…/}, то декодер исправит такую ошибку.

Рис. 2.28. Иллюстрация зависимости корректирующей способности кода от минимального расстояния по Хеммингу

Таким образом, исходными параметрами корректирующих кодов являются-

–                длина кода п (численно равная общему количеству символов в слове);

–                количество информационных символов в кодовом слове к;

–                минимальное кодовое расстояние dmin.

Длина кода п и длина его информационной части к однозначным образом определяют число проверочных символов кода п~к, избыточность кода, а так­же скорость кодирования. Последние две, наряду с выигрышем от кодирования, являются важнейшими характеристиками любого помехоустойчивого кода.

Избыточность кода определяется соотношением числа проверочных знаков, добавляемых к информационной части кода для придания ему корректирующих свойств, к общей длине кода (длине информационной части):

Избыточность характеризует «накладные расходы», имеющие место при передаче сообщения. Коды, обеспечивающие заданную корректирующую спо­собность при минимально возможной избыточности, называют оптимальными.

Скорость кодахарактеризует удельное уменьшение скорости

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

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

Алгебраические коды подразделяются на два больших надкласса: блоковые коды и непрерывные коды. Для первых кодирование сводится к сопоставлению «-символьного кодового слова каждому блоку из к передаваемых информацион­ных символов. Структура формируемого кодового слова полностью определяет­ся кодируемыми информационными символами. Во втором случае кодирование осуществляется без разделения на блоки (непрерывно), но также сводится к вве­дению избыточности в передаваемую информационную последовательность.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100