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

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

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

Профессор Тоби Бергер был моим другом и консультантом на протяжении всех лет работы над книгой: его советы всегда были очень полезны. Профессор Д. Л. Сервейт внимательно прочитал большую часть рукописи и спас меня от многих ошибок и неточностей. Полезные советы и критические замечания сделали также К. Л. Чинь, А. ЭльГамаль, М. Р. Бест, Н. М. Блечман, Т. Ха-симото, К. Кобаяси, М. Симада, Г. Унгербёк, В. Вандеркулк, С. Виноград и С. К- Вест. Кни-г-и и статьи, прямо или косвенно оказавшие существенное влияние на нашу книгу, перечислены в списке литературы; список статей, оказавших меньшее влияние, был бы необъятным.

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

Наиболее важное участие в подготовке книги приняла моя жена Барбара. Она помогала и морально поддерживала меня, разделяя все трудности и удачи. Наконец, эта книга посвящается Эдварду Дж. Блейхуту, Эндрю С. Чамеру и Карлу А. Краченфелсу; частицы их душ живут в ней.

ГЛАВА 1 ВВЕДЕНИЕ

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

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

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

1.1. ДИСКРЕТНЫЙ КАНАЛ СВЯЗИ

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

КоОовое слово источника

Оценка койобого слова

источника

Койер канала

Система сеязи

ДекоЭер канала

Койобое слово канала

Принятое слово

Мойулятор

ДемоОулятор

Канал

Рис. 1.1. Блок-схема цифровой системы связи.

цифровой системы связи так, как показано на блок-схеме на рис. 1.1.

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

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