Устройство для умножения s-ичных цифр в позиционно- остаточной системе счисления

 

Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих арифметических устройств, работающих в позиционно-остаточной системе счисления. Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления содержит четыре блока хранения констант, четыре блока умножения и четыре сумматора , соединенные между собой функционально . 3 ил,, 2 табл.

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

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

РЕСПУБЛИК

G 06 F 7/72

НОЕ ПАТЕНТНОЕ

ССР

CP) АНИЕ ИЗОБРЕТЕНИЯ

КОМУ СВИДЕТЕЛЬСТВУ (1) 5005314/24 (2) 01.08.91 (6) 30.08.93. Бюл. М 32 (1) Научно-исследовательский институт очного электронного приборостроения начно-производственного объединения Орион" (2} В.Г.Евстигнеев, А, Н,Кошарновский и .В.Бондаренко

6) Авторское свидетельство СССР

1236472, л. 6 06 F 7/72, 1984.

Авторское свидетельство СССР

1633401, кл. G 06 F 7/72, 1989..

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

На фиг,1 представлена структурная схеа предлагаемого устройства для умножеия S-ичных цифр в позиционно-остаточной истеме счисления, где 1 — первый блок храения констант; 2 — второй блок хранения онстант; 3 — первый блок умножения; 4— торой блок умножения; 5 — третий блок ножения; 6 — четвертый блок умножения; первый сумматор; 8 — второй сумматор; старший разряд произведения устройст10 — младший разряд произведения устйства; 11 — третий сумматор; 12— вертый сумматор; 13 — третий блок храния констант; 14 — четвертый блок хранея констант; 15 — первый вход устройства; — второй вход устройства; на фиг.2— руктурная схема первого сумматора 7, где — дешифратор первого операнда; 18—

„„. Ж,, 1837284 А1 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ SИЧНЫХ ЦИФР В ПОЗИЦИОННО-ОСТАТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих арифметических устройств, работающих в позиционно-остаточной системе счисления.

Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления содержит четыре блока хранения констант, четыре блока умножения и четыре сумматора, соединенные между собой функционально. 3 ил„2 табл. дешифратор второго операнда; 19 — матрица сумматоров по модулям; 20 — первый шифратор; 21 — второй шифратор; 22 — третий шифратор; 23 — мультиплексор; на фиг.3— структурная схема второго сумматора, где

24 — блок сравнения с константой, Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления содержит (см. фиг.1) первый и второй блоки 1, 2 хранения констант, четыре блока 3, 4, 5, 6 умножения, первый и второй сумматоры 7, 8, выходы которых являются соответственно выходами 9, 10 старшего и младшего разрядов произведения устройства. Входы первого блока 3 умножения соединены с первыми выходами соответственно первого и второго блоков 1, 2 хранения констант, вторые выходы которых подключены к соответствующим входам четвертого блока 6 умножения. Кроме того, устройство содержит третий и четвертый сумматоры 11, 12, третий и четвертый блоки

13, 14 хранения констант, входы которых

1837284 подключены к соответствующим выходам второго и третьего блоков 4, 5 умножения.

Входы второго блока 4 умножения соединены соответственно с первым выходом пер-. вого блока 1 хранения констант и со вторым выходом второго блока 2 хранения констант. Входы третьего блока 5 умножения соединены соответственно со вторым выходом первого блока 1 хранения констант и с первым выходом второго блока 2 хранения констэнг. Входы блоков 1 и 2 являются соответственно первым и вторым входами 15, 16 устройства. Выходы третьего блока 13 хранения констант подключены к соответству1ощим первым входам третьего и четвертого сумматоров 11, 12, вторые входы которых подключены к соответствующим выходам четвертого блока 14 хранения констант, а выходы сумматоров 11 и 12 соединены с соответствующими входами первых слагаемых первого и второго сумматоров 7, 8, входы вторых слагаемых которых подключены к соответствующим выходам первого и четвертого блоков 3, 6 умножения. Выход переноса второго сумматора 8 подключен ко входу переноса первого сумматора 7, Первый сумматор 7 конструктивно представляет собой S-ичный сумматор на три входа без формирования переноса и содержит дешифратор 17 первого операнда и дешифратор 18 второго операнда, входы которых являются соответственно входами второго и первого слагаемых сумматора 7.

Выходы дешифраторов 17 и 18 подключены к соответствующим входам матрицы сумматоров 19 по модулям Р, подключенной выходом к объединенным входам шифраторов

20, 21, 22, выходы (Х, Х + 1, Х + 2), которых подключены к соответствующим входам мультиплексора 23, выход которой является выходом 9 сумматора 7, Управляющие входы мультиплексора 23 являются входом переноса сумматора 7.

Второй сумматор 8 конструктивно представляет собой S-ичный сумматор на два входа с формированием переноса и содержит дешифратор 17 первого операнда и дешифратор 18 второго операнда, входы которых являются соответственно входами первого и второго слагаемых сумматора 8.

Выходы деширфаторов 17, 18 подключены к соответствующим входам матрицы 19 сумматоров по модулям Р . Выход матрицы подключен к объединенным входам блока 24 сравнения с константой и шифраторов 20, 21, 22. Выходы (Х, Х вЂ” S,Z — 2S) шифраторов

20 — 22 подключены к соответствующим входам мультиплексора 23, выход которого является выходом 10 сумматора 8. Управляющие входы мультиплексора 23 объединены с соответствующими выходами блока сравнения с константой 24 и являются выходом переноса сумматора 8.

Блок 24 сравнения с константой представляет собой блок постоянной памяти объемом (3S-3) х 1 бит, Блоки 13, 14 хранения констант конструктивно аналогичны блокам 1, 2 хранения

10 констант.

