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

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

Целью изобретения является повыте 1-ше бь строде11:ствия устройства,

Иа чертеке приведена схема предлагаемого устройства.

Устройство содержит регистр 1 нти ней 1чэаниц1г1, регистр 2 верхней гра- ницЫ; регистр 3 ключа, регистр 4 информации , ззыкодной регистр З, сумматор 6, гp,пы 7 л о элементов ИЛИ, элементы Iti M 9- П злементь; И 2 и 13, генератор 14 тактовых импульсов, распределитель 5 импульсов, (5лок 16 памяти, е.хемъ 17 и 18 сравнения, ечетчики 19 и 20, регистр 2 адреса, нход 22 адреса нижйей , вход 23 адреса верхней границы, зход 24 ключа, вгод 25 запуска, вход 26 разрешения начальной заниси, адресный 27 Бмход, Быкод, 28 признака отсутствия инфорьгации., выходы 29-37 Рав-мо, . Менъ ле и Больше схемы 18 соответственно, нервы;- 32, 33 и тре- TKii 34 Еыход л распределителя 15.

Каждая запись набора данных сос-- топт из ключа и-информад1-:ог1ной части .Иредглолагается,, записи набора, , на ходяцихся в блоке 16 ти, отсортировал Ь JTO ззозрастанию клю чег;, реиуется найти адрес заниси с заданным KJIIOHOM,- Адрес ячейки (записи), разделяющей набор данных (или оставшуюся часть набора данных, в КОТОРОЙ находится искомая запись) па две примерно равные частм называется рубежом,

Устройс.тпо работае г С1теду ОЕ1им образ ,. .

В исходном состояил-нт 19 и 20 If, регистр 5 оСягулень, генератор 14 заторможен, а рг1енреде,литель 5 устаног з. лвн в искоддюе состояние (со- ответс евуюшт-;е иепи на схеме пе пока- зан.Ел) , Па входы 22-24 подаются коды

адреса первой заниси в наборе данных а, 1,реса последней заннсп в наборе дан гшх- и к:гюча искомой заниси соответственно. По импульсу на входе 26 разрешается запись ииформадии в регистры 1-3, 13 результал е чег о код адре.са первой записи в наборе данных через группу 7 элементов HJn-I заносится в регистр -1, код адреса последней записи в нггборе данньпс через групну 8 элементов ИГШ записывается в регистр

5

2, а код ключа искомой записи - в регистр 3. После этого коды с входов 22-24 снимаются о Будем называть адрес первой записи в наборе данных пи:-кией границей (FT) , а адрес последней заниси - верх1 ей гранидей (ВГ).

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

Первый импульс появхшется на. выходе 32 распределителя 15. Этот им0

пульс разрешает зг.писъ информации в счет -гкки 19 и 20 Р: регистр 21, Б результате чего ИГ и ВГ с выходов сумматора 6 сс сдвигом на один в стороку - ладтих разрядов заносится .Б эти уз.лы. Этот код является первым (в поспедуюгдем - очереднь м) рубежом. I

После .этого поя.аляется 1мпульс на 5 в. 33 раСпределгггеля 15j по которому содержимое сч етчика 19 увеличивается на единицу, а счетчика 20-- у еньп1ается на .еди;-п.-1;пуо Кроме то.го, запись, определяе -1ая рубежом, с вы- 0 ходов блока 16 памяти заноситс.я в регистр 4. Схема 13 осуп ествляет сравнение кода .ключа искомой записи, находящегося .в регистре 3, с кодом ключа записи, считаниюй на регистр 4. llpii этом зозмолснь следуюпре ситуа- ц ли:

ключ считанной записи совпадает с ключом искомой записи. В этом случае появляется сигнал Равно па вы- Q ходе 29 схемы 18, по которому адрес искомой записи, на:;:одящийс.я в регнст- -ре 21 ,, заносится в регистр 5, а ге- ператор 4 останавливается;

ключ считанной гзаписи меньше клю- ia искомой записис К этом случае во.з5

5

0

пикает сигнал Меньше на вьп-соде 30 схемы 18. Этим сигналом открывается элемент Н 12 5

ключ считанной записи больше ключа искомой записи. Это приводит к появлению сигнала Больше на выходе 31 схемы 18,, по котором открывается элемент .И 13,

г После этого пояБляется импульс на выходе 34 распределителя 5э которьш iipoxo r,ит либо через элемент И 12, либо через элемент К 13 и разрешает запись кнформац11И либо в регистр 1 из

счетчика 19, либо в регистр 2 из счетчика 20,

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

После этого снова появляется импульс на выходе 32 распределителя 15 по которому 3 счетчики 19 и 20 и регистр 2 запис1-лвается второй рубеж, сформировапный. по же HpaBKjtj , только одна из НГ пли ВГ не равна соответствующему коду при формпроватпп nepBoi o рубежа.

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

Если искомая запись в наборе данных отсутствует, то наступает тако1 момент, когда ВГ С1 анет на едишпту меньше ИГ, Эту ситуадию фикс11рует схема 17, вьщазая сигнал на своем выходе, содерл.имое регистра 2 меньше содержимого регистра 1, Этот сигнал останаз;аивает генератор 14 и проходит на выход 28, чем засвидетельствует отсутствие записи с искомым ключом.

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

После этого па в::од 25 подается импульс, по которому на регистр 4 будет считала требуемая запись, а генератор 14 останавливается.

Форм у л а изо

р е т е

JJ JJ 55 третий }5ь;ход р:-:с :ред,ол.ителя иг.иту.чьУстройство для поиска. 1П1формадин, содержащее ре истр ншкней граннг.ы, регистр верхней границы, регистр

