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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

При таком представлении несложно выполнять сложение и вычитание элементов поля. Допустим c1=d1+αg1 и c2=d2+αg2, тогда сложение элементов поля запишется

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

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

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

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

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

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

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

где , а, d≠0.

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

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

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

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

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

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

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

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

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

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

где и , а≠0.

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

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

Тогда

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

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

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

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

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

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

, ,

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

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

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

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

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

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

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

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

Шаг 10. Конец

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

Пример.

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

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

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

0, α°=β°=l, α5=β=α+α2, α102=1+α+α2

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

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

c110+αα5, а c25+αα10.

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

c110+αα5, а10r110)=α5, b=r210)=2, c15α2

c25+αα10, а5r15)=1, b=r25)=3, c2=1α3

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

c=c1c2=-α5α2310α0

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

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

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

c110+αα0, а c25+αα5.

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

c110+αα0, а10r15)=α5, b=r25)=3, c15α3

c25+αα5, а5r1(1)=α5, b=r2(1)=4, c25α4

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

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

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

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

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

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

3. Способ по п. 1, отличающийся тем, что таблицы индексов и антииндексов элементов подполей вычисляют заранее и хранят в памяти.

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



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

Изобретение относится к технике связи. Технический результат - повышение скорости передачи и помехоустойчивости.

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

Изобретение относится к области радиосвязи. Технический результат - повышение скорости передачи данных за счет оценки вероятности ошибки на бит при кодировании с помощью линейного блока помехоустойчивого кода. Способ оценки вероятности ошибки на бит, при котором источник сообщений формирует последовательность бит и передает ее на вход кодера, в котором с помощью линейного блокового кода кодируют последовательность, получая кодовое слово длиной n бит, а с выхода кодовое слово передают на вход модулятора, в котором осуществляют модуляцию и получают информационный сигнал, передают сигнал в канал связи, а с выхода канала связи передают сигнал на вход демодулятора, в котором получают принятую кодовую комбинацию, которая может содержать ошибки из-за наличия искажений в канале связи, передают кодовую комбинацию на вход декодера, в котором декодируют комбинацию и получают информационное слово, а также число q обнаруженных ошибок и с первого выхода декодера передают информационное слово на вход получателя сообщений, а со второго выхода декодера передают число q, равное количеству обнаруженных декодером ошибок в полученном кодовом слове, на вход блока проверки. 1 ил.

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

Наверх