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

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

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

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

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

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

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

Укажем также на другой важный и интересный аспект алгебраической теории кодирования — изучение конечных абелевых групп на уровне подмножеств. Теория конечных абелевых групп на уровне подгрупп является вполне классической. Для многих прикладных вопросов (например, для теории распознавания образов) существенно изучение подмножеств конечной абелевой группы, не являющихся смежными классами по подгруппам, но полученных из таких смежных классов путем некоторых регулярных операций. Теория кодирования дает естественные классы таких подмножеств.

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

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

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

С. Берман

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

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

Новый подход к решению этой проблемы был найден в важных работах Рида и Соломона [1960], Хоквингема [1959], Боуза и Чоудхури [1960], Горенстейна и Цирлера [1961] и Питерсона [1961]. Выбрав в качестве алфавита кода поле Галуа, удалось свести задачу к решению алгебраического уравнения, корни которого определяют местоположение ошибок. При этом задача декодирования сводится к вычислительной задаче получения этого уравнения и определения его корней. Вычислительная сложность реализации такой процедуры примерно на порядок меньше вычислительной сложности непосредственного декодирования с помощью исчерпывающего перебора. В данной книге предлагается новая методика декодирования, позволяющая строить алгебраические декодеры, сложность которых на порядок меньше сложности тех, которые рассматривались до сих пор.

Читателя, интересующегося «простым» или «элементарным» доказательством теоремы Боуза — Чоудхури — Хоквингема, мы должны предупредить, что в данной книге такая попытка не предпринимается. Истинное достоинство конструкции Боуза — Чоудхури — Хоквингема (БЧХ-конструкции) состоит не в теореме о том, что для любого данного можно построить коды с исправлением ошибок. Как будет показано в гл. 13, минимальное расстояние БЧХ-кодов асимптотически стремится к нулю. Даже при умеренных блоковых длинах квадратично-вычетные коды либо столь же хороши, либо лучше. Важнейшее свойство БЧХ-кодов состоит в том, что они позволяют исправлять до ошибок (и многие ошибки более высокой кратности) с помощью простого легко реализуемого алгоритма. Часто наблюдается противоречие между так называемыми «простыми» доказательствами и доказательствами, приводящими к простой

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

В книге делается попытка изучить два круга вопросов:

1. Всестороннее рассмотрение алгебраической теории кодирования, включая БЧХ-коды (которые содержат коды Рида — Соломона), коды Сривэставы, новый класс негациклических кодов для метрики Ли, некоторые другие классы кодов и наилучшие из известных методов их декодирования.

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

Распределение материала по главам книги примерно показано на рис. 0.1. Например, вопросы, рассмотренные в гл. 6, лежат на стыке алгебраической теории кодов, современной алгебры, элементарной теории чисел, теории последовательностей, порождаемых регистрами сдвига. Инженерные направления соответствуют разделам, выписанным на рис. 0.1 справа, а математические — слева. Мы надеемся, что книга будет полезна для читателей с различными интересами.

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

(кликните для просмотра скана)

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

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

Обозначения. Во всей книге матрицы обозначаются рукописными буквами, например вектор-строки — полужирными буквами, например Вектор, транспонированный к вектору обозначается через IV; так как в книге нигде не используется степень вектора то это не приводит к путанице. Последовательность многочленов всегда снабжается верхними индексами, например где Там, где исключена неопределенность, последовательность иногда обозначается через

Во всей книге, за исключением рисунков, таблиц и задач, используется десятичная система нумерации. Например, уравнение (3.37) находится после теоремы 3.36 и до раздела 3.4. Аналогично, теорема 6.69 следует за определением 6.689 и перед леммой 6.691.

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

Элвин Р. Берлекэмп