Результат интеллектуальной деятельности: Способ умножения и деления элементов конечных полей

Изобретение относится к области вычислительной техники и может быть использовано при создании специализированных вычислителей для кодирования и декодирования информации, защищенной помехоустойчивым кодом.

Одним из основных путей повышения помехоустойчивости передачи сообщений по каналам связи с ошибками является применение помехоустойчивого кодирования. Для кодирования и декодирования алгебраических помехоустойчивых кодов Боуза-Чоудхури-Хоквинхема (БЧХ-коды), Рида-Соломона, Гоппы и других необходимо выполнение арифметических операций с элементами конечных полей. Структура конечных полей отличается от структуры обычных бесконечных числовых полей, таких как поля рациональных, действительных и комплексных чисел. Выполнение умножения и деления элементов конечных полей отличается от умножения и деления обычных чисел и часто вызывает затруднения. Для умножения и деления элементов конечных полей, особенно при большой их разрядности, требуется выполнение большого числа команд и наличие большого объема памяти для хранения таблиц логарифмов и антилогарифмов (таблиц индексов и антииндексов). Предлагаемый способ основан на использовании аддитивной и мультипликативной формы представления элементов конечных полей в виде соответственно суммы и произведения элементов подполей. Умножение и деление элементов конечных полей выполняется для мультипликативной формы их представления и сводится к умножению и делению элементов подполей, что и позволяет уменьшить сложность способа. При этом уменьшается объем памяти, требуемой для умножения и деления элементов конечных полей, и тем самым сокращаются необходимые вычислительные ресурсы. Способ может использоваться в расширениях конечных полей, содержащих подполя, например в полях Галуа GF(2^2m), и других, число элементов в которых разлагается на простые множители.

Известен способ умножения и деления элементов конечных полей, при котором для умножения элементов конечных полей сначала оба сомножителя представляют в виде полиномов с двоичными коэффициентами, затем вычисляют произведение этих двух полиномов и определяют остаток от деления произведения на порождающий полином поля, для деления элементов конечных полей сначала по таблице обратных элементов конечного поля находят обратный элемент делителя, а затем умножают делимое на этот обратный элемент [Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования. Пер. с японского А.В. Кузнецова. - М.: - Мир. - 1978. - с. 72-78].

Недостатком этого способа является его большая сложность из-за большого числа команд, необходимых для вычисления произведения полиномов и остатка от деления произведения на порождающий многочлен конечного поля, а также большой объем памяти для хранения таблицы обратного элемента конечного поля.

Наиболее близким к предлагаемому способу является способ (прототип) умножения и деления элементов конечных полей, заключающийся в том, что при умножении элементов конечных полей сначала по таблицам индексов конечного поля находят индексы сомножителей, затем складывают эти индексы по модулю n-1, где n - число элементов в конечном поле, и по таблице антииндексов находят произведение. При делении элементов конечных полей сначала по таблицам индексов конечного поля находят индексы делимого и делителя, затем вычитают из индекса делимого индекс делителя, приводят по модулю n-1 и по таблице антииндексов находят частное (Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. - Пер с англ. Грушко И.И. и Зиновьева Б.А. - М.: Мир. - 1979. - с. 95-98).

Недостатком этого способа является большая сложность из-за большого объема памяти для хранения таблиц индексов и антииндексов элементов конечного поля.

Целью изобретения является уменьшение сложности способа за счет использования мультипликативной формы представления элементов конечного поля через элементы подполей, что сокращает объем памяти для хранения табличных функций по сравнению с объемом памяти для хранения таблиц индексов и антииндексов элементов конечного поля.

Для достижения цели предложен способ умножения и деления элементов конечных полей, заключающийся в том, что при умножении элементов конечных полей сначала по таблицам индексов конечного поля находят индексы сомножителей, затем складывают эти индексы по модулю n-1, где n - число элементов в конечном поле, и по таблице антииндексов находят произведение. При делении элементов конечных полей сначала по таблицам индексов конечного поля находят индексы делимого и делителя, затем вычитают из индекса делимого индекс делителя, приводят по модулю n-1 и по таблице антииндексов находят частное. Новым является то, что сначала элементы конечных полей из аддитивной формы представления с помощью таблично заданных функций переводят в мультипликативную форму представления через элементы подполей, по таблицам индексов подполей находят индексы элементов подполей, выполняют умножение и деление элементов конечных полей через индексы подполей, а затем переводят с помощью таблично заданных функций произведение и частное из мультипликативной формы представления элементов конечных полей в аддитивную форму представления. При этом таблично заданные функции преобразования элементов конечных полей из аддитивной формы представления в мультипликативную форму представления и обратно вычисляют заранее и хранят в памяти. Причем таблицы индексов и антииндексов элементов подполей вычисляют заранее и хранят в памяти. При этом таблично заданные функции преобразования элементов конечных полей из аддитивной формы представления в мультипликативную форму и обратно вычисляют путем перебора всех элементов конечных полей и вычислений с использованием таблиц индексов и антииндексов элементов конечных полей.

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

Элементы поля с е GF(2^2m) обычно представляют в аддитивной форме

где d, g∈EGF(2^m),

α - примитивный элемент GF(2^2m).

При таком представлении несложно выполнять сложение и вычитание элементов поля. Допустим c₁=d₁+αg₁ и c₂=d₂+αg₂, тогда сложение элементов поля запишется

Сложение элементов поля сводится к более простому сложению элементов подполя. Аналогично для вычитания элементов поля.

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

