Код Шеннона-Фано

Техническое задание

Закодировать интервальным кодом фразу «Характеристики, цели и задачи системы.». Приняв частость повторения в предложенной фразе букв за их вероятности, вычислить энтропию сообщения. Вычислить энтропию передаваемого кодом сообщения. Определить избыточность передаваемой информации. Составить и описать алгоритмы кодирования и декодирования для предложенного кода. Привести закодированный вариант первой половины предложенной фразы и её декодирование.

 

Содержание

 

1 Теоретическое введение. 4

1.1 Интервальное кодирование. 4

1.2 Кодирование и декодирование интервальным кодом. 4

2 Решение поставленной задачи. 6

2.1 Вычисление энтропии сообщения. 6

2.2 Кодирование. 7

2.3 Декодирование. 9

Заключение. 12

Список использованной литературы.. 13

Приложение. 14

 

 

Теоретическое введение

Код Шеннона-Фано

 

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano). Данный метод сжатия имеет большое сходство с кодированием Хаффмана, которое появилось на несколько лет позже. Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированый символ и не является префиксом любого другого кода.