Устройство умножения булевых матриц

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 18.07. 80 (21) 2961343/18-24 15 т 1 М. КЛ.З с присоединением заявки Нов 6 06 Р 7/00 Гоеуларственный комитет СССР ио лелам изобретений и открытий(088. 8) Дата опубликования описания 15.09,82РЛенинградский институт авиационного приборосроНия(54) УСТРОЙСТВО УМНОЖЕНИЯ БУЛЕВЫХ МАТРИЦ Изобретение относится к цифровой вычислительной технике, в частности к специализированным вычислителям для обработки информации, представленной в матричной форме, и может быть использовано в устройствах цифровой обработки сигналов, в устройствах распознавания образов, а также в устройствах, где производится обработка массивов информации, представленной в матричной форме.Известно устройство для вычисления сумм произведений, содержащее регистры множимого и множителя, выходы которых. соединены со входами матрицы пкп одноразрядных модулей сложения и сумматор из та+и модулей сложения 1Недостатками этого устройства являются конструктивная сложность и необходимость сложной коммутации на входе при выполнении операции умножения матриц.Наиболее близким по технической сущности к, предлагаемому является устройство перемножения булевых матриц, содержащее запоминающее устройство с разрушением информации. при считывании, состоящее из трех частей, содержащих соответственноматрицу множимого, матрицу множителя, функциональную часть, в которойпроизводится вычисление матрицырезультата. Входы блока памяти множимого соединены с выходами разрядного распределителя, а выходы -со входами регистра многоадресногообращения. Выходы регистра многоадресного обращения соединены совходами блока памяти результата, Выходы блока памяти результата и выходы блока памяти множителя соединены с соответствующими входами регистра слова. Выходы регистра слова соединены со входами блоков памятимножимого и результата. Выходы блока управления соединены с управляющими входами блоков памяти множимого, множителя, результата, разрядногораспределителя, регистра слова ирегистрамногоадресного обращения 3Работа известного устройства состоит из двух этапов25 На первом этапе производитсятранспонирование матрицы множимогов Функциональной части блока памяти множимого перестановкой строк истолбцов и последующая пересылка 30 строк транепонированной матрицы множимого в блок памяти множимого. Навтором этапе формируются попарныелогические произведения строк транспонированнойматрицы множителя вфункциональной части блока памятимножителя в виде 5 С; =аЬ;1=1Операция транспонирования булевой матрицы множимого производится за и циклов, каждый из которых состоит из трех микротактов. В первом микротакте Й-го цикла осуществляется считы-ванне.и передача 1-й строки матрицы множимого иэ блока памяти множимого на регистр многоадресного обращения 15 в соответствии с состоянием разрядного распределителя и по команде блока управления, Во втором микротакте 1-я строка матрицы множителя из регистра многоадресного обращения 3) переписывается в Е-й разряд блока памяти результата. В третьем микро- такте производится обнуление регистра слова, регистра многоадресного обращения и подготовка разрядного распределителя к следующему циклу,Перед выполнением второго этапа умножения матриц производится пересылка транспонированной матрицы множителя через резистр слова из блока памяти результата.в блок памятимножимого. Пересылка выполняется за Зи микротактов.Второй этап умножения производится за и циклов, каждый из которых состоит из 4 микротактов. В первом микротакте производится обнуление регистра слова и регистра многоадресного обращения. Во втором микротакте -я строка транспонированной матрицы множимого передается из 40 блока памяти множимого на регистр многоадресного обращения. В третьем микротакте К-я строка матрицы множителя передается из блока памяти множителя на регистр слова. В четвертом 45 микротакте в блоке памяти результата формируются попарные конъюнкции между элементами Е-й строки транспонированной матрицы множимого и К-й строки матрицы множителя путем подачи соот ветствующих строк с регистра слова и регистра многоадресного обращения на,шины строк и столбцов блока памяти результата.55После выполнения и циклов второго этапа в блоке памяти результата оказываются записанными строки матрицы результата в видегС = Ч а Ь,(1)с=Таким образом, для умножения булевых матриц, содержащих и строк и и столбцов требуется. 10 и микротактов обращения к блоку памяти 12 3, 65 Недостатками известного устройст . ва являются невозможность выполнения операции умножения булевых матриц по модулю два, так как в нем осуществляется умножение булевых матриц, определяемое как (1), причем логическое сложение осуществляется пу" тем последовательной записи в ячейку блока памяти результата минтермов а)к Ь. Для выполнения умножения матриц по модулю два необходимо выполнять суммирование по модулю два. Выражение, определяющее умножение матриц по модулю два имеет видС , = О+ а .Ь,к= В устройстве используется .блок памяти с разрушением информации, что приводит к необходимости восстановления информации после считы,вания и таким образом приводит к не- обходимости увеличивать время выполнения операции, Кроме того, устройство не позволяет производить считывание информации как по строкам, так и по столбцам. Это приводит к необходимости транспонирования матриц путем пересылки ее строк из блока памяти множимого в блок памяти результата и обратно в блок памяти множимого. Результатом этого является значительное увеличение времени выполнения умножения и необходимость в сложном и громоздком управлении устройством из-за сложности системы пересылки информации между блоками памяти.Целью изобретения является расширение функциональных возможностей устройства за счет возможности выполнения операции умножения матриц по модулю два и увеличение быстродействия.Поставленная цель достигается тем, что устройство умножения булевых матриц, содержащее блок управления, блоки памяти множимого, множителя и результата, причем входы считывания блоков памяти множимого и множителя подключены к выходу считывания блока управления, выход записи результата которого подключен к входу записи блока памяти результата, устройство содержит программируемый матричный коммутатор и блок элементов логического умножения и суммирования, первый, второй и третий управляющие входы которого подключены к выходам суммирования по модулю два, логического суммирования,и сброса в нулевое состояние блока управления соответственно, выходы блока элементов логического умножения и суммирования подключены к входам блока памяти результата соответственно, первая группа информационных входов блока элементов логического умножения и суммирования подключена к выходам программируемого матричного коммутатора соответственно, управляющие входы которого подключены к программирующим выходам блока управления соответственно, информационные входы программируемого матричного коммутатора подключены к выходам блока памяти множителя соответственно, выходы блока памяти множимого подключены к второй группеинформационных входов блока элементов логического умножения и суммирования соответственно, синхронизирующий вход, вход тактовых импульсов, входы установки управляющего триггера в нулевое и единичное состояния блока управления подключены к синхронизирующему входу, входу. тактовых импульсов, входам программной установки управляющего триггера в нулевое и единичное состояние устройства соответственно,Блок управления содержит распреде литель импульсов, элемент И, счетчик циклов, регистр и управляющий триггер, входы установки в нулевое и единичное состояние которого подключены к входам установки в нулевое и единичное состояния блока соответственно,.нулевой и единичный выходы- управляющего триггера подключены к выходам суммирования по модулю два и логического суммирования блока соответственно, выходы регистра под-.ключены к программирующим выходамблока соответственно, вход тактовых импульсов регистра подключен к входу тактовых импульсов блока, информационный вход регистра подключен к первому выходу распределителя импульсов, второй и третий выходы которого подключены к выходам считывания и записи результата блока соответственно, четвертый выход распределителя импульсов подключен к выходу сброса в нулевое состояние блока, к входу сброса в нулевое состояние распределителя импульсов и к счетному входу счетчика циклов, выход которого подключен к первомувходу элемента И, второй вход которого подключен к синхронизирующему входу блока, выход элемента И подключен к входу распределителя.импульсов.Блок элементов логического умножения и сложения содержит элементы логического умножения и суммирования, каждый из которых содержит дваэлемента И и КЯТ-триггбр, причем вкаждом элементе логического умножения и суммирования первые и вторые входы элементов И подключены к информационным входам первой и второй группы блока соответственно, третьи входы первого и второго элементов И подключены к первому н второму управляющим входам блока соответственно, выходы первого и второго элементов И подключены к Т- и Я-входамКЯТ-триггера соответственно, Й-входкоторого подключен к третьему управляющему входу блока,Применение электрически программируемого матричного коммутаторапозволяет подавать элементы любого1 О столбца матрицы множителя на любойблок логического умножения и суммирования при подаче сигналов настройки с блока управления. Блоки логического умножения и суммирования позво.15 ляют наиболее простым способом реализовать Функции (1) и (2) при подачесоответствующих управляющих сигналов с блока управления, ОсобенностьюФерроакустических блоков памяти явля 2 О ется то, что считывание информацииможно производить как по строкам,так и по столбцам, независимо отпорядка записи информации в блокепамяти. В связи с этим отпадает не 5 обходимость в проведении операциитранспонирования матриц.Таким образом, применение электрически программируемого матричного коммутатора, блоков логическогоумножения и суммирования и ферроакустических запоминающих устройствпозволяет достичь положительногоэффекта, т.е, раааирить функциональные воэможности устройства при увеличении быстродействия,На фиг.1 изображена Функциональная схема устройства умножения булевых матриц; на Фиг.2 - Функциональная схема блока управления.40 Схема включает блок 1 управления, блок 2 памяти множителя, блок3 памяти множимбго, матричный коммутатор 4, блок 5 памяти, блоки 6элементов логического умножения исуммирования, количество которыхравно количеству строк в матрицемножимого и каждый из которых со"держит два трехвходовых элемента И7 и 8, ПЯТ-триггер 9, выход 10 блокапамяти множителя, выход 11 электрически программируемого, выход 12блока памяти множимого выход 13 логического элемента И 7, выход 14логического элемента И 8, выход 15 55 блока логического умножения и су"мирования, шина 16 программирующеговхода матричного коммутатора, управляющая шина 17 считывания блоков памяти множимего и множителя, управляющая шина 18 записи блока памяти 6 ф результата, управляющая шина 19 суммированияпо модулю два, управляющаяшина 20 логического суммирования, .шина 21 сброса, синхронизирующийвход 22 устройства, вход 23 тактовых 63 импульсов устройства, входы 24 и 25программной установки управляющего триггера в нулевое и единичное состояния, распределитель импульсов 26, элемент И 27, счетчик циклов 28, регистр 29, управляющий триггер 30.Выходы 10 блока 2 памяти множителя соединены с информационными входами матричного коммутатора 4, каждый выход 11 которого соединен со входом соответствующего блока б элементов логического умножения и суммирования, а именно со вторыми входами элементов И 7 и 8. Каждый выход 12 блока 3 памяти множимого соединен с первыми входами элементов И 7 и 8 соответствующего блока б элементов логического умножения и суммирования. Выход 13 каждого элемента И 7 соединен со счетным входом Т соответствующего КБТ-триггера 9. Выход 14 каждого элемента И 8 соединен с установочным входом Б соответствующего КБТ-триггера 9. Выходы 15 всех КБТ-триггеров 9 соединены с соответствующими входами блока 5 памяти результата. Программирующие входы 16 матричного коммутатора 4 соединены с соответствующими шинами блока управления. Управляющие входы 17 блока 3 памяти множимого, блока 2 памяти множителя и управляющий вход 18 блока 5 памяти результата соединены с соответствующими выходами блока управления 1. Управляющие входы блоков логического умножения и суммирования б, 19 и 20 соединяют соответственно выходы блока 1 управ-. ления со входами логических элементов И 7 и 8. Входы обнуления К КБТ-триггеров 9 соединены с шиной сброса блока управления 1.Принцип работы предлагаемого устройства состоит в следующем.Операция умножения матриц состоит э ряда циклически повторяющихся дей- ствий". логического умножения строки матрицы множимого на столбец матрицы .множителя и суммирования получившихся минтермов. Количество циклов определяется максимальной размерностью матриц сомножителей, Для простоты рассмотрим умножение квадратных булевых матриц пхп.В исходном состоянии в блоке 3 памяти множимого записана матрица множимого А, в блоке 2 памяти множител - матрица множителя В, блок 5 памятй результата обнулен.Работа устройства умножения булевых матриц состоит из двух этапов.На первом этапе производится настройка матричного коммутатора, При этом в коммутаторе записываются "еди ницыф в тех ячейках коммутации,;Ы которых должна образоваться связь, между входными и выходными шинами. Наиболее рациональным является такой режим настройки, при котором фединицы записываются во всех ячейках коммутатора, расположенных на одной строке,то есть, когда один вход коммутатораподключается ко всем его выходам,Таким образом, реализуется умножениестолбца матрицы множителя на все строки матрицы множимого, следовательно,за один цикл работы устройства реализуется столбец матрицы результатачто упрощает адресацию в блоке памяти 1 О результата.Настройка матричного коммутатора 4производится путем подачи на программирующие входы 16 матричного коммутатора 4 импульсов настройки, При этом 15 ультразвуковая волна возбуждается водной строке, а импульсы поля подаются. во все столбцы матричного коммутатора. Настройка электрически программируемого матричного коммутатора 4 2 О производится за один такт, Одновременно производится обнуление КБТ-триг- .геров 9 подачей сигнала на шину сброса 21.На втором этапе производится умно жение столбца матрицы множителя настроки матрицы множимого. На управляющий вход 17 блока 2 памяти множителя и блока 3 памяти множимого по"дается команда считывания. На входахматричного коммутатора 4 появляютсяэлементы соответствующих столбцовматрицы множителя, но только элементы 3 столбца последовательно передаются на выходы 11 матричного коммутатора 4 и далее на.входы элементов И З 7 и 8 блока б элементов логическогоумножения и суммирования. Одновременно с поступлением с выходов 11 элек.трического программируемого матричного коммутатора 4 Е-го элемента 3-го 40 столбца матрицы множителя с выходов12 блока 3 памяти множимого на другиевходы элементов И 7 и 8 соответствующих элементов логического умноженияи суммирования блока б.45 При подаче сигнала 19 сложения помодулю два в блок .б элементов.логического умножения и суммирования, на выходах 13 элементов И 7 появляютсясигналы, соответствующие величинам .р ас Ькоторые поступают на входыТ соответствующих КБТ-триггеров 9.На выходе 15 кБТ-триггера 9 и 1-гоэлемента логического умножения и сум.мирования блока б 1:п) появляютсясигйалы, соответствующие значениюфункции (2).В случае, если управляющий сигналподается с шины 20 логического сложения в блок б элементов логическогоо умножения и суммирования, сигналы,соответствующие а;к Ьс выходов 14 элементов И 8, подаются на входы Б КБТ-триггеров 9 и на выходе 15 кБТ- триггера 9 1 го элемента логическо- "И го умножения и суммирования блока бПреимущества предлагаемого устройства заключаются в расширении функциональных возможностей устройства, т.е. появляется возможность при использовании одного и того же устройства выполнять умножение булевых матриц по формулам (1) или (2), подавая различные управляющие сигналы, что является большим преимуществом для устройств цифровой обработки сигналов, устройств распознавания образцов,и других устройств матричной обработки информации, где применяются обе опе рации, Использование ЗУ позволяет производить считывание информации без разрушения, что избавляет от необходимости восстановления информации после считывания, позволяет не про изводить транспонирование матрицы множителя, что в конечном итоге ускоряет выполнение умножения матриц до порядка равного восьми, упрощает управление устройством и уменьшает 50 сложность устройства. формула изобретения55 1; Устройство умножения булевых матриц, содержащее блок управления, блоки памяти множимого, множителя и результата, причем входы считывания блоков памяти множимого и множителя подключены к выходу считывания блока управления, выход записи результата которого подключен к входу записи блока памяти результата, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможнос63 са в нулевое состояние распределителя импульсов. и к счетному входу счетпоявляются; сигналы, соответствующие значению функции (1).Таким образом, в зависимости от режима работы, на выходе каждого КЯТ-триггера 9 образуется элемент 1-го столбца матрицы результата, по лученного в виде (1) или в виде (2), После подачи на блок б элементов логического умножения и суммирования всех и элементов строк матрицы множимого и столбца матрицы множителя на 10 управляющий вход блока 5 памяти результата подается команда 18 записи и сдвига.Второй этап выполняется за и+1 микротакт. 15После выполнения второго этапа устройство переходит к выполнению первого этапа следующего цикла. При этом "единицы" записываются на и+1 строке матричного коммутатора 4.Суммарное время выполнения операции умножения. булевых матриц составляет и циклов по и+1 микротакта, что по сравнению с известным устройством позволяет увеличить быстродействие устройства для матриц, порядок. которых не превышает восьми. тей устройства за счет возможности выполнения операции умножения матриц по модулю два и увеличения быстродействия, устройство содержит программируемый матричный коммутатор и блок элементов логического умножения и суммирования, первый, второй и третий управляющие входы которого подключены к выходам суммирования по модулю два, логического суммирования и сброса в нулевое состояние блока управления соответственно, выходы блока элементов логического умножения и суммирования подключены к входам блока памяти результата соответственно, первая группа информационных входов блока элементов логического умножения и суммирования подключена к выходам программируемого матричного коммутатора соответственно, управля- ющие входы которого подключены к программирующим выходам блока управления соответственно, информационные входы программируемого матричного коммутатора подключены к выходам блока памяти множителя соответственно, выходы блока памяти множимого подключены к второй группе информационных входов блока элементов логического умножения и суммирования соответственно, синхронизирующий вход, вход тактовых импульсов, входы установки управляющего триггера в нулевое и единичное состояние блока управления подключены к синхронизирующему входу, входу тактовых импульсов, входам программной установки управляющего триггера в нулевое и единичное состояния устройства соответственно.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок управления содержит распределитель импульсов, элемент И, счетчик циклов, регистр и управляющий триггер, входы установки в нулевое и единичное состояние которого подключены к входам установки в нулевое и единичное состояние блока соответственно, нулевой и единичный выходы управляющего триггера подключены к выходам суммирования по модулю два и логического суммирования блока соответственно, выходы регистра подключены к программирующим выходам блока соответственно, вход тактовых импульсов регистра подключен к входу тактовых импульсов блока, информационный вход регистра подключен к первому выходу распределителя импульсов, второй и третий выходы которого подклю чены к выходам считывания и записи рерультата блока соответственно, четвертый выход распределителя импульсов подключен к выходу сброса в нулевое состояние блока, к входу сброчика циклов, выход которого подключен к. первому входу элемейта И, вто-, рой вход которого подключен к синхронизирующему входу блока, выход элемента И подключен к входу распределителя импульсов.3. Устройство по п,1, о т л и ч а ю щ е е с я тем, что блок элементов логического умножения и сложения содержит элементы логического умножения и суммирования., каждый,иэ которых содержит два элемента И и КИТ-триггер, причем в каждом элементе логического умножения и суммирования первые и вторые входы элементов И подключены к информационным входам первой и второй группы блока соответственно, третьи входипервого и второго элементов И подключены к первому и второму управляющимвходам блока соответственно, выходыпервого и второго элементов И подключены к Т- и Б-входам КЯТ-триггерасоответственно, В-вход которого подключен к третьему управляющему входублока.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 480077; кл,С 06 Р 7/50, 1976.2. Балашов Е,П. и др, Многофункци-ональные регулярные вычислительныеструктуры. М., "Советское радиоф,1978, с.73-76 (прототип).Составитель З.КайРедактор А.Гулько Техред И.Еоштура в рректор Г.ога 7/65 Тирак 731 Подп НИИПИ Государственного комитета СССР по делам изобретений и открытий13035, Москва, 3-35, Раушская наб, д.4 сное Заказ 701 В