Устройство для поиска информации в памяти

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 97 О д 4606 Р 15/4 ПИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРСНОМУ СВИДЕ ЬСТВУ к вычислить испольковых сисокращение в устройин стибрьск кий ти, реро нения,ассоциа 1 з и обриССР1979,ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Опубликованная заявка Втании В 2136612, кл, О 06 Р1984.Авторское свидетельство-СФ 809206, кл. С 06 Р 15/40,(54) УСТРОЙСТВО ДЛЯ ПОИСКАЦИИ В ПАМЯТИ(57) Изобретение относитсятельной технике и может бызовано в информационно-поистемах. Цель изобретения -оборудования. С этой цельюство, содержащее блок 1 пагистр Э признака поиска, фтель 4 адреса, схему 5 сраблок 10 управления, введентивный запоминающий блок 2ф-лы, 6 ил.Изобретение относится к вычислительной технике и может быть испольЗовано в информационно-поисковых системах.5Целью изобретения является сокращение оборудования,На фиг, 1 представлена схема предлагаемого устройства; на фиг. 2Схема формирователя адреса; на . рфиг. 3 - схема блока управления; нафиг. 4, 5 и 6 - временные диаграммыработы устройства.Устройство содержит блок 1 памяти,ассоциативный запоминающий блок 2, 5регистр 3 признака поиска, формирователь 4 адреса, схему 5 сравнения,Выходы 6 и 7 устройства, вход 8 устройства, выход 9 устройства, блок 10управления, связи 11-19, выходы 20 и 2021 устройства, связь 22,входы 23-26устройства, связи 27 и 28, элементы29 и 30 задержки, элементы И 31 и 32,элемент 33 задержки, элементы И 34 и35, элемент 36 задержки, элемент 25ИЛИ 37, элемент НЕ 38, элемент ИЛИ 39,элемент 40 задержки, элемент И 41,элемент ИЛИ 42, элемент НЕ 43, элемент И 44 элемент 45 задержки, элемент ИЛИ 46 и элемент НЕ 47, ЗОУстройство работает следующим образом,Устройство позволяет реализоватьзапись, хранение и поиск ш-разрядныхнформационных слов. Каждая ячейкаблока 1 и 5 лока 2 состоит из ш+разрядов, причем (в+1)-й разряд яв,ляется маркерным разрядом занятостиданной ячейки.Устройство может работать в одном.из трех режимов: запись информации,поиск информации и исключение информации. Порядок функционирования устройства в данных режимах иллюстрируется временными диаграммами. 45В режиме записи (фиг. 4) на вход8 устройства. поступает информационноеслово, а на вход 23 - потенциал единичного уровня. С подачей сигнала"Пуск" на вход 26 блок 10 управления50последовательно формирует сигналыединичного уровня на своих выходах12, 3 и 14, по которым соответственно производятся прием кода с входа 8на регистр 3 с выхода которого код- У55информационного слова поступает навход формирователя 4 адреса, навход схемы 5 сравнения и на информационные входы блоков 1 и 2; преобразование кода информационного слова в код адреса с помощью формирователя 4 адреса, с выхода которого код адреса поступает на адрес ный вход блока 1;считывание содержимого ячейки блокапо заданному формирователем 4 адресу.Если данная ячейка свободна, т,е. ее маркерный разряд, который поступает на вход 22 блока 10 управления, содержит О, на выходе 15 блока 10 уп-, равления формируется единичный сигнал, и так как выход 16 блока 10 управления, связанный с входами маркерных разрядов блоков 1 и,2, в режиме записи и поиска находится в единичном состоянии, а в режиме исключения - в нулевом, производится запись информационного слова и метки заносятся в блок 1, Если маркерный разряд выбранной ячейки блока 1 содержит 1, т,е. данная ячейка занята, блок 10 управления на выходе 17 формирует сигнал единичного уровня, по которому в блоке 2 производится запись информационного слова и метки заносятся в первую свободную ячейку. Если в. блоке 2 все ячейки заняты, то на выход 21 устройства поступает единичный сигнал переполнения, Блок 10 управле" ния выдает на выход 20 сигнал конца операции.В режиме поиска информации (фиг. 5) информационное слово поступает на вход 8 устройства, а на вход 24 подается потенциал единичного уровня. С подачей сигнала начала работы на вход 26 блок 10 пбследовательно формирует единичные сигналы сначала на выходах 12, 13, 14 и 18, а затем на выходе 11, по которым соответственно производятся:прием кода с входа 8 на регистр 3, с выхода которого код информационного слова поступает на входы формирователя 4 адреса, на вход схемы 5 сравнения и на информационные входы блоков 1 и 2;преобразование кода информационного слова в код адреса с помощью формирователя 4, с выхода которого код адреса поступает на адресный вход блока 1;считывание содержимого ячейки блока 1 по заданному формирователем 4,адресу, причем считанное слово поступает на вход схемы 5 сравнения, а99770 фор мул а 3 13также на вход 6 устройства, и одновременное выполнение поиска по признаку в блоке 1, причем адрес ячейки,содержимое которой совпадает с информационным словом, поступает на выход 7 устройства;проверка совпадения информационрого слова и слова, считанного изблока 1 на схеме 5 сравнения,При появлении на выходе 9 устройства единичного сигнала искомое слово находится в блоке 1 по адресу,определенному Формирователем 4, припоявлении нулевого сигнала данное.слово записано в блоке 2 в ячейке,адрес которой считывается с выхода7. Если на выходе 9 имеется нулевойсигнал и данное слово в блоке 2 ненайдено, то искомая информация в памяти не хранится, Блок 10 формируетна выходе 20 сигнал конца операции.Режим исключения (стирания) информации (фиг. 6) отличается от режимапоиска информации тем, что в исходном состоянии единичный сигнал подается на вход 25 устройства и одновременно с формированием единичногосчгнала на выходе 14 блока 10 управления формируется единичный сигнална его выходе 19, по которому производится запись по признаку в блок 2(при этом признаком является инфор.мационное слово, а записываемой ин"формацией - нулевой код в маркерномразряде блока 2), т.е. запись нуляв маркер занятости той ячейки, которая содержит информационное слово,На выходе 11 блока 10 управленияформируется единичный сигнал, по которому производится проверка совпадения информационного слова и снова,считанного иэ блока 1, на схеме 5сравнения. При появлении на выходе9 единичного сигнала, т.е. если инФормационное слово было найдено вблоке 1, на выходе 15 блока 1 О управления формируется единичный сигнал, под действием которого по адресу, определенному формирователем 4,производится запись нулевого значения в маркерный разряд блока 1. Блок1 О управления на выходе 20 формируетсигнал конца операции,При поиске информации по признакупризнаковая часть слов может помещаться в блок 1 памяти или в блок 2устройства, а информационная - в техже ячЕйках обычного блока памяти с 10 15 20 25 30 1 35 40 45 50 произвольным доступом и числом ячеек,равным общему числу ячеек блоков 1 и2 устройства. изобретения 1. Устройство для поиска информации в памяти, содержащее блок памяти, регистр признака поиска, формирователь адреса, схему сравнения, блок управления, причем информационный вход регистра признака поиска является информационным входом устройства, выход регистра признака поиска соединен с информационным входом формирователя адреса, выход которого соединен с адресным входом блока памяти, вход записи регистра признака поиска и синхронизирующие входы формирователя адреса и схемы сравнения соединены с выходом сигнала приема, выходом сигнала формирования адреса входом сигнала разрешения сравнения блока управления, выход схемы сравнения соединен с входом признака совпадения блока управления, о т л и ч а ю щ ее с я тем, что, с целью сокращения оборудования, оно содержит ассоциативный -запоминающий блок, информационный вход которого, информационный вход блока памяти и первый информационный вход схемы сравнения соединены с выходом регистра признака поиска, второй информационный вход схемы сравнения и первый информационный выход устройства соединены с информационным выходом блока памяти, выход схемы сравнения соединен с выходом сигнала наличия искомого слова устройства, второй информационный выход которого является информационным выходом ассоциативного запоминающего блока, выход признака занятости блока управления соединен с входами маркерных разрядов блока памяти и ассоциативного запоминающего блока, выход переполнения которого является выходом сигнала переполнения устройства, выход маркерного разряда блока памяти соединен с входом маркерного признака блока управления, выход сигнала разрешения считывания, первый н второй выходы сигналов разрешения записи, выход сигнала разрешения записи по признаку и выход сигнала разрешения поиска блока управления соединены с входами считывания и записи блока памяти, входами записи, записи по5 1399770 6признаку и разрешения поиска ассоци- разрешения сравнения блока и первыативного запоминающего блока соответ- ми входами пятого и шестого элементовственно, выход сигнала конца операции И, второй вход второго элемента И иблока управления является выходом первый вход второго элемента ИЛИ соепризнака окончания устройства, входы динены с входом признака поиска блоразрешения записи, поиска, стирания ка, выход второго элемента И соединени вход пуска которого являются входа- с вторым входом первого элемента ИЛИми признаков записи, поиска, стирания и выходом сигнапа разрешения поискаи входом пуска блока управления со- блока, вход признака совпадения блоответственно. ка соединен с вторым входом пятого2. Устройство по п, 1, о т л и - элемента И и через второй элемент НЕч а ю щ е е с я тем, что блок уп- с вторым входом второго элемента ИЛИ,равления содержит элементы И, ИЛИ, выход которого соединен с вторым вхоНЕ, задержки, причем вход пуска бло дом шестого элемента И, вход маркерКа соединен с входом первого элемента ного признака блока соединен с втоэадержки и выходом сигнала приема рым входом третьего элемента И и чеблока, выход первого элемента задерж- рез третий элемент НЕ с вторым вхоКи соединен с выходом сигнала форми- дом четвертого элемента И, вход прирования адреса блока и через второй 2 знака записи блока соединен с третьиэлемент задержки с выходом сигнала ми входами третьего и четвертого элеазрешения считывания блока, первыми ментов И, выход третьего элемента Иходами первого и второго элементов соединен с вторым выходом сигнала;1 и входом третьего элемента задерж- разрешения записи блока и через пяи, выход которого соединен с первы тый элемент задержки с первым входомМи входами третьего и четвертого эле- " третьего элемента ИЛИ, выход которогоментов И, второй вход первого эле- является выходом сигнала конца операмента И и вход первого элемента НЕ ции блока, первый и второй входы четсоединены с входом признака стирания вертого элемента ИЛИ соединены с выхоблока, выход первого элемента НЕ яв ходами четвертого и пятого элементовляется выходом признака занятости И, выход четвертого элемента ИЛИ соеблока, выход первого элемента И сое- динен спервым выходом сигнала раэреДинен с выходом сигнала разрешения шения записи блока и через шестойзаписи по признаку блока и первым элемент задержки с.вторым входом тревходом первого элемента ИЛИ выход тьего элемента ИЛИ третий вход кото 935которого через четвертый элемент за- рого соединен с выходом шестого элеДержки соединен с выходом сигнала мента И, 1399770399110 Составитель Н. МатвеевА. Лежнина Техред А.Кравчук Корректор О, Кравцова Ред Тираж 104 НИИПИ Государственног по делам изобретений 5, Москва, Ж, РаушПодписноекомитета СССРи открытийская наб д, 4