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

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