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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф (61) Дополнительное к авт. свид-ву— (22) Заявлено 18.07. 80 (21) 2961343/18-24 15$) М. Кд.з с присоединением заявки ¹â€”

G 06 F 7/00

ГоеуларсТвенный комитет

СССР оо лелам изобретений и открытий (23) Приоритет—

Опубликовано 15,09.82. Бюллетень ¹ 34 (33) УДК б 81. 3 (088. 8) Дата опубликования описания 15.09.82 (72) Авторы изобретения

Л. Ю. Коренев, В.И. Онищенко, Б. С. Петровский и А.М.Черепко ф (е;

Ф

Ленинградский институт авиационного приборос ро Ния (71) Заявитель (54) УСТРОИСТВО УМНОЖЕНИЯ БУЛЕВЫХ МАТРИЦ

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

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

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

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

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

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

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

Ф

С,. = V а„Ь„.

К=1

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

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

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

Зп микротактов.

Второй этап умножения производится за и циклов, каждый из которых состоит из 4 микротактов. В первом микротакте производится обнуление регистра слова и регистра многоадресного обращения. Во втором микротакте k-я строка транспонированной матрицы множимого передается из блока памяти множимого на регистр многоадресного обращения. В третьем микротакте k-я строка матрицы множителя передается из блока памяти множителя на регистр слова. B четвертом 45 микротакте в блоке памяти результата формируются попарные конъюнкции между элементами k-й строки транспонированной матрицы множимого и k-й строки матрицы множителя путем подачи соот- 5р ветствующих строк с регистра слова и регистра многоадресного обращения на,шины строк и столбцов блока памяти результата.

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

С „ = V а-„Ь1,.„(l)

1=1

Таким образом, для умножения булевых матриц, содержащих и строк и и столбцов требуется. 10 и микротактов обращения к блоку памяти 52 3. 65

Недостатками известного устройст ва являются невозможность выполнения операции умножения булевых матриц по модулю два, так как в нем осуществляется умножение булевых матриц, определяемое как (1), причем логическое сложение осуществляется путем последовательной записи в ячейку блока памяти результата минтермов а)к Ь1,„. Для выполнения умножения матриц по модулю два необходимо выполнять суммирование по модулю два. Выражение, определяющее умножение матриц по модулю два имеет вид

С, =О а..„Ь,„. к 9 (2)

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

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

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

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

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

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

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

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

5 обходимость в проведении операции. транспонирования матриц.

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

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

40 Схема включает блок 1 управления, блок 2 памяти множителя, блок

3 памяти множимого, матричный коммутатор 4, блок 5 памяти, блоки 6

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

7 и 8, RST-триггер 9, выход 10 блока памяти множителя, выход 11 электрически программируемого, выход 12 блока памяти множимого выход 13 логического элемента И 7, выход 14 логического элемента И 8, выход 15

55 блока логического умножения m cymmpoвания, шина 16 программирующего входа матричного коммутатора, управляющая шина 17 считывания блоков памяти множимего и множителя, управляющая шина 18 записи блока памяти

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

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

959063 программной установки управляющего триггера в нулевое и единичное состояния, распределитель импульсов

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 всех RST-триггеров 9 соединены с соответствующими входами блока 5 памяти результата. Программирующие входы 16 матричного коммутатора 4 соединены с соответствующими шинами блока управления. Управляющие входы

17 блока 3 памяти множимого, блока

2 памяти множителя и управляющий вход 18 блока 5 памяти результата соединены с соответствующими выходами блока управления 1. Управляющие входы блоков логического умножения и суммирования 6, 19 и 20 соединяют соответственно выходы блока 1 управ-. ления со входами логических элементов

И 7 и 8. Входы обнуления R RST-триггеров 9 соединены с шиной сброса блока управления 1.

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

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

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

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

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

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

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

1О результата.

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

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

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

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

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

40 столбца матрицы множителя с выходов

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

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

«р а Ь,которые поступают на входы

Т. соответствующих RST-триггеров 9.

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

СИГЙалы соответствующие значению функции (2).

В случае, если управляющий сигнал подается с шины 20 логического сложения в блок 6 элементов логического умножения и суммирования, сигналы, соответствующие а; Ь с выходов 14 элементов И 8, подаются на входы S

R5T-триггеров 9 и на выходе 15 RSTтриггера 9 1го элемента логическо"65 го умножения и суммирования блока 6

959063

Преимущества предлагаемого устройства заключаются в расширении функциональных возможностей устройства, т.е. появляется возможность при использовании одного и того же устройства выполнять умножение булевых матриц по формулам (1) или (2), подавая различные управляющие сигналы, что является большим преимуществом для устройств цифровой обработки сигналов, устройств распознавания образцов.и других устройств матричной обработки информации, где применяются обе операции. Использование ЗУ позволяет производить считывание информации без разрушения, что избавляет от необходимости восстановления информации после считывания, позволяет не про- 45 изводить транспонирование матрицы множителя, что в конечном итоге ускоряет выполнение умножения матриц до порядка равного восьми, упрощает управление устройством и уменьшает 50 сложность устройства.

Формула изобретения .

55 .4; Устройство умножения булевых матриц, содержащее блок управления, блоки памяти множимого, множителя и результата, причем входы считывания блоков памяти множимого и множителя подключены к выходу считывания блока управления, выход записи результата которого подключен к входу записи блока памяти результата, о т л и чающее с я тем, что, с целью расширения функциональных возможнос. J 6$ са в нулевое состояние распределителя импульсов. и к счетному входу счетпоявляются; сигналы, соответствующие значению функции (1).

Таким образом, в зависимости от режима работы, на выходе каждого

RST-триггера 9 образуется элемент

j-го столбца матрицы результата, полученного в виде (1) или в виде (2).

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

Второй этап выполняется за и+1 микротакт. 15

После выполнения второго этапа устройство переходит -к выполнению первого этапа следующего цикла. При этом "единицы" записываются на и+1 строке матричного коммутатора 4.

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

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

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

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

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

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

9 480077; кл.G 06 F 7/50, 1976.

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

959063

1Ю tt И

Составитель S.Êàéäàíîâ

Редактор А.Рулько Текред И.Ксиатура Корректор Г.Огар

Заказ 7017/65 Тирах 731 Подписное

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

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

Филиал ПНП "Патент", г.ухгород, ул.Проектная,4