Устройство для умножения в конечных полях Советский патент 1983 года по МПК G06F7/49 

но с управляющими входами переключателей, управляющие входы переключателей с первого по (Ы-1)-й соединены соответственно с вторыми входами элементов И с первого по (Ы-1)-й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым входом устройства.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В ПОЛЯХ, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (N-l)-ro разряда первого регистра сдвига соединен с вторым входом (N-2)-rO элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (N-l)-ro элемента ИЛИ первой группы, с первыми входами элементов И первой группы, выходы которых, соединены соответственно с первыми- входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы, отличающееся тем, что, с целью расщирения области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым многочленом, степень которого не превышает заданной, в него введены регистры многочлена, блок определения старшего нулевого разряда, вторая и третья группы элементов И, N переключателей, вторая группа сумматоров по модулю два, причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены соответственно с входами блока определения старшего ненулевого разряда, выходы разрядов с первого по I (Ы-1)-й регистра многочлена соединены соответственно с первыми входами элементов (П И второй группы, выходы разрядов с нулевого по (К1-2)-й второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (М-1)-й третьей группы и первыми информационными входами переключателей с первого по (Н-1)-й выход (N-l)-ro разряда второго регистра сдвига соединен с первым информационным входом N-ro переключателя, О5 второй информационный вход которого соединен с шиной нулевого потенциала устройства, выход N-ro переключателя соединен с вторым входом (N-l)-ro элемента 00 И второй группы и вторым информацион4 ным входом (N-l)-ro переключателя, выход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей групп соединены соответственно с первыми и вторыми входами сооответствующих сумматоров по модулю два второй группы, выходы сумматоров по модулю два с первого по (М-1)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по Ы-1)-й второй группы, выходы блока определения старшего нулевого разряда соединены соответствен

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

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

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

Наиболее близким по технической сущности к данному изобретению является устройство умножения в конечных полях, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены сот ответственно с входами разрядов первого регистра сдвига, выход (N-l)-ro разряда первого регистра сдвига соединен с вторым входом (N-2)-ro элемента ИЛИ первой группы, В:Ыход Нулевого разряда первого регистра сдвига соединен с вторым входом (N-r)-ro элемента ИЛИ первой группы, с первыми входами элементов И первой группы, выходы которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю:-два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, .выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы 2.

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

которое продолжается полиномом, раз и навсегда заданным при построении устройства, так как цепь для деления на порождающий полином поля неизменяема.

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

Поставленная цель достигается тем, что устройство, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элемен5 трв ИЛИ первой группы соединены соотвественно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой

Q группы соединены соответственно с входами разрядов первого регистра сдвига, выход (N-l)-ro разряда первого регистра сдвига соединен с вторым входом (N-2)-ro элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвиг;; соединен

5 с вторым входом (М -1)-го элемента ИЛИ первой группы с первыми входами элементов И первой группы, выходы которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответ0 ственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю, два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответ5 ственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвиQ га соединены соответственно с вторыми входами элементов И первой группы, введены регистры многочлена, блок определения старщего ненулевого разряда, вторая и третья группы элементов И, N переключателей, вторая группа сумматоров по модулю два,

5 причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены соответственно с входами блока определения старшего нулевого разряда, выходы разрядов с первого по (N-l)-ft регистра многочлена соединены соответственно с первыми входами элементов И второй группы, выходы разрядов с нулевого по (N-2)-ft и второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (N-l)-u третьей группы и первыми информационными входами переключателей с первого по (Ы-1)-й, выходы (N-l)-ro разряда второго регистра сдвига соединен с первым информационным входом N-ro переключателя, второй информационный вход которого соединен с шиной нулевого потенциала устройства, выход N-ro переключателя соединен с вторым входом (N-l)-ro элемента И второй группы и вторым информационным входом (N-l)-ro переключателя, выход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей группы соединены соответственно по модулю два второй группы, выходы сумматоров по модулю два с первого по (N-l)-A второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по (Ы-1)-й второй группы, выходы блока определения старшего нулевого разряда соединены соответственно с управляющими входами переключателей, управляющие входы переключателей с первого по (N-l)-й соединены соответственно с вторыми входами элементов И с первого по (Ы-1)-й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым вхо дом устройства.

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

Устройство содержит регистр 1 сдвига, содержащий N разрядных ячеек 2-5, регистр 6 сдвига, содержащий N разрядных ячеек 7-10, регистр 11 сдвига, содержащий N разрядных ячеек 12-15, регистр. 16 многочлена, содержащий N разрядных ячеек 17-20, группу элементов ИЛИ 21 - 24, группу элементов ИЛИ 25-28, группу элементов И 29- 32, группу элементов И 33-35, группу элементов И 36-38, группу сумматоров 39-42 по модулю два, группу сумматоров 43-45 по модулю два, блок 46 определения старшего ненулевого разряда, переключатели 47-50, входы 51-54 коэффициентов множителя устройства, входы 55-58 коэффициентов множимого устройства, входы 59-62 неприводимого многочлена устройства, выходы 63- 66 устройства, тактовый вход 67 устройства. Один из входов элементов И 33-35 выполнены инверсными.

