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

f

I-J

i i 1 Ч

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

Цель изобретения - упрощение устройства.

На фиг, 1 представлена функциональная схема параллельно-последова- . т ельного устройства для умножения в конечных полях; на фиг. 2 - функциональная схема блока умножения на при- м1итивный элемент. Устройство содержит регистр с|двига множителя, регистр 2 сдвига м1ножимого, блок 3 умножения на примитивный элемент, блок 4 формирования частичных произведений, состоящий ф п схем 5 умножения, блок. 6 суммирования, состоящий из п сумматоров .7, и регистр 8 произведения, при- ч|ем информационные входы первой груп- пЦ устройства соединены соответственно с информационными входами регист- pja 1 сдвига множителя, выход которЬ- го соединен с первыми входами схем 5: умножения блока 4 формирования частичных произведений, информационные входы второй группы устройства сЬединены соответственно с информационными входами регистра 2 сдвига множимого, п-й выходной разряд которого соединен с его входом последовательного ввода информации и с пер- BbiM входом блока 3 умножения на примитивный элемент, входы с второго по п-й которого соединены с выходами соответственно с первого по (п-1)-й регистра 2 сдвига множимого, разряд- иМе выходы блока 3 умножения на при- м;итивный элемент соединены соответ- с венно с вторыми входами.схем 5 ум- н ржении блока 4 формирования частичных произведений, первые входы сумматоров 7 блока 6-суммирования соеди- соответственно с выходами блока fy формирования частичных произведе- НИИ, выходы сумматоров 7 соединены соответственно с информационными вхо- д1ами регистра 8, разрядные выходы которого соединены с вторыми входа- Miii сумматоров 7 блока 6 суммирования с циклическим сдвигом на один разряд в сторону младших разрядов и явля- ю;тся выходами устройства.

Блок 3 умножения на пpимит шный эпемент содержит п регистров 9, п г рупп по п элементов И 10 в каждой и п

сумматоров 1I по модулю Р, причем каждый из п входов блока 3 соединен с первыми входами элементов И 0 соответствующей группы, вторые входы которых соединены соответственно с разрядными выходами соответствующих регистров 9, выход i-ro элемента И 10 j-й группы (i-l,...,n; j,...п)

соединен с j-м входом К-го сумматора 11 по модулю Р (К 1+j-l при i+j и п+1; К 1+j-п-1 при i+j п+1), выходы сумматоров 11 по модулю Р являются выходами блока 3 умножения

на примитивньй элемент.

Принцип работы устройства основан на следующем. Множитель А(Х) и множимое В(Х) можно представить в виде

Р IJ Р

А(Х)51а-,Х иВ(Х) Ь;Х. (1)

1

Тогда произведение n-i

А(Х)В(Х) |l/a;X B(X) - -

n-i РpiiP

(X)J i-o L

(2Г

которое .можно представить в виде

,-(-ПТР + Р

Ггг-nP V

...fa,.,(X) J .а„.,Х-1в(Х) . ...у.

35 + (Х).. (3)

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

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

п-1

.Ь;Х

p fi

(Д)

Б регистрах 9 блока 3 умножения на примитивный элемент записаны произведения базисных элементов на при, митивныи элемент, т.е. элементы Х

(i 0,1,..., п-1). Содержимое регистров меняется при смене конечного поля. Компоненты элементов поля, подаваемые на вход блока 3, умножают

на элементах И 10 на , в результате чего формируются члены выражения (4), которые суммируются в сумматорах 11, и в соответствии с (4) на выкоде блока 3 формируются произведения поступающего на вход элемента В- на примитивный элемент.

Множитель и множимое записываются соответственно в регистры 1 и 2. Эти регистры представляют собой сдви 1

говые регистры, в каждом разряде которых параллельно включено Р-1 трнг геров D-типа. При этом на D-вход подаются информационные разряды, а .на С-входы - тактовые импульсы для сдвига или стробирующие импульсы для параллельной записи А(Х) или В(Х) на регистр сдвига.

Вначале с выхода регистра 2 множи мого на вход блока 3 умножения на примитивный элемент поступает число В(Х)Р и на его выходе формируется произведение (Х) , которое умножают на старший разряд мно- жителя в схеме 5 умножения.

Результат умножения на старший разряд а ) через сумматоры 7 поступает в регистр 8 произведения, В следующем такте содержи- мое регистров 1 и 2 сдвигается на 1 разряд. При этом на первые входы сумматоров 7 подается величина а (Х) , полученная на выходе регистра 8, на вторые входы подается а (Х) ив регистр 8 произведения записывается р-(-ч ) Р

+ а

a.,(X,;- - J ..

Процесс продолжается аналогично до п-го такта, при котором содержимое регистра 8 произведения, соответствующее (3) и приведенное по модулю Р, выдается на выход устрой- ртва.

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

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

5

0 5

0

5

0 5 0

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

I

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

Т

Ф

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

.2