Вероятность и статистика в примерах и задачах. Том III. Теория информации и кодирования

ВЕРОЯТНОСТЬ
и СТАТИСТИКА
в примерах
и задачах

М. Я. КЕЛЬБЕРТ
Ю. М. СУХОВ

М. Я. КЕЛЬБЕРТ
Ю. М. СУХОВ

ТЕОРИЯ ИНФОРМАЦИИ
И КОДИРОВАНИЯ

Вероятность и статистика 
в примерах и задачах

ISBN 978-5-4439-0154-1

9 785443 901541 >
3

Сведения из теории
вероятностей 
и математической статистики 
становятся все более 
необходимыми в социологии, 
менеджменте, финансовой 
математике и во многих 
других отраслях знаний.

В книге собрано большое 
количество задач, 
снабженных полными 
решениями. Необходимые 
теоретические сведения 
приводятся по ходу 
изложения.

М. Я. Кельберт, Ю. М. Сухов

Вероятность и статистика
в примерах и задачах

Том 3

Теория информации и кодирования

Электронное издание

Москва
Издательство МЦНМО
2016

УДК 519.21
ББК 22.171
К34

Кельберт М. Я., Сухов Ю. М.
Вероятность и статистика в примерах и задачах
Т. 3: Теория информации и кодирования
Электронное издание
М.: МЦНМО, 2016
567 с.
ISBN 978-5-4439-2377-2

Для освоения таких разделов прикладной математики, как теория вероятностей, математическая статистика, теория информации и кодирование,
тренировка в решении задач и выработка интуиции важны не меньше, чем
изучение доказательств теорем; большое разнообразие задач по этому предмету затрудняет студентам переход от лекций к экзаменационным задачам,
а от них — к практике.
Этот том включает стандартный пакет информационно-теоретического
материала, обычно читаемого на факультетах информатики и электроники, а
также прикладной математики ведущих университетов. При этом излагаются как вероятностные, так и алгебраические аспекты теории информации и
кодирования, включая как основы теории, так и некоторые ее современные
аспекты. Предмет этой книги критически важен для современных приложений (телекоммуникации, обработка сигналов, информатика, криптография).
Авторы собрали большое количество упражнений, снабженных полными решениями. Эти решения адаптированы к нуждам и умениям учащихся.
Необходимые теоретические сведения приводятся по ходу изложения; кроме
того, текст снабжен историческими отступлениями.

Подготовлено на основе книги:
Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах
и задачах. Т. 3: Теория информации и кодирования. — М.: МЦНМО,
2014. — ISBN 978-5-4439-0154-1.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)-241-08-04
http://www.mccme.ru

ISBN 978-5-4439-2377-2
© Кельберт М. Я., Сухов Ю. М., 2014
© МЦНМО, 2016

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Гл а в а 1. Основные понятия теории информации . . . . . . . . . . . . .
11

§ 1.1. Основные понятия. Неравенство Крафта. Кодирование Хаффмана
12
§ 1.2. Понятие энтропии . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
§ 1.3. Первая теорема Шеннона о кодировании. Энтропийная скорость
марковского источника . . . . . . . . . . . . . . . . . . . . . . . . .
54
§ 1.4. Каналы передачи информации. Правила декодирования. Вторая
теорема Шеннона о кодировании
. . . . . . . . . . . . . . . . . . .
72
§ 1.5. Дифференциальная энтропия и её свойства . . . . . . . . . . . . . .
102
§ 1.6. Дополнительные задачи к главе 1 . . . . . . . . . . . . . . . . . . .
127

Гл а в а 2. Введение в теорию кодирования . . . . . . . . . . . . . . . . .
176

§ 2.1. Пространства Хэмминга. Геометрия кодов. Основные ограничения
на размер кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
176
§ 2.2. Геометрическое доказательство второй теоремы Шеннона о кодировании. Тонкие границы на размер кода
. . . . . . . . . . . . . . . .
196
§ 2.3. Линейные коды: основные конструкции . . . . . . . . . . . . . . . .
218
§ 2.4. Коды Хэмминга, Голея и Рида—Маллера . . . . . . . . . . . . . . .
234
§ 2.5. Циклические коды и алгебра многочленов. Введение в БЧХ-коды .
251
§ 2.6. Дополнительные задачи к главе 2 . . . . . . . . . . . . . . . . . . .
282

