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

 

В. С. Бренер, Л. Я. Мапярес, Г. A. Поляк, Л. и Т. И. Чергинцева (72) Авторы изобретения м тайюк,.1, -:, ь (71) Заявитель

Всесоюзный научно-исследовательский институт оргтехники (54) МАТРИЧНОЕ УСТРОЙСТВО УМНОЖЕНИЯ

ПО щ<Я Р

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

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

2 матрицы счисления )1)

Известно также устройство, которое, с целью уменьшения числа элементов матрицы, использует свойство коммутативности умножения, т.е. диагональную симметрию таблицы умножения. Дпя этого в устройстве предусмотрены блоки 20 расстановки операндов и равенства операндов. Первый блок представляет собой совокупность двухвходовых дизъюнктивных элементов, входы которых обьеди- . няют однозначные входы от каждого операнда. Второй блок — это совокупность двухвходовых конъюнктивных элементов с теми же связями, что и у элементов первого бпока. Выходы элементов второго блока соответствуют значениям диаFoHMIsBHx элементов таблицы умножения. Выходы элементов первого бпока подаются в матрицу двухвходовых конью-ктивных элементов так, что каждый иэ ее элементов связан с одной. парой выходов первого блока, а общее количество этих элементов равно числу таких пар.

Для системы счисления с основанием P число элементов матрицы равно P(p-() (2, а вместе с коньюктйвными эпементамй второго блока это число равноРф+()/ g, Таким образом, копичестгво логических элементов, фиксирующих все сочетания значений операндов, меньше общего числа эпементов табпицы умножения, равного Р $2)

Однако существует возможность дальнейшего умены ения числа элементов

3 94371 матрицы и затрат оборудования на устройство умножения за счет того, что таблица умножения имеет более глубокие закономерности, чем простая диагональная симметрии. S

Целью изобретения является уменьщение затрат оборудования на создание матричного устройства умножения.

J.

Указанная цель достигается тем, что tO матричное устройство умножения поп)од, содержащее блок расстановки операндов, блок сравнения операндов, матрицу элементов И и блок формирования результата, причем входы блокр расстановки операн- lS дов соединены с входами блока операндов, выходы блока расстановки операндов соединены соответственно с входами элементов И матрицы, а выходы блока формирования результата являются выходами 2а устройства, содержит блок выделения квадрантов, два блока обьединения квадрантов, четыре элемента ИЛИ, три элемента И и блок разделения произведений, причем входы первого и второго блоков обьединения квадратов соединены сооТ ветственно с входами первого и второго операндов устройства, соответствуюших всем значениям операндов, кроме 0" и

P/ 2", входы операндов устройства, соответствующие значениям операндов с единицы по (P/2 — 1), соединены соответственно с первой и второй группами входов блока выделения квадрантов, выходы первого и второго блоков объединения квадрантов соединены соответственно

35 с входами блока расстановки операндов, выходы элементов И матрицы и блока сравнения операндов соединены соответственно с информационными входами бло40 ка разделения произведений, управляющие входы которого соединены с выходами блока выделения квадрантов, входы операндов устройства, соответствующие значениям операндов, равным "0", соединены с входами первого элемента ИЛИ, входы операндов устройства, соответствующие значениям операндов, равным "P/2", соединены с входами первого элемента

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

Блок выделения квадрантов содержит элементы И, ИЛИ и НЕ, причем входы блока первой группы соединены соответственно с входами первого элемента

ИЛИ, входы блока второй группы соединены соответственно с входами второго элемента ИЛИ, выходы элементов ИЛИ соединены с входами первого элемента

И, а через первый и второй элементы

НЕ соответственно — с входами второго элемента И, выходы первого и второго элементов И соединены с входами третьего элемента ИЛИ, выход которого является первым выходом блока, который соединен с входом третьего элемента

HF.. выход которого — второй выход .блоKB., Блок обьединения квадрантов содержит (P/2-1) элементов ИЛИ, причем входы -го элемента ИЛИ (4 =1,..., Р/2-1, Р/2+1,... P-1) соединены с -м и (P- )-м входами блока, а выход это-го элемента является -м выходом блэка.

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

