Устройство для умножения элементов в поле галуа gf(2 @ )

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах, оперирующих над элементами поля Галуа, а также в системах кодирования, в устройствах обнаружения и исправления ошибок в кодовых словах, построение которых базируется на теории полей Галуа GF (2<SP POS="POST">M</SP>). Цель изобретения - расширение функциональных возможностей за счет одновременного умножения N ненулевых элементов поля Галуа GF (2<SP POS="POST">M</SP>). В устройстве для умножения элементов в поле Галуа GF (2<SP POS="POST">M</SP>), содержащее N блоков преобразования 2<SB POS="POST">1</SB>-2<SB POS="POST">N</SB> элементов поля Галуа GF (2<SP POS="POST">M</SP>) в двоичные коды, первый сумматор 5 по модулю 2<SP POS="POST">M</SP>-1 и блок преобразования 7 двоичных кодов в соответствующие им элементы поля Галуа GF (2<SP POS="POST">M</SP>), введен второй сумматор 4 по модулю 2<SP POS="POST">M</SP>-1, M - разрядный сумматор 6 и циклический компрессор 3, содержащий M каскадов по M групп (N,K) параллельных счетчиков. 3 ил.

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

ÄÄSUÄÄ 1517022 А1 (51)4 G 06 У 7/49

3!.:Е0,лп ".

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbITHRM

ПРИ ГКНТ СССР (21) 4289768/24-24 (22) 24.07.87 (46) 23.10.89. Бюл. Р. 39 (71) Объединенный институт ядерных исследований (72) Н.М.Никитюк (53) 681.325(088.8) (56) Гуськов Б.Н., Калинников В.А., Крастев В.P. и др. Быстродействующий параллельный счетчик. — Приборы и техника эксперимента, 1984, II 6, с. 91.

Патент ЕПВ У 0061345, кл. G 06 F 11/10, опублик. 1982. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ В ПОЛЕ ГАЛУА GF (2 ) (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах, оперирующих над элемента2 ми поля Галуа, а также в системах кодирования, в устройствах обнаружения и исправления ошибок в кодовых словах, построение которых базируется на теории полей Галуа GF (2 )..

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

2 — 1 и блок преобразования 7 двоичных кодов в соответствующие им элементы поля Галуа GF (2 ), введен второй сумматор 4 по модулю 2 — 1, m-разрядный сумматор 6 и циклический компрессор 3, содержащий М каскадов по ш групп (и, К)-параллельных счетчиков, 3 ил, 1517022

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

Цель изобретения — расширение функциональных возможностей за счет одновременного умножения N ненулевых элементов поля Галуа GF (2 ).

На фиг. 1 приведена функциональная схема устройства для случая, когда m = 4, т.е. умножения пятнадцати элементов поля Галуа GF (2 на фиг. 2 — один из вариантов кон кретной реализации циклического компрессора для случая, когда m = 4; на фиг. 3 — пример одновременного суммирования 15 степеней элементов поля Галуа при использовании варианта циклического компрессора.

Устройство для умножения (фиг. 1) содержит входы 1.1 — 1.15 для сомножителей, блоки 2.1-2.15 преобразования элементов поля Галуа GF (2 ) в двонч- 30 ные коды, циклический компрессор 3, сумматоры 4 и 5 по модулю 2"- 1, 4-разрядный сумматор 6, блок 7 преобразования двоичных кодов в соответствующие им элементы поля Галуа

GF (? ) и выход 8 устройства умно т 35 жения.

Циклический компрессор 3 (фиг. 2) содержит (15,4)-параллельные счетчики 9 — 12, (2,2)-параллельные счетчики 13-18, (3,2)-параллельные счетчики 19-21, (4,3)-параллельный счетчик 22 и четыре группы выходов 2326.

Параллельный счетчик — это уст45 ройство, которое подсчитывает число сигналов, поступающих одновременно на его входы. Обычно параллельный счетчик имеет и входов и K=log и выходов. Данные на входы параллельного счетчика поступают в позиционном

50 унитарном коде, а на его выходах получается двоичный код, равный числу единиц на входах. Каждый из входов

1.1-1.15 имеет по 4 шины. Таким образом, каждый из блоков 2.1-2.15 име- 55 ет по 4 входные и 4 выходные шины.

Все блоки 2.1-2.15 являются идентичньгчи и в каждом из них выполняется преобразование типа а = а - .1) 1); а 0001; а - 0010; аз - 00) );

