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

 

УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ , содержащее узел сравнения, регистр ключа и регистр информации, группа выходов которого соединена с первой группой входов узла сравнения, вторая группа входов которого соединена с группой выходов регистра ключа, группа входов которого является группой входов числа устройст;ва , о тлич ающе е с я тем, что, с целью 1;овышения быстродействия, оно содержит регистр сдвига, регистр рубежа, регистр адреса, выходной регистр , сумматор, три элемента задержки , генератор импульсов, дешифратор , четыре блока элементов И, элемент И,блок элементов ИЛИ, памяти и элемент ИЛИ, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с управляющим входом устройства, а выход подключен к управляющему входу регистра сдвига, группа информационных входов которого является группой входов ключа искомой записи устройства, а прямые выходы регистра сдвига соединены с входами дешифратора и с информационными входами первого элементов И, группа выходов которого соединена с первой группой входов блока элементов ИЛИ, группа выходов которого соединена -С первой группой входов cybtMaтора , выходы которогосоединены с входами регистра адреса, выходы которого соединены с информационныь и входами второго и третьего блоков элементов И и с входами блока памяти, выходы которого соединены с входами регистра информации, цнверсные выходы регистра сдвига соединены с информацнонными входами четвертого блока элементов И, выходы которого соединены с второй группой входов блока элементов ИЛИ, выход генератора импульсов через первый элемент задержки соединен с управляющим входом второго блока элементов И, выходы которого соединены с входами р гистра рубежа, группа выходов которого соединена с второй группой входов, сумматора, при этом выход генератора импульсов череэ второй элемент задержки соединен с у11равляющим входом сумматора, выход дешифратора соединен с первь м входом элемента ИЛИ, ю второй вход которого соединен с инО ) версным входом элемента И, первым се выходом узла сравнения и с управляющим входом третьего блока элементов И, зыходы которого соединены с входами выходного регистра, группа выходов которого является группой адресных выходов устройства, второй и третьи выходы узла сравнения соединены с управляющими входами первого и четвертого блоков элементов И соответственно, выход дешифратора череэ третий элемент задержки соединен с прямь м входом элемента И, выход которого является признаковым выходом устройства.

СО!ОЗ СОВЕТСНИХ

СО!4ИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (!9) (11) 3(1) G 06 F 15/40

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPHTHA

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

yrrrpemi s

i i;; I )I()

t(P P g j (? А 1!

4863! ИО ЕКА

1 (21) 3628239/24-24 (22) 04.05.83 (46) 30.!!.84. Бюл. К - 44 (72) Б.С.Богумирский, В.Я.Яцук и Н.С.Литус (53) 681.325(088.8) (56) I. Авторское свидетельства СССР !! 316087, кл. G 06 F 7/10, 1961.

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

Р 342185, кл. С 06 F 7/22, 1963 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОР—

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

ИЛИ, группа выходов которого соединена с первой группой входов сумматора, выходы которого соединены с входами регистра адреса, выходы кото—

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

1126972

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

Известно устройство для поиска данных, содержащее блок приема признаков поискового предписания. блок приема данных, блок сравнения„ исполнительный блок и блок поразрядного сравнения jl) . . 1О

Недостаток известного устройства — низкое быстродействие, так как оно осуществляет последовательный поиск информации.

Наиболее близким к предлагаемому является устройство для поиска инфор- мации, содержащее регистры, подклю— ченные к схеме сравнении, блок управления, соединенный с логическим блоком, с блоками сравнения адресов дорожки и числа, а выходы схемы сравнения подключены к соответствующим входам логического блока, выходы которого соединены с блоком формирования адресов дорожки и числа P) . 25

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

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается

35 тем, что устройство для поиска информации, содержащее узел сравнения, регистр ключа и регистр информации, группа выходов которого соединена с Щ первой группой входов узла сравнения, вторая группа входов которого соединена с группой вь;ходов регист" ра ключа, группа входов которого является группой входов числа устройства, содержит регистр сдвига, ре45 гистр рубежа,. регистр apoeñа, выходной регистр, сумматор, три элемента задержки, генератор импульсов,, дешиф" ратор, четыре блока элементов И, блок элементов ИЛИ, блок памяти и элемент ИЛИ, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с управляющим входом устройства, а выход подключен к управляющему входу 55 регистра сдвига, группа информационных входов которого является группой входов ключа искомой записи устройства, а прямые выходы регистра сдвига соединены с входами дешифратора и с информационными входами первого блока элементов И, группа выходов которого соединена с первой группой входов блока элементов ИЛИ, группа выходов которого соединена с первой группой входов суьматора, выходы которого соединены с входами регистра адреса, выходы которого соединены с информационными входами второго и третьего блоков элементов И и с входами блока памяти, выходы которого соединены с входами регистра информации, инверсные выходы регистра сцвига соединены с информационными входами четвертого блока элементов И, выходы которого соединены с второй группой входов блока элементов ИЛИ, выход генератора импульсов через первый элемент задержки соединен с управляющим входом второго блока элементов И, выходы которого соединены с входами регистра рубежа, группа выходов которого соединена с второй группой входов сумматора, причем выход генератора импульсов через второй элемент задержки соединен с управляюцнм входом сумматор"., выход дешифратора соединен с первым входом элемента И1 Л, второй вход которого соединен с инверсным входом элемен:а И, первым выходом узла:..равнения и с управляющим вхсдом третьего блока элементов И, выходы которого соединены с входами выходногo регистра, группа выходов которого является группой адресных вь..ходов устройства, второй и третий выходы узла сравнения соединены с управляющими входами первого и четвертого блоков элементов И соответственно, выход,,ьифра— тора через третий элемент задержки соединен с прямым входом элемента И, выход которого является признаковым выходом у стройства.

