Матричное устройство для умножения чисел (его варианты)

 

1. Матричное устройство для умножения чисел, содержащее блок формирования частичных произведений , выполненный в виде матрицы пхг элементов И (И-разрядность множителя и множимого) и блок суммирования частичных произведений, выполненный в виде матрицы П(П-2) одноразрядных сумматоров, причем первые входы элементов И --и строки матрицы соединены с входом -f -го разряда множителя устройства, J. -и разряд множимого которого соединен с вторь1ми входами

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

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

РЕСПУБЛИК

f19) Ъю (I

SU„

4(sent С 06 Р 7 49

Ь ь

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

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

rt0 ДЕЛАМ ИЗОБРЕТ)=НИЙ И ОТКРЫТИЙ

Р; . 1 1 Я"„"КА

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

° (22) 07,12.83 (46) 07.06.85. Бюл. Р 21 (72) Л.В.Вариченко, P.Á.Ïoïoâè÷, Д.M.Ñòåïàíþê и Ю.А.Томин (53) 681,325(088.8) (56) Карцев M.À. Арифметика цифровых машин. М., "Наука", 1969, с. 438.

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

Ф 600554, кл. С 06 F 7/52, 1978.

Патент США Р 4037093, кл. Г 06 F 7/52, опублик. 1977.

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

Ф 900281, кл. G 06 F 7/52, 1979.

Рабинер Л.P., Гоулд Б. Теория и применение цифровой обработки сигналов. М., "Мир", 1978, с.572573. (54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ (ЕГО ВАРИАНТЫ) . (57) 1. Матричное устройство для умножения чисел, содержащее блок формирования частичных произведений, выполненный в виде матрицы ttxtt элементов И (tl-разрядность множителя и множимого) и блок суммирования частичных произведений, выполненный в виде матрицыИ (-2) одноразрядных сумматоров, причем первые. входы элементов И 1 -й строки матрицы соединены с входом 4 -ro разряда множителя устройства, -й разряд множимого которого соединен с вторыми входами (1,ф)-х элементов И (1 =1,2,,...,n,j -1,2 °...,n), выход переноса (1 j)-го одноразрядного сумматора соединен с первым входом (f +1, ф +1) -ro одноразрядного сумматора, выход суммы (1, )-ro одноразрядного сумматора соединен

I .с вторым входом (< J. +1)-го одноразрядного сумматора, кроме выходов суммы переноса одноразрядных сумматоров последнего столбца и выходов переноса одноразрядных сумматоров последней строки, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения П разрядных двоичных чисел по модулю я

2 -1, в него введены первый и вто- рой И -разрядные сумматоры и блок коррекции результата, содержащий

tt-входовый элемент И и И -разрядный сумматор, а выход переноса (Л, К )-го одноразрядного сумматора соединен с первым входом (1, К +1)-го одноразрядного сумматора (К =1,2,..., И-3), выход (1,J )-го элемента И соединен с первым входом (1, 1)-го одноразрядного сумматора (где 1) соответственно, выход (2, ) -го элемента И соединен с вторым входом (1,1)-ro одноразрядного сумматора соответственно, где 1 (+1) Modn, K(A) Modn= n. при А tt и (А) Модп равен . остатку A/n при К4 п, выход (б,р)-ro элемента И (53, -.,tt) соединен с третьим входом (1,4)-го рдноразряд, ного сумматора, где 1 (+) -1)Nodn,,0=6-2, выход суммы (, и -2)-rо одноразрядного сумматора соединен с вхос дом 1 -го разряда первого слагаемого первого П -разрядного сумматора ! соответственно, выход переноса (1, й-2)-ro одноразрядного сумматора кроме (tt, n -?)-го одноразрядного сумматора соединен с входом Г -го разряда второго слагаемого первого Л -разрядного сумматора (2,3 ...,И), выkogt переноса (ttttt -2)-ro .одноразряд1160398 ного сумматора соединен с входом первого разряда второго слагаемого

Д -разрядного сумматора, выход пере.— носа которого соединен с входом переноса второго И -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы первого

И-разрядного сумматора соответственно, вход переноса первого 6-разядного сумматора и входы второго лагаемого второго И -разрядного сумматора соединены с шиной нулеврго потенциала, выходы суммы второго 1— разрядного сумматора соединены с входами И -входового элемента И и вхо/ дами второго слагаемого л -разрядного сумматора блока коррекции результата соответственно, входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потенциала и выходом 1 †входового элемента И, выходы устройства соединены с выходами суммы И -разрядногп сумматора блока коррекции результата.

2, Матричное устройство для умноже ния чисел, содержащее блок формирования частичных произведений, выполненный в виде матрицы n n элементов И (n-разрядность множителя и множимого, и блок суммирования частичных про— изведений, причем первые входы элементов И 1 -й строки матрицы соединены с входом 1 - го разряда множителя устройства, J -й разряд множимого которого соединен с вторыми входами (4, J ) -х элементов И (1 =1, 2,...,Р, Р =1, 2,...,}1), о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения и -разрядных двоичных чисел по модулю 2 -1, в него ввеи дены первый и второй И -разрядные сумматоры и блок коррекции результа° та, .содержащий И -входовый элемент И

И-разрядный сумматор, а блок суммирования частичных произведений выполнен в виде матрицы "(П-1) п -разрядных сумматоров (п7(О, K = П/ги — целое число), причем вход g.--ro разряда первого слагаемого (g =1,2,...,w) (p,1)-го П1 -разрядного сумматора (8=1,2,...К) соединен с выходом (1,p)-го элемента И соответственно, где =1-(t-1))п, Г = У/и+1, вход

$-ro разряда второго слагаемого (l, )-ro М -разрядного сумматора (r =1,2,...,и-1) соединен с выходом (j „р)-го элемента И соответственно, где < ) 1, g=(1+) — 1)Модп-7-1)n, Г (4 + — 1)Мос4п Ъ

