Логическое запоминающее устройство Советский патент 1975 года по МПК G11C11/06 

ные формпрователи 37 считывания, адресные форм11р01ват€Л11 38 записи, шина 39 управлен.и}, шина 40 строба, усилители 41 чтения, реrncTip 42 регенерации, триггеры 43 регистра регенерации, шина 44 сброса, .вентили 45 регеиерацаи, разрядно-адресные вентилп 46 и выходы 47 ус11лителей чтения.

Элементарные логические операции (дизъio: :;.:;::i i, конъюнкция, пмпликащи;, запрет и Д пт1;е) 1ВЫ1ИОЛ:НЯ1ОТся при подаче уиравляющего сигнала иа одну из шип 20-23 управле Н11Я. При этом операндами являются входное слово X(Xi, ... ,Xi,..., Хп) и некоторое слово (или Слова) F(K,, . . ., F,-, . . ., К„), запи-оанное .в ч исловой линейке 2 (или ли ненках) .накопителя /, причем Xi-г-ый разряд входного слоiBa, лраняи1, щ t-ом триггере 14 фегист/ра 13 слава; У; - /-ый разряд -слава, Х раняш,;ийся в /-ОМ сердечнИ|Ке 3 ч:и|сло.вой линейки 2 Накап.ителя 1, п - число разрядов. Триггеры 34 регистра 33 iHpn HaKOB обращения той числовой лннейки, в которой должна выполняться операция, устанавливаются в единичное состояH ie.

Выполнение операции логического умножения матриц двоичных символов (булевских матриц) производится в два этана: на первом этане осуществляется транспонироваHiie матриц А, на втором - непосредственное получение попарных логических произзедений всех элементов строк -матриц с накоплением их 1В числовых линей,ках 2 накопителя 1.

О-иерадия лопЕческого ум:ножения булевских -матриц А и В определяется следующим образом;

Л 0 5 С, где С;у Va,i,,bkj.

h

Операция транспонирования матрицы двоичных символов Л определяется аналогично аперацН-и транспонирования обычных матриц

А i:.3 с, где С/у «;/.

Работу предлагаемого логического ЗУ при .выаголнении операции логического умножения булевских матриц нояоняют, например, для /квадратных матриц -с числом строк и столб.цов, равным п.

На первом этапе выполнения операции логического умножения булевских матриц Л и В производят транспонирование матрицы Л. В исходном состояни-и матрица Л записана в п последовательно расположенных числовых лннейках 2 накопителя /, начиная с некоторой Сгой числовой линейки 2, где через а,- (t 1, 2,... ,п) для удобства описания функционирования данного логи-ческого устройства обозначены ч-исловые линейки 2 накопителя /, в которых пер1воначально записаны строки матрицы Л, причем агой числовой линейке 2 соответствует t-ая строка матрицы Л, а состояние /-ГО сердечника 3 агОЙ числовой линейки 2 накопителя / соответствует значению элемента a,-j матрицы Л. Матрица В записана в л последов:ательно расположенных ч-исловых линейках 2 -накопителя 1, начиная с некоторой Ргой числовой линей.ки 2, тде через р,- (/

1, 2, . . ., я) обозначены числовые линейки 2 накопителя /, в которых первоначально записаны строки -матрицы В, причем Ргой числовой линейке 2 накопителя / соответствует г-ая строка матрицы В, а состояние /-ого сердечаника 3 Ргой Ч ислов-ой линейки 2 соот.ветсивует значению элемента 6,-j матрицы В. Разрядный распределитель 17 устанавливается iB исходное положение (сигнал на первом выходе) подачей управляющего импульса на

шину 18 начальной у-станов-к;. Триггеры 43 реги-стра 42 -реге-иерации, устан-свлены в нулевое положение, триггер 34 ре-гисгра 33 .признако1В обращен-ия, соответст-вующий арой Ч;и,с.1овой лпней.ке 2, - s состояние «1, а остальные триггеры 34 регистра 33 признаков обращения - в нулевое состояние. Первые п числовых линеек 2 .накопителя / очищены (сердечники 3 данных числовых линеек 2 находятся в состоянии «О).

