Устройство умножения булевых матриц Советский патент 1982 года по МПК G06F7/00 

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

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

Недостатками этого устройства являются конструктивная сложностьи необходимость сложной коммутации на входе при выполнении операции умножения матриц.

Наиболее близким по технической сущности к, предлагаемому является устройство перемножения булевых матриц, содержащее запоминающее устройство с разрушением информациипри считывании, состоящее из трех

частей, содержащих соответственно матрицу множимого, матрицу множителя, функциональную часть, в которой производится вычисление матрицы результата. Входы блока памяти множимого соединены с выходами разрядного распределителя, а выходы со входами регистра многоадресного обращения. Выходы регистра-много10адресного обращения соединены со входами блока памяти результата. Выходы блока памяти результата и выходы блока памяти множителя соединены с соответствующими входами регис15тра слова. Выходы регистра слова соединены со входами блоков памяти множимого и результата. Выходы блока управления соединены с управляющими входами блоков памяти множимо20го, множителя, результата, разрядного распределителя, регистра слова и регистра многоадресного обращениями

Работа известного устройства состоит из двух этапов.

25

На первом этапе производится транспонирование матрицы множимого в функциональной части блока памяти множимого перестановкой строк и столбцов и последующая пересылка

30 строк транспонированной матрицы множимого в блок памяти множимого. На втором этапе формируются попарные логические произведения строк транспонированной матрицы множителя в функциональной части блока памяти множителя в виде V a,v b.,J J-K . Операция транспонирования булевой матрицы множимого производится за п циклов, каждый из которых состоит из трех ткротактов. В первом микротакте 1с-го цикла осуществляется считывание.и передача k-й строки матрицы множимого из блока памяти множимого на регистр многоадресного обращения в соответствии с состоянием разрядного распределителя и по команде бло ка управления. Во втором микротакте k-я строка матрицы множителя из регистра многоадресного обращения переписывается в k-й разряд блока памяти результата. В третьем микротакте производится обнуление регистра слова, регистра многоадресного обращения и подготовка разрядного распределителя к следующему циклу. Перед выполнением второго эта;па умножения матриц производится пересылка транспонированной матрицы множителя через резистр слова из блока памяти результата - в блок памяти множимого. Пересылка выполняется за Зп микротактов. Второй этап умножения производит ся за п циклов, каждый из которых состоит из 4 микротактов. В первом микротакте производится обнуление регистра слова и регистра многоадресного обращения. Во втором микротакте k-я строка транспонированной матрицы множимого передается из блока памяти множимого на регистр многоадресного обращения. В третьем микротакте k-я строка матрицы множи теля передается из блока памяти мно жителя на регистр сшова. В четверто микротакте в блоке памяти результат формируются попарные конъюнкции межд элементами k-й строки транспонирова ной матрицы множимого и k-й строки матрицы множителя путем подачи соот ветствующих строк с регистра слова и регистра многоадресного обращения на 111ИНЫ строк и столбцов блока памяти результата. После выполнения п циклов второго этапа в блоке памяти результата оказываются записанными строки матрицы результата в виде c %1, «jicbvi (1 Таким образом, для умножения булевых матриц, содержащих п строк и п столбцов требуется. 10 п микротактов обращения к блоку памяти 2 , Недостатками известного устройст-, ва являются невозможность выполнения операции умножения булевых матриц по модулю два, так как в нем осуществляется умножение булевых матриц, определяемое как (1), причем логическое сложение осуществляется путем последовательной записи в ячейку блока памяти результата минтермов ,-. Для выполнения умножения матриц по модулю два необходимо выполнять суммирование по модулю два. Выражение, определяющее умножение матриц по модулю два имеет вид ii. ©.-iVb в устройстве используется .блок памяти с разрушением информации, что приводит к необходимости восстановления информации после считывания и таким образом приводит к необходимости увеличивать время выпол нения операции. Кроме того, устройство не позволяет производить считывание информации как по строкам, так и по столбцам. Это приводит к необходимости транспонирования матриц путем пересылки ее строк из блока памяти множимого в блок памяти результата и обратно в блок памяти множимого. Результатом этого является значительное увеличение времени выполнения умножения и необходимость в сложном и громоздком управлении устройством из-за сложности системы пересылки информации между блоками памяти. Целью изобретения является расширение функциональных возможностей устройства за счет возможности выполнения операции умножения матриц по модулю два и увеличение быстродействия . Поставленная цель достигается тем, что устройство умноже.ния булевых матриц, содержащее блок управления, блоки,памяти множимого, множителя и результата, причем входы считывания блоков памяти множимого и множителя подключены к выходу считывания блока управления, выход записи результата которого подключен к входу записи блока памяти результата, устройство содержит программируемый матричный коммутатор и блок элементов логического умножения и суммирования, первый,второй и третий управляющие входы которого подключены к выходам суммирования по модулю два, логического суммирования, и сброса в нулевое состояние блока управления соответственно, выходы блока элементов логического умножения и суммирования подключены к входам блока памяти результата соответственно, первая группа информационных входов блока элементов логического умножения.и суммирования подключена к выходам программируемого матричного коммутатора соответственно, управляющие входы которого подключены к программирующим выходам блока управления соответственно, информационные входы программируемого матричного коммутатора подключены к

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

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

Блок элементов логического умножения и сложения содержит элементы логического умножения и суммирования, каждый из которых содержит два элемента И и RST-триггёр, причем в каждом элементе логического умнрже ния и суммирования первые и вторые входы элементов И подключены к информационным входам первой и второй группы блока соответственно, третьи входы первого и второго элементов И

подключены к первому и второму управляющим входам блока соответствен-н но, выходы первого и второго элементов И подключены к Т- и S-входам RST-триггера соответственно, R-вход которого подключен к третьему управляющему входу блока.

Применение электрически программируемого матричного коммутатора позволяет подавать элементы любого

0 столбца матрицы множителя на любой блок логического умножения и суммирования при подаче сигналов настройки с блока управления. Блоки логического умножения и суммирования позвог

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

0 можно производить как по строкам, так и по столбцам, независимо от порядка записи информации в блоке памяти. В связи с этим отпадает необходимость в проведении операции5транспонирования матриц. ; Таким образом, применение электрически программируемого матрич ного коммутатора, блоков логического {умножения и суммирования и ферро0акустических запоминающих устройств , позволяет достичь положительного эффекта, т.е. расширить функциональ|Ные возможности устройства при увеличении быстродействия.

5

На фиг.1 изображена функциональная схема устройства умножения булеЬых матриц; на фиг.2 - функциональная схема блока управления.

0

Схема включает блок 1 управления, блок 2 памяти множителя, блок 3 памяти множимйго, матричный коммутатор 4, блок 5 памяти, блоки 6 элементов логического умножения и

5 суммирования, количество которых равно количеству строк в матрице множимого и каждый из которых содержит два трехвходовых элемента И 7 и 8, RST-триггер 9, выход 10 блока памяти множителя, выход 11 электри0чески программируемого, выход 12 блока памяти множимого выход 13 логического элемента И 7, выход 14 логического элемента И 8, выход 15 блока логического умножения и суммиро5вания, шина 16 программирующего входа матричного кс 1мутатора, управляющая шина 17 считывания блоков памяти множимого и множителя, управляющая шниа 18 записи блока памяти

0 результата, управляющая шина 19 суммирования по модулю два, управляющая шина 20 логического суммирования, шина 21 сброса, синхронизирующий вход 22 устройства, вход 23 тактовых

5 импульсов устройства, входы 24 и 25

программной установки управляющего триггера в нулевое и единичное состояния, распределитель импульсов 26, элемент И 27, счетчик циклов 28, регистр 29, управляющий триггер 30.

Выходы 10 блока 2 памяти множителя соединены с информационными входами матричного коммутатора 4, каждый выход 11 которого соединен со входом соответствующего блока 6 элементов логического умножения и суммировария, а именно со вторыми входами элементов И 7 и 8. Каждый выход 12 блока 3 памяти множимого соединен с первыми входами элементов И 7 и 8 соответствующего блока 6 элементов логического умножения и суммирования. Выход 13 каждого элемента И 7 соединен со счетным входом Т соответствующего RST-триггера 9. Выход 14 каждого элемента И 8 соединен с установочным входом S соответствующего RST-триггера 9. Выходы 15 всех К5Т-тр1Иггеров 9 соединены с соответствующими входами блока 5 памяти результата. Программирующие входы 16 матричного коммутатора 4 соединены с соответствующими шинами блока управления. Управляющие входы 17 3памяти множимого, блока 2 памяти множителя и управляющий вход 18 блока 5 памяти результата соединены с соответствующими выходами блока управления 1. Управляющие входы блоков логического умножения и cy sмиpoвaния б, 19 и 20 соединяют соответственно выходы блока 1 управления со входами логических элементо И 7 и 8. Входыобнуления R RST-триггеров 9 соединены с шиной сброса блока управления 1. .

Принцип работы предлагаемого устройства состоит в следующем.

Операция умножения матриц состоит JI3 ряда циклически повторяющихся действий: логического умножения строки матрицы множимого на столбец матрицы множителя и суммирования получившихс минтермов. Количество циклов определяется максимальной размерностью матриц сомножителей. Для простоты рассмотрим умножение квадратных булевых матриц пхп.

В исходном состоянии в блоке 3 памяги множимого записана матрица мнозкимого А, в блоке 2 памяти множител - матрица множителя В, блок 5 памяти результата обнулен.

Работа устройства умножения булевых матриц состоит из двух этапов.

На первом этапе производится настройка матричного коммутатора. При этом в коммутаторе записывгиотся еди ницы в тех ячейках коммутации,/А которых должна образоваться связь между входными и выходными шинами. Наиболее рациональным является такой режим настройки, при котором единиц

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

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

0 результата.

Настройка матричного коммутатора 4 производится путем подачи на программирующие входы 16 матричного коммутатора 4 импульсов настройки, При этом

5 ультразшуковая волна возбуждается в одной строке, а импульсы поля подаются, во все столбцы матричного коммутатора. Настройка электрически программируемого матричного коммутатора 4

0 производится з.а один такт. Одновре- . менно производится обнуление RST-триггеров 9 подачей сигнала на шину сброса 21.

На втором этапе производится умножение столбца матрицы множителя на строки матрицы множимого. На управляющий вход 17 блока 2 памяти множитедя и блока 3 памяти множимого подается -команда считывания. На входах матричного коммутатора 4 появляются элементы соответствующих столбцов матрицы множителя, но только элементы j столбца последовательно передаются на выходы 11 матричного коммутатора 4 и далее на-входы элементов И :

5 7 и 8 блока 6 элементов логического умножения и суммирования. Одновременно с поступлением с выходов 11 электрического программируемого матричного коммутатора 4 k-ro элемента j-ro

0 столбца матрицы множителя с выходов 12 блока 3 памяти множимого на другие входы элементов И 7 и 8 соответствующих элементов логического умножения и суммирования блока 6.

5 При подаче сигнала 19 сложения по модулю два в блок 6 элементов.логического умножения и суммирования, на выходах 13 элементов И 7 появляются сигналы, соответствующие величинам

Q , которые поступают на входы Т соответствугадах RST-триггеров 9. На выходе 15 RST-триггера 9 и i-ro элемента логического умножения и суммирования блока б ) появляются

- сигналы, соответствующие значению функции (2)..

в случае, если управляющий сигнал подается с шины 20 логического сложения в блок б элементов логического умножения и суммирования, сигналы,

соответствующие а b - с выходов 14 элементов И 8, подаются на входы S RST-триггеров 9 и на выходе 15 RSTтриггера 9 i-го элемента логическо45 го умножения и суммирования блока 6 появляются; сигналы, соответствующие значению функции (1. Таким образом, в зависимости от режима работы, на выходе каждого RST-триггера 9 образуется элемент j-ro столбца матрицы результата, полученного в виде (1) или в виде (2) После подачи на блок б элементов логического умножения и суммирования всех п элементов строк матрицы множи мого и столбца матрицы множителя на управляющий вход блока 5 памяти результата подается команда 18записи и сдвига. ВТОРОЙ этап выполняется за n+l ми ротакт. После выполнения второго этапа устройство переходит к выполнению пер вого этапа следующего цикла. При 3том единицы записываются на n+l строке матричного коммутатора 4. Суммарное время выполнения операции уш1ожения. булевых матриц составляет п циклов по n+l микротакта, что по сравнению с известным устройством позволяет увеличить быстродействие устройства для матриц, порядок, которых не превышает восьми. Преимущества предлагаемого устрой ства заключаются в расширении функциональных возможностей устройства, т.е. появляется возможность при использовании одного и того же устройства выполнять умножение булевых мат риц по формулам (1) или (2), подавая различные управлякяцие сигналы, что является большим преимуществом для устройств цифровой обработки сигнало устройств распознавания образцов.и других устройств матричной обработки информации, где применяются обе oneрации. Использование ЗУ позволяет производить считывание информации без разрушения, что избавляет от необходимости восстановления информаци после считывания, позволяет не производить транспонирование матрицы множителя, что в конечном итоге уско ряет выполнение умножения матриц до порядка равного восьми, упрощает управление устройством и уменьшает сложность устройства. Формула изобретения J; Устройство умножения булевых матриц, содержащее блок управления, .блоки памяти множимого, множителя и результата, причем входы считывания блоков памяти множимого и кшожителя , подключены к выходу считывания блока управления, выход записи результата которого подключен к входу записи блока памяти результата, о т л и -; чающееся тем, что, с целью расширения функциональных возкюжностей устройства за счет возможности выполнения опергщии умножения матриц по модулю два и увеличения быстродействия, устройство содержит программируемый матричный коммутатор и блок элементов логического умножения и суммирования, первый, второй и третий управляющие входы которого подключены к выходам суммирования по модулю два, логического суммирования и сброса в нулевое состояние блока управления соответственно, выходы блока элементов логического умножения и суммирования подключены к входам блока памяти результата соответственно, первая группа информационных входов блока элементов логического умножения и суммирования подключена к выходам программируемого матричного коммутатора соответственно, управляющие входы которого подключены к программирующим выходам блока управления соответственно, информационные входы программируемого матричного коммутатора подключены к выходам блока памяти множителя соответственно, выходы блока памяти множимого подключены к второй группе информационных входов блока элементов логического умножения и суммирования соответственно, синхронизирующий вход, вход тактовых импульсов, входы установки управляющего триггера в нулевое и единичное состояние блока управления подключены к синхронизирующему входу, входу тактовых импульсов, входам программной установки управляющего триггера в нулевое и единичное состояния устройства соответственно. 2. Устройство по П.1, о тл ичающееся тем, что блок управлений содержит распределитель импульсов, элемент И, счетчик циклов, регистр и управляющий триггер, входы установки в нулевое и единичное состояние которого подключены к входам установки в нулевое и единичное состояние блока соответственно, нулевой и единичный выходы управляющего триггера подключены к выходам суммирования по модулю два и логичвского суммирования блока соответственно, выходы регистра подключены к программирующим выходам блока соответственно , вход тактовых импульсов регистра подключен к входу тактовых импульсов 5лока« информационный входрегистра подключен к первому выходу распределителя импульсов, вто рой и третий выходы которого подключены к выходам считывания и записи реэультата блока соответственно, четвертый выход распределителя импульсов подключен к выходу сброса в нулевое состояние блока, к входу сброса в нулевое состояние распределите- , ля импульсов, и к счетному входу счетчика циклов, выход которого подключен к. первому входу элемента И, второй вход которого подключен к синхрониэирукяцему входу блока, выход элемента И подключен к входу распределителя импульсов.

3. Устройство по П.1, отличающееся тем, что блок элементов логического умножения и сложения содержит элементы логического умножения и суммирования., каждый из которых содержит два элемента И и RST-триггер, причем в каждом элементе логического умножения и суммирования первые и вторые входы элементов И подключены к информационным входам первой и второй группы

блока соответственно, третьи входи первого и второго элементов И подключены к перйому и второму управляющим входам блока соответственно, выходы первого и второго элементов И подключены к Т- и S-входам RST-триггера соответственно, R-вход которого подключен к третьему управляющему входу блока.

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

1 Авторское свидетельство СССР 480077; кл.С Об F 7/50, 1976.

2. Балашов Е.П. и др. Многофункхдаональные регулярные вычислительные структуры. М., Советское радио, 1978, с.73-76 (прототип).

W

IS f9 fff

7/ 18 ir 16 19 Pii.t