Алгоритмы цифрового кодирования

К линейным сигналам предъявляются следующие требования:

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

- устойчивую работу цепи стабилизации выходной мощности оптического передатчика;

- код линейного сигнала должен обеспечивать возможность выделения колебания тактовой частоты, необходимой для нормальной работы тактовой синхронизации;

- код линейного сигнала должен обладать максимальной помехоустойчивостью, которая позволяет получать при прочих равных условиях максимальную длину участка регенерации;

- код линейного сигнала должен обладать избыточностью, которая позволяет по нарушениям правила образования судить о возникновении ошибок;

- код линейного сигнала должен быть простым для практической реализации преобразователей кода.

Биполярный метод

При биполярном методе символу 0 соответствует нулевое значение сигнала на передаче, а символу 1-попеременно значения +А или -А. В связи с этим в американской литературе его называют AMI (Alternate Mark Inversion) методом. График передаваемого сигнала показан на рисунке 4.23. Спектральная плотность мощности случайной последовательности сигналов данных относится к одному из типов, приведенных на рисунке 4.23 (кривая 2). Она обращается в нуль на нулевой частоте и на двойной частоте Найквиста 2/N. Таким образом, возможна передача и по линиям, содержащим разделительные трансформаторы. Максимум спектральной плотности прямоугольных импульсов располагается несколько ниже частоты fN.

Псевдотроичный метод

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

Парно-селективный троичный код

Алгоритмы замен вида BNZS, описанные в предыдущем подразделе, представляют собой примеры выбора кодов в троичном кодовом пространстве с целью увеличения содержания хронирующей составляющей двоичного сигнала. Еще одним примером является парно-селективный троичный код PST.

Код Хаффмана.

Алгоритм Хаффмана — адаптивный простой алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m₂ с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов:

Построение оптимального кодового дерева.

Построение отображения код-символ на основе построенного дерева.

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). ^[1]

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

Выбираются два свободных узла дерева с наименьшими весами.

Создается их родитель с весом, равным их суммарному весу.

Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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