ВВЕДЕНИЕ

Теория кодирования возникла в конце 40-х годов с появлением работ Голея, Хэмминга и Шеннона. Истоками теории являются инженерные задачи, но ее развитие приводит к все более и более утонченным математическим методам. Наша задача — дать простое, доступное и одновременно раскрывающее все важные аспекты предмета изложение теории кодирования. В книге читатель найдет достаточно подробное описание как простейших семейств кодов (кодов Хэмминга, БЧХ, циклических и кодов Рида — Маллера) вместе с методами их кодирования и декодирования, так и современных вопросов теории, таких как квадратично-вычетные коды, коды Голея, Гоппы, альтернантные, Кердока, Препараты, самодуальные коды и схемы отношений.

Тщательно освещается вопрос о границах объема кода. Обсуждаются простейшие результаты (границы сферической упаковки, границы Плоткина, Элайеса и Варшамова — Гилберта) и метод линейного программирования и асимптотически наилучший известный результат (граница Мак-Элиса, Родемича, Рамсея и Велча). В приложении приводятся таблицы границ и наилучшие известные на сегодняшний день коды длин вплоть до 512.

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

Начальный курс теории кодирования для математиков: гл. 1; гл. 2 (§ 2.6 до теоремы 2.22); гл. 3; § 4.1-4.5; гл. 5 (до упражнения 5); гл. 7 (за исключением § 7.7, 7.8); § 8.1-8.3; § 9.1-9.4; § 12.8; § 13.1 — 13.3; § 14.1 — 14.3.

Более полный курс для математиков: § 2.1-2.6, 2.8; § 4.6, 4.7 и часть § 4.8; гл. 5 (до упражнения 6 и § 5.3-5.5, 5.7); § 6.1-6.3 (без доказательства теоремы 33); § 8.5, 8.6; § 9.2, 9.3, 9.5; § 10.1 - 10.5, 10.11; § 13.4, 13.5. 13.9; § 16.1 — 16.6; § 17.7 (до теоремы 35); § 19.1 — 19.3.

(см. скан)

альтернантных (включая коды БЧХ, Гоппы, Сривэставы и обобщение Ченя - Чоя кодов БЧХ) - § 12.9; квадратично-вычетных кодов — § 16.9;

циклических кодов — § 16.9 (в замечаниях к гл. 16 упоминаются другие методы декодирования).

При чтении книги следуйте совету, который дается в любом предисловии: если материал вызывает у вас трудности, пропустите его, но продолжайте чтение! Не стесняйтесь пропускать доказательства теорем: мы часто делаем это. Материал, отмеченный звездочкой, является трудным или затянутым и может быть пропущен при первом (и даже при втором) чтении. В конце книги приводится обширный список литературы. Поскольку теория кодирования пересекается со многими другими областями (вычислительной техникой, дискретными системами, теорией групп, теорией чисел, планированием экспериментов и т. д.), то относящиеся к ней работы можно встретить в научной литературе практически всюду. Это, к сожалению, приводит к тому, что обычные реферативные журналы оказываются не всегда полезными. Именно поэтому мы чувствовали себя обязанными привести возможно более обширный список литературы. В конце каждой главы приводятся замечания, в которых указаны источники теорем, упражнений, таблиц, а также небольшой список литературы по некоторым вопросам (решенным или нерешенным), затрагиваемым в данной главе.

В книге рассматриваются только блоковые коды, предназначенные для исправления случайных ошибок; мы практически не касаемся кодов, исправляющих другие виды ошибок (пакетов или замещений), кодов с переменной длиной, сверточных кодов и кодирования источников (см. замечания к гл. 1). Более того, мы часто ограничиваемся только двоичными кодами, что существенно облегчает теорию. Многие авторы придерживаются другой точки зрения: анализируя двоичный случай, они формулируют результаты для произвольных полей.

