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

 

Изобретение относится к вычислительной технике и может быть использрвано в информационно-поисковых системах . Цель изобретения - сокращение оборудования. С этой целью в устройство , содержащее блок I памяти, регистр 3 признака поиска, формирователь 4 адреса, схему 5 сравнения, блок 10 управления, введен ассоциативный 3anohMHaK4iffw: блок 2. 1 з,п. ф-лы, 6 ил.

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

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

РЕа !УБЛИК д!! 4 6 06 F 15/40

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ;!3,, Н А ВТОРСКОМЪ СВИДЕТЕЛЬСТВУ l (21 ) 4! 68932/24-24 (22) 29.12.86 (46) 30,05.88. Бищ. !! 20 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции

172) Марта Зеебауэр (НУ), В. И. Корнейчук и А. П. Марковский (su) (53) 681.325(088.8) (56) Опубликованная заявка Великобритании В 2136612, кл, G 06 F 15/40, 1984.

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

Ф 809206, кл. С 06 F 15/40, 1979.

„„SU„„1399770 А1 (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ В ПАМЯТИ (57) Изобретение относится к вычислительной технике и может быть использовано в информационно-поисковых системах. Цель изобретения — сокращение оборудования. С этой целью в устройство, содержащее блок 1 памяти, регистр Э признака поиска, формирователь 4 адреса, схему 5 сравнения, блок 10 управления, введен ассоциативный запоминающий блок 2 ° 1 s.n. ф-лы, 6 ил.

1399770

Изобретение относится к вычислительной технике и может быть испольЗовано в информационно-поисковых системах.

Пелью изобретения является сокращение оборудования.

На фиг, 1 представлена схема предлагаемого устройства; на фиг. 2 схема формирователя адреса; на . 10 фиг. 3 — схема блока управления; на фиг. 4, 5 и 6 — временные диаграммы работы устройства.

Устройство содержит блок 1 памяти, ассоциативный запоминающий блок 2, регистр 3 признака поиска, формирователь 4 адреса, схему 5 сравнения, выходы 6 и 7 устройства, вход 8 устройства, выход 9 устройства, блок 10 управления, связи 11-19, выходы 20 и 2р

21 устройства, связь 22, входы 23-26 устройства, связи 27 и 28, элементы

29 и 30 задержки, элементы И 31 и 32, элемент 33 задержки, элементы И 34 и

35, элемент 36 задержки, элемент 25

ИЛИ 37, элемент.НЕ 38, элемент ИЛИ 39, элемент 40 задержки, элемент И 41, элемент ИЛИ 42, элемент НЕ 43, элемент И 44 элемент 45 задержки, элемент ИЛИ 46 и элемент HE 47. 30

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

Устройство позволяет реализовать запись, хранение и поиск m-разрядных информационных слов. Каждая ячейка блока 1 и блока 2 состоит из m+1 разрядов, причем (m+1)-й разряд явЛяется маркерным разрядом занятости данной ячейки.

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

В режиме записи (фиг. 4) на вход

8 устройства. поступает информационное слово, а на вход 23 — потенциал единичного уровня. С подачей сигнала

"Пуск" на вход 26 блок 10 управления

50 последовательно формирует сигналы единичного уровня на своих выходах

l2, l3 и 14, по которым соответственно производятся прием кода с входа 8 на регистр 3 с выхода которого код

У

55 информационного слова поступает на вход формирователя 4 адреса, на вход схемы 5 сравнения и на информационные входы блоков 1 и 2; преобразование кода информационного слова в код адреса с помощью формирователя 4 адреса, с выхода которого код адреса поступает на адрес ный вход блока 1; считывание содержимого ячейки блока 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 ,I адресу, причем считанное слово поступает на вход схемы 5 сравнения, а

99770

Фор мул а

3 13

t также на вход 6 устройства, и одновременное выполнение поиска по признаку в блоке 2, причем адрес ячейки, содержимое которой совпадает с информационным словом, поступает на выход 7 устройства; проверка совпадения информационрого слова и слова, считанного из блока 1 на схеме 5 сравнения.

При появлении на выходе 9 устройства единичного сигнала искомое слово находится в блоке ) по адресу, определенному формирователем 4, при появлении нулевого сигнала данное. слово записано в блоке 2 в ячейке, адрес которой считывается с выхода