Гл а в а 3. Дальнейшие темы из теории кодирования . . . . . . . . . . .
310

§ 3.1. Сведения по теории конечных полей . . . . . . . . . . . . . . . . . .
310
§ 3.2. Коды Рида—Соломона. Развитие теории БЧХ-кодов . . . . . . . .
334
§ 3.3. Развитие теории циклических кодов. Декодирование БЧХ-кодов
.
345
§ 3.4. Тождество Мак-Вильямс. Граница линейного программирования
.
358
§ 3.5. Асимптотически хорошие коды . . . . . . . . . . . . . . . . . . . . .
373
§ 3.6. Дополнительные задачи к главе 3 . . . . . . . . . . . . . . . . . . .
386

Гл а в а 4. Дальнейшие темы из теории информации
. . . . . . . . . . .
413

§ 4.1. Гауссовский канал и его обобщения . . . . . . . . . . . . . . . . . .
414

Оглавление

§ 4.2. А. с. р. в условиях непрерывного времени . . . . . . . . . . . . . . .
444
§ 4.3. Формула Найквиста—Шеннона . . . . . . . . . . . . . . . . . . . .
456
§ 4.4. Пространственные точечные процессы и сетевая теория информации 483
§ 4.5. Избранные примеры и задачи криптографии . . . . . . . . . . . . .
500
§ 4.6. Дополнительные задачи к главе 4 . . . . . . . . . . . . . . . . . . .
531

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
553

Список сокращений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
562

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
564

Предисловие

Эта книга частично основывается на нескольких математических курсах Кембриджа: теория информации для 3-го года обучения (который
читался, постоянно развиваясь, на протяжении последних четырех десятилетий под разными названиями), кодирование и криптография (более молодой и упрощ ¨енный курс, исключающий сложные технические вопросы)
и более сложные курсы из части III (представляющей собой кембриджский
эквивалент математической магистратуры). Содержание книги построено,
по существу, вокруг следующих понятий:
а) энтропия распределения вероятностей как мера «недостоверности»
и энтропия на случайный символ как мера «изменчивости» типичных траекторий случайного процесса,
б) кодирование как средство для измерения и использования избыточности информации, генерируемой процессом.
Таким образом, содержание данной книги включает более или менее
стандартный пакет информационно-теоретического материала, который
можно найти в наше время в учебных курсах по всему миру, в основном читаемых на факультетах информатики и электроники и иногда теории вероятностей и математической статистики. Что отличает эту книгу от остальных, так это, прежде всего, широкий спектр примеров (отличительная черта
всей нашей серии учебников «Вероятность и статистика, в примерах», опубликованной в издательстве Кембриджского университета).
Большинство из этих примеров соответствуют уровню, принятому на экзаменах математических курсов в Кембридже. Таким образом, наши читатели
могут сами понять, какого уровня они достигли или собираются достичь.
Второе отличие этой книги от большинства других книг по теории
информации или теории кодирования заключается в том, что она охватывает оба возможных направления: вероятностное и алгебраическое. Как
правило, эти направления исследований представлены в разных монографиях, учебниках и курсах, зачастую написанных людьми, работающими
на разных факультетах. Подготовке этой книги способствовало то, что её
авторы имели давние связи с Институтом проблем передачи информации
Российской академии наук (ИППИ), в котором традиционно изучается
широкий спектр проблем. Достаточно упомянуть, среди прочих, такие
имена, как Роланд Добрушин, Рафаил Хасьминский, Марк Пинскер, Владимир Блиновский, Вячеслав Прелов, Борис Цыбаков, Камиль Зигангиров
(теория вероятностей и математическая статистика), Валентин Афанасьев,

Предисловие