О) О) a6 - 01)ot

a О) )1; ао 1000; а 100) ° 1 а" -+ 1010; a " " 1011; a -+ 1100; а"- 1101; а" 1110.

Каждый из блоков имеет по 4 выхода, имеющие двоичные веса 2, 2, 2 и 2 . Выходы с равносильными ве2 3 сами объединены в группы по 15 шин в каждой группе.

Работа основана на свойстве цикличности поля Галуа, которое для случая m = 4 образуется над неприводимым полиномом четвертой степени

Х + Х + 1. Полагая, что а = 0100 есть корень этого полинома, получают 14 остальных его элементов из уравнения а + а + 1 = О, где знак

"+" означает суммирование по модулю два, а операции сложения и вычитания равнозначны. В этом поле имеется о

4 линейно независимых элемента а — 1000 = 1; а = 0100; а = 0010 и а = 0001. Hs уравнения а = а +

+ а получают, что а = 1100; а

4 а а = а +а = 0110; а у а . а = а +а = 0011; а = a »

3 +

«a =а +а =а +а +а =1101.

Аналогично получают а = 1010

a9 = 0101; а "= 1110; a" = 0111;

12 ))) ) 13 )О)) 14 )00) силу цикличности поля, так как 2 — 1 = 15. Далее степень произведения элементов равна циклической сумме степеней каждого из сомножителей.

)) ° 5 1 19 5 4 а или, складывая число 5 = 0101 и число 14 = 1110 по модулю 15, получают, 0101

1110

0011

0100 = 4

Выполняя обратное преобразование

0100 - 1100 = а, получают окончательный результат произведения двух элементов °

Допустим, что необходимо одновременно умножить 15 единичных элементов а = а в поле Галуа GF (? ). о

Коды, соответствующие элементу а

1000, одновременно подаются на входы блоков 2.1-2.15, на выходах которых формируются коды 1111 = )5„.

1517022

Затем с помощью циклического компрессора происходит суммирование единиц, выполняющееся параллельно по столбцам (фнг. 3). В каждом столбце содержится по 15 = 11)1 единиц. Эти единицы записываются по диагонали так, что старший разряд суммы весов

2 оказывается записанным под цифрао ми четвертого столбца, где содержатз

10 ся цифры с весом 2 . Аналогично saписываются результаты суммирования единиц с весами 2, 2 и 2 . В ре1 эультате после первого этапа суммирования из 15 слагаемых получается

4, которые суммируются на втором этапе. Аналогично на третьем этапе выполняется суммирование уже трех операндов. При этом вертикальной линией отделены те ци) ры, которые возникают в результате циклического переноса ° После суммирования на третьем этапе получается два слагаемых, т.е. из 15 двоичных 4-разрядных чисел получается два 8-разрядньж двоичных числа. Эти числа разделены на две группы, по четыре разряда в каждой группе. По существу числа слева от вертикальной линии представляют собой циклические переносы, которые возникают при суммировании чисел на соответствующих этапах 2,3,4 (фиг. 3). С помощью сумматора 4 получается результат суммирования без учета циклических переносов. С помощью сумматора 6 получается число, равное общему количеству циклических переносов, которое равно 11010000.

Старшие разряды этого числа 1101 складываются с результатом, полученным на выходах сумматора 4. После суммирования на выходах сумматора 5 получается код 0110, и на выходах блока 7 формируется элемент произведения а = а . Данный пример характерен тем, что он дает величину максимального количества циклических переносов, которое может получиться при циклическом суммировании в поле

