?

Log in

No account? Create an account

Entries by category: техника

В предыдущей части мы на ровном месте переизобрели арифметическое сжатие и получили формулу среднего количества бит на символ при оптимальном сжатии для случая статического разбиения на интервалы. Внезапно она внешне совпала с Шенноновской формулой информационной энтропии.

Сам Шеннон получил свою знаменитую формулу совсем иначе. Он рассматривал источники, выдающие сообщения с вероятностями Pi, и искал такую функцию H, которая бы выражала объем информации в сообщении, была бы мерой неопределенности.

К искомой функции он предъявлял следующие требования:
1. H должна быть непрерывной функцией от Pi.
2. Если все сообщения равновероятны, т.е. Pi = 1/N, то H(N) должна монотонно возрастать c ростом N: чем больше вариантов разных равновероятных сообщений, тем больше информации несет одно сообщение.
3. Если сообщение разбивается на несколько последовательно идущих, то мера Н информации в нем должна быть взвешенной суммой значений Н для частей. Например, если нам нужно передать сегодняшнее число, то не важно, пошлем мы месяц и день в одном сообщении или сначала месяц, а потом день, количество переданной информации должно быть одинаковым в обоих вариантах. Если вероятности и сообщения представить в виде дерева, где в узлах стоят сообщения, а дугам приписаны вероятности посылки следующих сообщений (например, из корня идут дуги к вариантам первого бита сообщения, из них - к вариантам второго бита и т.д., примерно как при построении дерева для кодов Хаффмана),

то
H(узла) = сумма по исходящим веткам от: P(ветки)*H(ветки).

Оказывается, этих требований достаточно, чтобы искомую функцию вывести.Read more...Collapse )