Примеры решения задач по теме «Сжатие и кодирование информации».

Примеры решения задач по теме «Сжатие и кодирование информации». Закодировать по Фано сообщения, имеющие следующие вероятности: сообщение 1 2 3 4 5 6 7 вероятность 0,4 0,2 0,1 0,1 0,1 0,05 0,05 Префиксный код Шеннона-Фано В 1948-1949 гг. Клод Шеннон и Роберт Фано независимо предложили префиксный код, названный в последствие в их честь. Рассмотрим этот префиксный код на примере. Пусть имеется первичный алфавит: a1, a2, … a6 c вероятностями появления этих символов в сообщении соответственно 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания их вероятностей. Кодирование осуществляется следующим образом. Все знаки делятся на две группы, так чтобы суммы вероятностей в каждой группе были приблизительно равны. В нашем примере в первую группу попадают знаки a1, a2, все остальные знаки попадают в другую группу. Установим в ноль первый знак кодов для всех символов из первой группы, и установим равным единицы первый знак кодов всех символов из второй группы. Продолжим деление каждой группы по той же схеме до тех пор, пока не получим группы, состоящие из одного элемента. Эта процедура изображена в таблице. Полученный код удовлетворяет условию Фано, следовательно он является префиксным. Средняя длина этого кода равна Среднее количество информации на один символ первичного алфавита равно Теперь по известной нам формуле найдем избыточность кода Шеннона–Фано. То есть избыточность кода Шеннона-Фано для нашего игрушечного алфавита составляет всего около 2,5 %. Префиксный код Хаффмана В 1952 году Давид Хаффман показал, что предложенный им метод кодирования является оптимальным префиксным кодом для дискретных источников без памяти. Именно такие источники сообщений мы с вами договорились рассматривать. Алгоритм кодирования методом Хаффмана состоит из двух этапов. На первом этапе исходный алфавит на каждом шаге сокращается на один символ и на следующем шаге рассматривается новый, сокращенный первичный алфавит. На следующем этапе происходит собственно кодирование. Мы познакомимся с кодом Хаффмана на том же примере, что был рассмотрен при изучении кода Шеннона-Фано. На первом шаге алгоритма два символа исходного алфавита с наименьшими вероятностями объединяются, чтобы получить новый символ. Вероятность нового символа есть сумма вероятностей тех символов, которые в него вошли. Таким образом, получаем новый алфавит, который содержит на один символ меньше чем предыдущий. На следующем шаге алгоритма та же процедура применяется к новому алфавиту. И так до тех пор, пока в очередном алфавите не остается только двух символов. Теперь начинается второй этап алгоритма кодирования по Хаффману. Мы нумеруем символы всех промежуточных алфавитов, начиная с последнего. В нашем примере – с А4 В А4 всего два символа. Они получают соответственно номера 0 и 1. В алфавите А3 уже три символа. Причем, один из знаков алфавита А4, назовем этот знак «предок», был получен объединением двух символов алфавита А3, назовем первый из этих символов «дочкой», а второй «сыном». Номера этих двух знаков формируются следующим образом. К номеру «предка» приписываются справа 0, чтобы получить номер дочки, и 1 – чтобы получить номер «сына». Следующая итерация алгоритма по той же схеме нумерует знаки алфавита А2. Процесс останавливается при достижении первичного алфавита A – коды для знаков первичного алфавита получены. Посчитаем среднюю длину кодового слова для кода Хаффмана и нашего первичного алфавита А. Эта величина оказывается равной К(Шеннона-Фано, А, 2)! А значит и избыточность кодирования алфавита А кодом Хаффмана будет равной избыточности кодирования алфавита А кодом Шеннона-Фано. Q(Хаффман, A, 2) = К(Хаффман, А, 2) / =К(Шеннона-Фано, А, 2) / – 1 = Q(Шеннона-Фано, A, 2) ~ 0,025. Однако, в тех случаях когда вероятности символов первичного алфавита сильно разнятся, ситуация меняется. Код Хаффмана обладает существенно меньшей избыточностью.