Устройство для умножения в конечных полях

(19) (11) 134 06 Г 7/4 ЕН АВТОРСКОМ ВУ Т с п ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ПИСАНИЕ ИЗ(54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ ПОЛЯХ, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы сое динены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (М)-го разряда первого регистра сдвига соединен с вторым входом (Ы) -го элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (Х) -го элемента ИЛИ первой группы, с первыми входами элементов И первой группы, выходы которых, соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно вторыми входами элементов И первой групы, отличающееся тем, что, с целью расширения области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым многочленом, степень которого не превышает заданной, в него введены регистры многочлена, блок определения старшего нулевого разряда, вторая и третья группы элементов И, И переключателей, вторая группа сумматоров по модулю два, причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены соответственно с входами блока определения старшего ненулевого разряда, выходы разрядов с первого по (М-)-й регистра многочлена соединены со- Е ответственно с первыми входами элементов И второй группы, выходы разрядов с нулевого по (И)-й второго регистра сдвига соединены соответственно с первыми вхо- С дами элементов И с первого по (И)-й третьей группы и первыми информационны- р ми входами переключателей с первого по (Х) -й выход (Х) -го разряда второго регистра сдвига соединен с первым информационным входом Х-го переключателя, второй информационный вход которого сое- Ж динея с шиной нулевого потенциала уст- Фе ройства, выход М-го переключателя сое- ы динен с вторым входом (И)-го элемента е И второй группы и вторым информационным входом (И)-го переключателя, вы- фЬ ход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей групп соединены соответственно с первыми и вторыми входами сооответствую- фр щих сумматоров по модулю два второй группы, выходы сумматоров по модулю два с первого по (1 Ч)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по Х)-й второй группы, выходы блока определения старшего нулевого разряда соединены соответствен1061134 которое продолжается полиномом, раз и навсегда заданным при построении устройства, так как цепь для деления на порождающий полином поля неизменяема.Цель изобретения - расширение области применения за счет обеспечения умножения полиномов в поле, порожденном любым неприводимым многочленом, степень которого не превышает заданной,Поставленная цель достигается тем, что устройство, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соотвественно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, выходы элементов ИЛИ первой группы соединены соответственно с входами разрядов первого регистра сдвига, выход (Х)-го разряда первого регистра сдвига соединен с вторым входом (М)-го элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (М -1)-го элемента ИЛИ первой группы с первыми входами элемен тов И первой группы, выходь 1 которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю, два первой группы соединены соответственно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы, введены регистры многочлена, блок определения старшего ненулевого разряда, вторая и третья группы элементов И, М переключателей, вторая группа сумматоров по модулю два,45 причем входы разрядов регистра многочлена соединены соответственно с входами неприводимого многочлена устройства, выходы регистра многочлена соединены со. но с управляющими входами переключателей, управляющие входы переключателей с первого по (Х)-й соединены соответственно с вторыми входами элементов И с перИзобретение относится к вычислительной технике и предназначено для выполнения операции перемножения многочленов в конечных полях.Известно устройство для умножения в конечных полях, содержащее первый, второй и третий регистры, блок умножения и группу элементов И 11.Недостатком этого устройства является невозмож ность перемножения многочленов в каком-либо ином поле, кроме того, которое порождается поли номом, и навсегда определенном при построении устройства.Наиболее близким по технической сущности к данному изобретению является устройство умножения в конечных полях, содержащее первый, второй и третий регистры сдвига, первую и вторую группы элементов ИЛИ, первую группу элементов И, первую группу сумматоров по модулю два, причем первые входы элементов ИЛИ первой группы соединены соответственно с входами коэффициентов множителя устройства, выходы разрядов третьего регистра сдвига являются выходами устройства, зыходы элементов ИЛИ первой группы соединены со-. ответственно с входами разрядов первого регистра сдвига, выход (М) -го разряда первого регистра сдвига соединен с вторым входом (М) -го элемента ИЛИ первой группы, выход нулевого разряда первого регистра сдвига соединен с вторым входом (Х)-го элемента ИЛИ первой группыс первыми входами элементов И первой группы, выходы которых соединены соответственно с первыми входами сумматоров по модулю два первой группы, вторые входы которых соединены соответственно с выходами разрядов третьего регистра сдвига, выходы сумматоров по модулю.два первой группы соединены соответствейно с входами разрядов третьего регистра сдвига, первые входы элементов ИЛИ второй группы соединены соответственно с входами коэффициентов множимого устройства, выходы элементов ИЛИ второй группы соединены соответственно с входами разрядов второго регистра сдвига, выходы разрядов второго регистра сдвига соединены соответственно с вторыми входами элементов И первой группы 12 .Недостатком данного устройства является невозможность перемножения многочленов в каком-либо ином поле, кроме того,5 10 15 20 25 Зо 35 40 вого по (М) -й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым входом устройства.ответственно с входами блока определения старшего нулевого разряда, выходы разрядов с первого по (М)-й регистра много- члена соединены соответственно с первыми входами элементов И второй группы, выходы разрядов с нулевого по (И)-й и второго регистра сдвига соединены соответственно с первыми входами элементов И с первого по (Х)-Й третьей группы и первыми информационными входами переключателей с первого по (Х)-й, выходы (И)-го 10 разряда второго регистра сдвига соединен с первым информационным входом И-го переключателя, второй информационный вход которого соединен с шиной нулевого потенциала устройства, выход Х-го переключателя соединен с вторым входом (Х)-го 15 элемента И второй группы и вторым информационным входом (Х) -го переключателя, выход первого переключателя соединен с вторым входом нулевого элемента ИЛИ второй группы, выходы элементов И второй и третьей группы соединены соот-ветственно по модулю два второй группы, выходы сумматоров по модулю два с первого по (М)-й второй группы соединены соответственно с вторыми входами элементов ИЛИ с первого по (Х) -й второй груп пы, выходы блока определения старшего нулевого разряда соединены соответственно с управляющими входами переключателей, управляющие входы переключателей с первого по (Х)-й соединены соответственно с вторыми входами элементов И З 0 с первого по (И) -й второй группы, тактовые входы первого, второго и третьего регистров сдвига соединены с тактовым вхо дом устройства.На фиг, 1 представлена функциональная схема устройства; на фиг. 2 - функциональ- з 5 ная схема блока определения старшего йе. нулевого разряда.Устройство содержит регистр 1 сдвига, содержащий И разрядных ячеек 2 - 5, регистр 6 сдвига, содержащий М разрядныхячеек 7 - 10, регистр 11 сдвига, содержащий Х разрядных ячеек 12 - 15, регистр, 16 многочлена, содержащий Х разрядных ячеек 17 - 20, группу элементов ИЛИ 21 - 24, группу элемейтов ИЛИ 25 - 28, группу элементов И 29- 32, группу элементов 4 И 33 - 35, группу элементов И 36 - 38, группу сумматоров 3942 по модулю два, группу сумматоров 43 - 45 по модулю два, блок 46 определения старшего ненулевого разряда, переключатели 4 - 50, входы 51 - 54 коэффициентов множителя уст ройства, входы 55 - 58 коэффициентов множимого устройства, входы 59 - 62 неприводимого многочлена устройства, выходы 63 - 66 устройства, тактовый вход 67 устройства, Один из входов элементов И 33 - 35 выполнены инверсными.Блок 46 определения старшего ненулевого разряда состоит из элементов И 68 - 75. Один из входов элементов И 69 - 75 выполнены инверсными. Входы 76 - 79 являются входами блока 46. Выходы 80 - 83являются выходами блока 46. Вход 84 является входом логической единицы.Устройство работает следующим образом.Рассмотрим поле бГ(2), порождаемое неприводимым многочленом: 1(х) степени т с коэффициентами. из поля бГ(2), т. е.1(х) =1+1,+1 х+ хЯ Е 6 Г(2),1=0,1, гп - 1), 1 = 1. каждый элемент поля бГ (2 ) представляют в виде многочлена над бГ(2), степень которого меньше т, тогда умножение элементов поля друг на друга выполняется по правилам умножения, представляющим эти элементы многочленов по модулю образующего многочлена 1(х) . Пусть а (х) = =а +а, (х) а,.х , а; ЕбГ(2), 1= =0,1, в - 1 - множимое в(х) =в+в,х+ +вщ.,х , в 6 Г(2),1=0,1т - 1 - множитель, когда их произведение с(х) с,+с,х +сй-, хс е бГ(2), 1=0,1т - 1 равно с(х) =в(х) а(х) вод 1(х). т. е. с(х) =в,11, (х) +В,Ц (х) в 1.)е- (х), гдеЫ = = х 1 а (х) подх)В предлагаемом устройстве степень многочлена х) гп может быть любой, но не больше, чем разрядность регистров 1, 6, 11, 16.В исходном соястоянии регистр находится в нулевом состоянии. На входы устройства 51 О, 52 53 н-г, 54 кподаются одновременно коэффициенты многочлена в (х) в; в в причем условию в; =1 соответствует единичный потенциал на соответствующем входе, а условию в; =0 - нулевой потенциал на соответствующем входе. При этом, если гп(М, то в; =0 при 1 уп. Аналогичным образом на входы 591, 60 г, 61 , 621 устройства подаются коэффициенты многочлена 1(х), а на входы 55, 56 571 2. 581- коэффициенты много- члена а(х) и запоминаются в регистрах 16 и 6 соответственно.После того, как в регистр 16 записаны коэффициенты многочлена 1(х), на входах блока 46 определения старшего ненулевого разряда появляется слово, состоящее из нулей, кроме разряда, соответ" твующего крайней правой единице в слове, составленном из коэффициентов многочлена 1(х) . Переключатели 47 - 50, на управляющий вход которых подается эта единица, соединяют выход соответствующей разрядной ячейки регистра 6 со своим входом. На управляющие входы остальных переключателей 47 - 50 поступают нули, и они устанавливаются в положение, при котором выход каждого последующего переключателя 47 - 50 соединен с выходом предыдущего. Таким образом разрядные ячейки регистра 6, переключатели 47 - 50 элементы 33 и 38 И и сумматоры 43 и 45 по модулю два, стоящие левее этого выделенного переключателя 47 - 50 вместе с ним образуют цепь ум 10611343иожеиия на х по модулю 1(х), иа входы же сумматоров 43 - 45 по модулю два, стоящих правее выделенного переключателя 47 - 50, поступают только нули, поэтому соответствующие разрядные ячейки регистра 6 всегда обнулены.5При поступлении иа тактовый вход 67 устройства тактового импульса происходит сдвиг в регистрах 1 и 6, при этом содержащееся в регистре 6 слово из коэффициентов миогочлеиа а(х) умножается иа х по мо б дулю 1(х), одновременно иа входы элементов И 29 - 32 поступает значение коэфФициента в а в регистре 11 записывается слово. из коэффициентов ва(х). На вторые входы элементов И 29 - 32 теперь поданы коэффициенты многочлена ха(х) пюН(х). 15 Легко видеть, что иа 1-м шаге, т. е. при поступлении 1-го тактового импульса, в ячейках регистра 2 образуется миогочлеи 1.1 (х), иа выходах элементов И 29-32 и появляется миогочлен в 1 Ц (х), а в регистр.11 записывается многочлен в, 11 (х) + Ф+ в, 1.1 (х) ++ в;К -1 (х), После в-го так. тового импульса в регистре 11 будет содержаться результат умножения с(х) = =в(х) а(х) вой(х) . Дальнейшее поступление тактовых импульсов не будет влиять иа содержимое регистра 11, поскольку старшие разряды в (х) равны нулю, в 1 =О, при 1 а.Таким образом, предложенное устройство выгодно отличается от прототипа, так как с его помощью можно производить умножение в поле, порожденном любым не- приводимым многочленом. Для этого достаточно загрузить коэффициенты этого много- члена в регистр 16. Ограничение накладывается только на степень образующего многочлена поля, которая не должна превышать разрядности устройства. Это особенно удобно в тех случаях, когда устройство реализуется в интегральном исполнении или входит в состав БИС, когда доступ к цепи деления на порождающий многочлен невозможен,1061134 77 78иг,2 Редактор К, ВолощЗаказ 10041/51 ила Составитель Л.Медведеваук Техред И, Верес КорректорТираж 706 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж - 35, Раушская набд. 4/5филиал ППП Патент, г. Ужгород, уя. Проектная