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

.

Условиям:

,

при удовлетворяет только одна функция - :

.

Рассмотрим опыт А, состоящий из опытов и имеющих вероятности . Тогда общая неопределенность для опыта А будет равна:

Это последнее число будем называть энтропией опыта и обозначать через .

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

Мы рассмотрим здесь лишь простейший случай сообщений, записанных при помощи некоторых п «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р1, р2, … …, рп, где, разумеется, р1 + р2 + … + рп = 1, при котором вероятность pi проявления i-й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.

Мы будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число т элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве» сообщения. Каждому двоичному коду для п-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего п, при помощи вопросов, на которые отвечается лишь «да» (1) или «нет» (0) , что и приводит нас к двоичному коду. При заданных вероятностях р1, р2, … …, рп отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим.

Прежде всего, среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p1 log p1 – p2 log p2 - … - pn log pn – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита.

Если вероятности р1, р2, … …, рп не все равны между собой, то Н < log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв.

1.2 Классификация назначения и способы представления кодов

Коды можно классифицировать по oc различным oc признакам:^[5]

1. oc По oc основанию oc (количеству oc символов oc в oc алфавите): oc бинарные oc (двоичные oc m=2) oc и oc не oc бинарные oc (m oc № oc 2).

2. oc По oc длине oc кодовых oc комбинаций oc (слов): oc равномерные, oc если oc все oc кодовые oc комбинации oc имеют oc одинаковую oc длину oc и oc неравномерные, oc если oc длина oc кодовой oc комбинации oc не oc постоянна.

3. oc По oc способам oc передачи: oc последовательные oc и oc параллельные; oc блочные oc - oc данные oc сначала oc помещаются oc в oc буфер, oc а oc потом oc передаются oc в oc канал oc и oc бинарные oc непрерывные.

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

5. oc В oc зависимости oc от oc назначения oc и oc применения oc условно oc можно oc выделить oc следующие oc типы oc кодов:

Внутренние oc коды oc - oc это oc коды, oc используемые oc внутри oc устройств. oc Это oc машинные oc коды, oc а oc также oc коды, oc базирующиеся oc на oc использовании oc позиционных oc систем oc счисления oc (двоичный, oc десятичный, oc двоично-десятичный, oc восьмеричный, oc шестнадцатеричный oc и oc др.). oc Наиболее oc распространенным oc кодом oc в oc ЭВМ oc является oc двоичный oc код, oc который oc позволяет oc просто oc реализовать oc аппаратное oc устройства oc для oc хранения, oc обработки oc и oc передачи oc данных oc в oc двоичном oc коде. oc Он oc обеспечивает oc высокую oc надежность oc устройств oc и oc простоту oc выполнения oc операций oc над oc данными oc в oc двоичном oc коде. oc Двоичные oc данные, oc объединенные oc в oc группы oc по oc 4, oc образуют oc шестнадцатеричный oc код, oc который oc хорошо oc согласуется oc с oc архитектурой oc ЭВМ, oc работающей oc с oc данными oc кратными oc байту oc (8 oc бит).

Коды oc для oc обмена oc данными oc и oc их oc передачи oc по oc каналам oc связи. oc Широкое oc распространение oc в oc ПК oc получил oc код oc ASCII oc (American oc Standard oc Code oc for oc Information oc Interchange). oc ASCII oc - oc это oc 7-битный oc код oc буквенно-цифровых oc и oc других oc символов. oc Поскольку oc ЭВМ oc работают oc с oc байтами, oc то oc 8-й oc разряд oc используется oc для oc синхронизации oc или oc проверки oc на oc четность, oc или oc расширения oc кода. oc В oc ЭВМ oc фирмы oc IBM oc используется oc расширенный oc двоично-десятичный oc код oc для oc обмена oc информацией oc EBCDIC oc (Extended oc Binary oc Coded oc Decimal oc Interchange oc Code). oc В oc каналах oc связи oc широко oc используется oc телетайпный oc код oc МККТТ oc (международный oc консультативный oc комитет oc по oc телефонии oc и oc телеграфии) oc и oc его oc модификации oc (МТК oc и oc др.).

При oc кодировании oc информации oc для oc передачи oc по oc каналам oc связи, oc в oc том oc числе oc внутри oc аппаратным oc трактам, oc используются oc коды, oc обеспечивающие oc максимальную oc скорость oc передачи oc информации, oc за oc счет oc ее oc сжатия oc и oc устранения oc избыточности oc (например: oc коды oc Хаффмана oc и oc Шеннона-Фано), oc и oc коды oc обеспечивающие oc достоверность oc передачи oc данных, oc за oc счет oc введения oc избыточности oc в oc передаваемые oc сообщения oc (например: oc групповые oc коды, oc Хэмминга, oc циклические oc и oc их oc разновидности).

Коды oc для oc специальных oc применений oc - oc это oc коды, oc предназначенные oc для oc решения oc специальных oc задач oc передачи oc и oc обработки oc данных. oc Примерами oc таких oc кодов oc является oc циклический oc код oc Грея, oc который oc широко oc используется oc в oc АЦП oc угловых oc и oc линейных oc перемещений. oc Коды oc Фибоначчи oc используются oc для oc построения oc быстродействующих oc и oc помехоустойчивых oc АЦП.

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

