Введение в кибернетику - Эшби У.Р.
Скачать (прямая ссылка):
9/17
ЭНТРОПИЯ
263
жет быть передано никаким каналом с меньшей пропускной способностью К
Быть может, и без того было достаточно очевидно, что каналы с высокой скоростью передачи могут сообщать больше, чем каналы с низкой скоростью. В этой теореме важен, во-первых, ее общий характер (ибо она не имеет в виду никаких особых механизмов и поэтому одинаково применима к телеграфной линии, к нервным волокнам и к разговору) и, во-вторых, ее количественная строгость. Так, если бы наш пруд с насекомыми был расположен далеко среди холмов, то мог бы возникнуть вопрос о возможности передачи сообщений с помощью дымовых сигналов. Предположим, что отдельный клуб дыма можно пускать или не пускать каждые четверть минуты, но не быстрее. Энтропия на символ равна здесь 1 биту, и пропускная способность канала равна поэтому 4 битам в минуту. Поскольку 4 больше, чем 2,53, канал может передавать сообщения о положении насекомого и можно найти код, который будет переводить положения в клубы дыма, несущие эту информацию.
Сам Шеннон построил пример, чрезвычайно ярко демонстрирующий точность этого количественного закона. Предположим, что некоторый источник выдает буквы А, В, С, й с частотами, относящимися друг к другу соответственно как 4:2:1:1, причем последовательные сим-
1 Имеется в виду, конечно, передача без накопления задержки. В силу § 8/13 любая информация может быть передана по каналу, обладающему ненулевой пропускной способностью, но, возможно, со значительным замедлением. Так, в принципе мы могли бы передавать события о положении насекомого, даже если бы пускали или не пускали клуб дыма (см. пример ниже в этом параграфе) всего лишь раз в сутки; но при этом очередь из еще не переданных сообщений росла бы с катастрофической быстротой (хотя каждое отдельное сообщение рано или поздно было бы передано). Смысл теоремы Шеннона состоит именно в том, что она говорит о передачах с рассасывающейся очередью еще не переданных сообщений на приемном конце (более точно, имеется некоторая минимальная длина такой очереди и для каждого момента времени с вероятностью 1 наступит вслед за ним другой момент, когда длина очереди не будет превосходить своего минимального значения).— Прим. ред.
264 ГЛАВА 9. НЕПРЕКРАЩАЮЩАЯСЯ ПЕРЕДАЧА* 9/17
волы независимы. Типичным отрезком такой последовательности будет... BAABDAAAABCABAADA.... В состоянии равновесия относительные частоты символов Л, В, С
lill
и D суть соответственно -?7, -j, Y' ТГ» и ЭНТР0ПИЯ равна з
1 j бита на шаг (т. е. на букву).
Канал, который может выдавать на каждом шаге любое из четырех состояний без ограничений, имел бы пропускную способность в 2 бита на шаг. Согласно теореме Шеннона, должен существовать такой код, который позволит этому последнему каналу (с пропускной способностью 2 бита на шаг) передавать указанную последовательность (с энтропией 1~ бита на шаг) так, что сообщение любой длины потребует меньшего числа шагов, и притом в отношении 2к1|,т. е. 8к 7. Этот код,
изобретенный Шенноном, сводится к следующему. Сна-чала сообщение кодируется посредством преобразования
I А В С D J 0 10 110 111'
например, приведенное сообщение кодируется так:
\B.AAB.D..AAAAB.C..AB.AAD. . А
4loooioi11оо ooioiiooioooi 1 1 о;
Теперь разделим нижнюю строку на пары и перекодируем их в другое множество букв:
| 00 01 10 11 I Е F G Н'
Эти коды однозначно переводят любое сообщение из букв от А до D в буквы от ? до Я и обратно. Теперь мы можем констатировать следующий замечательный факт. ЕСЛИ, МЫ возьмем типичное множество из восьми первоначальных букв (где каждая будет представлена с характерной частотой)f то окажется, что они могут быть
9/13
ЭНТРОПИЯ
265
переданы с помощью семи новых букв: ААААВ.В.С. .О. . |0000101011011 1.
Тем самым демонстрируется возможность того сокращения, которое было количественно предсказано энтропией первоначального сообщения!
Упр. 1. Покажите, что описанное кодирование устанавливает взаимно однозначное соответствие между посылаемым и получаемым сообщением (за исключением возможной неопределенности первой буквы).
Упр. 2. Печатный английский текст имеет энтропию примерно в 10 битов на слово. Мы можем читать примерно по 200 слов в минуту. Укажите нижнюю границу пропускной способности канала зрительного нерва.
Упр. 3. Пианист может каждым из десяти пальцев ударить одну из трех клавишей и может делать это 300 раз в минуту; найдите нижнюю границу пропускной способности канала нервов, идущих к рукам пианиста.
Упр. 4. Банковские записи, состоящие из бесконечной последовательности случайных по видимости цифр, имеющих значения от 0 до 9, должны для хранения кодироваться шрифтом Брайля. Если за 1 час в хранилище должно поступить 10 000 цифр, то с какой скоростью должны печататься символы Брайля при оптимальном кодировании? (Указание: в «алфавите» Брайля 64 символа.)
9/18. Приведем еще один пример, показывающий удивительную способность метода Шеннона проникать в самое существо проблем связи. Рассмотрим систему с состояниями а, Ь, с, й и с вероятностями переходов
