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

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

ISSN 1996-3955

ИФ РИНЦ = 0,593

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

Рахман П.А. 1

---

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

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

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

1525 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(2^m).

Однако для эффективной программной и аппаратной реализации алгоритмов, также необходима быстродействующая аппаратная реализация арифметики поля Галуа 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(2^m) мы имеем сложение соответствующих коэффициентов многочленов по модулю 2 (при представлении в виде многочленов) или побитовое сложение по модулю 2 соответствующих разрядов двоичных чисел (при представлении в виде двоичных чисел):

(1)

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

.

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

.

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

.

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

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

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

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

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

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

(2)

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

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

(3)

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

,

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

.

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

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

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

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