где а - элемент подполя GF(2^m) поля GF(2^2m), а∈GF(2^m)⊂GF(2^2m),

α - примитивный элемент GF(2^2m),

b - множество индексов элементов поля, b=0…2^m, ∞, α^∞=0, операции с индексами поля GF(2^m) проводят по модулю 2^m-1. Индекса нулевого элемента поля не существует, поэтому для него используют условное обозначение ∞.

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

Задание d и g однозначно определяет a и b. Разделим обе части на d и преобразуем (5) к виду

где , а, d≠0.

В силу единственности (6)

где r₁(h) - функция: GF(2^m)→GF(2^m),

a r₂(h) - функция: GF(2^m)→{0…2^m, ∞}.

Функции r₁(h) и r₂(h) можно определить заранее и хранить в табличном виде. Тогда

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

Умножение и деление элементов поля выполняют через индексы элементов подполя i₁ и i₂ в соответствии с формулами

где - примитивный элемент поля GF(2^m),

Сложение и вычитание индексов элементов поля и подполя выполняется с приведение по модулю числа элементов соответственно в поле или подполе минус 1.

Затем переводят произведение и частное из мультипликативной формы представления элементов конечных полей в аддитивную форму представления. Такой перевод выражается в виде

Или можно записать

где и , а≠0.

Из единственности (12) следует

где функции и : {0…2^m, ∞}→GF(2^m).

Тогда

Функции и можно определить заранее и хранить в табличном виде.

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

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

Табличное задание функций , , r₁ (x), r₂ (x) может выполняться заранее, и, поэтому не критично к числу операций и объему памяти. Например, составление таблиц этих функций можно выполнять заранее перебором элементов поля GF(2^2m) и используя таблицы индексов и антииндексов для элементов поля GF(2^2m).

Для определения таблиц функций и необходимо выполнение следующих шагов.

Шаг 1. Положим , ,

, ,

Шаг 2. Положим b=2, a=1,

Шаг 3. Положим g₁=1

Шаг 4. Положим d₁=1

Шаг 5. Проверить d₁+αg₁=aα^b, если выполняется, идти к 7

Шаг 6. Если , идти к 8, иначе d₁:=βd₁, идти к 5

Шаг 7. , , идти к 9

Шаг 8. g₁:=βg₁ идти к 4

Шаг 9. Если b=2^m-2, идти к 10, иначе b:=b+1, идти к 3

Шаг 10. Конец

Таблицы функций r₁(x) и r₂(x) составляют аналогичным образом.

Пример.

Поле GF(2⁴) с порождающим полиномом g(x)=x⁴+x+1

Подполе GF(2²) с порождающим полиномом g(x)=x²+х+1

Элементы поля GF(2⁴), являющиеся элементами подполя GF(2²)

0, α°=β°=l, α⁵=β=α+α², α¹⁰=β²=1+α+α²

Умножение элементов поля GF(2⁴).

Пусть элементы поля заданы в форме (2)

c₁=α¹⁰+αα⁵, а c₂=α⁵+αα¹⁰.

Шаг 1. Перевод элементов поля из формы (2) в форму (1)

c₁=α¹⁰+αα⁵, а=α¹⁰r₁(α¹⁰)=α⁵, b=r₂(α¹⁰)=2, c₁=α⁵α²

c₂=α⁵+αα¹⁰, а=α⁵r₁(α⁵)=1, b=r₂(α⁵)=3, c₂=1α³

Шаг 2. Умножение элементов поля

c=c₁c₂=-α⁵α²1α³=α¹⁰α⁰

Шаг 3. Перевод произведения в форму (2)

Деление элементов поля GF(2⁴).

Пусть элементы поля заданы в форме (2)

c₁=α¹⁰+αα⁰, а c₂=α⁵+αα⁵.

Шаг 1. Перевод элементов поля из формы (2) в форму (1)

c₁=α¹⁰+αα⁰, а=α¹⁰r₁(α⁵)=α⁵, b=r₂(α⁵)=3, c₁=α⁵α³

c₂=α⁵+αα⁵, а=α⁵r₁(1)=α⁵, b=r₂(1)=4, c₂=α⁵α⁴

Шаг 2. Деление элементов поля

Шаг 3. Перевод частного в форму (2)

Предложенный способ может быть использован не только в расширениях полей Галуа GF(2^2m) характеристики 2, но и в других расширениях конечных полей с характеристикой, отличной от 2, которые могут быть разложены на подполя. Многие важные технические приложения, например кодирование и декодирование помехоустойчивых кодов, могут быть реализованы только при сокращении памяти для хранения табличных функций, с помощью которых выполняют умножение и деление элементов конечных полей. Для небольших значений разрядности элементов конечного поля m умножение и деление можно выполнять с использованием таблиц индексов и антииндексов. Однако для больших m(≥8) возникают затруднения из-за возрастания объема таблиц индексов и антииндексов. Предложенный способ требует для своей реализации меньшего объема памяти и упрощает умножение и деление элементов поля Галуа GF(2^2m). Объем памяти для хранения таблиц индексов и антииндексов оценивается величиной O (2^2m), а для предложенного способа объем памяти для хранения табличных функций - величиной O(2^m). Например, при m=8 объем памяти для хранения таблиц индексов и антииндексов равен 262144 байта, а для предложенного способа требуемый объем памяти - всего 1540 байт. Причем с увеличением m преимущество предложенного способа возрастает по экспоненте, то есть очень быстро.

Достигаемым техническим результатом способа умножения и деления элементов конечных полей является уменьшение объема памяти для реализации способа и его упрощение.