Сергей Гельфанд, Валерий Гоппа, Инна Грушко, Григорий Кабатянский,
Григорий Маргулис, Юрий Сагалович, Алексей Скоробогатов, Михаил
Цфасман, Леонид Бассалыго, Виктор Зиновьев, Виктор Зяблов (алгебра,
комбинаторика, геометрия и теория чисел), которые работали или продолжают работать в ИППИ (было время, когда все они размещались в пяти
комнатах в центре Москвы). Традиции преподавания математических тем
в теории информации и кодирования в Кембридже восходят первоначально
к Питеру Уиттлу (теория вероятностей и оптимизация) и позднее к Чарльзу
Голди (теория вероятностей), Ричарду Пинчу (алгебра и геометрия), Тому
К ¨ернеру и Кейту Карну (анализ) и Тому Фишеру (теория чисел).
Мы также хотели бы добавить, что книга написана авторами, имеющими математическое образование (и остающимися до сих пор математиками),
которые, тем не менее, имеют сильную тягу к приложениям, невзирая на
все сопутствующие проблемы, возникающие в процессе прикладной работы: неопредел ¨енность, неточность, дискуссионность (включая, разумеется,
личностный фактор) и последнее, но отнюдь не менее важное — необходимость эффективно применять на практике математические идеи. Авторы
твердо считают, что математизация является основным пут ¨ем к выживанию
и совершенствованию в современном конкурентном мире и, следовательно,
математику необходимо воспринимать всерь ¨ез и изучать добросовестно.
Обе вышеупомянутые концепции (энтропия и коды), формирующие
основу информационно-теоретического подхода к случайным процессам,
были введены Шенноном в 1940-х гг., в довольно заверш ¨енной форме
в публикациях [S, SW]. Конечно, понятие энтропии уже существовало
в термодинамике, и его очень хорошо осознавали Больцман и Гиббс на
стыке XIX и XX столетий. Коды также эффективно применялись на практике со времен античного мира. Но именно Шеннон полностью оценил
роль этих понятий и положил их в основу современного информационнотеоретического подхода к случайным процессам. Не будучи профессиональным математиком, он не всегда давал полные доказательства своих
конструкций. (Может быть, он и не задумывался о них.) В соответствующих разделах мы прокомментируем некоторые довольно деликатные
моменты в отношениях Шеннона с математическим сообществом. К счастью, похоже, это его сильно не тревожило. (В отличие от Больцмана,
который был особенно чувствителен к внешним отзывам и принимал их,
пожалуй, слишком близко к сердцу.) Шеннон, несомненно, понимал всю
ценность своих открытий, и, по нашему мнению, они ставят его в один ряд
с такими выдающимися математиками, как Винер и фон Нейман.
Будет справедливо отметить, что имя Шеннона по-прежнему доминирует как в вероятностном, так и в алгебраическом направлениях в современной теории информации и кодирования. Это довольно необычно, учитывая,

Предисловие
7

что мы говорим о вкладе человека, который работал в этой области более чем 40 лет назад. (Хотя в отношении нескольких сложных вопросов
Шеннон, вероятно, мог бы повторить слова Эйнштейна, переформулировав
их так: «С тех пор как математики вторглись в теорию связи, я перестал
что-либо понимать в ней».)
За годы, что прошли после работ Шеннона, в математике и электротехнике произошли большие изменения, не говоря уже о компьютерных
науках. Кто бы мог предвидеть в 1940–1950-х гг., что соперничество между
подходами Шеннона в теории информации и Винера в кибернетике получит
такое завершение? Действительно, кибернетика обещала огромные (даже
фантастические) выгоды для всего человечества, в то время как теория информации только утверждала, что в определенных пределах можно достичь
скромной цели исправления ошибок при передаче.
Книга Винера [W] в 1950–1960-х гг. пленила умы мыслителей практически во всех областях интеллектуальной деятельности. В частности,
кибернетика стала серьезной политической проблемой в Советском Союзе и его странах-сателлитах: сначала она была объявлена «буржуазной
антинаучной теорией», а затем ей придали неоправданно большое значение. (Цитата из критического обзора кибернетики в ведущем в советской
идеологии журнале «Вопросы философии» 1953 г. гласит: «Империалистам не уда ¨ется разрешить противоречия умирающего капиталистического
общества. Они не могут предотвратить неизбежный экономический кризис. И поэтому они пытаются найти решение не только в бешеной гонке
вооружений, но и в идеологической войне. В глубоком отчаянии они
прибегают к помощи псевдонауки, которая да ¨ет им некоторые проблески надежды продлить их существование». Советский «Краткий словарь
по философии» (1954 г.), имевший тираж в сотни тысяч экземпляров,
определял кибернетику как «реакционную псевдонауку, которая появилась
в США после первой мировой войны и позднее распространилась в других капиталистических странах: вид современного механицизма». Однако
под давлением ведущих советских физиков, завоевавших авторитет после
успехов советской ядерной программы, тот же самый журнал «Вопросы
философии» в 1955 г. опубликовал позитивный отзыв о кибернетике.
Среди авторов этой статьи были Алексей Ляпунов и Сергей Соболев,
выдающиеся советские математики.)
Любопытно, что в недавно опубликованной биографии Винера [CS] указывается, что существуют «тайные правительственные документы (США),
которые показывают, как ФБР и ЦРУ следили за Винером в разгар холодной войны, чтобы помешать его социальной активности и растущему влиянию кибернетики в стране и за рубежом». Интересные сравнения можно
найти в работе [Hei].

