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

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

На чертеже приведена схема предложенного логического запоминающего устройства.

Устройство содержит накопитель 1 с числовыми линейками 2 на тороидальных сердечниках 3 с прямоугольной петлей гистерезиса, пронизанных разрядными шинами 4 записи, разрядными шинами 5 считывания, разрядными щннами 6 чтения, линейными шинами 7 записи, линейными шинами 8 считывания, разрядные формирователи 9 записи, разрядные формирователи 10 считывания, разрядные элементы ИЛИ 11, разрядные элементы И 12, регистр 13 слова на триггерах 14, шину 15 сброса, входные элементы ИЛИ 16 с входами 17, элементы 18 задержки, элемент ИЛИ 19, управляюшие шины 20-27, элементы ИЛИ 28, регистр 29 адреса, управляющую шину 30, управляющую шину 31, служащую для управления установкой регистра адреса в исходное состояние, входные шины 32 регистра адреса, первый дополнительный элемент И 33, унравляющую шину 34, адресные элементы И 35, адресные формирователи 36 записи, адресные формирователи 37 считывания, управляющую шину 38, служащую для сброса, усилители 39 считывания, разрядные элементы 40 задержки, регистр 41 регенерации, управляющую шину 42, служащую для сброса, триггеры 43 регистра регенерации, управляющие шины

44, 45 для сброса, управляющую шину 46, триггер 47 признака окончания операции, триггер 48 признака перестановки, межразрядные элементы ИЛИ 4Э, второй дополиительный элемент И 50, первую группу элементов И 51, управляющую шину 52, вторую группу элементов И 53, третью группу элементов И 54, выходы 55 усилителей считывания, четвертую группу элементов И 56, управляющую шину 57, дополнительные входные элементы ИЛИ 58 с входами 59, дополнительный регистр 60 на триггерах 61, управляющие шины 62-64, дополнительные выходные элементы 65, дополнительные выходные элементы И 66, дополнительные разрядные элементы ИЛИ 67.

Одни входы межразрядных элементов ИЛИ 49 подключены к выходам усилителей 39, начиная с второго (на чертех е первый усилитель - справа), другие квыходам элементов И 51, а выходы - к информационному входу второго дополнительного элемента И 50 и к одним из входов элементов И 51, другие входы элементов И 51 подключены к нулевым выходам триггеров 43, другой пход ..торого дополнительного элемента И 50 - к шине 46. Одни входы элементов И 53 подключевы к единичным выходам триггеров 43, другие - к шине 52, а выходы - к входам входных элементов ИЛИ 16. Один из входов первого элемента И 51 (на чертеже - справа) подключен к выходу первого усилителя 39. Вход первого дополнительного элемента И 33 соединен с выходом второго дополнительного элемента И 50, а управляющий вход - с соответствующей шиной 34, выходы первого и второго дополнительного элементов И 33 и 50 подключены к триггерам 47 и 48 соответственно.

1-1нформационные входы элементов И 56 подключены к единичным вы.ходам триггеров 43, управляющие входы к шине 57, а

выходы к входам дополнительных элементов ИЛИ 58. Другие входы дополнительных входных элементов ИЛИ 58 связаны с входами 59, а выходы подсоединены к информационным входам триггеров 61, управляющие входы триггеров 61 подключены к шине 62.

Выходы триггеров 61 подключены к информационным входам дополнительных выходных элементов И 65, управляющие входы которых подключены к шине 64, а выходы связаны с одними из входов дополнительных разрядных элементов ИЛИ 67, другие входы которых связаны с выходами выходных элементов И 66, а выходы нодключены ко входам разрядных элементов И 12.

Информационные входы выходных элементов И 66 соединены с выходами триггеров 14, а управляющие входы подключены

к шине 63.

