Научный журнал

Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955

ИФ РИНЦ = 0,593

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Рахман П.А. 1

---

1 ФГБОУ ВПО «Уфимский государственный нефтяной технический университет» филиал в г. Стерлитамаке

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

Статья в формате PDF

1589 KB

поле Галуа

логарифмы

примитивный элемент

арифметический процессор

1. Todd K. Moon. Error correcting coding: mathematical methods and algorithms. – Hoboken, New Jersey: John Wiley & Sons Inc., 2005.

2. Рахман П.А., Григорьева Т.В. Кодирование информации с применением кодов Рида-Соломона. – Уфа: Изд-во УГНТУ, 2015.

3. Рахман П.А., Шарипов М.И. Модель надежности двухузлового кластера приложений высокой готовности в системах управления предприятием // Экономика и менеджмент систем управления. – 2015. Т. 17. № 3. – С. 85–102.

4. Рахман П.А., Шарипов М.И. Модели надежности каскадных дисковых массивов в системах управления предприятием // Экономика и менеджмент систем управления. – 2015. – Т. 17. № 3.1. – С. 155–168.

5. Рахман П.А. Коэффициент готовности трехуровневых локальных сетей передачи данных // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 9–3. – С. 463–466.

6. Рахман П.А. Показатели надежности восстанавливаемых систем с заданным порогом аварийного отключения // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 9–3. – С. 467–470.

7. Рахман П.А. Среднее время до потери данных двухдискового массива // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 9–4. – С. 603–607.

8. Рахман П.А. Коэффициент готовности системы обработки данных с основным и резервным узлами // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 9–4. – С. 608–611.

9. Рахман П.А. Модель надежности мажоритарной вычислительной системы на базе элементов с тремя состояниями // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 10–1. – С. 33–37.

10. Рахман П.А. Алгоритм выбора кратности исправляемых искажений для кодирования информации с применением кодов Рида-Соломона // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 10–2. – С. 208–212.

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

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

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

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

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

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

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

(1)

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

.

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

(2)

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

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

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

.

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

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

.

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

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

.

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

.

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

.

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

.

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

,

а ,

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

,

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

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

.

Также заметим, что это не что иное, как «побитовая» инверсия разрядов 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(2^m) на базе схемы сложения и вычитания логарифмов. Теперь располагая узлом сложения / вычитания по модулю 2^m – 1, и добавив к нему двухпортовое ПЗУ с таблицей логарифмов, а также ПЗУ с таблицей степеней, и некоторые вспомогательные узлы, можем рассмотреть арифметический процессор, выполняющий четыре основные операции с элементами поля Галуа GF(2^m). Суммарная емкость двух ПЗУ составляет бит.

Библиографическая ссылка