Замечания

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

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

Хотя в данной книге используется только расстояние Хэммннга [107], существует по крайней мере еще одна функция — расстояние Ли [41, 64, 82], которая уже использовалась в теории кодирования. В случае двоичного кода расстояние Ли и расстояние Хэмминга совпадают.

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

эффективной процедурой декодирования были развиты Галлагером [18] и Возенкрафтом [15, 16], и в обоих случаях моделирование на вычислительных машинах дало весьма ободряющие результаты. Эти результаты обсуждаются очень кратко соответственно в гл. II и 12.

В последнее время некоторое внимание привлекла проблема кодирования сообщений в непрерывные сигналы и вместе с тем проблема полного использования пропускной способности непрерывных каналов. Сейчас наше понимание непрерывных каналов сравнимо с нашим пониманием дискретных каналов приблизительно пятилетней давности [36, 118]. Некоторый прогресс был также достигнут в понимании возможностей двусторонних каналов [17, 106].

Почти всегда для любого результата, относящегося к каналам с ошибками (таким, как двоичный симметричный канал), существует аналогичный результат для каналов со стиранием. Многие из таких результатов приведены как упражнения. Некоторые из них — в основном в связи с использованием двоичных кодов Боуэа — Чоудхури для каналов с ошибками и стираниями — включены в основной текст. Понятие канала со стиранием ввел Элайес [126], и практически ему должны быть прямо или косвенно приписаны все результаты, включенные в эту книгу относительно таких каналов. Декодирование для каналов со стиранием было изучено Эпстейном [130].

Фано [87] закончил только что книгу, представляющую собой прекрасное общее введение в теорию связи. Эта книга содержит многие важные результаты, относящиеся к теории кодирования, которые прежде были доступны только по журнальным статьям. Классическая основополагающая статья Шеннона все еще является хорошим руководством. Читателю математику можно рекомендовать книгу Файнстена [85], Простейшее и наиболее доступное изложение можно найти в книге Голдмана [21].

Задачи

(см. скан)

(см. скан)