Г=

m +1 г . = — 1 выхоУ д., „ы (г,,)-, ....„,...,. сумматора соединены с соответствующими входами первого слагаемого (E, "+1)-ro ter-разрядного сумматора, выход переноса (t, ")-гоЮ-разрядного сумматора соединен с входом переноса (1+1, " +1)-го N -разрядного сумматора, кроме выходов суммы и переносов т -разрядных сумматоров последнего столбца и выходов переноса F17 -разрядных сумматоров последней строки, выход переноса (K,д)-го

in-разрядного сумматора (d- 1,2,..., И-2) соединен с входом переноса (1,6+1)-го ю1 -разрядного сумматора, вход переноса (g, 1) — го Vn -разрядного сумматора соединен с шиной нулевого потенциала, выходы суммы (g, И-1)-х rn -разрядных сумматоров соединены с соответствующими входами первого слагаемого первого И-разрядног сумматора, выход переноса (K,n-1)-ro m-разрядного сумматора соединен с входом переноса первого й-разрядного сумматора, выход перен,са (P, и -1)-ro Ри-разрядного сумматора соединен с (p-xm+1)-ым входом второго слагаемого первого

0-разрядного сумматора соответственно (Р=1,2,..., K -1), выход переноса которого соединен с входом переноса второго < -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы перного Л -разрядного сумматора соответственно, входы второго слагаемого второго Г7 -разрядного сумматора и оставшиеся входы второго слагаемого первого tl -разрядного сумматора соединены с шиной нулевого потенциала, выходы суммы второго 0 -разрядного сумматора соединены с входами И -входового элемента И и входами второго слагаемого 0 -разрядного сумматора блока коррекции результата соответственно, входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потенциала и выходом

П-входового элемента И, выходы устройства соединены с выходами суммы

П-разрядного сумматора блока коррекции результата.

3. Матричное устройство для умножения чисел, содержащее блок форми1160398 рования частичных произведений, выполненный в виде матрицы и х и элементов И (tt-разрядность множителя и множимогo), и блок суммирования частичных произведений, причем первые входы элементов И I -й строки матрицы соединены с входом . -ro разряда множителя устройства, 1- -й разряд множимого которого соединен с вторыми входами (1 >P)-х элементов

И (3=1,2,...,t1, р =1,2,...,И), о т— л и ч а ю щ. е е с я тем, что, с целью расширения функциональных воэможностей за счет обеспечения умножения И -разрядных двоичных чисел по модулю -1, в него введены

->П первый и второй 11 -разрядные сумматоры и блок коррекции результата, содержац)ий 1 ) -входовый элемент И и