Блок 46 определения старшего ненулевого разряда состоит из элементов И 68-75. Один из входов элементов И 69-75 выполнены инверсными. Входы 76-79 являются входами блока 46. Выходы 80-83 являются выходами блока 46. Вход 84 является входом логической единицы.

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

Рассмотрим поле GF(2), порождаемое Неприводимым многочленом f(x) степени ш с коэффициентами из поля C3F(2), т. е. f(x) fo + f,+ f.x...,f EGF(2),1 0,1..., m-1), fm 1. Каждый элемент поля GF (2 ) представляют в виде многочлена нaд-OF(2), степень которого меньше т, тогда умножение элементов поля друг на друга выполняется по правилам умножения, представляющим эти §лёменты многочленов по модулю образуюш.ёго многочлена f(x). Пусть а(х) а ,+.ai(x)+... + , ajEGF(2), i 0,i,...,m-1 - множимое в(х) Bo-fВ4Х + + ...в.x ,в GF(2),i 0,lm-1 -множитель, когда их произведение с(х) +...сй-. xrcieGF(2), i 0,l,...,m-1 равно c(xj B(x)a(x)modf(x). т. е. с(х) BeUo (х) -fBiU, (х)+... + Bre.i Um- (х), где Ui (x)modf(x).

В Предлагаемом устройстве степень многочлена f(x)m может быть любой, но не больше, чем разрядность регистров 1, 6, 11, 16.

В исходном соястоянии регистр находится в нулевом состоянии. На входы устройства 51о, 52, 53ы-2, 54н-1 подаются одновременно коэффициенты многочлена в(х) BO; ..., Bm-i, причем условию Si 1 соответствует единичный потенциал на соответствующем входе, а условию в; 0 - нулевой потенциал на соответствующем входе. При этом, если , то Bi 0 при . Аналогичным образом на. входы 591, бОг, 61я-1, 62н устройства подаются коэффициенты многочлена f(x), а на входы 55о, 56i, 57j.2- 58(g..j - коэффициенты многочлена а(х) и запоминаются в регистрах 16 и 6 соответственно.

После того, как в регистр 16 записаны коэффициенты многочлена f(x), на входах блока 46 определения старшего ненулевого разряда появляется слово, состоящее из нулей, кроме разряда, соответствующего крайней правой единице в слове, составленном из коэффициентов многочлена f(x). Переключатели 47-50, на управляющий вход которых подается эта единица, соединяют выход соответствующей разрядной ячейки регистра 6 со своим входом. На управляющие входы остальных переключателей 47-50 поступают нули, и они устанавливаются в положение, при котором выход каждого последующего переключателя 47- 50 соединен с выходом предыдущего. Таким образом разрядные ячейки регистра 6, переключатели 47-50 элементы 33 и 38 И и сумматоры 43 и 45 по модулю два, стоящие левее этого выделенного переключателя 47-50 вместе с ним образуют цепь умножения на х по модулю f(x), йа входы же сумматоров 43-45 по модулю два, стоящих правее выделенного переключателя 47-50, поступают только нули, поэтому соответствующие разрядные ячейки регистра 6 всегда обнулены. При поступлении на тактовый вход &7 устройства тактового импульса происходит сдвиг в регистрах 1 и 6, при этом содержащееся в регистре 6 слово из коэффициентов многочлена а(х) умножается на х по модулю f(x), одновременно на входы элементов И 29-32 поступает значение коэффициента в,, а в регистре И записывается слово. из коэффициентов Воа(х). На вторые входы элементов И 29-32 теперь поданы коэффициенты многочлена xa(x)modf(x). Легко видеть, что на i-м шаге, т. е. при поступлении i-ro тактового импульса, в ячейках регистра 2 образуется многочлен и (х), на выходах элементов И 29-32 и появляется многочлен BiUi(x), а в регистр11 записывается многочлен BoUo(x)+ фиёЛ + BI Ui (х) +...-f Bi-i Ui-t (х). После m-готактового импульса в регистре 11 будет содержаться результат умножения с(х) B(x)a(x)modf(x). Дальнейшее поступление тактовых импульсов не будет влиять на содержимое регистра 11, поскольку старшие разряды в(х) равны нулю, BJ 0, при . Таким образом, предложенное устройство выгодно отличается от прототипа, так с его помощью можно производить-умножение в поле, порожденном любым неприводимым многочленом. Для этого достаточно загрузить коэффициенты этого многочлена в регистр 16. Ограничение накладывается только на степень образующего многочлена поля, которая не должна превышать разрядности устройства. Это особенно удобно в тех случаях, когда устройство реализуется в интегральном исполнении или входит в состав БИС, когда доступ к цепи деления на порождающий многочлен невозможен. ЬЬы-1