На фиг. 1 изображена структурная схема устройства; на фиг. 2 — таблица умножения по mod Р; на фиг. 3 — усеченная таблица по mod Р; на фиг. 4— схема блока выделения квадрантов; на фиг. 5 — схема блока объединения квадрантов; на фиг. 6 — схема блока расстановки операндов; на фиг. 7 — схем . блока сравнения операндов; на фиг.. 8— схема матрицы элементов И; на фиг. 9схема блока разделения произведений; на фиг. 10 - схема блока формирования результата.

Устройство содержит блок 1 выделения квадрантов, блоки 2 и 3 объединения квадрантов, блок 4 расстановки операндов, блок 5 сравнения операндов., матрицу 6 элементов И, элементы ИЛИ 7, 8, 9 и 10, элементы И 11, 12 и 13, блок 14 разделения произведений и блок формирования результата 15.

943714 6 агоналей, причем квадранты 1 и1Ч,II и, Шявляются попарно зеркальным отображением друг друга. Далее числа в1 и17 квадрантах симметричны относительно главной диагонали матрицы (слева — внизнаправо), а числа во11 и1Нквадрантах

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

15 в общем случае восьмиугольники. Для элементов, находящихся на диагойалях, восьмиугольники превращаются в квадраты.

Полученные таким образом труппы элементов обладают следующими свойствами:

e элементы одной группы имеют только два разных значения, причем элементы 1 и1T

Ц, и 1Иквадрантов попарно совпадают, пары значений элементов в разных группах. встречаются всегда в одних и тех же сочетаниях: 1 и 9, "2" и "8", "3" и

"7, 4 и 6". На фиг. 3 показаны две ,группы для пары 4 и 6. Одна гоуппа образует восьмиугольник, другая квадрат.

Указанные овонотва таблнлы умножения используются для аализации схемы младшего разряда произведения (произведения по 10).

Вводятся промежуточные переменные

Z„,%„,Ч», б» (» =1, 4); которые полу35 чаются из исходных переменных с помоо- щью следующих. логических операций:

2,» =Х„ч Х9

2 . = Х ч Х8

Z,„==Х чХ8

Ь4= Х4,ч Х<

s; = . „л щ; (< - <,4) (4) .

Входы предлагаемого устройства

Х 1-ух p) ел», Х p » -Х р 4, У» -Уру2 «1

Ур/2+» -Ур-» iсл всех сигналов определяется позже) соединены со входами блока 1 и блоков 2 и 3, причем

Х подаются в блок 2, а У вЂ” в блок 3.

