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

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

2.

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

3.

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

4.

Пусть первичный алфавит А состоит из N знаков со средней информацией
на знак I(A), а вторичный алфавит В- из М знаков со средней информацией
на знак I(В). Пусть также исходное сообщение, представленное в
первичном алфавите, содержит п знаков, а закодированное сообщение -т
знаков. Если исходное сообщение содержитIst(A) информации, а
закодированное - Ifin(B),то условие обратимости кодирования,
т.е.неисчезновения информации при кодировании, очевидно, может быть
записано следующим образом:
Смысл которого в том, что операция обратимого кодирования может
увеличить количество информации в сообщении, но не может его
уменьшить. Однако каждая из величин в данном неравенстве может быть
заменена произведением числа знаков на среднее информационное
содержание знака, т.е.:

5.

Отношение т/n, очевидно, характеризует среднее число знаков
вторичного алфавита, которое приходится использовать для
кодирования одного знака первичного алфавита - будем называть его
длиной кода или длиной кодовой цепочки и обозначим К(А,В).
Следовательно:
Минимально возможным значением средней длины кода будет:
Данное выражение следует воспринимать как соотношение оценочного характера,
устанавливающее нижний предел длины кода, однако, из него неясно, в какой степени
в реальных схемах кодирования возможно приближение К(А,В) к Kmin(A,B).

6. Первая теорема Шеннона

При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее
число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к
отношению средних информации на знак первичного и вторичного алфавитов.
Из (3.2) видно, что имеются два пути сокращения Kmin(A,B):
•уменьшение числителя - это возможно, если при кодировании учесть различие частот появления разных знаков в
сообщении, корреляции двухбуквенные, трехбуквенные и т.п. (в п.2.3. было показано, что I0>I1>I2>…>I∞);
•увеличение знаменателя - для этого необходимо применить такой способ кодирования, при котором появление
знаков вторичного алфавита было бы равновероятным, т.е. I(B)=log2M.
Для минимальной средней длины кода оказывается справедливым соотношение:
В качестве меры превышения К(А,В) над Kmin(A, B) можно ввести относительную избыточность кода (Q(A,B):
Данная величина показывает, насколько операция кодирования увеличила длину исходного
сообщения.

7.

При отсутствии помех всегда возможен такой вариант кодирования сообщения, при
котором избыточность кода будет сколь угодно близкой к нулю.
Наиболее важной для практики оказывается ситуация, когда М = 2, т.е. для
представления кодов в линии связи используется лишь два типа сигналов - технически
это наиболее просто реализуемый вариант или его отсутствие (пауза); наличие или
отсутствие отверстия; подобное кодирование называется двоичным. Знаки двоичного
алфавита принято обозначать "О" и "1", но нужно воспринимать их как буквы, а не
цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях
каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log2M = 1); тогда
из β.3)
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой
к средней информации, приходящейся на знак первичного алфавита.

8.

Особенности вторичного алфавита, используемого при кодировании:
1)элементарные сигналы (0 и 1) могут иметь одинаковые длительности
(τ0=τ1) или разные (τ0≠τ1);
2)длина кода может быть одинаковой для всех знаков первичного
алфавита (в этом случае код называется равномерным) или же коды
разных знаков первичного алфавита могут иметь различную длину
(неравномерный код);
3)коды могут строиться для отдельного знака первичного алфавита
(алфавитное кодирование) или для их комбинаций (кодирование блоков,
слов).

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

Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак
конца знака), а разделителем слов-слов -000 (признак конца слова - пробел). Довольно
очевидными оказываются следующие правила построения кодов:
Код признака конца знака может быть включен вкодбуквы, поскольку не существует отдельно
(т.е. кода всех букв будут заканчиваться00);
Коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут
восприниматься как конец знака);
Код буквы (кроме пробела) всегда должен начинаться с1;
разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется
последовательность00000 (т.е., если в конце кода встречается комбинация...000 или...0000, они
не воспринимаются как разделитель слов); следовательно , коды букв могут оканчиваться на0
или00 (до признака конца знака).
Средняя длину кода К(r,2) :
Избыточность данного кода:
Q(r,2)=4,964/4,356-1≈0,14,

10.

Пример 3.1.
а
л
м
Р
у
ы
Пусть имеется следующая таблица префиксных кодов:
10
010
00
11
0110
0111
Требуется декодировать сообщение:
00100010000111010101110000110
Декодирование производится циклическим повторением следующих действий:
•(a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
•(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
•(c) декодировать рабочее кодовое слово, очистить его;
•(d) проверить, имеются ли еще знаки в сообщении; если "да", перейти к (а).
Применение данного алгоритма дает:
Доведя процедуру до конца, получим сообщение: "мама мыла раму".
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку
нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования
префиксного кода и, в частности, наилучшего из возможных. Мы рассмотрим две схемы построения префиксных
кодов.

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

Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном .
Пусть имеется первичный алфавит А, состоящий из шести знаков a1…a6, с вероятностями появления в сообщении,
соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей. Разделим
знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными. В нашем
примере в первую группу попадута1 и а2 с суммой вероятностей 0,5 - им присвоим первый знак кода "О". Сумма вероятностей
для остальных четырех знаков также 0,5; у них первый знак кода будет "1". Продолжим деление каждой из групп на
подгруппы по этой же схеме, т.е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно
более близкими. В результате получаем:
Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является
префиксным. Средняя длина кода равна:
К(А,2) =0,3∙2 + 0,2∙2 + 0,2∙2 + 0,15∙3 + 0,1 ∙4 + 0,05∙4 = 2,45
I(A)1= 2,390 бит. Подставляя указанные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%.
Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65,
соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.