2.2. Полиномиальные коды

В предыдущих разделах кодовое слово -кода представлялось в виде набора длиной

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

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

2.2.1. Арифметика конечных полей

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

Все конечные поля обладают следующими свойствами:

1) существуют две операции, используемые для комбинирования элементов: умножение и сложение;

2) результатом умножения или сложения двух элементов поля является третий элемент, лежащий в том же поле;

3) поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0; таким образом, а для любого элемента а;

4) для любого элемента а существует обратный элемент по сложению и обратный элемент по умножению (если такие что и существование этих элементов позволяет использовать обычные обозначения для вычитания и делення;

5) выполняются обычные правила ассоциативности коммутативности и дистрибутивности

Конечные поля существуют не при любом числе элементов, а только в случае, если число элементов является простым числом или степенью простого числа. В первом случае поле называется простым, во втором — расширением соответствующего простого ноля.

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

таблицы сложения и умножения для простого поля объединены в табл. 2.3. Для выполнения вычитания или деления следует, используя таблицы, найти соответствующий обратный элемент а затем выполнить сложение или умножение обычным образом. Например,

Аналогично,

Если является степенью простого числа (скажем, то элементами поля являются все многочлены степени или менее, коэффициенты которых лежат в простом поле

Таблица 2.3. (см. скан) Таблицы умножения и сложения для

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

Многочлен неприводим над и может быть использован для построения Пусть два элемента Можно образовать их сумму

и их произведение

Для того чтобы привести это выражение по модулю будем последовательно использовать равенство Так,

и

Читатель должен заметить, что приведение многочлена по модулю эквивалентно делению на и взятию остатка. Это легко провбрить для только что рассмотренного примера. С этим тесно связано понятие сравнимости:

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

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

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

в точности как для обычных чисел.

Точно так же можно поступить в случае поля Если положить то

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

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

Таблица 2.4. (см. скан) Связь того и логарифмического представлений элементов

Существование логарифмов в конечном поле означает, что имеется представление элементов конечного поля, которое оказывается удобным для умножения, и другое представление, которое оказывается удобным для сложения. После того как установлено соответствие между этими представлениями, уже не нужно явно выписывать элементы поля в виде многочленов. Наиболее удобный метод состоит в представлении элемента поля в виде набора длиной при выполнении сложения и в виде степени примитивного элемента при выполнении умножения. Так, для представление в табл. 2.4 эквивалентно представлению, задаваемому уравнениями (2.7). Используя табл. 2.4, легко производить арифметические операции в поле Пусть, например, требуется вычислить значение

Из табл. 2.4 получаем Поэтому

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

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

Логарифмы Зеча для приведены в табл. 2.5. Используя эту таблицу, получаем

Таблица 2.5. (см. скан) Логарифмы Зеча в