Scientific journal
International Journal of Applied and fundamental research
ISSN 1996-3955
ИФ РИНЦ = 0,593

EFFECTIVE COMPUTATIONAL SCHEMES FOR THE ARITHMETIC OF GALOIS FIELD GF(28) IN THE ERROR-CORRECTING CODING TECHNOLOGY

Rahman P.A. 1
1 Ufa State Petroleum Technological University Sterlitamak branch
1076 KB
This paper deals with the arithmetic of Galois Field GF(28) based on the irreducible polynomial p(x) = x8 + x4 + x3 + x2 + 1, which is widely used in error-correcting coding technologies. The schemes for generating the tables of logarithms and anti-logarithms on base of the primitive element α = 2, formula for the addition, multiplication, division, inversion of field elements and powering elements to the given degree are also discussed. Calculation examples of arithmetic operations with the field elements are also provided. The high-performance schemes of the direct multiplication and inversion of the field elements are also observed.
Galois field
arithmetic
effective computations
error-correcting coding

На сегодняшний день информация играет ключевую роль, как в жизни отдельного человека, так и в бизнес-процессах предприятий. Соответственно, защита ее от искажения в системах хранения и каналах передачи данных при помощи технологии помехоустойчивого кодирования является актуальной задачей [1]. Однако, современные технологии помехоустойчивого кодирования данных [2] базируются на специализированных разделах математики, в частности, арифметике полей Галуа GF(28), и для разработки программных или аппаратных реализаций, требуются дополнительные исследования [3-8] и выведение достаточно простых для понимания, и в то же время, высокопроизводительных вычислительных схем для конкретных технологий помехоустойчивого кодирования.

Арифметика поля Галуа GF(28) с применением логарифмов в технологии помехоустойчивого кодирования на базе кодов Рида-Соломона. Поле Галуа GF(28) является частным случаем расширенных конечных полей GF(2m) характеристики 2 и имеет широкое применение в технологиях помехоустойчивой передачи и хранения информации благодаря тому, что основной единицей информации в вычислительной технике является байт. Байт состоит 8 битов и с помощью него можно представить 256 различных символов, и поле Галуа GF(28) также содержит 256 элементов, которые также можно представить в виде 8-разрядных двоичных чисел.

Яркие примеры использования арифметики поля Галуа GF(28): помехоустойчивое кодирование с применением кодов Рида-Соломона для хранения информации на оптических дисках с данными – Data CD-ROM и при передаче информации в стандарте цифрового телевещания DVB – Digital Video Broadcasting.

Поле Галуа GF(28) по определению содержит 256 элементов:

rah01.wmf

Поле Галуа GF(28), по определению являющееся полем многочленов вида rah02.wmf, образуется на базе простого поля Галуа GF(2) и неприводимого многочлена 8-й степени. В технологии помехоустойчивого кодирования используется неприводимый многочлен следующего вида:

rah03.wmf (1)

В двоичном представлении неприводимый многочлен выглядит как: rah04.wmf, а в десятичном представлении: rah05.wmf.

В качестве примитивного элемента поля GF(28) в технологии помехоустойчивого кодирования выбирают элемент α(x) = x. При помощи него можно получить все ненулевые элементы поля. В двоичном представлении примитивный элемент поля выглядит как (α)2 = 10, а в десятичном представлении, соответственно, как (α)10 = 2.

Для формирования таблицы степеней примитивного элемента (α)10 = 2 используется представленная ниже рекуррентная схема для случая поля Галуа GF(28) с неприводимым многочленом p(x) = x8 + x4 + x3 + x + 1. Что касается таблицы логарифмов, то ее можно формировать параллельно с формированием таблицы степеней, используя десятичное представление степеней примитивного элемента в качестве индексов таблицы логарифмов.

rah06.wmf (2)

Под выражением rah07.wmf понимается сдвиг двоичного числа влево на один разряд. Под выражением rah08.wmf понимается сдвиг двоичного числа влево на один разряд с последующей операцией «побитового» XOR результата сдвига с двоичным эквивалентом примитивного неприводимого многочлена.

Примечание. Поскольку в десятичном виде примитивный элемент поля GF(28) выглядит как (α)10 = 2, то будем также обозначать k-ую степень примитивного элемента как 2k, а логарифм от элемента a по основанию примитивного элемента как log2a.

rahm1.tif

Рис. 1. Таблица степеней 2k для поля Галуа GF(28)

Ниже на рис. 1 (в виде матрицы 16 x 16) приведены степени примитивного элемента (α)10 = 2 поля GF(28), образованного при помощи примитивного неприводимого многочлена p(x) = x8 + x4 + x3 + x2 + 1. Степени примитивного элемента для компактности приведены в десятичном представлении, и расположены построчно (по 16 в строке), начиная с 0-й степени, и заканчивая 255-й. Заметим, что 255-я степень эквивалентна 0-й степени и равна 1 в силу свойств конечных полей Галуа rah09.wmf: rah10.wmf.

Примечание 1. Для того, чтобы выбрать в таблице требуемую степень 2k, необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца (индексы строк приведены в левом заголовочном столбце серого цвета, индексы столбцов – в верхней заголовочной строке серого цвета) была равна показателю степени k.

