ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

Предлагаемая вниманию читателя книга Галлагера является уже третьей в серии переведенных на русский язык небольших монографий по теории кодирования. Первая из этих монографий — книга Возенкрафта и Рейффена «Последовательное декодирование», вышедшая в русском переводе два года назад, хорошо известна читателям-специалистам. Вторая — книга Месси «Пороговое декодирование» — недавно издана в русском переводе. Объединяет эти три книги многое. Все они написаны молодыми учеными, принадлежащими к ведущей в США научной школе в области теории информации — школе, работающей в Массачусетском технологическом институте, и все они представляют собой изложение оригинальных исследований их авторов, предложивших различные подходы к решению важнейшей проблемы техники связи: проблемы построения практически осуществимых методов кодирования и декодирования, позволяющих вести надежную передачу информации по реальным каналам связи со скоростью, приближающейся к теоретической границе — пропускной способности канала. Чтобы полностью исчерпать список основных идей в этой проблематике, нужно добавить к темам этих трех перечисленных книг, пожалуй, лишь широко известный метод циклических кодов, хорошо изложенный в книге Питерсона «Коды, исправляющие ошибки». Кроме того, стоит специально отметить небольшую, но важную статью нашего соотечественника М. Пинскера, опубликованную в журнале «Проблемы передачи информации» (№ 1 за 1965 г.), которая развеивает предрассудок (разделяемый, по-видимому, специалистами Массачусетской школы теории информации), состоящий в том, что возможность передачи информации со сколь угодно малой вероятностью ошибки и без чрезмерно большой по объему вычислительной работы при декодировании всегда ограничена

некоторой скоростью, меньшей пропускной способности канала.

Метод Галлагера основан на простой, но остроумной математической идее. Он рассматривает групповой код, проверочная матрица которого в основном состоит из нулей и содержит лишь небольшое число единиц. Простота структуры проверочной матрицы создает возможность предложить простые алгоритмы декодирования. Желание доказать, что введенный алгоритм декодирования дает ошибку лишь с малой вероятностью, приводит автора к необходимости провести сложные математические построения как комбинаторного, так и аналитического характера. Один из введенных при этом методов — оценка вероятности ошибки декодирования через структуру кодовых расстояний — интересен для теории кодирования и вне рамок основной темы книги. Тем не менее автору не удается создать достаточно полную теорию кодов с малой плотностью проверок на четность; то, что им получено, — это скорее фрагменты такой теории. Конечно, установленные в книге теоретические результаты и приведенные в ней результаты моделирования на вычислительных машинах создают должную эмпирическую уверенность в пригодности алгоритмов декодирования; однако, вступая в противоречие с замечанием, мельком сделанным автором в книге, автор предисловия думает, что дальнейшие теоретические исследования вопроса были бы плодотворными как с математической, так и с инженерной точки зрения.

Книга написана четко и ясно, но сжато. Предполагается предварительное знакомство с элементами теории групповых кодов (например, достаточно ознакомления с первыми главами упомянутой выше книги Питерсона). Кое-где используются также элементы общей теории информации (с которыми можно ознакомиться, например, по книге Фано «Передача информации»). Книга Галлагера доступна и интересна быстро растущему кругу инженеров и математиков, работающих в области теории кодирования и ее приложений.

Р. Л. Добрушин

ПРЕДИСЛОВИЕ АВТОРА

Теорема кодирования для канала с шумами, уста новленная К. Э. Шенноном в 1948 г., показала инженерам-связистам возможность получения сколь угодно малых частот ошибок без потерь в скорости передачи информации. Главными препятствиями в практическом использовании этой теоремы были сложность оборудования и большое время вычислений, требуемых для декодирования принятой при наличии шума информации.

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

Главы монографии построены так, что каждую можно читать независимо (за исключением гл. 5). В гл. 1 обсуждается общее состояние предмета, суммируются результаты и кратко сравнивается кодирование с малой плотностью проверок на четность с другими методами кодирования. В гл. 2 исследуются расстояния между кодовыми словами в кодах с малой плотностью проверок, а в гл. 3 эти результаты используются при оценке вероятности ошибки декодирования, которой можно достичь для таких кодов в широком классе каналов с двоичным входом. Результаты гл. 3 можно применить непосредственно к любому коду или классу кодов, для которых можно найти оценку свойств расстояния. В гл. 4 приводится про стой алгоритм декодирования в кодах с малой плот ностью проверок и для него исследуется вероятность

ошибки декодирования. В гл. 5 предыдущие результаты кратко обобщаются на недвоичные каналы, а в гл. 6 приводятся результаты моделирования алгоритма декодирования с малой плотностью проверок на четность на вычислительной машине.

Эта книга представляет собой расширенный и пересмотренный вариант моей докторской диссертации, законченной в 1960 г. в Электротехническом отделе МТИ. Я признателен моему руководителю, проф. Питеру Элайесу, и моим оппонентам, проф. Роберту М. Фано и Джону М. Возенкрафту, за помощь и ободрение как во время подготовки диссертации, так и после этого.

Это исследование стало возможным отчасти благодаря поддержке, оказанной Исследовательской лабораторией электроники Массачусетского технологического института, которая частично поддерживается армией США, Отделом научных исследований военно-воздушных сил и Отделом военно-морских исследований; дополнительная поддержка была получена от Национального научного фонда и от Национального института здоровья.

Большая часть гл. 4 перепечатана с разрешения редакторов из статьи автора в Transactions of the

Экспериментальные результаты гл. 6 были получены частично при поддержке Авиационного исследовательского центра в Риме и Вычислительного центра МТИ.

Роберт Дж. Галлагер

Кембридж, Массачусетс Июль 1963 г.