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

ARITHMETIC OF BINARY GALOIS FIELD BASED ON CIRCUIT FOR ADDITION AND SUBTRACTION OF LOGARITHMS AND ITS HARDWARE IMPLEMENTATION

Rahman P.A. 1
1 Ufa State Petroleum Technological University Sterlitamak branch
1589 KB
This paper deals with Galois fields GF(2m) with characteristic 2 and their arithmetic. The addition, subtraction operations, primitive elements, logarithms of elements on base of primitive element, and multiplication and division operations based on addition and subtraction of logarithms are also observed. Mathematical background and hardware implementation for addition and subtraction of logarithms, based on two full adders for binary numbers are also given. Hardware implementation of processor for Galois field arithmetic, based on modulo 2 adders, read-only memory for logarithm and exponent tables, multiplexor and circuit for addition and subtraction of logarithms, are also overviewed.
Galois field
logarithms
primitive element
arithmetic processor

В мире информационных технологий конечные поля Галуа GF(2m) имеют огромное практическое значение [1]. В частности, важнейшие алгоритмы обнаружения и исправления искажения информации в системах хранения и сетях передачи данных, использующие коды Рида-Соломона, а также криптографические алгоритмы (например, AES – Advanced Encryption Standard), защищающие информацию от несанкционированного доступа, базируются на арифметике конечных полей Галуа GF(2m).

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

В рамках научных исследований в области надежности систем хранения, передачи и обработки данных [3–9], а также методов информационного резервирования [2, 10], автором была исследована эффективная аппаратная схема сложения и вычитания логарифмов, и на базе нее была разработана схема арифметического процессора для поля Галуа GF(2m).

Арифметика поля Галуа GF(2m). Поле Галуа GF(2m), по определению являющееся полем многочленов вида rah01.wmf, rah02.wmf, образуется на базе простого поля Галуа GF(2) и нормированного примитивного неприводимого многочлена m-й степени: rah03.wmf, rah04.wmf. Особо отметим, что элементы поля можно также рассматривать как m-разрядные двоичные числа rah05.wmf, и более того, для компактной формы представления записывать двоичные эквиваленты элементов поля в десятичной форме (а)10.

Например, поле Галуа GF(24) образуется при помощи неприводимого многочлена rah06.wmf, и его элементы можно рассматривать как многочлены, так и соответствующие двоичные и десятичные эквиваленты:

rah07.wmf

rah08.wmf

Отметим, что в базовом простом поле GF(2) для элемента 0 обратным элементом по сложению является сам элемент 0, также как и для элемента 1 обратным элементом по сложению является сам элемент 1. Соответственно, как сложение, так и вычитание элементов простого поля GF(2) фактически сводятся к одной и той же операции суммирования по модулю 2, и обозначается символом rah09.wmf.

Тогда, при сложении и вычитании элементов поля GF(2m) мы имеем сложение соответствующих коэффициентов многочленов по модулю 2 (при представлении в виде многочленов) или побитовое сложение по модулю 2 соответствующих разрядов двоичных чисел (при представлении в виде двоичных чисел):

rah10.wmf (1)

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

rah11.wmf.

Что касается операций умножения (деления) элементов, то их можно свести к сложению (вычитанию) соответствующих дискретных логарифмов элементов поля по основанию примитивного элемента α поля Галуа GF(2m), и последующего вычисления степени примитивного элемента в степень суммы (разности) логарифмов.

rah12a.wmf (2)

В качестве примитивного элемента обычно выступает элемент α(х) = х, который в десятичном представлении выглядит как (α)10 = 2, но в общем случае может быть и другой элемент поля (например, в криптографических алгоритмах (α)10 = 3). Особо отметим, что логарифмирование и возведение степень для максимальной скорости вычислений лучше производить табличным методом, причем таблицы подготавливать заранее для заданного поля GF(2m), с заданным неприводимым многочленом p(x) и примитивным элементом α, путем последовательного вычисления rah13.wmf, причем rah14.wmf, k = 0…2m – 2.

Так, например, для поля GF(24) таблицы степеней и логарифмов в двоичном и десятичном представлении элементов выглядят следующим образом:

rah15.wmf

rah16.wmf

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

rah19.wmf.

По «таблице степеней» для поля GF(24) имеем α3 = (8)10. Таким образом, результат равен (8)10.

Пример 3. Найдем отношение элементов «12» на «9» в поле GF(24). По «таблице логарифмов» для поля GF(24) имеем логарифмы элементов: rah21.wmf и rah22.wmf. Тогда получаем:

rah23.wmf.

По «таблице степеней» для поля GF(24) имеем α7 = (11)10. Таким образом, результат равен (11)10.

Сложение и вычитание логарифмов элементов поля GF(2m). Теперь отметим то, что для аппаратной реализации операций умножения и деления элементов поля GF(2m) с использованием таблиц степеней и логарифмов, очевидно, что помимо ПЗУ, хранящих эти таблицы, потребуется функциональный узел сложения и вычитания логарифмов элементов поля. Учтем, что логарифмы с точки зрения алгебры вещественных чисел являются целыми неотрицательными числами в диапазоне rah24.wmf и их сложение / вычитание производится по модулю 2m – 1. Среди цифровых интегральных микросхем присутствуют, так называемые полные сумматоры, позволяющие складывать целые неотрицательные числа в диапазоне rah25.wmf, представленные в виде m-разрядных двоичных чисел. Полные сумматоры также формируют выходной сигнал «переноса» в случае, когда сумма чисел больше 2m – 1 и не умещается в m разрядов. Также полные сумматоры имеют специальный вход для учета сигнала переноса от другого сумматора. То есть, фактически полный сумматор складывает три двоичных числа: два m-разрядных и одно 1-разрядное двоичное число, и формирует m + 1 – разрядную двоичную сумму. Особо отметим, что без разряда переноса, m-разрядная сумма, формируемая полным сумматором при сложении m-разрядных двоичных чисел u и v, это не что иное, как остаток (u + v) по модулю 2m, иными словами rah26.wmf, а разряд переноса можно интерпретировать как целую часть от деления (u + v) на число 2m, иными словами rah27.wmf. Теперь заметим, что мы имеет место быть тождество

