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

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

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

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



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

использовать для кодирования одного знака первичного алфавита - будем называть его длиной кода или длиной кодовой цепочки и обозначим К(А,В). Следовательно:


Минимально возможным значением средней длины кода будет:

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

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

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

Для минимальной средней длины кода оказывается справедливым соотношение:

В качестве меры превышения К(А,В) над Kmin(A, B) можно ввести относительную избыточность кода (Q(A,B):

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

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

и первая теорема Шеннона получает следующую интерпретацию:

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

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

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

Q(r,2)=4,964/4,356-1≈0,14,

производится циклическим повторением следующих действий:

(a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
(c) декодировать рабочее кодовое слово, очистить его;
(d) проверить, имеются ли еще знаки в сообщении; если "да", перейти к (а).
Применение данного алгоритма дает:

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

Р. Фано и К. Шенноном .
Пусть имеется первичный алфавит А, состоящий из шести знаков 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.