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

:.ИИ 0 Е ТЕЛЬСТВ ВТОРСИОМ вой группой ИЛИ, группа нена с перв а, вых ходы кот анова г запуска н с вх не ко с тора импульсо рого соединен устройства, а х входами выходног выходов которого адресных выходов и третий выходы динены с управля го и четвертого соответственно,регистра, групп вляется группой вляющим входом авыход подключен ра сдвига в которог устроиства, втузла сравненияющими входамиблоков элементвыход дешифратомент задержки сходом элементавляется признак группао являомой еги вхо ляющему информа ходу онны гервоов И люча иск пои вхо тся ямые выходы устроиства, а а сдвига соед апи ены с входа регист ми деш входам выход о рез третин эле нен с прямым в информацио ментов И, единена с ными раторапервого и выход которого я вым выходом устр которого иств ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРОО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) . Авторское свидетельство СССР У 31608, кл. О 06 Р 7/10, 1961,2. Авторское свидетельство СССР 9 342185, кл, С 06 Р 7/22, 1963 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ, содержащее узел сравнения, регистр ключа и регистр информации, группа выходов которого соединена с первой группой входов узла сравнения, вторая группа входов когорого соединена с группой выходов регистра ключа, группа входов которого является группой входов числа устройст - ва, о т л и ч а ю щ е е с я тем, что, с цельюовышения быстродействия, оно содержит регистр сдвига, регистр рубежа, регистр адреса, выходной регистр, сумматор, три элемента задержки, генератор импульсов, дешифратор. четыре блока элементов И, элемент И,блок элементов ИЛИ, блок памяти и элемент ИЛИ, ьыход которого входов блока элементо выходов которого соед ои груипои входов суммакоторогосоединены с входами регистра адреса, вь о - рого соединены с информационными входами второго и третьего блоков элементов И и с входами блока памяти, выходы которого соединены с входами регистра информации, инверсные выходы регистра сдвига соединены с ин- формационными входами четвертого блока элементов И, выходы которого соединены с вторсй группой входов блока элементов ИЛИ, вьход генератора импульсов через первый элемент д задержки соединен с управляющим входом второго блока элементов И, выходы которого соединены с входами регистра рубежа, группа выходов которого соединена с второй группой входов сумматора, при этом выход генератора импульсов через второй элемент задержки соединен с управляющим входом сумматора, выход дешифратора соединен с первым входом элемента ИЛИ, второй вход которого соединен с ин версным входом элемента И, первым выходом узла сравнения и с управляющим входом третьего блока элементов И, выходы которого соединены сИзобретение относится к вычислительной технике и может быть использовано в системах управления базами данных.Известнс устройство для поиска данных, содержащее блок приема признаков поискового предписания. блок приема данных, блок сравнения исполнительный блок и блок поразрядного сравнения 1 . . ОНедостаток известного устройства - низкое быстродействие, так как оно осуществляет последовательный поиск информации.Наиболее близким к предлагаемому 5 является устройство для поиска инфор- мации, содержащее регистры, подключенные к схеме сравнении, блок управления, соединенный с логическим блоком, с блоками сравнения адресов дорожки и числа, а выходы схемы сравнения подключены к соответствующим входам логического блока, выходы которого соединены с блоком формирования адресов дорожки и числа Я . 25Недостатком данного устройства является низкое быстродействие, обусловленное тем, что адрес первого рубежа формируется вне зависимости от степени заполнения запоминающего устройства информацией, что увеличивает максимальное число обращений для поиска записи по ключу.Цель изобретения - повышение быстродействия устройства.Поставленная цель достигается35 тем, что устройство для поиска информации, содержащее узел сравнения, регистр ключа и регистр информации, группа выходов которого соединена с40 первой группой входов узла сравнения, вторая группа входов которого соединена с группой вь;ходов регист" ра ключа, группа ходов которого является группой входов числа устройства, содержит регистр сдвига, ре 45 гистр рубежа,. регистр адреса, выходной регистр, сумматор, три элемента задержки, генератор импульсов дешиф" ратор, четыре блока элементов И, блок элементов ИЛИ, блок памяти и элемент ИЛИ, выход которого соединен с входом останова генератора импульсов, вход запуска которого соединен с управляющим входом устройства, а выход подключен к управляющему входу 55 регистра сдвига, группа информационных входов которого является группой входов ключа искомой записи устройства, а прямые выходы регистра сдвига соединены с входами дешифратора и с информационными входами первого блока элементов И, группа выходов которого соединена с первой группой входов блока элементов ИЛИ, группа выходов которого соединена с первой группой входов суькатора, выходы которого соединены с входами регистра адреса, выходы которого соединены с информационными входами второго и третьего блоков элементов И и с входами блока памяти, выходы которого соединены с входами регистра информации, инверсные выходы регистра сцвига соединены с информационными входами четвертого блока элементов И, выходы которого соединены с второй группой входов блока элементов ИЛИ, выход генератора импульсов через первый элемент задержки соединен с управляющим входом второго блока элементов И, выходы которого соединены с входами регистра рубежа, группа выходов которого соединена с второй группой входов сумматора, причем выход генератора импульсов через второй элемент задержки соединен с управляюцим входом сумматора, выход дешифратора соединен с первым входом элемента ИЛ, второй вход которого соединен с инверсным входом элемента И, первым выходом узла:равнения и с управляющим вхсдом третьего блока элементов И, вьгходы которого соедипены с входами выходного регистра, группа выходов которого является группой адресных вьходов устройства,второй и третий выходы узла сравнения соединены с управляющими входамипервого и четвертого блоков элементов И соответственно, выход,;гьифратора через третий элемент задержкисоединен с прямым входгм элемента И,выход которого является признаковымвыходом устройства.На чертеже приведена схема устройства.Устройство содержит узел 1 сравнения с выходами 2 - 4,регистр з клоча, регистр 6 информации, регистр 7сдвига., регистр 8 рубежа, регистр 9адреса, выходной регистр О, сумматор 1, элементы 2 - 1 ч задержки,генератор 15 импульсов, дешифратор 6, блоки 1 - 20 элементов И, элемент И 21, блок 22 элементов ИЛИ, блок 23 памяти, элемент ИЛИ 24, грппы 25 и 26 входов, вход 27 управлеИ;=й+2 Последующие, обращения к найденной записи могут быть реализованы путем установки устройства в исходное состояние и загрузки в регистр 9 адреса искомой записи, а в регистр 5 - ее ключа, 11 осле этого на вход 27 подается импульс, по которому на регистре 6 будет считана требуемая запись, а генератор 15 импульсов остановится.Таким образом, предлагаемое устройство по сравнению с устройством-прототипом позволяет сократить время поиска информации за счет 3 1126ния, группу 28 выходов и признаковый выход 29.Устройство работает следующим образом.В исходном состоянии регистры 6и 8 обнулены, а генератор 5 заторможен. В блоке 23 памяти записанупорядоченный по возрастанию ключейнабор данных, в котором будет производиться поиск требуемой записиЧисло записей в блоке 23 равнооМ =2 Ф 1где й - целое положительное число,.или же дополнительно до этого числа фиктивными записями с максимальным ключом. С Груп пы 26 входов в регистр 7 записывается число 2 . Ключ искомой записиИзаносится в регистр 5 по группе входов 25. После этого устройство готово к поиску записи по ключу. Таккак содержимое регистра 5 большесодержимого регистра 6 искомый ключне может быть нулевым), то узел 1сравнения выдает сигнал на выходе 3.Поиск информации инициируется подачей импульса по входу 27, в результате чего запускается генератор 15.Первый импульс на выходе генератора 5 произведет сдвиг содержимого регистра 7 на один разряд вправо.Тот же импульс с выхода элемента 1330задержки поступит на управляющий входсумматора 11, в результате чего ь регистр 9 запишется код 2, сформированный ь регистре 7 поскольку регистр 8 обнулен). Этот код с задерж кой, определяемой элементом 12, через блок 18 элементов И запишется в регистр 8. Кроме того, код с выхода регистра 9 поступит на вход блока 23 памяти и считает содержимое соответствующей записи в регистр 6. Число 2" " представляет собой номер (адрес) средней записи в наборе данных. В дальнейшем (в зависимости от кодасчитанной записи) работа устройства может происходить следующим,образом.Ключ считанной записи совпадает с искомым ключом. В этом случае появляется сигнал,на выходе 2 узла 1, по 50 которому адрес искомой записи заносится в регистр 10, а генератор 15 импульсов останавливается.Ключ считанной записи меньше искомого ключа. В этом случае возниает сигнал на выходе 3 узлаи следующий импульс с выхода генератора 15 сдвинет содержимое регистра 7 972 4еще на один разряд вправо. Далее сумматорсложит содержимое регистра 8 рубежа с новым содержимым регистра 7 и операция сравнения повторится.Ключ считанной записи больше искомого ключа. Это приводит к появлению сигнала на выходе 4 узла 1 сравнения, в результате чего откроется блок 20 элементов И, который подключит к входу сумматора инверсный выход регистра 7. Очередной импульс на выходе генератора 15 сдвинет содержимое регистра 7 на один разряд вправо и вычтет его из содержимого регистра 8. Далее операция сравнения повторяется,В дальнейшем устройство работает аналогично. Номер очередного рубежадля-го типа сравнения формируется по следующему правилу: где " - значение для-го и ( -) -го этапов сравнения, а знак перед степенью выбирается в зависимости от соотношения искомого ключа и ключа считанной записи на (-1)-м этапе сравнения.Когда после очередного сдвига в регистре 7 окажется единица, то это приведет к появлению сигнала на выходе дешифратора 16, который остановит генератор 5. Этот же сигнал с задержкой, необходимой для обновления состояния узла сравнения, поступит на прямой вход элемента И 21. Если к этому времени сигнал на выходе 2 узла 1 не появится, то сигнал на выходе 29 засвидетельствует отсутствие записи с искомым ключом.1126972 Составитель В. ИикуцкийРедактор А.Ревин Техред О.Ващишина Корре Демчи аз н 4/ иал ППП "Патент", г.ужгород, ул.Проектная учета степени заполнения памяти иформирования адреса первого рубежав зависимости от числа записей (чис 413 Я Тираж 6 ВНИИПИ Государстве по делам изобрет 113335, Иосква, Ж ло обращений к блоку памяти сокращается до величины 1 оф Й, где Нчисло записей в наборе данных). 8 Подпного комитета СССРний и открытий5 Раушская наб, д