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

ISSN 1996-3955
ИФ РИНЦ = 0,570

АРИФМЕТИКА ДВОИЧНОГО ПОЛЯ ГАЛУА НА БАЗЕ БЫСТРОГО УМНОЖЕНИЯ И ИНВЕРТИРОВАНИЯ ЭЛЕМЕНТОВ ПОЛЯ И ЕЕ АППАРАТНАЯ РЕАЛИЗАЦИЯ

Рахман П.А. 1
1 ФГБОУ ВПО «Уфимский государственный нефтяной технический университет» филиал в г. Стерлитамаке
В данной статье рассматриваются поля Галуа GF(2m) характеристики 2 и их арифметика. Рассматриваются операции сложения и вычитания, операция умножения элементов на базе прямых формул для расчета коэффициентов многочлена-произведения, а также операции деления на базе умножения на мультипликативную инверсию элемента-множителя. Приводится математическое описание и аппаратная реализация схемы быстрого умножения на базе двухвходовых элементов «И» и многовходовых сумматоров по модулю 2. Также приводится схема аппаратной реализации процессора, реализующего арифметические операции в поле Галуа на базе сумматоров по модулю 2, постоянного запоминающего устройства для хранения мультипликативных инверсий элементов, мультиплексора и схемы быстрого умножения элементов.
поле Галуа
быстрое умножение
таблица инверсий
арифметический процессор
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(2m) имеют огромное практическое значение [1]. В частности, важнейшие алгоритмы обнаружения и исправления искажения информации в системах хранения и сетях передачи данных, использующие коды Рида-Соломона, а также криптографические алгоритмы (например, AES – Advanced Encryption Standard), защищающие информацию от несанкционированного доступа, базируются на арифметике конечных полей Галуа GF(2m).

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

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

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

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

rahman07.wmf

rahman08.wmf

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

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

rahman10.wmf (1)

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

rahman11.wmf.

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

rahman12.wmf.

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

rahman14.wmf.

После перемножения многочленов и вычисления остатка по модулю rahman15.wmf в общем виде получаем:

rahman16.wmf

Таким образом, мы имеем m аддитивных функций для вычисления коэффициентов rahman17.wmf. Функции содержат слагаемые в виде произведений коэффициентов ai∙bj, где rahman18.wmf. Поскольку мы имеем дело с полями GF(2m), являющиеся расширением базового простого поля GF(2), то произведение коэффициентов эквивалентно логическому умножению (конъюнкции).

Для аппаратной реализации таких функции удобнее использовать специализированные программируемые логические матрицы (ПЛМ), содержащие в себе логические элементы «И» с двумя входами и многовходовые сумматоры по модулю 2.

Ниже на рис. 1 приведена функциональная схема умножителя элементов поля GF(24), образованного на базе примитивного неприводимого многочлена rahman19.wmf.

Входы сумматоров в соответствии с аддитивными функциями подключаются к выходам логических элементов «И», формирующих соответствующие произведения коэффициентов ai∙bj. Незадействованные входы сумматоров подключаются к «земле».

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

rahman21.wmf (2)

Следует особо отметить, что итерационный вывод прямых формул осуществляется лишь один раз на этапе проектирования аппаратной реализации, и далее формулы аппаратно реализуются в коммутационной матрице соединений между выходами m2 двухвходовых элементов «И» и входы m элементов сумматоров по модулю 2.

Что касается операции деления элемента a на ненулевой элемент b поля, то ее можно свести к операции умножения на обратный элемент b–1.

rahman23.wmf (3)

Вычисление обратного элемента по умножению для максимального быстродействия, очевидно, лучше всего опять же осуществлять табличным способом, используя ПЗУ емкостью 2mm бит. Что касается формирования самой таблицы обратных элементов на этапе проектирования, то ее можно подготовить заранее, используя расширенный алгоритм Евклида для многочленов, который сводит решение уравнения

rahman24.wmf,

где b–1(x) разыскиваемый обратный многочлен по умножению, к нахождению многочленов g(x) и h(x), а также наибольшего общего делителя rahman25a.wmf для многочленов b(x) и p(x) таких, что

rahman26a.wmf.

Поскольку мы имеем дело с полем, то для любого ненулевого многочлена rahman27.wmf алгоритм в качестве rahman28a.wmf дает скаляр rahman29.wmf (многочлен нулевой степени), и в нашем «двоичном» случае скаляр будет равен строго λ = 1, так как в базовом простом поле GF(2) существует только один ненулевой элемент – это единица. Соответственно, многочлен g(x), находимый алгоритмом, и является искомым обратным многочленом по умножению, то есть rahman30.wmf.

Приведем для примера таблицу обратных элементов для элементов поля GF(24), представленных для компактности в виде десятичных и двоичных эквивалентов элементов.

rahman31.wmf

 

rahmanP1a.wmf

Рис. 1. Функциональная схема умножителя элементов поля Галуа GF(24) на базе специализированной логической матрицы

Арифметический процессор для поля Галуа GF(2m) на базе быстрого умножения и инвертирования элементов. Используя умножитель элементов поля Галуа GF(2m) на базе специализированной программируемой логической матрицы теперь можно построить арифметический процессор для поля Галуа GF(2m), сведя операцию деления элемента a на ненулевой элемент b поля к умножению на обратный элемент b–1 по умножению. Вычисление обратного элемента по умножению для максимального быстродействия, очевидно, лучше осуществлять табличным способом, используя ПЗУ емкостью 2mm бит.

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

rahmanP2a.wmf

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

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

Арифметический процессор на базе умножителя и таблицы обратных элементов требует одного ПЗУ емкостью 2mm бит, и умножителя, состоящего из m2 двухвходовых логических элементов «И», m многовходовых сумматоров по модулю 2, и коммутационной матрицы размером rahman34.wmf. Если коммутационную матрицу тоже рассматривать как «постоянную память», то, очевидно, что ее размер составляет m5.

Заключение

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

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


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

Рахман П.А. АРИФМЕТИКА ДВОИЧНОГО ПОЛЯ ГАЛУА НА БАЗЕ БЫСТРОГО УМНОЖЕНИЯ И ИНВЕРТИРОВАНИЯ ЭЛЕМЕНТОВ ПОЛЯ И ЕЕ АППАРАТНАЯ РЕАЛИЗАЦИЯ // Международный журнал прикладных и фундаментальных исследований. – 2015. – № 12-3. – С. 403-408;
URL: http://applied-research.ru/ru/article/view?id=7942 (дата обращения: 17.10.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074