Выходы блоков 2Z „, и 3 УЧ (» =1,Р/2соединены со входами блоков 4 и 5.

Входы матрены 6 свеон:.ены с выходамн блока »У; (i=1,p/2.— 1), одна rpynn которых (четные) с индексами j =2 l1 (й=1, 2,... пока» а P/2) соединена со входами элемента ИЛИ 9, а другая (н четные) с индексами 5 =2п-1 (и =1, 2,... пока» с P/2) — со входами эле мента ИЛИ 10. Входы устройства Х оу> и Ур<< подаются на вход элементов

ИЛИ 8 и И 11, а входы устройства Х и У, — на вход элемента ИЛИ 7, Выход элемента ИЛИ 8Ур/< подается на нервы входы элементов И 12 и 13, вторые входы которых соединены соответственно с выходами элементов ИЛИ 9Tur и

10 и», . Выходы блока 5 5; (. » =1,Р/2-1) и матрицы 6У„(»cj;j,j =l.P/2-1) соединены с информационными входами. блока 14, управлякщие входы которого связаны с выходами Н 4 и Й» блока 1.

Выходы блока 1 45» Н», 5 у Н» (» =1,Р/2

1),0» Н;,О» Ц; (»(j, j), =l,P/2-1), а также выходы элементов ИЛИ

7Vo и ц-11Хрц Ур(2, 12У р/ Тчт и

13Чр/ Ти,, подаются на вход блока 15.

Выходы последнего являются выходами устройства Р„ (» =О,Р-1).

Работа предлагаемого устройства и ясняется на примере десятичного умножения (Р=10). -Для этого необходимо рассмотреть свойства таблицы умножения десятичных чисел и способ вычисления произведения с учетом этих свойств.

Таблица умножения по mod 10 (фиг. 2) представлена в виде матрицы размерности 10 10. Строки и столбцы матрицы соответствуют значениям операндов от "0" до 9, а элементы матрицы — значениям

Ф . Ю

45 произведения соответствующих чисел. На фиг. 2 операнды обозначены буквами Х и У с индексами, соответствукщими значениям операндов.

На фиг. 3 изображена матрица размерности 8.8, полученная иэ матрицы (фиг.2) путем вычеркивания строк и столбцов, соответствукщих значениям операндов, равным 0" и "5" (Хот Уо ° Х т Уо ) е Полученная матрица разделена на четыре квадранта 4д4, пронумерованных числами

E,II,Ш и 1V . Значения элементов матри-. цы симметричны относительно обеих диКаждая группа из восьми элементов, лежащих в вершинах восьмиугольника, получается с помощью конъкыкции соответствующих переменных. В примере на фиг. 3 восьмиугольник получается так.

Действительно:

9 ля(=/Х»ч ХЧч (» ч Y9/) Х4ч Хаьч » 4 зу (< / =

Х»Х4чХ»ХьчХ»Y4ч Х» (ьч Х>Х4v Х9Xьч Х9 Y4v ч Х9У ч Ч» Х4чУ» Х6>У» Y4ч (»Уьч Yq Х4 ч ч (9 (4 У » Y6

943714 (здесь и далее для управления записи знак конъюнкшш сптущен ).

В полученном выражении конъюнкции одноименных переменных (Х; Х> и У„ У» ) тождественно равны О, так как одни и 5 те же переменные не могут одновременно иметь разные значения. Таким образом:

V»V4 х»Ур х» Y(ч хдЦ4ч Х9 (ч ) 4ч Y» x v ч 9Х4 Ч9ХЬ

1 т.е. группа соответствукицая V» Y4, содержит восемь элементов, объединенных упомянутым выше восьмигранником.

Рассмотренные группы элементов обозначаются

- ч;ч, (.i: »,;.<,<)

Группы из четырех элементов (квадраты) отображаются переменными 5 „ (4) .3В

Так квадрат на фиг. 3 описывается переменной 5 „.

Де йствительно

54.{Х4ЧХ5/f V4V»5(=Х444ЧХ4 (5" Х »4ч X6Y6, ZS

Принадлежность элемента матрицы к какой-.либо паре кввдрантов Г и?Чили

II иШвыражается переменными Н» и

Н2 соответственно. Для получения Н» и

Н < достаточно определить принадлежность элемента либо к кввдранту I (К ), либо к квадранту 1 1 (К ). » /Х ЧХ ЧХЗЧХ4//У У ч 1 ч (4/ M (6)

K jXчХ, Х vX„//Y»vYЧМ чY / тогда

Н»=К»Ч К4 (7) 4О

H2=H».

Для того, чтобы в каждой группе элементы разделить но значениям, достаточно взять конъюнкцию "„" или 5; с

Н» или с Н„. Так в одном из приведен4s ных ранее примеров 0» Н» соответствует числу "4, а 0,4 Н„соответствует числу 6 .

Каждое значение первого разряда произведения получается путем обьединения элементов с одинаковыми значениями, вы-30 деленных описанным образом из разных групп. В результате дпя разных значений

1-го разряда произведения, обозначаемых

Р (» =0,9) где » †.значение, получаются выражения:

ss

Р-S H, 8 Н 32- О»2Н» ч 03+Н» ч 02+Н

Рь u»çН»

52Н»" О»4Н»ч 54ц,ч О» 3Н»

6 S2,Н,ЧО»4Н чб4Н»чО Н» .(8)

7»ЗН»

РР - U «H»v U3»H,V u2 4Н»

Р =g„P чg

Следует отметить, что выражения для пвр Р» и Р9, Р> и Р®, P> и Р>, Р4 и Р аналогичны и отличаются лишь тем, что множители Н„и Н» в них инвертированы.

Результат, равный "О (P ), получается, если хотя бы один из операндов равен "О" или при умножении 5 на четное число, а результат, равный 5 (P ), получается при умножении "5 на нечетное число (в том числе на само себя) .

Для выработки этих результатов вводятся переменные Vo, Ч5, Г»т и »»ч.

v0 Xо 10 С9) (»ОЭ (»») йИ

Тогда

О оч 51чт. (13) и Р5 X5Y5 V V5 THAN (!4?

Действительно, йз выражений (1), (2) и (3) получается Г„,-/X Ч ИY>vY»(=

/Х чY //72чW2v2 ч К /= (is)

/Х "У /(Х ХЭ У Ч чХ»чX Y4vY>(=

Х5/1 чу у (/ Y5/Х мХ чХ6 Х / так как конъюнкции одноименных переменных Х Х или У У тождественно равны

"0", поскольку один операнд не может одновременно принимать два разных значения.

Аналогично ч5Гцт Х5/т» "У ч1<у/чУ !Х чХ ч, (чХ / ((Ц

Таким образом, в первом случае обеспечивается объединение всех элементов матрицы (фиг. 2), соответствующих произведениям "5" на четные числа, а во втором — произведениям 5" на нечетные числа.

В выражении (13) к {15) добавля-, ются строка и столбец матрицы, соответствующие Хо и Уо, а в выражении (14) к (16) добавляется элемент матрицы, соответствующий произведению 5" 5.

14 10 ножения дпя Р> и Р> можно условно считать, что выходной блок просто проводит соответствукщий сигнал Hà выход усч ройства.

На схемах фиг. 4-9 показана одна из возможных реализаций блоков дпя случая десятичного умножения на логических схемах И, ИЛИ и НЕ. ..Блок объединения операндов (фиг. 5) входит в устройство в двух экземплярах по одному из каждый операнд. Один операнд указан в скобках, другой без скобок.

Изображенная реализация точно )ледует логическим выражениям (1) - (14). Однако возможны и другие реализации, связанные с преобразованием этих выражений в соответствии с теоремой де Морга-. на, а также с использованием логических элементов, реализукщих сложные логические функции. Может быть произведена минимизация выражений. Например, в выражениях типа (8) можно вынести за скобки подобные члены. Так для Р4 и P>. в частности, получается, что

Р IS2÷0 4 Н, v(84 02 I H 2V 44j И ч 1 54ч U 2, 1

Таким образом, может быть предусмот1 рена предварительная сборка некоторых сигналов с последующей подачей ик иа схемы И. В этом случае блок 14 состоит из элементов ИЛИ и И, причем общее их количество меныие количества элементов И в первом варианте. Следует также отметить, что разделение данного устройства на блоки является логическим.

Физически при наличии элементов, реализующих сложные логические функции, . логические границы блоков могут прокопить внутри этик. элементов.

Предложенное устройство дает экономию затрат оборудования. Если эти затраты выразить в количестве двухвходовык и опиовходовых логических элементов И,. ИЛИ и НЕ, то окажется, что схема известного устройства требует 91 элемент, а схема данного устройства -, 66 элементов, что составляет экономию более 25%. Соответственно и уменьшается количество соединений в схеме.

9 9437

Аналогичными свойствами обладают таблицы умножения по другим (четным) основаниям, и для них могут быть составлены подобные выражения.

В соответствии со сказанным блок 1: 5 (фиг. 1) представляет собой совокупность, элементов И 16, 17, ИЛИ 18-20 и НЕ

21-23, реализукщих логические выражения типа (6} и (?) для выработки сит палов Н> и Н . Блоки 2 и 3 реализуют 10 логичесиие выражения типа (1) и (2) соответственно. Онн содержат по/Р/2-1/ двухвходовых элементов ИЛИ 24-28, каждый из которых связан со входами данного устройства, соответствующими 35 значениям одного операнда в сочетаниях и /Р- j/. Выходы элементов ИЛИ являются соответственно пля блока 2 сигналы Е, дпя блока 3 сигналы 9l (1=

= P/2 11). Блок 4 реелиоуег логииес- ив кие выражения типа (3). Он содержит

/Р/2-1/ двухвходовых элементов ИЛИ

28-31, каждый из которых связан с однозначными сигналами Е „и W дпя вы рвбоеки сигвелов Ч; (i 1,Р72-1). 2В

Блок 5 реализует логические выражения типа (4}; вырабатывая сигналы 5 „ ((=

=1,Р/2-1). Он состоит из /P/2-1/ -элементов И 32-35, каждый из которых соединен с однозначными выходами ; и 59

Щ блоков 2 и 3 соответственно. Матрица 6 реализует выражения типа (5), вырабатывая сигналы 0;> (/(j; j,j =1,Р/2-1). Она содержит у Р/2-1/ /P/2-2/ элементов И 36-41. Каждый из них свя-з

35 зан с одной парой выходов У иМ блока

4 из всех возможных сочетаний пар этик выходов. Элементы ИЛИ 7 и 8 реализуют выражения типа (9) и (10), а элементы ИЛИ 9 и 10 — выражения типа (11) и (12) соответственно. Элемент И 11 реализует конъюнкцию X /2

УР 2 из выражения типа (14), а элементы И 12 и 13 — конъкйкции Vp/2 н) и7р 2 Ти из выражений типа (13) и (14) соответственно. Блок 14 обеспечивает реализацию конъюнкций из выражений типа (3}. Он содержит две группы элементов в каждой. Каждый элемент одной . группы вырабатывает сигнал 0 Н или Ь Н;1

Ч 1 .1 Ч56 а каждый элемент другой группы - оиг-. ,нал 0; К или Gj Н, . Соответствукщие сигналы поступают из блоков 1 и 5 и матрицы 6, Блок 15 реализует выражения типа (8) без содержацпп ся в них конъюнкций. Он содержит группу элементов ИЛИ 62-69. Если отдельные выражения из (8) состоят из одного члена, как например в случае десятичного умФормула изобретения

1. Матричное устройство умножения по mod Р, содержащее блок расстановки операндов, блок сравнения операндов, 11 9437 матрицу элементов И, и блок формирования результата, причем входы блока расстановки операндов соединены со входами блока сравнения операндов, выходы блока расстановки операндов соединены соответственно с входами элементов И матрицы, а выходы блока формировании результата являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения затрат оборудования !0 устройство содержит блок выделения . квадрантов, два блока объединения квадрантов, четыре элемента ИЛИ, три элемента И и блок разделения, произведений, причем входы первого и второго блоков объединения квадрантов соединены соответственно с входами первого н второго операндов устройства, соответствующих всем значениям операндов, кроме 0" и

"P/2", входы жерандов устройства, соот-20 ветствующие значениям операндов.с единицы по (P/2-1), соединены соответствен.но с первой В второйГ группами входов блошка выделения квадрантов, выходы первого и второго блоков объединения квадрантов соединены соответственно с входами блока расстановки операндов, выходы элементов И матрицы и блока сравнения операндов соединены соответственно с информационными входами блока разделе- 30 ния произведений, управлякзцие входы которого соединены с выходами блока выделения квадрантов, входы операндов устройства, соответствующие значениям операндов, равным 0", соединены с входами первого элемента ИЛИ, входы операндов устройства, соответствукщие значениям операндов, равным "P/2", соединены с входами первого элемента И и с входами второго элемента ИЛИ, выход ip второго элемента ИЛИ соединен с первыми входами второго и третьего элементов

И, вторые входы которых соединены соответственно с выходами третьего и четвертого элементов ИЛИ, входы которых соединены соответственно с группой четных и нечетных выходов блока расстановки операндов, входы первого элемента

ИЛИ, элементов И и блока разделения

14 12 произведений соединены.с входами блока формирования результата. . Устройство по п.1, о т л и ч a— ю щ е е с я тем, что, блок выделения квадрантов содержит элементы И, ИЛИ и

НЕ, причем входы блока первой группы соединены, соответственно с входами первого элемента ИЛИ, входы блока второй группы соединены соответственно с входами второго элемента ИЛИ, выходы элементов ИЛИ соединены с входами первого элемента И, а через первый и второй элементы HE соответственно — с входами второго элемента И, выходы первого и второго элементов И соединены с входами третьего элемента ИЛИ, выход которого является первым выходом блока, который соединен с входом третьего элемента НЕ,, выход которого является втсьрым выходом блока.

3. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок объединения . квадрантов содержит (Р/2-1 ) элементов

ИЛИ, причем входы -го элемента ИЛИ (j =1,..., P/2-1, Р/2+1,..., Р-1) соединены с I -м и (Р- )-м входами блока, а выход этого элемента является -м выходом блока.

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

И второй группы соединены с другим управляющим входом блока, а выходы элементов И обеих групп являются выходами блока.

Источники информации, принятые во внимание при экспертизе

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

% 2 59479, кл. Cj 06 Р 7/3 8, 1 9 & .

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

% 496555, кл. g 06 Г 7/38, 1974 (прототип ) .

943714

Составитель А. Суздалев

Редактор М. Дылын Техред М.Рейвес Корректор У, Пономаренко

Заказ 5111/56 Тираж 731 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4