Доказательство лемм

Доказательство. Докажем данное утверждение индукцией по длине последовательности к. Для к = 1 утверждение очевидно. Пусть уже доказано, что число двоичных слов длины к равно 2к. Все двоичные слова длины к + 1 делятся на два типа: начинающиеся с нуля и начинающиеся с единицы. Выпишем все слова длины к, в силу предположения индукции их 2. Припишем к каждому из них слева ноль. Ниже выпишем все слова длины к снова и припишем к ним слева единицу. Так мы записали все слова длины к + 1. Таким образом, число последовательностей длины к + 1 равно 2к + 2к = 2к + '. Что и требовалось доказать.

Двоичным кодированием множества N называется отображение, ставящее в соответствие каждому элементу множества N его двоичный код — последовательность нулей и единиц. Кодирование называется однозначным, если коды различных элементов множества N различны.

Лемма 2. Множество N допускает однозначное двоичное кодирование с длинами кодов, не превосходящими к в том и только в том случае, когда число элементов множества N не превосходит 2 к.

Доказательство. Одно множество можно однозначно отобразить в другое множество, только если число элементов первого множества не превышает числа элементов второго множества. Так как по лемме 1 число двоичных слов длины к равно 2к, то утверждение леммы доказано.

Согласно леммам 1 и 2, длина кода при двоичном кодировании одного символа из алфавита мощности N = 2к (то есть алфавита, состоящего ровно из N различных символов) равна к. Это позволяет давать эффективные оценки на минимально необходимый объем памяти компьютера для запоминания различного рода данных. Так, кодирование сообщений на английском языке можно осуществлять с помощью алфавита, состоящего из 32 = 25 различных символов (к 26 латинским буквам необходимо добавить символ пробела, точку, запятую и еще три символа по желанию). Один символ при равномерном двоичном кодировании (одинаковой длине двоичного слова для каждого символа нашего алфавита) тогда будет занимать 5 бит памяти, а не 8, как при АSCII-кодировании текстовой информации вообще.

Формула Хартли. Количество информации, которое вмещает один символ N-элементного алфавита, равно lоgгN

По-другому это же утверждение можно сформулировать так. Количество информации, полученной при выборе одного предмета из N равнозначных предметов, равно 1оg2N. То есть именно такое количество информации необходимо для устранения неопределенности из N равнозначных вариантов.

Доказательство. Для алфавита из N различных символов можно составить Nm всех возможных слов длины т (доказывается аналогично лемме 1). Пусть к таково, что

2 к < Nm <= 2 к+1 (*)

То есть количество информации, содержащееся в одном символе этого алфавита, заключено между к/т и (k + 1)/m. Логарифмируя неравенства (*), получаем к< т1оg2N < (к + 1).

Разделив эти неравенства на т, делаем вывод, что разность между количеством информации, которое несет один символ N-элементного алфавита, и 1оg2N не превосходит 1/m для любого т. Значит, при оптимальном двоичном кодировании такого символа (которое при росте т достижимо с какой угодно точностью) средняя длина слова составит 1оgгN.

Для доказательства утверждения во второй формулировке будем отгадывать один предмет из N возможных не один раз, а т, или отгадывать набор из т предметов, каждый из которых принадлежит множеству N различных, но равнозначных предметов (а предметы в наборе могут и совпадать). Тогда среднее число вопросов, необходимое для отгадывания одного предмета из набора, будет отличаться от lоgгN не более чем на 1/т. Утверждение доказано.