Матричное устройство для умножения чисел (его варианты) Советский патент 1985 года по МПК G06F7/49 

кого сумматора соединен с входом первого разряда второго слагаемого Л-разрядного сумматора, выход переноса которого соединен с входом переноса второго П -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы первого И-разрядного сумматора соответственно, вход переноса первого II-разрядного сумматора и входы второго слагаемого второго И -разрядного сумматора соединены с шиной нулеврго потенциала, выходы суммы второго flразрядного сумматора соединены с входами И -входового злемента И и входами второго слагаемого П -разрядного сумматора блока коррекции результата соответственно, входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потенциала и выходом 1-входового элемента И, выходы устройства соединены с выходами суммы П -разрядного сумматора блока коррекции результата.

2. Матричное устройство для умножения чисел, содержащее блок формирования частичных произведений, выполненный в виде матрицы П п элементов И (п-разрядность множителя и множимого), и блок суммирования частичных произведений, причем первые входы элементов И 1 -и строки матрицы соединены с входом 1-го разряда множителя устройства, -и разряд 1ножимого которого соединен с втррь1ми входами (, J-)-x элементов И О 1,2,.. . ,п, j 1, 2,...,л), отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения умножения и -разрядных двоичных чисел по модулю , в него введены первый и второй И -разрядные сумматоры и блок коррекции результата, содержарщй П -входовый элемент И И-разрядный сумматор, а блок суммирования частичных произведений выполнен в виде матрицы (П-1)т-разрядных сумматоров (г77 П , К - целое число), причем вход q,-го разряда первого слагаемого ( 1,2,... ,т) (Р,1)-го m -разрядного сумматора (,2,...К) соединен с выходом (l,j.)-ro элемента И соответственно, где i-(f-1)w, f { /rn}n, вход -го разряда второго слагаемого (t,()-ro W-разрядного сумматора (,.,..,-1) соединен с выходом

а,)-го элемента И соответственно, , q. (-i+J-1)Modn-(T-1)n,

р /О )Modn t 1mJ

+1 г -1, выходы суммы (,)-го W1 -разрядного сумматора соединены с соответствующими входами первого слагаемого (,+1)-го 17-разрядного сумматора, выход переноса (,)-го/ 1-разрядното сумматора соединен с входом переноса (t+1,/ +1)-го W-разрядного сумматора, кроме выходов суммы и переносов т -разрядных сумматоров последнего столбца и выходов переноса W -разрядньк сумматоров последней строки, выход переноса (К,с/)-го т-разрядного сумматора (с/-1,2,..., h-2) соединен с входом переноса (1,о(+1)-го m-разрядного сумматора вход переноса (,1)-го r)-разрядного сумматора соединен с шиной нулевого потенциала, выходы суммы (t, И-1)-х m-разрядных сумматоров соединены с соответствующими входами первого слагаемого первого И-разряднот сумматора, выход переноса . (К,п-1)-го W-разрядного сумматора соединен с входом переноса первого М-разрядного сумматора, переHivca (Р,П-1)-го )Г1-разрядного сумматора соединен с ()-ым входом второго слагаемого первого П-разрядного сумматора соответственно (,2,..,, К-1), выход переноса которого соединен с входом пер нрса второго 1 -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы первого Л -разрядного сумматора соответственно, входы второго слагаемого второго г -разрядного сумматора и оставшиеся входы второго слагаемого первого П -разрядного сумматора соединены с шиной нулевого потенциала, выходы суммы второго 1 -разрядного сумматора соединены с входами Г -входового элемента И и входами второго слагаемого П -разрядного сумматора блока коррекции результата соответственно , входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потенциала и выходом П-входового элемента И, выходы устройства соединены с вьпсодами суммы П-разрядного сумматора блока коррекции результата.

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

И (1 1,2И, 1,2,...,), о т л и ч а ю щ. е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения. умножения И -разрядных двоичных чисел по модулю 2-1, в него введены первый и второй )7 -разрядные сумматоры и блок коррекции результата, содержащий П -входовый элемент И и h-разрядный сумматор, .а блок суммирования частичных произведений выполнен в виде матрицы (п-1) гп -ч разрядных сумматоров (т п , К { /ni}+ 1, гдй tn/mj - целая часть от деления п наш), причем вход (-го разряда первого слагаемого ( 1,. 2,,,.те) (f,1)-го гп -разрядного сумматора (,2,...,К) соединен с выходом (1,)-го элемента И соответственно, где ( j.-(f-i)rn, f /т} + 1 вход О.-го разряда второго слагаемого (Р, г)-го rrj-разрядного сумматора (Г 1,2,... ,П-1) соединен с выходо (l,)-ro элемента И соответственно, где , ( (i+j.-1)Modn -(f-l)n,P

„ J(l+J-1)Koc/nl . . - 1 irri7+ 1), выход суммы (t,r)-ro 171 -разрядного сумматора соединены с соответствующими входами первого слагаемого (Р,Г+1)-го 1-раз рядного сумматора, выход переноса ()-го )Т1-раз рядного сумматора соединен с входом переноса (+1,Г+1)гот-разрядного сумматора, кроме выходов суммы и переносов т -разрядных сумматоров последнего столбца и П-х выходов суммы т -разрядных сумматоров последней строки, где И п-(К-1)пи-1, f й выход суммы (k,d)-ro«ii -разрядного сумматора, гдef П-(К-1) + 1, ,2,.,.,n-2) соединен с входом переноса (1,4-+1)-гго

