Устройство для умножения элементов конечного поля размерности 2 @ Советский патент 1982 года по МПК G06F7/68 

(54) УСТРОЙСТВО для УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ РАЗМЕРНОСТИ 2т ,

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

Известно устройство -для умножения элементов конеч ного поля, содержащее регистр множимого, регистр множителя, блок умножения, вьисодной регистр tl.

Недостатком такого устройства является большая затрата машинного времени при реализации его програмлшыми средствами.

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

При использовании известного устройства для умножения элементов конечного поля размерности 2уипотребуется блок памяти с объемом, равным

V 2т-2 - бит.

В случае перемножения чисел большой разрядности, что необходимо, например, при формировании помехозащищенных кодов, объем блока памяти возрастает настолько, что становится практически нереализуемым. Таким образом, недостатком устройства является значительное увеличение объема блока памяти при.увеличении

10 разрядности перемножаемых чисел.

Цель изобретения - уменьшение объема оборудования.

Поставленная цель достигается тем, что в устройство дополнительно

15 введены параллельный п-разрядный регистр, первая и вторая группы элементов ИЛИ, по ичэлементов ИЛИ в каждой, третья, четвертая, пятая и шестая группы элементов И по УН

20 элементов И в каждой, параллельный 2м-разрядный регистр адреса, накапливающий сумматор и блок управления, содержащий распределитель тактовых сигналов и шесть элемен25тов ИЛИ, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы, выходы регистра множител-: соединены соответственно с первыми

