Параллельное устройство для умножения в конечных полях Советский патент 1988 года по МПК G06F7/49 

со

00

со

00 00

сх

Изобретение относится к вьтисли- тельной технике и может быть использовано для построения спецвычислителей произв-едения в конечных полях. Цель изобретения - расширение области применения за счет возможности умножения элементов поля Галуа GF (Р ), представленных в нормальном базисе,

На фиг.1 представлена структурная схема параллельного устройства для умножения в конечных полях; на фиг.2- структурная с-хема блока умножения на примитивный элемент.

Устройство содержит п регистров 1 п блоков 2 умножения на примитивный элемент, п блоков 3 формирования частичных произведений, каждый из которых содержит п умножителей 4, и п блоков 5 суммирования, причем каждый блок 5 сут мирования содержит п входных шин, каждая из которых содержит Р- цепей, п входных шин первой группы первого блока 2 умножения -на примитивный элемент соединены соответственно с первой группой информацион- ньк входов устройства, а п входных шин первой группы каждого блока 2 умножения на примитивный элемент, начиная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд в сторону старших разрядов, группы с второй по (п+1)-ю входных шин п блоков 2 умножения на примитивный элемент соединены соответственно СП выходами каждого из п регистров 1, каждый информационный вход второй группы устройства соединен с первыми входами п умножителей 4 соответствующего блока 3 формирования частичных произведений, вторые входы которых соединены с выходами соответствующих блоков 2 умножения на примитивный элемент, i-й выход j-ro блока 3 формирования частичных произведений соединен с j-M входом k-ro блока 5 суммирования (,,..,n; j 1,.. .,n; k i+j-1 при i+j n+l; k i4-j-n-l, при ), выходные шины блоков 5 суммирования являются вьгходом параллельного устройства для y шoжeния в конечных полях.

Блок 2 умножения на примитивный элемент содержит п групп по п элементов И 6 и п сумматоров 7 по модулю Р, причем каждая из входных шин первой группы блока 2 соединена с пер

выми входами п элементов И 6 соответствующей группы, вторые входы которых являются группами входных шин от второй до (п+1)-й блока 2, выход i- го элемента И 6 j-й группы (i

1,.,.,п; ) соединен с j-M

входом k-ro сумматора 7 по модулю Р (, при i+j k i+j-n-l, при i+j п+1), выходы сумматора 7 по модулю Р являются выходами блока 2 умножения на примитивный элемент.

Устройство работает по следующему алгоритму.

Множимое и множитель обозначаются

п-1 ; - а;х и В(х) Е Ь; х ; оi O

Р

(1)

20

где Р - характеристика;

п - степ ень расширения поля. Тогда произведение имеет вид

А(х)В(х) (х) ; о

0

«-

(х)р- } ; 0

р (2)

Произведение хВ(х) может быть

0

5

0

5

0

(3)

представлено в виде

1п-1 .

21Ь;Х -.

в регистрах 1 .записаны произведения базисных элементов на примитив- ньй элемент, т.е. элементы х (,1,...,п-1), выходы которых соединены с j-й группой входов блоков 2 умножения, куда подается величина

X . Содержимое регистров меняется при смене представления элементов поля. Компоненты элементов поля, поступающие на первую группу входов блока 2 умножения, умножаются на элементах И 6 на х , в результате чего получают члены произведения (3), которые суммируются в сумматорах 7 и в соответствии с (3) на выходе блока 2 формируются произведения, поступающие на вход элемента на элемен-

На первую группу входов параллельного устройства подается множитель А(х), а на вторую - множитель В(х). В связи с приведенным сначала по первой группе входов на первый блок 2 подана величина В(х), на второй блок

2- вСх) , а на п-й блок 2 .. . р-(г.-1)

LB(x)j . На выходе первого блока 2 формируется Х В (х), на выходе второго блока 2 - (х) , на выхо- де п-го блока 2 - X в(х) В блоках 3 формирования частичных произведений полученные величины умно- жают на соответствующие разряды множителя А (х) . Полученные произведения с выхода схем умножения блоков формирования частичных произведений подаются на блоки 5 суммирования.

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

Формула изобретения

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

j

5

0

5 0 0

устройства, а п входных шин первой группы каждого блока умножения на примитивный элемент, начиная с второго, соединены с первой группой информационных входов устройства с циклическим сдвигом на один разряд в сторону старших разрядов, группы с второй по (п+1)-ную входных шин п блоков умножения на примитивный элемент соединены соответственно с п выходами каждого из п регистров, каждый информационный вход второй группы устройства соединен с первыми входами п умножителей соответствующего блока формирования частичных произведений, вторые входы которых соединены с выходами соответствующих блоков умножения на примитивный элемент, i-й выход j-ro блока формирования частичных произведений соединен с J-M входом k-ro блока суммирования (,...,n; ,...,n; k i+j-1 при i+j n+I; k i+j-n-l при i+j n+1).

2. Устройство по П.1, отличающееся тем, что блок умножения на примитивный элемент, содержащий п групп по п элементов И и п сумматоров по модулю Р, причем каждая из входных шин первой группы, блока соединена с первыми входами п элементов И соответствующей группы, вторые входы которых являются груп- входных шин от второй до (п+1)-й блока, выход i-ro элемента И j-й группы (,...,,...,п) соединен с J-M входом k-ro сумматора по модулю Р (k i+j-l при k i+j-n-l при i+j п+1), выходы сумматоров по модулю Р являются выходами блока.

Изобретение относится к вычислительной технике и может быть использовано для построения спецвычислителей произведения в конечых полях. Цель изобретения - расширение облас ти применения за счет возможности умножения элементов поля Галуа GF(P ), представленньк в нормальном базисе. Предложенное устройство содержит п регистров 1, п блоков 2 умножения на примитивный элемент, п блоков 3 формирования частичных произведений, каждый из которых содержит п умножителей 4, и п блоков 5 суммирования с соответствующими связями. Блок 2 умножения на примитивный элемент содержит п групп по п элементов И и п сумматоров по модулю Р с соответствующими связями. Устройство производит умножение элементов поля Галуа GF (Р ), представленных в нормальном базисе. 1 з.п. ф-лы, 2 ил. с В (Л