И-разрядный сумматор, а блок суммирования частичных произведений выполнен в виде матрицы < (rt 1) гпРазРЯдных сУмматоРов (m (П, K =1 trtj.

)П

+1, где (П/m$ — целая часть от деления и на m), причем вход ф -го . разряда первого слагаемого (ф=1,.

2,...ttt) (Р,1)-ro tn -разрядного сумматора (=1,2, ° ..,К) соединен с выходом (1 p)-го элемента И соответствевво, где g, =г-(г — l)m, 1 =P/щ)т1, вход -го разряда второго слагаемого (F,t )-ro m -разрядного сумматора (1 =1,?,...,П-1) соединен с выходом (1,p)-го элемента И соответственно, где 1 >1, Q =(1 +) -1)Nodtt -(1- — 1)n,Р= (от j+), г = -1), выход суымы (,Г)-ro m -разрядного сумматора соединены с соответствующими входами, первого слагаемого (Р,Г+1)-го М-разрядного сумматора, выход переноса (8,0)-го Ф-разрядного сумматора соединен с входом переноса (1+1,Г+1)гоЖ-разрядного сумматора, кроме выходов суммы и переносов п1 -разряд6ных сумматоров последнего столбца и

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

N) tt-(К-1)п1+1, f —.й выход суммы (I(,d)-го )и -разрядного сумматора, где j =tt-(К вЂ” 1)+1, д =1,2,...,и-2) соединен с входом переноса (1 d+1)-ro . I ,ttt-разрядного сумматора, вход переноса (f,1)-ro m -разрядного сумматора и 5 -е входы (К,r)-ro m -разрядного . сумматора (5 ) n-(K — 1)m+2) соединены с шиной нулевого)потенциала, 4 --е выходы суммы (K,r)-x tn -разрядных сумматоров (Ф >и -(К-1)в+1) не задействованы, f -й выход суммы (<,б — l)—

ro N -разрядного сумматора соединен с входом переноса первого Vl --разрядного сумматора, входы первого слагаемого которого соединены с соответствующими выходами суммы (P,tt-l)-х

N-разрядных сумматоров, выход переноса -(P, И -l)-го Ю -разрядного сумматора соединен с (p)tert+1)-м вхо. дом второго слагаемого первого 1— разрядного сумматора соответственно (Р=1,2,...,К-1), выход переноса которого соединен с входом переноса второго И -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы первого) 1— разрядного сумматора соответственно, входы второго слагаемого второго И— разрядного сумматора и оставшиеся входы второго слагаемого первого

И-разрядного сумматора соединены с шиной нулевого потенциала, выходы суммы второго ц -разрядного сумматора: соединены с входами И -входового элемента И и входами второго слагаемого 1 -разрядного сумматора блока коррекции результата соответственно, входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потенциала и выходом ю --входового элемента И, выходы устройства соединены с выходами суммы Vt -разрядного сум-. маторах) блока коррекции результата.

I сигналов (в частности, для циФровой обработки изображений), а также в системах кодирования,принципдействия. которых базируется на теории полей Галуа.

1160

Цель изобретения — расширение функциональных возможностей за счет обеспечения умножения, et-разрядных

П двоичных чисел по модулю M=2 -1.

На фиг.1 представлена структурная схема матричного устройстна для умножения чисел, пеpBbBf вариант; на фиг.2 — то же, второй вариант; на фиг. 3 — то же, третий вариант; на фиг.4 †. схема блока формирования l0 частичных произведений; на фиг.5— схема блока суммирования .частичных произведений; первый вариант; на фиг.б — то же, второй вариант; на фиг. 2 вЂ, то же, третий вариант; на фиг.8 — схема блока коррекции результата, Устройство (фиг. 1=3) содержит блок 1 формирования частичных произведений, блок 2 суммирования частич-, ных произведений, пер,ый 3 и второй