O

5

0

5

ключа регистр информации, выходной регистр, сумматор, две группы элементов 1Ш11, три элемента ПЛИ, два элемента И, roiiepai op тактовых импульсов , распределитель импульсов, б:ток памяти, две схемы сравнения и перБый счетчик, выходы разрядов которого соединены с первыми вхо/дами элементов ИЛИ первой групны, вторые входы которых являются входом адреса нихлгей границы устройства, выходы элеме1ггов МЛН первой групны соединены с информационным входом регистра нижней границы, выход которого соедплел с первыми входами пер- ;зо;: схемы спаБненил и сумг.5атора, вы- . -;од, K.oTopoi o сосд.н.чоп с иг.тформацион- ным входом первого счетчика, такто- Ebii i вход icoTopoi o соединен с первым выходом распрсдел.ителя импульсов, KOTopoi o соедгпюн с выходом генератора тактовых п illyльcoв, вход запуска тсот орого является входом запуска устройства. вход адреса верх- Hci; границы которого соедияен с пер- входа:; . эле:.;ентов второй групны, выходы которых соедпь ены с информан,ион1;ым входом регистра верхней границы, выходн которого соединен с вторыми входами сумматора и первой с лемы сравпслшя, выход которой соединен с выходом признака отсутствия пнформацрл устройства и с первым входом первого элемента ШИ, выход которого соединен со входом останова . генератора тактог-ых 1 мпульсов, второй выход распределителя импульсов соединен с входом записи регистра информацип, выход которого соедннеп с перным входом второй схемы сравнения, второй вход которой соединен с .выходом регистра ключа, информационны вход которого является входом ключа устройства, вход разрешения на- .чальпой заниси которого соед1Н1ен с первыми входа и второго и третьего элементов ИЛИ и с входом записи регистра ключа, 1.;формационный вход ре- гнстра инфор ;;гции соедпне с выходом памяти, п;:рес1;1чй вход которого соединен с 11П ;)ор:-5ацнонньм входом вы- ходн ого рог-астра, выход которого является а;;рес;-1Ь:.: БЫХО.ОМ ycTpoi lcTBa,

0

5

0

0

Сов ссе;.;,инен с первыми входягг-;и пер- -Бох о и 1- тсрсго элементов И, выход Равпо второй схемы сравлепия соединен с входом :: а;:псп выходного регист512

pa и вторым входом первого элемента ИЛИ, выход Меньше второй схемы сравнения соединен с вторым входом первого элемента И, выход которого соединен с вторым входом второго эле- мента ИЛИ, выходпкоторого соединен с входом записи регистра игекней грани

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

го ;элемента И, выход которого соеди- fO первого счетчика и вычитающий

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

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

первого счетчика и вычитающий

вход )зторого счетчика соедд5нены с вторым выходом распределителя импульсов, первый вьпшд которого соединен с входами записи регистра адреса и второго счетчика.

23

t

26

Редактор Г.Волкова

Составитель А.Жеренов Техред Л.Кравчук

Заказ 6841/49

Тираж 671Подписное

ВНИКЛИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Корректор 0.Луговая