8.1.4. Конечные поля

Для понимания принципов кодирования и декодирования недвоичных кодов, таких как коды Рида-Соломона, нужно сделать экскурс в понятие конечных полей, известных как поля Галуа (Galois fields — GF). Для любого простого числа p существует конечное поле, которое обозначается GF(p) и содержит p элементов. Понятие GF(p) можно обобщить на поле из  элементов, именуемое полем расширения GF(p); это поле обозначается GF( ), где т — положительное целое число. Заметим, что GF( ) содержит в качестве подмножества все элементы GF(p). Символы из поля расширения GF(

) используются при построении кодов Рида-Соломона.

Двоичное поле GF(2) является подполем поля расширения GF( ), точно так же как поле вещественных чисел является подполем поля комплексных чисел. Кроме чисел 0 и 1, в поле расширения существуют дополнительные однозначные элементы, которые будут представлены новым символом а. Каждый ненулевой элемент в GF( ) можно представить как степень . Бесконечное множество элементов, F, образуется из стартового множества  и генерируется дополнительными элементами путем последовательного умножения последней записи на .

                         (8.9)

Для вычисления из F конечного множества элементов GF( ) на F нужно наложить условия: оно может содержать только  элемента и быть замкнутым относительно операции умножения. Условие замыкания множества элементов поля по отношению к операции умножения имеет вид неприводимого полинома.

                                                 (8.9)

или, что тоже самое,

                                             (8.10)

С помощью полиномиального ограничения любой элемент со степенью, большей или равной , можно следующим образом понизить до элемента со степенью, меньшей .

                           (8.11)

Таким образом, как показано ниже, уравнение (8.10) можно использовать для формирования конечной последовательности F* из бесконечной последовательности F.

           (8.12)

Следовательно, из уравнения (8.12) можно видеть, что элементы конечного поля GF( ) даются следующим выражением.

                                 (8.13)

8.1.4.1. Операция сложения в поле расширения gf(2m)

Каждый из  элементов конечного поля GF( ) можно представить как отдельный полином степени от m-1 или меньше. Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент GF( ) полиномом , в котором последние т коэффициентов  нулевые. Для ,

              (8.14)

Рассмотрим случай m = 3, в котором конечное поле обозначается GF(2³). На рис. 8.7 показано отображение семи элементов { } и нулевого элемента в слагаемые базисных элементов , описываемых уравнением (8.14). Поскольку из уравнения (8.10) , в этом поле имеется семь ненулевых элементов или всего восемь элементов. Каждая строка на рис. 8.7 содержит последовательность двоичных величин, представляющих коэффициенты ,  и  из уравнения (8.14). Одним из преимуществ использования элементов  поля расширения, вместо двоичных элементов, является компактность записи, что оказывается удобным при математическом описании процессов недвоичного кодирования и декодирования. Сложение двух элементов конечного поля, следовательно, определяется как суммирование по модулю 2 всех коэффициентов при элементах одинаковых степеней.

         (8.15)