4 и -разрядные сумматоры и блок 5 коррекции результата.

Блок 1 формирования частичных произведений (фиг.4) содержит матрицу из г1» и элементов И 6, Блок 2 суммирования частичных произведений по первому варианту (фиг.5) содержит матрицу из 0 (и-2) одноразрядных сумматоров 7.

Блок 2 суммирования частичных произведений по второму варианту (фиг.б) содержит матрицу иэ K (ll-1)

m-разрядных сумматоров 8.

Блок 2 суммирования частичных произведений по третьему варианту (фиг.7) содержит матрицу из " (й-1)

rrl-y:àçðÿäHûõ сумматоров 9..

Блок 5 коррекции результата (фиг.Я) содержит п -входовый элемент

И 10 и rl -разрядный сумматор 11.

Блок формирования частичных про,изведений образует произведения

Oq 6 .. Произведения разрядов множимого на младший разряд множителя о 61 4> образуют слоно частичных произведений первой ступени fg а произведения разрядов множимого на второй разряд множителя 0q 6g — слово частичных произведений второй ступени jz и т.д.50 произведения разрядов множимого на старший. (и-й) разряд множителя О; 5п образуют слово частичных произведений Я -й ступени f . Слово f 2 сдвиrl нуто относительно слова f на один разряд влево, слово f> сдвинуто относительно слова К1 на два разряда влево и т.д ., слово f< сдвинуто от398 4 носительно слона f Hà (rt-1) раэря-.

f дов влево.

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

Vl -1 и-2

Множимое Л= 0> 2 + Я„.2 +... +

l1- l

+ О ?+ > -и множитель В= бп 2 + и-2

+ б„. 2 +... + 6> ?+ 6q поступают на входы,блока формирования частичных произведений, где формируются слова

f<,2,...,fz. Выходы элементов И блока формирования частичных произведений соединены с входами сумматоров блока 2 суммирования частичных произвел1ений. Так как ? =1 по модулю М=

=2 †.1, то умножение на степень двойки

2 равносильно циклическому сдвигу влево на rn разрядов и -разрядной двоичной записи множимого, т.е. ли-. нейный сдвиг слов f l,..., заменяется циклическим. Блок суммирования. частичных произведений осуществляет суммирование циклически сдвинутых слов частичных произведений. Слово частичных произведений первой ступени поступает на входы суммы сумматоров первого столбца без сдвига.

Слово частичных произведений второй ступени f2 поступает на вторые входы сумматоров первого столбца, причем это слово поступает с циклическим сдвигом на один разряд влево, слово f поступает на третьи входы сумматоров первого столбца с циклическим сдвигом на два разряда влево, слово f<на третьи входы сумматоров второго столбца с циклическим сдвигом на. три разряда влево и т.д. слово с циклическим сдвигом на rl -1 разряд поступает на третьи входы сумматоров последнего столбца.

В результате суммирования циклически сдвинутых слов частичных про.— изведений блоком 2 на выходах суммы матрицы сумматоров S,.... Яп получается г1 -разрядное слово, принадлежащее кольцу вычетов по модулю M=

П

2 -1, а на выходах переноса P

Рп - A -разрядное слово, сдвинутое линейно по отношению к слову на выходах суммы на один разряд влево.

Линейный сдвиг заменяется циклическим путем соединения выхода переноса сумматора и (rl-2) Р, с младшим разрядом входа второго слагаемого первого г1 -разрядного сумматора 3. Разряды слова переносов ,P>,..., P «1 подаются на входы вто$ 160398 рого слагаемого первого и -разряд.ного сумматора 3, начиная с второго разряда. Разряды fl -разрядного слова суммы подаются на входы первого слагаемого первого 11 -разрядного 5 сумматора 3. Суммирование слов суммы 5 = 5, S,..., Ьп и циклически сдвинутого слова переносов P = P, Р1, Р2, °,Pп 1 осуш ствл помоцью сумматора 3. На выходе этого сумматора образуется слово суммы.

