Проблемы передачи информации (лекция 3)

Неравномерный код
Если заданы четыре сообщения А1, А2, А3, А4 с вероятностями
Р(А1)=1/2, Р(А2)=1/4, Р(А3)=Р(А4)= 1/8.

Идея метода Шеннона-Фано
Идея этого метода заключалась в том, чтобы заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами.
Метод Шеннона-Фано относится к вероятностным методам сжатия

Схема метода Шеннона-Фано

Если заданы четыре сообщения А1, А2, А3, А4 с вероятностями
Р(А1)=1/2, Р(А2)=1/4, Р(А3)=Р(А4)= 1/8.
Идея метода Шеннона-Фано

Идея метода Шеннона-Фано

Кодовые деревья
Чем более вероятно сообщение, тем быстрее оно образует «самостоятельную» группу и тем более коротким словом оно будет закодировано. Эго обстоятельство обеспечивает высокую экономность кода Фано.

Кодовые деревья
В любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков.
Чтобы код удовлетворял следующему требованию:
- всякая последовательность кодовых символов может быть единственным образом разбита на кодовые слова
Коды для которых последнее требование выполнено,
называются однозначно декодируемыми (иногда их называют
кодами без зanятой).
Наиболее простыми и употребимыми кодами без запятой являются так называемые nрефuкcные коды, обладающие тем свойством. что никакое кодовое слово не является началом (префиксом) другого кодового слова. Если код префиксный, то, читая кодовую запись подряд от начала. мы всегда сможем
разобраться, где кончается одно кодовое слово и начинается следующее.

Префиксный код
Префиксный код называется полным если добавление к нему нового слова не нарушает свойство префиксности.
Подумать является ли двоичный код Фано является полным кодом.

Однозначно декодируемый код, который не является префиксным
{1,10}, {01, 10, 011}
Не существует префиксного кода с длинами кодовых слов 1,1,2.
Существует ли префиксный код с заданными длинами слов?

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Неравенство Крафта

Метод Шеннона построения префиксного кода с заданными длинами слов

Метод Шеннона построения префиксного кода с заданными длинами слов

Метод Шеннона построения префиксного кода с заданными длинами слов

Метод Шеннона построения префиксного кода с заданными длинами слов

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Свойства оптимальный код

Алгоритм Хаффмана

Алгоритм Хаффмана

Алгоритм Хаффмана