Б. Д. Кудряшов - Основы теории кодирования. Учебное пособие

посвященный проблеме достижения пределов скорости
передачи информации, предугаданных Клодом Шенноном. В связи с тем, что научное сообщество готовится отметить в 2016 году
столетний юбилей Шеннона, в 2013 году от лица ученых и инженеров, работающих в области теории информации и ее приложений,
президент IEEE M. S. Coleman, президент Bell Labs G. Rittenhouse
и президент MIT R. Reif выступили с инициативой выпустить в
США почтовую марку, посвященную этому юбилею. В их обращении к руководству Почтовой службы США говорится о значении
теории Шеннона для нашего времени:

We are writing to propose a stamp to honor the centenary
of Clode Elwood Shannon, father of the information
age.
Information systems like smart phones, MP3 players and
World Wide Web are changing our lives. They store
our memories, connect our communities, and carry out
entertainment. They facilitate healthcare delivery and
provide the backbone upon our financial, industrial and
governmental institutions are built.
Much as Newton discovered the laws of gravity
and motion, Shannon discovered the laws of
information. By uncovering the simple laws at the heart of

such overwhelmingly complex problems as communication,
computing, memory and cryptography, Shannon unlocked
the door that led us to the information age.

2

Предисловие

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

Рис. 1. Клод Шеннон

По мере появления новых задач и новых технологий для решения этих задач содержание теории кодирования быстро изменялось,
особенно в последние 20 лет. С другой стороны, время, отводимое
на изучение предмета, все время уменьшается, поскольку появляются на свет новые важные объекты для освоения студентами информационных специальностей. В результате относительно недавно
изданные и переизданные классические монографии и учебники по
теории кодирования объемом свыше 1000 страниц (см., например,
[26]), тяжелы для студентов и аспирантов (в том числе и в буквальном смысле) и при этом не успевают отражать важные обновления
в теории и практике кодирования.

Предисловие

3

Поэтому задача данной книги — сконцентрировать фундаментальные практические важные результаты современной теории кодирования в объеме семестрового курса. При этом предполагается,
что большая часть прикладных вопросов изучается на практических занятиях, при выполнении лабораторных работ и самостоятельно при подготовке проектов. Поэтому в учебник включены задачи, решение которых требует использования компьютера, а также примеры программ, которые будут полезны при решении этих
задач и при реализации алгоритмов кодирования и декодирования.
Особенность теории кодирования — разнообразие используемых
математических методов. «Классические» методы кодирования основывались на дискретной математике, на теории конечных полей.
Параллельно развивались вероятностные методы. В 1990-е годы
произошла «турбо-революция», после которой выросло значение алгоритмических методов анализа графов. Соответственно, предполагается, что читатель умеет программировать, знаком с основами
теории вероятности, комбинаторики и линейной алгебры, знает терминологию теории графов, а также фундаментальные понятия высшей алгебры. Хотя почти все используемые термины дополнительно поясняются, этих напоминаний может оказаться недостаточно и
тогда придется воспользоваться учебниками по соответствующим
разделам математики.
Одна из трудностей при отборе материала — избежать перекоса
в сторону тематики, которая наиболее близка и интересна автору.
В полной мере избежать такого перекоса не удалось. Представлению кодов решетчатыми диаграммами, теории сверточных кодов
и некоторым другим вопросам уделено, возможно, несколько больше внимания, чем следовало. С другой стороны, некоторые важные
вопросы теории и практики кодирования не попали в учебник. Обзор литературы, по которой можно восполнить пробелы, приведен
в параграфе 1.2.
Автору учебника посчастливилось учиться теории информации
и кодированию у В. Д. Колесника, Г. Ш. Полтырева, Е. Т. Мирончикова. Пониманию предмета помогли практическая работа с Г. Тененгольцем в США, с компанией Samsung, совместные научные исследования с Р. Йоханнессоном и его аспирантами в университете
г. Лунд (Швеция), сотрудничество с В. Сидоренко и М. Боссертом

4

Предисловие

в университете г. Ульм --">