Матричное представление кодов. Используется для представления равномерных n - значных кодов. Для примитивного (полного и равномерного) кода матрица содержит n - столбцов и 2n - строк, т.е. код использует все сочетания. Для помехоустойчивых (корректирующих, обнаруживающих и исправляющих ошибки) матрица содержит n - столбцов (n = k+m, где k-число информационных, а m - число проверочных разрядов) и 2k - строк (где 2k - число разрешенных кодовых комбинаций). При больших значениях n и k матрица будет слишком громоздкой, при этом код записывается в сокращенном виде. Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и т.д.

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

1.3 Метод кодирования Хаффмана

Метод кодирования или сжатия информации oc на oc основе oc двоичных oc кодирующих oc деревьев oc был oc предложен oc Д.А. oc Хаффманом oc в oc 1952 oc году oc задолго oc до oc появления oc современного oc цифрового oc компьютера.^[6] oc Обладая oc высокой oc эффективностью, oc он oc и oc его oc многочисленные oc адаптивные oc версии oc лежат oc в oc основе oc многих oc методов, oc используемых oc в oc современных oc алгоритмах oc кодирования. oc Код oc Хаффмана oc редко oc используется oc отдельно, oc чаще oc работая oc в oc связке oc с oc другими oc алгоритмами oc кодирования. oc Метод oc Хаффмана oc является oc примером oc построения oc кодов oc переменной oc длины, oc имеющих oc минимальную oc среднюю oc длину. oc Этот oc метод oc производит oc идеальное oc сжатие, oc то oc есть oc сжимает oc данные oc до oc их oc энтропии, oc если oc вероятности oc символов oc точно oc равны oc отрицательным oc степеням oc числа oc 2.

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

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

Алгоритм oc основан oc на oc том, oc что oc некоторые oc символы oc из oc стандартного oc 256-символьного oc набора oc в oc произвольном oc тексте oc могут oc встречаться oc чаще oc среднего oc периода oc повтора, oc а oc другие oc - oc реже. oc Следовательно, oc если oc для oc записи oc распространенных oc символов oc использовать oc короткие oc последовательности oc бит, oc длиной oc меньше oc 8, oc а oc для oc записи oc редких oc символов oc - oc длинные, oc то oc суммарный oc объем oc файла oc уменьшится. oc В oc результате oc получается oc систематизация oc данных oc в oc виде oc дерева oc («двоичное oc дерево»).

Пусть oc A={a1,a2,...,an} oc - oc алфавит oc из oc n oc различных oc символов, oc W={w1,w2,...,wn} oc - oc соответствующий oc ему oc набор oc положительных oc целых oc весов. oc Тогда oc набор oc бинарных oc кодов oc C={c1,c2,...,cn}, oc такой oc что:

- ci oc не oc является oc префиксом oc для oc cj, oc при oc i!=j; oc минимальна oc (|ci| oc длина oc кода oc ci) oc называется oc минимально-избыточным oc префиксным oc кодом oc или oc иначе oc кодом oc Хаффмана.

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

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

Пусть oc Т- oc бинарное oc дерево, oc А=(0,1)- oc двоичный oc алфавит oc и oc каждому oc ребру oc Т-дерева oc приписана oc одна oc из oc букв oc алфавита oc таким oc образом, oc что oc все oc ребра, oc исходящие oc из oc одной oc вершины, oc помечены oc различными oc буквами. oc Тогда oc любому oc листу oc Т-дерева oc можно oc приписать oc уникальное oc кодовое oc слово, oc образованное oc из oc букв, oc которыми oc помечены oc ребра, oc встречающиеся oc при oc движении oc от oc корня oc к oc соответствующему oc листу. oc Особенность oc описанного oc способа oc кодирования oc в oc том, oc что oc полученные oc коды oc являются oc префиксными.

Очевидно, oc что oc стоимость oc хранения oc информации, oc закодированной oc при oc помощи oc Т-дерева, oc равна oc сумме oc длин oc путей oc из oc корня oc к oc каждому oc листу oc дерева, oc взвешенных oc частотой oc соответствующего oc кодового oc слова oc или oc длиной oc взвешенных oc путей: oc , oc где oc - oc частота oc кодового oc слова oc длины oc oc во oc входном oc потоке. oc Рассмотрим oc в oc качестве oc примера oc кодировку oc символов oc в oc стандарте oc ASCII. oc Здесь oc каждый oc символ oc представляет oc собой oc кодовое oc слово oc фиксированной(8 oc бит) oc длины, oc поэтому oc стоимость oc хранения oc определится oc выражением oc , oc где oc W- oc количество oc кодовых oc слов oc во oc входном oc потоке.

Поэтому oc стоимость oc хранения oc 39 oc кодовых oc слов oc в oc кодировке oc ASCII oc равна oc 312, oc независимо oc от oc относительной oc частоты oc отдельных oc символов oc в oc этом oc потоке. oc Алгоритм oc Хаффмана oc позволяет oc уменьшить oc стоимость oc хранения oc потока oc кодовых oc слов oc путем oc такого oc подбора oc длин oc кодовых oc слов, oc который oc минимизирует oc длину oc взвешенных oc путей. oc Будем oc называть oc дерево oc с oc минимальной oc длиной oc путей oc деревом oc Хаффмана.

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