rah28.wmf.

Преобразуем его следующим образом:

rah29b.wmf

rah29c.wmf.

Теперь применим операцию вычисления остатка по модулю 2m – 1 к левой и правой части тождества, и тогда в итоге получим:

rah31b.wmf

rah31c.wmf.

Тогда, очевидно, что для сложения m-разрядных двоичных чисел u и v по модулю 2m – 1 можно воспользоваться двумя полными сумматорами: первый будет осуществлять сложение чисел, вычисляя m-разрядную двоичную сумму rah32.wmf и перенос rah33.wmf, а второй – складывать rah34.wmf с переносом rah35.wmf, как с одноразрядным двоичным числом, и на втором сумматоре будет получаться

rah36.wmf.

Однако, для получения итогового результата нужно еще вычислить остаток по модулю 2m – 1, но мы заметим, что в большинстве случаях rah37.wmf меньше 2m – 1, и вычисления остатка по модулю 2m – 1 излишне, кроме двух особых случаев, когда rah38.wmf, а rah39.wmf, и когда

rah40.wmf,

а rah41.wmf,

в обоих случаях получается, что

rah42.wmf,

и итоговым результатом должен быть 0. Заметим, что в m-разрядной двоичной сетке, число 2m – 1 несложно превратить в 0, прибавив к нему «лишнюю» 1 при возникновении особых случаев на втором сумматоре, используя его возможность складывать два m-разрядных и одно 1-разрядное число.

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

rah43b.wmf

rah43c.wmf.

Также заметим, что rah44.wmf это не что иное, как «побитовая» инверсия разрядов m-разрядного двоичного числа v.

Тогда с учетом всего вышесказанного, можно использовать следующую схему сложения / вычитания логарифмов u и v по модулю 2m – 1, представленную на рис. 1.

Двоичное число u поступает непосредственно как первое слагаемое на первый сумматор. Двоичное число v поступает как второе слагаемое, предварительно пройдя элементы XOR, которые либо сохраняют его в неизменном виде в случае операции сложения (вход выбора операции Add/Sub = 0), либо осуществляют побитовую инверсию в случае операции вычитания (вход выбора операции Add/Sub = 1). Первый сумматор вычисляет m-разрядную сумму и одноразрядный перенос, которые поступают на второй сумматор, где m-разрядная сумма складывается с переносом, как с одноразрядным двоичным числом. Кроме того, если либо сумма равна 2m – 1, а перенос равен 0, либо сумма равна 2m – 2, а перенос равен 1, то при помощи многовходового элемента «И» и двухвходового элемента XOR формируется «лишняя» 1, которая также подается на второй сумматор, как слагаемое. В итоге на выходе второго сумматора получаем сумму или разность u и v по модулю 2m – 1.

Арифметический процессор для поля Галуа GF(2m) на базе схемы сложения и вычитания логарифмов. Теперь располагая узлом сложения / вычитания по модулю 2m – 1, и добавив к нему двухпортовое ПЗУ с таблицей логарифмов, а также ПЗУ с таблицей степеней, и некоторые вспомогательные узлы, можем рассмотреть арифметический процессор, выполняющий четыре основные операции с элементами поля Галуа GF(2m). Суммарная емкость двух ПЗУ составляет rah45.wmf бит.

rahm1.wmf

Рис. 1. Функциональная схема узла сложения и вычитания по модулю 2m – 1

rahm2.wmf

Рис. 2. Функциональная схема арифметического процессора для поля Галуа GF(2m) с использованием таблиц логарифмов по основанию и степеней примитивного элемента.

Ниже на рис. 2 представлена функциональная схема арифметического процессора. Ключевым элементом является m-разрядный выходной мультиплексор 2 → 1, который при управляющем сигнале S1 = 0 соединяет свои выходы с выходами элементов XOR, осуществляющих фактически сложение (оно же эквивалентно вычитанию) путем операции «побитового» XOR между входными операндами a и b – элементами поля GF(2m). При управляющем сигнале S1 = 1, мультиплексор подключает свои выходы к выходам ПЗУ с таблицей степеней, на вход которого, в свою очередь, поступает результат сложения (при управляющем сигнале S0 = 0) или вычитания (при S0 = 1) по модулю 2m – 1 логарифмов, извлекаемых из ПЗУ с таблицей логарифмов, одновременно по двум независимым шинам для обоих входных операндов a и b – элементов поля GF(2m).

Таким образом, при S1 = 0, и S0 = 0 или S0 = 1, выполняется операция сложения (вычитания) элементов поля путем одной и той же операции «побитового» XOR. При S1 = 1 и S0 = 0 выполняется операция умножения, а при S1 = 1 и S0 = 1 выполняется деление. Отметим также, что в схеме присутствует логическая схема, проверяющая равенство второго операнда b нулю, и при b = 0 в случае выбора операции деления, формируется специальный выходной сигнал ошибки деления на нуль – «divide by zero error». Управляющий вход CS (chip select) служит для активизации выходов микросхем ПЗУ и мультиплексора.

Заключение

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

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