Information Theory and Reliable Communication Robert G. Gallager MASSACHUSETTS INSTITUTE OF TACHNOLOGY John Wiley and sons, Inc. New York, London, Sydney, Toronto, 1968 P. ГАЛЛАГЕР ТЕОРИЯ ИНФОРМАЦИИ И НАДЕЖНАЯ СВЯЗЬ * Перевод с английского под редакцией М. С. Пинскера и Б. С. Цыбакова Москва -Советское радио • 1974 6Ф0.1 Г15 УДК 621.313.684 Галлагер Р. Теория информации и надежная связь. США, 1968 г. Пер. с англ., под ред. М. С. Пинскера и Б, С. Цыбакова, М., «Советское радио», 1974, 720 с. В книге собраны, подытожены и заново переосмыслены все основные ре- зультаты теории информации. Конструкция наиболее перспективных для прак- тического использования кодов, разнообразные методы декодирования, выра- жения для вероятностей ошибки, пропускная способность реальных каналов связи, методы сокращения избыточности—все это и многое другое изложено с самых современных позиций. Предлагаемые читателю результаты (вместе с изящ- ными и полными их доказательствами) сведены в книге в единую систему. Мате- матические рассуждения удачно сочетаются с инженерными выводами и техни- ческими рекомендациями. Книга предназначена для широкого круга инженеров и математиков, спе- циализирующихся по системам связи, системам управления, вычислительным машинам и кибернетическим устройствам. Она также может служить хорошим учебным пособием для аспирантов и студентов. Рис. 304, табл. 194, библ. 160 назв. Редакция кибернетической литературы Г30501-048 БЗ-27-159-1974 046 (01)-74 © Перевод на русский язык. Издательство «Советское радио», 1974. ОГЛАВЛЕНИЕ Предисловие редакторов русского перевода ............. 9 Предисловие к русскому изданию ................... 13 Предисловие ............................ 14 1 СИСТЕМЫ СВЯЗИ И ТЕОРИЯ ИНФОРМАЦИИ 17 1.1. Введение ........................... 17 1.2. Модели источников и кодирование для источников ......... 20 1.3. Модели каналов и кодирование для каналов. ............ 22 Исторические замечания и ссылки ................ 28 2 ' МЕРА ИНФОРМАЦИИ 29 2.1. Дискретные вероятности; обзор и обозначения .......... 29 2.2. Определение взаимно? информации ................ 32 2.3. Средняя взаимная информация и энтропия . . .......... 39 2.4. Вероятность и взаимная информация для непрерывных ансамблей ... 42 2.5. Взаимная информация для произвольных ансамблей ........ 49 Итоги и выводы .......................... 53 Исторические замечания и ссылки ................. 53 3 КОДИРОВАНИЕ ДЛЯ ДИСКРЕТНЫХ ИСТОЧНИКОВ 54 3.1. Коды с фиксированной длиной .................. 55 3.2. Неравномерные кодовые слова .................. 60 3.3. Теорема кодирования для источника ................ 66 3.4. Процедура выбора оптимального неравномерного кода ....... 68 3.5. Дискретные стационарные источники ............... 72 3.6. Марковские источники ...................... 80 Итоги и выводы ......... ^................ 86 Исторические замечания и ссылки ................. 87 4 ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ПАМЯТИ И ПРОПУСКНАЯ 88 СПОСОБНОСТЬ 4.1. Классификация каналов ..................... 88 4.2. Дискретные каналы без памяти .................. 90 4.3. Обращение теоремы кодирования ................. 93 4.4. Выпуклые функции ....................... 99 4.5. Нахождение пропускной способности дискретного канала без памяти 107 4.6. Дискретные каналы с памятью ................... 113 Неразложимые каналы ...................... 122 Итоги и выводы ......................... 127 Исторические замечания и ссылки ... ............. 128 Приложение 4А ........................... 128 5 ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ 132 5.1. Блоковые коды ........................... 132 5.2. Декодирование блоковых кодов .................. 136 5.3. Вероятность ошибки для двух кодовых слов ............ 138 5.4. Обобщенное неравенство Чебышева и граница Чернова ...... 142 5.5. Случайные кодовые слова .................... 147 5.6. Теорема кодирования для кода с числом слов, большим двух .... 152 Свойства показателя экспоненты случайного кодирования EJ- (R) 157 5.7. Вероятность ошибки для ансамбля кодов с выбрасыванием ..... 166 5.8. Нижние границы для вероятности ошибки ............. 172 Вероятность ошибки на блок при скоростях, больших пропускной способности ........................... 188 5.9. Теорема кодирования для каналов с конечным числом состояний . . . 191 Состояние известно на приемном конце ............... 197 Итоги и выводы .......................... 202 Исторические замечания и ссылки ................ 203 Приложение 5А .......................... 203 Приложение 5Б .......................... 208 6 МЕТОДЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ 211 6.1. Коды с проверкой на четность .................. 211 Порождающие матрицы ...................... 214 Проверочные матрицы систематических кодов с проверкой на четность 215 Таблицы декодирования ....................... 217 Коды Хэмминга ......................... 218 6.2. Теорема кодирования для кодов с проверкой на четность ...... 222 6.3. Теория групп .......................... 225 Подгруппы ............................ 226 Циклические подгруппы ...................... 228 6.4. Поля и многочлены ........................ 229 Многочлены ........................... 231 6.5. Циклические коды ........................ 237 6.6. Поля Галуа ........................... 243 Коды максимальной длины и коды Хэмминга ............ 248 Существование полей Галуа. .................... 252 6.7. БЧХ-коды ........................... 256 Итеративный алгоритм для нахождения o(D) ...:........ 263 6.8. Сверточные коды и пороговое декодирование ........... 276 6 6.9. Последовательное декодирование ................. 282 Сложность последовательного декодирования ........... 291 Вероятность ошибки при последовательном декодировании ..... 299 6.10. Кодирование в каналах с пакетами ошибок ............ 304 Циклические коды ........................ 309 Сверточные коды ......................... 317 Итоги и выводы .................. ., ...... 323 Исторические замечания и ссылки ................. 324 Приложение 6А .......................... 324 Приложение 6Б ....................'...... 327 Случайные блуждания и доказательство леммы ОБ. 1 ... . . . . . 331 7 ДИСКРЕТНЫЕ ПО ВРЕМЕНИ КАНАЛЫ БЕЗ ПАМЯТИ 334 7.1. Введение ............................ 334 7.2. Отсутствие ограничений на входе ................. 336 7.3. Ограничения на входе ....................... 341 7.4. Аддитивный шум и аддитивный гауссов шум ............ 351 Аддитивный гауссов шум и ограничение на энергию входного сигнала 353 7.5. Параллельные каналы с аддитивным гауссовым шумом ...... 361 Итоги и выводы ......................... 371 Исторические замечания и ссылки ................ 372 8 НЕПРЕРЫВНЫЕ КАНАЛЫ 373 8.1. Ортонормальные разложения .сигналов и белый гауссов шум .... 373 Гауссовские случайные процессы ................. 380 Взаимная информация для каналов с непрерывным временем .... 387 8.2. Белый гауссов шум и ортогональные сигналы ........... 389 Вероятность ошибки для двух кодовых слов . . .......... 392 Вероятность ошибки для ортогональных кодовых слов ...... 396 8.3. Эвристическое изучение пропускной способности канала с аддитивным гауссовым шумом и ограничениями на полосу частот ..... . . . .401 8.4. Представление линейных фильтров и небелый шум ......... 407 Профильтрованный шум и разложение Карунена — Лоэва ..... 415 Идеальные фильтры нижних частот ... ............ 419 8.5. Каналы с аддитивным гауссовым шумом и сигналами на входе, огра- ниченными по мощности и по частоте ............... 422 8.6. Диспергирующие каналы с замираниями ............. 446 Итоги и выводы 455 Исторические замечания и ссылки . . ............. 455 9 КОДИРОВАНИЕ ИСТОЧНИКА С ЗАДАННЫМ КРИТЕРИЕМ 457 ВЕРНОСТИ 9.1 Введение ............................ 457 9.2. Дискретные источники без памяти и меры искажения отдельной буквы 458 9.3. Теорема кодирования для источников при заданном критерии верности 466 , 7 9.4. Вычисление R(d*) ......................... 472 9.5. Модификация обращения теоремы кодирования для канала с шумами 480 9.6. Дискретные по времени источники с непрерывными амплитудами . 484 9.7. Гауссовские источники с квадратично-разностным искажением .... 490 Источники, порождающие гауссовские случайные процессы .... 496 9.8. Дискретные эргодические источники .............. 504 Итоги и выводы ......................... 514 Исторические замечания и ссылки ................ 516 Задачи и упражнения ........................ 517 Решения задач ............................ 575 Список обозначений .......................... 691 Примечания редакторов ....................... 693 Список использованной литературы и рекомендуемые книги ..... 695 Именной указатель ......................... 709 Предметный указатель ......................... 711 ПРЕДИСЛОВИЕ РЕДАКТОРОВ РУССКОГО ПЕРЕВОДА Круг проблем, составляющих основное содержание этой книги, восходит к К. Э. Шеннону, к его первоначальной работе «Математичес- кая теория связи», опубликованной в 1948 г. В центре внимания книги находится детальное развитие идеи о применении кодирования для помехоустойчивой передачи сообщений по каналам с шумами и для сокращения избыточности, содержащейся в сообщении. История развития теории информации была бурной и неровной. Новизна тематики, идей и постановок, оригинальность и общность под- хода, открытие новых сфер применения современного математического аппарата, а также широковещательное и, быть может, несколько неоп- равданное название («теория информации» вместо «теория передачи информации») произвели в начале пятидесятых годов своего рода науч- ный бум. В эти годы теория информации привлекла внимание многих ученых за рубежом и в нашей стране, рекрутировала талантливую мо- лодежь. Это не замедлило сказаться на достижениях теории и ее пер- вых шагах практического использования. Именно в пятидесятые годы была выдвинута идея алгебраического кодирования и доказана его оп- тимальность; построены БЧХ-коды; предложены сверточные и итера- тивные коды, последовательное декодирование; получены границы ве- роятности ошибки для оптимальных кодов; исследована пропускная способность многих каналов и е-энтропия источников. Вместе с тем такое бурное развитие теории и шум, поднятый вокруг этого, сделали ее модной и привлекательной для ученых самых разных специальностей. Возможность перефразировать проблемы многих наук в терминах извлечения, переработки или хранения информации и пер- спектива получения после этого готовых решений создали около теории информации атмосферу научного Клондайка. Страницы журналов захлестнул поток легковесных, а иногда и ошибочных статей, посвя- щенных неоправданным применениям теории информации (в боль- шинстве случаев понятия «энтропия») к физике, психологии, кристалло- графии, лингвистике, теории графика и т. п. Наряду с привлечением внимания к теории информации, что не- сомненно стимулировало ее развитие, эта волна несла в себе и скрытые опасности; в первую очередь, возможность обратного отлива и компро- метации самой теории информации. Благодаря усилиям многих уче- ных, глубоко понимавших новую науку и обеспокоенных за ее судьбу (поучительны в этом отношении статья К. Э. Шеннона «Бандвагон» и предисловие А. Н. Колмогорова к сборнику работ К. Э. Шеннона), эти опасности были предотвращены. Правда, отлив от теории информа- ции произошел, но это послужило ей лишь на пользу, так как ушли те, кто либо разочаровался в возможности автоматического пере- несения результатов, либо почувствовал себя несостоятельным для преодоления обнажившихся трудностей. Если вначале теорией информации занимались ученые, получив- шие в основном техническое образование, то впоследствии в её разви- 9 тие все активнее начали включаться математики различных направле- ний. Этот естественный процесс происходил в основном потому, что, с одной стороны, инженерам удалось четко сформулировать интересные с точки зрения приложений новые математические задачи, а с другой— эти задачи оказались настолько трудными, что без длительного и глу- бокого математического анализа нельзя было ожидать их решения. Интересно отметить здесь, что среди инженеров, работающих в области радиотехники и электросвязи, существовало мнение, что все методы передачи и приема были предложены инженерами и что эти ме- тоды основываются на простых и интуитивно понятных соображениях. К таким методам относятся, например, различные классические методы модуляции, фильтрация, накопление, разнесение, корреляционный прием и т. п. Согласно этому мнению специалисты, занимающиеся теорией информации, разрабатывают лишь математически более со- вершенные основания этих методов, а также исследуют предельно дости^ жимые потенциальные границы для основных параметров систем связи, что в большинстве случаев опять-таки, согласно этому мнению, сводит' ся к доказательству, что известные методы являются оптимальными. Это мнение действительно отражало положение дел на начальных ста- диях развития теории информации как науки, выросшей -из потребно. стей радиосвязи, телефонии, телевидения, локации и других видов тех- ники связи и, естественно, питавшейся материнским молоком их пло- дотворных идей. Однако с течением времени положение изменилось. Для этого потребовались годы глубоких теоретико-информационных исследований. В результате были открыты классы алгебраических, ите- ративных, каскадных, сверточных и других кодов, а также разработаны изящные методы их декодирования (алгоритмы декодирования цикли- ческих кодов, процедуры последовательного и порогового декодиро- вания и др.). Для развития и понимания этих методов требуется знание идей, постановок и решений теории информации наряду с владением целым рядом современных разделов математики. Техническая интуи- ция здесь уже не является адекватным методом. Далее, когда удельный вес математически сложных работ в теории информации стал превалирующим, начал ощущаться известный отрыв специалистов, работающих в области теории, от инженеров, занятых непосредственным проектированием систем связи. Причиной этого, с одной стороны, была недостаточность традиционного математичес- кого образования инженеров, а с другой стороны, типичное для мате- матиков увлечение абстрактными задачами и формальным изложением, за которыми неискушенному читателю порой трудно было найти рацио- нальное техническое зерно. Немаловажным обстоятельством было то, что в момент первоначальной публикации результатов их доказатель- ства, как правило, выглядели чрезвычайно сложными и запутанными; они не позволяли легко вскрыть лежащие в их основании идеи. Этот отрыв породил некоторую обоюдную иронию в оценке имеющихся до- стижений. Взаимная разобщенность инженеров и теоретиков стала осо- бенно противоестественной, когда к середине шестидесятых годов в тео- рии был разработан ряд перспективных для практического использо- вания методов кодирования и декодирования. 10 В связи с этим книга Р. Г. Галлагера, известного специалиста по теории информации, профессора Массачузетского технологического института, занимает особое место среди публикаций, появившихся в последнее время в нашей стране и за рубежом. Как указано в преди- словии к русскому изданию, автор поставил себе задачу «перекинуть мост между математиками и инженерами». Излагаемый в книге мате- риал базируется, с одной стороны, на стройных математических резуль- татах, а с другой стороны, направлен на конкретные технические при- ложения. Весьма примечательно, что автор все результаты приводит с полными доказательствами на уровне строгости, отвечающем мате- матическим публикациям, и в то же время содержание книги доступно для широкого круга читателей. Достигается это за счет того, что изло- жение начинается с разбора простейших случаев, затем проводится подробное обсуждение, истолкование и практическое осмысливание полученных результатов. Введение полных и строгих доказательств позволяет читателю более глубоко проникнуть в суть выводимых ре- зультатов и найти возможности их изменения в соответствии с запро- сами теории и практики. Книга представляет собой методически превосходно написанный учебник по теории информации, освещающий результаты, полученные вплоть до конца шестидесятых годов. Тщательно отобранный и внутрен- не согласованный материал книги дает описание различных сторон проблемы передачи информации. Подробно исследуется применимость основных теорем кодирования для обширного класса каналов и источ- ников: дискретных, непрерывных, без памяти и с памятью. Изучают- ся их характеристики, пропускная способность, энтропия и скорость как функция искажения. Большое место в книге уделяется построе- нию эффективных методов кодирования и декодирования и оценке их сложности, что весьма существенно для приложений теории инфор- мации. Кодирование трактуется автором как некоторое преобразова- ние выхода источника (включающее модуляцию); декодирование — как некоторая обработка сигнала, принятого на выходе канала (вклю- чающая демодуляцию), т. е. кодирование и декодирование рассматри- ваются с наиболее общих позиций, объединяющих теории кодирования, модуляции и приема сигналов. Значительное внимание уделяется источникам и каналам без памяти и гауссовским, что вполне естествен- но, поскольку изучение теории на примере таких источников и каналов, отражающих определенную реальную ситуацию, позволяет довольно быстро войти в существо изучаемого предмета. Наряду с изложением известных результатов в книге впервые при- веден ряд новых, полученных в последнее время автором и его колле- гами. Так, например, среди последних имеются результаты, относя- щиеся к непрерывным каналам (гл. 7) и источникам (гл. 9). Даны также новые доказательства целого ряда опубликованных ранее результатов. К сожалению, в книге, как отмечает и сам автор, недостаточно пол- но отражены результаты, полученные в Советском Союзе. Некоторые из них, непосредственно примыкающие к тексту, указаны в коммента- рии редакторов, приведенном в конце книги. Отметим здесь, что резуль- таты, полученные в нашей стране, в ряде случаев приводят к сущест- 11 венному усилению фактов, приведенных автором. Укажем здесь на работы по последовательному декодированию, по е-энтропии сообще- ний и исследованию пропускной способности и кодирования для не- прерывных источников и каналов. Введены интересные новые классы кодов, исправляющих ошибки, предложены обобщения задачи кодиро- вания источника, когда неизвестна его статистика. Весьма существен для развития теории передачи информации выдвинутый А. Н. Колмого- ровым новый подход к ее основаниям. Для чтения книги требуется знакомство с начальными курсами математического анализа, теории вероятностей, а также элементами теории случайных процессов. Кроме того, предполагается, что читатель имеет некоторую подготовку к восприятию математических доказа- тельств. Наличие большого числа примеров, упражнений и задач в тексте книги способствует более продуктивному ее усвоению, а также при- обретению некоторых навыков к исследованию изучаемых проблем. В русское издание включены решения задач, которые в США были изда- ны отдельной книгой, доступ к которой разрешен лишь профессорам университетов. В библиографию добавлены публикации на русском языке, вышедшие в основном до 1969 г. В процессе перевода и редактирования был устранен ряд опечаток, часть из которых нам сообщил Р. Г. Галлагер. Вместе с тем у редакторов остается ощущение, что некоторые опечатки исправить не удалось, особенно в тексте задач и их решений. Кроме того, следует отметить, что автор не всегда строго придерживается при- нятых им обозначений. Однако это не затрудняет чтения и восприя- тия материала книги. Без сомнения, предлагаемая книга Р. Г. Галлагера будет полезна широкому кругу специалистов, работающих в самых различных об- ластях, а также студентам и аспирантам, впервые приступающим к изу- чению предмета. Следует надеяться, что выход книги будет способ- ствовать взаимопониманию математиков и инженеров, сближению теории и практики передачи информации. Книга может послужить твердой основой для намечающихся в последнее время серьезных тенденций расширения области приложения теории и ее методов. Перевод книги выполнен Б. С. Цыбаковым (гл. 1—5), К. Ш. Зиган- гировым (гл. 6) и М. С. Пинскером (гл. 7—9). М. С. Пинскер Б. С. Цыбаков ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Одна из моих главных задач при написании этой книги состояла в том, чтобы перекинуть мост между американскими математиками и инженерами, работающими в теории информации. Математики счи- тают, что техническая литература недоступна им отчасти из-за недоста- точного понимания реальных проблем связи, а отчасти из-за невнима- ния к математической строгости, свойственной технической литерату- ре. Инженеры считают, что математическая литература недоступна им из-за широко распространенного использования в ней незнакомых ма- тематических результатов. В связи с этим мое мнение состоит в том, что в большей части книги следует использовать лишь простейшие ма- тематические методы, ограничивая общность результатов там, где не- обходимо избежать затруднений, связанных с математическими тон- костями. Более математически настроенные советские специалисты по тео- рии информации, несомненно, найдут необычным то, что я часто по- лучаю один и тот же результат дважды или трижды в различной сте- пени общности, в то время как доказательство наиболее общего резуль- тата так же просто, как и доказательства в менее общих случаях. Это было вызвано желанием не отвлекать внимания студентов, специализи- рующихся в области техники, от основных идей использованием нез- накомого математического аппарата. Мне бы хотелось принести свои извинения советским коллегам за малочисленность ссылок на советскую литературу. Частично это произошло потому, что существует большая задержка во времени при переводе советской литературы на английский язык, а частично при- чина была в моем нежелании задерживать публикацию книги на доста- точно долгое время, которое требуется для подробного обзора многих важных опубликованных результатов и выяснения их взаимосвязи. Мне кажется, что без этого простое расширение множества ссылок было бы бессмысленным. Роберт Г. Галлагер ПРЕДИСЛОВИЕ Эта книга написана, главным образом, как учебник по теории ин- формации для студентов старших курсов и аспирантов первого года обучения, специализирующихся в области техники или в математике. Предполагается, что читатель обладает знанием начального курса ана- лиза и элементов теории вероятностей, а для чтения последних глав требуются некоторые начальные знания из теории случайных процес- сов. К сожалению, имеется еще одно требование, которое труднее вы- полнить. Читатель должен находиться на разумном уровне математи- ческой зрелости и обладать способностью к абстрактному мышлению. Основные результаты теории являются довольно тонкими и абстракт- ными и в ряде случаев они были получены с помощью, казалось бы, весьма окольных путей. К счастью, недавно достигнутые упрощения в теории позволили сделать главные результаты более доступными, чем это было ранее. Из-за этой деликатности и абстрактности теории приходится про- водить рассуждения на более строгом по сравнению с обычно принятым в технике уровне. Чтобы облегчить чтение там, где это было возможно, я старался вместе с доказательством трудных теорем давать объясне- ние того, почему теорема является важной, и приводить обоснование справедливости теоремы на интуитивном уровне. Была также предпри- нята попытка дать каждой теореме наиболее простое и элементарное до- казательство; многие из приведенных здесь доказательств являются новыми. Я тщательно избегал довольно неудачную для многих элемен- тарных учебников практику упоминания в середине доказательства некоторых нечетко сформулированных математических теорем, на ос- нове которых и завершается доказательство. Существует целый ряд причин для того, чтобы доказательству тео- рем уделить здесь особое внимание. Одна из главных причин состоит в том, что при попытке приложить теорию инженер быстро установит, что задачи, возникающие в технике, не часто можно решить с помощью непосредственного применения к ним теорем. Теоремы редко могут быть применены без всяких изменений и нужно разобраться в доказательст- ве для того, чтобы выяснить, дает ли эта теорема какое-либо продвиже- ние в решении поставленной задачи. Другой причиной для выделения доказательств является то, что методы, использованные в доказательст- вах, часто оказываются более полезными при проведении новых иссле- дований в этой области по сравнению с самими результатами. Последняя причина обращения особого внимания на точность формулировок ре- зультатов и на тщательность доказательств состоит в том, что эта книга задумана, скорее, как существенная часть курса по теории информации, а не как весь курс целиком. Например, философию, интуитивное тол- кование, примеры и приложения лучше передавать при непосредствен- ном общении на занятиях, в то время как точные утверждения и детали лучше изложить в виде'написанного учебника. Для преподавателя I.I и самостоятельно изучающего курс аспиранта здесь приводится вполне достаточно интуитивного материала, однако студентам последних кур- сов требуется давать дополнительные разъяснения на занятиях. В конце книги приведено большое число упражнений и задач. Их диапазон простирается от простых численных примеров до существен- ных теоретических обобщений. В тексте книги рассмотрено лишь от- носительно небольшое число примеров, и читатель, который нуждается в конкретных примерах, должен часто прерывать чтение для решения некоторых наиболее простых задач, помещенных в конце книги. Имеется целый ряд возможностей выбора помещенного здесь мате- риала для односеместрового курса. Главу 1 следует читать вначале (а возможно, также и в конце). После этого, по моему мнению, предпоч- тительно чтение следующих параграфов (в указанном порядке): 2.1— 2.4, 3.1—3.4, 4.1—4.5, 5.1—5.6., 6.1—6.5 и, наконец, либо 6.8—6.9, либо 6.6.—6.7, либо 8.1—8.3. Другая возможность, открытая для сту- дентов, которые имеют некоторые знания из теории случайных процес- сов, состоит в том, чтобы начать с § 8.1 и 8.2 и затем проследовать по указанному выше пути, используя повсюду в качестве примера^канал с гауссовым белым шумом. Следующая возможность, предлагаемая для слушателей, с серьезными намерениями применений на практике, со- стоит в том, чтобы начать с гл. 6 (опустив § 6.2), затем перейти к § 5.1— 5.5, после этого § 6.2 и далее к гл. 2 и 4 и § 8.1 и 8.2. Иные возможности построения курса можно установить с помощью следующей таблицы используемого в тексте материала. Таблица используемого материала Параграфы Используемый материал Параграфы Используемый материал 2.1-2.3 нет 6.2 5.6, 6.1 2.4—2.5 2.1—2.3 6.3—6.7 6.1 3.1 2.1-.2.3 6.8 6.1 3.2—3.4 2.1—2.3 6.9 5.1—5.5, 6.1—6.5, 6.8 3.5—3.6 3.1-3.4 6.10 6.1-6.5, 6.8 4.1-4.5 2.1-2.3 7.1-7.5 2.1-2.5, 4.3, 5.6-5.7 4.6 3.6,4.1—4.5 8.1-8.2 нет 5.1—5.5 нет 8.3-8.6 7.1—7.5, 8.1—8.2 5.6-5.8 4.4,5.1-5.5 9.1—9.6 4.1—4.5 5.9 4.6,5.1—5.6 9.7 8.5,9.1—9.5 6.1 нет 9.8 3.5,9.1—9.5 Как общее правило, последние темы каждой главы являются самы- ми трудными и излагаются в более сжатой форме по сравнению с темами, рассмотренными ранее. Они включены, главным образом, для асппран- 15 тов, а также лиц, работающих в этой области, хотя большинство из них может быть прочитано в течение второго семестра. Преподавателей сле- дует предупредить не тратить слишком много времени на гл. 3, особен- но в односеместровом, курсе. Материал, помещенный в §4.1—4.5, 5.1—5.6 и 6.1—6.5, проще и имеет большее значение, чем материал, помещенный в § 3.5—3.6, несмотря на то, что он, возможно, менее зна- ком некоторым преподавателям. Я приношу извинения многим авторам значительных работ в тео- рии информации, которых я не упомянул. Я пытался привести ссылки, которые мне казались полезными при написании этой книги, наряду со ссылками на отдельные работы, содержащие дальнейшие продви- жения. Многие работы, имеющие историческое значение, были опуще- ны, и цитируемые здесь авторы не обязательно являются теми, кто внес наибольший вклад в эту область. Мне хочется выразить признательность Исследовательской лабо- ратории электроники и Электротехническому факультету Массачузетс- ского технологического института (МТИ) за терпеливую поддержку во время подготовки этой книги. Эта работа была поддержана Нацио- нальной администрацией по аэронавтике и космосу по контракту NSG- 334. Я особенно благодарен Р. М. Фано, который стимулировал мой первый интерес к теории информации и кому я во многом обязан моим подходом к пониманию этого предмета. Работа над этой книгой была начата более четырех лет назад с первоначальным замыслом произвести переработку (под двойным авторством) книги Р. М. Фано «.Передача информации». Шли годы, текст разрастался и изменялся и стало ясно, что получилась полностью отличная книга. Однако мой долг «Передаче информации» очевиден всякому, кто знаком с обеими книгами. Я также очень благодарен П. Элайсу, Дж. М. Возенкрафту и К. Э. Шеннону, за их идеи и методы изложения, которые широко ис- пользованы здесь. Другой долг я обязан отдать многим студентам и аспирантам, которые слушали курс теории информации в МТИ и де- лали беспристрастные замечания о многих экспериментах по различным представлениям содержащегося здесь материала. Наконец, я обязан многочисленным коллегам, которые были очень великодушны и дали детальную критику различных частей этой рукописи. В этом отноше- нии особенно большую пользу оказал Дж. Л. Месси. Г. Д. Форни, X. Юдкин, А. Вайнер, П. Элайс, Р. Кэн, Р. С. Кеннеди, Дж. Макс, Дж. Пинкстон, Э. Берлекэмп, А. Коленберг, И. Джекобс, Д. Сакри- сон, Т. Кайлат, Л. Сейдман и Ф. Препарата все вместе сделали большое число критических замечаний, которые способствовали значительному улучшению рукописи. Роберт Г. Галлагер СИСТЕМЫ СВЯЗИ И ТЕОРИЯ ИНФОРМАЦИИ 1.1. ВВЕДЕНИЕ Теория связи имеет главным образом дело с системами, предназ- наченными для передачи информации или данных из одной точки в дру- гую. На рис. 1.1.1 приведена довольно общая блок-схема для того, что- бы наглядно представить поведение таких систем. Выход источника на рис. 1.1.1 может, например, представлять собой звуковую речь; после- довательность двоичных символов, поступающих с магнитной ленты; выход ряда датчиков при зондировании космоса; сигналы, поступающие Шум Источник кодер ————— ———— ——i—— —————-• .—————, —е», Адреспгп P;ic. I.I.I. Блок-схема системы связи. к органам чувств живого организма или цель в радиолокационной системе. Каналом может быть, например, телефонная линия; высоко- частотная радиолиния; линия космической связи; устройство памяти или живой организм (для случая, когда выходом источника являются сигналы, поступающие к органам чувств живого организма). В канале обычно действуют различные шумовые помехи, которые в телефонной линии, например, могут возникать из-за временных изменений частот- ной характеристики; из-за разговоров, проникающих из других линий; из-за теплового шума и из-за импульсного шума, источником которого являются переключательные схемы. Кодер на рис. 1.1.1 производит любую обработку выхода источника, совершаемую до передачи. Такая обработка может включать в себя, например, какую-либо комбинацию модуляций, редукции данных и внесения избыточности для борьбы с шумом в канале. Декодер производит обработку сигналов на выходе канала, целью которой является воспроизведение на приемном конце приемлемой копии (или отклика) выхода источника. В начале 1940-х годов К. Э. Шеннон (1948) разработал математи- ческую теорию, названную теорией информации, которая имеет дело с наиболее фундаментальными аспектами систем связи. Замечательны- ми свойствами этой теории являются, во-первых, широкое привлече- ние теории вероятностей, во-вторых, указание определяющего значе- ния кодера и декодера как с точки зрения их функциональной роли, так и с точки зрения существования (или не существования) таких коде- ров и декодеров, на которых достигается заданный уровень качества передачи. За последние двадцать лет теория информации стала более 17 точной, получила значительное развитие и достигла того уровня, на котором возможно ее применение к практическим системам связи. Целью этой книги является представление как логической структуры этой теории, так и указание того, где и как эта теория может быть применена. Так же как любая математическая теория, эта теория оперирует только с математическими моделями, а не с физическими источниками и физическими каналами. Можно было бы предположить поэтому, что было бы удобным начать изложение теории с обсуждения того, как построить подходящие математические модели физических источников и каналов. Однако теории строятся не так главным образом потому, что физическая реальность очень редко является достаточно простой для того, чтобы ее можно было точно представить с помощью модели, под- дающейся математической обработке. Мы начнем с изучения простей- ших классов математических моделей источников и каналов и далее используем складывающиеся представления об этих моделях и относя- щиеся к ним результаты для изучения все более сложных классов моде- лей. Естественно, что выбор классов моделей для изучения будет на- веян и обусловлен наиболее важными чертами реальных источников и каналов, но наше представление о том, какие из этих черт являются важными, будет видоизменяться на основе теоретических результа- тов. Наконец, после того как теория будет понята, будет установлено, что она является полезной при исследовании реальных систем связи по следующим двум причинам. Во-первых, она даст основу, на которой можно построить подробные модели реальных источников и каналов. И, во-вторых, что более важно, взаимосвязи, установленные теорией, указывают на типы обменных соотношений, возникающих при построе- нии кодеров и декодеров для заданных систем. В то время как указа- ные выше замечания могут быть отнесены к почти любой математичес- кой теории, они особенно необходимы здесь потому, что должна быть разработана весьма развитая теория до того, как наиболее важные для построения систем связи рекомендации станут очевидными. Для того чтобы произвести дальнейшие упрощения при изучении моделей источников и моделей каналов, полезно частично отделить эффекты, связанные с источником в системе связи, от эффектов, свя- занных с каналом. Это может быть сделано с помощью разбиения как кодера, так и декодера, изображенных на рис. 1.1.1, на две части, как это показано на рис. 1.1.2. Задачей кодера для источника является представление выхода источника с помощью последовательности двоичных символов, и один из главных вопросов, возникающих в свя- зи с этим, является вопрос о том, как много двоичных символов в единицу времени требуется для представления выхода любой задан- ной модели источника. Задача кодера и декодера для канала состоит в том, чтобы надежно воспроизвести двоичные последовательности дан- ных на выходе декодера для канала, и один из главных вопросов, воз- никающих в связи с этим, состоит в том, возможно ли это сделать, и если возможно, то как. Конечно, не очевидно, приводят ли представления кодера и деко- дера в виде, указанном на рис. 1.1.2, к каким-либо фундаментальным ограничениям характеристик системы связи. Однако одним из наибо- лее важных результатов теории является то, что при весьма широких условиях никакие такие ограничения не возникают (но этот результат не означает, что кодер и декодер вида, изображенного на рис. 1.1.2, всегда являются наиболее экономичными для достижения заданной точности передачи). С практической точки зрения разбиение кодера и декодера, ука- занное на рис. 1.1.2, является особенно удобным, так как это позволяет строить кодер и декодер для канала фактически независимо от кодера и декодера для источника и использовать двоичное представление дан- ных в качестве границы раздела. Это, конечно, облегчает использова- ние различных источников при одном и том же канале. Источник Кодер оля источника. Двоичные Кодер сля канала. ffavHb/e Канал Декодер ^ля источника. Двоичны? Декодер с?ля канала. данные Адресат Рис. 1.1.2. Блок-схема системы связи, в которой кодер и декодер раз- биты на две части. В следующих двух параграфах будут кратко описаны классы мо- делей источников и моделей каналов, которые изучаются в последую- щих главах, а также будут описаны кодирование и декодирование этих источников и каналов.Так как основное внимание в теории информации сосредоточено, главным образом, на кодировании и декодировании, то нужно ясно понимать, что эта теория неприменима в равной мере ко всем ситуациям, возникающим в связи. Так, например, если источником является радиолокационная цель, то здесь нет возможности кодиро- вать выход источника (если конечно, мы не хотим рассматривать выбор радиолокационных сигналов как метод кодирования), и поэтому нель- зя ожидать, что эта теория дает здесь больше, чем взгляд со стороны. Подобно этому, если выходом источника являются сигналы, поступаю- щие к органам^ чувств живого организма, то мы могли бы рассмотреть организм как комбинацию кодирования, канала и декодирования, но мы не смогли бы управлять кодированием и декодированием, и не сов- сем ясно, что такая модель является наиболее плодотворной для изу- чения живых организмов. Таким образом, опять-таки теория информа- ции может дать некоторое понимание поведения таких организмов, но ее нельзя, конечно, рассматривать как магический ключ для понима- ния. 19 1.2. МОДЕЛИ ИСТОЧНИКОВ И КОДИРОВАНИЕ ДЛЯ ИСТОЧНИКОВ Здесь мы дадим краткое описание математических моделей источ- ников, которые будут рассматриваться в дальнейшем. Естественно, что более подробно эти модели будут рассмотрены в последующих главах. Все источники в теории информации моделируются с помощью случай- ных процессов или случайных последовательностей. Простейший класс моделей источников составляют дискретные источники без памяти. В этих источниках выходом является последовательность (во времени) Способ < а,^-00 a^Of а ^10 g»—// Способ 2 a,-f0 d^fO a.s -> t/0 a„-^11f Рис. 1.2.1. Два способа пре- образования алфавита из четырех букв в двоичные символы. букв, каждая из которых выбрана из некоторого фиксированного ал- фавита, скажем, содержащего буквы Qi, flg, ..., а^. Последовательность на выходе источника состоит из этих букв, выбираемых из алфавита статистически независимо и случайно, и при этом выбор производится в соответствии с некоторым заданным распределением вероятностей . Q(ai), ..., <ЗЫ. Несомненно, что на первый взгляд кажется довольно странным мо- делирование реальных источников, которые по предположению про- изводят осмысленную информацию, с помощью случайных процессов. Следующий пример поможет пояснить причину этого. Предположим, что нужно провести некоторое измерение несколько раз подряд и что результатом каждого измерения может быть одно из четырех событий GI, из, а.з или 0:4. Пусть эта последовательность измерений должна быть накоплена в двоичной форме записи, и предположим, что предлагаются два способа перехода к двоичным символам, изображенные на рис. 1.2.1. В первом из представленных выше способов требуются два двоич- ных символа для представления каждой буквы источника, в то время как во втором способе требуется переменное число символов. Если известно, что в подавляющем большинстве измерений результатом будет QI, тогда способ 2 позволит накопить длинную последовательность измерений с помощью значительно меньшего числа двоичных симво- лов, чем способ 1. Методы кодирования выхода дискретного источника в двоичные данные будут подробно обсуждаться в гл. 3. Важным момен- том здесь является то, что относительная эффективность методов, изо- браженных на рис. 1.2.1, критически зависит от частоты появления различных событий и что в математической модели источника последние определяются с помощью распределения вероятности на множестве букв источника. Хорошо известные, но более сложные примеры такого типа дает стенография, в которой короткие символы'"используются для наиболее употребительных слов,' и код Морзе, в котором короткие последовательности точек и тире сопоставлены часто встречающимся буквам, а длинные последовательности — редким буквам. 20 С кодированием выхода источника в двоичные данные тесно свя- зана мера информации (или неопределенности) букв алфавита источ- ника, которая будет описана в гл. 2. Если k-я буква алфавита источника имеет вероятность Q (а;;), то собственная информация этой буквы (из- меренная в битах) определяется как / (а^)^ — loga Q (яь). С интуи- тивной точки зрения (подробнее это будет рассматриваться в гл. 2) это, связанное с техникой связи определение, имеет много качественных черт, свойственных общеупотребительному понятию информации. В частности, если Q (а^) = 1, то / (а^) = 0 в соответствии с тем, что появление а^ не несет никакой информации, так как оно неизбежно должно произойти. Точно также, чем меньше вероятность а^, тем боль- ше ее собственная информация. Вместе с тем, нетрудно заметить, что это специальное определение информации имеет некоторые качест- венные недостатки в сравнении с общеупотребительным понятием информации. Например, не имеет значения то, насколько редким яв- ляется событие; мы не считаем это информативным (в общеупотреби- тельном смысле), если само по себе наступление события не оказывается интересным для нас. Это не означает, что имеется какой-то недостаток в определении собственной информации; польза от того или иного оп- ределения в теории определяется тем, насколько оно дает возможность проникнуть в существо проблемы, и тем, как оно упрощает теоремы. Определение, которое дается здесь, оказывается полезным в теории, главным образом, именно потому, что оно позволяет отделить понятие неожиданности в информации от того, что представляет в информации интерес или смысл. Среднее по буквам алфавита значение собственной информации является особенно важной величиной, которая называется энтропией буквы источника; энтропия задается выражением к 2- ft=i Значение энтропии буквы источника определяется, главным образом, теоремой кодирования для источника, которая рассматривается в гл. 3. Она утверждает, что если Н — энтропия буквы источника в дискрет- ном источнике без памяти, то последовательность на выходе источника не может быть представлена двоичной последовательностью, использую- щей в среднем меньше чем Н двоичных символов на букву источника, но она может быть представлена двоичной последовательностью, ис- пользующей в среднем сколь угодно близкое к Н число двоичных символов на букву источника. Некоторое ощущение справедливости этого результата может быть получено, если заметить, что в случае, когда для некоторого целого L источник имеет алфавит из 2L равно- вероятных букв, то энтропия буквы источника равна L бит. Вместе с тем, если заметить, что всего ""имеется 2L различных последователь- ностей из L двоичных символов, то можно понять, что каждая из этих последовательностей может быть сопоставлена различным буквам'ал- фавита источника, представляя, таким образом, выход источника с по- мощью L двоичных символов на букву источника. Этот пример дает 21 кое-что для понимания того, почему в определении собственной информации и энтропии появляется логарифм. Часто энтропия также выражается в битах в секунду. Если для дискретного источника без памяти энтропия буквы источника равна Н и если источник производит одну букву за каждые tg секунд, то энтро- пия в битах в секунду равна Я/т-s и теорема кодирования для источника указывает, что выход источника может быть представлен двоичной последовательностью, в которой число двоичных символов в секунду сколь угодно близко к Я/Ts. В качестве более сложного класса моделей источников можно рас- смотреть дискретные источники с памятью, в которых последователь- ные буквы источника статистически зависимы. В § 3.5 аналогичным, но более сложным образом определяется энтропия этих источников (в би- тах на букву или в битах в секунду) и доказывается, что теорема коди- рования для источников справедлива, если источник является эрго- дическим. Наконец, в гл. 9 будут рассмотрены недискретные источники. Наи- более известным примером недискретного источника является такой, у которого выходом источника является случайный процесс. При по- пытке закодировать случайный процесс случайной последовательностью возникает ситуация, по своей природе сильно отличающаяся от коди- рования дискретных источников. Случайный процесс можно закоди- ровать в двоичные данные, например, следующим образом: взять вы- борки случайной функции, затем проквантовать их и после этого зако- дировать проквантованные выборки в двоичные символы. Различие между этим кодированием и двоичным кодированием, описанным ра- нее, состоит в том, что выборочные функции не могут быть точно вос- становлены по двоичной последовательности и, таким образом, это кодирование следует описывать как в терминах числа двоичных сим- волов в секунду, так и в терминах некоторой меры искажения функции на выходе источника при представлении ее функцией, восстановлен- ной по двоичной последовательности символов. В гл. 9 рассматривает- ся проблема отыскания минимального числа двоичных символов в се- кунду, достаточного для того, чтобы закодировать выход источника так, чтобы среднее искажение выхода источника при его воспроизведении по двоичной последовательности находилось в заданных пределах. Основное здесь состоит в том, что недискретный источник может быть закодирован с некоторыми искажениями в двоичную последователь- ность и что требуемое число двоичных символов в единицу времени зависит от допустимого искажения. 1.3. МОДЕЛИ КАНАЛОВ И КОДИРОВАНИЕ ДЛЯ КАНАЛОВ Для того чтобы описать математически модель канала, мы, во- первых, определим множество возможных сигналов на входе канала (или просто входов канала), во-вторых, множество возможных сигна- лов на выходе (или выходов канала) и, в-третьих, для каждого сигнала на входе вероятностную меру на множестве сигналов на выходе. Про- 22 BKoa'h'ou, а /'•фо.бтп •^ О Выгодной. с.."фа. в и т ^) О Двоичный симметричный нал. стейший класс моделей каналов образуют дискретные каналы без па- мяти; они определяются следующим образом. Входом является после- довательность букв из конечного алфавита, пусть а^, ..., а^, выходом — последовательность букв из того же самого или другого алфавита, скажем &i, ..., OJ. Наконец, каждая буква выходной последовательности зависит статистически только от буквы, стоящей на соответствующей позиции во входной последовательности, и определяется заданной условной вероятностью P(bj\a,,), определенной для всех букв а„ ал- фавита на входе и всех букв bj алфавита на выходе. Примером может служить двоичный симметричный канал (рис. 1.3.1), который представ- ляет собой дискретный канал без памяти с двоичными последователь- ностями на входе и выходе, в котором каждый символ после- довательности на входе с неко- торой фиксированной вероятно- стью 1 — е воспроизводится на выходе канала правильно и с вероятностью е изменяется шу- мом на противоположный сим- вол. В общем случае, в дискрет- ном канале без памяти переход- ные вероятности исчерпывают собой все известные сведения о том, как сигнал на входе, взаимо- действуя с шумом, образует сигнал на выходе. В дальнейшем будет описано, как дискретные каналы без памяти, связаны с реальными каналами. Намного более широкий класс каналов (эти каналы будут назы- ваться каналами с памятью) образуют каналы, в которых сигналами на входе снова являются последовательности букв из конечных алфави- тов, но в которых каждая буква последовательности на выходе может статистически зависеть не только от соответствующей буквы входной последовательности. Другой класс моделей каналов, которые имеют более непосредст- венное сходство с физическими каналами, является класс, в котором как множество входных, так и множество выходных сигналов представ- ляют собой множества функций времени и для каждой заданной функ- ции на входе выход — случайный процесс. Частной моделью из это- го класса, которая имеет большую теоретическую и практическую важ- ность, является канал с аддитивным белым гауссовым шумом. Множест- вом сигналов на входе для такой модели является множество функций времени, удовлетворяющих заданному ограничению сверху на мощ- ность, а сигналы на выходе — сумма сигнала на входе н белого гауссо- вого шума. При использовании этой модели для физического канала с затуханием в качестве входа в модели берется, естественно, сигнал на входе физического канала после его затухания в канале. При передаче двоичных данных по каналу из рассмотренных выше классов часто бывает удобно разделить как кодер для канала, так и де- кодер для канала на две части, как показано на рис. 1.3.2. Выходом 23 кодера для дискретного канала на рис. 1.3.2 является последователь- ность букв из конечного алфавита а^, ..., о/<. Эти буквы производятся во времени с некоторой фиксированной скоростью (одна буква, напри- мер, за каждые Тр секунд). В каждом интервале Те секунд модулятор дискретных данных (МДД) производит одну функцию из заданного множества функций Si (t), ..., s^ (t), определенных на интервале длины Тд. Какая именно из этих функций будет произведена, определяется буквой, поступающей на МДД в течение этого интервала: так, Ci при- водит к Si (t), а ид приводит к Sg (/) и т. д. Таким образом, вся функция на входе канала имеет вид 2s, (t—m:,), Днепре rr"ib:il какал Источник Кодер длп источника. Кодер дг/я ffu.CHpem»oso канала Модулятор ёиск^етнь/fi. банных непре (рун/- сывныfil,UU. ччнНН/г1 1,е Два00. ь/е Даннь р канал Адресат Декодер для источника Дискретный-декодер для канала Демодулятор дискретные данных Рис. 1.3.2. Представление непрерывного канала как дискретного канала. где последовательность^, п = ...,—1,0, 1, ..., определяется соответст- вующими символами на входе МДД. Демодулятор дискретных данных (ДДД) принимает поступающие из канала функции и преобразует их в последовательности букв конечного алфавита, &i, ..., bj, производя буквы вновь со скоростью одна буква за каждые Те секунд. В простейшем случае каждая буква, выходящая из ДДД, является решением (возможно, что неправильным) о том, какая буква поступила на МДД в соответствующем временном интервале, и в этом случае алфавит &i, ..., bj будет совпадать с алфави- том на входе МДД. В более сложных случаях выход ДДД будет так- же содержать информацию о том,' насколько правдоподобно решение; в этих случаях выходной алфавит ДДД будет больше, чем входной алфавит МДД. е Как можно заметить из рис.'1.3.2, совокупность МДД, канала, по которому передаются непрерывные сигналы, и ДДД может быть рас- смотрена как дискретный канал; именно поэтому дискретные каналы играют большую роль при моделировании физических каналов. Если шум на последовательных интервалах по Те секунд является независи- мым, что имеет место в случае^аддитивного белого гауссового шума, то описанный выше дискретный' канал является также каналом без памяти. 24 Рассматривая кодирование и декодирование для класса дискрет- ных каналов, мы, во-первых, получим некоторые результаты, касаю- щиеся кодера и декодера для дискретного канала, входящего в систему, изображенную на рис. 1.3.2, и, во-вторых, сможем использовать эти результаты для того, чтобы в какой-то степени понять, как можно по- строить МДД и ДДД в такой системе. Одним из наиболее важных параметров канала является его про- пускная способность. Пропускная способность будет определена в гл. 4 и там будет показано, как ее найти для широкого класса дискретных каналов; в гл. 7 и 8 эти рассмотрения будут обобщены, так чтобы охва- тить 'недйскретные каналы. Пропускная способность определяется с помощью информационной меры, подобной той, которая была исполь- зована при рассмотрении источников, и пропускная способность интер- претируется как максимальное среднее количество информации (в би- тах в секунду), которое может быть передано по каналу. Оказывается, что пропускная способность недискретного канала может быть сколь угодно точно приближена пропускной способностью дискретного кана- ла, который получается из исходного недискретного канала при соот- ветствующем выборе модулятора дискретных данных и демодулятора дискретных данных. Важность понятия пропускной способности канала основана прежде всего на теореме кодирования для канала с шумами и ее обра- щении. Грубо говоря, эта теорема кодирования, справедливая для ши- рокого класса каналов, утверждает, что если пропускная способность канала равна С бит в секунду и если двоичные данные поступают на вход кодера этого канала (см. рис. 1.1.2) со скоростью (в двоичных сим- волах в секунду) R •< С, то с помощью соответствующим образом по- строенных кодера и декодера можно воспроизводить двоичные символы на выходе декодера со сколь угодно малой вероятностью ошибки. Этот результат точно сформулирован и доказан в гл. 5 для дискретного ка- нала и в гл. 7 и 8 для недискретных каналов. Далеко идущее значение этой теоремы будет обсуждаться ниже в этом параграфе, однако до гл. 5 на интуитивном уровне можно сказать не так уж много. Если объеди- нить этот результат с теоремой кодирования для источников, которая была указана в предыдущем параграфе, то найдем, что если дискретный источник имеет энтропию (в битах в секунду) меньшую, чем С, то выход источника может быть воспроизведен на приемном конце с произволь- но малой вероятностью ошибки с помощью использования соответст- вующего кодирования и декодирования. Аналогично для недискрет- ного источника, если R является минимальным числом двоичных сим- волов в секунду, требующихся, чтобы воспроизвести выход источника с данным уровнем среднего искажения, и если R < С, то выход источ- ника может быть передан по каналу и воспроизведен с""этим уровнем искажения. Обращение теоремы кодирования формулируется и доказывается при различной степени общности в гл. 4, 7 и 8. В не очень строгой фор- мулировке она утверждает, что если энтропия дискретного источника в битах в секунду больше, чем С, то независимо от кодирования и деко- дирования, использованных при передаче выхода источника по каналу, вероятность ошибки при воспроизведении выхода источника на прием- ном конце не может быть меньше, чем некоторое положительное число, которое зависит от источника и от С. Так же как показано в гл. 9, если R является минимальным числом двоичных символов в секунду, требуе- мых для воспроизведения источника с заданным уровнем среднего искажения, и если R > С, то независимо от кодирования и декоди- рования выход источника не может быть передан по каналу и воспро- изведен с этим заданным уровнем среднего искажения. Наиболее удивительным и важным среди указанных выше резуль- татов является теорема кодирования для канала с шумами, которую мы обсудим сейчас более детально. Предположим, что требуется передать данные по дискретному каналу и что по каналу передается одна вход- ная буква за каждые т с секунд. Предположим также, что двоичные дан- ..ные поступают на кодер для канала со скоростью R двоичных символов в секунду. Рассмотрим частный вид кодеров для канала, которые назы- ваются блоковыми кодерами; блоковый кодер работает следующим об- разом. Кодер накапливает двоичные символы на входе кодера в те- чение некоторого фиксированного интервала Т секунд, где Т является конструктивным параметром кодера. Во время этого интервала TR двоичных символов поступают на кодер (для простоты мы пренебрегаем здесь тем, что TR может не быть целым числом). Кодер можно предста- вить себе как устройство, которое имеет список всех 2TR• возможных последовательностей TR двоичных символов и сопоставленного каж- дой из этих последовательностей кодового слова, состоящего из последо- вательности N == Т/Тс букв на входе канала. При получении некоторой отдельной последовательности TR двоичных символов кодер отыски- вает эту последовательность в списке и передает по каналу соответст- вующее кодовое слово из списка. Требуется Т секунд, чтобы передать N — буквенное кодовое слово по каналу, и за это время другая после- довательность TR двоичных символов поступит на кодер и начнется передача следующего кодового слова. Простой пример такого кодера представлен на рис. 1.3.3. В этом примере, когда двоичная последова- тельность ООН... поступает на кодер, то 00 является входом кодера на первом интервале в Т секунд, и в конце этого интервала формирует- ся кодовое слово а^а^ и передается за интервал времени в Т секунд. Аналогично 11 является входом кодера на втором интервале времени в Т секунд, и a-fl^a-s,—соответствующим кодовым словом, передаваемым в течение третьего интервала времени. Декодер для такого блокового кодера работает аналогичным образом. Декодер накапливает N принятых символов, поступающих из канала и соответствующих переданному кодовому слову, и строит решения (возможно неправильные) относительно соответствующих TR двоичных символов, которые поступили на" кодер. Можно считать, что эта процедура решения выполняется декодером с помощью списка всех возможных принимаемых последовательностей из N символов и соот-' ветствующей каждой из этих последовательностей последовательности из 7'R двоичных символов. Для данного дискретного канала и данной скорости R (в двоичных символах в секунду) поступления символов на кодер имеется свобода 26 в выборе, во-первых, Т (или, что эквивалентно, свободе в выборе N = == 77тс), во-вторых, множества 2ГR кодовых слов и, в-третьих, правила решения. Вероятность ошибки в декодированных двоичных данных, сложность системы и задержка при декодировании зависят от этих вы- боров. В гл. 5 будет установлено следующее соотношение между пара- метром Т и вероятностью Ре ошибочного декодирования блока TR двоичных символов. Будет показано, что для широкого класса каналов можно выбрать 2TR кодовых слов и правило решения таким образом, что Ре<ехр [—ТЕ (R)]. функция Е (R) является функцией R (числа двоичных символов в се- кунду, поступающих на кодер) и зависит от модели канала, но не зави- сит от Т. Показывается, что Е (R) убывает с ростом R, но остается по- Двоичная послеаова -гпельность на входе кодера Кодовое слово на. выходе кодера. 00 Ofю и -ч- д/д/д/ -«- а^а^а/ -» а^а,аг ->• а, а, a-J Рис. 1.3.3. Пример кодера для дискретного канала, TR=2, N"3. Рис. 1.3.4. График функции E(R) для типичной модели канала. ложительной при всех R меньших, чем пропускная способность (рис. 1.3.4). Оказывается, что приведенная выше граница для Р с яв- ляется довольно точной, и не является нецелесообразным рассмотрение ехр [—ТЕ (R)] в качестве оценки минимальной вероятности ошибки (по всем выборам 27"^ кодовых слов и всем правилам решения), которая может быть достигнута при использовании блокового кодера с за- данным временем Т. Таким образом, чтобы сделать Ре малой, необхо- димо выбрать Т большим, и чем R ближе к С, тем больше должно быть Т. В гл. 6 будут рассмотрены способы построения кодеров и декоде- ров для канала. Трудно дать простые утверждения, касающиеся слож- ности и вероятности ошибки этих устройств. Однако, грубо говоря, не трудно заметить, что сложность увеличивается с ростом времени Г (для наилучших способов, приближенно линейно с Т), что Ре убывает с ростом Т при фиксированной R и что Г должно возрастать вместе с ростом R для достижения фиксированного значения Ре. Следователь- но, грубо говоря, имеется обменное соотношение между сложностью, скоростью и вероятностью ошибки. Чем ближе R к пропускной спо- собности и чем меньше Р е, тем требуется большая сложность кодера и декодера. Имея в виду указанное выше обменное соотношение, на рис. 1.3.2 можно увидеть с большей ясностью практические преимущества разде- 27 ления кодера и декодера на две части. В последние годы стоимость циф- ровых логических устройств постоянно снижалась, в то время как та- кой революции не было в технике аналоговых устройств. Таким обра- зом, в сложной системе желательно выполнить самые сложные опера- ции в цифровой части системы. Это не говорит, конечно, о том, что ана- логовые системы связи полностью вышли из моды, но просто говорит, что, когда отдается предпочтение цифровым системам, возникают мно- гие преимущества не существовавшие еще десять лет тому назад. ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ Многое в современной теории связи исходит из работ Шеннона (1948), Винера (1949) и Котельникова (1947). Все они ясно понимали фундаментальную роль шума в ограничении точности передачи в си- стемах связи, а также желательность моделирования как сигнала, так и шума с помощью случайных процессов. Винер интересовался отыс- канием наилучшего линейного фильтра для разделения сигнала и адди- тивного шума при заданной задержке, и его работа оказала важное влияние на последующие исследования в теории модуляции. Кроме того, интерес Винера к приему с отрицательной задержкой (т. е. к пред- сказанию) вместе с работой Колмогорова (1941) по предсказанию в от- сутствии шума дали важный толчок в развитии теории управления. Аналогично Котельников интересовался обнаружением и оценкой сигналов на приемном конце. Хотя его работа не так широко известна и используется в Соединенных Штатах (как должно было быть), она внесла значительное понимание как аналоговой модуляции, так и дискретной модуляции. Работа Шеннона много больше, чем остальные, связана с дискрет- ной техникой и, что более важно, сфокусирована на кодере и декодере в совокупности. Благодаря этому совместному рассмотрению и благо- даря тому, что она не ограничивается частными типами приемных устройств, теория Шеннона дает наиболее общие из известных концеп- ций, которые можно заложить в основу при изучении эффективной и надежной передачи. Хорошее теоретическое введение в теорию связи дают учебники Возенкрафта и Джекобса (1965) и Сакрисона (1968). МЕРА ИНФОРМАЦИИ Понятия информации и связи в нашем мире являются слишком широкими и емкими, чтобы можно было ожидать какую-либо универ- сально применимую количественную меру информации. Однако, как это было объяснено в предыдущей главе, имеется множество ситуаций в связи (в особенности таких, которые включают в себя передачу и об- работку данных), для которых информация (или данные) и канал адекватно представляются вероятностными моделями. Меры инфор- мации, которые будут определены в этой главе, соответствуют этим вероятностным ситуациям, и вопрос о том, насколько адекватны эти меры, зависит в общем от адекватности вероятностной модели. 2.1. ДИСКРЕТНЫЕ ВЕРОЯТНОСТИ; ОБЗОР И ОБОЗНАЧЕНИЯ Можно представить себе вероятностную модель как эксперимент, исход которого выбирается из множества возможных исходов с ве- роятностной мерой, заданной на этих возможных исходах. Множество возможных исходов называется выборочным пространством. Для дискретного множества возможных исходов вероятностная мера просто означает приписывание вероятности каждому исходу. Вероятности, конечно, не отрицательны и сумма их равна единице. Выборочное пространство и его вероятностная мера называются ансамблем*); ан- самбль будет обозначаться заглавной буквой; исход эксперимента — той же самой, но строчной буквой. Для ансамбля U с выборочным пространством {QI, 0:2, ..., а к} вероятность того, что исходом и будет некоторый заданный элемент а^ выборочного пространства, будет обозначаться Рц(а.]^. Вероятность того, что исходом будет произволь- ный элемент и, обозначается через Ру(ы). В этом выражении нижний индекс U используется для того, чтобы отметить, какой ансамбль рас- сматривается, а аргумент и используется как переменная, которая при- нимает значения из выборочного пространства. Когда это не вызовет путаницы, нижний индекс будет опускаться. Например, ансамбль U может представлять выход источника в некоторый заданный момент времени; в этом случае алфавит источни- ка есть множество букв {QI, ..., а.к} и Рц (а^) является вероятностью того, что выходом будет буква йд. Обычно мы будем иметь дело с экспе- риментами не с одиночным исходом, а с несколькими. Например, нас *> Почти везде в математической литературе то, что мы называем здесь ан- самблем, называется вероятностным пространством. 29 может интересовать последовательность букв источника, или вход и выход канала, или последовательность входов и выходов канала. Обозначим исходы эксперимента с парой исходов через л- и у, и пусть х принимает значения на множестве исходов а^, ..., од-, а у выбирается на множестве исходов Ь^, ..., bj. Множество {fli, ..., Ок} называется выборочным пространством X; множество {Ь^, ..., bj} на- зывается выборочным пространством Y, а множество пар {а^Ь,}, 1 ^ ^ k ^ К, 1 ^ /' ^ J называется совместным выборочным простран- ством. Вероятностная мера на совместном выборочном пространстве задается совместной вероятностью Рд-у (а^, bj), определенной для 1 ^ ё^ k <; К., 1 < / < J. Совокупность совместных выборочного про- странства и вероятностной меры для исходов х и у называется совмест- ным ХУ-ансамблем. В ансамбле или совместном ансамбле событие определяется как подмножество элементов выборочного пространства. Для дискретного ансамбля вероятность события равна сумме вероятностей элементов выборочного пространства, содержащихся в этом событии. В рассмат- риваемом ХУ-ансамбле событие, состоящее в том, что х принимает не- которое частное значение а^, соответствует подмножеству пар {afebi; афч, ...; ahbj}. Таким образом, вероятность этого события равна РхЮ- 2Рху(а„^.). (2.1.1) /=i В более сокращенной записи то же равенство имеет вид Р(х)=2Р(х,у). (2.1.2) Подобно этому вероятность данного исхода у равна Р(У)-^Р{Х,У). (2.1.3) Следует соблюдать определенную осторожность при обращении с обозначениями Р {х) и Р (у) в равенствах (2.1.2) и (2.1.3) . Символы х и у играют двойную роль: они обозначают как тот исход, который рассматривается, так и переменную. В частности, если выборочные про- странства х и у одни и те же, мы не можем подставить элементы выбо- рочного пространства вместо х и у, не вызвав неопределенности. ' Если Р д- (а?;) > 0, то условная вероятность того, что исходом у является bj при условии того, что исходом х является <7д, определяется равенством Pyv(cih, h,) ^|х(^)=-^———-- (2-1-4) гx(ak> В сокращенной записи оно имеет вид Р(у х) = Р (х, у)/Р (х). (2.1.5) Подобно этому Р(х\у)=Р(х, у)/Р(у). (2.1.6) 30 События х == мые, если Рху(а^Ь,)=Рх(а^Ру(Ь,). Если Р х (dfi) >• 0, то последнее равенство эквивалентно Ру^(Ь,\а^=Ру(Ь,}, Яд и у = Б] по определению статистически независи- (2.1.7) (2.1.8) т. е. условие не меняет вероятность того, что у == bj. Ансамбли Х и У являются статистически независимыми, если условие (2.1.7) удовлет- воряется для всех пар а^Ь, из совместного выборочного пространства. Рассмотрим далее эксперимент со многими исходами, скажем Ui, и.г, ..., UN, каждый из которых выбирается из некоторого множества возможных исходов. Множество возможных исходов для Un называется выборочным пространством для t/„, I <;ra < N, а множество возмож- ных исходов для последовательности Ui, ..., Uy, называется совместным выборочным пространством эксперимента. Для дискретных выбороч- ных пространств вероятностная мера задается совместной вероят- ностью Ру, ... УЛГ ("!' •••' и^), определенной для каждой последова- тельности исходов «1 ..., UN в аргументе. Совокупность совместного выборочного пространства и совместного распределения вероятности называется совместным ансамблем U^, ..., UN. Распределение вероятностей частных исходов и совокупностей ис- ходов определяется с помощью Р («i, ..., и^) так же, как в случае двух исходов. Например, Pu^Un} ==2. • .2- • -2^("i,. • .,".,..., и»), (2.1.9) "' "i "м I in где суммирование распространяется по всем возможным исходам для каждого исхода эксперимента, отличного от тг-го. Точно так же ^J""' "m)=2. • .2. . .^P(Ul,- ..,"„..., "Л-). (2.1.10) "1 "г "•f/ i=i--n l^m Ансамбли L/i, [/2, ..., UN называются статистически независимыми, если для всех и^, ..., и^ (2.1.11) В качестве примера использования этих обозначений рассмотрим последовательность N букв источника с двоичным алфавитом О, 1. Выборочным пространством для каждого tin является множество {О, 1}. Совместным выборочным пространством эксперимента является множество всех 2^ последовательностей из N двоичных цифр. Вероят- ностная мера задает вероятность каждой из этих последовательностей. В частном случае, когда буквы источника статистически независимы, зти вероятности имеют вид (2.1.11). Если YV букв имеет одинаковое рас- 31