Автор переведенной на иностранный язык книги чувствует себя как отец, сын которого покидает дом, чтобы начать собственную жизнь: к чувству гордости примешивается сознание, что книга начинает новую жизнь, которую ты никогда не узнаешь. Русское издание готовилось специалистами высокого класса: редактором Камилем Зигангировым и переводчиками Инной Гру-шко и Владимиром Блиновским. Я очень благодарен им за большую работу по переводу книги «Теория и практика кодов, контролирующих ошибки» на русский язык.

Используя возможность, предоставленную мне издательством «Мир», я обращаюсь к советскому читателю. Он несомненно заметит, что книга адресована как инженерам, так и математикам, работающим в области приложений, и что в ней декодерам и алгоритмам декодирования уделяется гораздо больше внимания, чем в других книгах. Это связано отчасти с моими научными интересами и отчасти с широким распространением декодеров, исправляющих ошибки, за последнее десятилетие. Найти хороший алгоритм декодирования сейчас так же важно, как и найти хороший код. Читатель обнаружит также, что в книге недостаточно отражен крупный вклад советских исследователей в эту область. Частично это объясняется моей неосведомленностью, частично тем, что во многих советских работах принят более высокий уровень математической строгости, чем принятый в данной книге, и, наконец, тем, что советские исследователи не столь интенсивно работают в области алгоритмов декодирования, которая интересует меня больше всего.

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

Р. Э. Блейхут

одни лишь СЛОВА - это ничто

- девиз Королевского общества

ПРЕДИСЛОВИЕ

В настоящее время невозможно представить себе инженера-конструктора цифровых систем, который бы не был знаком с кодами, контролирующими ошибки. Сегодняшний интерес к этому предмету резко контрастирует с тем, что в прежние годы такие коды считались практически применимыми лишь в самых дорогих системах связи. Необходимость в контроле ошибок сейчас так велика, а возможности электроники столь развиты, что интерес к этой тематике непрерывно растет. Умение применять кодирование стало важным для любого специалиста, создающего современные системы связи или большие цифровые системы, и это умение ценится все больше. По этой теме написаны превосходные книги, но в них основное внимание уделяется математическим исследовательским аспектам. Традиционно превалируют вопросы, связанные с построением лучших кодов. Хотя эти вопросы важны для дальнейшего развития теории, конструктору в принципе интересно лишь то, что он может построить.

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

Книга возникла из конспекта курса лекций, посвященного контролирующим ошибки кодам, который автор много раз читал как в Корнеллском университете, так и в корпорации ИБМ. От слушателей этих лекций нельзя было ожидать какой-либо подготовки по современной алгебре. Поэтому одно из требований к курсу состояло в изложении необходимых основ алгебры, которое обеспечило бы достаточную математическую строгость, и в то же время умещалось в считанное число лекционных часов. Учитывая это ограничение, я попытался включить в книгу все те основы алгебры, которые требуются для введения в теорию контролирую-

ПРЕДИСЛОВИЕ 9

щих ошибки кодов И позволяют проводить доказательства или убедительную аргументацию. Это тот минимум, без которого инженер не может быть уверен в своих построениях.

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

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

Я пытался выдвинуть на первый план преобразование Фурье в конечных полях, так как оно интуитивно понятнее инженерам и быстро усваивается людьми с техническим образованием. Применение преобразования Фурье проясняет также тот факт, что теория контролирующих ошибки кодов является одной из ветвей теории дискретной обработки сигналов. Хотя для студентов инженерных специальностей предпочтительнее другой способ изложения того же круга идей, который основан на использовании многочленов Мэттсона-Соломона, такое изложение вызвало бы необходимость изучать новый для них язык в то время, как они уже владеют одним, столь же употребительным.

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

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