Устройство для поиска информации в памяти Советский патент 1988 года по МПК G06F17/30 

со со со

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

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

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

Устройство содержит блок 1 памяти фссоциативный запоминающий блок 2, регистр 3 признака поиска, формирова- teль 4 адреса, схему 5 сравнения, йыходы 6 и 7 устройства, вход 8 устройства, выход 9 устройства, блок 10 управления, связи 11-39, вьрсоды 20 и 2 устройства, связь 22, входы 23-26 устройства, связи 27 и 28, элементы 29 и 30 задержки, элементы И 31 и 32 : лемент 33 задержки, элементы И 34 и J5, элемент 36 задержки, элемент ИЛИ 37, элемент-НЕ 38, элемент ИЛИ 39 элемент 40 задержки, элемент И 41, элемент ИЛИ 42, элемент НЕ 43, элемент И 44 элемент 45 задержки, элемент ИЛИ 46 и элемент НЕ 47.

Устройство работает спеду1ш;им об- разом.

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

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

В режиме записи (фиг. 4) на вход 8 устройства поступает информационно (лоно, а на вход 23 - потенциал единичного уровня. С подачей сигнала Пуск на вход 26 блок 10 управления последовательно формирует сигналы единичного уровня на своих выходах 12, 13 и 34, по которым соответственно производятся прием кода с входа 8 ма регистр 3, с выхода которого код информационного слова поступает на Эход формирователя 4 адреса, на вход схемы 5 сравнения и на и-нформа- даонные входы блоков 1 и 2;

Q

5 0 5 о

5

0

5

преобразование кода информацион- Hoi o слова в код адреса с помощью формирователя 4 адреса, с выхода которого код адреса поступает на адрес ный вход блока 1;

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

Если даннай ячейка свободна, т.е. ее маркерный разряд, который поступает на вход 22 блока Ю управления, содержит О, на выходе 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 сравнения, а

3

также на вход 6 устройства, и одновременное выполнение поиска по признаку в блоке 2, причем адрес ячейки содержимое которой совпадает с информационным словом, поступает на вы ход 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 блока 10 управления формируется единичньй сигнал, под действием которого по адресу, определенному формирователем 4, производится запись нулевого значения в маркерный разр яд блока 1. Блок 10 управления на выходе 20 формирует сигнал конца операции.

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

99770

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

2 устройства.

5

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

1. Устройство для поиска информации в памяти, содержащее блок памяти,

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

15 выход регистра признака поиска соединен с информационным входом формирователя адреса, выход которого соединен с адресным входом блока памяти, вход записи регистра признака поиска

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

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

5Q выход маркерного разряда блока памяти соединен с входом маркерного признака блока управления, выход сигнала разрещения считывания, первый и второй выходы сигналов разрешения запи- gg си, выход сигнала разрешения записи по признаку и сигнала разрешения поиска блока управления соединены с входами считывания и записи блока памяти, входами записи, записи по

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

2, Устройство поп, 1, отли чающееся тем, что блок управления содержит элементы И, ИЛИ, НЕ, задержки, причем вход пуска блока соединен с входом первого элемент вздержки и выходом сигнала приема блока, выход первого элемента задержки соединен с выходом сигнала формирования адреса блока и через второй элемент задержки с выходом сигнала )азрешения считывания блока, первыми Ьходами первого и второго элементов 1 и входом третьего элемента задерж- |си, выход которого соединен с первы- Йи входами третьего и четвертого элементов И, второй вход первого элемента И и вход первого элемента НЕ соединены с входом признака стирания блока, выход первого элемента НЕ является выходом признака занятости блока, вьгход первого элемента -И соединен с выходом сигнала разрешения записи по признаку блока и первым Входом первого элемента ИЛИ, выход Которого через четвертый элемент за- Держки соединен с выходом сигнала

5

0

5

0

5

разрешения сравнения блока и первыми входами пятого и шестого элементов И, второй вход второго элемента И и первый вход второго элемента ИЛИ соединены с входом признака поиска блока, выход второго элемента И соединен с вторым входом первого элемента ИЛИ и выходом сигнала разрешения поиска блока, вход признака совпадения блока соединен с вторым входом пятого элемента И и через второй элемент НЕ с вторым входом второго элемента ИЛИ, выход которого соединен с вторым входом шестого элемента И, вход маркерного признака блока соединен с вторым входом третьего элемента И и через третий элемент НЕ с вторым входом четвертого элемента И, вход признака записи блока соединен с третьими входами третьего и четвертого элементов И, выход третьего элемента И соединен с вторым выходом сигнала разрешения записи блока и через пятый элемент задержки с первым входом третьего элемента ИЛИ, выход которого является выходом сигнала конца операции блока, первый и второй входы четвертого элемента ИЛИ соединены с выхо- ходами четвертого и пятого элементов И, выход четвертого элемента ИЛИ соединен с первым выходом сигнала разрешения записи блока и через шестой элемент задержки с вторым входом третьего элемента ШШ, третий вход которого соединен с выходом шестого элемента И,

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

27

29

i J

2o

я:

3 о

f f OJ

2

j °

/T7 on

-x

T

2/

f3 I $ t

o

/f

Й7

F

nil

23 Zif 25 26

( i 6 9

Фиг.1

ZB

Фаг.г

n

t/Я О

26

l/1Z

О

о и

1/„

%

п