Устройство для умножения
Изобретение относится к вычислительной технике и может быть использовано для умножения многоразрядных чисел в двоичных системах счисления. Цель изобретения - расширение функциональных возможностей устройства за счет умножения в избыточных системах счисления. Поставленная цель достигается тем, что в устройство, содержащее регистр множителя, регистр множимого, матрицу элементов И из N столбцов и N строк /N - разрядность операндов устройства умножения/, введены шифратор, накапливающий сумматор, в матрицу элементов И введены 5N элементов И, /2K+3/ элементов ИЛИ/K - МИНИМАЛЬНОЕ КОЛИЧЕСТВО НУЛЕВЫХ РАЗРЯДОВ МЕЖДУ БЛИЖАЙШИМИ СОСЕДНИМИ ЕДИНИЧНЫМИ РАЗРЯДАМИ В ПРЕДСТАВЛЕНИИ ЧИСЕЛ В ИЗБЫТОЧНЫХ СИСТЕМАХ СЧИСЛЕНИЯ/, N СЧЕТНЫХ ТРИГГЕРОВ С СООТВЕТСТВУЮЩИМИ СВЯЗЯМИ. 1 ИЛ.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН (19) (11) (Si)S 0 06 F 7/49
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А BTOPGKOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
Il0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (21) 4499787/24-24 .(22) 18.04.88 (46) 15.06.90. Бюл. Ф 22 (71) Кубанский государственный университет (72) В.,В.Дудкин и Н.А,Яковенко (53) 681 ° 325 (088.8) (56) Авторское свидетельство СССР
М I 193667,. кл. G 06 F 7/52, 1 982 °
Авторское свидетельство СССР 122947, кл. С 06 F 7/52, 1959. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для умножения многоразрядных чисел в двоичных системах счисления.
Цель изобретения — расширение функИзобретение относится к вычислительной технике и может быть использовано для умножения многоразрядных чисел в двоичных системах счисления.
Цель изобретения — р асширение
AyHKHHoHaJIbHblx возможностей устройства за счет умножения в избыточных системах счисления.
На чертеже приведена схема устройства для умножения многоразрядных чисел в двоичных избыточных системах счисления.
Устройство содержит регистр 1 множителя, регистр ? множимого,шифратор 3, накапливающий сумматор 4, матрицу 5 элементов И из и столбцов и и строк, матрица 5 содержит эле.менты И 6-1, 6-2,..., 6-i б-п, 2 циональных возможностей устройСтва за счет умножения в избыточных системах счисления. Поставленная цель достигается тем, что в устройство, содержащее регистр множителя, регистр множимого, матрицу элементов И из и столбцов и и строк (и — разрядность операндов устройства умножения),введены шифратор, накапливающий сумматор, в матрицу элементов И введены
5п элементов И,(2К+3) элементов ИЛИ (К вЂ” минимальное количество нулевых разрядов-между ближайшими соседними единичными разрядами в представлении чисел в избыточных системах счисления), и счетных триггеров с соответствующими связями. 1 ил. 9 элементы И 7-1, 7-2,..., 7-,...,7-п, элементы И 8-1,8-2,...,8-1, 8-п, триггеры 9-1, 9-2, ..., 9-i, ...,9-п элементы ИЛИ 10-i,..., 10-п, элементы ИЛИ 11 и 12, элементы И 13-1, 13-?, ..., 13-i ..., 13-п, элементы И 14-1, 14- 2, ..., 14-i, ...,!4-п, элементы ИЛИ 15-,), ..., 15-п, элемент ИЛИ 16, элементы И 17-1-1
17-1-2, .... 17-п-п.
Входы 18-1, 18-2, ..., 1.8-п являются информационными входаьж регистра I,входы 19-1,19-2,...,19-n — входами регистра 2, вход 20 — упр авляющим входам устройства, выход 21 — выходом окончания умножения, выходы 22-1,.
22-2, ..., 22-n — выходами накапли. 1571574 причем
7 9
1 1 2 2 3 4 5
1 2
1 2
1 2
2 4
3 . 6
4 8
5 )О
7 14
9 )8
1
2
3
5
1
1
2
4
7
1
2
3
5
4
4
8
I P
16
28
2 3
2 3
2 3
4 6
6 . 9
8 12
10 li5, 14 2!
18 27
5
i0
7 9
7 9
7 9
14" 18
14 l8
21 27
28 36
35 45
49 63
63 81 вающего сумматора 4, выходами кода произведения, Любое число в двоичных избыточных системах счисления (в традиционной классической системе счисления такыре) может быть представлено как
А = > а;L)(i)
10 где a;E$0 lI причем а; = 1 при выполнении условия и
L<(i) а А- а 7 (i) Ьq(i + 1), (2) l5
О, при 0;
D при 0 i 1; (3)
Т. (i) e+a
Ь (1-1-3), IIPH,) 1. (;=6
В формулах (1), (2), (3) под принимается номер разряда (i = О, 1, 2,..., N ), под 1 — номер сис т емы счисления (1 = О, ll 2,...,N), D— произвольное число, могущее .принимать значения в интервале целых чисел от
-И до +N, но в конкретном случае от О до И, А и  — целые произвольные числа, равны О, 1,2,...,N.АФВФЭ, 3О но. могут быть системы, когда общее неравенство принимает вид равенства.
L<(i) — имя системы счисления. 11-, однако на практике оно значительно меньше, 3 определено в. формуле (3) .
Выражение (2) задает форму представ-, ления чисел.
Условие (3) справедливо для минимальной формы изображений, предполагающей наличие минимального коли:че,ства единиц в изображении числа, а
: также характерной строго обозначенным .снизу количеством нулей между единицами К. Для минимального изображения в р-системах счисления Фибонач О
К = Р (4), для двоичной,1-системы счисления, при 1 ; — 1, К = 4 (5), Оче-i видно, что при уменьшении основания системы счисления возникает возможность производить построение форм изображения чисел по определенному алгоритму, в нашем случае его задает выражение (2) для систем счисления (3) и испольэовать эти особенности для увеличения быстродействия при выполнении арифметических опepаций.
Реализованный способ умножения основан на принципе таблицы умножения и состоит в следующем.
Б столбец записываются в порядке возрастания веса конкретно выбранной системы счисления, 2. В строку записываются в порядке возрастания веса конкретно (той же„что и для столбца) выбранной сист емы счи сления .
3. На пересечении строк и столбцов з аписывают ся произ ведения в есов соответствующих строк на веса соответствующих столбцов, причем в соответствии с выражением
О, при i<0
Ь (х) L (m), при О з и 1, (4) +А
+ Х (i-1-j ), при i>1, -в где i — номер столбца;
m — номер строки; х — номер разряда множимого, m — номер разряда множителя, 4. Произведения, попавшие на пересечение строк и столбцов в аналогичных разрядах сомножителей, имеющих коэффициент а; = 1, являются частными произведениями.
5. Просуммировав частные произведения, получаем окончательное, интересующее нас произведение сомножителей, Рассмотрим приведенный .способ умножения для двоичной 1-системы счисления, при 1 = 1:, 157 1 574
Вьппе 1112234579... — веса двоичной 1-системы счисления, вычисленные в соответствии с выражением
Произведение веса i столбца на вес m-й строки определится, как
О, при ic О, g,(m) при 0 5 17" (i) О, при (О, 1 при О- 1 (5) Q,(i 2) +1!1,(i -3), при i ) l. Рассмотрим умножение чисел 1) и 8: Множитель 0 0 0 0 1 0 0 0 0 1 1 1 2 2 3 4 5 7 9 2 4 6 14 18 мое Аналогично рассмотренному примеру происходит умножение в других системах счисления. Рассмотрим пример умножения чисел l2 и 10 в традиционной двоичной системе счисления: В кружочки обведены частные произведения, которые необходимо просуммировать: 11 х 8 = 63 + 14 + 9 + 2 = 88, 12 1 0 0 0 1 4 8 16 О8 Я) 32 16 32 64 (32) (бф 128 64 128 256 0 l 1 2 1 2 2 4 10 0 4 4 8 1 8 Я 16 О 16 16 32 В данном случае i m — веса разрядов множимого и множителя, над веса,ми размешены кодовые записи чисел. В кружочках частные произведения чисел 4 на 2, 4 на 8, 8 на 2, 8 на 8. Имеем 10 х 12 = 8 + 16 + 32 + 64 .= 120, т.е. произведения соответствуют истине. I быть построен в соответствии с выражениями (1 ) и (2 ) для любого слу45 чая. Матрица частных произведений тогда будет определяться выражением (4), однако значение ?,(ш) при О (i 1 будет определено весом системы счисления множимого, 50 Рассмотрим пример умножения чисел 6 и 18 в 2- и 3-системе счисления Фибоначчи. В зтом случае выражение (4) преУстройство позволяет умножать числа, где множимое и множитель представлены в различных системах счисления, а произведение получено в третьей системе, отличной от системы, счисления и множителя и множимого. Это возможно благодаря введению в устройство шифратора, который может образится в следующее: О, при О, Vã(m) ° 1 0 i 3 (7) Ч!(э.-р-) ), при д ) 3 ° 1=о 0 1 0 2 0 2 0 3 0 4 0 5 l 7 О. 9 1 . 1 1 1 ) 1 2 2 2 2 3 3 4 4 5 5 7. 7 9, 9 7. 07 4 8 З4 3 3 6 12 2l 4 5 7 9 4 5 7 9 Q9 8 10 14 18 8 10 14 18 12 !5 21 27 16 15 28 36 20 25 35 45 28 35 49 ДЗ 30 45 63 81 1571574 1 2 3 4 5 4 5 4 5 8 10 12 15 l 6 20 24 30 1 1 1,,1 1 2 2 2 3 3 3 4 4 4 6 6 6 19 19 19 38 57 76 116 l4 ! 14 24 42 56 7 10 7 10 7 10 14 20 21 30 28 40 42 60 2 3 2 3 2 3 4 6 6 9 8 12 I 2 18 О . 0 О О 0 О В данном случае i — веса 3-систе" (! мы счисления Фибоначчи m — веса 2- . Э системы счисления Фибоначчи, в кру жочках частные произведения: 6 х х 18 = 84 + 24 = 108. Устройство работает следующим обр азам, 25 ! В регистр 1 записывается код мно-, жителя, в регистр 2 — код множимого. На вход 20 подается сигнал управления, который поступает на вторые вхо-. ды элементов И 6-1, 7-1. Положим раз- ЗО ряд регистра, к которому подключены элементы И 6-1, 7-1 нулевой, зто приведет к единичному уровню на первом входе элемента И 7-1, на выходе которого появится единичный сигнал, который передается на вторые входы элементов И 6-2, 7-2. Положим, что разряд, к которому подключены элементы И 6-2,- 7-2 единичный, в этом случае первый вход элемента И 6-2 будет 40 подключен к единичному сигналу, на его выходе появится единичный уровень, который установит триггер 9-2 в единичное состояние, что в свою очередь приведет к тому,, что на пер- 45 вых выходах элементов И 17-1-2, 17" 2-2,..., 17- j-2, -..., 17-и-2 поя-, вится единйчный сигнал, единичный сигнал через элемент ИЛИ 11. поступит ..также на вторые входы элементов . И 13-1, 14-1 ° Положим, что опрашивае" : мый разряд регистра 2 (а именно к опросу его мы приступили), к которому прикреплены элементы И 13-1,! 4-1, равен нулю, тогда на выходе элемен55 та И 14-1 .появится единичный сигнал, так как на его входе два единичных сигнала с выхода элемента ИЛИ 11 и с инверсного выхода опрашиваемого разО О О 1 O 4 5 7 10 14 !9 1 ряда регистра 2, это приведет к тому, что на вторых входах элементов И 13-2, 14-2 появится единичный сигнал„Положим, что регистр 2 имеет в разряде, к которому подключены И 13-1, 14-2 логическую единицу,тогда на выходе. элемента И 13-2 появится единичный сигнал, который передается на вторые входы элементов И 17-2-1, 17-2-2, 17 — 2-3, 17-2- . ..,, 17-2-п. На выходе элемента И 17-2-2 появится единичный уровень, так как на его входах единичный сигнал, выходной сигнал с элемента И 17-2-2 поступит через произ.ведения матрицы 5 на соответствующий в силу выражений (1), (2) вход шифратора 3, где преобразуется в позиционный код интересующей нас системы и поступит на входы накапливающего сумматора 4 суммирующего числа в системе счисления шифратора..Одновременно единичный сигнал с выхода элемента И 13-2 поступит на первый вход элемента ИЛИ 15 (i-k-1)-го разряда, выход последнего подключен к вторым входам элементов И 13, 14 этого разряда, произойдет опрос содержимого разряда. Положим, содержимое этого разряда имеет нулевое значение, в этом случае на выходе элемента И 14 появится логический сигнал, который через элемент ИЛИ 15 опросит следующий р азряд. Положим, последний и-й разряд регистра 2 имеет, единичное значение, В этом случае на выходе элемента И 13-и появится единичный сигнал, который передается на вторые входы элементов И 17-п-1, 17-п-2, 17 "п-3, ..., 17-n" J, ..., 1 7-и-и. На выходе элемента И 17-п-2, следовательно, появится единичный сигнал, 1571574 10 который через выход произведения матрицы шифруется и попадает на вход сумматора 4, где суммируется с предыдущим значением. Одновременно единичный. сигнал через элемент ИЛИ 16 сбрасывает триггер 9-2 в ноль, подается на вторые входы элементов И 8. На выходе элемента И 8-2 в этом случае появится логическая единица,которая через элемент И3% 10 приведет к опросу элементов И 6, 7 (i-k-1) вЂ,го разряда. Если этот разряд имеет кулевое значение, то на выходе элемента И 7 появится единичное значение, кото- 15 рое через элемент ИЛИ 10 опросит следующий разряд. Положим, и-й разряд регистра 1 равен единице., В этом случае на выходе элемента И 6-п появитедкничный уровень, который усТаНо- 2р вит триггер 9-п в единичное состояние, а последний в свою очередь подключает первые входы элементов И 171-п, 17 — 2-n, ..., 17-j-n, ..., 17-n-n u через элемент ИЛИ 11 разрешит опрос 25 содержимого регистра 2, так как у регистра 2 второй и и-й разряды единичны,то на выходе элемента И 13-2 появи тся единичный сигнал, подключающий вторые входы элементов- И 17-2-.1, 17- 3р 2-3, °... 17-2-,)...,, 17-2-п на выходе элемента И 17-2-и появится еди— .ничный сигнал, который через вход произведения матрицы преобразится в позиционный код шифратор 3 и поступит на входы сумматора 4, где просум,мируется с содержанием последнего, Произойдет опрос последующих разрядов через элементы И 14. На выходе элемента И 13-п появится единичный сигнал, что подключает вторые входы элементов И 17-п-1, 17-п-2, 17-п-3 17-n-g 17-n-n и приведет к появлению единичного сигнала на вь ходе элемента И 17-п-п, который изве- 45 стным путем попадет на. сумматор 4 и просуммируется в нем. Также единичный сигнал через элемент ИЛИ 16 обнулит триггер 9-п поступит на вторые входы элементов И 8, что приведет к появлению единичного сигнала на выходе элемента И 8-п, который через элемент ИЛИ 12 засвидетельствуетоб окончании процесса умножения. С выходов 22 сумматора 4 можно считывать код прои эведения . «функциональные возможности изобретения позволят отказаться от устройства преобразования исходных кодов сомножителей в специализированных средствах вычислительной техники,что упростит их, повысит быстродействие и помехоустойчивость. Формула изобретения Устройство для умножения, содержащее регистр множителя, регистр множимого, матрицу элементов И из п столбцов и и строк, и-разрядность операндов устройства умножения, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет умножения в избыточ" кых двоичных системах счисления, в устройство введены шифратор, накапливающий сумматор, в матрицу элементов И введены 5п элементов И, (2K+3) элементов ИЛИ (К вЂ” минимальное количество нулевых разрядов между ближайшими соседними единичными разрядами в представлении чисел в,избыточных системах счисления), и счетных триггеров, причем прямой выход i-ro разряда регистра множителя соединен с первым входом (2i-1)-го элемента И матрицы (i = 1, 2, ..., n), инверсный выход i-го разряда регистра множителя соединен с первым входом 2i-го элемента И матрицы, выход (2i-1)-ro элемента И матрицы соединен с первым входом (2n+i)-го элемента И матрицы, со счетным входом i-го триггера матрицы, с соответствующим входом первого элемента ИЛИ матрицы, второй вход (2n+i)-го элемента И матрицы соединен с выходом второго элемента ИЛИ матрицы и с входом сброса i-го триггера матрицы, выход третьего элемента ИЛИ матрицы соединен с выходом окончания процесса умножения устройства, выход 2)-го элемента И матрицы соединен с вторым входом (2 + + 1)-ro и с (2 +2)-ro элемента И К+ 1 матрицы (j = 1, 2,..., — — — — ), выход -го элемента И матрицы,1 = 2(K+2), 2(K+3) ..., 2(n-1)1 соединен соответственно с первым входом элемента ИЛИ матрицы с четвертого по К-й, выход элемента ИЛИ матрицы с четвертого по К-й соединен с вторыми входами элементов И матрицы соответственно с 2(n-К) по 2п-й,.выходы элементов И матрицы с (2n+1)-ro no (3n-К-1)-й соединены соответственно с вторыми входами элементов ИЛИ мат,1571574 рицы с четвертого по К-й, выход i-ro триггера матрицы соединен с вто ьии входами элементов И i-й строки матрицы вторые входы первого и вто1 5 ,рого элемента И, матрицы соединены с управляющим входом матрицы, прямой выход i-го разряда регистра множимо;го соединен с первым входом (Çn+2i-I )-го элемента И матрицы, инверсный 1п выход i-го разряда регистра множимого соединен с первым входом (Çn+2i)го элемента И матрицы, выход каждо"го J-ro элемента И матрицы (J = (Зп+ +2), (Зп+4)...,,(2К+2)) соединен с ! вторым входом (1+1)-го и (1+2)-го элементов И матрицы, выход каждого четного элемента И матрицы с (Çn + + 2К + 4)-го по (5n-2).-й соединен соответственно с первым-входом эле- 2О ментов ИЛИ с (К+4)-го по (2К+3)-й, выход каждого )-ro элемента ИЛИ мат рицы () = К+4) K+5 ° ° ° ° ° 2Ê+3) соеди-. нен с вторым входом (Зп+2)+1)-го и (Зп+2 +2)-го элемента И матрицы,выхо- 25 ды элементов И матрицы с (Çn+2i-1)-ro по (5n-2К-2 )-й соединены соответственно с вторыми входами элементов ИЛИ матрицы с (K+4)-го по (2K+3)-й, выход (Çn+2i-1)-го элемента И матрицы соединен с первьии входами элементов И i"ãî столбца матрицы, вторые вхо- ды (Çn+1 )-го, (Зп+ 2 )-го элементов И матрицы соединены с. выходом первого элемента ИПЛ, выходы нечетных элементов И матрицы с (5n-2К-.1)-го по (5n-.l )-й и ьыход 5n-ro элемента И матрицы соединены соответственно с входами второго элемента ИЛИ матрицы, выходь1 элементов И матрицы с (Зп-5).-й по Çn-й и выход 2п-ro элемента И матрицы соединены соответственно с входами третьего элемента ИЛИ, выходы элементов И строк матрицы соединены с соответствующими входами шифратора устройства умноже-.. ния, выходы шифратора соединены с соответствующими весовыми входами накапливающего сумматора,,выход которого соединен с выходом результата устройства умножения, I 57 L574 / г У 2) - и-1 Составитель 1б, Варакин Редактор T. Лазоренко Техред Л. Серд окова Корректор Л, Бескид Заказ 1512 Тираж 564 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101
