Файл: Методы кодирования данных (Физическое кодирование данных).pdf

Рис.1.4. Манчестерское кодирование

При передаче любой битовой последовательности сигнал не содержит постоянную составляющую. Длительность единичного импульса линейного сигнала t₀ равна половине битового интервала, то есть B=2N. Частота основной гармоники сигнала зависит от характера битовой последовательности и находится в диапазоне f_о=N/2 – N (Гц).

Манчестерский код используется в сетях Ethernet со скоростью передачи 10 Мбит/с (спецификация 10Bаsе-Т).

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

2.5 Потенциальный код 2B1Q

Это потенциальный код с четырьмя уровнями сигнала для кодирования данных. Название отражает суть кодирования – каждые два бита (2В) передаются за один такт сигналом определенного уровня (1Q). Линейный сигнал имеет четыре состояния.

Дибиту «00» соответствует потенциал -2,5 В (-3), «01» - потенциал -0,833 В (-1), «11» - потенциал +0,833 В (+1), «10» - потенциал +2,5 В (+3). Скорость передачи сигнала В при таком кодировании в 2 раза меньше скорости передачи информации N. На рис.1.5 изображен сигнал, соответствующий последовательности бит: 01 01 10 00.

Рис.1.5 Сигнал в коде 2B1Q

Основная частота сигнала не превышает f_о=N/4 Гц. Однако для реализации этого метода кодирования мощность передатчика должна быть выше, чтобы четыре значения потенциала четко различались приемником на фоне помех.[6]

2.6 Код MLT3 (Multi Level Transmission - 3).

Используются три уровня линейного сигнала: «-1», «0», «+1». Логической единице соответствует обязательный переход с одного уровня сигнала на другой. При передаче логического нуля изменение уровня линейного сигнала не происходит.

При передаче последовательности единиц период изменения уровня сигнала включает четыре бита. В этом случае f_о=N/4 (Гц). Это максимальная основная частота сигнала в коде MLT-3. В случае чередующейся последовательности нулей и единиц основная гармоника сигнала находится на частоте f_о=N/8 (Гц).

Рис.1.6 Сигнал в коде MLT-3

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

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

Различают два метода логического кодирования:

• избыточные коды;
• скремблирование.

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

Логический код 4В/5В заменяет исходные группы (слова) длиной 4 бита словами длиной 5 бит. В результате, общее количество возможных битовых комбинаций 25=32 больше, чем для исходных групп 24=16. В кодовую таблицу включают 16 кодовых слов, которые не содержат более двух нулей подряд, и используют их для передачи данных. Код гарантирует, что при любом сочетании кодовых слов на линии не могут встретиться более трех нулей подряд.

Остальные комбинации кода используются для передачи служебных сигналов (синхронизация передачи, начало блока данных, конец блока данных, управление передачей). Неиспользуемые кодовые слова могут быть задействованы приемником для обнаружения ошибок в потоке данных. Цена за полученные достоинства при таком способе кодирования данных - снижение скорости передачи полезной информации на 25%.

Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используются кодовые слова из 6 элементов, каждый из которых может принимать одно из трех значений. Избыточность кода 8В/6Т выше, чем кода 4В/5В, так как на 28=256 исходных комбинаций приходится 36=729 результирующих комбинаций.[6]

1. Методы кодирования в программировании

3.1 Код Шеннона

Оптимальным кодом можно определить тот, в котором каждый двоичный символ будет передавать максимальную информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, следовательно, двоичный код будет оптимальным, если в закодированном сообщении символы 0 и 1 будут встречаться одинаково часто.[2]

Рассмотрим в качестве примера оптимальное двоичное кодирование букв русского алфавита вместе с символом пробела «-». Полагаем, что известны вероятности появления в сообщении символов русского алфавита, например, приведенные в таблице.

Таблица 1.Частота букв русского языка (предположение)

К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. способ построения кода, основанный на выполнении условия равной вероятности символов 0 и 1 в закодированном сообщении. [11]

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

Для символов первой группы значение первого разряда кода присваивается равным «0», для символов второй группы – равными «1».

Далее каждая группа разделяется на две подгруппы, так чтобы суммы вероятностей знаков в каждой подгруппе были равны. Для символов первой подгруппы каждой группы значение второго разряда кода присваивается равным «0», для символов второй подгруппы каждой группы – «1». Такой процесс разбиения символов на группы и кодирования продолжается до тех пор, пока в подгруппах не остается по одному символу.

Пример кодирования символов русского алфавита приведен в табл.(2)

Таблица 2.

Пример кодирования букв русского алфавита с помощью кода Шеннона-Фано. [5]

(Таблица 2)

Анализ приведенных в таблице кодов приводит к выводу, что часто встречающиеся символы кодируются более короткими двоичными последовательностями, а редко встречающиеся - более длинными. Значит, в среднем для кодирования сообщения определенной длины потребуется меньшее число двоичных символов 0 и 1, чем при любом другом способе кодирования.

Вместе с тем процедура построения кода Шеннона-Фано удовлетворяет критерию различимости Фано. Код является префиксным и не требует специального символа, отделяющего буквы друг от друга для однозначного него декодирование двоичного сообщения.

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

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

3.2 Метод Хафмана

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

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

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

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

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

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

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.[12]

Допустим, у нас есть следующая таблица частот:

Этот процесс можно представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n₀ потомков — символы из предыдущего шага и т. д.

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

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

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что энтропия источника, независимым образом порождающего символы с указанными частотами составляет ~2,1858 бита на символ, т.е. избыточность построенного для такого источника кода Хаффмана, понимаемая, как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

Классический алгоритм Хаффмана имеет ряд существенных недостатков. Во-первых, для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Во-вторых, избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. В-третьих, для источника с энтропией, не превышающей 1, непосредственное применение кода Хаффмана не имеет смысла.

3.3 Адаптивное сжатие

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.[1,12]