ВУЗы и колледжи

Вопрос по смыслу энтропии информации по формуле Шеннона

Видел много примеров подсчёта энтропии для вероятностей возникновения 4-х символов на подобии
p1 = 0.5; p2 = 0.25; p3 = 0.125; p4 = 0.125
Вроде бы всё логично, первый символ встречается чаще, поэтому его можно закодировать одним битом, второй - двумя и 3 и 4 с помощью трёх бит. При этом сумма -Pi * log2(Pi) при i от 1 до 4 будет матожиданием количества передаваемой информации для одного символа. И вроде как сначала считал энтропию средним количеством передаваемой информации для кодирования одного символа

Однако, почему такая схема будет работать для других значений, например:
p1 = 0.75, p2 = 0.125, p3 = 0.125

Вроде как по формуле подразумевается, что для кодирования p2 и p3 будет использовано 3 бита, однако можно же закодировать первый символ одним битом, а 2 и 3 двумя и это будет явно оптимальнее. Однако, ещё интереснее, что при таком случае матожидание будет
0.75 * 1 + 0.125 * 2 + 0.125 * 2 = 1.25

А энтропия будет примерно:
0.75 * 0.415 + 0.125 * 3 + 0.125 * 3 = 1.06125

Т. е., результат получился оптимальнее за счёт малого количества бит, нужного для кодирования символа (0.75 * 0.415 = 0.31125) 1.
Теперь вопрос: как понять физический смысл данной формулы для такого случая, если мы всё равно не сможем закодировать символ 1 менее, чем 1 битом?
И если речь идёт не о битах, тогда второй вопрос: почему log2?
Виталий Евстигнеев
Виталий Евстигнеев
94
"По формуле подразумевается, что символы кодируются 3 битами" - почему? Формула дает энтропию меньше 2, это и есть средняя длина кода.
Онд Олени Е.с.п.
Онд Олени Е.с.п.
96 935
Лучший ответ
Виталий Евстигнеев Т. к. -log2(0.125) = -log2(1/8) = 3
Вы что-то придумали, из примера, в котором 4 символа кодируется, что если вероятность равна 0.125, то для кодирования нужно 3 бита. Это же не так, ведь будь у вас всего два символа с любой вероятностью, то каждому по 1 биту бы хватало. Например вероятность 0.875 и 0.125.
Просто при кодировании 4 символов получается, что допустим символы A, B, C, D
A - 0
B - 11
для кодирования C и D используется по 3 бита, так как, если для C использовать 2 бита, а это будет вариант только с
10, так как 00 и 01 будет невозможно однозначно определить, что значат
00 - это будет либо AA, либо C, если для C использовалось 00.
А при использовании 01 для кодировки C - будет проблема с сообщением типа
01111..01 - будет ли это CBBB.. C или же ABBB..C или ABBB.. A1 узнать по мере поступления сообщения будет сразу невозможно, а только после подсчёта честности числа единиц в каждой последовательности единиц.
Но если использовать 10 для C, то для D будет невозможно определить однозначный код.
Код не должен будет начинаться ни с 0, ни с 11, ни с 10, а других вариантов просто нет никаких.
Если же всего три символа возможных в сообщении, то такой проблемы не возникает.

Смысл формулы в том, что приход символа, у которого низкая частота несёт больше информации, чем символа, у которого высокая частота в сообщении.
Энтропия - это не информация, а противоположное ей понятие.
Ирина Мустафина
Ирина Мустафина
23 232

Похожие вопросы