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

« Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть применено для поиска в большом объеме хранящихся данных информации по числовым критериям для р)ешения задач статистической обработки данных. Целью изобретения является расширение функциональных возможностей . устройства за счет увеличения числа типовпоиска информации. На чертеже представлена функциональная схема предложенного устройства. Устройство содержит кольцевой накопитель 1, первый 2 и второй 3 счет чики, регистр 4, вход 5 установки устройства и входы 6 сдвига накопителя 1. Устройство, содержит также формирователь 7 сигналов стирания и записи, первый нуль-орган 8, генератор 9 тактовых импульсов, первый 10 и второй 1 элементы И, первый элемент ИЛИ 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. Рассмотрим работу устройства в режиме Запись. Все разряды накопителя 1 находятся в нулевом состоянии. Код записыва 0022 емого числа цо входам 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, в накопитель

1 были записаны, например, числа один четыре, шесть, семь. После записи последнего числа зтого массива чисел в накопитель 1 сигнал Запись снимается .

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

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

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

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

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

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

Запрещающий потенциал, снимаемый с триггера 18, блокирует элемент И 20 и прекращает поступление сдвигающих импульсов в накопитель 1.

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

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, при этом опяч.ь осуществляет перезапись содеожимого счетчика 2 в регистр 4 (например, записывается число 110 шесть), Кроме того, этот же импульс проходит через открытый элемент И 25 и осуществляет считьшание из регистра 4 на выходы 37 числа, большего за данного. Седьмой импульс, выданный элементом И 23, переводит счетчик 2 в состояние 111 (семь) и осуществляет седьмой сдвиг вправо в накопителе 1. При переносе единиды, хранящейся в седьмом разряде накопителя 1, из крайнего правого разряда в крайний левый разряд образуется импульс, который разрешает перезапись содержимого счетчика 2 в регистр 4. Этот же импульс проходит через откры тый элемент И 25 и осуществляет опрос регистра 4, На выходах 37 появляется число 111 (семьУ. Восьмой импульс, выданный элементом И 23, производит восьмой сдвиг в накопителе I и перецрдит счетчик 2 в нулевое со стояние, что фиксируется нуль-органом 13, которьй устанавливает триггер 18 в единичное состояние, при этом блокируется элемент И 23, после чего устройство готово к работе в другом режиме. Таким образом, на выходах 37 появились числа шесть и семь, являющиеся большими заданного числа пять. Рассмотрим режим поиска числа меньшего заданного. В счетчик 3 записывается число, относительно кото- 35 соответствующее состояние. При

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

Сигнал по входу 34 открывает элементсоответствующей минимальному записанИ 22, а через элемент ИЛИ 15 подается на вход элемента И 24. На этот же элемент И 24 подается разрешающий потенциал с нулевого плеча триггера 16. Кроме того, сигнал на входе 34 открывает элемент И 29. Каждый импульс с выхода элемента И 22 производит очередной сдвиг в накопителе 1 устанавливает счетчик 2 в состояние, большее на 1, и счетчик 3 в состояние, меньшее на 1 При переносе хранящейся в крайнем правом единицы разряде накопителя в крайний левый разряд .образуется импульс, который разрешает перезапись содержимого сче чика 2 в регистр 4. Этот же импульс, йроходя через открытый элемент И 24, осуществляет опрос регистра 4, и на выходных шинах появляется очередное 1 26 число, хранившееся в накопителе 1 и меньшее заданного. Этот процесс продолжается до тех пор, пока число сдвигов не станет равным заданному поисковому числу, причем по окончании этого сдвига счетчик 3 устанавливается в нулевое состояние, а содержимое счетчика 2 равно заданному поисковому числу. Нулевое состояние счетчика 3 фиксируется нуль-органом 8, в результате блокируется опрос регистра 4, при следующих сдвигах числа из накопителя 1 (т.е. большие заданного) не поступают на входы 37 устройства. Импульсы сдвига поступают на входы 6. накопителя 1 тех пор, пока значения его разрядов не установятся в первоначальное состояние. В результате последнего сдвига счетчик 2 устанавливается в нулевое состояние, которое фиксируется нуль-органом 13, импульс с выхода которого устанавливает триггер 18 в единичное состояние, сигнал с выхода которого блокирует элемент И 22, что прекращает поступление импульсов сдвига. При поиске минимального числа сигналы поступают по входу 33 через элемент ИЛИ 15 на элемент И 24, открывают элемент И 19 и элемент И 27. Очередной импульс с выхода элемента И 19 производит вправо сдвиг накопителя 1 и устанавливает счетчик ному числу, из крайнего правого разряда накопителя 1 в крайний левый его разряд образуется импульс, которьй осуществляет перезапись содержимого счетчика 2 в регистр 4. Этот же импульс производит опрос регистра 4 и считывает минимальное число на выходы 37, проходя через открытый элемент И 24, и устанавливает триггер 16 в единичное состояние, проходя через открытый элемент И 27. Запрещающий потенциал с нулевого плеча триггера 16 закрывает элемент И 24 и этим прекращает дальнейший опрос регистра 4. После этого поступают импульсы сдвига, последовательно увеличивающие содержимое счетчика 2 на единицу и производящие сдвиг вправо в накопителе 1 до тех пор, по ка его разряды не установятся в пар71

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

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

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

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

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

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