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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

09) (И) ЗСЮ С 06 F 7 49

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3438916/18-24

: (22) 14.05.82 (46) 30.06.84. Бюл. Ф 24 (72) В. Г. Евстигнеев, P.Ñ. Белова, .. А.С.Новожилов и В.Н.Сведе-Швец (71) Московский институт инженеров гражданской авиации (53) 681.325(088.8) .:f56) 1, Авторское свидетельство СССР

У 352275, кл.. С 06 F 7/38, 1972.

2. ТИИЭР, т. 68, Ф 4, 1980, с. 114-116, рис. 3 (прототип) . (54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ОДНОРАЗРЯДНЫХ Ч, -ИЧНЫХ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее первый сумматор,rto модулю О, первый и второй вычитатели по модулю 0 первый и второй квадраторы по модулю с, первый блок деления на константу, причем разрядные выходы первого сумматора по модулю и первого вычитателя по модулю q подключены к входам первого ив втс Гого квадраторов по модулю q соответственно, о тличающееся тем, что, с целью расширения области применения путем формирования результата произведения как в непозиционном, так и позиционном представлении, в устройство введены второй блок деления на константу, второй и третий сумматоры по модулю, третий вычитатель по модулю g, первый, второй:и третий блоки умножения на константу, первая, вторая и третья группы элементов И, группа элементов ИЛИ, блок управления коррекцией, содержащий первый и второй элементы НЕ, первый, второй и третий элементы И, выходы которых соединены с первыми входами элементов И соответственно первой, второй и третьей групп, первый информационный вход устройства соединен с вхо-. дом первого блока деления на константу, разрядные выходы которого соединены с,входами первого блока умножения на константу, с первой группой входов первого сумматора по модулю, с первой группой входов первого вычитателя по модулю, вторая группа входов которого соединена с второй группой входов первого сумматора по модулю о, с входами второго блока умножения на константу и с разрядными выходами второго блока деле- Р9 ния на константу, вход которого соединен о втором информационным входом (/) устройства, выход признака четности числа второго блока деления на константу соединен с входом первого элемента НЕ и первыми входами первого и второго элементов И блока управления коррекцией, вход второго эле мента НЕ которого соединен с выходом признака четности числа первого блока деления на константу, с вторым входом первого элемента И и первым входом третьего элемента И блока управления коррекцией, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ, выход второго л элемента НЕ соединен с вторьм входом второго элемента И блока управления р» коррекцией, разрядные выходы первого сумматора по модулю (соединены с входами третьего блока умножения на. константу, разрядные выходы которого соединены соответственно с вторыми входами элементов И третьей группы, 11006 выходы которых соединены соответственно с первыми входами элементов ИЛИ группы, вторые входы которых соединены соответственно с выходами элементов И первой группы, вторые входы которых соединены соответственно с разрядными выходами первого блока умножения на константу, третьи входы элементов ИЛИ группы соединены соответственно с выходами элементов И второй группы, вторые входы которых соединены соответственно с разрядными выходами второго блока умножения на константу, разрядные выходы первого вычитателя по модулю q соединены с входами второго квадратора по модулю 0,старшие разрядные выходы которого соединены соответственно с первой группой входов второго вычитателя по модулю 0, вторая группа входов которого соединена соответственно со старшими разрядными выходами первого квадратора по модулю 0, младшие разрядные выходы которого соединены с первой группой

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

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

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

Данное устройство выполняет перемножение двух операндов А и В по модулю P по следующему алгоритму (А+В) (А-В)2

AB(mod Р). I5

4 4

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

Наиболее близким к предлагаемому 20 по техническому решению является квадратичный умножитель по модулю Р, со/ держащий сумматор и первый вычитатель rio модулю Р, первые и вторые входы которых соответственно объединены и являются первым и вторым вхо-, 2

Лами устройства, первый и второй квадраторы, входами подключенные к выходам соответственно сумматора и вычитателя по модулю Р, а выходами-— к входам второго. вычитателя по моду-. лю P выход которого подключен к входу блока деления на константу, выход которого является выходом устройства (2), Д;:нное устройство выполняет умножение двух чисел по модулю P. В качестве модуля принято простое (или нечетное) число, близкое к 2, т.е.

8 к байту.

Недостатком устройства является невозможность получения результата произведения в позиционном 0. -ичном коде (устройство формирует только младший разряд произведения по модулю P).

Целью изобретения является расширение области применения путем формирования в устройстве младшего . -ичного (с весом с ) и. старшего g ично0

ro (с весом о ) разрядов произведения, так как двухразрядное представI l00b t ление результата произведения дает возможность использовать устройство как для умножения чисел по модулю (используется только младший разряд произведения), так и для умножения одноразрядных 0 -ичных чисел (используется младший и старший разряд произведения).

Поставленная цель достигается тем, что в устройство, содержащее первый сумматор по модулю с, первый и второй вычитатели по модулю g, первый и второй квадраторы по модулю 0 первый блок деления на константу, 15 причем разрядные выходы первого сумматора по модулю и первого вычитателя по модулю 0 подключены к входам первого.и второго квадрато\ ров по модулю 0 соответственно, - %6 20

Введены второй блок деления на константу, второй и третий сумматоры по модулю q, третий вычитатель по модулю 0, первый, второй и третий блоки умножения на константу, первая

25 вторая и третья группы элементов И, группа элементов ИЛИ, блок управления коррекцией, содержащий первый и второй элементы НЕ, первый, второй и третий элементы И, выходы которых с соединены с первыми "входами элементов И соответственно первой, второй и третьей групп, первый информационный вход устройства соединен с входом первого блока деления на константу, разрядные выходы которого соеди- З5 иены с входами первого блока умножения на константу, с первой группой входов первого сумматора по модулю с1., с первой группой входов первого вычитателя по модулю q вто- 40 рая группа входов которого соединена с второй группой входов первого сумматора по модулю g, c входами второго блока умножения на константу и с разрядными выходами второго блока 45 деления на константу, вход которого соединен с вторым информационным входом устройства, выход признака четности числа второго блока деленияна константу соединен с входом первого элемента НЕ и первыми входами первого и второго элементов И блока управления коррекцией, вход второго элемента НЕ которого соединен с выходом признака четности числа пер- 55 вого блока деления на константу, с вторым входом первого элемента И и первым входом третьего элемента И

9 4 блока управления коррекЦией, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ, выход второго элемента НЕ соединен с вторым входом второго элемента И блока управления коррекцией, разрядные выходы первого сумматора по модулю ц соединены с входами третьего блока умножения на константу, разрядные выходы которого соединены соответственно с вторыми входами элементов И третьей группы, выходы которых соединены соответственно с первыми входами элементов ИЛИ группы, вторые входы которых соединены соответственно с выходами элементов И первой группы, вторые входы которых соединены соответственно с разрядными выходами первого блока умножения на константу, третьи входы элементов ИЛИ группы соединены соответственно с выходами элементов И второй. группы, вторые входы которых соединены соответственно с разрядными выходами второго блока умножения на константу, разрядные выходы первого вычитателя по модулю g соединены со входами второго квадратора по модулю 0, старшие разрядные выходы которого соединены соответственно с первой группой входов второго вычитателя по модулю 0, вторая группа входов, которого соединена соответственно со старшими разрядными выходами первого квадратора по модулю младшие разрядные выходы которого соединены с первой группой входов третьего вычитателя по модулю о вторая группа входов которого соединена с соответствующими младшими разрядными выходами второго квадраторапо модулю q,,выход передачи заема второго вычитателя по модулю 0 соединен с входом приема заема тре- тьего вычитателя по модулю Q разрядные выходы которого соединены со-, ответственно с первой группой входов третьего сумматора по модулю а, вторая группа входов которого соединена с выходами элементов ИЛИ группы, разрядные выходы второго вычитателя по модулю q соединены соответственно с входами второго сумматора по модулю, вход переноса которого соединен с выходом переноса третьего сумматора по модулю разрядные выходы которого соединены с младшими разрядными выходами уст1100619 (А+В) - (А-В)

А, В

К ройства, разрядные выходы второго сумматора по модулю 0 соединены со старшими разрядными выходами .устройства.

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

Устройство содержит первый 1 и второй 2 блоки деления на константу, блок 3 управления коррекцией, 10 .первый 4, второй 5 и третий 6 сумматоры по модулю q, первый 7, второй 8 и третий 9 вычитатели по модулю ь, первый 10 и второй 11 квадраторы по модулю q первый 12, второй 13 и третий 14 блоки умножения на константу, первую 15, вторую 16 и третью 17 группы элементов И, группу элементов ИЛИ 18.., Входы первого I и второго 2 блоковп@еления на константу являются информационными входами устройства 19 и 20 -ичных чисел. Их выходы четности подключены к входам блока 3 управления коррекцией, а разрядные к первой группе входов первого сумматора 4 по модулю 0, к первой груп,, пе входов первого вычитателя 7 по

30 .уодулю 0, к входам первого блока 12 умножения на константу и соответственно ко второй группе входов первого сумматора 4 по модулю g к второй группе входов первого вычитате,ля 7 по модулю о, к входам второго блока 13 умножения на константу.

> ъ

Разрядные выходы первого сумматора 4 по модулю 0 подключены к входам первого квадратора 10 и третьего блока 14 умножения на константу. Разряд40 ные выходы первого вычитателя 7 по модулю О подключены к входам второго квадратора 11. Старшие разрядные выходы квадраторов 10 и 11 подключены к входам второго вычитателя

45 по модулю 8, а младшие разрядные выходы квадраторов 10 и 11 к входам .третьего вычитателя 9 по модулю 0

Вычитатели 8 и 9 соединены между собой цепью переноса. Разрядные выходы вычитателей 8 и 9 подключены

50 соответственно к вх, ду второго сумматора 5 по модулю и к первой группе входов третьего сумматора 6 по модулю, к второй группе входов которого подключены выходы элементов ИПИ 18. Вхогы элементов ИЛИ 18 подключены к выходам элементов И 15, 16 и 1i. Первые входы элементов И 15, 16 и .17 соответственно объединены и подключены к выходам блока 3 управления коррекцией. Выходы 21 устройства являются выходами кода старшего разряда произведения с весом выходы 22 — выходами кода младшего разряда произведения с весом gO .

В основу работы устройства положе. на формула где А и  — два -ичных числа, приведенная к виду

А-Ь, 8-Ь2 А-Ь 8-ЬЯ г А В . A 8 1

С-2 — ) D= — - — A =А-Ь В = В-Д

2 2 2

2С11 при Ь, = Ь =1

С-D=В при Ь„=<,Ь =a

С 0=4 при h,=Q, Ь2-1 (2)

0 .при Ь.|"-0 где Ь,, Ь2 — показатели четности соответственно чисел А

| и В (признаком четности числа является равенство нулю Ь, или Д ) ..

Для проведения чисел А и В к четному виду, чтобы выполнить их деление на два, из них приходится вычитать величины Ь, или Ь, принимающие значение 0 или 1, Блок 3 предназначен для того, чтобы на основе значений Ь, и h2 выработать три функции Е, = Д, Е Ь, Д ЕЬ2 N Г = h1 ЕЬ2 торые определяют величину поправки Е, прибавляемой к результату.

Блоки 1 и 2 деления на константу приводят исходные числа к четному виду, делят их на два и формируют величины д, и Ь, которые подаются на блок 3 для выработки поправки в соответствии с (2).

Блок 3 (фиг. 2) включает в себя два элемента НЕ 23 и 24 и три элемента И 25, 26 и 27, входы 28 и 29 соответственно, выходы 30, 31 и 32.

Сумматор 4 по модулю q вычисляА В ет величину С = — — + — — вычита2 2 тель 7 по модулю g величину 9 =

А В.

Квадраторы 10 и 11 вы2 2 числяют соответственно С и D блоки умножения 12 . 13 14 =.соответстА - В венно величины 2 — — 2 2С 1

2 2

Вычита тели 8 и 9 по модулю g вычис7 11006 ляют величину С - D причем на вычитателе 8 формируется старший разряд с весом а, а на вычитателе 9младший разряд с весом о . Сумматоры 5 и 6 по модулю g с учетом поправки Е формируют старший и младший g -ичные разряды произведения А В.

Предварительно деление. исходных чисел на два связано с тем, что ре- 10 зультат их суммирования не должен выходить за пределы неизбыточного арифметического диапазона, определяемого величиной . В этом случае все дальнейшие блоки устройства становятся конструктивно более простыми, особенно при реализации их в виде таблично-матричных схем;

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

Исходные числа А и В в унитарном коде поступают на входы блоков 1 и 2 деления на константу, в которых приводится к четному виду и делятся на два. На выходах четности блоков 1

2 формируются сигналы А,Аи. Ьу, а на разрядных — величины — — и

2 2 которые поступают на соответствующие входы сумматора 4 по модулю 0 и вычитателя 7 по модулю g где вычисЗ0 ляются величины С и D соответственно.

Одновременно величина А /2 поступает на вход первого блока 12 умножения на константу, где умножается на два и превращается в А . Величина В 35

2 в блоке 13 превращается в В .С выходов блоков 4 и 7 величины С и D соответственно поступают на входы квад19 8 раторов 10 и 11, где преобразуются в величины С и П . Величина С,, кро. ме того, пост;пает на вход третьего блока 14 умножения на константу, где преобразуется к виду 2С+1.

Квадраторы 10 и 11 устроены таким образом, что на их выходах величина, возведенная в. квадрат, получается в виде старшего разряда с веI .сом (и в виде ьцхадшего разряда-. с весом о . Старшие и младшие Я о ичные разряды величин С и 9 с выходов соответствующих квадраторов поступают на вычитатели 8 и 9 по модулю старших и младших разрядов соответственно. Между вычитателями 8 и 9 существует цепь переноса, по которой в случае необходимости заема из вычитателя 8 старшего разряда пересылается единица в вычитатель 9 младшего разряда. Результат вычитания С вЂ” D2 с выходов вычитателей 8 и 9 поступает, на сумматоры старших 5 и младших 6 разрядов, где производится коррекция произведения на величину поправки Е, поступающей в сумматор младшего разряда 6 через группу элементов ИЛИ 18 с выхода одной из групп элементов И 15, 16, 17, управляемых управляющими выходами блока 3. В результате на сумматорах 5 и 6 образуется окончательный, результат произведения в виде старшего с весом. Ч и младшего с ве1 сом (разрядов соответственно.

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

1100619 иг.. 1 100619

Составитель В. Виноградов

Редактор Л.Веселовская Техред М. Гергель Корректор H ЗРдейи

Заказ 4581/37 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва, Ж-35 Раушская наб. д. 4/5

Филиал ППП "Патент", г.ужгород, .Ул.Проектная, 4