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

. С. Бре Авторызобретеиия к,оюзный научно-исспедоваторгтехники аяветедь 54) МАТРИЧНОЕПО що ИСТВО УМНОЖЕ няюг однозначные входы от каждого операнда. Второй блок - это совокупность . двухвходовых конъюнктивных эпементов с теми же связями, что и у элементов первого бпока, Выходы элементов второго блока соответствуют значениям диагональных элементов таблицы умножения. Выходы элементов первого бпока подаются в матрицу двухвходовых конь ктивных элементов так, что каждый из ее элементов связан с одной. парой выходов первого блока, а общее количество этих элементов равно числу таких пар, Дпя системы счисления с основанием Рчисло элементов матрицы равно РР.) (2, а вместе с коньюктйвными элементамйвторого блока это число равноРРфЦ 2,Таким образом, копичестгво логических элементов, фиксирукщнх все сочетания 20 значений операндов, меньше общего сда эпевентов табпицы умножения, равного Р 2Однако адьнейшего у чи Изобретение относится к вычислительной технике и может быть использовано в арифметических устройствах, работающих в десятичной системе счисления,Известно матричное устройство умножения, содержащее матрицу конъюктив ных элементов, каждый иэ которых соответствует определенному сочетанию значений операндов, и выходной блок, обьединякщий выходы тех элементов матрицы, которые соответствуют одному эна чению произведения. Количество эпементов матрицы равно Р, где Р - основание2матрицы счисления 1Известно также устройство, которое, с целью уменьшения числа элементов матрицы, использует свойство коммутативности умножения, т.е, диагональную симметрию таблицы умножения. Для этого в устройстве предусмотрены бпоки расстановки операндов и равенства операндов. Первый блок представляет собой совокупность двухвходовых дизъюнктивных элементов, входы которых обьеди 3 существует возможность дменыдения числа элементов/56 Тираж 7ВНИИПИ Государстпо делам изо113035, Москва,По енного ко ретений и 35, Рауш3 94371 матрицы и затрат оборудования на устройство умножения зв счет того, что таблица умножения имеет более глубокие закономерности, чем простая диагональная симметрия. 5Целью изобретения является уменьщение затрат оборудования на создание матричного устройства умножения.У Указанная цель достщ ается тем, что 10 матричное устройство умножения поп)од Р, содержащее блок расстановки операндов, блок сравнения операндов, матрицу элементов И и блок формирования результата, причем входы блока расстановки операн дов соединены с входами блока операндов, выходы блока расстановки операндов соединены соответственно с входами элементов И матрицы, а выходы блока формирования результата являются выходами 2 э устройства, содержит блок выделения квадрантов, два блока обьединения квадрантов, четыре элемента ИЛИ, три элемента И и блок разделения произведений, причем входы первого и второго блоков обьединения квадрантов соединены соответственно с входами первого и второго операндов устройства, соответствующих всем значениям операндов, кроме 0" и Р/ 2 ", входы операндов устройства, со- ЗО ответствующие значениям операндов с единицы по (Р/2 - 1), соединены соответственно с первой и второй группами входов блока выделения квадрантов, выходы первого и второго блоков объединения квадрантов соединены соответственно35 с входами блока расстановки операндов, выходы элементов И матрицы и блока сравнения операндов соединены соответственно с информационными входами бло 40 ка разделения произведений, управляющие входы которого соединены с выходами блока выделения кввдрантов, входы операндов устройства, соответствующие значениям операндов, равным "0", соединены с входами первого элемента ИЛИ, входы операндов устройства, соответствующие значениям операндов, равным "Р/2 ", соединены с входами первого элемента И и с входами второго элемента ИЛИ, выход второго элемента ИЛИ соединен с первыми входами второго и третьего элементов И, вторые входы которых соединены соответственно с выходами третьего и четвертого элементов ИЛИ, входы которых соединены соответственно с группой четных и нечетных выходов блока расстановки операндов, входы первого лементв ИЛИ, элементов И и блока рвзделения произведений соединены с входами блока формирования результата,Блок выделения квадрантов содержитэлементы И, ИЛИ и НЕ, причем входыблока первой группы соединены соответственно с входами первого элементаИЛИ, входы блока второй группы соединены соответственно с входами второгоэлемента ИЛИ, выходы элементов ИЛИсоединены с входами первого элементаИ, а через первый и второй элементыНЕ соответственно - с входами второгоэлемента И, выходы первого и второгоэлементов И соединены с входами третьего элемента ИЛИ, выход которого является первым выходом блока, которыйсоединен с входом третьего элементаНЕ. выход которого -второй выход.блока.,Блок обьединения квадрантов содержит (Р/2-1) элементов ИЛИ, причемвходы 4 -го элемента ИЛИ (4 =1Р/2-1, Р/2+1,. Р) соединены с-ми (.Р-)-м входами блока, а выход это го элемента является-м выходом блэка,Блок разделения произведений содержит две группы элементов И по 1/4 Р(Р/2-1) элементов в каждой, причемпервые входы элементов И каждой группы соединены соответственно с информационными входами блока, вторые входыэлементов И первой группы соединены содним управляюшим входом блока, вторыевходы элементов И второй группы соединены с другим управлякхцим входом блока, а выходыэлементов И, обоих группявляются выходами блока,Нв фиг. 1 изображена структурнаясхема устройства; на фиг. 2 - таблицаумножения по п 1 од Р; на фиг. 3 - усеченная таблица по щод Р; на фиг. 4 -схема блока выделения квадрантов; нафнг, 5 - схема блока объединения квадрантов; на фиг. 6 - схема блока расстановки операндов; на фиг. 7 - схем:блока сравнения операндов; на фиг, 8 -схема матрицы элементов И; на фиг, 9 схема блока разделения произведений;на фиг. 10 - схема блока формированиярезультата.Устройство содержит блок 1 выделения квадрантов, блоки 2 и 3 объединенияквадрантов, блок 4 расстановки операндов, бпок 5 сравнения операндов;, матрицу 6 элементов И, элементы ИЛИ 7,8, 9 и 10, элементы И 11, 12 и 13,блок 14 разделения произведений и блокформирования результата 1 5.943714 6агоналей, причем квадранты 1 иЖ,11 и,Шявляюгся попарно зеркальным отображением друг друга. Далее числа в 1 и 17квадрвнтах симметричны относительноглавной диагонали матрицы (слева - вниз .направо), а числа во 11 и 1 Нквадрантах 1) симметричны относительно вспомогательной диагонали (слева - вверх - неправо),Эти особенности поэволяюг обьединить в 1 ф симметричные элементы каждого квадранта, находящиеся на одинаковых позицияхотносительно своих осей симметрии, в е- одну группу. Линии на фиг. 3, соединяющие соответствукзцие элементы, образу юг( в общем случае восьмиугольники. Для элементов, находящихся на диагойалях, восьмиугольники преврашвюгся в квадраты,Полученные таким образом 1 руппы элементов обладают следующими свойствами: е щ элементы одной группы имеюг только дввразных значения, причем элементы 1 и 1T11, и 1 Иквадрантов попарно совпадают;пары значений элементов в разных группах.встречаюгся всегда в одних и тех же сочетаниях: "1". и 9", "2" и "8", "3" и,группы для пары 4 и 6. Одна гоуппа образует восьмиугольник, другая квадрат,Указанные сводства табпнпы умножения используются для аализации схемымладшего разряда произведения (произведения по 3.0).Вводятся промежуточные переменные3%Ч(б=1, 4); которые полу 35 чаются из исходных переменных с помоо- щью следующих логических операций с,( =Хч Х 92.2= Хч Х 8с,. =Х, чХЬ 4-. Х 4 ч Х,9, =У, ч()фМ 3 в В;=ЕЛВ; (ы 4,4) (4) . 5Входы предлагаемого устройства Х-Хр 2, Х рр ( -Х р (, У( -Ур/2 Ур/2+ -Ур-(1 сл всех сигналов определяется позже) соединены со. входами блока 1 и блоков 2 и 3, причем Х подаются в блок 2, а У - в блок 3. Выходы блоков 2 Е , и 3 Ю ( =1,Р/2- соединены со входами блоков 4 и 5. Входы матрены 6 соедн:.сны с выходамн блока 4 У; (=1,Р/з, одна трупп которых (четные) с индексами ( =2 и (0=1, 2 пока с Р/2) соединена со входами элемента ИЛИ 9, а другая (н четные) с индексами 1 =2 п(и =1, 2,. пока с Р/2) - со входами эле мента ИЛИ 10. Входы устройства Х р 2 и Ур/2 подаются на вход элементов ИЛИ 8 и И 11, а входы устройства Х и У, - на вход элемента ИЛИ 7, Выход элемента ИЛИ 8 Чр/ подается на нервы входы элементов И 12 и 13, вторые входы которых соединены соответственно с выходами элементов ИЛИ 9 Тцг и 10 ц, . Выходы блока 5 б;(. =1,Р/2- -1) и матрицы 6 Ч с;(,(=1.Р/2-1) соединены с информационными входами блока 14, управлякщие входы которого связаны с выходами Н ( и Й( блока 1, Выходы блока 145 Н,5 уН=1,Р/2 1),О Н;,0 Н; с =1,Р/2- -1), в также выходы элементов ИЛИ 7 Чо и 0-11 Хрц 2 Ург12 Чр(2 чт и 13 Чр 214 подаются на вход блока 15. Выходы последнего являются выходами устройства Р ( =О,Р).Работа предлагаемого устройства п ясняется на примере десятичного умножения (Р=10),-Для этого необходимо рассмотреть свойства таблицы умножения десятичных. чисел и способ вычисления произведения с учетом этих свойств.Таблица умножения по вод 10 (фиг. 2) представлена в виде матрицы размерности 10 В 10. Строки и столбцы матрицы соответствуюг значениям операндов от "0" до 9, а элементы матрицы - значенияму ы4 В произведения соответствующих чисел. На фиг. 2 операнды обозначены буквами Х и У с индексами, соответствукщими значениям операндов.На фиг. 3 изображена матрица размерности 8 8, полученная иэ матрицы (фиг.2) путем вычеркивания строк и столбцов, соответствукщих значениям операндов, равным "0 и "5 (Хо УоХ У)е Пофлученная матрица разделена на четыре квадранта 4 д 4, пронумерованных числами 1,11 ,111 и 1 У . Значения элементов матри-. цы симметричны относительно обеих ди% Каждая группа из восьми элементов, лежащих в вершинах восьмиугольника, получается с помощью конънзкции соответствующих переменных. В примере на фиг. 3 восьмиугольник получается твк. Действительно:7 л-/Х(ч Х 9 ч ч(4(Х/ч Хбч Ч 4 ч ГХ Х 4 Х Хьч Х (4 ч Х(Ь ч Х 9 Х 4 ч Х 9 Х 6 ч Х У 4 чХ 9 о" М(Х 4 чУ(ХчУ(У 4 чМч У 9 Х 4 ч ч 94 ч У11 9437 матрицу элементов И, и блок формирования результата, причем входы блока расстановки операндов соединены со входами блока сравнения операндов, выходы блока расстановки операндов соединены соответственно с входами элементов И матрицы, а выходы блока формировании результата являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения затрат оборудования ф устройство содержит блок выделения .квадрантов, два блока объединения квадрантов, четыре элемента ИЛИ, три элемента И и блок разделения. произведений, причем входыпервого и второго блоков 1 ф объединения квадрантов соединены соответственно с входами первого н второго операндов устройства, соответствующих всем значениям операндов, кроме "0" и "Р/2", входы мерандов устройства, соответствующие значениям операндов.с единицы по (Р/2-1), соединены соответствен.но с первой В второйГ группами входов блока выделения квадрантов, выходы первого и второго блоков объединения квад рантов соединены соответственно с входами блока расстановки операндов, выходы элементов И матрицы и блока сравнения операндов соединены соответственно с информационными входами блока разделе ния произведений, управляющие входы которого соединены с выходами блока выделения квадрантов, входы операндов устройства, соответствующие значениям операндов, равным О", соединены свходами первого элемента ИЛИ, входы операндов устройства, соответствукщие значениям операндов, равным "Р/2", соединены с входами первого элемента И и с входами второго элемента ИЛИ, выход р второго элемента ИЛИ соединен с первыми входами второго и третьего элементов И, вторые входы которых соединены соответственно с выходами третьего и четвертого элементов ИЛИ, входы которых соединены соответственно с группой четных и нечетных выходов блока расстановки операндов, входы первого элемента ИЛИ, элементов И и блока разделения 14 12произведений соединены.с входами блокаформирования результата.Т, Устройство по п.1, о т л и ч а -ю щ е е с я тем, что, блок выделенияквадрантов содержит элементы И, ИЛИ иНЕ, причем входы блока первой грутпгысоединены, соответственно с входами первого элемента ИЛИ, входы блока второйгруппы соединены соответственно с входами второго элемента ИЛИ, выходыэлементов ИЛИ соединены с входами первого элемента И, и через первый и второй элементы НЕ соответственно - с входами второго элемента И, выходы первого и второго элементов И соединены свходами третьего элемента ИЛИ, выходкоторого является первым выходом блока,который соединен с входом третьего элемента НЕ выход которого является вторым выходом блока.3. Устройство по п,1, о т л и ч аю щ е е с я тем, что блок объединения .квадрантов содержит (Р/2-1) элементовИЛИ, причем входы-го элемента ИЛИ( =1 Р/2-1, Р/2+1 Р) соединены с 1 -м и (Р-)-м входами блока,а выход этого элемента является-мвыходом блока,4, Устройство по п,1, о т л и ч аю щ е е с я тем, что блок разделенияпроизведений .содержит две группы элементов И по 1/4 Р (Р/2-1) элементов в каждой, причем первые входы элементов И каждой группы соединены соответственно с информационными входамиблока, вторые входы элементов И первойгруппы соединены с одним управляющимвходом блока, вторые входы элементовИ второй группы соединены с другимуправляющим входом блока, а выходыэлементов И обеих групп являются выходами блока.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР% 259479 ю кл, Й 06 Р 7/38, 192. Авторское свидетельство СССРМц 496555, кл.06 Г 7/38, 1974