Параллельно-последовательное устройство для умножения в конечных полях

 

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

СОЮ3 СОВЕТСКИХ

СОВЯЛИСТИЧЕСКИХ

РЕСПУБЛИК ш 4 G 06 F 7 49

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4058749/24-24 (22) 24.04.86 (46) 30.05.88. Бюл. У 20 (71) Институт проблем передачи информации АН СССР и Пензенский политехнический институт (72) В. А. Зиновьев, В. В. Зяблов, Б. А. Савельев (SU), Валентина Маркова Георгиева, Стефан Манев Додунеков, Николай Лазаров Манев, Петер

Атанасов Попов и Владимир Борисов

Стойнов (BG) (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 824202,, кл. G 06 Р 7/49, 1981.

Авторское свидетельство СССР

Р 900281, кл. G 06 F 7/49, 1982.

„„SU„„ i 399725 М (54) ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНОЕ

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ

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

Устройство производит умножение полиномов, коэффициенты которых представлены в нормальном базисе. 1 з.п. ф-лы, 2 ил.

B(x>

1399725

Тогда произведение (а х(в(х)) (2 )

)) -

+b;X

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

Галуа GF (Р ) .

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

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

Устройство содержит регистр l сдвига множителях регистр 2 сдвига ножимого, блок 3 умножения на прими( ивный элемент, блок 4 формирования частичных произведений, состоящий з п схем 5 умножения, блок б суммирования, состоящий из п суммато! ров 7, и регистр 8 произведения, причтем информационные входы первой группЫ устройства соединены соответственно с информационными входами регистра 1 сдвига множителя, выход которо.го соединен с первыми входами схем

5 умножения блока 4 формирования частичных произведений, информационные входы второй группы устройства соединены соответственно с информа ионными входами регистра 2 сдвига м ожимого, и-й выходной разряд котор го соединен с его входом последов тельного ввода информации и с перв м входом блока 3 умножения на прим активный элемент, входы с второго по п и которого соединены с выходами с ответственно с первого по (n-1)-й регистра 2 сдвига множимого, разряднЬ|е выходы блока 3 умножения на примитивный элемент соединены соответственно с вторыми входами схем 5 ум" ножения блока 4 формирования частичных произведений, первые входы суммагоров 7 блока 6. суммирования соеди! иены соответственно с выходами блока

4 формирования частичных произведений, выходы сумматоров 7 соединены соответственно с информационными вход<ами регистра 8, разрядные выходы которого соединены с вторыми входамй сумматоров 7 блока 6 суммирования с циклическим сдвигом на один разряд в сторону младших разрядов и являются выходами устройства.

Блок 3 умножения на примитивный элемент содержит и регистров 9, и групп по и элементов И 10 в каждой и и сумматоров 11 по модулю Р, причем каждый из и входов блока 3 соединен с первыми входами элементов И 10 соответствующей группы, вторые входы которых соединены соответственно с разрядными выходами соответствующих регистров 9, выход i-ro элемента

И 10 1"й группы (i=1,...,n; j =1,...n)

10 соединен с j"ì входом К-ro сумматора !

1 по модулю P (К = I+j-1 при i+j

« п+1; К = i+j -n-1 при i+j > и+1), выходы сумматоров 11 по модулю P являются выходами блока 3 умножения

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

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

20 А(Х)=, а Х и В(Х)=, Ь Х, (1)

<=0 =о

))-<

А(х)В(х) = 0 (а;х (В(х)Я = =о

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

35 + а, Х (В (Х)) . (3)

Произведение Х1В(X}) может быть представлено в виде

В регистрах 9 блока 3 умножения на примитивный элемент записаны произведения базисных элементов на прир!4-1 митивный элемент, т.е. элементы Х (i = 0,1,..., n-1) . Содержимое регистров меняется при смене конечного поля. Компоненты элементов поля, подаваемые на вход блока 3, умножают на элементах И 10 на Х ", в результате чего формируются члены выражения (4), которые суммируются в сумматорах 11, и в соответствии с (4) на выходе блока 3 формируются произведения поступающего на вход элемента

В ", на примитивный элемент.

Множитель и множимое 3 lïèñûâàþò,1 ся соответственно в регистры 1 и 2, Зти per истры представ!!яют с <)бой cga H2:

4 информационными входами регис,pa

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

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

13997 говые регистры, в каждом разряде которых параллельно включено P-1 тр-..-.-,— геров D-типа. При этом íà D-вход подаются информационные разряды, а

5 на С-входы — тактовые импульсы для сдвига или стробирующие импульсы для параллельной записи А(Х) или В(Х) на регистр сдвига.

Вначале с выхода регистра 2 множи" 10 мого на вход блока 3 умножения на примитивный элемент поступает число

-(n->)

В(X)1 и на его выходе формирует(тз-t) ся произведение X(B(X)), которое умножают на старший разряд множителя в схеме 5 умножения.

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

1 разряд, При этом на первые входы сумматоров 7 подается величина а Х(Б(Х))Р, полученная на выходе регистра 8, на вторые входы 25 подается а Х(В(Х)) и в регистр 8 пройзведения записывается („х (a)

+ а Х(В(Х))

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

2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок умножения на примитивный элемент содержит и регистров, и групп по п элементов И и и сумматоров по модулю P причем каждый из и входов блока соединен с первыми входами элементов И соответствующей группы, вторые входы которых соединены соответственно с разрядными выходами соответствующих регистров, выход i-го элемента

И j -й группы (i = 1,...,и, j=1,...,n) соединен с j-м входом К-го сумматора по модулю p(K = i+j — 1 при +1 оп+1;

К = i+j-и-1 при i+j ) и+1), выходы сумматоров по модулю P являются выходами блока.

1399725

° е à ° И

Составитель В. Гусев

Техред Л.Сердюкова Корректор А. Обручар

Редактор A. Orap

Эаказ 2666/48 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

133035, Москва, iK"35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4