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

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

Цель изобретения - повышение быст родействия устройства за счет уменшения количества обращений к блоку памяти для поиска требуемой записи.

На чертеже изображена блок-схема устройства.

Устройство содержит регистр 1 адреса верхней границы, регистр 2 адрса нижней границы,,.сумматор 3, регистр 4 ключа, первую схему 5 сравнния, регистр 6 информации, блок 7 памяти, выходной регистр 8, генератор 9 импульсов, первый элемент ИЛИ 10, первую группу элементов ИЛИ 11, второй и третий элементы ИЛИ 12 и 13 реверсивный счетчик 14, распределитель 15 импульсов, вторую схему 16 сравнения, первый и второй элементы И 17 и 18, вторую группу элементов ИЛИ 19, вход 20 пуска устройства, установочный вход 21 устройства, вход 22 кода ключа устройства, вход 23 адреса верхней границы устройства, вход 24 адреса нижней границы устройства, выход 25 адреса устройства, выход 26 признака устройства.

Позициями 27, 28 и 29 обозначены выходы Равно, Меньше и Больше первой схемы 5 соответственно. Позициями 30 - 33 обозначены первый, второй, третий и четвертый выходы распределителя 15 соответственно.

Каждая запись набора данных состоит из ключа и информационной части. Предполагается, что записи набора данных, находящегося в блоке 7 памяти, отсортированы по возрастанию ключей. Требуется найти адрес записи с заданным ключом. Адрес ячейки (записи), разделяющей набор данных (или оставшуюся часть набора данных, в которой находится искомая запись) на две примерно равные части, называется рубежом.

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

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

установочном входе 21 разрешается запись информации в регистры 4, 1 и 2, в результате чего код-ключа искомой записи заносится в регистр 4, код адреса последней записи в наборе данных через первую группу элементов ИЛИ 11 записывается в регистр 1, а код адреса первой записи в наборе данных через вторую группу злементов ИЛИ 19 - в регистр 2. Будем называть адрес последней записи в наборе данных верхней границей (БГ), а адрес первой записи - нижней границей (НГ).

Поиск записи инициируется подачей импульса по входу 20, в результате чего запускается генератор 9. Импульсы с его выхода через распределитель 15 подаются в различные

точки устройства. Первый импульс появляется на выходе 30 распределителя 15. Этот импульс разрешает запись информации в счетчик 14, в результате чего сумма НГ и ВГ с выходов сумматора 3 со сдвигом на один разряд в сторону младших разрядов заносится в счетчик 14. Этот код является первым (в последующем - очередным рубежом. Таким образом, первый рубеж Р, определяется след5тощим образом:

Р/ L (НГ + ВГ )/2J,

где 1цхД - ближайшее целое, меньшее или равное х. После этого появляется импульс на выходе 31 распределителя 15, по которому запись, определяется рубежом, с выходов блока 7 памяти заносится в регистр 6. Первая схема 5 осуществляет сравнение кода ключа искомой записи, находящегося в регистре 4, с кодом ключа записи, считанной на регистр 6. При этом возможны

следующие ситуации.

Код считанной записи совпадает с искомым кодом ключа. В этом случае появляется сигнал Равно на выходе 27 первой схемы 5, по которому адрес

искомой записи, находящийся в счетчике 14, заносится в регистр 8, а генератор 9 останавливается.

Код считанной записи меньше иско-; мого кода ключа. В этом случае возникает сигнал Меньше на выходе 28 первой схемы 5. Этим сигналом задается суммирующий режим счетчика .14 и открывается первый элемент И 17.

31

Код считанной записи больше искомого кода ключа. Это приводит к появлению сигнала Больше на вьпсоде 29 первой схемы 5, по которому задается вь1читаю1ций режим счетчика 14 и откры- вается второй элемент И 18.

По импульсу на выходе 32 распределителя 15 содержимое счетчика 14 увеличивается или уменьшается на единицу в зависимости ат заданного режима работы.

После этого появляется импульс на выходе 33 распределителя 15, который проходит либо через первый элемент И 17, либо через второй элемент И 18 и стробирует запись информации либо в регистр 2, либо в регистр 1. В результате этого в один из регистров 1 или 2 осуществляется запись кода, сформированного в счетчике 14.

Таким образом, если код ключа считанной из блока 7 записи меньше искомого кода ключа (т.е. в первой половине набора данных искомой записи нет), то 1 первому рубежу прибавляет- ся единица и получившийся код записывается в регистр 2 в качестве нижней границы нового набора данньпс, содержащего искомую запись, если же код ключа считанной из блока 7 записи больше искомого кода ключа (т.е. во второй половине набора данных искомой записи нет), то из первого рубежа вычитается единица и получившийся код записывается в регистр 1 в качестве верхней границы нового набора данных, содержащего искомую за- пис,ь. Следовательно после выборки записи по первому рубежу и анализа ее ключа размер набора данных уменьшается вдвое.

После этого снова появляется импульс на выходе 30 распределителя 15, по которому формируется второй рубеж по тому же правилу,

P,j L(Hr + 8r)/2J,

только одна из Иг или 8Г не равна соответствующему коду при формировании первого рубежа.

В дальнейшем устройство работает аналогично описанному.

Если искомая запись в наборе данных отсутствует, то наступит такой момент, когда ВГ станет меньше НГ (на единицу). Эту ситуацию фиксирзг- ет вторая схема1-16 сравнения, выдавая сигнал на своем выходе, когда

81

j

0

5 0

5 б Q

с

5

0

5

164

содержимое регистра I меньше содержимого регистра 2. Этот сигнал остановит генератор 9 и пройдет на выход 26, чем засвидетельствует отсутствие записи с искомым ключом.

Поспедукяцие обращения к найденной записи могут быть реализованы путем установки устройства в исходное состояние и загрузки в регистры 1 и 2 адреса этой записи, а в регистр 4 - ее ключа. После этого на вход 20 подается импульс, по которому на регистр 6 будет считана требуемая запись, а генератор 9 импульсов остановится.

За счет реализации в предлагаемом устройстве другого принципа формирования рубежа на количество записей в наборе данных не накладывается никаких ограничений. Следовательно для обеспечения работы устройства нет необходимости искусственно увеличивать количество записей. Реальное число записей в этом случае совпадает с фактическим числом записей Это ведет к более экономному расходу памяти и к уменьшению количества обращений к блоку памяти дЛя поиска требуемой записи.

Таким образом, применение изобретения позволяет повысить быстродей- ствие устройства и сократить аппаратурные затраты.

Формула изобрет ения

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

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

10

15

20

5

0

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

гг

ВНИИПИ Заказ 2288/50

Тираж 671

Подписное

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4

Тираж 671

Подписное

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