Если в результате суммирования образуется перенос, то его необходимо просуммировать со словом суммы сумматора. 3, подавая в младший разряд.

Эту функцию выполняет сумматор 4.

В результате получается произведение А В (гос1 М), И=2 — 1, представ ленное в двоичном коде.

При построении матрицы сумматоров 2В в качестве элементарного сумматора можно использовать одноразрядный сумматор (первьп» вариант) либо m— разрядный. сумматор с обработкой переноса; причем тогда матрица сумматоров содержит К (и-1) сумматоров, где К =1л/гл1 е1, в случае если л не делится нацело на rn (третий вариант), и К = и /щ, если и делится нацело на

m (второй вариант). Зо

На каждый сумматор (для второго и третьего вариантов) поступает группа из m разрядов У(,, где а(=1,2,... К вЂ” номер rn -разрядного сумматора в столбце, У =1,2, 1 — номер ступени слова частичных произведений.

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

4 2 К суммь: Ядд1, Я„п1+1 р..., Ьщ +1. В ре» эультате суммирования на выходах

O-разрядных сумматоров последнего столбца получаются значения разрядов срова сумм 5щ,, S $к д где щ — группа из и разрядов сумматора. Выходы переносов (с учетом к, переноса бщ ig ) образуют слово„вида

ОО вОР 1 ° 00 ОРп 00 OSù + е-раэря- m -разря- rA -разрядов дов дов которое поступает ка входы второго слагаемого VI --разрядного сумматора к (за исключением переноса Sm +1, который поступает на вход переноса сумматора, на входы первого слагаемого которого поступает слово сумм (*иг.2 и 3).

Матричное устройство для умножения чисел имеет представления нуля

00...0 . и 11...1 р1-разря- П -разрядов дов так как слово 11...1 сравнимо

П -рааридов

f7 с нулем по модулю M=2 -1. В случае использования этого устройства для. обычного умножения чисел последнее обстоятельство не имеет значения, так как число 11...1 не должно

И -разрядов восприниматься как нуль. Для вычислений в конечном поле или в конечном и кольце с модулем вида M=2 -1 в связи с наличием двойного представления нуля окончательный результат необходимо корректировать. Коррекция результата умножения происходит в блоке 5 коррекции результата (фиг.8).

Результат умножения или ряда умножений и сложений по mod(2"-1) поступает на п -входовый элемент И 10 и одновременно на 0 -разрядный сумматор 11 (на входы одного из слагаемых на входы другого слагаемого подаются нулевые значения) . При равенстве всех разрядов единице на выходе элемента И 10 появляется единица, кото-. рая поступает на вход переноса Л разрядного сумматора 11. В результа- те на выходах этого сумматора устанавливаются нулевые значения, т.е. нуль получает единственное представление.

При использовании матричного устройства для умножения чисел для обычного умножения значения сомножителей должны удовлетворять условию

А- В<2 -1 где А и В - положительные двоичные числа. В этом случае результат умножения по июд (2"-1) ке отличается от результата обычного умножения. Например, если число разрядов сомножителей не превышает Й/2, то результат умножения таких сомножителей по

mod(2 -1) ке отличается от результат та обычного умножения.

1160398

1160398

1160398

O O Ю е е е е е е

Э O Ф е е е е е е ю е . е е е ю е юв ю е е ею е е

° °

O ° °

lI60398

02 Ь/

ay bg

1160398

<п

<п

<п

1160398

l 160398 m

I Ъ

/ я

М рС

m к, т

1, 50398

Составитель Е.Захарченко

Редактор О.йрковецкая Техред Л.Иикеш Корректор А.Тяско !

Заказ 3779/46 Тираж 710 Подписное

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

1.13035, Москва, Ж-35, Раушская наб., д. 4/5 л (Филиал ППП "Патент", г. Ужгород, ул. Проектная,4