Спирина, М.С. Дискретная математика

Реальная ценность понятия энтропии определяется в первую очередь тем, что выражаемая им «степень неопределенности» опы­ тов оказывается во многих случаях именно той характеристикой, которая играет роль в разнообразных процессах, встречающихся в природе и технике и так или иначе связанных с передачей и хра­ нением каких-либо сообщений. Ф о р м у л а Х ар т л и . Итак, в передачу сообщения входит процесс выбора, который осуществляет как отправитель, так и получа­ тель сообщения. Этот процесс выбора можно измерить количе­ ственно. Пусть нам необходимо передать одно из восьми возможных сообщений: А, В , С, D, Е, F, /, Н. Условимся для удобства поста­ вить в соответствие каждому сообщению двоичное число и пред­ ставим результат в виде графа (рис. 6.1), где каждому сообщению соответствует свой набор сигналов. Тогда один двоичный сигнал позволяет выбрать одно из двух сообщений: 2 = 21. Два двоичных сигнала позволяют выбрать одно из четырех сообщений: 4 = 22. Набор из трех сигналов — одно из восьми сообщений: 8 = 23, из шести — одно из шестидесяти четы­ рех сообщений: 64 = 2б, из т двоичных сигналов — одно из 2™ сообщений. И наоборот, для набора N= 2т сообщений нужно иметь не менее т сигналов. Важно знать, что одно из тридцати двух сообщений выбирается с помощью пяти сигналов. Поэтому для распознавания одного определенного сообщения из ./Vвозможных сообщений требуется т - log2N сигналов. Так, при j V = 100 требуется т = log2100 = log2102 = 21og210 = = 2 • 3,32 = 6,64 = 7 знаков. Следовательно, для выбора одного из N вариантов нужна информация в J бит: J = log2M Эту формулу в 1928 г. предложил американец Хартли. В качестве единицы измерения используется бит. Таким образом, для выбора из 8 знаков потребуется 3 бита. Ф орм ул а Ш е н н о н а . Если сообщение появляется с одинаковой частотой, то полученные выводы единственно возможные. Если относительная частота сообщений одинакова, то для одного из ® ® © ® ® ® ® ® 000 001 010 011 100 101 ПО 111 А В с D Е F / н 000 001 010 011 100 101 по 111 Рис. 6.1. Двоичное дерево для восьми символов 302