Матричное устройство умножения по моD П Советский патент 1982 года по МПК G06F7/52 

1

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

Известно матричное устройство умножения, содержащее матрицу конъкжтив ных Элементов, каждый иЗ которых соотBeTCTBjreT определенному сочетанию значений сперандов, и выходной блок, объединяющий выходы тех элементов матри- д цы, которые соответствуют одному значению произведения. Количество элементов матрицы равно Р , где Р - основание матрицы счисления l .

Известно также устройство, которое, 5 с целью уменьшения числа элементов матрицы, использует свойство коммутативности умножения, т.е. диагональную симметрию таблицы умножения. Для этого в устройстве предусмотрены блоки 20 расстановки операндов и равенства сятерандов. Первый блок представляет собой совокупность двухвходовых дизъюнктивных элементов, входы которых объединяют однозначные входы от каждого операнда. Второй блок - это совокупность двухвходовых конъкшктивных элементов с теми же связями, что и у элементов первого блока. Выходы элементов второго блока соответствуют значениям диагональных элементов телицы умножения. Выходы элементов первого блока подаются в матрицу двухвходовых конъюктивных элементов так, что каждый из ее элементов связан с одной.парой выходов первого блока, а общее количество этих элементов равно числу таких пар. Для системы счисления с основанием Р число элементов матрицы равноР(р-)/2, а вместе с конъюктнвнымн элементами второго блока это число равно Р( Р iV 2. Таким образом, количество логических элементов, фиксирующих все сочетания значений операндов, меныие числа элементов табтшы умножения, равного Р 2 .

Одаако существует возможность дальнейшего уменьшения числа элементов матрицы и затрат оборудования на устройство умножения за счет того, что таблица умножения имеет более глубокие закономерности, чем простая диагональная симметрия. Целью изобретения является уменьшение затрат оборудования на создание матричного устройства умножения. Указанная цель достигается тем, что мйтричное устройство умножения по mod Р содержащее блок расстановки операндов, блок сравнения операндов, матрицу элеме тов И к блок формирования результата, причем входы блокр расстановки операндов соединены с входами блока операндов, выходы блока расстановки сятерандов соединены соответственно с входами эле ментов И матрицы, а выкрды блока формирования ре льтата являются выходам устройства, содержит блок выделения квадрантов, два блока объединения квадрантов, четыре элемента ИЛИ, три элемента И и блок разделения произведений причем входы первого и второго блоков объединения квадрантов соединены соответственно с входами первого и второго операндов устройства, соответствующих всем значениям операндов, кроме О и Р/ 2, входы операндов устройства, соответствующие значениям операндов с единицы по (Р/2 1), соединены соотве ственно с первой и второй группами Входов блока выделения квадрантов, выхо ды первого и Второго блоков объединения квадрантов соединены соответственно с входами блока расстановки операндов, выходы элементов И матрицы и блока сравнения операндов соединены соответственно с информационными входами блока разделения произведений, управляющие входы которого соединены с выходами блока выделения квадрантов, входы операндов устройства, соответствующие значениям операндов, равным О, соединены с входами первого элемента ИЛИ, входы операйдов устройства, соответству ющие значениям операндов, равным Р/2 соединены с входами первого элемента И и с входами второго элемента ИЛИ, выход второго элемента ИЛИ соединен с первыми входами второго и третьего эле ментов И, вторые Входы которых соединены соответственно с вькодами третьего и четвертого элементов ИЛИ, входы которых соединены соответственно с груп пой четнък и нечетных выходов блока расстановки операндов, входы первого элемента ИЛИ, элементов И и блока разделения произведений соединены с входами блока формирования результата. Блок выделения квадрантов содержит элементы И, ИЛИ и НЕ, причем входы блока первой группы соединены соответственно с входами первого элемента ИЛИ, входы блока второй группы соединенъ соответственно с входами второго элемента ИЛИ, выходы элементов ИЛИ соединены с входами первого элемента И, а через первый и второй элементы НЕ соответственно - с входами второго элемента И, выходь первого и второго элементов И соединены с входами третьего элемента ИЛИ, выход которого является nepBbnvi выходом блока, который соединен с входом третьего элемента НЕ. выход которого - второй выход .блока.. Блок объединения квадрантов содержит (Р/2-1) элементов ИЛИ, причем входы i -го элемента ИЛИ (ч 1,..., Р/2-1, Р/2+1,,,. Р-1) соединены с -f -м и (P-i)-M входами блока, а выход это- го элемента является -i -м выходом блока. Блок разделения произведений содержит две группы элементов И по 1/4Р (Р/2-1) элементов в каждой, причем первые входы элементов И каждой группы соединены соответственно с информационными входами блока, вторые входы элементов И первой группы соединены с одним управляющим входом блока, вторые входы элементов И второй группы соединены с другим управляющим входом блока, а выходы элементов И, обоих групп являются выходами блока. На фиг. 1 изображена структурная схема устройства; на фиг. 2 - таблица умножения по mod Р; на фиг. 3 - усеченная таблица по mod Р; на фиг. 4 схема блока выделения квадрантов; на фиг. 5 - схема блока объединения квадрантов; на фиг. 6 - схема блока расстановки операндов; на фиг. 7 - схемй/ блока сравнения операндов; на фиг. 8 схема матрицы элементов И;- на фиг. 9 схема блока разделения произведений; на фиг. Ю - схема блока формирования результата. Устройство содержит блок 1 выделения квадрантов, блоки 2 и 3 объединения квадрантов, блок 4 расстановки операндов, блок 5 сравнения операндовд. матрицу 6 элементов И, элементы ИЛИ 7, 8, 9 и 10, элементы И 11, 12 и 13, блок 14 разделения произведений и блок формирования результата 15. Входы предлагаемого устройства р/7-1 Р/24- ( 1 -Ур/2-( 4- -Ур (смысл всех сигналов определяется позже) соединены со входами блока 1 и блоков 2 и 3, причем Х; подаются в блок 2, а У - в блок 3 Выходы блоков 22, и 3W (,P/2соединены со входами блоков 4 и 5. Входы матрицы 6 соеди ;ены с выхода- ми блока 4Y (,P/2-l), одна группа которых (четные) с индексами i 2П (, 2,... пока 1 -i. Р/2) соединена со входами элемента ИЛИ 9, а другая (нечетные) с индексами I 2 п-1 (п 1, 2,.,. пока -i Р/2) - со входами элемента ИЛИ 1О. Входы устройства р/2 и Ур/2 подаются на вход элементов ИЛИ 8 и И 11, а входы устройства Х и Уд - на вход элемента ИЛИ 7, Выход элемента ИЛИ SYp подается на первые входы элементов И 12 и 13, вторые входы которых соединены соответственно с выходами элементов ИЛИ 9Тц и , Ю HP . Выходы блока 5 6 (.P/2-1) и матрицы 6Vx (,l.P/2-i) соединены с информационными входами блока 14, управляющие входы которого связаны с выходами Н;. и Н блока 1. Выходы блока . (( 1.Р/25 j i 1.Р/2-1), а также выходы элементов ИЛИ 7Уо- и U-llXp/2 Yp/2 , 12Vp/2 T и 13Ypi2Tj p подаются на вход блока 15. Выходы последнего являются выходами устройства Р ( 0,Р-1). Работа предлагаемого устройства поясняется на примере десятичного умножения ().-Для этого необходимо рассмотреть свойства таблицы умножения десятичных чисел и способ вычисления произведения с учетом этих свойств. Таблица умножения по mod Ю (фиг. представлена в виде матрицы размерности 1О«1О. Строю и столбцы матрицы с ответствуют значениям операндов от О до 9, а элементы матрицы - значенияг произведения соответствующих чисел. На фиг. 2 операнды обозначены буквами X и У с индексами, соответствукдшми зна чениям операндов. На фиг. 3 изофажена матрица разме ности 8-8, полученная из матрицы (фиг путем вычеркивания строк и столйюв, соответствующих значениям операндов, равным /О и 5 (Хд, УО, Х, У5). По лученная матрица разделена на четыре квадранта 44, пронумерованных числам 1,11 ,111 и IV . Значения элементов матри цы симметричны относительно обеих дй14агоналей, причем квадранты I иIV,И и , Шявляются попарно зеркальным отофажением друг друга. Далее числа в 1 и IV квадрантах симметричны относительно главной диагонали матрицы (слева - вниз . направо), а числа воИ и 111 квадрантах симметричны относительно вспомогательной диагонали (слева - вверх - нелраво), Эти особенности позволяют объединить имметричные элементы каждого квадрана, находящиеся на одинаковых позициях относительно своих осей симметрии, в дну группу. Линии на фиг. 3, соединяюие соответствующие элементы, образуют в общем случае восьмиугольники. Для элеентов, находящихся на диагоналях, восьиугольники превращаются в квадраты. олученные таким образом группы элеентов обладают следующими свойствами: лементы одной группы имеют только два разаьа. значения, причем элементы 1 и IV П , и Шквадрантов попарно совпадают; ары асачений элементов в разных группах, встречаются всегда в одних и тех же соетаниях: t. и 9, 2 и 8, 3 vi 7, 4 и 6. На фиг. 3 показаны две грутшы для пары 4 и 6. Одна группа обра ет восьмиугольник, другая квадрат. Указаншле свойства таблицы умножения используются для эализации схемы младщего разряда произведения (произведения по 1О). Вводятся промежуточные переменные 21, W;|, Y , S (i 1, 4), которые получаюггся из исходных переменных с помощью следующих- логических операций: Z.,X,v)(, .vY, 22 X2VKg Wj-YjVY Zj XjVXy WjY.vy )(, W4-Y,vY, Y ZiVW- (4-4,4) (3) Si 7./W ( U) 14). Каждая группа из восьми элементов, лежащих в вершинах восьмиугольника, . получается с помощью конъюнкции соот ветствукяцих переменных. В примере на фяг. 3 восьмиугольник получается так. Действительно: V -X X4VX X4VX Y4vX Y vX9X4VX9X6VXqY4V VX,,,Y6VY,X4V (здесь и далее для упрощения записи знак конъюнкции опушен ). В полученном шлражении конъюнкции одноименных переменных (X) Xj и У тождественно равны О, так как одни и те же переменные не могут одновременно иметь разные значения. Таким офазом: - X. х Y,Y X,Y4V ХрУб фС у Х, , т.е. группа соответствующая V V , содержит восемь элементов, объединенных упомянутым выше восьмигранником. Рассмотренные группы элементе обозначаются .V). (5) . Группы из четырех элементов (квадраты) отофажаются переменными (4 Так квадрат на фиг. 3 сжисывается переменной 5 f,Действительно Ye, W Принадлежность элемента матрицы к какой-либо паре квадрантов I к IV или II и III выражается переменными Н и Н2 соответственно. Для получения Н и Н2 доегаточно определить принадлежност элемента либо к кващ)анту I (К), либо к квадранту IV (К). R./X,vXaVX3vX4//Y/YgVY3vY4/; ,vXjvX3vX4//Y,vYjVV vY /, H, . Для того, чтобы в каждой группе элементы, разделить по даачениям, достаточно ветть конъюнкцию и . или S с Н1 lum с Н.. Так в одном из приведенных ранее примеров соответствует числу 4, а 1)4.4 Н соответствуе т чис 6. Каждое значение nef«oro разряда про изведения получается путем объединения элементов с одинакоными значениями, вы деленных описанным образом из разных групп. В результате для раашпс значени 1-го разряда произведения, обозначаемы Р| ( О,9),где i -. значение, получаются выражения: ,H,vs,H, Pa-Uu i U3,4H,. ,3 P4-S2H,U,4H,vS4R,vU.3Hi Рб-52Йли,дН,,уи.„Н, (8) 7,г ,,H,vu,H,vu,,,H ,. Следует отметить, что выражения для пар Р и Рд, Р2 и Pg, Р и Р., Р и аналогичны и отличаются лишь тем, что множители Н и Н,( в них инвертированы. Результат, равный О (Р0)| получается, если хотя бвы один из операндов равен О или при умножении 5 на четное число, а результат, равный 5 (PC), получается при умножении 5 на нечетное число (в том числе на само себя).: Для выработки этих результатов вводятся переменные о, Yj.TijT .Y, а 5 5 %TVjVV4 ViVY3 Po V«vV5T4r.Vl и Ps X5Y5VV5.TH,.(4) Действительно, из выражений (1Ь (2) и (3) получается V4T /X5vY5//ZjVW,vZ.4vW4A. -/X5 Ys//X,vXgVY-YgvX4vX vY4vV6/ X5,VVY6-Y8/ 5/ 2 4 6 0/, так как конъюнкции одноименных переменных X X или У У тождественно равны О, поскольку один операнд не может одновременно принимать два разных значения. Аналогично VHT- S/V Сб) Таким образом, в первом случае обеспечивается объединение всех элементов матрицы (фиг. 2), соответствующих произведениям 5 на четные числа, а Ьо втором - произведениям 5 на нечетные числа. В выражении (13) к (15) добавляются строка и столбец матрицы, соответствующие Х и Уд, а в вьфажении (14) к (16) добавляется элемент матрицы, соответствующий произведению . Анапогичными свойствами обладают таблицы умножения по другим (четным) основаниям, и для них могут быть составлены подобные выражения. В соответствии со сказанным блок 1 (фиг. 1) представляет собой совокупность элементов И 16, 17 , ИЛИ 18-2О и НЕ 21-23, реализующих логические выраже кия типа (6 и (7)-для выработки сигналов Н и Hjf. Блоки 2 и 3 реализуют логические выражения типа (1) и (2) соответственно. Они содержат по/Р/2-1/ двухвходовых элементов ИЛИ 24-28, каждый из которых связан со входами данного устройства соответствующими значениям одного операнда в сочетаниях и /P-i/. Выходы элементов ИЛИ являются соответственно для блока 2 сигналы 2 , для блока 3 сигналы Wj ( I,P/2--l). Блок 4 реализует логические выражения типа (3). Он содержит /Р/2-1/ двухвходовых элементов ИЛИ 28-31, каждый из которых связан с однозначными сигналами Z 4 и W для выработки сигналов V (( 1,Р/2-1). Блок 5 реали ет логические выражения типа (4)i вырабатывая сигналы 5 ( 1,Р/2-1). Он состоит из /Р/2-1/ элементов И 32-35, каждый из которых со единен с однозначными выходами 2, и VV блоков 2 и 3 соответственно. Матрица 6 реализует выражения типа (5), вы рабатывая сигналы (i; i ,i l,P/2 -1). Она содержит 4 Р/2-1/ /Р/2-2/ элементов И 36-41. Каждый из них CBH зан с одной парой выходов V; иУ блок 4 из всех возможных сочетаний пар этих выходов. Элементы ИЛИ 7 и 8 реализуют выражения типа (9) и (1О), а элементы ИЛИ 9 и 1О - выражения типа (11) и (12) соответственно. Элемент И 11 реализует конъюнкцию Хр/2. Ур/2 из выражения типа (14), а элемен ты И 12 и 13 - конъюнкции Vp,2 Т fj иУр/2 Ти4 3 выражений типа (13) и (14) соответственно. Блок 14 обеспечивает реализацию конъюнкций из выражений типа 43). Он сопеожит две группы эле ментов в каждой. Каждый элемент одной группы вырабатывает сигнал а каждый элемент другой группы - Н;, или 5 Н . Соответствующие сигналы поступают из блоков 1 и 5 л матрицы 6. Блок 15 реализует выражения типа (8) без содержащихся в них конъюнкций. Он содержиРг группу элемен тов ИЛИ 62-69. Если отдельные выражения из (8) состоят из одного члена, как например в случае десятичного умножения для Pg и Р можно условно считать, что выходной блок просто проводит соответствующий сигнал на выхоп устройства. На схемах фиг. 4-9 показана одна из возможных реализаций блоков для случая десятичного умножения на логичесих схемах И, ИЛИ и НЕ. .Блок объединения ешерандов (фиг. 5) ходит в устройство в двух экземплярах о одному из каждый операнд. Один опеанд указан в скобках, другой без скобок. Изофаженная реализация точно Ьледует огическим выражениям (1) - (14). Одако возможны и другие реализации, связанные с преобразованием этих выражеий в соответствии с теоремой де Моргйна, а также с использованием логических элементов, реали кхцих сложные логические функции. Может быть произведена минимизация выражений. Например, в выражениях типа (8) можно вынести за скобки подобные члены. Так ля Р4 и F , в частности, получается, что P4-/S2,,i/H, . P64S2VU 4lV 5442. Таким образом, может быть препусмотрена предварительная сборка некоторых сигналов с последукяцей подачей их на схемы И. В этом случае блок 14 состоит из элементов ИЛИ и И, причем общее „ ы „л. их количество меньше количества элементов И в первом варианте. Следует также отметить, что разделение данного устройства на блоки является логическим. Физически при наличии элемент;, реализующих сложные логические функции, логические границы блоков могут проходигь внугри этих эпеменгов. Предложенное устройство дает экономию затрат оборудования. Если эти затраты выразить в количестве двухвходовых и одновходовых логических элементов И,. ИЛИ и НЕ, то окажется, что сяема известного устройства требует 91 элемент, а схема данного устройства - . 66 элементов,, что составляет экономию более 25%. Соответственно и-уменьшается количество соединений в схеме. Формула изобретения 1. Матричное устройство умножения по mod Р, содержащее блок расстановки операндов, бпоЕ сравнения ешерандов.

матрицу элементов И, и ок формирования результата, причем входы блока расстановки операндов соединены со входами блока сравнения операндов, выходы блока расстановки операндов соединены соответственно с входами элементов И матрицы, а выходы блока формирования результата являются выходами устрой ства, отличающееся тем, что, с целью сокрашения затрат оборудования, устройство содержит блок выделенияквадрантов, два блока объединения квадрантов, четыре 9леме11та ИЛИ, три элемента И и блок разделения произведений, причем входы первого и второго блоков объединения квадрантов соединены соответственно с входами первого и второго операндов устройства, соответствующих всем значениям операндов, кроме О и P/2.t входы операндов устройства, соот ветствующие жачешшм операндов.с единицы по (Р/2-1), соединены соответствено с первой k второй : группами входов выделения квафантов, выходы первого и второго блоков объединения квадрантов соединены соответственно с входами блока расстановки операндов, въкоды элементов И матрицы и блрка сравнения сшерандов соединены соответственно информационными входами блока разделения произведений, управляющие входы которого соединены с выходами блока выделения квадрантов, входы операндов устройства, соответствующие значениям операндов, равным О, соединены свходами первого элемента ИЛИ, входы операндов устройства, соответствующие значе.ниям операндов, равным Р/2, соединены с входами первого элемента И и с входами вторйго элемента ИЛИ, выход второго элемента ИЛИ соединен с первыми входами второго и третьего элементов И, вторые входы которых соединены соответственно с выходами третьего и четвертого элементов ИЛИ, входы которък соединены соответственно с группой четных и нечетных выходов блока расстановки сяерандов, входы первогчэ элемента ИЛИ, элемеетов И и блока разделения

Произведений соединены с входами блока формировашш результата.

2 ycTpolKTBo ПОП.1, отливающееся тем, что, блок выделения квадрйнтов содержит элементы И, ИЛИ и НЕ, причем входы блока первой группы соединены соответственно с входами первого элемента ИЛИ, входы блока второй группы соединены соответственно с входами второго элемента ИЛИ, въосоды элементов ИЛИ соединены с входами первого элемента И, а через первый и второй элементы НЕ соответственно - с второго элемента И, выходы первого и второго элементов И соединены с входами третьего элемента ИЛИ, выход которого является первым выходом блока который соединен с входом третьего элемента НЕ,, вьосод которого является вторьп выходом блока.

3. Устройство по П.1, отличающееся тем, что блок объединения квадрантов содержит (Р/2-1) элементов ИЛИ, причем входы -i -го элемента ИЛИ (Х 1...., Р/2-1, Р/2+1,..., Р-1) соединены с i -м и (Р- i )-м входами блока, а выход этого элемента является ч -м выходом блока.

. 4. y cTpofiteTBo по П.1, отличающееся тем, что блок разделения произведений .содержит две группы элементов И по 1/4 Р (Р/2-1) элементов в каждой, причем первые входы элементов И каждой группы соединены соответственно с информационными входами блока, вторые входы элементов И первой группы соединены с одним управляющим входом блока, вторые входы элементов И второй группы соединегал с другим управляющим входом блока, а выходы элементов И обеих групп являются выходами блока.

Источники информации,

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 259479, кл. Q 06 Г 7/38, .

2.Авторское свидетельство СССР № 496555, кл. Q 06 F 7/38, 1974 (прототип).

фи.

S

т

Фиг.З

36

/f

J7

IL Ji.

J«

Jii J

Л9

JlJ

JlLS

w

Лм

фиг. 9

иг.10