Файл: Изучение основных методов кодирования данных..pdf

2.3 Конкретные методы кодирования

1. Алфавитное неравномерное двоичное кодирование

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

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

Очевидно, возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования – важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв. Проще всего этого достичь, если коды будут разграничены разделителем – некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова – пробел). Довольно очевидными оказываются следующие правила построения кодов:

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

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

- код буквы (кроме пробела) всегда должен начинаться с 1;

- разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация …000 или …0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

Длительность передачи каждого отдельного кода t_i, очевидно, может быть найдена следующим образом:

где k_i – количество элементарных сигналов (бит) в коде символа i.

В соответствии с приведенными выше правилами получаем следующую таблицу кодов (таблица 1).

Таблица 1 - Таблица кодов [15, c. 116]

Теперь по формуле можно найти среднюю длину кода K⁽²⁾ для данного способа кодирования:

Поскольку для русского языка, I₁(r)=4,356 бит, избыточность данного кода составляет:

;

это означает, что при данном способе кодирования будет передаваться приблизительно на 12% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение K⁽²⁾ = 4,716, что при I₁(e) = 4,036 бит приводят к избыточности кода Q(e) = 0,144.

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

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

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода. Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных [15, c. 117].

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

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

Таблица 2 - Таблица кодов русских букв

Средняя длина кода оказывается равной K(2) = 4,395; избыточность кода Q(r) = 0,00887, т.е. менее 1%.

Таким образом, можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Не следует думать, что он представляет число теоретический интерес. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.

Кодирование энтропии - кодирования словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее короткие коды [13, c. 73].

2. Равномерное алфавитное двоичное кодирование.

В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное I₀. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: K⁽²⁾ log₂N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). При этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.

Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе. Исходный алфавит должен содержать не более 32-х символов; тогда K⁽²⁾ = log₂ 32 = 5, т.е. каждый знак содержит 5 бит информации. Условие N≤32, очевидно, выполняется для языков, основанных на латинском алфавите (N = 27 = 26+ «пробел»), однако в русском алфавите 34 буквы (с пробелом) – именно по этой причине пришлось «сжать» алфавит (как в коде Хаффмана) и объединить в один знак «е» и «ё», а также «ь» и «ъ». После такого сжатия N = 32, однако, не остается свободных кодов для знаков препинания, поэтому в телеграммах они отсутствуют или заменяются буквенными аббревиатурами; это не является заметным ограничением, поскольку, как указывалось выше, избыточность языка позволяет легко восстановить информационное содержание сообщения. Избыточность кода Бодо для русского языка Q^(r) = 0,129, для английского Q^(e) = 0,193 [13, c. 75].

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

26*2=52 букв латинского алфавита (с учетом прописных и строчных);

33*2=66 букв русского алфавита;

цифры 0...9 – всего 10;

знаки математических операций, знаки препинания, спецсимволы = 20.

Получаем, что общее число символов N=148. Теперь можно оценить длину кодовой цепочки: K⁽²⁾≥log₂148≥7,21. Поскольку K⁽²⁾ должно быть целым, очевидно, K⁽²⁾= 8. Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие цепочка из 8 двоичных разрядов (8 бит). Такая цепочка получила название байт, а представление таким образом символов – байтовым кодированием.

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном символе алфавита при их равновероятном распределении. Этот способ измерения количества информации называется также объёмным. Пусть имеется некоторое сообщение (последовательность знаков); оценка количества содержащейся в нём информации согласно рассмотренному ранее вероятностному подходу (с помощью формулы Шеннона) даёт I_вер, а объемная мера пусть равна Iоб; соотношение между этими величинами: I_вер ≤ I_об.

Собственно, байт установлен как единица измерения количества информации в интернациональной системе единиц СИ. 1 байт = 8 бит. Применение 8-битных цепочек дает возможность зашифровать 28=256 символов, что превосходит оцененное выше N и, следственно, дает возможность применить остальную часть кодовой таблицы для изображения дополнительных символов [13, c. 76].

Однако слишком мало только условиться об некоторой длине кода. Понятно, что методов кодирования, т.е. вариантов сравнения знакам первичного алфавита восьмибитных цепочек, множество. По данной причине для сопоставимости технических устройств и предоставления потенциала обмена информацией между многочисленными пользователями требуется состыковка кодов. Подобная состыковка исполняется в форме типизации кодовых таблиц. Начальным таким интернациональным стандартом, который использовался на и телекоммуникационных системах используется международный байтовый код огромных вычислительных машинах, был EBCDIC> (Extended Binary Coded Decimal Interchange Code) – «расширенная двоичная кодировка десятичного кода обмена». В персональных компьютерах ASCII (American Standard Code for Information Interchange – «американский стандартный код обмена информацией»). Он регулирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, т.е. первый бит всех кодов 0). В данную часть определяются коды прописных и строчных английских букв, цифры, знаки препинания и математических операций, а также определенные заправляющие коды (номера от 0 до 31). Ниже представлены некоторые ASCII-коды (таблица 3).