Операция транспонирования булевской

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

на следующие такты:

Первый такт - считывание строки матрицы на регистр 42 регенерации.

Для этого на управляющую щи-.ну 24 подается сигнал, поступающий через управляющий

элемент 29 ИЛИ и через элементы 11 ИЛИ на запуск разрядных формирователей 10 считывания. Одновременно через управляющий элемент 29 ИЛИ и через а.дресный вентиль 36 происходит запуск того адресного формирователя 37 считывания, вход которого через -адрагиый (вантиль 36 связан с триогером 34 регистра 33 признаков обращения, находящимся в состоянии «1. При этом под действием адресного и разрядных полутоков считывается информация с соответствую.щей числовой линейки 2 накопителя /, и на разрядных щинах 6 чтения при переключении сердечников 3, находящихся IB состоянии «I, наводятся выходные сигналы, которые при подаче управляющего импульса на шииу 40 строба через усилители 41 чтения поступают на -входы установки в «1 триггеров 43 регистра 42 регенерации.

Второй такт - очистка регистра 33

признаков обраще-ния.

Для этого подается управляющий сигнал на шину 32 сброса, поступающий на входы установки в «О три-гге ров 34 -регистра 33 признаков О1браще-ния.

Третий такт - пересылка содержимого регистра 42 регенерации на регистр 33 при:з:наков обращения.

Для этого подается сигнал на управляющую 1Щ-ину 39, в .результате чего на :выходах разрядно-адресных вент1илей 46, входы которых ювязаны с шрямьши выходами триггеров 43 регистра 42 регенерации, находящихся в единичном состоянии, иоявляются выходные сигналы, которые через адресные элементы 31 ИЛИ поступают 1на входы установки в «1 соответствующих триггеров 34 регистра 33 признаков обращения.

Четвертый такт - запись -ой строки матрицы А в /г-ый разряд первых п числовых линеек 2 накопителя /.

Для этого подается сигнал на управляющую шину 26, поступающий через вентиль 30 М аскирова,ния, сигнальный вход которого связан с возбужденным выходом разрядного распределителя 17, и элемент // ИЛИ на запуск соответствующего разрядного формирователя 9 записи. Одновремевно -через управляющий элемент 29 ИЛИ и адресные вентили 36 происходит залуск тех адресных формирователей 38 записи, входы которых через адресные вентили 36 связаны с прямыми выходами триггеров 34 регистра 33 признаков обращения, находящихся в состоялии «1. При этом те сердечники 3 числовых линеек 2 лакопителя /, на которые воздействуют адресный ,и разрядный полутоки, переключаются IB состояние «1.

Таким образо, в результате вьиполнения этого такта в k-oM цикле происходит транспонирование й-ой строки матрицы А, т. е. состояние сердечников 3 k-oro разряда первых п числовых линеек 2 соответствует значениям элементов k-o& строки матрицы А.

Пятый такт - очистка регистра 42 регенерации и регистра 33 признаков обращения.

Для этого подается управляющий сигнал на шины 32, 44 сброса, поступающий на входы установки в «О триггеров 34 регистра 33 признаков обращения и триггеров 43 регистра 42 регенерации.

Шестой такт - анализ окончания транспонирования матрицы А, подготовка разрядного распределителя 17 и регистра 33 рризл.аков об|ращен:ия к следующему циклу.

В рассмотренном случае квадратных матриц с числом строк и столбцов, равным п, признаком окончания олерации транспонирования матрицы А служит наличие сигнала «а последнем выходе разрядного распределителя 17. (В более общем случае этот признак должен быть сформирован в блоке управления). Для трансполирования очередной строки матрицы Л производят лодготоБку к следующему циклу, которая осуществляется установкой в единичное состояние триггера 34 регистра 33 признаков обращения, соответствующего «4+1-ой числовой линейке 2, где k - номер цикла, посредством подачи сигнала на входы 35 регистра 33 Л1ризнаков обращения и подачей упр-авляющего импульса еа шину 19, в результате воздействия которой выходной сигнал разрядного распределителя 17 переходит с k-opo на ( -f 1) -ый выход.

Ори наличии сигнала окончания транслонирования матрицы А (сигнал на п-ом выходе

разрядного распределителя J7) поддается

упрвЕляющий имтульс на шину 18 начальной установки разрядного распределителя 17.

Таким образом, по окончании лервого этапа выполнения операции лотического умножения булевских м-атриц А и В, ъ первых п числовых линейках 2 накопителя 1 оказываются записаны строки транспонированной матрицы .

Для выполнения второго этапа освобождают первые п числовых линеек 2 лаколителя 1, что осуществляется -пересылкой млтрицы Л в те числовые линейки 2 накопителя /, в которых первоначально была записана матрица Л. Так как пересылка следует (непосредственно за этапом транспонирования матрицы А, триггеры 34 регистра 33 призлаглоз Об|ращен,11я и Tpiirrepbi 43 регистра 42 регенерацн-п находятся в нулевом состоящий; разрядный распределитель /7-в исходном состоянии (возбужден первый выход), а сердечники 3 с агой по а,г-ую числовых линеек 2 включительно - в состоянии «О. Пересылка матрицы Л производится за п циклов (в fe-oM цикле пересылается /г-ая строка матрицы Л ), каждый из которых включает в себя следующие такты:

Первый такт - установка адреса очередной строки Матр.пцы Л

Для этого на входь 3 5-регистра признаков обращения подается соответствующий входной сигнал, , который усталавливает А-ый триггер 34 регистра 33 признаков, обращения в состояние «1.

Второй такт -считывание fe-ой строки матрицы Л ла регистре регенерации.

Производится аналогично первому такту цикла этапа транспонирования матрицы Л посредством лодачи сигнала -на управляющую шину 24. .

Третий такт - очистка регистра 33 признаков обращения.

Для этого подается управляющий сигнал на шину 32 сброса, поступающий на входы установки в «О триггеров 34 регистра 33 приз(наков обращения.. :,

Четвертый такт - установка адреса аг;-ой числовой линейки 2.

Для этого на входы 35 регистра 33 признаков обращения подается входной сигнал, который устанавливает триггер. 34 регистра 33 признаков обращения, соответствующий числовой линейке 2 накопителя 1, в единичное состояние.;.

Пятый такт - запись k-он строки матрицы Л в Ой-ую ЧИСЛОВУЮ:линейку 2 накопителя 1.

Для этого подается Сигнал на управляющую ши1ну 27, поступающий через те вентили 45 регенер.ации, сигнальные входы которых .подключены к прямым выходам триггеров 43 регистра 42 регенерации, находящихся в состоянии «1, на .выходы элементов 11 ИЛИ, а .с выходов последних - на запуск соответствующих разрядных формирователей 9 записи. .Одновременно через управляющий элемент 29 ИЛИ и адресный вентиль «36 сигнальный вход

которого Связан с -Г)ймы-:,г выходом триггера 3 регистра 33 признако В обращении находящегося В Состоянш «1, происходят запуск сг/,)твеТ:СПвующ,его адресного форм-ироз-аггеля 38 . При этом тс Сердечники га/гой чнслоБсй линейки 2 накопителя ,/, на Которые воз.чеи.гзуют адресный и разрядный полутоки, лг.;к: л1Оча10тся в состояние «1. Таким образом, .3 результате выполнений этого такта в k-sM цикле в a/t-ofi Числовой линейке 2 окажется ззпИСана k-ал строка Флатр Щы А .

Шестой такт - очисггка регистра 33 льрлзнак-ав обраЩ-ан ня, очиют. репист-рл 42 pei-енерации, агНалнз окончания Лересылки 5aтpицы Л .

Для этого пщаеТся управляющий сигнал на шины 32 и 44 сброса, nocTynatomiui на входы уета,}ювки в «О трипгер-аа 34 регистра 33 признаков обращения и тригг«роа 4-3 регистра 42 регенерации. ОдноВременно анализтпгуется агризнак окончания пересылки матрицы Л (э .данЮМ случае - налиЧие сигнала iHa Последнем выходе разря аного распределителя 17}, в отсутствие которого подается управляющий импульс на шину -/Р, переводящий выходной сиплал разрядного расПределителя 17 с /г-ого на (k + 1)-ый выход. При наличии признака ахолчаиия пересыл:к11 мафращы Л ДЮДается управляющий сигнал на шину М начальной ycTaiHCJBixM .ра.з1ря1Дног.о раСП|р€деллтг.чя 17.

