Ассоциативное запоминающее устройство

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК,.SU „„1274002

А1 (59 4 С 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3917086/24,-24 (22) 25.06.85 (46) 30.11.86. Бюл. У 44 (72) В.Н.Сасковец и И.Я.Акушский (53) 681.327(088.8) (56) Крайзмер Л.П., Бородаев Д.А. др. Ассоциативные запоминающие устройства, M. "Энергия", 1967,с.136.

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

У 496604, кл. G 11 С 19/00,1973., (54) АССОЦИАТИВНОЕ ЗАП0 1ИНА10ЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности, к запоминающим устройствам и предназначено для поиска информации по чис ловым критериям. Целью изобретения является расширение функциональных воэможностей устройства за счет увеличения числа типов поиска информации. Устройство содержит кольцевой накопитель, выполненный из циклических регистров сдвига, два счетчика, регистр, формирователь сигналов стирания и записи, генератор тактовых импульсов, два нуль-органа, три триггера, элементы ИЛИ и элементы И. Запись информации осуществляется установкой в единичное состояние того разряда регистра сдвига в накопителе, номер которого соответствует записываемому числу, помещенному в первый счетчик. В устройстве реализуются следующие типы ассоциативного поиска: поиск числа, большего (или меньшего) заданного, поиск наибольшего (или наименьшего) из записанных чисел. Поисковый числовой критерий помещается в первый счетчик, При считывании выполняется циклический сдвиг значений разрядов накопителя, причем второй счетчик подсчитывает число считанных единичных значений, которое сравнивается с поисковым критерием. При совпадении их первый счетчик устанавливается в нулевое состояние, в результа те считанное число выводится из регистра на выходы устройства. Но завершении циклического сдвига второй счетчик переходит в нулевое состояние, фиксируемое нуль-органом, импульсы сдвига блокируются и поиск по заданному критерию прекращается.! ил.

1274002

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

> статистической обработкй данных.

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

Устройство содержит кольцевой накопитель 1, первый 2 и второй 3 счетчики, регистр 4, вход 5 установки устройства и входы 6 сдвига накопителя 1. Устройство. содержит также формирователь 7 сигналов стирания и записи, первый нуль-орган 8, генератор 9 тактовых импульсов, первый 10 и второй 11 элементы И, первый элемент ИЛИ 12, второй нуль-орган 13, второй 14 и третий 15 элементы ИЛИ, триггеры 16-18 с первого по третий и элементы И 19-29 с третьего по тринадцатый.

На чертеже обозначены также управляющие входы 30 и 31 и входы 32-35 условия поиска, информационные входы 36 и выходы 37 устройства.

Кольцевой накопитель 1 выполнен на базе циклического регистра сдвига, разрядность которого определяется разрядностью счетчиков 2 и 3.

Устройство, работает следующим образом.

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

Устройство имеет шесть режимов работы: "Запись", "Стирание", причем сигналы подаются на входы 30 и 31 соответственно, поиск наименьшегочисла (вход 33), поиск наибольшего числа (вход 32), поиск числа большее заданного (вход 35), поиск числа меньшего заданного (вход 34). Перед посылкой любого из сигналов режима устанавливаются в нулевое состояние триггеры 16-18 сигналом со входа 5.

Рассмотрим работу устройства в

tt tI режиме Запись

Все разряды накопителя 1 находятся в нулевом состоянии, Код записыва15

55 емого числа цо входам 36 поступает в счетчик 3 ° Сигнал подается по входу

30, который открывает через элемент

ИЛИ 14 элемент И 21 и поступает на элемент И 10. После срабатывания от генератора 9 элемента И 21 импульсы проходят через элемент ИЛИ 12 на входы 6 накопителя 1, на вход счетчика 2, работающего в режиме сложения, и на вход счетчика 3, работающего в режиме вычитания, В накопителе 1 производится циклический сдвиг, осуществляющийся слева направо. Предположим, например, что в счетчик 3 был записан код 011 Э (т.е. число три). Тогда первый импульс от генератора 9 переведет счетчик 2 в состояние 001, счетчик

3 — в состояние 010 и произведет один сдвиг вправо в накопителе 1.

Второй импульс от генератора 9 произведет еще один сдвиг вправо в накопителе 1, переведет счетчик 2 в состояние 010 и счетчик 3 в состояние 001. Третий тактовый импульс произведет третий сдвиг в накопителе 1, устанавливает счетчик 2 в состояние

011 и счетчик 3 — в состояние 000.

Нулевое состояние счетчика 3 зафиксирует нуль-орган 8, который выдаст сигнал в открытый сигналом "Запис ь элемент И 10. Сигнал пройдет на вход формирователя 7 для установки в состояние "1" третьего слева разряда в накопителе 1, что соответствует записи числа три.

Далее через элемент И 21 должны быть выделены пять импульсов, производящих сдвиг в накопителе 1 до установки его разрядов в первоначальное положение. При этом импульсы сдвига, поступая на вход счетчика 2, последовательно увеличивают его содержимое на единицу. С приходом пятого (т.е. восьмого с начала работы) импульса сдвига счетчик 2 устанавливается в нулевое состояние 000. При этом срабатывает нуль-орган 13 и выдается импульс, устанавливающий триггер 18 в единичное состояние. Разрешающий потенциал с выхода триггера

18 перестает поступать на элемент И

21, что обуславливает запирание элеманта И 21, таким образом сигналы сдвига блокируются. После этого устройство готово к записи следующего числа. Будем считать, что подобнымже образом как и число "3", в накопитель

002 4 ется.

При стирании какого-либо числа необходимо это число записать в счетчик 3. После посылки сигнала "Установка" по входу 31 подается сигнал, открывающий элемент И 21. Работа уст- 10 ройства в режиме Стирание" аналогична работе в режиме "Запись". Отличие этих двух режимов заключается в том, что в результате установки счетчика

3 в состояние 000 сигнал, выдаваемый нуль-органом 8 через открытый элемент И Il, поступает на формирователь,7, который записывает "0" вкрайний левый (в данном случае)разряд в накопителе 1. 20

Относительно первоначального состояния накопителя 1 этот разряд имеет номер, равный числу, поданному в счетчик 3 для стирания. Установка разрядов накопителя 1 в первоначаль- 25 ное состояние производится аналогично режиму Запись 1.

Рассмотрим режим поиска наибольшего числа. Перед проведением режима подается сигнал УстаноЬка", устанав-З0 ливающий в нулевое состояние триггеры 16-18. Далее подачей по входу 32 сигнала открывается элемент И 20 и элемент 26. Каждый импульс, выданный элементом И 20, производит сдвиг в накопителе 1 на один разряд вправо и увеличивает содержимое счетчика 2 на единицу.

При сдвиге единиц, записанных в определенных (например, в первом, третьем, четвертом, шестом и седьмом) разрядах накопителя l, из крайнего правого разряда в крайний левый

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

4 всегда будет содержаться последнее 50 число, сдвинутое из крайнего правого разряда в крайний левый разряд накопителя. После выдачи элементом И -20 восьмого импульса счетчик 2 переходит в состояние 000 нуль. При этом срабатывает нуль-орган 13, устанавливает триггер IS в единичное состояние и импульс проходит через откры40 з 1274

1 были записаны, например, числа один, четыре, шесть, семь. После записи последнего числа этого массива чисел в накопитель 1 сигнал "Запись" сниматый элемент И 26, обеспечивая считывание информации с регистра.4. В этот момент регистр 4 содержит наибольшее число, записанное в накопителе 1, так как оно является последним сдвинутым числом.

Запрещающий потенциал, снимаемый с триггера 18, блокирует элемент И

20 и прекращает поступление сдвигающих импульсов в накопитель 1.

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

Число пять записывается в счетчик 3, состояние которого становится 101.

По входу 35 подается сигнал "Число больше заданного" на элемент И 28 и на элемент И 23, который вырабатывает импульс, производящий первый сдвиг вправо в накопителе 1, при этом устанавливается счетчик 2 в состояние

001 — (единица) и счетчик 3 — в состояние 100 — (четыре).При этом пере нос единицы, хранящейся в первом справа разряде накопителя (число

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

2 в регистр 4, в который записывается число 011 (три). Четвертый импульс от элемента И 23 производит четвертый сдвиг вправо в накопителе 1, устанавливает счетчик 2 в состояние

100 (четыре) и счетчик 3 в состояние

001 — (единица). При переносе единицы, хранящейся в четвертом разряде накопителя- 1, (обозначающей число четыре), в первый (левый) разряд образуется импульс, разрешающий перезапись содержимого счетчика 2 в регистр 4, который устанавливается в состояние 100 — (четыре). Пятый импульс сдвига переводит счетчик 2 в состояние 101 — (пять) производит пятый сдвиг вправо в накопителе 1 и устанавливает счетчик 3 в нулевое состояние, которое фиксируется нуль-органом :8.

С выхода нуль-органа 8 импульс проходит через открытй элемент И 28 и устанавливает триггер 17 в состояние "1". При этом открывается элемент И 25. Шестой импульс с выхода элемента И 23 производит шестой сдвиг вправо в накопителе, устанавливает счетчик 2 в состояние 110, при этом опять осуществляет перезапись содер74002

30

40

5 12 жимого счетчика 2 в регистр 4 (например, записывается число 110 шесть). Кроме того, этот же импульс проходит через открытый элемент И 25 и осуществляет считывание из регистра 4 на выходы 37 числа, большего заданного. Седьмой импульс, выданный элементом И 23, переводит счетчик 2 в состояние 111 (семь) и осуществляет седьмой сдвиг вправо в накопителе 1. При переносе единицы, хранящейся в седьмом разряде накопителя

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

Этот же импульс проходит через открытый элемент И 25 и осуществляет опрос регистра 4. На выходах 37 появляется число 111 (семь). Восьмой импульс, выданный элементом И 23, производит восьмой сдвиг в накопителе

1 и переводит счетчик 2 в нулевое. состояние, что фиксируется нуль-органом 13, который устанавливает триггер 18 в единичное состояние, при этом блокируется элемент И 23, после чего устройство готово к работе в другом режиме. Таким образом, на выходах 37 появились числа шесть и семь, являющиеся большими заданного числа пять.

Рассмотрим режим поиска числа меньшего заданного ° В счетчик 3 записывается число, относительно которого будет производиться поиск мень-. ших чисел, например число 101 †пя.

Сигнал по входу 34 открывает элемент

И 22, а через элемент ИЛИ 15 подается на вход элемента И 24. На этот же элемент И 24 подается разрешающий потенциал с нулевого плеча триггера 16.

Кроме того, сигнал на входе 34 открывает элемент И 29. Каждый импульс с выхода элемента И 22 производит очередной сдвиг в накопителе 1, устанавливает счетчик 2 в состояние, большее на "1", и счетчик 3 в состояние, меньшее на "1". При переносе единицы, хранящейся в крайнем правом разряде накопителя в крайний левый разряд образуется импульс, который разрешает перезапись содержимого счетчика 2 в регистр 4. Этот же импульс, 5 проходя через открытый элемент И 24,. осуществляет опрос регистра 4, и на выходных шинах появляется очередное число, хранившееся в накопителе 1 и меньшее заданного.

Этот процесс продолжается до тех пор, пока число сдвигов не станет равным заданному поисковому числу, причем по окончании этого сдвига счетчик 3 устанавливается в нулевое состояние, а содержимое счетчика 2 равно заданному поисковому числу.

Нулевое состояние счетчика 3 фиксируется нуль-органом 8, в результате блокируется опрос регистра 4, при следующих сдвигах числа из накопителя 1 (т.е. большие заданного) не поступают на входы 37 устройства.

Импульсы сдвига поступают на входы 6.накопителя 1 до тех пор, пока значения его разрядов не установятся в первоначальное состояние. В результате последнего сдвига счетчик 2 устанавливается в нулевое состояние, которое фиксируется нуль-органом 13, импульс с выхода которого устанавливает триггер 18 в единичное состояние, сигнал с выхода которого блокирует элемент И 22, что прекращает поступление импульсов сдвига.

При поиске минимального числа сигналы поступают по входу 33 через элемент ИЛИ 15 на элемент И 24, открывают элемент И 19 и элемент И 27.

Очередной импульс с выхода элемента И 19 производит вправо сдвиг накопителя 1 и устанавливает счетчик

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

Этот же импульс производит опрос регистра 4 и считывает минимальное число на выходы 37, проходя через открытый элемент И 24, и устанавливает триггер 16 в единичное состояние, проходя через открытый элемент И 27.

Запрещающий потенциал с нулевого плеча триггера 16 закрывает элемент

И 24 и этим прекращает дальнейший опрос регистра 4, После этого поступают импульсы сдвига, последовательно увеличивающие содержимое счетчика

2 на единицу и производящие сдвиг вправо в накопителе 1 до тех пор, по ка его разряды не установятся в пер7 1274 воначальное положение, а счетчик 2— в состояние 000, в результате блокируется поступление импульсов сдвига. формула изобретения

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

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

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

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

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

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

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

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

1274002

Составитель Т.Зайцева

Редактор А.Долинич Техред И.Попович Корректор А.Тяско

Заказ б482/50 Тираж 543 Подписное

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

113035, 11осква, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие,г.ужгород,ул.Проектная,4