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

цт;

J2

22

н

;j

ZJ

п

а

ел

о ю ю

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

пи

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

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

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

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

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

Параллельньй счетчик - это устройство, которое подсчитывает число сигналов, поступающих одновременно на его входы. Обычно параллельный счетчик имеет п входов и выходов. Данные на входы параллельного счетчика поступают в позиционном унитарном коде, а на его выходах получается двоичный код, равный числу единиц на входах. Каждый из входов 1.1-1.15 имеет по 4 шины. Таким образом, каждый из блоков 2.1-2.15 имеет по 4 входные и 4 выходные шины. Все блоки 2.1-2„15 являются идентичными и в каждом из них выполняется

преобразование типа а а - Л111; а - 0001; а - 0010; а - ООП; а - 0100; 0101; а -. ОНО; а - 0111; а - 1000; а - 1001; 1010; а н. 1011; а - 1100;

,1.

1101; , 1110.

Каждый из блоков имеет по 4 выхода, имеющие двоичные веса 2°, 2,

2 и 2. Выходы с равносильными весами обьединены в группы по 15 шин в каждой группе.

Работа основана на свойстве цикличности поля Галуа, которое для

случая m 4 образуется над неприводимым полиномом четвертой степени Х + X + 1. Цолагая, что а 0100 есть корень этого полинома, получают 14 остальных его элементов из

уравнения а + 1 О, где знак + означает суммирование по модулю два, а операции сложения и вычитания равнозначны. В этом поле имеется 4 линейно независимых элемента а

ИЮО 1; а 0100; а 0010

и а 0001. Из уравнения а а + + а° получают, что а 1100; а

а а а + а ОНО; а

а а + а ООН; а а + а а + а .

Аналогично получают а 1010; аЗ 0101; а 1110; а 0111; а - 1111; а 1011; а 1001 в силу цикличности ПОЛЯ, так как 2 - 1 15. Далее степень произведения элементов равна циклической сумме степеней каждого из сомножителей. Например, а.- а а а а или, складывая число 5 0101 и число 14 1110 по модулю 15, получают ,

0101

1ПО

ООН

ОТОО 4j

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

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

Коды, соответствующие элементу а° 1000, одновременно подаются на входы блоков 2.1-2.15, на выходах

которых формируются коды 1111 15|с.

Затем с помощью циклического компрессора происходит суммирование единиц, выполняющееся параллельно по столбцам (фиг. 3). В каждом столбце содержится по 15 1111 единиц. Эти единицы записьшаются по диагонали так, что старший разряд суммы весов 2 оказывается записанным под цифрами четвертого столбца, где содержатся цифры с весом 2. Аналогично записьшаются результаты суммирования единиц с весами 2, 2. В результате после первого этапа суммирования из 15 слагаемых получается 4, которые суммируются на втором этапе. Аналогично на третьем этапе выполняется суммирование уже трех операндов. При этом вертикальной линией отделены те ци1)ры, которые возникают в результате циклического переноса. После суммирования на третье этапе получается два слагаемых, т.е. из 15 двоичных 4-разрядных чисел получается два 8-разрядньгх двоичных числа. Эти числа разделены на две группы, по четыре разряда в каждой группе. По существу числа слева от вертикальной линии представляют собой циклические переносы, которые возникают при суммировании чисел на соответствующих этапах 2,3,4 (фиг. 3). С помощью сумматора 4 получается результат суммирования без учета циклических переносов. С помощью сумматора 6 получается число, равное общему количеству циклических переносов, которое равно 11010000. Старшие разряды этого числа 1101 складываются с результатом, полученным на выходах сумматора 4. После суммирования на выходах сумматора 5 получается код 0110,и на выходах блока 7 формируется элемент произведения а а . Данный пример характерен тем, что он дает величину максимального количества циклических переносов, которое может получиться при циклическом суммировании в поле GF (.). Эта величина равна 1101000. Тем самым отпадает необходимость в использовании циклического переноса в сумматоре 6.

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

При этом вьшолняется преобразование следующего вида: 0001 - 0100; 0010- а 0010; 0011

0001; 0100- а 1100; 0101- ОНО; ОНО - а -1.а « 1101; 1000 1001 - а

ООП; 0111 1 1010;

lO

а 0101; 1010 а 1110; 1011 - а 0111; 1100 - а 1111; 1101 - а 1011; 1110 - а 1001;

1111

а

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

Устройство для умножения элементов в поле Галуа GF (2), содержащее N блоков преобразования элементов поля Галуа GF (2) в двоичные коды (2 i N i 2 1), первый сумматор

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

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

с входами блоков преобразования элементов поля Галуа GF (2) в двоичные коды, выход старщего разряда первого сумматора по модулю 2 - 1 соединен с входом младшего разряда первого сумматора по модулю 2 - 1, выходы одинаковьгх двоичных весов 2°, 2... 1 N блоков преобразования элементов поля Галуа GF (2) в двоичные коды объединены в m групп, отличающееся тем, что, с целью расширения функциональных возможностей за счет одновременного умножения N ненулевых элементов поля Галуа GD (2), введены второй сумматор по модулю 2 - 1, т-разряд- ный сумматор и циклический компрессор, содержащий М каскадов(М - количество двоичиых цифр в числе in)no m групп (п. К)-параллельных счетчиков (К logjn) и имеющий m групп по 1 входов и четыре группы по m выходов, причем выходы N блоков преобразования элементов поля Галуа GF (Z) соединены с соответствующими входами (п. К)-параллельных счетчиков; первого каскада циклического компрессора, выходы первой и второй групп (п, К)-параллельных счетчиков М-го каскада циклического компрессора сое

динены cooTBe-rcTBe iHo с входами старших m - М разрядов первого и второго слагаемых второго сумматора по модулю 2 - 1, выход которого соединен с входом первого слагаемого первого сумматора по модулю 2 - 1, вход второго слагаемого которого соединен с выходом т-разрядного сумматора, входы первого и второго слагаемых которого соединены соответственно с выходами третьей и четвертой групп (п, К)-параллельных счетчшсов М-го каскада циклического компрессора, выход старшего разряда второго сумматора по модулю 1 соединен с

I/ v Ч vv V Ч vv V Wy

Фиг 2

входом младшего разряда второго сумматора по модулю 1, выходы (п. К)-параллельных счетчиков i-ro

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

каскада циклического компрессора, выходы младших разрядов (п. К)-параллельных счетчиков каждого каскада циклического компрессора соединены соответственно с входами

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

Г Г5.

Ю