Кодирование

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

Алфавитное кодирование- кодирование при котором символы некоторого первичного алфавита кодируются комбинациями символов другого алфавита

Алфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) s:

ai Î A, bi Î В*.

Множество кодов букв V:={bi} называется множеством элементарных кодов. Алфавитное кодирование пригодно для любого множества сообщений S:F:A*®B*, a_il...a_ik=aÎA*, F(a) := bi1…bik.

Неравенство Макмиллана.

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

В качестве кодирующего алфавита часто рассматривается множество {0,1} — так называемый двоичный или бинарный алфавит.

конкатенацию кодовых слов, соответствующих каждому символу этого слова.

Код называется разделимым, если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.

Префиксным кодом называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. Любой префиксный код является разделимым.

Теоремы Шеннона (первая, обратная).

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

V ср=(С/Н-Е) букв /сек

Е – сколь угодно малая величина.

Обратная теорема.Передача букв по каналу со средней скоростью больше, чем С/Н невозможна, следовательно Vmax=С/Н

Алгоритмы Фено и Хаффмена.

Алгоритм Хаффмана . Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу