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

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

входов третьего вычитателя по модулю ( , вторая группа входов которого соединена с соответствующими младшими разрядными выходами второго квадратора МО модулю , выход передачи заема второго вычитателя по модулю (J соединен с входом приема заема третьего вычитателя по модулю О , разрядные выходы которого соединены соответственно с первой группой входов третьего сумматора по модулю Q , вторая группа входов которого соединена с выходами элементов ИЛИ группы, разрядные выходы второгб вычитателя по модулю CJ соединены соответственно с входами второго сумматора по модулю CJ , вход переноса которого соединен с выходом переноса третьего сумматора по модулю , разрядные выходы которого соединены с младшими разрядными выходами устройства, разрядные выходы второго сумматора по модулю соединены со старшими разрядными выходами устройства.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ОДНОРАЗРЯДНЫХ ( -ИЧНЫХ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее первьй сумматор .по модулю CJ , первый и второй вычитатели по модулю о , первьй и второй квадраторы по модулю с , первый блок деления на константу, причем разрядные выходы первого сумматора по модулю и первого вычитателя по модулю q подключены к входам первого ив второго квадраторов по модулю с соответственно, о т личающееся тем, что, с целью расширения области применения путем формирования результата произведения как в непозиционном, так и позиционном представлении, в устройство введены второй блок деледил на константу, второй и третий сумматоры по модулю CJ , третий вычитатель по модулю о , первыйj второй :и третий блоки умножения на константу, первая, вторая и третья группы элементов И, группа элементов ИЛИ, блок управления коррекцией, содержащий первьй и второй элементы НЕ, первый, второй и третий элементы И, выходы которых соединены с первыми входами элементов И соответственно первой, второй и третьей групп, первый информйционный вход устройства соединен с входом первого блока деления на константу, разрядные выходы которого соединены с.входами первого блока умноже-.ния на константу, с первой группой входов первого сумматора по модулю ( , с первой группой входов первого вычитателя по модулю ( , вторая группа входов которого соединена с второй группой входов первого сумматора по модулю ( , с входами второго . блока умножения на константу и с разрядными выходами второго блока деления на константу, вход которого сое(Л динен с вторым информационным входом устройства, выход признака четности , числа второго блока деления на константу соединен с входом первого элемента НЕ и первыми входами первого и второго элементов И блока управления коррекцией, входвторого элемента НЕ которого соединен с выходом признака четности числа первого блока деления на константу, с вторым входом 9д первого элемента И и первым входом третьего элемента И блока управления ;о коррекцией, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ, вьпсод второго элемента НЕ соединен с вторьм входом BTOpoJ-o элемента И блока управления коррекцией, разрядные выходы первого сумматора по модулю ( соединены с входами третьего блока умножения на константу, разрядные выходы которого соединены соответственно с вторыми входами элементов И третьей группы.

Изобретение относится к вычислительной технике и может быть использовано при разработке специализированных арифметических устройств. Известно арифметическое устройств в системе остаточных классов, содержащее регистры числа, регистры результата, табличный сумматор и квадратор, соединенные соответствующими связями ij . Данное устройство выполняет перемножение двух операндов А и В по модулю Р по следующему алгоритму (А+В)2 (А-В)2 AB(mod Р). - , Недостатком устройства является невозможность позиционного кода значения результата произведения Наиболее близким к предлагаемому по техническому решению является ква ратичный умножитель по модулю Р, содержащий сумматор и первый вычитатель по модулю Р, первые и вторые входы которых соответственно объединентз и являются первым и вторым вхо-. дами устройства, первьш и второй квадраторы, входами подключенные к выходам соответственно сумматора и вычитателя по модулю Р, а выходами к входам второго вычитателя по модулю Р, выход которого подключен к входу блока деления на константу, выход которого является выходом устройства 2, Д:;нное устройство выполняет умножение двух-чисел по модулю Р. В качестве модуля принято простое (или нечетное) число,близкое к 2, т.е. к байту. Недостатком устройства является невозможность получения результата произведения в позиционном Cj, -ичном коде (устройство формирует только младший разряд произведения по модулю Р) . Целью изобретения является расширение области применения путем формирования в устройстве младшего с. -ичного (с весом о) и. старшего Q - ичного (с весом Q ) разрядов произведения, так как двухразрядное представ3.1 ление результата произведения дает возможность использовать устройство как для умножения чисел по модулю (используется только младший разряд произведения), так и для умножения одноразряднььх а -ичных чисел (используется младший и старший разряд произведения). Поставленная цель достигается тем что в устройство, содержащее первый сумматор по модулю с , первый и второй вычитатели по модулю q , пер вый и второй квадраторы по модулю о первый блок деления на Константу, приче разрядные выходы первого сумматора по модулю с и первого вы читателя по модулю Q подключены к входам первого-и второго квадраторов по модулю о соответственно, введены второй блок деления на константу, второй и третий сумматоры по модулю CJ , третий вычитатель по модулю с , первьй, второй и третий блоки умножения наконстанту, первая вторая и третья группы элементов И, группа элементов ИЛИ, блок управления коррекцией, содержащий первый и второй элементы НЕ, первый, второй и третий элементы И, выходы которых соединены с первыми входами элементов И соответственно первой, второй и третьей групп, первый информационный вход устройства соединен с входом первого блока деления на констан ту, разрядные выходы которого соединены с входами первого блока умножения на константу, с первой группой входов первого сумматора по модулю о , с первой группой входов первого вычитателя по модулю Q , вторая группа входов которого соединена с второй группой входов первого сумматора по модулю о , с нходами второго блока умножения на константу и с разрядными выходами второго блока деления на константу, вход которого соединен с вторым информационным входом устройства, выход признака четности числа второго блока деления на константу соединен с входом первого элемента НЕ и первыми входами первого и второго элементов И блока управления коррекцией, вход второго элемента НЕ которого соединен с выходом признака четности числа первого блока деления на константу, с вторым входом первого элемента И и первым входом третьего элемента И 4 блока управления коррекцией, второй вход-третьего элемента И которого соединен с выходом первого элемента НЕ, выход второго элемента НЕ соединен с вторым входом второго элемента И блока управления коррекцией, разрядные выходы первого сумматора по модулю соединены с входами третьего блока умножения на константу, разрядные выходы которого соединены соответственно с вторыми входами элементов И третьей группы, выхрды которых соединены соответственно с первыми входами элементов ИЛИ группы, вторые входы которых соединены соответственно с выходами элементов И первой группы, вторые входы которых соединены соответственно с разрядными выходами первого блока умножения на константу, третьи входы элементов ИЛИ группы соединены соответственно с выходами элементов И второй, группы, вторые входы которых соединены соответственно с разрядными выходами второго блока умножения на константу, разрядные выходы первого вычитателя по модулю соединены со входами второго квадратора по модулю о , старшие разрядные выходы которого соединены соответственно с первой группой входов второго вычитателя по модулю о , вторая группа входов ,которого соединена соответственно со старшими разрядными выходами первого квадратора по модулю Q , младшие разрядные выходы которого соединены с первой группой входов третьего вычитателя по модулю Q , . вторая группа входов которого соединена с соответствующими младшими разрядными выходами второго квадратора по модулю и , выход передачи заема второго вычитателя по модулю Q соединен с входом приема заема третьего вычитателя по модулю ( , разрядные выходы которого соединены со- , ответственно с первой группой входов третьего сумматора по модулю q , вторая группа входов которого соединена с выходами элементов ИЛИ группы, разрядные выходы второго вычитателя по модулю о соединены соответственно с входами второго сумматора по модулю о , вход переноса которого соединен с выходом переноса третьего сумматора по модулю с , разрядные выxojD;ы которого соединены с младшими разрядными выходами устSройства, разрядные выходы второго сумматора по модулю о соединены со старшими разрядными выходами.уст ройства. На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема бл ка управления коррекцией. Устройство содержит первый 1 и второй 2 блоки деления на константу, блок 3 управления коррекцией, .первый 4, второй 5 и третий 6 сумматоры по модулю о , первый 7, второй 8 и третий 9 вычитателй по моду лю о , первый 10 и второй 11 квадр торы по модулю CJ , первый 12, второй 13 и т-ретий 14 блоки умножения на константу, первую 15, вторую 16 и третью 17 группы элементов И, гру пу элементов ИЛИ 18. ..иВходы первого 1 и второго 2 блоковпгб,«;ления на константу являются информационными входами устройства и 20 о -ичных чисел. Их выходы чет ности подключены к входам блока 3 управления коррекцией, а разрядные к первой группе входов первого сумматора 4 по модулю (J , к первой гр ,, .пе входов первого вычитателя 7 по . «МОДУЛЮ ( , к входам первого блока умножения на константу и соответственно ко второй группе входов перво го сумматора 4 по модулю о , к второй группе входов Первого вычитате,ля 7 по модулю CJ , к входам второ го блока 13 умножения на константу. Разрядные выходы первого сумматора 4 по модулю о подключены к входам первого квадратора 10 и третьего бло ка 14 умножения на константу. Разря ные выходы первого вычитателя 7 по модулю ( подключены к входам вто рого квадратора 11. Старшие разрядные выходы квадраторов 10 и 11 подключены к входам второго вычитателя по модулю 8, а младшие разрядные выходы квадраторов 10 и 11 к входам .третьего вычитателя 9 по модулю Q . Вычитателй 8 и 9 соединены -между собой цепью переноса. Разрядные выходы -вычитателей 8 и 9 подключены соответственно к входу второго сумматора 5 по модулю ( и к первой группе вхо,иов треть.его сумматора 6 по модулю С) , к второй группе входо выходы элеменкоторого подключены тов ИЛИ 18. Вхогм элементов ИЛИ 18 подключены к выходам элементов И 15 16 и 17. Первые входы элементов И 15 9 16 и 17 соответственно объединены и подключены к выходам блока 3 управления коррекцией. ВыхоДы 21 устройства являются выходами кода старшего разряда произведения с весом о , выходы 22 - выходами кода младшего разряда произведения с весом q . В основу работы устройства положена формула , (А-(-В)2 - (А-в)г А ц где А и В - два q -йчных числа, приведенная к виду . /А-Л, e-uaf (Л-й. iT/T гдеС.А,|.о А.|.,,.д.д 2Cfi при u, &2 1 C-DB при й 1,U2 0 CtD A при fc,,rO, U2 1 (2) .при AI O j где Д , Л.2 - показатели четности соответственно чисел А и В (признаком четности числа является равенство нулю U, или Л 2 ) Для проведения чисел А и В к четному виду, чтобы выполнить их деление на два, из них приходится вычитать величины А, или Ья принимающие значение О или 1. Блок 3 предназначен для того, чтобы на основе значений и A,j выработать три функции f, Д, fug которые определяют величину поправки Е, прибавляемой к результату. Блоки 1 и 2 деления на константу приводят исходные числа к четному виду, делят их на два и формируют величины U, и Дл которые подаются на блок 3 для выработки поправки в соответствии с (2). Блок 3 (фиг. 2) включает в себя два элемента НЕ 23 и 24 и три элемента И 25, 26 и 27, входы 28 и 29 соот: етственно, выходы 30, 31 и 32. Сумматор 4 по модулю вычисляА в т величину С --- + о вычитаель 7 по модулю i величину D А в -т- - :) Квадраторы 10 и 11 выисляют соответственно С и D, блои умножения 12, .13, 14 -. соответственно величины 2-х-,2 -2- и 2С+1 ычитателй 8 и 9 по мрдулю CJ вьгчисляют величину С D. причем на вычитателе 8 формируется старший разряд с весом а , а на вычитателе 9 младший разряд с весом о , Сумматоры 5 и 6 по модулю ( с учетом поправки Е формируют старший и младший ( -ичные разряды произведения А-В. Предварительно деление,исходных чисел на два связано с тем, что результат их суммирования не должен выходить за пределы неизбыточного арифметического диапазона, определяемого величиной Q . В этом случае все дальнейшие блоки устройства ста новятся конструктивно более простыми, особенно при реализации их в виде таблично-матричных схем-. Устройство работает следующим образом., Исходные числа Л и В в унитарном коде поступают на входы блоков 1 и деления на константу, в которьк при водится к четному виду и делятся на два. На выходах четности блоков 1 2 формируются сигналы л,.и й,,, на разрядных - величины -г- и -гкоторые поступают на соответствующи входы сумматора 4 по модулю о и вычитателя 7 по модулю q , где вь1ч ляются величины С и D соответственн Одновременно величина А /2 поступае на вход первого блока 12 умножения на константу, где умножается на два и превращается в А . Величина в блоке 13 превращается в В .С выходов блоков 4 и 7 величины С и D соответственно поступают на входы ква раторов 10 и 11, где преобразуются в величиныС и П. Величина С, кроме того, поступает на вход третьего блока 14 умножения на константу, где преобразуется к виду 2С+1. Квадраторы 10 и 11 устроены таким образом, что на их выходах величина, возведенная в квадрат, получается в виде старшего разряда с весом ( ив виде м гаДшего разряда с весом q . Старшие и младшие ичные разряды величин С и D с выходов соответствующих квадратбров поступают на вычитатели 8 и 9 по модулю старших и младших разрядов соответственно. Между вычитателями8 и 9 существует цепь переноса, по которой в случае необходимости заема из вычитателя 8 старшего разряда пересылается единица в вычитатель9 младшего разряда,. Результат вычитания С - D с выходов вычитателей 8 и 9 поступает на сумматоры старших 5 и младших 6 разрядов, где производится коррекция произведения на величину поправки Е, поступающей в сумматор младшего разряда 6 через группу элементов ИЛИ 18 с выхода одной из групп элементов И 15, 16, 17, управляемых управляющими выходами блока 3. В результате на сумматорах 5 и 6 образуетс.я окончательный , результат произведения в виде старшего С весом а и младшего с весом Q разрядов соответственно. Таким образом, предлагаемое изобр етение позволяет расширить функциональные возможности устройства.

21

I

22

риг.

29 29

ц

V

30

31 (put, 2 32