Параллельное устройство для умножения в поле Галуа GF (2 @ ) Советский патент 1989 года по МПК G06F7/49 

со со оо

00

25

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

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

На фиг.1 представлена структурная схема параллельного устройства для 10 умножения в поле Галуа GF (2); на фигс 2 и 3 - функциональная схема параллельного устройства для умножения в поле Галуа GF (2).варианты

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

Параллельное устройство для умножения в поле Галуа GF (2) элементов, представленных в нормальном базисе с помощью полинома g(x) +х +1, содержит восемь блоков 1-1, 1-2,..., 1-8 ключей, в каждый из которых входит по восемь элементов И 2-1,2-2, .о.,2-8, причем каждая входная цепь множимого А(х) соединена соответственно с первыми входами элементов И блоков 1-1, 1-2,...,1-8 ключей, и восемь групп 3-1,3-2,„..,3-8 сумматоров по модулю два, при этом вы- 35 ходы 4,5,...,67 элементов И блоков 1-1, 1-2,...,1-8 ключей соединены с входами сумматоров групп 3-1,3-2,..., 3-3 следующим образом: входы сумматора 3-1-1 соединены соответственно 40 с выходами 6,18,19,20,22,30,32,33 и 39 элементов И, входы сумматора 3-1-2 соединены соответственно с выходами 10,17,21,24,38,45,50 и 57 элементов И, входы сумматора 3-2-1 соединены 45 соответственно с выходами 15,27,38, 48,56 и 62 элементов И, входы сумматора 3-3-1 соединены соответственно с выходами 7,24,28,29,38,41,50,51 и 57 элементов И, входы сумматора 50 3-5-1 соединены соответственно с выходами 11,19,25,33,42,46,47,56 и 59 элементов И, входы сумматора 3-7-2 соединены соответственно с выходами 5,10,12,14,15,21,39.,43 и 52 элемен- 55 тон и, входы сумматора 3-7-1 соединены ёоответственно с вьгходами 20, 34,55,60 и 65 элементов И, входы сумматора 3-1-3 соединены соответствен5

0

5 -

5 0 5 0 5

но с выходами 9,14,34,44,47,53,55,6 и 67 элементов И, и с выходами 68 и 69 сумматоров 3-1-1,3-1-2, входы сумматора 3-2-2 соединены соответственно с выходами 4,27,29,41,43,47,53, 54,59,61,64 и 66 элементов И и с выходами 68 и 70 сумматоров 3-1-1, 3-2-1, входы сумматора 3-3-2 соединены соответственно с выходами 6,9,11, 13,20,32,35,39,44,60,63 и 65 элементов И и с выходами 70 и 71 сумматоров 3-2-1, 3-3-1, входы сумматора 3-4 соединены соответственно с выходами 5,8,10,12,15,16,18,22,33,36,37,47, 48,52,53,59,65 и 66 элементов И и с выходом 71 сумматора 3-3-1,входы сумматора 3-5-2 соединены соответственно с выходами 14,16,27,32,37,60, 61,62 и 66 элементов И и с выходами 69 и 72 сумматоров 3-1-2,3-5-1, входы сумматора 3-6 соединены соответственно с выходами 5.,6,7,12,23,26, 28,30,40,52,54,61 и 66 элементов И и с выходами 72 и 74 сумматоров 3-5-1, 3-7-1, входы сумматора 3-7-3 соединены соответственно с выходами 6,11, 16,32,35,37,39,44,49,52,57,63 и 64 элементов И и с выходами 73 и 74 сумматоров 3-7-2, 3-7-1, входы сумматора 3-8 соединены соответственно с выходами 8,9,19,23,24,25,30,367, 38,41,44,46,48,52,58,61,64 и 65 эле- ментов И и с выходом 73 сумматора 3-7-2, вторые входы элементов И блоков 1-1, 1-2,.,.,1-8 ключей соединены с соответствующими входами множителя В(х), выходы групп сумматоров являются выходами С(х) устройства.

Устройство работает следующ1Ш образом

I

Множимое А(х) и множитель В(х), как и в известном устройстве, представляются в виде выражений

А(х) 21а;х и В(х) bjx.d)

Произведение имеет вид