Часть вопросов, включенных в первоначальный план книги, была с сожалением опущена, чтобы не увеличивать объем книги:

(i). Коды Грея и коды для задачи «змея в ящике» — см. Адель-сон и др. [5, 6], Бухнер [210], Кавио [253], Чин и др. [290], Кон [299], Данцер и Кли [328], Девайс [355], Дуглас [382, 383], Ивен [413], Флорес [432], Гарднер [468], Гилберт [481], Гюи [571], Харпер [605], Кли [764—767], Мекленберг и др. [951], Миллс [956], Препарата и Нивергемт [1083], Синглтон [1215], Тэнг и Лью [1307], Васильев [1440], Юен [1448, 1449].

(ii). Коды без запятой — см. Болл и Каммингс [60, 61], Баумерт и Кантор [85], Крик и др. [316], Истмен [399], Голомб [523], Голомб и др. [528], Холл [587], Джиггс [692], Миякава и Морайя [967], Нихо [993], Рединбо и Уолкотт [1102]. О кодах для синхронизации см. также в замечаниях к гл. 1.

(iii). Коды с неравной защитой символов — см. Гор и Килгас [549], Килгас и Гор [761], Мандельбаум [901].

(iv). Кодирование для каналов с обратной связью — см. Берлекэмп [124], Хорстейн [664], Шелквик и др. [1153—1155].

(v). Коды для гауссовского канала — см. Бильери и др. [148— 151], Блейк [155, 156, 158], Блейк и Муллин [162], Чедвик и др. [256, 257], Галлагер [464], Ингемарссон [683], Ландау [791], Оттосон [1017], Шеннон [1191], Слепян [1221 — 1223], Цеттерберг [1456].

(vi). Сложность декодирования — см. Байога и Волбессер [59], Чейтин [257а-258а], Гельфанд и др. [471], Гросс [564], Юстесен [706], Колмогоров [774а], Маргино [916], Мартин-Леф [917а], Пинскер [1046а], Сервейт [1145], Сэведж [1149—1152а].

(vii). Связь между теорией кодирования и задачей упаковки -мерного евклидового пространства одинаковыми шарами — см. Лич [803—805], Лич и Слоэн [808—810], Слоэн [1226].

Нашей книге предшествовали следующие монографии и книги по теории информации: Берлекэмп [113, 116], Блейк и Муллин [162], Камерон и Ван Линт [234], Голомб [522], Лин [834], Ван Линт [848], Месси [922а], Питерсон [1036а], Питерсон и Уелдон [1040], Соломон [1251], Слоэн [1227а]; обширный список литературы имеется в работах: Берлекэмп [126], Блейк [157], Хартнетт [620], Манн [909], Слепян [1224], специальные выпуски - [377а, 678, 679]. См. также список литературы в [1022].

Мы обязаны нескольким друзьям, тщательно прочитавшим первый черновик, внесшим исправления и улучшения и спасшим нас от грубых ошибок. В частности, мы хотим выразить свою признательность И. Ф. Блейку, П. Дельсарту, Дж. М. Геталсу, Р. Л. Грехэму, Дж.-М. Ван Линту, Дж. Лонго, К. Л. Мэллоусу, Дж. Мак-Клею, В. Плесс, Г. О. Поллаку, Л. Д. Рудольфу, Д. У. Сервейту, а также многим другим коллегам по работе в лабораториях Белла, в частности А. М. Одлыжко, за их помощь. Однако мы следовали не всем их предложениям, поэтому авторы несут полную ответственность за оставшиеся ошибки. (Это замечание следует принимать всерьез.) Нам также приятно поблагодарить всех машинисток лабораторий Белла, помогавших нам на разных этапах подготовки рукописи, нашего секретаря Пегги ван Несс и особенно Мэрион Мессерсмис, печатавшую и перепечатывавшую большинство глав. Сэм Ломонако весьма любезно помог нам исправить опечатки в верстке.

Авторы