На чертеже прив едена схема у стройства.

Устройство содержит узел 1 сравнения с выходами 2 — 4,регистр 5 клоча, регистр 6 информации, регистр 7 сдвига., регистр 8 рубежа, регистр 9 адреса, выходной регистр 10, сумматор 11, элементы !2 — 14 задержки, генератор 15 импульсов, дешифратор

16, блоки 1? — 20 элементов И, элемент И 21, блок 22 эл"-ментов И11И, блок 23 памяти, элемент ИЛИ 24, гр п— пы 25 и 26 входов, вход 27 унравле—

И; =!1,,+2

Последующие, обращения к найденной записи могут быть реализованы путем установки устройства в исходное состояние и загрузки в регистр 9 адреса искомой записи, а в регистр

5 — ее ключа. После этого на вход 27 подается импульс, по которому на регистре 6 будет считана требуемая запись, а генератор 15 импульсов остановится.

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

3 1126 ния, группу 28 выходов и признаковый выход 29.

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

В исходном состоянии регистры 6 и 8 обнулены, а генератор 15 заторможен. В блоке 23 памяти записан упорядоченный по возрастанию ключей набор данных, в котором будет производиться поиск требуемой записи.

Число записей в блоке 23 равно

Д

Й =2 e I (где rl — целое положительное число) .или же дополнительно до этого числа фиктивными записями с максимальным ключОм О груп пы 26 входов в регистр 7 записывается число 2 . Ключ искомой записи

И заносится в регистр 5 по группе входов 25. После этого устройство готово к поиску записи по ключу. Так как содержимое регистра 5 больше содержимого регистра 6 (искомый ключ не может быть нулевым), то узел 1 сравнения выдает сигнал на выходе 3.

ПОиск инфОрмации инициируется пО- 25 дачей импульса по входу 27, в результате чего запускается генератор 15.

Первый импульс на выходе генератора !5 произведет сдвиг содержимого регистра 7 на один разряд вправо.

Тот же импульс с выхода элемента 13

30 задержки поступит на управляющий вход сумматора 11, в результате чего ь регистр 9 запишется код 2, сформированный ь регистре 7 (поскольку регистр 8 Обнулен). Этот код с задерж- >5 кой, определяемой элементом 12, через блок 18 элементов И запишется в регистр 8. Кроме того, код с выхода регистра 9 поступит на вход блока 23 памяти и считает содержимое соответ- 40 ствующей записи в регистр 6. Число 2" " представляет собой номер (адрес) средней записи в наборе данных.

В дальнейшем (в зависимости от кода считанной записи) работа устройства может происходить следующим,обра зом.

Ключ считанной записи совпадает с искомым ключом. В этом случае появляется сигнал,на выходе 2 узла 1, по 50 которому адрес искомой записи заносится в регистр 10, а генератор 15 импульсов останавливается.

Ключ считанной записи меньше искомого ключа. В этом случае возни- 55 ает сигнал на выходе 3 узла и следующий импульс с выхода генератора 15 сдвинет содержимое регистра 7

972 4 еще на один разряд вправо. Далее сумматор !! сложит содержимое регистра 8 рубежа с новым содержимым регистра 7 и операция сравнения повторится.

Ключ считанной записи больше искомого ключа. Это приводит к появлению сигнала на выходе 4 узла 1 сравнения, в результате чего откроется блок 20 элементов И, который подключит к входу сумматора инверсный выход регистра 7. Очередной импульс на выходе генератора 15 сдвинет содержимое регистра 7 на один разряд вправо и вычтет его из содержимого регистра 8. Далее операция сравнения повторяется.

В дальнейшем устройство работает аналогично. Номер очередного рубежа ! для -ro типа сравнения формируется по следующему правилу: где " — значение для -го и (i - ) -го этапов сравнения, а знак перед степенью выбирается в зависимости от соотношения искомого ключа и ключа считанной записи на (j-1)-м этапе сравнения.

Когда после очередного сдвига в регистре 7 окажется единица, то это приведет к появлению сигнала на выходе дешифратора 16, который остановит генератор !5. Этот же сигнал с задержкой, необходимой для обновления состояния узла сравнения, поступит на прямой вход элемента И 21.

Если к этому времени сигнал на выходе 2 узла 1 не появится, то сигнал на выходе 29 засвидетельствует отсутствие записи с искомым ключом.

l l 26972

Составитель В. Микуцкий

Редактор А.Ревин Техред О.Ващишина Корректор И.Демчик

Заказ 874)/38 Тираж 698 Подписное

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

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

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная, 4 учета степени заполнения памяти и формирования адреса первого рубежа в зависимости от числа записей (число обращений к блоку памяти сокращается до величины 1оф Й, где Н число записей в наборе данных).