7. Если на выходе 9 имеется нулевой сигнал и данное слово в блоке 2 не найдено, то искомая информация в памяти не хранится. Блок 10 формирует на выходе 20 сигнал конца операции.

Режим исключения (стирания) инфор мацки (фиг. 6) отличается от режима поиска информации тем, что в исходном состоянии единичный сигнал подается на вход 25 устройства и одновременно с формированием единичного счгнала на выходе 14 блока 10 управления формируется единичный сигнал на его выходе 19, по которому производится запись по признаку в блок 2 (при этом признаком является инфор.мационное слово, а записываемой ин" формацией — нулевой код в маркерном разряде блока 2), т.е. запись нуля в маркер занятости той ячейки, которая содержит информационное слово .

На выходе 1) блока )О управления формируется единичный сигнал, по которому производится проверка совпадения информационного слова и снова, считанного иэ блока l, на схеме 5 сравнения. При появлении на выходе

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

10 управления на выходе 20 формирует сигнал конца операции.

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

50 произвольным доступом и чис ткам ячеек, равным общему числу ячеек блоков l u

2 устройства. изобретения

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

5 1399770 6 признаку и разрешения поиска ассоци- разрешения сравнения блока и nepBbtативного запоминающего блока соответ- ми входами пятого и шестого элементов ственно, выход сигнала конца операции И, второй вход второго элемента И и блока управления является выходом первый вход второго элемента ИЛИ соепризнака окончания устройства, входы динены с входом признака поиска блоразрешения записи, поиска, стирания ка, выход второго элемента И соединен и, вход пуска которого являются входа- с вторым входом первого элемента ИЛИ ми признаков записи, поиска, стирания и выходом сигнапа разрешения поиска и входом пуска блока управления со- блока, вход признака совпадения блоответственно.- ка соединен с вторым входом пятого

2. Устройство по п, 1, о т л и — элемента И и через второй элемент НЕ ч а ю щ е е с я тем, что блок уп- с вторым входом второго элемента ИЛИ, равления содержит элементы И, ИЛИ, выход которого соединен с вторым вхоHE задержки, причем вход пуска бло- 1> дом шестого элемента И, вход маркерКа соединен с входом первого элемента ного признака блока соединен с втоэадержки и выходом сигнала приема рым входом третьего элемента И и чеблока, выход первого элемента задерж- рез третий элемент НЕ с вторым вхоКи соединен с выходом сигнала форми- дом четвертого элемента И, вход прирования адреса блока и через второй знака записи блока соединен с третьиэлемент задержки с выходом -сигнала ми входами третьего и четвертого элеразрешения считывания блока, первыми ментов И, выход третьего элемента И ходами первого и второго элементов соединен с вторым выходом сигнала;

И и входом третьего элемента задерж- разрешения записи блока и через пяКи, выход которого соединен с первы- 26 тый элемент задержки с первым входом чи входами третьего и четвертого эле- " третьего элемента ИЛИ, выход которого ментов И, второй вход первого эле- является выходом сигнала конца операмента И и вход первого элемента HE ции блока, первый и второй входы четсоединены с входом признака стирания вертого элемента ИЛИ соединены с выхоблока, выход первого элемента HE яв- 3р ходами четвертого и пятого элементов ляется выходом признака занятости И, выход четвертого элемента ИЛИ соеблока, выход первого элемента И сое" динен с первым выходом сигнала разреДинен с выходом сигнала разрешения шения записи блока и через шестой записи по признаку блока и первым элемент задержки с. вторым входом тревходом первого элемента ИЛИ выход тьего элемента ИЛИ третий вход котоУ

35 которого через четвертый элемент за- рого соединен с выходом шестого элеДержки соединен с выходом сигнала мента И.

1399770

1399770

"23! 399770

О 26

О

Й2

О

U д

As

О

Ур

У

Ми

О

off

Уу

0 / б а

62О

О

Составитель Н. Матвеев

Редактор А, Лежнина Техред А.Кравчук Корректор О. Кравцова

Заказ 2668/50 Тираж 704 Подписное

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

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

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

П оектная 4