А(х)-В(х) il 11а; Ь: (2) ;-о

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

; к

- Z. « . k O

(3)

514993346

Тогда (2) гфедст вляется такДесятичные числа представляют соА(х) В(х) Zl Z lla; bj ot , (4) бой степени oi ,

; o le. данном случае множитель и множиКонкретное представление х

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

в виде (3) зависит от полинома, по-5,,

рождающего поле GF (2 ). Покажем прин-. . пг V ь ципы построения параллельного уст-4-- / Z-- j

ройства умножения элементов поля Галуа GF (2«), образованного е помощью помош ю уравнения (4 и таблиполинома 8(х)хв-нх -ьхб+х-И. Элемен- Ц произведение А(х) - В(х) приводитты ПОЛЯ представлены в таблице. виду

А(х) В(х) /ЗдЬ + a,bg + а, Ь ,, + + , + + 4- + a,bj/ + /а(,Ьб + , + , + + , + agb + agbp + agbj/ + + a,b2 + + + , + + + . + , + x + + , + a, b + ajb + + + ajbi + a,bs + + /a,bj + + + + + + + + ajbfi + a,b, + + + ajb., + ag,b, + + + + a7b, + + a-jbg. x + , + + + , + + + + ajb + абЬ5/-ь/а,Ь5 + a2.b7 + + + + + , + aobs + + a,b, + + + + + + Ejbg + + , + . x + /a,b, + , + + a,b, + + + + ajbg + + + , + + + a,bo + + a,b, + a,b4 + a,bg + + + + , + , + + + + , + agb + + . x + + a,b + + + a,b5 + + agb + ajbj + + agb /+/ajjb6 + + , + + + + + a + + a bj/H- a,b2 + + + , + , + « , + атЬ + . x + , + a, by + + + a,by + + a5bj + а5Ьз + + + ajbg + + + / + , + , + + a,bo + + +

+ a,b,+ . X + /aob, + + a, b + + + , +

+ ,+ ац.Ь + a5b7/ + + + a, b + ,, + + +

+ ,+ , + + + + agbj + aeb4 + + +

+ ,+ . x , + + a,b(, + Ejb a,bj + , +

+ a,b,+ + ajb,/ + + + + , + + . +

+ + + + + + + , + + ;

+ a,b,+ + x .(5)

В соответствии с полученной фор-суммы в круглых скобках совпадают и

мулпй синтезировано устройство дляэто уменьшает количество сумматоров

умножения двух элементов поля Галуа ° модулю два. GF (2) (фиг.2). Это устройстно по- 55

строено на элементах И, образующихФормула изобр. етения матрицу размером 8х 8, и сумматорах

по модулю два. Из представленного вы-Параллельное устройство для умноражения также видно, что некоторые «e««« « °- GF (2 ),содержащее n блоков ключей, в каждом из которых имеется n элементов И, при этом вход каждого разряда первого множимого устройства соединен с первыми входами n элементов И соответствующего блока ключей и n блоков суммирования, выходы которых являются выходом устройства, о г л и ч а- ю щ е е с я тем, что, с целью упрощения устройства, блоки суммирования выполнены в виде n групп сумматоров

по модулю два, входы с первого по п-й каждого из которых соединены соответственно с теми выходами n блоков ключей, которые определяются видом порождающего поле Галуа GF (2) полинома,причем вход каждого разряда второго множимого устройства соединен с вторыми входами элементов И со-° ответствующего разряда всех блоков ключей.

«k

Изобретение относится к области вычислительной техники и может быть использовано в устройствах кодирования помехоустойчивыми кодами при передаче данных. Цель изобретения - упрощение устройства. Параллельное устройство для умножения в поле Галуа GF (2^N) содержит N блоков 1-1, 1-2,....,1-N ключей, в каждый из которых входят N элементов И 2-1, 2-2,...2-N и N групп сумматоров 3-1, 3-2,...,3-N по модулю два, соединенных между собой функционально. 2 ил. 1 табл.

ФЙ/

Составитель В.Гусев PeflakTOp Л.Рратилло Техред А,Кравчук Корректор Э.Лончакова

Заказ 4694/47

Тираж 668

ВНИИПИ Государственного комитета до изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

(Dta.3

Подписное