В основу работы устройства для умножения S-ичных цифр в позиционно-остаточной системе счисления положено следующее, Запишем произведение двух S-ичных цифр в виде:

a1bp Л- С1с + Со, аоЬо S = f14 + Оо, (2)

25 где aib — значения S-ичных цифр сомножителей;

S — основание внешней позиционной системы счисления.

Сгруппируем из (2) члены с одинаковыми весами

r1S = C1S + d1S, го = Со + до (3) Соединяя (1) и (3), получим аЬ =(aib1+ ci)S+(apbp+ го) . (4) При вычислении выражения г, = Со+ dp

40 из (3) результат может превысить величину

S, при вычислении выражения (aobo+ го) из (4у) результат может превысить 2S. Позтому второй сумматор 8 (см.фиг.1) должен уметь формировать результат в виде:

45 аоЬо + го если аоЬо + го (S, f =0, аоЬо + го — Si, если apbo + rp > S, f = 1

) аоЬо +го S, еглиаоЬо +го 2S,f =2, со =

50 а первый сумматор 7 результат в виде (6) С1 = а1Ь1+ г+ f, 55 где f — значение переноса из второго 8 сумматора в первый 7 сумматор.

Известно, что цифры в S-ичной позиционно-остаточной системе счисления представляются по модулям СОК в виде:

ab - (а1 Ю+ ао} (Ь1 vS+ Ьо) =

=a1b1S+ a1bo VS+ aob1 VS+ aobp, (1)

Запишем второе и третье слагаемые в виде:

1837284 а = (а1, а,... а)), b= ф1, pz,... p) ), г/)е rr/= rest(s/Pi), /)/= rest (ЫР/) .

) = 1, К, Pl — модули СОК. удовлетворяюы ие условию к

П Pl 2$, /=1

Pl — взаимно просты.

Для согласования с устройствами, работ ющими в двоичной системе счисления, в ! озиционно-остаточных устройствах обычо выбирают S = 2m. Удобнее всего в настощее время принять m = 8 соответственно

= 2 = 256, а среди модулей СОК иметь дин, равный ЧБ. В частном случае, пусть

1 = 9256= 16, Это позволяет при аппаратой реализации блоков 1, 2, 13 и 14 получить кономичные решения.

Устройство для умножения S-ичных ифр в позиционно-остаточной системе числения работает следующим образом, Операнды а = (а1, а2,... ак ) и в=

1,Д,...p)), представленные кодом СОК о модулям Р1, Р ...Рк, по входам 15 и 16 г)оступают на входы соответствующих блоов 1 и 2 хранения констант. Эти блоки онструктивно представляют собой блоки остоянной памяти на $21-разрядных слов. каждый, где! = Il, ll-двоичная разрядl =1 ость вычета а1 или Д, В этих блоках в оответствии с выражением (1) формируютЯ величины а1, ао и b1, bp соответственно, оторые поступают на первые и вторые вхоы блоков 3, 4, 5 и 6 умножения, B этих локах в соответствии с выражением Щ ормиоуются величины 31b1S, a1bо V5, ob1 VS4, Bpbo. Величины a1b1S4 aobp постуают на входы вторых слагаемых соответстенно первого и второго сумматоров 7, 8. ервый сумматор 7 работает в поэиционностаточной системе счисления в соотаетстии с табл,N 1 и всегда выдает результат еньше S. о

Второй сумматор 8 работает в соответ ствии с табл.2 и выдает результат до 3S — 3.

Величины а1ЬО Я и 8pb)VS поступают на входы соответственно третьего и четверlroro блоков 13, 14 хранения констант, где в соответствии с выражением (2) формируют ,: величины С1, Со соответственно, которые

)поступают на соответствующие входы, третьего и четвертого сумматоров 11, 12. На ,:выходе третьего сумматора 11 в соответст, вии с выражением (3) формируется ве ;личина г1 = C1 + d1, на выходе четвертого сумматора 12 в соответствии с выражением

15 (3) формируется величина ro = Co+ dp. Величина r1 поступает на вход первого слагаемого первого сумматора 7, величина ro поступает на вход первого слагаемого второго сумматора 8. Таким образом, на сумматорах 7 и 8 в соответствии с выражениями (5) и (6) формируют соответственно величины Сои С1, Таким образом, предлагаемое устройство может быть использовано в качестве разрядного умножения S-ичных цифр в позиционно-остаточной системе счисления для умножения чисел в СОК

К в диапазоне ПР>, а также в качестве байто) =1 вого умножения (1 байт >8 бит) в позиционных системах счисления.

Формула изобретения

Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления, содержащее первый и второй блоки хранения констант, первый, второй, третий и четвертый блоки умножения, первый и второй сумматоры, выходы которых являются соответственно выходами старшего и младшего разрядов произведения устройства, входы первого блока умножения соединены с первыми выходами соответственно первого и второго блоков хранения констант, вторые выходы которых соединены с соответствующими входами четвертого блока умножения; о т л и ч а ющ е е с я тем, что в него дополнительно введены третий и четвертый сумматоры, третий и четвертый блоки хранения констант, входы которых подключены к соответствующим выходам второго и третьего блоков умножения, входы второго блока умножения соединены соответственно с первым выходом первого блока хранения констант и с вторым выходом второго блока хранения констант, входы третьего блока

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

1837284

Таблица 1

Таблица 2 первого и четвертого блоков умножения, причем выход переноса второго сумматора подключен к входу переноса первого сумматора.

1837284

I ! !

l

l

l ! !

l

I ! ! !

Составитель B.Ãóñåâ

Техред М.Моргентал!

Редактор H.Êîëÿäà

Корректор А.Козориз

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

- — -д: Заказ 2865 Тираж Подписное

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

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