Предисловие

Однако история пошла своим пут ¨ем. Фримен Дайсон написал в сво ¨ем
обзоре [Dy]: «(Теория Шеннона) была математически элегантной, понятной и легко применимой на практике к проблемам связи. Она была намного
более удобной для пользователя, чем кибернетика. Теория стала основой
новой дисциплины под названием ”теория информации...“(В настоящее
время) в базовый курс подготовки инженеров по электронике входит теория информации, основанная на теории Шеннона, а кибернетика оказалась
забытой».
Однако это не совсем так: только на территории бывшего Советского
Союза до сих пор работают институты и отделы, в название которых входит
слово «кибернетика»: два в Москве, два в Минске, и по одному в Таллине,
Тбилиси, Ташкенте и Киеве (последний являлся известнейшим центром
компьютерной науки в целом в бывшем СССР). И в Великобритании
существуют по крайней мере четыре факультета, в университетах Болтона,
Брэдфорда, Халла и Рединга, не считая различных ассоциаций и обществ.
Во вс ¨ем мире общества, связанные с кибернетикой, кажется, процветают,
что видно из перечисления названий: от Института метода (Швейцария)
или Академии кибернетики (Италия) до аргентинской Ассоциации общей
теории систем и кибернетики, Буэнос-Айрес. И мы были рады узнать
о существовании Кембриджского кибернетического общества (Бельмонт,
Калифорния, США). Напротив, теория информации фигурирует в названиях лишь нескольких организаций. Видимо, давний спор между Шенноном
и Винером еще не вполне закончен.
В любом случае репутация Винера в области математики оста ¨ется несокрушимой. Достаточно назвать несколько жемчужин его творчества, таких
как теорема Пэли—Винера (которая была доказана во время многочисленных посещений Винером Кембриджа), метод Винера—Хопфа и, конечно,
особенно близкий нашему сердцу винеровский процесс, чтобы понять его
истинную роль в научных исследованиях и приложениях.
Существующие воспоминания об этом гиганте науки изображают Винера сложной и противоречивой личностью. (Название биографии [CS]
в этом смысле весьма показательно, хотя такие взгляды оспариваются;
см., например, обзор [Mar]. В этой книге мы пытаемся принять более
мягкий тон, как, например, в главе о Винере в книге [Ja], с. 386–391.)
С другой стороны, имеющиеся документальные записи о жизни Шеннона
(так же как и других отцов теории информации и кодирования, в частности
Ричарда Хэмминга) дают целостную картину спокойного, умного человека,
не лиш ¨енного чувства юмора. Мы надеемся, что такое впечатление не будет
мешать написанию биографии Шеннона и что в будущем мы увидим столь
же много книг о Шенноне, сколько их написано о Винере.

Предисловие
9

