Сигнал о некоторых понятиях кибернетики - Полетаев И.А.
Скачать (прямая ссылка):
80
лее экономным» для передачи сообщения, так как потребует наименьшего числа символов и наименьшего времени передачи.
Рассмотрим пример, приведенный Шэнноном. Пусть источник выдает четыре взаимно-независимых символа А,
В, С, D с вероятностями, соответственно, V2, V*, Ve, 4s-
Иначе говоря, источник изображается конечной схемой
(А В С °\ (4Л1)
V/, 7. '/, W
Энтропия источника, очевидно, равна
= ^ 4"4" 8"^°ё 8']==8‘ '
Рассмотрим два кода, которые переводят эти символы в двоичный алфавит— (0,1).
Код № 1:
Л-00, В — 01, С-10, D— i 1.
Код № 2:
Л-0, В-10, С — 110, ?>— 111.
Подсчитаем вероятности появлении символов нового алфавита для обоих кодов. Для этого выпишем все символы исходного алфавита в соответствии с их вероятностями или частотой их появления и соответствующие комбинации символов нового алфавита для обоих кодов, а затем подсчитаем частоты появления последних.
Исходный алфавит:
AAAABBCD
Код № 1:
00 00 00 00 .01 01 10 11
Код № 2:
0 0 0 0 10 10 110 111
Подсчитаем частоты появления (вероятности) символов.
Исходный алфавит:
рИ) = 4/8=1/2. Р(В) = *1& = Ч4, Р (С)~ */8, Р(D) — ‘/8.
Кол JVo 1;
Л(0) = п/|6. Я,(1) = 5/|в.
81
Код № 2:
^(0)=7/u=1/8. ^(1)=7/м=72-
В результате кодирования мы получили две новые конечные схемы.
Код № 1:
Код № 2:
V
1 \
(4.13)
Подсчитаем теперь энтропии на символ.
Для исходного алфавита [по формуле (4.12)]:
Я0 —?/4 едишщ1символ.
Для кода № 1:
Н\ = (n/i61°? П/16"Ъ 5/i6 log 5/I6) = 0,875.
Для кода *№ 2:
^2 = -('/2logV2 + '/2log'/2) = l.
Очевидно, что код № 2 является более экономичным, чем код № 1, так как каждый символ кода № 2 несет большее количество информации.
Закодировав сообщения кодом № 2 в алфавит (0,1), можно снова вернуться к исходному алфавиту (Л, В, С, D), воспользовавшись кодом № 1 в обратном порядке:
00 — Л, 01—В, 10 — С, 11 — D. После такого двойного перекодирования мы получим в исходном алфавите новую конечную схему с новыми вероятностями. Чтобы подсчитать эти вероятности, снова прибегнем к тому же приему и в результате получим:
Р'(А) = % Р' (B)=1U, P'(C) = 4i, P'(D) = %
Таким образом, новая конечная схема, полученная после двойного перекодирования, будет
(А В С D\ (4.14)
V/Ч ‘/4 1/4 4J
Как нетрудно видеть, энтропия на символ в новой схеме #3 равна 2, т. е. информационной емкости применяемого
алфавита.
82
Максимальная энтропия данного алфавита равна егС информационной емкости и достигается при равенстве вероятностей всех символов. Всякий конкретный код с определенной энтропией можно оценить с точки зрения его экономичности, т. е. близости его к оптимальному коду, обладающему максимальной энтропией. Для этого достаточно взять отношение значения энтропии данного кода к максимальному ее значению в том же алфавите. Это отношение носит название относительной энтропии h
h = • (4.15)
макс
Наибольшее значение относительной энтропии равно единице.
В вышеприведенном примере относительная энтропия сообщений в исходном алфавите по схеме (4.11) равна 7U: 2=7/8; после двойного перекодирования относительная энтропия стала равна 1. Таким образом, двойное перекодирование дало «сжатие» сообщений в 7/в раза, т. е. для передачи той же информации по -новому коду потребуется число символов на */в меньше, чем по исходному.
Вычитая величину относительной энтропии из ее -максимального значения, мы получим число, называемое избыточностью кода г и служащее мерой числа излишних символов в передаче
Г = \ -h = H*aHKC~H . (4.16)
Л макс
В приведенном выше примере: для исходных сообщений го=1—7/в= Ve* для кода № 1 /*1 = 1—0,875=0,125, для кода № 2 /*2=0, для окончательно полученной схемы (4.14) /*3—0.
Избыточность равиа нулю только при оптимальном коде, когда появление всех символов независимо и равновероятно, как в схеме (4.14). Неравномерность распределения вероятностей, как в схеме (4.11), или же наличие внутренних вероятностных связей (корреляции между появлениями букв) уменьшает относительную энтропию и увеличивает избыточность.
При составлении текста мы делаем по нашему произволу гораздо меньше выборов, чем число букв текста. В среднем лишь lU—*/з общего числа букв появляется случайно вследствие выбора нами смысла фразы, подбора выражений и т. д., а остальные приходят вынужденно, благодаря б* 83
