Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления Советский патент 1993 года по МПК G06F7/72 

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

На фиг,1 представлена структурная схе- ia предлагаемого устройства для умноже- ия S-ичных цифр в позиционно-остаточной истеме счисления, где 1 - первый блокхра- 1ения констант; 2 - второй блок хранения онстант; 3 - первый блок умножения; 4 - торой блок умножения; 5 - третий блок множения; 6 -четвертый блок умножения; - первый сумматор; 8 - второй сумматор; 9 - старший разряд произведения устройст- ita; 10 - младший разряд произведения устройства; 11 - третий сумматор; 12 - v етвертый сумматор; 13 - третий блок хра- йения констант; 14 -четвертый блок хранения констант; 15 - первый вход устройства; ; 6 - второй вход устройства; на фиг.2 - Структурная схема первого сумматора 7, где 7 - дешифратор первого операнда; 18 дешифратор второго операнда; 19 - матрица сумматоров по модулям; 20 - первый шифратор; 21 - второй шифратор; 22 - третий шифратор; 23 - мультиплексор; на фиг.З - структурная схема второго сумматора, где 24 - блок сравнения с константой.

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

СО

с

со

GJ XJ ГчЭ 00 4

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

Первый сумматор 7 конструктивно представляет собой S-ичный сумматор на три входа без формирования переноса и содержит дешифратор 17 первого операнда и дешифратор 18 второго операнда, входы которых являются соответственно входами второго и первого слагаемых сумматора 7. Выходы дешифраторов 17 и 18 подключены к соответствующим входам матрицы сумматоров 19 по модулям Р, подключенной выходом к объединенным входам шифраторов 20,21.22, выходы (2,2+ 1,2 + 2), которых подключены к соответствующим входам мультиплексора 23, выход которой является выходом 9 сумматора 7,

Управляющие входы мультиплексора 23 являются входом переноса сумматора 7.

Второй сумматор 8 конструктивно представляет собой S-ичный сумматор на два входа с формированием переноса и содержит дешифратор 17 первого операнда и дешифратор 18 второго операнда, входы которых являются соответственно входами первого и второго слагаемых сумматора 8. Выходы деширфаторов 17,18 подключены к соответствующим входам матрицы 19 сумматоров по модулям Р. Выход матрицы подключен к объединенным входам блока 24 сравнения с константой и шифраторов 20, 21,22. Выходы (2,2- S ,2- 2S) шифраторов 20-22 подключены к соответствующим входам мультиплексора 23, выход которого является выходом 10 сумматора 8. Управляющие входы мультиплексора 23 объединены с соответствующими выходами блока сравнения с константой 24 и являются выходом переноса сумматора 8.

Блок 24 сравнения с константой представляет собой блок постоянной памяти объемом (3S-3) х 1 бит.

Блоки 13, 14 хранения констант конструктивно аналогичны блокам 1, 2 хранения

констант.

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

Запишем произведение двух S-ичных цифр в виде:

ab (ai (bi )

aibiS + aib0VS + a0bi VS +a0b0 . (1)

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

aibo V5 CiS + Со, a0bo S dWST+ do. (2)

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

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

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

35

nS CiS + diS, r0 Со + do(3)

Соединяя (1) и (3), получим

ab (aibi + ci)S + (a0bo + r0) .(4)

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

С0

aobo + гоесли aobo + го S , f О,

aobo + го - SL если aobo + го S, f 1

0

S, егли aobo + (Ч 2S, f 2 .

(5)

aobo + Го

а первый сумматор 7 результат в виде Ci-aibi+ r + f,(6)

где f - значение переноса из второго 8 сумматора в первый 7 сумматор.

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

j a - («1, 02Ok), b {61,/fc/3k),

4е aJ llist (a/p|). A rest (b/pj) I J 1, K, Pj - модули СОК, удовлетворяюи|ие условию

t

П PJ 2S,

Pj - взаимно просты.

Для согласования с устройствами, работающими в двоичной системе счисления, в позиционно-остаточных устройствах обычно выбирают S 2т. Удобнее всего в настоящее время принять m 8 соответственно Ј 28 256, а среди модулей СОК иметь один, равный Vo. В частном случае, пусть F 1 V256 16. Это позволяет при аппарат- к ой реализации блоков 1,2,13 и 14 получить экономичные решения.

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

Операнды а («1 , оз ,.. . Ok ) и в i./fc , . $), представленные кодом СОК о модулям Pi, Ра...Рк, по входам 15 и 16 поступают на входы соответствующих блоков 1 и 2 хранения констант. Эти блоки конструктивно представляют собой блоки постоянной памяти на S 21-разрядных словКаждый, где I J Ij, lj-двоичная разряд IJ i

1юсть вычета а или /3j. В этих блоках в

соответствии с выражением (1) формируются величины ai, а0 и bi, Ь0 соответственно, которые поступают на первые и вторые входы блоков 3, 4, 5 и 6 умножения, В этих элоках в соответствии с выражением (1) рормируются величины aibiS, aibo VS, a0bi VST, a0bo. Величины aibiS4 а0Ь0 посту- тают на входы вторых слагаемых соответст- 5енно первого и второго сумматоров 7, 8. Первый сумматор 7 работает в позиционно- зстаточной системе счисления в соответст- ии с табл,№ 1 и всегда выдает результат иеньше S..

| Второй сумматор 8 работает в соответ- Јтвии с табл.2 и выдает результат до 3S - 3. | Величины aibo aobiVST поступают |на входы соответственно третьего и четвер- froro блоков 13, 14 хранения констант, где в соответствии с выражением (2) формируют величины Ci, Co соответственно, которые |поступают на соответствующие входы третьего и четвертого сумматоров 11,12. На |выходе третьего сумматора 11 в соответствии с выражением (3) формируется ве- |личина ri Ci + di. на выходе четвертого сумматора 12 в соответствии с выражением

(3) формируется величина г0 Со + d0- Величина п поступает на вход первого слагаемого первого сумматора 7, величина го поступает на вход первого слагаемого вто5 рого сумматора 8. Таким образом, на сумматорах 7 и 8 в соответствии с выражениями (5) и (6) формируют соответственно величины Со и Ci.

Таким образом, предлагаемое уст0 ройство может быть использовано в качестве разрядного умножения S-ичных цифр в позиционно-остаточной системе счисления для умножения чисел в СОК к

с в диапазоне ПР, а также в качестве байтоJ 1

вого умножения (1 байт 8 бит) в позиционных системах счисления.

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

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

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

Q блоков умножения, входы второго блока умножения соединены соответственно с первым выходом первого блока хранения констант и с вторым выходом второго блока хранения констант, входы третьего блока

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

е четвертого блока хранения констант, а выходы третьего и четвертого сумматоров сое- динены с соответствующими входами первых слагаемых первого и второго суммэ- торов, входы вторых слагаемых которых подключены к соответствующим выходам

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

Таблица1

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

5.х

Таблица 2

pЈ/&i

L.

фЈ/р.г

3