т-разрядного сумматора, вход переносА (P,1)-row -разрядного сумматора и 5 -е входы (К,г)-го m-разрядного, сумматора (S f7-(K-i)m-«-2) соединены

с шиной нулевого потенциала, -t -е выходы суммы (К,Г )-х m-разрядных

сумматоров (t п -(К-1)т+1) не задействованы, f -и выход суммы (К,Л-1)го /tj -разрядного сумматора соединен с входом переноса первого М -разрядного сумматора, входы первого слагаемого которого соединены с соответ,ствующими выходами суммы (t,«-1)-x П7-разрядных сумматоров, выход переноса - (р,П-1)-го W -разрядного сумматора соединен с (pxtrT + t)-M входом второго слагаемого первого П разрядного сумматора соответственно (,2К-1), выход переноса которого соединен с входом переноса второго И -разрядного сумматора, входы первого слагаемого которого соединены с выходами суммы первого И разрядного сумматора соответственно, входы второго слагаемого второгоrtразрядного сумматора и оставшиеся входы второго слагаемого первого h-разрядного сумматора соединены с шиной нулевого потенциала, выходы суммы второго П -разрядного сумматора- соединены с входами (1 -входового элемента И и входами второго слагаемого п -разрядного сумматора блока коррекции результата соответственно, входы первого слагаемого и вход переноса которого соединены соответственно с шиной нулевого потен1щала и выходом и-входового эяемента И, выходы устройства соединены с выходами суммы И -разрядного сум-. матор / блока коррекции результата.

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

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

сигналов (в частности, для цифровой обработки изображений) , а также в сие темах кодирования,принципдействия. которых базируется на теории полей Галуа. 3 Цель изсУбретения - расржрение функциональных возможностей за счет обеспечения умножения, ЯП-разрядных двоичных чисел по модулю -1, На фиг.1 представлена структурная схема матричного устройства для умно жения чирел, нервьйвариант; на фиг.2 - то же, второй вариант; на фиг. 3 - то же, третий вариант; на фиг.4 - схема блока формирования частичных произведений; на фиг.5 схема блока суммирования .частичньгх произведений; первый вариант; на фиг.6 - то же, второй вариант; на фиг. -г то же, третий вариант; на фиг.8 - схема блока коррекции резул тата., . Устройство (фиг.1-3) содержит блок 1 формирования частичных произведений, блок 2 суммирования частичных произведений, пер.;ый 3 и второй А п -разрядные сумматоры и блок 5 коррекции результата. Блок 1 формирования частичных произведений (фиг.4) содержит матрицу из элементов И 6, Блок 2 суммирования частичных про изведений по первому варианту ЧФИГ.5) содержит матрицу из П (п-2) одноразрядных сумматоров 7. Блок 2 суммирования частичных произведений по второму варианту (фиг.6) содержит матрицу из К (п-1) т-разрядных сумматоров 8. Блок 2 суммирования частичных про изведений по третьему варианту (фиг.7) содержит матрицу из К (п-1) т-разрядных сумматоров 9. EjioK 5 коррекции результата (фиг.8) содержит п -входовый элемент И 10 и П -разрядный сумматор 11. : Блок формирования частичных про, изведений образует произведения 0 О . Произведения разрядов множимо го на младший разряд множителя образуют слово частичньрс произведений первой ступени f, а произведения разрядов множимого на второй разряд множителя Of 02 ,- слово чactичныx произведений второй ступени /2 и т.д произведения разрядов множимого на старший (п-й) разряд множителя 0 Or образуют слово частичньк произведений п -и ступени f . Слово f2 сдвинуто относительно слова /у на один разряд влево, слово f сдвинуто относительно слова f на два разряда влево и т.д ., слово ff сдвинуто от9S4носительно слова f на (rj-1) разрядов влево. Устройство работает следующим образом. Множимое Л Qf, 2 + С|„., -2 +.. .+ + Og- 2+ а и множитель B 6rj-2 + + 6„,... 6 поступают на входы .блока формирования частичных произведений, где формируются слова , f , ..., fp. Выходы элементов И блока формирования частичньгх произведений соединены с входами сумматоров блока 2 суммирования частичных произведений. Так как rio модулю М 2 -1, то умножение на степень двойки 2 равносильно циклическому сдвигу влево на m разрядов п -разрядной двоичной записи множимого, т.е. ли-. нейный сдвиг слов f, ...,f заменяется циклическим. Блок суммирования, частичных произведений осуществляет суммирование циклически сдвинутых слов частичных произведений,. Слово частичных произведений первой ступени- поступает на входы суммы сумматоров первого столбца без сдвига. Слово частичных произведений второй ступени f поступает на вторые входы сумматоров первого столбца,причем это словопоступает с циклическим сдвигом на один разряд влево, слово f, поступает на третьи входы сумматоров первого столбца с циклическим сдвиfoM на два разряда влево, слово f на третьи входы сумматоров второго столбца с циклическим сдвигом на. три разряда влево и т.д. слово fq с циклическим, сдвигом на п -1 разряд поступает на третьи входы сз мматоров последнего столбца. В результате суммирования циклически сдвинутых слов частичных произведений блоком 2 на выходах суммы матрицы сумматоров S ,...., 5 получае.тся п -разрядное слово, принадлежащее кольцу вычетов по модулю М 2 -1, а на вькодах переноса Р. ,..., Pf7 П -разрядное слово, сдвинутое линейно по отношению к слову на вьйсодах суммы на один разряд влево. Линейный сдвиг заменяется циклическим путем соединения выхода переноса сумматора г (п-2) Р, с младшим разрядом входа второго слагаемого первого П -разрядного сумматора 3. Разряды слова переносов Р| , Р2,.. ., f.., подаются на входы второго слагаемого первого п -разрядного сумматора 3, начиная с второго разряда. Разряды п -разрядного сло ва суммы подаются на входы первого слагаемого первого п -разрядного сумматора 3. Суммирование слов суммы 5 5 2 п и цикличес ки сдвинутого слова переносов Р Р PJ , Pj ,...,Pr,-i осуществляется с помощью сумматора 3. На выходе этого сумматора образуется слово суммы Если в результате суммирования образуется перенос, то его необходимо просуммировать со словом суммы сумматора- 3, подавая в младший разряд Эту функцию выполняет сумматор 4. В результате получается произведение АВ (nod М), 1, представленное в двоичном коде.; При построении матрицы сумматоро в качестве элементарного сумматора можно использовать одноразрядный сумматор (nepBbrii вариант) либо тразрядный сумматор с обработкой пер носа, причем тогда матрица сумматоров содержит К (п-1) сумматоров, где К 1 в случае если п н делится нацело на m(третий вариант и К /т, если п делится нацело Ш (второй вариант). На каждый сумматор (для второго и третьего вариантов) поступает группа из m разрядов где 1,2,... К - номер m-разрядного сумматора в столбце, .,У 1,2, П - номер ступени слова частичных произведений. В третьем варианте устройства сумматоры последней строки натри- цы используются не полностью. В качестве вькодов переносов сумматоров последней строки выступают выходы cyMMf: , Srri+i ,..., . В ре эультате суммирования на выходах W-разрядных сумматоров последнего .столбца получаются значения разря-сумм 5,,5Д ,...,S; дов слова где S группа из m разрядов сум Выходы переносов (с учетом матора переноса ) образуют слово вида OO... ...ОО...ОР OO...OSmH Т1 гп-разря- гп-разря- m-разрядов дов дов которое поступает на входы второго слагаемого П -разрядного- сумматора (за исключением переноса s|J, ко торый поступает на вход переноса сумматора, на входы первого слагаемого которого поступает слово сумм Sjn , 5,..., s;;,. (фи.2 и 3), Матричное устройство для умножения чисел имеет представления нуля .00...О/ и J1...1, п-разря- п -разрядов дов так как слово , 11 ... 1 сра:внимо П -разрядовс нулем по модулю -1. В случае использования этого устройства для обычного умножения чисел последнее обстоятельство не имеет значения, так как число, 11...1. не должно П -разрядоввосприниматься как нуЛь. Для вычис-; лений в конечном поле или в конечном кольце с модулем вида -1 в связи с наличием двойного представления нуля окончательный результат необходимо корректировать. Коррекция результата умножения происходит в блоке 5 коррекции результата (фиг.8). Результат умножения или ряда умнокений и сложений по inod() поступает на п -входрвый элемент И Ю и одновременно на П -разрядный сумматор 11 (на входы одного из слагаемых на входы другого слагаемого подаются нулевые значения). При равенстве всех разрядов единице на выходе элемента И 10 появляется единица, которая поступает на вход переноса П разрядного сумматора 11. В результате на выходах зтого сумматора устанавливаются нулевые значения, т.е. . нуль получает единственное представление . . При использовании матричного устройства для умножения чисел лпя обычного умножения значения сомножителей должны удовлетворять условию А -Г где А и В - полсмкитеяьные двоичные числа. В этом случае результат умножения по tnod () не отличается от результата обычного умножения. Например, если число разрядов сомножителей не превышает П/2, то результат умножения таких сомножителей по mod С ) не отличается от результата обычного умножения.

Ml

Qrf

Cs

c

c

M

to

vr

0

1 «

cei

-J

bj

«

M

to w

tr

«0

T f i-r f I-l

41

1/Г vo

, «4

S

СЧ JN

-ч: ч:

5

N

sJ

J4

-- -c

с:

o

c§

ч

o

i

/ ciT

ci:

c. X

с

с

«Ч

Q-i

ar

Hi

(

& %/

an

fir/ 2

n

Фиг 4

Фиг.6

Фцг:в