УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ АЛГЕБРАИЧЕСКИХМАТРИЦ Советский патент 1970 года по МПК G06G7/16 

Изобретение относится к области вычислительной техники.

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

Предлагаемое устройство отличается от известного тем, что в нем одни входы группы схем сравнения, число которых равно порядку матрицы, соединены с выходом генератора случайных импульсов, а другое - с ввода информации о значении элементов первой матрицы. Выходы группы схем сравнения соединены с одними входами группы реверсивных счетчиков, вторые входы которых соединены с выходом первой схемы сравнения и входом первого счетчика, не входящих в соответствующие группы,; третьи входы группы счетчиков соединены с шинами ввода информации о знаке элементов первой матрицы, а четвертые входы -- с шиной ввода информации о знаке элементов второй матрицы. Выходы группы счетчиков подсоединены к шинам вывода информации о значении элементов матрицы-произведения и их знаке. Входы первой схемы сравнения, не входящей в группу, соединены соответственно с шиной ввода информации о порядке матрицы и выходом первого счетчика, не входящего в группу счетчиков.

Один вход второго счетчика соединен со входом генератора случайных импульсов и через схему несовпадения с выходом генератора опорных импульсов, второй вход схемы несовпадения соединен с выходом триггера, нулевой и единичный входы которого соединены соответственно с шиной ввода команды о начале работы устройства и с выходом второй схемы сравнения, который дополнительно соединен со вторыми входами двух счетчиков, не входящих в группу счетчиков. Входы второй схемы сравнения соединены соответственно с выходом второго счетчика и с шиной ввода информации о значении элементов второй матрицы.

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

где;:Л :||а; ||„; , то вычисляются одновременно п нроизведений: а,л, /-IKJ - па Ь/n - ( где C,-к-тое произведение, входящее слагаемым в элемент матрицы-произведения С, то есть Q,.-id7 Ja,, ,2, ...п. Таким образом, вычисляется одновременно 1-тая строка матрицы-произведения С. Граф, поясняющий работу устройства, представлен па фиг. 1, на котором ствол «дерева моделирует fljj, общее для всех, сомножителей; ветви «дерева моделируют . Ограничением на элементы матриц /1 и S является S / 1; 6j,.| 4 1. Если моделиро/-Iвать число uij регулярным потоком импульсов в количестве, равном Nai , где Л/ - количество импульсов, поданных для испытания графа на проводимость, а числа моделировать вероятностным образом, то отношение количества прошедших на выход импульсов /-той ветви графа MjKN даст приближенное значение произведения . Погрешность при этом оказывается меньше, чем если бы оба сомножителя моделировались вероятностным образом. Моделирование выполнено на базе известных и широко используемых в вычислительной технике узлов и блоков. Блок-.схема устройства представлена на фиг. 2. Она содержит генератор / опорных импульсов с частотой (1-5)-10 гц; генератор 2 случайных чисел; га схем сравнения 3i-3„, счетчик 4; схему сравнения 5; триггер 6; схему несовпадения 7; п реверсивных счетчиков (Si-й„; счетчик 9; схему сравнения 10. На схе.ме введены обозначения: ai-а„ - шины для ввода чисел - ; б - шина для ввода числа в - шина для ввода знака элемента шины для ввода знаков элементов -ь д - шина для ввода команды начала испытаний; е-шина для ввода числа п (порядка матрицы); ж - з/г„ - шины для вывода вычисленных элементов f-той строки матрицы-произведения; - шины для .J вывода знаков вычисленных элементов. В момент стробирования импульсами генератора / опорных импульсов генератор 2 случайных равномерно распредел.енных чисел выдает т-разрядные случайные числа на схемы сравнения . Пороги сравнения в схемах сравнения устанавливаются /тг-разрядными числами, вводимыми в них по шинам . На выходах схем сравнения Зх-з„ появляются одиночные импульсы при выполнении неравенства;на сравнение на тот же блок; в .противном случае импульсы не появляются. Так как генерируемые случайные числа и числа, подаваемые на сравнение, заключены в интервале (0,1), то вероятность появления импульса на выходе каждой схемы сравнения равна самому числу, поданному на сравнение. Таким образом, блоки Л 2 и моделируют элементы правой матрицы-сомножителя б,,-нв/;„. Элемент левой матрицы-сомножителя моделируется регулярным потоком импульсов в количестве Nui. Они считываются счетчиком 4, со счетным входом которого соединен генератор I опорных импульсов. Счетчик 4 соединен со схемой сравнения 5, на которую по шине б подается число Л/а. В момент фиксации счетчиком 4 числа No-i схема сравнения 5 выдает импульс, который устанавливает счетчик 4 в нулевое состояние, а триггер 6 - в единичное. С единичного плеча триггера 6 снимается потенциал, который, запирая схему несовпадения 7, прекращает цикл вычисления. При этом реверсивные. счетчики , счетные входы которых связаны с выходами схем сравнения , зафиксируют числа , где тИу - .,. ; / 7,2,п, с некоторой погрешностью Д/с. Взяв отношение М- icN получаем с погрешностью бд, -- . Число Л/ выбирается равным степени двух. Знаки элементов Оц, подаются до начала испытаний на счетчики 5i-8„ в виде одиночных импульсов. По шине б подается знак а/., по шинам ei-г„- знаки элементов При этом знак минус обозначает наличие, а знак плюс - отсутствие импульса. Команда начала испытаний подается по шине д в виде одиночного импульса, который фиксирует триггер 6 в нулевом положении. При этом триггер снимает запрет со схемы несовпадения, давая возможность импульсам проходить от генератора 1 опорных импульсов. Количество циклов испытаний фиксируется счетчиком 9, счетный вход которого соединен с выходом схемы сравнения 5. Счетчик 9 соединен со схемой сравнения 10, на которую по шине е подается число п. В момент фиксации счетчико.м 9 числа п схема сравнения 10 выдает одиночный импульс, который переводит счетчики Si-8 и 9 в нулевое состояние. При этом со счетчиков . Si-S« по шинам считываются вычисленные элементы i-той строки матрицы С АБ и по шинам их знаки. Предмет изобретения Н1ия и триггер, отличающееся тем, что, с целью 1овыи ения быстродействия устройства, в нем )дни входы группы схем сравнения, число которых равно порядку матрицы, соединены с выходом генератора случайных импульсов, а другие - с шинами ввода информации о зна1ении элементов первой матрицы, выходы руппы схем сравнения соединены с одними ходами группы реверсивных счетчиков, втоэые входь которых соединень с выходом схемы сравнения и входом первого счет-шка, не входящих в соответствующие группы, третьи входы группы счетчиков соединены с ликами ввода информации о знаке элементов лервой матрицы, а четвертые входы - с шиной ввода информации о знаке элементов втоэой матрицы, выходы группы счетчиков под;оединены к шинам вывода информации о шачении элементов матрицы-произведения и их знаке; входы первой схемы сравнения, не входящей в группу, соединены соответственно с шиной ввода информации о порядке матрицы и выходом первого счетчика, не входящего в группу счетчиков, один вход второго счетчика соединен со входом генератора случайных импульсов и через схему несовпадения с выходом генератора опорных импульсов, второй вход схемы несовпадения соединен с выходом триггера, нулевой и единичный входы которого соединены соответственно с шиной ввода команды о начале работы устройства и с выходом второй схемы сравнения, который дополнительно соединен со вторыми входами двух счетчиков, не входящих в группу счетчиков, а входы второй схемы сравнения соединены соответственно с выходом второго счетчика и с шиной ввода информации о значении элементов второй матрицы.