Как было сказано ранее, цель этой книги двояка: обеспечить синтетическое введение в вероятностные и алгебраические аспекты теории,
поддерживаемое значительным количеством задач и примеров, и обсудить
ряд вопросов, редко представленных в большинстве книг. Главы 1–3 дают
введение в основы теории информации и кодирования и обсуждают некоторые современные ответвления этих тем. Мы концентрируемся в этих главах
на типичных задачах и примерах (многие из которых возникли в кембриджских курсах) больше, чем на подробном изложении теории, стоящей за
ними. Глава 4 да ¨ет краткое введение в более специализированные разделы
теории информации. Здесь изложение более сжато и некоторые важные
результаты приводятся без доказательств.
В связи с тем, что большая часть текста основана на конспектах лекций
и решений различных задач для аудиторных занятий и экзаменов, в книге
встречаются неизбежные повторы, многие обозначения и примеры даются
на упрощ ¨енном языке. Часто мы делали это сознательно, чтобы передать
живую атмосферу процесса преподавания и изучения.
Три прекрасные книги [GP], [M] и [CT] оказали особенно сильное
влияние на наш учебник. Здесь сыграла свою роль наша долгая дружба
с Чарльзом Голди, так же как и знакомство с Томом Ковером. Кроме того,
на наш текст оказали влияние такие книги, как [Bl, MWS, R1] и [vL] (мы
даже кое-что заимствовали из них). Мы благодарим за гостеприимство
Институт Исаака Ньютона Университета Кембриджа (2002–2010 гг.), особенно программу стохастических процессов в коммуникационных науках
(январь–июль 2010 г.). Различные части книги обсуждались со многими
коллегами из разных учреждений, в первую очередь из Института проблем
передачи информации и Института математической геофизики и прогноза
землетрясений, Москва. В частности, мы признательны за интерес к книге,
проявленный Г. Кабатянским и С. Пироговым, и за замечания, которые
возникли в результате последовавших обсуждений. Мы также хотели бы
поблагодарить Джеймса Лоуренса (статистическая лаборатория Университета Кембриджа) за его помощь с рисунками.
В ходе заключительного этапа работы над книгой значительную роль
сыграла поддержка агентства FAPESP (штат Сан-Пауло, Бразилия),
в рамках грантов 2010/17835-0, 2011.20133-0 и 2012.04372-7, а также
Ректории Университета Сан-Пауло в рамках гранта 2011.5.764.45.0. Перевод книги на русский язык и техническая сторона её подготовки к печати
были выполнены при поддержке РФФИ. Работа переводчика С. Кулешова
и редактора О. Широковой заслуживает самой высокой оценки и глубокой
благодарности.
Ссылки на том 1 и том 2 относятся к переводам наших книг «Вероятность и статистика в примерах», том 1 и 2 (Probability and Statistics

Предисловие

by Example, Cambridge University Press); страницы даются по русскому
изданию. Мы используем стиль этих книг, подавая б ´ольшую часть материала как «примеры с решениями». Много материала дается в виде
задач, взятых из экзаменационных работ (Cambridge Tripos Exam papers),
которые сохраняют свой оригинальный стиль.
На протяжении всей книги мы старались развлечь читателя. Когда нашей собственной фантазии не хватало, мы привлекали идеи других авторов,
в основном из различных интернет-источников. (К счастью, поток юмора
кажется неиссякаемым, и иногда в интернете появляются блестящие высказывания.)
Символ □ указывает на конец отдельной части книги, чтобы отделить е ¨е
от последующего текста: это относится к примерам, задачам (решениям),
определениям, замечаниям и доказательствам.

Глава 1

Основные понятия теории информации

На протяжении всей книги символ P обозначает различные распределения вероятностей. В частности, в гл. 1 этот символ преимущественно
обозначает распределение вероятностей последовательности случайных
величин (с. в.), характеризующей источники информации. Как правило,
это будут последовательности независимых одинаково распределенных
случайных величин (н. о. р. с. в.) или цепи Маркова с дискретным временем (ц. м. д. в.); P(U1 = u1, . . . , Un = un) — совместная вероятность
события, при котором с. в. U1, . . . , Un принимают значения u1, . . . , un,
а P(V = v|U = u, W = w) — условная вероятность, т. е. вероятность
того, что с. в. V принимает значение v, при условии, что с. в. U и W
равны u и w соответственно. Символ E закрепл ¨ен за математическим
ожиданием с. в. с распределением P.
Символы p и P используются для обозначения различных вероятностей
(и связанных с ними объектов, таких как переходная функция ц. м. д. в.).
Символ #A обозначает мощность конечного множества A. Символом 1
обозначается индикаторная (характеристическая) функция множества.
Для логарифмов будем использовать следующие обозначения и правила
действия: log = log2 и ∀ b > 1: 0 · logb 0 = 0 · logb ∞ = 0. Далее, при x > 0
через ⌊x⌋ и ⌈x⌉ мы обозначим максимальное целое число, не превосходящее x, и минимальное целое число, не меньшее x, соответственно. Таким
образом, ⌊x⌋ ⩽ x ⩽ ⌈x⌉; неравенство превращается в равенство при целых x
(⌊x⌋ называется целой частью числа x).
Аббревиатуры л. ч. и п. ч. обозначают соответственно левую и правую
части уравнения или неравенства.