30 входами элементов И второй группы, выходы rn-раэрядиого параллельного регистра соединены соответственно с первыми входами элементов И третьей, группы, вторые входы m первых элементов И первой группы объединены и соединены с выходом первого элемента ИЛИ блока управления, вторые входы остальных элементов И первой группы объединены и соединены с выходом второго элемента ИЛИ блока управления, вторые входы м пе ., вых зэтементов И второй группы объединены и соединены с выходом третье го элемента ИЛИ блока управления, вторые входы остальных элементов И второй группы объединены и соединенй с выходом етвертого элемента ИЖ блока управления, вторые входы элементов И третьей группы объединены и соединены с первым выходом распре делителя тактовьгх сигналов блока уп равления и с oбъeдинeнны JИ вторыг входами элементов И четвертой группы, выходы Я1 первых элементов И пер вой группы соединены соответственно с первыми входами элементов ИЛИ пер вой группы, выходы остальных элементов И первой груптл соединены со ответственно со вторыми входами эле ментов ИЛИ первой группы, выхода эл ментов И третьей групгш соединены соответственно с третьими входами элементов 11ЛИ первой группы, выходы vnпервых элементов И второй груп ги соединены соответственно с перзы im вкодами элементов ИЛИ второй группы, выходы остальных элементов второй группы соединены соответственно со вторыми входами элементо ИЛИ второй группы, выходы элементов четвертой-группа соединены соответственно с третьими взгодамк элементов ИЛИ второй групщ, выкоды эле.ментов ИЛИ первой группы соединены соответственно с ж первыми входами регистра адреса, выходы элементов ИЛ второй группы соединены соответстве но с остальны.ми входами регистра адреса, выходы которого соответстве но соединены с адресными входами бл ка памяти, выходы которого соединены соответственно с первыми вкодами элементов И пятой н шестой групп, вторые входы элементов И пятой груп пы объединены и соединены с выходам пятого элемента ИЛИ блока управ ления, вторые входы элементов И шес той группы объединены и соедшзены с выходом шестого элемента ИЛИ блока управления, выходы элементов И пятой и шестой групп соединены соответственно с информационными входами накапливакадего сумматора,, выходы ni первых разрядов которого соединены соответственно с первыми ;входам элементов И четвертой группы и являются m первыми раэрядам аяходной шины устройства, а остальные выходы накапливающего сумматора являются соответствующими раэрядами выходной шины устройства, второй выход распределителя тактовых сигналов блока управления соединен с первыми входами первого, третьего и пятого элементов ИЛИ блока управления, первый Выход распределителя тактовых сигналов блока управления соединен с первым входом шестого элемента ИЛИ блока управления, третий выход распределителя тактовых сигналов блока управления соединен с первым входом четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертый выход распределителя тактовых сигналов блока управления соединен с первым входом второго элемента ИЛИ, вторым входом третьего элемента ИЛИ и третьим входом пятого элемента ИЛИ блока управления, пятый выход распределителя тактовых сигналов блока управления соединен со вторыми вкодами второго, четвертого и шестого элементов ИЛИ блока управления. На чертеже изображена функциональная схема устройства. Устройство содержит 2ги-разрядные параллельные регистры 1, 2 множимого и множителя, 2т элементов ЗИ пер,вой группы, 2т элементов 4 И второй группы, блок 5 памяти, параллельный г(-разрядный регистр б, w элементов 7 ИЛИ первой группы, v элементов 8 ИЛИ второй группы, m элементов 9 И третьей группы, m элементов 10 И четвертой группы, т элементов 11 И пятой группы, щ элементов 12 И шестой группы, параллельный 2р11-разрядный регистр 13 адреса, накапливающий сумматор 14-и блок 15 управления, содержащий шесть элементов 16 ИЛИ и распределитель 17 тактовых сигналов. Устройство реализует возможность формирования произведения элементов поля размерности 2 путем последовательного использования операций над элементами поля размерности т, на которые разлагаются 2ит-разрядные числа множимого и множителя. благодаря чему значительно уменьшается объем матрицы. Указанная возможность основана на том, что любой элемент А поля ) можно представить в виде линейного многочлена вида а X 4- а, коэффициенты которого а и а являются как элементами поля GF ( так и его подполя GF (2. , при этом элемент А может быть представлен в виде 2т раз-рядной двоичной комбинации, а компоненты и в видеИ1-разрядных двоичных комбинаций. Сложение двух элементов А и В поля GF(2 можно производить как сложение двух многочленов: А + В ( + +() (а .+ Ь )х + (а-г + Ь) , При этом сложение производится по модулю два. Произведение двух элементов поля ) может быть выполнено как произведение двух соответствующих многочленов по мо- дулю неприводимого квадратного многочлена F(x) над полем GF{2 ) о В . качестве многочлена F(x) может быть использован многочлен вида + X + с, где с - элемент поля GF(2). Поэтому имеем: А-В (а X + а,) (Ь х + Ь,) + ( + a,)x + а,( Ь X + (эу bi + aj. bi)x + -t+ (x) (, + + )х + + ca b . . Устройство осуществляет умножение за пять тактов работы распределители 17 тактовых сигналов и работает следукедим образом. Два .перемножаемых элемента А и В поля {3F( в виде 2ь«-разрядных двоичных комбинаций в исходном состоянии хранятся в параллельных ре-. гистрах 1,2 множимого и множителя. В первый такт работы распределителя 17 тактовых сигналов блока 15 уп равления управлянийий сигнал с выходов первого, третьего и пятого эле ментов 16 ИЛИ блока 15 управления поступает на вторые входы m -первых элементов 3 И первой группы, i-пер вых элементов 4 И второй группы и элементов 11 И пятой группы, разрешая прохождение компоненты а с первых выходов регистра 1 множимого через элементы 7 ИЛИ первой группы на Т1 первые входы регистра 13 адре са, а компоненты Ь - с m первых вы ходов регистра 2 множителя через эл менты 8 ИЛИ второй группы на осталь ные входы регистра 13 адреса. Регис 13 адреса по компонентам «, и Ь вы1би рает ячейку в блоке 5 памяти, в ко рой записано произведение этих HeHTj и считывает содержимое этой яче ки, которое в виде VM-разрядного дв ичного числа через элементы 11 И пя той группы поступает на первые ин формационные входы накапливающего сумматора 14. Во втором такте работы распредел теля 17 тактовых .сигналов блока 15 управления управляющий сигнал с пер вого выхода распределителя 17 посту пает на вторые входы элементов 9 И третьей группы и элементов 10 И чеу вертой группы, а с выхода шестого элемента 16 ИЛИ блока 15 управления на вторые входы элементов 12 И шестой группы, разрешая прохождение ко поненты : с выходов параллельного регистра б через э лементы 7 ИЛИ пер вой группы на ГЦ первые входы регист р,а 13 адреса, а произведения с m первых выходов накапливающего сумMkTopa 14 через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса. С помощью регистра 13 адреса из блока 5 памяти считывается произведение , которое через элементы 12 И шестой группы поступает на остальные информационные входы накапливающего сумматора 14. В третьем.такте работы распределителя 17 тактовых сигналов блока 15 управления управляющий сигнал с выходов первого, четвертого и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы vw первых элементов 3 И первой группы, остальных элементов 4 И второй груп1Ы и элементов 11 И пятой группы, разрешая прохождение компоненты m первых выходов регистра 1 множимого через, элементы 7 ИЛИ первой группы на vw первые входы регистра 13 адреса, а компонент Ь - с остальных выходов регистра 2 множителя через элементы 8 ИЛИ второй группы на остальные входы регистра 13 адреса, С помсяцью регистра 13 адреса из блока 5 памяти считывается произведение , которое через элементы 11 И пятой группы поступает на m первые входы накапливa oщeгo сумматора 14, суллиируясь в нем с произведением а Ь . Таким образом, после третьего такта работы устройства , в W первых разрядах накапливающего сумматора 14 зафиксировано числи ( ч- ) , .JJ ч-етвертом такте работы управляющий сигнал с вьетодов второго, третьего и пятого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остальных элементов 3 И первой группы, ги первых элементов 4 И второй группы и элементов 11 И пятой группы, разрешая прохождение компонент а и Ь на входы регистра 13 адреса, а следовательно, и считывание из блока 5 памяти произведения которое поступает через элементы 11 И пятой группы в m первые разряды накапливающего сумматора 14. Таким образом, после четвертого такта работы устройства в m первых разрядах накапливающего сумматора 14 записана сумма (а Ь + ,2.+ ,,} . В пятом такте работы управляющий сигнал с выходов второго, четвертого и шестого элементов 16 ИЛИ блока 15 управления поступает на вторые входы остал нйх элементов 3 И первой группы, остал| ннх элементов 4 И второй группы и элементов 12 И шестой группы, разрешая прохождение компонент а и Ь, на входы регистра 13 адреса, а следовательно, и считывание из блока 5 памяти произведения аabi,которое через элементы 12 И шеетой группы поступает в остальные разряды накапливающего сумматора 14. Таким образом, после пятого такта ра боты устройства в ni первых разрядах накапливающего сумматора 14 зафиксирована компонента ( + + + а Ь ) , а в остальных компонента ( + ) произведения АВ.

Устройство по сравнению с прототипом обеспечивает выигрыш в объеме памяти для хранения произведений, а тркже в разрядности перемножаемых чисел.

Если в прототипе объем памяти составляет

4 10

V 2т2

бит.

6Г

то в данном устройстве он составит

V ,

и таким образом выигрыш в памяти данного, устройства по сравнению с прототипом

,2w

10 32

2

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

Устройство для умножения элементов конечного поля размерности 2т, содержащее параллельные 2т-разрядные регистры множимого и множителя, первую и вторую группы элементов и по 2т элементов И в каждой, блок памяти,, о ичающееся тем, что, с целью уменьшения объема оборудования, в устройство введены параллельный т-разрядный регистр, первая н вторая группы элементов ИЛИпо ш элементов ИЛИ в каждой, третья, четвертая, пятая и шестая группы элементов И по m элементов И в каждой, параллельный 2т-разрядный регистр адреса, .на)агшивающий сумма,тор и блок управления, содержащий .распределитель тактовых сигналов и шесть элементов ИЛИ, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы, выходы регистра множителя соединены соответственно с первыми входами элементов И второй группы, выходы параллельного w-разряд|нрго регистра соединены соответственно с первыми входами элементов И третьей группы, вторые входы т первых элементов И первой группы объединены и соединены с выходом пер вого элемента ИЛИ блока управления, вторые входы остальных элементов И первой группы объединены и соединены с выходом второго элемента ИЛИ блока управления, вторые входы rvt первых элементов И второй группы объединены и соединены с выходом третьего

элемента ИЛИ блока управления, вторые входы остальных элементов И второй группы объединены и соединены с выходом четвертого элемента ИЛИ блока управления, вторые входы элементов И третьей группы объединены и соединены с первым выходом распределителя тактовых сигналов блока управления и с объединенными вторыми входами элементов И четвертой группы,

0 выходы m первых элементов И первой группы соединены соответственно с . первыгли входами элементов ИЛИ первой группы, выходы остальных элементов И первой группы соединены соот5 ветстаенно со вторыми входами элементов ИЛИ первой группы, выходы элементов И третьей группы соединены соответственно с третьими входами элементов ИЛИ первой группы, выходы m

0 первых элементов И второй группы соединены соответственно с первыми входами элементов ИЛИ второй группы, выходы остальных элементов И второй группы соединены соответственно со

5 вторыми входами элементов ИЛИ второй группы, выходы элементов И четвертой группы соединены соответственно с третьими входами элементов ИЛИ второй группы, выходы элементов ИЛИ

первой группы соединены соответственно с уп первыми входами регистра адреса, выходы элементов ИЛИ второй группы соединены соответственно с остальными входами регистра адреса, выходы которого соответственно соединены с адресными входами блока памяти , выходы которого соединены соответственно с первыми входами элементов И пятой и шестой групп, вто.рые входы элементов И пятой группы

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

е соответствующими разрядами выходной шины устройства, второй выход распределителя тактовых сигналов блока управления соединен с первыми входами первого, третьего и пятого элементов ИЛИ блока управления, первый выход распределителя тактовых сигналов блока управления соединен с первым входом шестого элемента ИЛИ блока управления, третий выход распределителя тактовых сигналов блока

5 управления соединен с первым входом

четвертого элемента ИЛИ и со вторыми входами первого и пятого элементов ИЛИ блока управления, четвертый выход распределителя тактовых сигналов блока управления соединен с первым входом второго элемента ИЛИ, вторым входом третьего элемента ИЛИ и третьим входом пятого элемента ИЛИ блока управления, пятый выход распределителя тактовых сигналов блока управления соединен со вторыми входа-

мй второго, четвертого, и шестого элементов ИЛИ блока управления.

Источники информации, принятые во внимание при экспертизе

550636, кл. G 06 F 7/52,1971 (прототип ).