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

(51 ГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ МУ СВИДЕТЕЛЬСТВ К АВТО нстиОР иееЪеудачный коне горитма, и К=О-, Сравнение. Ес Если К Кь то Если К= К;,то у Если К44, т Корректировк на 4. ли К К;,т переход н дачный ко о переход О.О = -1 о пера 5,нецана 6,пере ритма на 2(54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНМАЦИИ Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки систем управления базами знаний (СУБЗ).Цель изобретения - упрощение устройства и повышение быстродействия устройства за счет реализации поиска в упорядоченном по ключам массиве информации по методу Айверсона.Алгоритм по методу Айверсона предназначен для поиска аргумента К в таблице записей В 1, В 2,.Яч, расположенных в порядке возрастания ключей К) К 2, Ки,Начальная установка= 1, О = К.Нахождение середины, Если О , то(57) Изобретение относится к вычислительной технике. Цел ь изобретения - уп рощение и повышение быстродействия устройства за счет реализации поиска по методу Айверсона. Устройство содержит регистры верхней и нижней границ, три элемента И, блок памяти, две схемы сравнения, три счетчика, регистр ключа, выходной регистр, три группы элементов ИЛИ,четыре элемента ИЛИ, сумматор-вычитатель, регистр стратегии поиска, две группы элементов И, четыре элемента задержки, триггер с соответствующими связями. Устройство наиболее эффективно при поиске в небольших наборах. 1 ил. Корректировка . = +1, переход на 2,Начальная установка= ,Сравнение, Если КК;, то переход на 9.Увеличение . = +1, переход на 7,Сравнение, Если К = Кь то удачный ко-- днец алгоритма, иначе неудачный конец ал-горитма. фПрименение устройства оправдываетсяпри поиске в небольших наборах с числомзаписей 2 - 2 . При М = 2 алгоритмическая1 отрудоемкссть снижается пиша на 11 "укНа чертеже лриеедена структурная ске- , чЛма устройства.Устройство содержит регистр 1 верхней границы, регистр 2 нижней границы, сумматор-вычиттель 3, ремстр 4 стратегии поиска, вычитающийсчетчик 5, суммирующие счетчики 6 и 7, схему 8сравнения, блок 9 памяти, регистр 10 ключа, схему11 сравнения, выходной регистр 12, группы13 - 15 элементов ИЛИ, группы 16, 17 элементов И, элементы ИЛИ 18 - 21, элементы 22 - 25задержки, триггер 26, элементы И 27 - 29, вход30 запуска, вход 31 адреса верхней грани 1711185цы, вход 32 адреса нижней границы, вход 33 кода критерия смены стратегии поиска, вход 34 ключа, выход 35 адреса, выход 36 признака отсутствия информации. Элементы 22 - 25 задержки объединены в распределитель 37 импульса.Устройство начинает работать по методу поиска делением пополам,При поступлении импульса запуска с входа 30 осуществляется запись в регистр 1 кода адреса верхней границы, поступающего с входа 31 через элементы ИЛИ группы 13, в регистр 2 кода адреса нижней границы, поступающего с входа 32 через элементыИЛИ группы 14, в регистр 4 кода критерия смены стратегии поиска, поступающего с входа 33, в регистр 10 кода ключа искомой записи, поступающего с входа 34, и обнуление триггера 26. После записи информация с входов 31 и 32 снимается, Одновременно импульс проходит через элементы ИЛИ 21 и 22, где задерживается на время поступления информации в регистры 1 и 2, и поступает на вход Яь, а через элемент ИЛИ 20 - на вход Ч сумматора-вычитателя 3, разрешая поступление в него уменьшаемого и вычитаемого, Разность поступает на вход схемы 8, где сравнивается с числом 44, поступающим с выхода регистра 4. При условии О -44 дальнейшая работа устройства аналогична, работе известного устройства, Импульс с выхода элемента 22 поступает на элемент 23, где задерживается на время выполнения операций вычитания и сравнения, в сумматор-вычитатель 3 и схему 8, соответственно, поступает на вход ЯМ и через элемент ИЛИ 20 на вход Ч, разрешая поступление слагаемых в сумматор-вычитатель 1. Задержанный на элементе 24 на время выполнения операции суммирования в :умматоре-вычислителе 4, импульс разрешает запись кода с выхода сумматора-вычитателя 3, сдвинутого на один разряд в сторону младшего разряда, в счетчики 5 и 7 и в счетчик б через элементы И группы 16, открытые единичным потенциалом с инверсного выхода триггера 26, и элементы ИЛИ группы 15. Задержанный на элементе 25 на время записи информации в счетчики 5 - 7, импульс поступает на входы С счетчиков 5 и 7, осуществляя уменьшение и увеличение на единицу их содержимого соответственно.Адрес с выхода счетчика б поступает на адресный вход блока 9, где по нему производится выборки записи с ключом, который поступает с выхода блока 9 на схему 11, где сравнивается с ключом искомой записи, поступающим с выхода регистра 10,При этом возможны следующие ситуации,Ключ искомой записи совпадает с ключом считанной записи. Сигнал с выхода"Равно" схемы 11 разрешает запись адресаискомой записи с выхода счетчика 6 в регистр5 12, после чего этот адрес появляется на выходе 35,Ключ искомой записи меньше ключасчитанной записи, Сигнал с выхода "Меньше" схемы 11 поступает через элемент ИЛИ10 18 на вход Ч регистра 1, разрешая запись внего через элементы ИЛИ группы 13 содеркимого с выхода счетчика 5.Ключ искомой записи больше ключа считанной записи, Сигнал с выхода "Больше"15 схемы 11 проходит через элемент И 28,открытый единичным потенциалом с инверсного выхода триггера 26, и поступает черезэлемент ИЛИ 19 на вход Ч регистра 2, разрешая запись в него через элементы ИЛИ20 группы 14 содержимого счетчика 7. Такжесигнал с выходов "Меньше" или "Больше"схемы 11 проходит через элемент ИЛИ 21 ипоступает на распределитель импульсов,состоящий из элементов 22 - 25, При условии25 О -44 появляется сигнал на выходе"Меньше или равно" схемы 8, по которомутриггер 26 устанавливается в единичное состояние. При этом происходит смена стратегии поиска, и устройство начинает30 работать по методу последовательного поиска.При поступлении сигнала с выхода элемента 24 на вход Ч счетчика б в него записывается содержимое регистра 2 через35 элементы И группы 17, открытые единичным потенциалом с прямого выхода триггера 26 и элементы ИЛИ группы 15,При работе схемы 11 в этом режимевозможны следующие ситуации.40 Ключ считанной записи совпадает сключом искомой записи аналогично описанному,Ключ искомой записи больше ключа считанной записи, Сигнал с выхода "Больше"45 схемы 11 проходит через элемент И 27, открытый единичным потенциалом с прямоговыхода триггера 26 и поступает на вход Ссчетчика б, увеличивая его содержимое наединицу.50 Ключ искомой записи меньше ключасчитанной записи. Сигнал с выхода "Меньше" схемы 11 проходит через элемент И 29,открытый единичным потенциалом с прямого выхода триггера 26, на выход 36, сигнали 55 зируя об отсутствии информации с искомымключом,Формула изобретения Устройство для поиска информации, содержащее регистр верхней гра1711185 10 15 20 25 30 35 45 50 55 ницы, информационные входы которого соединены с выходами элементов ИЛИ первой группы, первые входы которых являются входами адреса верхней границы устройства, регистр нижней границы, информационные входы которого соединены с выходами элементов ИЛИ второй группы, первые входы которых являются входами адреса нижней границы устройства, управляющие входы регистров верхней и нижней границ соединены с выходами первого и второго элементов ИЛИ соответственно, первые входы которых объединены и являются входом запуска устройства, выходы регистров верхней и нижней границ подключены к информационным входам сумматора, вторые входы элементов ИЛИ первой и второй групп соединены с выходами первого и второго счетчиков соответственно, информационные входы которых соединены с выходом сумматора, а входы управления записью объединены, блок памяти, вход которого соединен с входом выходного регистра, выход которого является выходом искомой записи устройства, а управляющий вход соединен с выходом "Равно" первой схемы сравнения, первый вход которой соединен с выходом регистра ключа, информационный вход которого является входом ключа устройства, а управляющий вход подключен к входу запуска устройства, выход "Меньше" первой схемы сравнения соединен с первым входом первого элемента И и вторым входом первого элемента ИЛИ, триггер, инверсный выход которого соединен с первым входом второго элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, третий элемент И, четвертый и пятый элементы ИЛИ, распределитель импульсов, первую и вторую группы элементов И, выходы которых соединены с входами элементов ИЛИ третьей группы, о т л и ч а ю щ е е с я тем, что, с целью упрощения и повышения быстродействия, сумматор выполнен с возможностью вычитания, причем выход сумматора-вычитателя соединен с информационными входами первого и второго счетчиков со сдвигом на один разряд в сторону младших разрядов, а первый счетчик выполнен вычитающим, причем в устройство дополнительно введены вторая схема сравнения, третий счетчик и регистр стратегии поиска, информационный вход которого является входом стратегии поиска устройства, вход запуска которого соединен с управляющим входом регистра стратегии поиска,выход которого соединен с первым входом второй схемы сравнения, второй вход которой соединен с выходом сумматора-вычитателя, входы управления сложением и вычитанием которого соединены с первым и вторым входами третьего элемента ИЛИ и с первым и вторым выходами распределителя импульсов, третий и четвертый выходы которого соединены соответственно с входом управления записью первого счетчика и с объединенными синхровходами первого и второго счетчиков, выход третьего счетчика соединен с адресным входом блока памяти,выход которого соединен с вторым входом первой схемы сравнения, выходы "Больше" и "Меньше" которой соединены с первым и вторым входами четвертого элемента ИЛИ, выход которого соединен с входом запуска распределителя импульсов, выход "Больше" первой схемы сравнения соединен с вторыми входами второго и третьего элементов И, первый вход третьего элемента И соединен с прямым выходом триггера, вторым входом первого элемента И и первыми входами элементов И второй группы, вторые входы. которых соединены с выходами регистра нижней границы, выходы сумматора-вычитателя соединены с вторым входом второй схемы сравнения, вторыми входами элементов И первой группывторые входы которых соединены с инверсным выходом триггера, установочный вход которого соединен с выходом второй схемы сравнения,40 вход сброса триггера соединен с входом запуска устройства, выход признака отсутствия информации которого соединен с выходом первого элемента И, выход третьего элемента И соединен с синхровходом третьего счетчика, вход управления записью которого соединен с третьим выходом распределителя импульсов, а информационные входы - с выходами элементов ИЛИ третьей группы, третий вход четвертогоэлемента ИЛИ - с входом запуска устройства.1711185 Составитель В. ЧистобородовРедактор С.Патрушева Техред М.Моргентал Корректор О.Кунд каз 341 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 атент", г. Ужгород, ул.Гагарина, 1 изводственно-издательский комби