Так. образом, но окончании пересылки матрицы Л последняя оказывается записанной в числовых линейках 2 накопителя / с арой по сс„-ую числовую ЛИнейКу 2 ,ИтелЬно, сераечники 3 первых п числовых линеек.2 накопителя } находятся ;в состоянии «О, разрядный раопредеччитель 17 - в исходном состояяиИ (возбужден :п«рвый .выхОд), а -триггеры 34 (регистра 33 iipH3. О1б;раЩеМя й триггеры 43 регистра 42 (регенерации установлены в нулевое состояние. С этого момента начинается (второй STain (ВЬ полнеН|Ия опе.рац;Мн логического умножения булевской 1матр.ицы Л на булевскую матрицу В, осуществляемый также sa п циклов, .каждый (из 1которых включает s себя следующие девять тактов;

Первый т а к т - установка адреса ал-ой ЧИСЛОВОЙ линейкн i2.

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

Второй такт - считывание k-ofi строки матрицы Л .на регистр 42 регенерации.

Выполняется так же, как и первый такт цикла этапа транс-пониравания матрицы А при подаче ои пналов на управляющую шину 24 и шину 40 строба.

Третий та;кт - очистка регистра 33 призаaiKOiB о-бращаняя.

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

Четвертый т а к т - пересылка содержимого регистра 42 регенерации на регистр 33 признаков обращения.

Выполняется так же, как и третий такт цикла этапа транспонирования матрицы .4 при подаче сигнала на у1правляюп;ую шину 39.

Пятый такт - очистка регистра 42 регенерации.

Для этого подается управляющий сигнал на шину 44 сброса, поступающий на входы установки в «О приггеров 43 -.регистра 42 регенерации.

Шестой такт - установка адреса Рь-ой

числовой линейки -2. Для этого на шходы 35 регистра 33 .признаков обращения подается входной сигнал, который устанавливает триггер 34 регистра 33 приз.наков обращения, соответствующий Pfe-ой числовой линейке 2 на«ояителя 1, в единичное состояние.

Седьмой т а iK т - считьизаиие й-ой

строки матрицы В на регистр 42 регенерации.

Выполняется так же, как и Первый такт

цикла этана транспонирования .матрицы А,

с той лишь разницей, что управляющие сигналы подаются на шину 25 и также на ши-ну 40 строба. Это позволяет не осуществлять запуСК адресных фор.мирователей 37 считывания тех .первых п чйсло.вь1х линеек 2 накопителя /, которы.м соответствуют триггеры 34 регистра 33 -признаков обращения, находящиеся в единичном состоянии, что имеет место при равенстве единице соответствующих элементов k-ои строки матр:и.цы Л , записанной на регистр 33 признаков обращения в четвертом такте данного -цикла.

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

матриц Л и В состояние i-oro триггера 34 регистра 33 Признаков обращения будет соответствовать значению элемента матрицы А, равного элементу а/гг матрицы Л , а состояние триггера 43 /-ото разряда регистра 42 регенерации-значению элемента bhj матрицы В.

Восьмой такт - получение попарных

1Ко.нъю(НК,ций Между Всем1И элементами, й-ой

строюи матрицы Л и всеми элементами k-он

строки матрицы В.

Для этого атодается Сигн:ал на управляющую шину 27, поступающий через те вентили 45 регенерации, сигнальные входы которых связаны с пря.мыми выходами триггеров 43 регистра 42 регенерации, находящихся в един,ич1юм состоянии, и через схемы // ИЛИ на запуск соответствующих разрядных формирователей 9 записи- Одновраменно через управляющие элементы 29 ИЛИ и через те адресные веншили 36, сигнальные входы

которых coeдJИнвны с пря1МЫМ;и выходами триггерОВ 34 регистра 33 (признаоссв обращеиия, иаходящихся в состоящий «1, происходит запуск 1Соответствую ЩИХ адресных формирователей 38 записи. При этом в единичвое состояние переключаются только те сердечники 3 числовых линеек 2 .накопителя /, нахоаив111- бся .в cocTOHiHiiiH «О, на которые воздейстзуют а.дрсоный и ;разрядНый лолугоки, а те сс:5деч;н:11ки, которые .находиЛТьсь в СОСТОЯ :;.: «1, не заменят его. Та.к как i-ын адресны;( форм;1:оо,ватель 38 записи возбуждается 3 данном та-кте -ого цикла IB тс-м п только 3 том случае, когда элемент ац -матрш цы А (равный элементу а/,; матрицы А ) рявен едп/ггице, а .разрядный формирователь 9 записи /-аго разряда возбуждается в да:нНОЛ1 тажте ft-oro цикла в том и только .в том случае, когда элемент bhj матрицы В также равен едкн:ице, .сигнал лереключешия в еди|цич,ное 1состоя.н:ие сердечника 3 /-ото разряда t-ой Ч1ИСЛОВОЙ л.иней;ки 2 (Накопителя / (т. е. адновременное возбуждение г-ого адресного фор1м;ирОвателя 38 записи и разряд1ного формирователя 9 за.п1иои /-ОГО разряда) будет соответстзо.зать значению конъюнкции a:/,bi,i.

Кроме того, в результате выполнен.ия данного такта в /г-ом цикле строка матрицы В .будет воостащовлена в (З/гОЙ числовой линей.ке 2, откуд-а она была .сч-ита на в седьмом такте этого цикла, так как триггер 34 регистра 33 признаков обращения, соответствующий рй-ой ч;исловой л.инейке 2 .на1ко.г1ителя /, .при вьтолнении этого (восьмого) такта находится в состоянии «1.

Девятый такт - очиютка регистра 33 признаков .обращения, очистка регистра 42 регенерации, аиа.тиз окончаниЯ .опеграции ло.пичеакого умвдожееия ;булбвокой матрицы А на булевскую матрицу В.

Выполняется так же, как н шестой такт ЦИ-кла пе|ресыл1ки матрицы Л посредством подачи управляющих (Оигн.алов «а щ«ны 32 м 44 сброса и, лри .наличии признлка окончания операади:и (в данном случае - сигнала на :последнем выходе разрядного распределителя 17}, на шину 18 начальной установки разрядного ра.сиределителя 17, а в его отсутствие - на управляющую шину 19.

Таким образом, в .результате выиол;нения второго этапа олераци и логического умножения булевской матрицы А на булевскую матрицу В состояние 1сердечыико,в 3 j-oro разряда г-ой числовой линейю 2 .пакопителя 1

1

будет соответствовать значению V aikbin,

l l

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

Предмет изобретения

20

Логическое заполишающее устройство по авт. св. N° 226681, отличающееся тем, что, с целью расщирения области 1при1мбнения, оно содерж1ит разрядный распредел;итель, вентили маскирования, разрядно-адресные вентили и адресные элементы ИЛИ, выходы разрядного р.аспределителя соединены с сигнальяьши входами вентилей маскирования, к управляющим входам которых подключена соответствующая шина управления, а выходы вентилей маскирования подключены к элементам ИЛИ, сигнальные входы разрядноадресных вентилей соединены с .прямыми выходами триггеров регистра (регенерации,

управляющ|ие входы разрядно-адресных вентилей подключены к соответствующей щине управления, а выходы этих вентилей черс адресные элементы ИЛИ соедине;1Ы с единичными входамИ триггеров регистра n.p i3 iaков обращения.