В предлагаемом устройстве выполнение элементарных логических операций (дизъюнкция, конъюнкция, запрет и другие) ироизводится так же, как и в известном. При этом операндами являются: некоторое елово X(xi, ..., Xi, ..., Хп, записанное на регистре 13, слова или слово Z(zi, ..., 2,-, ..., Zn), записанное на дополнительном регистре 60, и слово У (г/1, ..., у-:, ..., уп, хранящееся в избранной линейке 2 накопителя 1, причем Xi - это i-й разряд слова X, записанный в триггере 14 регистра 13 слова, Уг - это i-й разряд слова У, хранящийся в i-w. сердечнике 3 избранюй чтсловой линейки 2 накопителя 1, z; - это t-й разряд слова Z, записанный в триггере 61 дополнительного регистра 60, п-число разрядов. На регистре 29 адреса устанавливается код адреса, соответствующего числовой линейке 2 накопителя 1, в которой должна быть выиолнена операция.

Операция поиска по критерию «Ближайшее большее (меньшее) в описанном устройстве выполняется следующим образом.

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

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

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

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

Выполнение операции поиска по критерию «Ближайщее бо.льшее поясним, например, для массива длиной N, равного

6

числовых ячеек 2 в накопитеКОЛ-:(

ле 1.

В исходном состоянии в числовых ячейках 2 накопителя 1 хранятся слова массива информации Л1, в котором должен быть произведен поиск по критерию «Ближайшее большее по от;;ошению к числу, храняц1.ем}ся на регистре 13 слова, при этом тпиггеры 43 устанавливаются в нуль, триггеры 61 -в единицы, триггер 41 признака охончагпя операции и. триггер 48 признака ггпестановки - в НУЛЬ.

С помощью и-ппты 31 устанавливается на1:я1ь п.: адрес массива Л в котором необходгмо прпгтзвости поиск, при этом разряд регистра 29 адреса, связанный с адресным лс:гс:1том PI пегвой числовой линейки 2 изхоштеля 1, устанавливается в состояние «Ь, все остальные разряды регистра 20 адреса - в состояние «О. Кроме того, на рсгистпс 13 слова хстановлено слово А , являющееся аргументом поиска.

Каждь и;яг 1;а.1анного алгоритма выполняется за -1-11 тактов, причем на /-м ншге просмотпа массива сравниваются /-е слпт,о массива :; слово, находящееся на рсгис ле слова.

ТПлг состоит 3 слд Ю н,х тактов.

1.Выполнение поразрядтой логической спспаиии XY.

Для этого глодается сиг;;ал на нишу 24, п результате чего на разрядных И1инах 6 чтения тех разрядов, где л ,-, , появляются выходные сигналы, которые при подаче с гнала на шину 38 через усилители 39 пост .па;от на информационные входы соот1;етствующпх тр;;ггсров 43.

2.Восстановление слова У.

Для этого подается сиг;.ал на шину 26, п результате чего в f-f; числовой линейке 2 на1.:опителя 1 будет восстановлено слово Y.

3.Сравнение слов X и У по критерию y.Y.

Для этого подаетея сигиал на шину 20, в результате чего на разрядных шинах 6 чтения тех разря.з,ов, где л;г/; 1, появятся выходные сигналы, которые при подаче ., л а на шину 38 поступают через усилители 39 чтения нп информационные входы соответствующих триггеров 43, на входы разрядных элементов 40 задержки и на в:.:олы межразрядных элементов ИЛИ 49, младшего разряда, в котором при л-,,г, сигнал с выхода усилителя 39 чтения поступает на информационный вход первого триггера 43 (правый на чертеже), на вход первого разрядного элемента 40 задержки и на вход элемента И 51 второго разряда.

Далее с выхода межразрядного элемента ИЛИ 49 наиболее старшего t-ro разряда, для которого справедливо равенство л:,, кроме последнего разряда, поступает сигнал на вход элемента И 51 (f-

- 1)-го разряда, при этом, если для всехй-х разрядов, где имеет место равенство A:fti/ft 0, так как триггеры 43 всех разрядов старше г-го находятся в состоянии «О, то сигнал с выхода межразрядного элемента ИЛИ 49 /-ГО разряда поступает через элемент 51 и межразрядные элементы ИЛИ 49 старших разрядов на информационный вход второго дополнительного элемента И 50 (для ), т. е. из старшего разряда сигнал с выхода межразрядного элемента ИЛИ 49 поступает непосредственно на информационный вход второго дополнительного элемента И 50, при подаче сигнала на шину 46 проходит на вход установки в«1 триггера 48 признака перестановки. В то же время триггер 47 останется в первоначальном состоянии из-за отсутствия сигнала на шине 34.

Все вышеизложенное имеет место только в том случае, когда . Если , то для любого /-го разряда, в котором х-,уг 1, существует такой -разряд (где , в котором A/it/ft l, при этом k-K триггер 43 находится в состоянии «1, и сигнал из f-ro разряда пе может пройти на информационный вход триггера 48 перестановки и на информационный вход первого дополнительного элемента И 33, выход которого связан с информационным входом триггера 47 признака окончания операции. В том сл)чае, если , для любого г-го разряда справедливо равенство %ji/j 0.

Таким образом, в результате выполнения этого такта, сигнал на вход установки в «I триггера 48 перестановки поступает только в том случае, если , а сохранение нулевого состояния триггеров 47 и 48 происходит, если .

Кроме того, через время, определяемое разрядными элементами 40 задержки и элементом 18 задержки, происходит восстановление слова У в /-Й числовой линейке 2 накопителя 1, причем к этому моменту сигналы с шин 38 и 46 уже сняты, и ложного переключения триггера 48 признака перестановки произойти не может.

Дальнейшее выполнение шага зависит от результата, полученного в третьем такте шага. В том случае, если состояние триггера 48 после выполнения третьего такта шага-нулевое, то следует сравнить слово У в накопителе 1 с содержимым дополнительного регистра 60, так как имеет место соотношение .. Тогда следующие такты шага (для отличия присвоим им индекс единица) будут выглядеть так.

4(1). Очистка регистра 41 регенерации.

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

5(1). Выполнение поразрядной логической операции ZY.

Для этого подается сигнал на шину 24 и сигнал на шину 64, в результате чего на разрядных шинах 6 чтения тех разрядов,

где г,, появляются выходные сигнальт, которые при нодаче сигналов на шину 38 через усилители 39 поступают на информационные входы соответствующих триггеров 43.

6П.). Восстановление слова У. Для этого подается сигнал на ШИНУ 26, в результате в /-и числовой линейке 2 накопителя будет восстановлено слово.

7П). Сравнение слов Z и У по критерию

