АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ КОДИРОВАНИЯ

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

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

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

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

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

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

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

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

С. Берман

Хорошее исследование синхронизирующих кодов дал Стиффлер [1969].

° S н

п 5 в

ф о э

а и » а

I I I

н 5 " о. g.«<o о Cf ео Ю m ts Л о Н Ч W W

1«1

Й о g и

« - я -2

О И e H S " m 3 о H ZrZ

H S>e<rot=t:3

о H <gg

at, §

И о

о n, ч А S S §

л о ни

се се

н «.

19 S се

и >, ее

19 И m

о о о

m о П Л.

19 CV

°

° S 3 lift

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

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

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

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

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

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

Гл. 1. Основные двоичные коды

следующее правило. Подсчитывается число нулей и число единиц в полученной последовательности. Если нулей получено больше, чем единиц, то выносится решение, что передаваемое кодовое слово состояло из нулей; если единиц получено больше, чем нулей, тО выносится решение, что передаваемое кодовое слово состояло и» единиц. Если число нулей оказывается равным числу единиц, то решение не принимается.

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

В наших рассмотрениях отказ от декодирования предпочтительнее ошибки декодирования, а правильное декодирование предпочтительнее обеих этих возможностей. Конечно, модифицируя алгоритм декодирования, часто можно изменить соотношения между отказами и ошибками декодирования. Например, рассмотрим код с повторением с блоковой длиной и = 5. Сначала предположим, что если полученная последовательность содержит не более двух единиц, то она декодируется как нулевое кодовое слово. В противном случае она декодируется как единичное кодовое слово. Этот алгоритм декодирует каждое возможное полученное слово в одно из возможных кодовых слов; такое декодирование называется полным. В полных алгоритмах декодирования отказ от декодирования невозможен. Однако для того же кода с повторением с блоковой длиной п = 5 можно использовать и альтернативный алгоритм неполного декодирования. Например, можно декодировать все полученные последовательности, содержащие О или 1 единиц как нулевое кодовое слово, а все полученные последовательности, содержащие 4 или 5 единиц, как единичное кодовое слово. Этот алгоритм декодирования не действует при декодировании последовательностей, содержащих 2 или 3 единицы. Хотя этот алгоритм неполного декодирования имеет положительную вероятность отказа от декодирования, он имеет значительно меньшую вероятность ошибки декодирования, чем полный алгоритм.

В некоторых приложениях ошибка декодирования равносильна катастрофе, например при получении неправильной команды на

1.1. Коды с повторением и коды с одной проверкой на четность

1) То есть декодер оказывается в классической ситуации буриданова осла.- Прим. ред.

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

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

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

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

Замечательным примером таких высокоскоростных кодов являются коды с одной проверкой на четность, содержащие только один проверочный символ. Этот проверочный символ является суммой по модулю два п - 1 информационных символов. Информационные символы складываются в соответствии с двоичными правилами: 0+0=0, 0 + 1 = 1, 1+0 = 1, 1 + 1=0. Двоичная сумма некоторого числа двоичных цифр равна О или 1 в соответствии с четностью или нечетностью числа единиц среди складываемых двоичных цифр. Поэтому общее число единиц (включая проверочный символ) в каждом кодовом слове кода с одной проверкой на четность всегда четно. Если полученное слово содержит четное число единиц, то декодер должен декодировать его без изменений, а в противном случае слово не декодируется. Это правило неполного декодирования позволяет правильно декодировать только тогда, когда канал не исказил ни одного символа передаваемого блока. Одиночные ошибки (или любое нечетное число ошибок) приводят к отказу от декодирования и тем самым обнаруживаются. Любое ненулевое четное число ошибок приводит к ошибке декодирования.