Устройство для умножения

Устройство для умножения

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для умножения многоразрядных чисел в двоичных системах счисления. Цель изобретения - расширение функциональных возможностей устройства за счет умножения в избыточных системах счисления. Поставленная цель достигается тем, что в устройство, содержащее регистр множителя, регистр множимого, матрицу элементов И из 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