Источник генерирует знак x1 и x2с вероятностями р(x1)=0,33 и р(x2)=0,67. Построить коды Шеннона – Фано и Хаффмана для для последовательности из трех знаков. Каково среднее число символов на знак? Сравнить с энтропией.
266
ОТВЕТЫ
Строить коды для алфавита из двух символов немного странно - и так понятно, что получатся 0 и 1, и все эти кодирования бессмысленны.
Код Шеннона - Фано: делим знаки на две части, чтобы суммарные вероятности появления символов частей были максимально близки (тут в каждой части всего один символ - иначе никак). Одной приписываем 0, другой 1. На этом всё кончилось.
Код Хаффмана: выбираем два символа с наименьшими вероятностями, у одного постфикс 0, у другого 1. Объединяем в одну вершину, и она осталась одна. Конец.
В среднем 1 символ - 1 бит.
Энтропия -∑ p ㏒₂ p = -0.33 log 0.33 - 0.67 log 0.67 = 0.915 бит на символ.
Учитывая, что энтропия всегда не превосходит среднюю длину кода, тут сошлось.
Код Шеннона - Фано: делим знаки на две части, чтобы суммарные вероятности появления символов частей были максимально близки (тут в каждой части всего один символ - иначе никак). Одной приписываем 0, другой 1. На этом всё кончилось.
Код Хаффмана: выбираем два символа с наименьшими вероятностями, у одного постфикс 0, у другого 1. Объединяем в одну вершину, и она осталась одна. Конец.
В среднем 1 символ - 1 бит.
Энтропия -∑ p ㏒₂ p = -0.33 log 0.33 - 0.67 log 0.67 = 0.915 бит на символ.
Учитывая, что энтропия всегда не превосходит среднюю длину кода, тут сошлось.
15
Отв. дан
Оксана
Для написания вопросов и ответов необходимо зарегистрироваться на сайте
Другие вопросы в разделе - Математика
Марк
эссе на тему Как я понимаю что такое Вирус ...
2018-09-25 00:00:00
Екатерина
Оцените информационный объём моноаудиофайла длительностью 1 с при частоте ...
2018-09-25 00:00:00
Никита
Перевести число 40 из десятичной системы счисления в четверичную ...
2018-09-25 00:00:00
Gasius
Как узнать сколько значкщих нулей в двоичной записи восьмиричного ...
2018-09-25 00:00:00