Кодирование символьной информации

Определения

Обратимое и необратимое кодирование

Алфавитное неравномерное двоичное кодирование сигналами равной длительности.

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

´! построить такую схему кодирования, в которой суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей. ) ∙ τ.

​

Неравномерный код с разделителем

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

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

´иначе они будут восприниматься как конец знака);

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

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

Частотность русских букв

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

​

условие Фано

Пример 1

Алгоритм декодирования

´a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;

´(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);

´(c) декодировать рабочее кодовое слово, очистить его;

´(d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).

​

Префиксный код Шеннона-Фано

В результате получаем:

​

Префиксный код Хаффмана