В. Д. КОЛЕСНИК Г. Ш. ПОЛТЫРЕВ КУРС ТЕОРИИ ИНФОРМАЦИИ Допущено Министерством высшего и среднего специального образования СССР в качестве учебного пособия для студентов высших технических учебных заведений МОСКВА <НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1 982 32.S1 К60 УДК 62-50 Курс теории информации. Колесник В. Д., П о л т ы р е в Г. Ш. — М.: Наука. Главная редакция физико-мате.у.атической литературы. 1982. — 416 с. Теория информации представляет собой ветвь статистической теории связи, круг проблем которой можно охарактеризовать как исследования кодирования для обработки и передачи сообщений. Книга состоит из следующих пяти разде- лов: кодирование дискретных источников, кодирование в дискретных каналах, кодирование в непрерывных каналах, кодирование непрерывных источников и кодирование в системах с многими пользователями. Основные параграфы книги задуманы как пособие для студентов, впервые знакомящихся с теорией информа- ции. Дополнительные параграфы, отмеченные звездочкой, предназначены для углубленного изучения «традиционной» теории информации и могут быть полезны аспирантам. Особое место в книге занимает глава, посвященная кодированию в системах с многими пользователями, содержащая наиболее поздние результаты теории информации. Для чтения этой части нужна определенная теоретико- информационная эрудиция. Каждая глава снабжена рядом задач и упражнений. Табл. 8, илл. 56, библ. 70 назв. Виктор Дмитриевич Колесник, Григорий Шоулович Полтырев Курс теории информации Редактор Г. Л. Кацман Техн. редактор И. Ш. Аксельрод Корректоры О. А. Бутусова, Л.С. Сомова И Б Ns 11892 Сдано в набор 27.01.82. Подписано к печати 11.11.82. Т-20915. Формат eOXOO'/m. Бумага типографская № 1. Гарнитура литературная. Печать высокая. Усл. печ. л. 26. Уч.-изд. л. 28,99. Тираж 14000 экз. Заказ 119. Ценд 1 р. 20 к. Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 Ленинградская типография № 6 ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 193144, г. Ленинград, ул. Монсеенко, 10. К 1502000000—157 053(02)-82 119-82 Издательство «Наука». Главная редакция физико-математической литературы, 1982 ОГЛАВЛЕНИЕ Предисловие ............................ 6 Глава 1. Кодирование дискретных источников .......... 11 .1. Дискретные ансамбли и источники ............ 11 .2. Случайные величины. Закон больших чисел ........ 19 .3. Количество информации в сообщении. Энтропия ...... 24 .4. Условная информация. Условная энтропия ........ 27 .5. Энтропия на сообщение дискретного стационарного источника 31 .6. Постановка задачи кодирования дискретных источников равномерными кодами .................. 34 ^ 1.7. Теорема о высоковероятных множесгвах дискретного источ- ника без памяти ..................... 39 V § 1.8. Скорость создания информации дискретным источником без памяти при равномерном кодировании ........... 41 § 1.9. Эргодические дискретные источники ............ 44 § 1.10. Постановка задачи неравномерного кодирования дискретных источников. Коды с однозначным декодированием ..... 54 § 1.11. Кодовые деревья. Неравенство Крафта ........... 58 § 1.12. Неравномерное кодирование дискретных стационарных ис- точников ......................... 60 § 1.13. Оптимальные неравномерные коды ............ 64 § 1.14. Обсуждение основных результатов ............ 68 Задачи, упражнения и дополнения ................ 72 Краткий исторический комментарий и литература ......... 78 Глава 2. Взаимная информация и ее свойства .......... 80 §2.1. Количество информации между дискретными ансамблями 80 § 2.2. Непрерывные ансамбли и источники. Обобщение понятия количества информации ................. 88 § 2.3. Относительная энтропия и ее свойства ........... 100 § 2.4*. Ортогональные преобразования случайных векторов .... 107 § 2.5*. Выпуклость средней взаимной информации ........ 112 § 2.6*. Случайные процессы непрерывного времени ........ 119 § 2.7*. Средняя взаимная информация между случайными про- цессами ......................... 128 § 2,8*. Поиск экстремумов ................... 130 2.8.1. Метод неопределенных множителей Лагранжа (130). 2.8.2. Не- обходимые условия Куна—Таккера (132). 2.8.3. Достаточность условий Куна—Таккера для выпуклых функций (136). 2.8.4. Поиск экстремумов на множестве вероятностных векторов (137). Задачи, упражнения и дог.-слнения ................ 140 Краткий исторический комментарий и литература ......... 151 Глава 3. Кодирование в дискретных каналах ........... 153 § 3.1. Классификация ка;:алсв СЕЯЕИ .............. 153 § 3.2. Постановка задачи кодирования в дискретном канале ... 158 4 ОГЛАВЛЕНИИ § 3.3. Неравенство Фано .................... 163 § 3.4. Общая обратная теорема кодирования для дискретных каналов ........................ 167 . i § 3.5. Информационная емкость дискретных каналов без памяти 169 I 3.5.1. Упрощение формулы (3.4.3) (169). 3.5.2*. Вычисление информационной емкости дискретного канала без памяти (171). § 3.6. Симметричные дискретные каналы без памяти ....... 179 § 3.7. Дискретные стационарные каналы с аддитивным по модулю L шумом ......................... 182 § 3.8. Неравенство Файпстейна ................. 185 § 3.9. Прямая теорема кодирования для дискретных каналов без памяти ........................ 190 § 3.10. Прямая теорема кодирования для дискретных стационар- ных каналов с аддитивным эргодическим шумом ..... 192 § 3.11. Декодирование для кодов с заданным множеством кодовых слов .......................... 194 § 3.12. Верхняя граница вероятности ошибки декодирования для дискретных каналов без памяти ............. 197 3.12.1. Метод случайного кодирования (197). 3.12.2. Оценка средней по ансамблю кодов вероятности ошибки декодирования для произвольного дискретного канала (197). 3.12.3. Оценка средней по ансамблю кодов вероятности ошибки декодирования для дискретных каналов без памяти (200). 3.12.4*. Свойства функции Е, (р, О) и построение экспоненты случайного кодиро- вания (203). 3.12.5*. Показатель экспоненты случайного кодирования для симметричных каналов без памяти (211). § 3.13*. Нижняя граница вероятности ошибки декодирования для дискретных каналов без памяти (граница сферической упа- ковки) ......................... 215 3.13.1. Нижняя граница вероятности ошибки для ДСК (215). 3.13.2. Коды с фиксированной композицией (219). 3.13.3. Нижняя граница для вероятности ошибки декодирования кода с фикси- рованной композицией (221), 3.13.4. Совместное рассмотрение экспонент случайного кодирования и сферической упаковки (227). Задачи, упражнения и дополнения ................ 234 Краткий исторический комментарий и литература ......... 246 Глава 4. Кодирование в непрерывных каналах .......... 248 § 4.1. Непрерывные каналы с дискретным временем. Обратная тео- рема кодирования .................... 249 § 4.2. Непрерывные каналы без памяти с дискретным временем . . . 254 § 4.3*. Каналы с непрерывным временем. Обратная теорема кодиро- вания .......................... 261 § 4.4*. Прямая теорема кодирования для непрерывных каналов с аддитивным белым гауссовским шумом ......... 270 Задачи, упражнения и дополнения ................ 275 Краткий исторический комментарий и литература ......... 281 Глава 5. Кодирование источников с заданным критерием качества 282 § 5.1. Критерии качества. Постановка задачи кодирования с за- данным критерием качества ............... 283 § 5.2. Эпсилон-энтропия и ее свойства .............. 290 § 5.3. Обратная теорема кодирования непрерывных источников при заданном критерии качества ............. 295 § 5.4. Эпсилон-энтропия гауссовского источника без памяти . . . 297 ОГЛАВЛЕНИЕ 5 § 5.5. Прямая теорема кодирования стационарного источника не- зависимых гауссовских сообщений при квадратическом кри- терии качества ..................... 300 5.5.1. Закон больших чисел и принцип «затвердевания сферы» (300). 5.5.2. Аппроксимация векторов, лежащих на поверхности «-мерной сферы (302). 5.5.3. Аппроксимация последовательно- стей сообщений источника с помощью е-сети на гг-мерной сфере (304). 5.5.4. Прямая теорема кодирования (307). 5.5.5. Обсу- ждение (311). § 5.6 *. Эпсилон-энтропия гауссовского случайного вектора .... 313 5.6.1. Эпсилон-энтропия системы независимых гауссовских случай- ных величин (314). 5.6.2, Эпсилон-энтропия системы зависимых •гауссовских случайных величин (317). § 5.7 *. Эпсилон-энтропия стационарного гауссовского процесса дис- кретного времени .................... 319 § 5.8 *. Формулировка прямой теоремы кодирования для стацио- нарного гауссовского источника с дискретным временем . . . 323 Задачи, упражнения, дополнения ................. 324 Краткий исторический комментарий и литература ......... 332 Глава б*. Кодирование в системах с многими пользователями . . 333 § 6.1. Кодирование зависимых источников ............ 335 6.1.1. Постановка задачи (335). 6.1.2. Обратная теорема кодиро- вания (338). 6.1.3. Прямая теорема кодирования (340). § 6.2. Кодирование источников с дополнительной информацией . . . 345 6.2.1. Постановка задачи (345). 6.2.2. Функция Т (d) и ее свой- ства (348). 6.2.3. Обратная теорема кодирования (354). 6.2.4. Пря- мая теорема кодирования (366). § 6.3. Кодирование в каналах с множественным доступом ..... 364 6.3.1. Постановка задачи (364). 6.3.2. Двоичный суммирующий КМД (367). 6.3.3. Обратная теорема кодирования (370). 6.3.4. Пря- мая теорема кодирования (374). § 6.4. Кодирование в широковещательных каналах ........ 378 6.4.1. Постановка задачи (378). 6.4.2. Ухудшающиеся широко- вещательные каналы (УШК.) (382). 6.4.3. Двоичный симметричный широковещательный канал (384). 6.4.4. Обратная теорема коди- рования (387). 6.4.5. Прямая теорема кодирования (396). Задачи, упражнения и дополнения ................ 401 Краткий исторический комментарий и литература ......... 409 Приложение I ........................... 411 Приложение II .......................... 412 Предметный указатель ....................... 414 ПРЕДИСЛОВИЕ Теория информации представляет собой ветвь статистической теории связи (ее часто с нею отождествляют), основы которой были заложены классическими трудами Н. Винера, А. Н. Колмо- горова, В. А. Котельникова и К. Шеннона. Круг проблем, соста- вляющих основное содержание д-еорни информации (проблем «шенноновской теории информации»), можно охарактеризовать как исследование методов кодирования для экономного предста- вления сообщений различных источников и для надежной пере- дачи сообщений по каналам связи с шумом. В основе теории информации лежит статистическое описание (статистические модели) источников сообщений и каналов связи, а также основанное на этом описании измерение количества информации между сообщениями по Шеннону, т. е. такое, при котором количество информации определяется только вероятно- стными свойствами сообщений и ни от каких других их свойств ^ не зависит. В отличие от других разделов теории связи, например, - теории обнаружения, теории оценивания, теории модуляции, алгебраической теории кодирования и т. д., предметом теории информации, как правило, являются теоремы, устанавливающие предельные возможности различных методов обработки и пере- дачи сообщений. Эти предельные возможности зависят только от статистических свойста источников и каналов. В качестве примеров можно привести три типичные задачи теории информации. 1. Предположим, что задан источник сообщений. Требуется найти наименьшее количество символов (например, двоичных), которое необходимо для указания последовательности сообщений, порожденных источником. При этом может быть задан критерий качества восстановления сообщений источника и требоваться указание последовательности сообщений с ошибкой относительно данного критерия качества, не превосходящей заданную вели- чину. 2. Предположим, что задан канал связи. Требуется найти наибольшую возможную скорость передачи по этому каналу, при которой вероятность ошибочного приема сообщений может быть сделана произвольно малой. 3. Предположим, что заданы источник и канал, а также задан критерий качества. Требуется определить наименьшую возмож- ПРЕДИСЛОВИЕ 7 ную относительно данного критерия качества величину ошибки, которую можно достичь, передавая сообщения данного источника по данному каналу связи. Всякий раз, решая подобные задачи, пытаютсяТне только найти предельные значения количества двоичных символов, ско- рости передачи или величины ошибки, но и найти некоторый способ обработки сообщений (некоторый способ кодирования и декодирования), который позволяет достичь указываемых пре- делов. Однако очень часто не удается указать наилучший способ кодирования и декодирования. Поэтому теория информации, как правило, не дает непосредственных практических рекомендаций инженерам, проектирующим аппаратуру обработки и передачи сообщений. Тем не менее, она является важным инструментом анализа различных технических систем: телеметрических систем, систем передачи речи или телевизионных изображений, систем передачи данных, банков данных, различных систем управления и т. д. На основе теории информации можно ответить на вопросы о предельных возможностях перечисленных систем, определить, в какой мере проектируемая система уступает теоретически воз- можной. Следует отметить также, что в некоторых случаях логика вывода, используемая в теории информации, подсказывает путь, на котором может быть найдено конструктивное решение для дан- ной реальной системы. Первоначально теория информации возникла из инженерных задач радиосвязи и телеграфии. Датой ее рождения считают 1948 год, год появления двух основополагающих статей американ- ского инженера и математика Клода Шеннона «Математическая теория связи» и «Связь при наличии шума» (см.: Шеннон К., Сборник работ по теории информации и кибернетике. —М.: ИЛ, 1963). Начиная с этого времени, теория информации бурно раз- вивалась, главным образом благодаря работам математиков и математически образованных инженеров. Нельзя не отметить огромный вклад, который внесли в теорию информации Дж. Воль- фовиц, Р. Галлагер, Р. Л. Добрушин, А. Н. Колмогоров, М. С. Пинскер, В. И. Сифоров, А. Файнстейн, Р. Фано, А. А. Хар- кевич, А. Я. Хинчпн и многие другие. В результате развития теории информации основная часть теоретических работ стала носить математически сложный характер, и образовался опре- деленный разрыв между инженерами-практиками и адресованной в первую очередь им прикладной математической теорией. К со- жалению, до настоящего времени этот разрыв не имеет тенденции уменьшаться; желание его преодолеть было одним из основных стимулов при написании этой книги, которая по замыслу авторов должна помочь студенту технического вуза познакомиться с тео- рией информации или ее отдельными разделами. ПРЕДИСЛОВИЕ Сегодня можно указать две основные книги, которые могут служить учебниками по теории информации. Это книга Р. Фано «Передача информации. Статистическая теория связи» (Мир, 1965) и книга Р. Галлагера «Теория информации и надежная связь» (Сов. радио, 197'4). Обе эти книги написаны известными американскими учеными, внесшими существенный вклад в теорию информации. Однако обе они в значительной степени носят моно- графический характер и предназначены достаточно подготовлен- ным читателям. Следует также отметить одну из первых книг на русском языке — книгу Ф. П. Тарасенко «Введение в курс теории информации» (изд. Томского ун-та, 1963) и книгу Р. Л. Страто- новича «Теория информации» (Сов. радио, 1975), посвященную нетрадиционному изложению шенноновской теории информации с позиций статистической термодинамики. Настоящая книга состоит из следующих пяти основных частей: кодирование дискретных источников, кодирование в дискретных каналах, кодирование в непрерывных каналах, кодирование непрерывных источников и кодирование в системах с многими пользователями. В первой главе рассматривается задача точного или сколь угодно точного кодирования дискретных источников. В ней дается ответ на вопрос, каково наименьшее количество двоичных симво- лов на сообщение, по которому можно точно или с какой угодно малой вероятностью ошибки восстановить последовательность сообщений на выходе дискретного источника. Во второй главе задачи кодирования не рассматриваются. Она посвящена исследованию свойств количества информации для различных вероятностных объектов. Кроме того, в этой главе приводятся математические сведения, необходимые для чтения этой и последующих глав книги. В третьей главе рассматривается задача кодирования в ди- скретных каналах связи и дается ответ на вопрос, каково наи- большее количество информационных двоичных символов, кото- рое может быть передано по каналу связи в единицу времени при условии, что вероятность ошибки при определении переданных сообщений может быть сделана сколь угодно малой величиной. Кроме того, в этой главе строятся верхняя и нижняя границы вероятности ошибки декодирования для дискретных каналов без памяти. Четвертая глава посвящена обобщению результатов третьей главы на случай различных непрерывных каналов. В пятой главе рассматривается задача кодирования источников при заданном критерии качества (теория эпсилон-энтропии). В ней дается ответ на вопрос, каково наименьшее количество двоичных символов на сообщение, по которым можно восстановить с заданной ошибкой относительно выбранного критерия качества ПРЕДИСЛОВИЕ последовательность сообщений на выходе некоторого источ- ника. Шестая глава посвящена задачам кодирования в системах с многими пользователями (многими источниками, каналами связи и получателями сообщений). Здесь также даются ответы на вопросы о минимальном числе двоичных символов на сообщение источника или о максимальном числе информационных двоичных символов, передаваемых по каналу в единицу времени, в ситуа- ции, когда имеется несколько источников и они зависимы или когда имеется несколько каналов и передача по одному каналу мешает передаче по другим. В книге имеются основные и дополнительные параграфы. Основные задуманы как пособие для читателя, который впервые знакомится с теорией информации и который не рискнул бы счи- тать себя хорошо владеющим теорией вероятностей. Тем не менее, эта часть книги позволяет читателю проникнуть в проблематику теории информации и познакомиться с ее основными результатами, пройдя через все трудности доказательств. Следующие параграфы являются основными: вся гл. I, §§ 2.1—2.3, вся гл. III (кроме пп. 3.5.2, 3.12.4, 3.12.5 и §3.13), '§§ 4.1, 4.2, 5.1—5.5. Эти раз- делы могут составить материал для односеместрового курса лек- ций по теории информации. Курсы лекций примерно с таким содержанием читаются в течение ряда лет в Ленинградском ин- ституте авиационного приборостроения. При рассмотрении основ- ных разделов сделана попытка упростить изложение за счет суже- ния круга рассматриваемых вопросов, использования в связи с этим более простой математической техники, более подробного обсуждения постановок задач и примеров. Кроме того, здесь даются все необходимые математические сведения, что делает .эту часть книги в определенной мере самостоятельной. Дополнительных параграфов несколько (в книге они помечены звездочкой над номером параграфа). Все, что не вошло в пере- численные выше основные параграфы (в пределах первых пяти глав), можно рассматривать как дополнительный материал, пред- назначенный для углубленного изучения «традиционной» теории информации. Хотя многие математические сведения здесь также приводятся, предполагается, что читатель знаком с элементами функционального анализа, с элементами теории случайных про- цессов и с элементами нелинейного программирования. Кроме того, для чтения этих разделов требуется несколько большая мате- матическая тренированность. Особое место в книге занимает шестая глава, посвященная задачам кодирования в системах с многими пользователями. В ней представлены результаты, полученные в теории информации в течение последнего десятилетия и отражающие развитие совре- менных систем обработки и передачи информации. Содержание 10 ПРЕДИСЛОВИЕ шестой главы адресовано в первую очередь читателям,- хорошо знакомым с традиционными вопросами теории информации, на- пример, по книге Р. Галлагера, или хорошо овладевшим содержа- нием первых пяти глав 'настоящей книги. Для успешного чтения этой главы от читателя требуется наличие определенной теоре- тико-информационной эрудиции. Каждая глава снабжена рядом задач, упражнений и дополне- ний. Среди задач и упражнений имеются очень простые, предна- значенные только для проверки того, что читатель правильно понял формулировки определений и теорем. Имеются задачи, ко- торые требуют овладения техникой доказательств. В ряде случаев приводятся дополнительные сведения, затрагивающие как методы, так и интересные и важные результаты теории информации, кото- рые по тем или другим соображениям не включены в основной текст, но которые могут быть полезны при более глубоком изуче- нии теории или при использовании теории на практике. В заключение отметим, что хотя в книге содержатся основные математические сведения, которые используются при изложении рассматриваемых теоретико-информационных задач, их явно не- достаточно для глубокого понимания математических основ теории информации. Читателю, желающему более детально познако- миться с этими основами, мы рекомендуем обратиться к следующим книгам. С теорией вероятностей лучше знакомиться по книгам Б. В. Гнеденко «Курс теории вероятностей» (Наука, 1965) и В. Феллера «Введение в теорию вероятностей и ее приложения», т. I (Мир, 1967). С элементами теории случайных процессов можно познакомиться по книге В. Б. Давенпорта и В. Л. Рута «Вве- дение в теорию случайных сигналов и шумов» (ИЛ, 1960). Основы матричной алгебры и теория операторов в конечномерных про- странствах лучше всего изложены в книгах Ф. Р. Гантмахера «Теория матриц» (Наука, 1967) или Р. Беллмана «Введение в тео- рию матриц» (Наука, 1969). По книге Б. 3. Вулиха «Введение в функциональный анализ» (Наука, 1967) можно познакомиться с элементами функционального анализа. Авторы выражают огромную признательность всем, кто зна- комился с многочисленными вариантами рукописи этой книги и делился своими замечаниями. Особенно большое влияние на работу авторов оказали замечания и советы Ю. М. Штарькова и рецензентов — Р. Л. Добрушина и Э. М. Габидулина. Глава! КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ В этой главе будут даны основные определения: дискретного вероятностного ансамбля, дискретного источника, дискретной случайной величины на ансамбле и кода для дискретного источ- ника. Дискретные источники представляют собой наиболее простой объект теории информации. Начинать именно с этого типа источ- ников удобно не только потому, что здесь требуется наименьшее количество определений и вспомогательных результатов, но и по- тому, что на этом простом объекте можно показать методологию теории информации и продемонстриропать ее основные техниче- ские приемы. Задача, которая рассматривается в этой главе, весьма часто встречается на практике и иногда называется задачей сжатия данных. Предположим, что некоторый источник порождает после- довательность дискретных сообщений и требуется представить эту последовательность с помощью некоторых символов, скажем, с помощью нулей и единиц. Не вызывает сомнения то, что это можно сделать для любой последовательности сообщений. Вопрос может заключаться в том, как это сделать наиболее экономным образом, т. е. как затратить на это наименьшее количество двоич- ных символов. Ответ на этот вопрос лежит в изучении различных статистических моделей источников и определения для этих моде- лей величины, называемой скоростью создания информации. Будет показано, что скорость создания информации равна энтро- пии источника на сообщение, величине, которая определяется с помощью вводимого в этой главе понятия количества информа- ции р. сообщении. § 1.1. Дискретные ансамбли и источники -__ Основным объектом изучения в этой главе будут дискретные источники сообщений. Здесь мы дадим определения, необходимые для описания математических моделей источников. Описание источников удобно начать с определения дискретных вероятностных ансамблей. Пусть Х ~- [х^. ..., х^\ — множество, состоящее из М элементов. Прописные латинские буквы X, У и т. д. будут обозначать сами множества, а соответствующие строчные буквы х, i/ и т. д. будут обозначать элементы множеств. 12 Гл. 1. КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ Иногда элементы множеств мы будем снабжать подстрочными индексами, как это сделано выше. Такой индекс представляет собой номер элемента в множестве. Хотя для большинства случаев природа элементов несущественна, мы будем называть элементы множеств Х сообщениями, подчеркивая тем самым область при- ложения теории. Говорят, что на конечном множестве Х задано распределение вероятностей р (х), если каждому элементу х, ^ Х сопоставлено число р (xi), причем р(х,)^0, i =1,2, М, (1.1.1) м Пусть А есть подмножество множества X, Л ^ X. Число *) Рг(Л)4 S Р(х.) ^<=-4 представляет собой вероятность того, что при случайном выборе сообщения из множества Х в соответствии с распределением р (х}, будет выбрано сообщение, принадлежащее множеству А. Число Рг (Л) называют также вероятностью множества Л. Пример 1.1.1. Пусть Х — множество сообщений о'результатах бросания правильной игральной кости. Тогда .Y —- {д-,, ..., Хц). р (л-,) = l,'^^, i == 1, ..., 6, причем Xt есть сообщение о том, что выпало i очков. Если Л — [х^, х^, Ху], то Рг (A)==3•l/s=l/2 есть вероятность того, что при бросании кости выпало четное число очков. Сообщения Xi G ^ иногда называют элементарными событи- ями. Как показывает предыдущая формула, могут одновременно рассматриваться как элементарные события, так и более сложные события, являющиеся объединением некоторого числа элементар- ных. Мы используем различные обозначения для вероятностей таких событий: р (xf) — для элементарных событий и Рг (Л) — для множества Л, образованного элементарными событиями ,v, ^ t Л. Это различие не принципиально, но делает некоторые фор- мулы наглядными. Определение 1.1.1. Конечное множество Х вместе с заданным на нем распределением вероятностей р (х) называется дискретным вероятностным ансамблем или коротко — дискретным ансамблем (сообщений) и обозначается символом {X, р (х)\. В тех случаях, когда из контекста видно, о каком распределении вероят- *) Здесь и ниже знак ^ используется для обозначения того, что правая и ле- вая части равны по определению. Иногда для упрощения обозначений мы будем ППСЛТЬ РГ (Л) — V р [Xi) ^ § 1.1. ДИСКРЕТНЫЕ АНСАМБЛИ И ИСТОЧНИКИ 13 ностей идет речь или когда точное описание распределения несу- щественно, мы будем обозначать ансамбль через X. Пусть Х =- {;q, .... х^\ и Y = \yi, ..., i/A'i — два конечных множества. Множество, элементы которого представляют собой все возможные упорядоченные пары (х,, у,), А', (: X, у, ^ Y. i — 1, ..., Л''1, j ^ 1, ..., N, называется произведением множеств Х и Y и обозначается через XY. Согласно этому определению XY и YX суть различные множества. Если множества Х и Y совпа- дают, Х == Y, то произведение XY обозначается как X2. Аналогич- ным образом определяются произведения более чем двух мно- жеств Произведение X^Xg ... Х„ представляет собой множество всех последовательностей (л-<11, х12', ..., ^")) длины п таких, что первый элемент л-0' принадлежит множеству Xi, второй х<2' — множеству Xg и т. д., п-и элемент принадлежит множеству Х„*). Если все множества совпадают между собой и с множеством X, то такое произведение обозначается как X". Таким образом, X"— это множество всех последовательностей длины п, образованных из элементов множества X. Пусть XY есть произведение двух конечных множеств Х и У и на множестве XY задано совместное распределение вероятностей р (х, у), которое каждой паре (х;, у,), х, С X, у, С У, сопоста- вляет вероятность р (л';, у,). Очевидно, что соотношения Р1№)Д S Р{х,.У,}, г==1,2,..,М, (1.1.2) -У^У Р2 (У!) и S Р(^,У/), /-1,2,... Л, л-, ^ Л- (1.1.3) задают распределения вероятностей pi (х) и ру, (у) на множествах Х и Y соответственно. Таким образом, при задании ансамбля \XY, р (х, у}} фактически задаются еще два ансамбля {X, р^ {х)\ и \Y, р^ (у)\. Иногда, имея в виду ансамбль {XY, р {х, у)}, мы будем говорить, что совместно заданы два ансамбля Х и Y. Это будет означать, что распределения вероятностей на множествах Х и Y определяются по формулам (1.1.2) и (1.1.3), исходя из рас- пределения вероятностей р (х, у) на множестве XY. Если распределение вероятностей на произведении двух мно- жеств Х и У удовлетворяет условию р(х,, у,} == /?i (х,) рз (У/} Для всех х, ^ X, у, С Y, (1.1.4) <го ансамбли Х и Y называются статистически независимыми. В противном случае говорят, что эти ансамбли статистически зависимы. *) Здесь и в аналогичных обозначениях дальше надстрочный индекс обо- .('•)- эле- значает номер элемента в последовательности, другими словами, х мент, расположенный на i-м месте последовательности. 14 Гл. 1. КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ Пусть задан ансамбль \XY, р (х, у}\, предположим, что х, — такой элемент множества X, для которого р^ (л';) ф 0. Число .,/.. i.-.л P(X^^Уi) (1.1.5) называется условной вероятностью сообщения у, при условии, что сообщение Xi известно (иногда это число называют условной вероят- ностью сооби^ения у/ относительно сообщения л';). Легко увидеть, что множество условных вероятностей относительно фиксирован- ного сообщения А',, которое получается, когда индекс / пробегает все возможные значения, удовлетворяет определению распределе- ния вероятностей (1.1.1). Такое распределение называется услов- ным распределением на множестве Y относительно фиксирован- ного сообщения Х{; заметим, что (1.1.3) определяет так называемое безусловное распределение на Y. Понятно, что аналогичные распре- деления могут быть определены также на множестве X. Таким образом, задание ансамбля {XY, р (х, у)} определяет также услов- ные ансамбли \Х, р (х | у)\, р^(у) ^ 0, и [Y, р (у \ х)\, pi(x) =f= 0. Опишем теперь общее семейство условных ансамблей, которые образуются при совместном задании двух ансамблей. Пусть А — произвольное подмножество элементов из Х такое, что Pfi (A) ^ ^ ? PiW^O, где распределение р^ (х) определено выше. Число ^л ^Ы-4)4р—— У,р(^,у;} (1.1.6) ' = Pri (Л) называется условной вероятностью сообщения у, при условии, что сообщение Х{ принадлежит множеству А {или условной веро- ятностью относительно множества Л). Легко видеть, что множе- ство условных вероятностей относительно фиксированного мно- жества А, которое получается, когда индекс / пробегает все воз- можные значения, снова удовлетворяет определению распределе- ния вероятностей. Такое распределение называется условным распределением на множестве Y относительно фиксированного множества А. Если выбрать А --- X, то р (у, \А) = р^ (у,). Таким образом, условное распределение относительно множества Х — это просто безусловное распределение на Y. Если А состоит из одного элемента, скажем Х{, то р (у,\ А} равно вероятности, определенной в (1.1.5). Аналогичные условные распределения могут быть определены также для множества X. Тем самым определены условные ан- самбли {X, р (х | В)}, В <= у, Рс., (В) ^ 0 и {Y, р (у | А)\, А с=- ^ X, Pfi (Л) ^ 0. Рассмотрим произведение п множеств Xi ... Хл и распределе- ние вероятностей р (х<", ..., А:(")), л-о (: X,, i = 1, ..., п, задаи- § 1.1. ДИСКРЕТНЫЕ АНСАМБЛИ И ИСТОЧНИКИ 15 ное на этом произведении. Другими словами, рассмотрим вероят- ностный ансамбль \Х^ ... Х„, 'р (А-'", ..., х^)\. Пусть ^(A-d))4 S S ... S/?(^1', ...,.^"'), P.W^ S S ... SP^1', .•.,^")), — Х- X. Х„ Рп (xW) Д ? S S.oC^r, .. .,-v4"'). (1.1.7) Соотношения (1.1.7) задают безусловные распределения вероят- ностей на множествах Xi, Х.г, ..., Хп соответственно. Если для любых д-с' 0 х^ •••> ^(") е ^-п имеет место равенство p(xW, ..., xW)=p^(xW) ...p„(xW), (1.1.8) то ансамбли Xi, ..., Х„ называют статистически независимыми. При совместном задании п ансамблей Х^, ..., Х,; оказываются совместно заданными всевозможные совокупности по пг < п ан- самблей. Так, ансамбль (Х^ ... Х,^, р (хС l\ ..., хС т^} опреде- ляется с помощью следующего соотношения, которое дает без- условное распределение вероятностей на произведении множеств p(^'i),...,^'"))4S... ? Р^, ...,^"'), (1.1.9) где суммирование производится по всем множествам Х/^, .... Х^_ таким, что произведение соответствующим образом упорядочен- ных множеств Х^, ..., Х,^, Х^, ..., Х/^ есть множество Xi...X„({ti, ...,;•„,} П {/I. •••> in-m} -=ф, {il,....,i,n} U Ul, •••,jn-m\--= == {1,2, ..., /г}). Другими словами, множество Ху участвует в сум- мировании в (1.1.9), если / не содержится среди чисел t'l, .... im. Вводя по аналогии с (1.1.5) и (1.1.6) условные распределения на множестве X, , .... Х,^, можно получить различные условные ансамбли. Пример 1.1.2.Пусть {A', pi (х)} - ансамбль сообщений из примера 1.1.1, a [Y, p.t (у)} — ансамбль сообщений о результате бросания монеты, Y -= {у^, уч} \4 Рг ('/i) = Ра (ч-^ =~-1^- Элементы множества XY (произведения множеств Х irY) представляют собой пары сообщений (х;, у;), причем первый элемент пары есть сообщение х: о результате бросания кости, а второй элемент г/у есть сооб- щение о результате бросания монеты. В случае независимого бросания кости и монеты все пары имеют одинаковые вероятности: р (х[, у/} == Viz для всех t, /. Можно представить себе более сложный эксперимент с костью и монетой. Предположим, что вначале бросается кость. Если выпало четное число очков, бросается неправильная монета, у которой вероятность выпадения стороны, 16 Гл. 1. КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ соответствующей г/i, равна l/4 (а стороны, соответствующей ) определена вероятность р (л'<'+1), .... х^^) этой последовательности. Верно и обратное, если для любых п и i определены вероятности всех последователь- ностей сообщений длины п, начинающихся с позиции (t'+l). то говорят, что задан источник сообщений. Отсюда следует, что все источники, которые могут иметь совершенно различную физи- ческую природу, задаваемые одним и тем же набором вероятностей последовательностей сообщений, с позиции теории информации отождествляются. Подытожим и уточним сказанное с помощью следующего определения. Определение 1.1.2. Пусть Uy — дискретный источник, выбирающий сообщения из множества X. Будем говорить, что • источник Ux задан, если для любых п =-= 1, 2, ..., любых f =~- 0, ^fcl, ±2, ... задано семейство распределений вероятностей i> (хС+1), ..., л-с+"))}, J^'» е ^ /==<+!, ..., i + п, удовлетворяющих условию согласованности, состоящему в том, что распределение вероятностей р {х^11^, .... х^"1^) для любого набора позиций ;i, .... i„i определено однозначным образом. 3 а м е ч а н и е. Распределение вероятности р (л'С1^, ..., х^1'^) на подпоследовательностях (л-^'^, ..., л-С"'^) может быть получено 18 Гл. 1. КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ с помощью соотношения (1.1.9), причем многими способами. Например, p(xW, xW)== Т p{xW, х^, л<з)), ^i Р(Л-(2>, Х<3))= У р(.<(2), А-*3», Х»4»). ^4 Условие согласованности обеспечивает совпадение всех этих распределений. В определении 1.1.2 легко усмотреть определение случайного процесса дискретного времени, который в каждый момент времени принимает значение из множества X. Таким образом, определение источника и определение случайного процесса, который генери- рует источник, совпадают. Как источник, так и случайный про- цесс, порождаемый источником, задается своими п-мерными рас- пределениями, п == 1, 2, ... Всякое п-мерное распределение ве- роятностей в общем случае является функцией 2п переменных, р (^'^, .... х('^; <'i, ..., in). В случае дискретных источников н дискретных случайных процессов значение этой функции есть вероятность того, что в фиксированные моменты времени ii, ..., 1,1 источник породит сообщения (или процесс примет значения) д-('1), ..., д'('") соответственно. В общем случае вероятность некоторого отрезка сообщений зависит как от самого отрезка, так и от его расположения на оси времени. Имеется, однако, важный класс источников, облада- ющих однородностью во времени или стационарностью. Свойство стационарности состоит в том, что для любого целого числа j вероятности двух одинаковых последовательностей, одна из кото- рых занимает временные позиции г,. ..., in, а другая —временные позиции t\ + /', ..-, in + /> равны. Другими словами, ^+/), ...,х^''^ i,-\-j, ..., <„+/)= ^p(xw....,xw; i„ / t i \ / , \ \ ^ -рС^,...,.^"' при (v^'i4^), . . ., д-^"47)) — (х(11), ..., л-('")). Всюду в этой книге мы используем сокращенную форму записи р (х^'4'1*, ..., х^'^'") вмес-ю р (л•<'+i), ..., ;^•^t+'"; t + 1, ..., t + п). Определение 1.1.3. Дискретный источник U^ назы- вается стационарным, если сообщения на его выходе образуют стационарный случайный процесс. В случае стационарных источников распределение вероят- ностей не зависит от сдвига по оси времени. Все последователь- ности, отличающиеся только положением на оси времени, имеют одинаковые вероятности. Поэтому их положение на оси времени можно не оговаривать. § 1.2. СЛУЧАЙНЫЕ ВЕЛИЧИНЫ. ЗАКОН БОЛЬШИХ ЧИСЕЛ 19 Определение 1.1.4. Дискретный источник называется источником без памяти, если для любых п = 1, 2, .... любых t = 0, ±1, ±2, ... и любых последовательностей (xW), ..., ^d+n)^ ^(/) ^ ^ имеет место равенство ^(xC+i», ...,х('+">)== П^,.(хС+/'). (1.1.11) /• -1 В общем случае .распределение вероятностей для сообщений на выходе источника в момент времени г зависит от /. Эта зависи- мость показана с помощью нижнего индекса у сомножителей в правой части соотношения (1.1.11). Однако в случае стационар- ных источников, как это следует из (1.1.10), все одномерные рас- пределения (п == 1) одинаковы для гсех моментов времени. По- этому для стационарных источников (5ез памяти п р (л-С-1), . . ., А-('+">) ---= П р (Д-С+/)), (1.1.12) /=!' где через р (^обозначено общее для всех моментов времени одно- мерное распределение. Всюду в этой книге мы будем рассматривать только стаци- онарные источники. Поэтому вместо длинного сочетания слов «стационарный источник без памяти» будет употребляться более короткое выражение «источник без памяти». В этом случае ста- ционарность будет подразумеваться. В случае стационарных источников с памятью, для которых соотношение (1.1.12) не вы- полняется, мы будем использовать термин «стационарный источ- ник». Заметим, что стационарные источники без памяти иногда называются постоянными. Пример 1.1.4. Пусть А' п Y — ансамбли примера 1.1..2. Рассмотрим источ- ник, выбирающий сообщения в четные моменты времени из множества X, а в не- четные — из У. Такой источник, очевидно, нестационарен. Пусть теперь источ- ник выбирает сообщения из ансамбля Y примера 1.1.3. Если распределение вероятностей будет такое, как в п. б), то источник будет стационарным, но с па- мятью. Если же распределение вероятностей такое, как в п, а), то источник будет источником без памяти. § 1.2. Случайные величины. Закон больших чисел Предположим, что {X, р (х)\ -- дискретный ансамбль п (р (х) — функция, определенная на Х = [х^, ..., х^\ и принимающая значения на числовой оси. Элементы множества Х могут иметь произвольную природу, однако (р (л-i), ..., ср (х^) —числа. Всякая действительная функция fp (,r), заданная на произвольном дискрет- ном ансамбле, порождает действительную дискретную случай- ную величину (или коротко -- дискретную случайную величину).