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

К АВТОРСКОМУ/ ЕЛЬСТВ вч ри- ных И тораеди-с иГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1. Авторское свидетельствоВ 976440, кл. С 06 Г 7/49, 1981.2. Авторское свидетельство ССИф 922731, кл. С 06 Р 7/52, 1978(54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее два входных регистра, два дешифратора, восемь элементов ИЗИ, первый выходной регистр, сумматор по модулю два, три группы элементов ИЛИ, две группы ключевых элементо коммутатор, четыре элемента И, п чем входы первого и второго вход регистров соединены с входами.первого и второго операндов в коде табличного умножения устройства соответственно, первая группа выходов,. первого и второго дешифраторов соединена с первыми входами элементов ИЛИ первой и второй групп и с входами первого и второго элементов ИЛИ соответственно, выходы которых соединены соответственно с первым и вторым нулевыми входами сумма по модулю два, первый и второй ничные входы которого соединены выходами третьего и четвертого элементов ИЛИ, входы которых соедине с второй группой выходов первого .второго дешифраторов, и вторыми входами элементов ИЛИ первой и второй групп соответственно, выходы которых соединены с информационными входами ключевых элементов первойи второй групп соответственно, управляющие входы которых соединены свходами управления устройства, авыходы - с первой и второй группамивходов коммутатора, первая и втораягруппы выходов которого соединены спервыми и вторыми входами элементовИЛИ третьей группы и с входами пятого и шестого элементов ИЛИ соответственно, выходы которых соединеныс первыми входами всех четвертыхэлементов И, вторые входы первого итретьего элементов И соединены снулевым выходом сумматора по модулюдва, единичный выход которого соединен с вторыми входами второго и четвертого элементов И, выходы первогои второго элементов И соединены спервыми входами седьмого и восьмого элементов ИЛИ соответственно, вторыевходы которых соединены с выходамичетвертого и третьего элементовсоответственно, выход первого выходного регистра соединен с выходомустройства, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей за счет умножения комплексных чисел по модулющ=+ и; , в него введены третий.и четвертый входные регистры, дваблока умножения, два сумматора помодулю И, четвертая и пятая группыэлементов ИЛИ,две группы элементов И,И, пятый, шестой, седьмой и восьмойэлементы И, шифратор и второй выходной регистр, причем входы трегьегои четвертого .,входных регистров соединены с входами первого и второгооперандов в комплексной форме уст 11 ройства соответственно, вход коэффициента изоморфизма которого соединен с первыми входами первого и второго блоков умножения, вторые входы котррых соединены с первыми выходами третьего и четвертого входных регистров соответственно, вторые выходы которых соединены с входами первого слагаемого первого и второго сумматоров по модулю М соответственно, входы второго слагаемого которого соединены с выходами первого и второго блоков умножения соответственно, а выходы - с первыми входами элементов ИЛИ четвертой и пятой групп соответственно, вторые входы которых соединены с выходами первого и второго входных регистров соответственно, а выходы " с входами первого и второго дешифраторов соответственно, выходы элементов ИЛИ третьей группы соединены с первыми выходами элементов И первой и второй групп, вторые входы элементов И пер 66098вой группы и первые входы пятогои шестого элементов И соединены свходом управления признаком определения результата в вещественной области устройства, вход управления признаком определения результата в комп-.лексной области которого соединенс вторыми входами элементов И второйгруппы и первыми входами седьмогои восьмого элементов И, вторые входы которых соединены с выходами седьмого и восьмого элементов ИЛИ и вторыми входами пятого и шестого элементов И соответственно, выходы эле-.ментов И первой группы и выходыпятого и шестого элементов И соединены с входами первого выходного регистра, выходы элементов И второйгруппы и выходы седьмого и восьмогоэлементов И соединены с входами шифратора, выходы которого соединеныс входами второго выходного регистра,выход которого соединен с вторымвыходом устройства.Изобретение относится к вычислительной технике и может быть использовано в вычислительных устройствах, работающих в системе остаточных классов (СОК). 5Известно устройство для умножения чисел по модулю, содержащее входные регистры, дешифраторы, элементы, ИЛИ, элементы И, коммутатор, сумматоры по модулю два, ключи, шифратор,0 сумматор по модулю Р, выходной ре-. гистр; обрабатывающее по модулю как положительные, так и отрццательные числа (11.Недостатком этого устройства является невозможность обработки комплексных чисел.Наиболее близким к изобретению является устройство, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ. Известнде устройство позволяет осу. - , ществить операцию модульного умноже 25 ния двух операндов А 1 и А 2, т.е.А,А,(шод В), используя код табличного умножения (КТУ). При этом реализуется всего 0,25 части общей таблицы модульного умножения 121.Однако известное устройство позволяет производить операцию модульного умножения только в вещественной области и не позволяет производить модульного умножения в комплексной области.Цель изобретения - расширение функциональных возможностей за счет умножения комплексных чисел по модулю м= э 1 +,Поставленная цель достигается тем, что в устройстве для умножения в системе остаточных классов, содержащее два входных регистра, два дешифратора, восемь элементов ИЛИ, первый выходной регистр, сумматор по модулю два, три группы элементов ИЛИ, две группы ключевых элементов, коммутатор, четыре элемента И, причем входы первого и второго входных ре-ф11660 гистров соединены с входами первого и второго операндов в коде табличного умножения устройства соответственно, первая группа выходов перво" го и второго дешифраторов соединены. с первыми входами элементов ИЛИ первой и второй групп и с входами первого и второго элементов ИЛИ соответственно, выходы которых соединены соответственно с первым и вторым нулевым входами сумматора по модулю два, первый и второй единичные входы которого соединены с выхо" дами третьего и четвертого элементов ИЛИ, входы которых соединены с вто 15 рой группой выходов первого и второ" .го дешифраторов; и вторыми входами элементов ИЛИ первой и второй групп соответственно, выходы которых сое" динены с информационными входами ключевых элементов первой и второй групп. соответственно, управляющие . входы которых соединены с входами управления устройства, а выходы - с первой и второй группами входов ком-.25 мутатора, первая и вторая группы выходов которого соединены с первыми и вторыми входами элементов ИЛИ третьей группы и с входами пятого и шестого элементов ИЛИ соответст-венно, выходы который соединены с первыми входами всех четырех элементов И, вторые, входы первого и третьего элементов И соединены с нулевым выходом сумматора по модулю, два, 35 единичный выход которого соединен с вторыми входами второго и четвертога элементов И, выходы первого и второго элементов И соединены с первыми входами седьмого и восьмого элемен О тов ИЛИ соответственно, вторыевходы которых соединены с выходами четвертого и третьего элементов И соответственно, .выход первого выходного регистра соединен с выходомРустройства, введены третий и четвертый входные регистры, два блока умножения, два сумматора по модулю К; четвертая и пятая группы элемен 50 тов ИЛИ; две группы элементов И, пятый, шестой, седьмой и восьмой элементы И, шифратор и второй выходной регистр, причем входы третьего и четвертого входных регистров соединены с входами первого и второго операндов в комплексной форме уст" ройства соответственно, вход коэффи-:, циента изоморфизма которого соединен 98 4с первыми входами первого и второгоблоков умножения, вторые входы которых соединены с первыми выходамитретьего и четвертого входных регистров соответственно, вторые выходыкоторых соединены с входами первогослагаемого первого и второгосумматоров по модулю И соответственно,входы второго слагаемого которогосоединены с выходами первого и вто-рого блоков умножения соответствен"но, а выходы - с первыми входамиэлементов ИЛИ четвертой и пятой группсоответственно, вторые входы которыхсоединены с выходами первого и второго входных регистров соответственно, а выходы - с входами первого ивторого дешифраторов соответственно,выходы элементов ИЛИ третьей группысоединены с первыми входами элементов И первой и второй групп, вторыевходы элементов И первой группы ипервые входы пятого и шестого элемен-.тов И соединены с входом управленияпризнаком определения результата в вещественной области устройства, вход уп-равления признаком определения результата в комплексной области которого соединен с вторыми входами элементов Ивторой группы и первыми входами седьмого и восьмого элементов И, вторыевходы которых соединены с выходамиседьмого и.восьмого элементов ИЛИи вторыми входами пятого и шестогоэлементов И соответственно, выходыэлементов И первой группы и выходыпятого и шестого элементов И соединены с входами первого выходногорегистра, выходы элементов И второйгруппы и выходы седьмого и восьмогоэлементов И соединены с входамишифратора, выходы которого соединеныс входами второго выходного регистра, выход которого соединен с вторымвыходом устройства. На фиг, 1-3 представлена структурная схема устройства для умножения в системе остаточных классов.Устройство содержит входы 1 и 2 первого и второго операндов в коде табличного умножения устройства, входы 3 и 4 первого и второго операндов в комплексной Форме устройства, первый 5, второй 6, третий 7, четвертый 8 входные регистры, первый 9, и второй 10 блоки умножения, вход 11 коэффициента изоморфизма устройст ва, первый 12 и второй 13 сумматоры5 1166по модулю И, группы 14-18 элементовИЛИ, первый 19 и второй 20 дешифраторы, сумматор 21 по модулю два, элементы ИЛИ 22-29, первая 30 и вторая31 группы ключевых элементов, коммутатор 32, элементы И 33-40, первая41 и вторая 42 группы элементов И,шифратор 43, первый 44 и второй 45выходные регистры, входы 46 управления устройства, входы 47 и 48 управ Оления признаком определения результата в вещественной и комплекснойобластях устройства, первый 49 и,второй 50 выходы устройства,ИнФормационные входы 1-4 устройст ва подключены к входам соответственно первого 5, второго 6, третьего 7и четвертого 8 входных регистров.Первые выходы третьего 7 и четвертого 8 входных регистров подключены к 20первым входам соответственно первого9 и второго 10 блоков умножения, квторым входам которых подключен.вход 11 подачи значения коэффициента изоморфизма. Второй выход 25третьего входного регистра 7 и выходпервого блока 9 умножения подключены к входам первого сумматора 12 помодулю Б, выходы которого одновременно с выходами первого входного ЗОрегистра 5 через группу элементовИЛИ 14 подключены к входам первогодешифратора 19. Второй выход четвертого входного регистра 8 и выходвторого блока 10 умножения подключенк входам второго сумматора 13 по модулю В, выходы которого одновременно с выходами второго входного регистра 6 через группу элементов:.ИЛИ 15 подключены к входам второгоИ дешифратора 20. Первая (1 - , ) И+1и вторая ( в . - В - 1) группы вы 2ходов,дешифратора 19 через соответ.ственно элементы ИЛИ 22 и 24 подключены,соответственно к первым нулевому и единичному входам сумматора 21 по модулю два, одновременно пары (сумма значений, присвоенная каждой 50паре выходов равна И) выходов дешифратора 19 через группу элементов ИЛИ 16, через ключевые элементы 30 подключены к первой группе входовМ55 коммутатора 32. Первая (1 -- -)И+ 1и вторая ( -- М - 1) группы вы 21 098 6ходов дешифратора 20 через соответственно элементы ИЛИ 23 и 25 подключецы соответственно к вторым нулевому и единичному входам сумматора 21 по модулю два, одновременнопары (сумма значений, присвоеннаякаждой паре выходов равна Н) выходовдешифратора 20 через группу элементоп ИЛИ 17 через ключевые элементы 31 подключены к второй группе входов коммутатора 32. К входам управления ключевых элементов 30 и 31 подключены входы 46 управления устройства.Н - 1 И - 1 Первая (1 -- , - ) и вторая (2 2М - 1) группы выходов коммутатора 32 подключены к входам элементов ИЛИ 26 и 27 соответственно и одновременно пары (сумма значений присвоена каждой паре выходов равна И) выходовкоммутатора 32 через элементы ИЛИ 18 подключены к первым входам соответствующих элементов И 4 1 и 42 групп. Выход элемента 26 подключен к первым входам элементов И 33 и 34, а выход элемента ИЛИ 27 подключен к первым входам элементов И 35 и 36. Нулевой выход сумматора 21 подключен к вторым входам элементов И 33 и 35, а единичный выход сумматора 21к вторым входам элементов И 34 и ЗЬ. Выходы элементов И 33, ЗЬ и 34,35 подключены соответственно к входам элементов ИЛИ 28 и 29, выходы которых .подключены к первым входам соот-. ветствующих элементов И 37-40. К вторым входам элементов И 31 группы и элементов И 37 и 38 подключен вход 47 управления, а к вторым входам элементов И 42 группы и элементов И 39 и 40 - вход 48 управления. Выходы элементов И 42 группы и элементов И 39 и 40 подключены к входам шифратора 43. Выходы элементов И 41 группы и элементов И 37 и 38 подключены к входам первого выходного регистра 44, а выходы шифратора 43 подключены к входам второго выходного регистра 45, выходы 49 и 50 кото-. рых являются выходами устройства. Входные операнды в комплексной форме представлены в виде А 1 =.а ++ Ь;, А, = а, + Ь а модуль имеет вид ш = р + л . При этом наибольший общий делитель (НОД) компонент р, ф модуля ш равен единице, т.е.(р, ) = 1. В соответствии с первой фундаментальной теоремой Гаусса позаданному комплексному модулю г,норма которого равна М = р + ). ипри НОД (р, 9) = 1 комплексное числоА = а + Ъ 1 сравнимо с одним и только одним вычетом из ряда О, 1, 2, 5М - 1, т.е. А = Ь(вод в), где Ь -вещественное целое число. Определение результата операции умножениякомплексных чисел А , А, по модулюв можно заменить выполнением этой 10операции над соответствующими имвещественными вычетами Ь Ь, по модулю М, т.е. Ь,Ь,(вой М). Таким образом, А 1, А,: Ь(вос в),где Ь ==Ь, (гюд М), (а + ЯЬ,) - Ь,(вод М),где Я = 1 - Чр - коэффициент изоморфизма, Значения целых чисел 0 и Чопределяются из равенства Бр - Чр =1.20Изоморфизм между комплексными числами и их вещественными вычетамидает возможность реализовать операцию модульного умножения в комплексной области посредством алгоритмов, 25реалиэукцих операцию модульного умножения в вещественной области. Впредлагаемом устройстве используются свойства симметрии арифметическойтаблицы относительно диагонали, вер- ЗОтикали и горизонтали. Это и определяет возможность реализации в схемемодульного умножения только 0,25полной таблицы. .ри этом используется код табличного умножения (КТУ).Блоки 9 и 1 О умножения служатЭ 5. для реализации операции у Ь = (цс -Чр) Ь (вод М). Сумматоры 12 и 13реализуют операцию (а + Ь) вой М..Дешифраторы 19 и 20 служат для преобразования чисел из двоичного кода в десятичный.Сумматор 2 1 по модулю два реализует операцию 9 ( й Ь + 9 Ь, ) вой 2где Ь = (РЬ х ), Ь, =,(ЯЬ 2 У х 2) 45операнды в КТУ (таблица).Отметим, чтоЬ 1, Ь, 6 М - 1,М - 11 хе, х 6 2, ЯЬ 1, аЬ, - индексы КТУ,(второй квадрант) . Количество входов в каждой группе входов коммутаМ - 1тора 32 равно , а количество выходов равно М.Иифратор 43 служит для определения комплексного вычета хх + у 1, изоморфного вещественному вычету Ь = Ь,Ь (вой М), по значению й - (аЬ + ЛЬ )шос 2 или 2 = (1 + + ( ЯЬ, + рЬ;.)шой 2)шой 2 и,по значению х = х, х (шой М) или хЯ -- хх,(вод М) и представляет собой М - 1( - + 2) - входовое ПЗУ. Подевеот 2во выходов шифратора 43 равно количеству возможных наименьших вычетов по модулю в = р + ф Устройство работает следующим образом.Определение результата операции модульного умножения в вещественной области (присутствует сигнал со входа 47), т.е. ЬЬ (вос М).На первый 1 и второй 2 входы уст- . ройства поступают соответственновходные операнды Ь е = ( ЙЬ х.,), Ь, = ( Я Ь х,) в двоичном коде, которые через соответственно первый 5 и второй 6 регистры, через элемен- . ты ИЛИ группы 14 и 15 поступают на соответствующие дешифраторы 19 и 20. С выхода дешифраторов 19 и 20 значения х, и х, через соответствующиеэлементы ИЛИ групп 16 и 17, ключевые элементы групп 30 и 31 поступают на входы коммутатора 32 (сигнал входа28 открывает соответствующую пару ключевых элементов групп 30 и 31). Выходной сигнал коммутатора 32, соответствующий значению х,х (шод М), через элементы ИЛИ группы 18, через открытый соответствующий элемент И группы 41 поступает во входной ре гистр 44. Выходной сигнал сумматора 21, соответствующий значению (Я Ь, + + Р Ь )пюй 2, открывает один из элементов И 33-36, через который выходной сигнал одного из элементов ИЛИ 26 и 27 через элементы ИЛИ 28 и 29, через соответствующий открытый элемент И .37 илн 38 поступает на нулевой или единичный вход регистра 44, Таким образом, в выходном регистре 44 содержится результат модульного умножения в КТУ, т.е. ЬЬ,(вой М)ееЬ 1 + ЯЬ 2 )вос е хх 2 (гпо М) )1166 Ь+ 15с х х (вой И) 4 И - 1.Определение результата операциимодульного умножения в комплекснойобласти (присутствует сигнал со вхо-,да 48), т.е. А А (вос в).По входным шийам 3 и 4 во входныерегистры 7 и 8 заносятся соотвест 1венно числа А = а + Ьс 1 и А,а, + Ь 1. Значение Ъ в двоичном15коде поступает на первый вход первогоблока 9 умножения, на второй. входкоторого с входа 1 1 в двоичном кодепоступает значение коэффициента изоморфизма= П - Чр, Выходной сиг 20нал блока 9 соответствующий значению Ь (вос 1 И), поступает на первыйвход сумматора 12, на второй входкоторого поступает значение а в двоичном коде. С выхода сумматора 12на элементы ИЛИ группы 14 поступаетзначение (а+ Ь, О ) = Ь,(вос 1 И) .Аналогично, получим на выходе сумматора 13 значение Ь (вос 1 Н). Далееустройство работает как описано вьппе.00001 13 01101 1 00010 14 01110 1 01100 00001000100001100100 01011 01010 01001 01000 00011 15 01111 00100 16 10000 00101 17 10001 00110 18 10010 00101 00111 00110 10011 00110 00111 19 0 00111 00101 00100 00011 00010 01000 20 10100 01001 21 10101 01010 22 10110 01011 23 10111 01000 01001 10 01010 01011 01100 24 11000 1 00001 01100 К при 14 х,х, (вод И) с . илиЬ 1 Ь,(вос 1 й) И 1 + ( й Ь+ а Ь,)вос 1 2)вой 2, И - х,х, (вос 1 Я при 098 10Таким образом, значение Ь 1 Ь (вой И) в КТУ через открытые элементы И груп" пы 42 и элементы И 39 или 40 поступает на входы шифратора 43, где по значениям ( й Ь + 17 Ь,)вод 2 (или по значению (1 + ( Я Ь, + Я Ь,)тос 1 2) вой 2) и х,хивой И)(или по значению И- - х, х,(вод М) ) выбирается комплексное число, изоморфное вещественному вычету ЬсЬ,(вос 1 И). В этом случае в регистре 45 содержится результат операции ЛА,(вос 1 в). Техническое преимущество изобретения, по сравнению с. известным состоит в существенном расширении функциональных возможностей за счет цополнительного выполнения операции модульного умножения в комплексной области. Положительный эффект заключается в уменьшении количестваоборудования за счет совмещения водном устройстве (посредством одногокоммутатора) выполнения операциимодульного умножения как в вещественной, так и в комплексной областях,что приводит к уменьшению стоимостимашинной операции модульного умножения и повьппению надежности ЭВМ в СОК.116 б 098 Составитель Е.Захарченкодактор Г.Волкова. Техред А.Бабинец Корректор С.Черни Заказ 4310/4 ППП "Патент", г. Ужгор Проектна Фи 3 Тираж 710ВНИИПИ Государственногопо делам изобретений 113035, Москва, Ж, Раушс Подписноекомитета СССи открытийая наб., д,