rahm2.tif

Рис. 2. Таблица логарифмов log2a для поля Галуа GF(28)

Также ниже на рис. 2 (в виде матрицы 16 x 16) приведены логарифмы по основанию примитивного элемента (α)10 = 2 поля GF(28). Логарифмы расположены построчно (по 16 в строке) для всех элементов поля, начиная с (a)10 = 0, заканчивая (a)10 = 255. Заметим, что логарифм от 0 не существует (соответствующая ячейка «N/A»).

Примечание 2. Для того, чтобы выбрать в таблице логарифм log2a заданного элемента a поля GF(28), необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца (индексы строк приведены в левом заголовочном столбце серого цвета, индексы столбцов – в верхней заголовочной строке серого цвета) была равна десятичному представлению (эквиваленту) элемента a.

Тогда с учетом всего вышесказанного имеем арифметику поля Галуа GF(28), образованного с помощью неприводимого многочлена p(x) = x8 + x4 + x3 + x2 + 1 и на базе применения логарифмов по основанию примитивного элемента (α)10 = 2:

- rah12.wmf

- rah13.wmf (3)

- rah14.wmf

Кроме того, если необходимо найти обратный элемент по умножению, то можно воспользоваться упрощенным вариантом формулы деления элементов:

- rah15.wmf. (4)

Наконец, для возведения в степень v заданного элемента a поля GF(28) можно использовать формулу, применив операцию модулярного умножения логарифмов:

- rah16.wmf (5)

Пример 1. Найдем сумму элементов расширенного поля GF(28), представленных в виде соответствующих чисел «123» и «231» в десятичной системе счисления. Имеем,

rah17.wmf

rah18.wmf.

Таким образом, rah19.wmf.

Пример 2. Найдем произведение элементов поля GF(28), представленных в виде соответствующих чисел «20» и «11» в десятичной системе счисления. По таблице логарифмов для поля GF(28) имеем логарифмы элементов: rah20.wmf и rah21.wmf. Тогда получаем:

rah22.wmf.

По таблице степеней для поля GF(28) имеем 235 = (156)10. Таким образом:

rah23.wmf

Пример 3. Найдем отношение элементов поля GF(28), представленных в виде соответствующих чисел «220» и «127» в десятичной системе счисления. По таблице логарифмов для поля GF(28) имеем логарифмы элементов: rah24.wmf и rah25.wmf. Тогда получаем:

rah26a.wmf

rah26b.wmf.

По таблице степеней имеем 2100 = (17)10. Таким образом: rah27.wmf.

Пример 4. Найдем обратный элемент по умножению для элемента «111», представленного в десятичном виде. По таблице логарифмов имеем логарифм элемента: rah28.wmf. Тогда обратный элемент:

rah29.wmf.

По таблице степеней имеем 2194 = (50)10. Таким образом: rah30.wmf.

Пример 5. Возведем элемент «13», представленный в десятичном виде, в заданную степень v = 17. По таблице логарифмов для поля GF(28) имеем логарифм элемента: rah31.wmf. Тогда по формуле получаем:

rah32.wmf.

По таблице степеней имеем 2238 = (11)10. Таким образом, rah33.wmf.

Схемы прямого умножения и инвертирования элементов поля Галуа GF(28) в технологии помехоустойчивого кодирования информации. В случае необходимости высокопроизводительного прямого умножения элементов a и b поля Галуа GF(28), можно использовать заранее подготовленную свертку соответствующих многочленов a(x) и b(x) по модулю неприводимого многочлена p(x) = x8 + x4 + x3 + x2 + 1:

rah34.wmf

Аппаратную реализацию схемы умножения мы не будем приводить в силу ее громоздкости. Отметим лишь, что ее несложно построить при помощи 64 двухвходовых логических элементов «И» и 8 многовходовых сумматоров по модулю 2.

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

rahm3.tif

Рис. 3. Таблица обратных элементов по умножению для поля Галуа GF(28)

Ниже на рис. 3 (в виде матрицы 16 x 16) приведены обратные элементы по умножению для элементов поля Галуа GF(28), представленные в десятичном виде. Обратные элементы по умножению расположены построчно (по 16 в строке) для всех элементов поля, начиная с (a)10 = 0, заканчивая (a)10 = 255. Заметим, что обратного элемента по умножению для нуля не существует (соответствующая ячейка «N/A»).

Для аппаратной реализации таблицы можно использовать ПЗУ емкостью 256 x 8 бит.

Заключение

Таким образом, в рамках данной статьи рассмотрено поле Галуа GF(28) на базе неприводимого многочлена p(x) = x8 + x4 + x3 + x2 + 1, которое применяется в технологии помехоустойчивого кодирования информации. Также рассмотрены схема формирования таблиц степеней и логарифмов на базе примитивного элемента (α)10 = 2, формулы сложения, умножения и деления, а также инвертирования элементов и возведения в заданную степень. Приведены примеры выполнения арифметических операций с элементами поля. Также рассмотрены высокопроизводительные схемы прямого умножения и инвертирования элементов поля.

Полученные результаты могут быть использованы при разработке эффективных программных и аппаратных реализаций вычислительных блоков в рамках кодирования и декодирования информации с применением кодов Рида-Соломона.