GF (2 ). Эта величина равна 1101000.

Тем самым отпадает необходимость в использовании циклического переноса в сумматоре 6.

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

При этом выполняется преоб ра эование следующего вида: 0001 -- а

0100; 0010 а 0010; 0011 - а =

0001; 0100 а 1100; 0101- а

Ol l 0- 0110 -в а = 0011; Ol l l

- а 1101, 1000 - a 1010;

1001 - а 0101; 1010 - а = 1110;

1011 - а" = 0111 ° 1100 - а = 1) l l1101 - а" = )011- ) 110 а = ) 001;

1111 — а = а = 1000.

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

Устройство для умножения элементов в поле Галуа GF (2"), содержащее

N блоков преобразования элементов поля Галуа GF (2 ) в двоичные коды (2 < N " 2 — 1), первый сумматор по модулю 2 — 1 и блок преобразования двоичных кодов в соответствующие им элементы поля Галуа GF (2 ), причем выходы первого сумматора по модулю 2 — 1 соединены с входами блока преобразования двоичных кодов в соответствующие им элементы поля

Галуа GF (? ), выходы которого соединены с выходами устройства, информационные входы которого соединены с входами блоков преобразования элементов поля Галуа СР (2 ) в двоичные коды, выход старшего разряда первого (П сумматора по модулю 2 — 1 соединен с входом младшего разряда первого сумматора по модулю 2 — I, выходы о одинаковьж двоичных весов 2

2 ...2 — 1 N блоков преобразования элементов поля Галуа GF (2 ) в двоичные коды объединены в m групп, 40 о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей sa счет одновременного умножения N ненулевых элементов поля Галуа GD (2"), введены второй

45 сумматор по модулю 2 — 1, m-разрядный сумматор и циклический компрессор, содержащий И каскадов(М вЂ” количество двоичных цифр в числе т)по

m групп (n, К)-параллельных счетчиков (К = logqn) и имеющий m групп по 2 — 1 входов и четыре группы по

m выходов, причем выходы N блоков преобразования элементов поля Галуа

GF (2 ) соединены с соответствующими входами (n, К)-параллельных счетчиков первого каскада циклического компрессора, выходы первой и второй групп (n, К)-параллельных счетчиков М-ro каскада циклического компрессора сое1517022

1 r O

Риг 2

1 1 1 1=15,О

Фигз

Составитель Е. Мурзина

Техред Л.Олийнык Корректор З, Лончакова

Редактор О, Ирковецкая

Заказ 6391/51 Тираж 668 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/>

Производственно-издательский комбинат "Патент", r.ужгорол, ул. Гагарина, 101 динены соответственно с входами старших m — М разрядов первого и второго слагаемых второго сумматора по моду1 1 лю 2 — 1, выход которого соединен с входом первого слагаемого первого

tn сумматора по модулю 2 — 1, вход второго слагаемого которого соединен с выходом m-разрядного сумматора, входы первого и второго слагаемых которого соединены соответственно с выходами третьей и четвертой групп (п, К)-параллельных счетчиков М-ro каскада циклического компрессора, выход старшего разряда второго сумматора по модулю 2" — 1 соединен с входом младшего разряда второго сумffl матора по модулю ? — 1, выходы (п, К)-параллельных счетчиков i-го

5 каскада (i = 1,2,..., M-1) циклического компрессора, кроме выходов младших разрядов, соединены с входами соответствующих двоичных весов (п, К)-параллельных счетчиков (i + 1)-ro каскада циклического компрессора, выходы младших разрядов (n, К)-параллельных счетчиков каждого каскада циклического компрессора соединены соответственно с входами

M младших разрядов второго сумматорапо модулю 2 — 1.

25 Zã Zt

1 1 1 1

1 1

1 1 1 1

1 1 1

1 1 1

1 1 1 1

1 1 1 1

1 1 1

+ 1 1 1 1

1 1 1 1

1 1 1 1 !

1 1 1

1 1 1

1 1 1 1