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

Изобретение относится к вычислительной технике и может быть использовано Б системах управления базами данных. Известие устройство для поиска данных, содержащее блок приема признаков поискового предписания 5 блок приема данных, блок сравкения,, исполнительный блок и блок поразрядного сравнения ij . Недостаток известного устройства - низкое быстродействие, так как оно осуществляет последовательный поиск информации. Наиболее близким к предлагаемому является устройство для поиска инфор мации, содержащее регистры, подключенные к схеме сравненияj блок управ ления, соединенный с логическим блоком, с блоками сравнения адресов дорожки и числа, а выходы схемы сравнения подключены к соответствующим входам логического блока, выходы которого соединены с блоком формирования адресов дорожки и числа 2j . Недостатком данного устройства является низкое быстр.одействие, обус ловленное тем, что адрес первого рубежа формируется вне зависимости от степени заполнения запоминающего устройства информацией, что увеличивает макс-шальное число обращений для поиска записи по ключу. Цель изобретения - повышение быст родействия устройства. Поставленная цель достигается тем, что устройство для поиска информации, содержащее узел сравнения регистр ключа и регистр информации, группа выходов которого соединена с первой группой входов узла сравнения, вторая группа входов которого Соединена с группой вьгходов .регист(ра ключа, группа входов которого является группой входов числа устрой ства, содержит регистр сдвига, регистр рубежа,, регистр адреса5 выходной регистр; сут-шатор, три элемента задержки, генератор импульсов, дешиф ратор, четыре блока элементов И, бло элементов ИЛИ, блок памяти и элемент ИЛИ, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с управляющим входом устройства, а выход подключен к управляющему входу регистра сдвига, группа информационньпс входов которого является группой входов ключа искомой записи устройст 22 ва, а прямые выходы регистра сдвига соединены с входами дешифратора и с информационными входами первого блока элементов И, группа вьгходов которого соединена с первой.группой входов блока элементов ИЛИ, группа выходов которого соединена с первой группой входов сумматора, выходы которого соединены с входами регистра адреса, выходы которого соединены с информационными входами второго и третьего блоков элементов И и с входами блока памяти, выходы которого соединены с входами регистра информации, инверсные выходы регистра сдвига соединены с информационными входами четвертого блока элементов И, выходы которого соединены с второй группой входов блока элементов ИЛИ, выход генератора импульсов через первый элемент задержки соединен с управляющим входом второго блока элементов И, выходы которого соединены с входами регистра рубежа,группа выходов которого соединена с второй группой входов сумматора, причем выход генератора импульсов через второй элемент задержк:и соединен с управляющим входом сумматора, выход дешифратора соединен с первым входом элемента Ш1И, второй вход которого соединен с инверсньм входом элемента И, первым выходом узла сравнения и с управляющим входом третьего блока эи 1ементов И, выходы которого соединены с входами выходного регистра, группа вькодов которого является группой адресных вьгходов устройства, второй и третий выходы узла сравнения соединены с управляющими входами первого и четвертого блоков элементов И соответственно, выход дешифратора через третий элемент за,м,ержки соединен с прямым входом элемента И, выход которого является признаковым выходом устройства. На чертеже приведена схема устройства. Устройство содержит узел 1 сравнения с выходами 2 - 4,регистр 5 ключа, регистр 6 информация, регистр 7 сдвига, регистр 8 рубежа, регистр 9 адреса, выходной регистр 10, сумматор И, элементы 2 - 14 задержки, генератор 15 импульсов, деш ;фратор 6, блоки 17-20 элементов PJ, элемент И 21, блок 22 элементов ИЛИ, блок 23 памяти, элемент ИЛИ 24, группы 25 и 26 входов, вход 27 улразления, группу 28 выходов и признаковый выход 29 о Устройство работает следующим об разом, В исходном состоянии регистры 6 и 8 обнулены, а генератор 15 заторможен. В блоке 23 памяти записан упорядоченный по возрастанию ключей набор данных, в котором будет производиться поиск требуемой записи.. Число записей в блоке 23 равно 11. 241 ( где П - целое положительное число У или же дополнительно до этого числа фиктивными за писями с максимальным ключом. С гру пы 26 входов в регистр 7 записьшается число 2 . Ключ искомой записи заносится в регистр 5 по группе вхо дов 25. После этого устройство готово к поиску записи по ключу. Так как содержимое регистра 5 больше содержимого регистра 6 (искомый ключ не может быть нулевьм), то узел 1 сравнения выдает сигнал на выходе 3 Поиск информации инициируется по дачей импульса по входу 27, в резуль тате чего запускается генератор 15. Первый импульс на выходе генератора 15 произведет сдвиг содержимого регистра 7 на один разряд вправо. Тот же импульс с выхода элемента 13 задержки поступит на управляющий вхо сумматора 11, в результате чего Б ре гистр 9 запишется код 2 , сформир ванный в регистре 7 ( поскольку peгистр 8 обнулен). Этот код с задержкой, определяемой элементом 12, через блок 18 элементов И запишется в регистр 8. Кроме того, код с выхода регистра 9 поступит, на вход блока 23 памяти и считает содержимое соответствующей записи в регистр 6. Число представляет собой номер (ад рес) средней записи в наборе данных В дальнейшем (в зависимости от кода считанной записи) работа устройства может происходить следующим .обраКлюч считанной записи совпадает с искомым ключом. В этом случае появляется сигнал .на выходе 2 узла,1 , по которому адрес искомой записи заносится в регистр 10, а генератор 15 импульсов останавливается. Ключ считанной записи меньше искомого ключа. В этом случае вознирсает сигнал на выходе 3 узла 5 и сле дующий импульс с выхода генератора 15 сдвинет содержимое регистра 7 724 еще на один разряд вправо.Далее сумматор 1f сложит содержимое регистра 8 рубежа с новым содержимь м регистра 7 и операция сравнения повторится. Ключ считанной записи больше искомого ключа. Это приводит к появлению сигнала на выходе 4 узла I сравнения, в результате чего откроется блок 20 элементов И, который подключит к входу сумматора инверсный выход регистра 7. Очередной импульс на выходе генератора 15 сдвинет содержимое регистра 7 на один разряд вправо и вычтет его из содержимого регистра 8. Далее операция сравнения повторяется. В дальнейшем устройство работает аналогично. Номер очередного рубежа для -го типа сравнения формируется по следующему правилу: .-, где 1 - значение для 1-го и (l)-гo этапов сравнения, а знак перед степенью выбирается в зависимости от соотношения искомого ключа и ключа считанной записи на (л-О-м этапе сравнения. Когда после очередного сдвига и регистре 7 окажется единица, то это приведет к появлению сигнала на вы. дешифратора 16, который остановит генератор 15. Этот же сигнал с задержкой, необходимой для обновления состояния узла сравнения, поступит на прямой вход элемента И 21. Если к этому времени сигнал на выходе 2 узла 1 не появится, то сигнал на выходе 29 засвидетельствует отсутствие записи с искомь м ключом. Последующие, обращения к найденной записи могут бить реализованы путем установки устройства в исходное состояние и загрузки в регистр 9 адреса искомой записи, а в регистр 5 - ее ключа. После этого на вход 27 подается импульс, по которому на егистре 6 будет считана требуемая запись, а генератор 15 импульсов остановится. Таким образом, предлагаемое устройство по сравнению с устройством-прототипом позволяет сократить время поиска информации за счет

J1126972

степени заполнения памяти и ло обращений к блоку памяти сокр формирования адреса первого рубежа щается до величины Pog N , где Н в зависимости от числа записей (чис- число записей в наборе данных).

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