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

В теории оптимального кодирования информации за последние годы центр тяжести переместился от общих теорем о существовании способов кодирования и декодирования с нужными свойствами к построению конкретных методов кодирования, позволяющих реально осуществить передачу информации с большой надежностью и достаточно высокой скоростью. Главных направлений в построении таких методов два: перспективный метод последовательного декодирования, основанный на теоретико-вероятностных соображениях, и алгебраическая теория кодов, исправляющих ошибки. Первому из них, еще недостаточно разработанному, посвящена книга Дж, Возенкрафта и Б. Рейффена "Последовательное декодирование" (ИЛ, 1963); основным же направлением, которому посвящена подавляющая часть работ в этой области, является алгебраическая теория кодов, исправляющих ошибки. Первые исследования в этой области появились в США лишь в середине 50-х годов, однако их количество бурно растет (библиография к книге, доведенная до 1960 года, содержит более 100 названий), и теперь эта теория представляет собой обширную и математически глубокую отрасль науки. Расширяются ее приложения к технике связи и вычислительным машинам, что вызывает у инженеров соответствующих специальностей большой интерес к теории кодов, исправляющих ошибки.

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

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

из букв алфавита А, трактуемые как подлежащие передаче сигналы. Особенно важен случай двоичного кода Расстояние между двумя последовательностями определяется как число пар несовпадающих их членов с тем же индексом. Код объема совокупность К таких последовательностей. Кодовое расстояние кода — это наименьшее из попарных расстояний между последовательностями кода. (Если расстояние между двумя переданными сигналами равно то после передачи можно, очевидно, все еще различить переданные сигналы даже в том случае, когда каждый из них исказится в местах. Поэтому о коде с кодовым расстоянием говорят, что он исправляет ошибок.) Требуется при заданных и К построить код с наибольшим кодовым расстоянием

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

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

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

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

русском языке (Ван-дер-Варден Б. Л., Современная алгебра, ч. I, Гостехиздат, 1947; Постников М. М., Основы теории Галуа, Физматгиз, 1960; Зарисский О., Самюэль П., Коммутативная алгебра, т. I, ИЛ, 1963), хотя они мало приспособлены к нуждам теории кодирования.

При переводе книги возникли серьезные терминологические трудности, связанные с отсутствием или неоднозначностью русской терминологии. Так, после долгих размышлений в качестве перевода английского термина burst of error был выбран термин "пачка ошибок", хотя в русской литературе встречаются и другие варианты ("пакет ошибок", "вспышка ошибок" и т. п.).

Редактор и переводчик искренне благодарны автору книги проф Питерсону. любезно приславшему список поправок к английскому изданию книги. Эти поправки, конечно, внесены в русский перевод,

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

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

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

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

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

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

Серьезную работу в области кодирования я начал в 1955 г. в корпорации ИБМ совместно с Макдональдом и Фонтейном и продолжал работать с ними вплоть до 1960 г. в качестве консультанта и временного сотрудника в период летних каникул. Особенно интенсивно я занимался вопросами теории кодирования в связи с сотрудничеством в исследовательской лаборатории электроники Массачусетс ского технологического института, где я работал консультантом весной 1956 г. и вторым профессором в течение 1959 учебного года.

Я в долгу перед профессором Р. М. Фано за его предложение написать эту книгу. Было очень приятно сравнивать мои наброски рукописи с рукописью книги, которую он сам одновременно готовил

к печати, и соревноваться в том, чья книга первой увидит свет. Наше соревнование закончилось вничью.

Мне повезло и в том, что я имел возможность обсудить многие вопросы теории кодирования с крупными специалистами в этой области. Я глубоко благодарен Э. Прейнджу за ряд бесед, в течение которых мы обсуждали, в частности, содержание 3, 8 и II глав этой книги; кроме того, именно его работа впервые вызвала у меня интерес к циклическим кодам. В ряде вопросов мне помогли разобраться Н. Цирлер и Д. Горенштейн, Д. Хегельбергер сделал несколько ценных предложений, касающихся гл, 12. Несколько раз в жарких и плодотворных спорах я обсуждал главным образом циклические коды с Н. Эйбрамсоном, К. М. Меласом и Дж. Меггитом. Я позволю себе выразить благодарность Д. Брауну, Р. Галлагеру и А, Фонтейну за ряд бесед, посвященных содержанию книги.

Практическая минимизация логических схем из разд. 11.1 была проделана Дж. П. Ротом из корпорации ИБМ и Т. Барти из лаборатории Линкольна Массачусетского технологического института. Остальные вычисления были выполнены в лабораториях ИБМ в Поукипси, в вычислительном центре Массачусетского технологического института и в лаборатории статистики Флоридского университета.

Первые десять глав представляют собой конспект лекций по курсу теории информации, прочитанному мной во втором семестре 1959/1960 учебного года в Массачусетсом технологическом институте. Как студенты, так и некоторые из моих коллег указали на ряд допущенных ошибок. Особенно ценными оказались списки ошибок, которые мне любезно передали Прейндж, Фонтейн, Галлагер, Г. Экре, К, Кампопиано и Дж. Крускал.

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

Уэсла Питерсон

Гейпсвил, Флорида, январь 1961