.

Для этого подается сигнал на пшну 20, в результате чего иа разрядных шинах 6

чтения тех разрядов, где 2,-м,, появятся выходные сигналы, которые при подаче

сиггтяла на шину 38 поступают через усилители 39 чтения на информационные входы соответствуюших триггеров 43, на входы разпядных элементов 40 задержки и на входы межразрядных элементов ИЛИ 49,

Р™ младшего разряда, в котором при 2„г,/„ сигнал с выхода усилителя 39 чтения поступает на информационный вход первого триггера 43 (правый на чертеже), на вход первого разрядного элемента 40

задержки и на вход элемента И 51 второго разряда.

Пялер с выхода межразрядного элемента ИЛИ 49 наиболее старшего г-го разряда, для которого снраведлиБО 2,-{/,, кроме

последнего разряда, поступает сигнал на вход элемента И 51 (I-1)-го разряда. При этом, если для всех й-х разрядов, где , пмрет место равенство 2;,уг,:0, т. е. триггеры 43 всех разрядов, старше г-го, нахо.аятся в состоянии «О, то сигна.л с выхода межразрядного элемента ИЛИ 49 j-ro разряда поступает через э.лемент И 51 и межразпядные элементы ИЛИ 49 старших разрядов на информационный вход второго

дополнительного элемента И50 (для ), т. е. из старшего разряда сигнал с выхода мех-грязрядного элемента ИЛИ 49 поступает непосредственно на информационный вход второго дополнительного элемента

И 50, и при подаче сигнала на шину 46 и сигнала на шину 34 ПРОХОДИТ на входы установки в «1 триггеров 47 и 48. Это имеет место только в том случае, когда .

Если же , то для любого г-го разряда, в котором Ziyi, существует такой разряд (где ), в котором . При этом А-й триггер 43 находится в состоянии «I, и сигнал из г-го разряда не

может пройти на информационный вход триггера 48 и через первый-дополнительный элемент И 33 на информационный вход триггера 47. В том случае, когда , для любого i-ro разряда справедливо ггУг 0. Таким образом, в результате

выполнения этого такта сигнал на вход установки в «1 триггера 47 поступает только в том случае, если .

Кроме того, через время, определяемое разрядными элементами 40 задержки и элементами 18 задержки, происходит восстановление слова У в /-Й числовой линейке 2 накопителя 1, причем к этому моменту сигналы шин 38 и 46 уже сняты, и ложного переключения триггера 47 произойти не может.

Дальнейшее выполнение шага зависит от результата, полученного на седьмом такте шага.

В том случае, если состояние триггера 47 после выполнения седьмого такта-единичное, следует записать слово У в дополнительный регистр 60, так как имеет место соотношение . Тогда следующие такты шага (для отличия присвоим им индекс два) будут выглядеть так.

8(2). Очистка регистра 41 регенерации.

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

9(2). Считывание слова, записанного по адресу, установленному на регистре 29 адреса, на регистр регенерации.

Для этого подается сигнал на шину 25, поступаюш,ий через разрядные элементы ИЛИ И на запуск разрядных формирователей 10 считывания. Одновременно через управляющий элемент ИЛИ 28 и адресный элемент И 35, второй вход которого связан с выходом соответствующего разряда регистра 29 адреса, который находится в единичном состоянии, происходит запуск адресного формирователя 37 считывания, соответствующего коду, установленному на регистре 29 адреса. Под действием адресного и разрядного полутоков происходит переключение в нулевое состояние тех сердечников 3, которые находились в состоянии «1, и на соответствующих разрядных шинах 6 чтения находятся выходные сигналы, которьте при подаче импульса на шину 38 через усилители 39 поступают на входы установки в «1 триггеров 43.

10(2). Пересылка содержимого регистра 41 регенерации на дополнительный регистр 60.

Для этого подается сигнал на шину 57, в результате чего через те элементы И 56, входы которых связаны с единичными выходами триггеров 43, находящихся в состоянии «1, и через дополнительные входные элементы ИЛИ 58 поступят сигналы на входы установки в единичное состояние соответствующих триггеров 61.

11(2). Анализ окончания поиска в массиве, подготовка к следующему шагу.

Производится очистка регистра 41 реге1 ерации посредством подачи управляющего сигнала на шину 42, поступающего на входы установки в «О триггеров 43, одновременно анализируется признак окончания поиска, вырабатываемый в блоке управления устройством (признак окончания поиска становится равным единице в том случае, когда код, установленный на регистре 29 адреса, равен адресу последнего слова массива, в нащем случае для массива длиной, равной количеству числовых линеек 2 накопителя 1, этот код - единица во всех разрядах).

В том случае, когда признак окончания поиска равен нулю, производится увеличение на единицу кода, установленного на регистре 29 адреса посредством подачи

сигнала на щину 30. Одновременно подаются управляющие сигналы на шины 44 и 45, устанавливающие триггеры 48 и 47 в состояние «0, а затем осуществляется переход к следующему щагу (т. е. снова на

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

сигнала, поступающего на шину 31.

В любом случае на дополнительном регистре 60 по окончании такта 11(2) хранится число, являющееся блил айшим большим по отношению к числу, хранящемуся

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

В том случае, если после выполнения третьего такта г-го шага триггер 48 нахоД1 тся в единичном состоянии, производить спэвнен ;е слова У с содержимым дополнительного регистра 60 не следует, так как имеет место соотношение У.Х. В этом случае следует перейти к следующему такту шага, который в отличие от обозначаемого елин1щей, обозначим единица-щтрих. Тогда следующие такты шага будзт выглядеть так.

4(1). Анализ окончания поиска в массиве, подготовка к следующему шагу.

Выполняется полностью аналогично такту 11(2). В том случае, если после выполнения седьмого такта i-ro щага состояние

триггера 47 нулевое, т. е. выполняется соотношение , не следует записывать слово У в дополнительный регистр 60. В этом случае следует перейти к следующему такту шага, обозначим его два-

штрих). Тогда следующие такты шага будут выглядеть следующим образом.

8(2). Анализ окончания поиска в массиве, подготовка к следующему шагу. Выполняется полностью аналогично такту

11(2). Таким образом, такты 11(2), 4(1) и 8(2) приводят к окончанию операции поиска по критерию «Ближайщее больщее относительно числа, хранящегося на регистре 13 числа, при этом результат поиска

находится на дополнительном регистре 60.

11

Аналогично могут быть выполнены операции поиска по критерию «Блилойшее меньшее.

Для этого (используя принятые обозначенртя: слово X, хранящееся на регистре 13 числа, слово У, принадлежащее массиву информации Л4, хранящемуся в накопителе 1, слово Z, находящееся на дополнительном регистре 60) происходит сравнение слова, находящегося на регистре 13 числа и являющегося аргументом поиска со словами, принадлежащими массиву М, хранящемуся в накопителе.

Когда J,y, происходит сравнение слова У с содержимым дополнительного регистра 60 (словом Z); когда , в этом режиме дополнительный регистр 60 должен быть установлен в нулевое состояние, слово У должно быть записано в дополнительный регистр 60. В этом случае единичное состояние триггера 48 будет соответствовать соотнощению , а нулевое состояние триггера 47 - соотнощению .

Все остальное производится аналогично вышеописанной операции поиска по критерию «Ближайолее большее.

Технико-экономическая эффективность изобретения заключается в возможности значительного повыщсния быстродействия за счет исключения предварительного упорядочения слов массива М в режиме поиска по критерию «Ближайщее большее (меньшее).

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

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

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

элементы ИЛИ. четвертую группу элементов И и два дополнительных э.лемента И, выходы которых подключены соответственно к входам триггеров, информационный вход первого дополнительного элемента И

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

дополнительных входных элементов ИЛИ, первые входы которых соединены с одними управляющими Щ1;нг1ми, а вторые с выходами элементов И четвертой группы, информационные вход, которых подключены

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

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

1.Авторское свидетельство СССР № 226681, кл. G НС 11/00, 1966.

2.Авторское свидетельство СССР № 428450, кл. G ПС 15/00, 1973.