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

 

СОЮЗ СОВЕТСНИН

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УЬЛИ К

Al (бц 4 G 06 Г 15/40 с с ч3

13, ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3943378/24-24 (22) 30.04.85 (46) 23.12,86. Бюл. Р 47 (72) Б.С.Богумирский, В.Я,Яцук и В.А.Палагушин (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1126972, кл. С 06 Г 15/40, 1983.

Авторское свидетельство СССР

Р 1228116, кл. G 06 Р. 15/40, 1984, (54) УСТРОЙСТВО ДЛЯ ПОИСКА HIMOPNAЦИИ

„SU„, 12788 с (57) Изобретение относится к вычислительной технике. Целью изобретения является повьппение быстродействпя устройства. Устройство содержит регистр нижней границы, регистр верхней границы, регистр ключа, регистр ин<)ормации, выходной регистр, сумматор, две группы элементов ИЛИ, три элемента ИЛИ, два элемента И, генератор тактовых импульсов, распределитель импульсов,, блок памяти, две схемы сравнения, два счетчика и регистр адреса. 1 ил.

1278891

ИЭ ОбрЕТQЕ)ие ОТНО(1 - ТС. Я E(БЫтпт Гти-"

ТЕЛЬПОЙ ТЕХНИКЕ и МО .";=Т I>!!TE> ЦСПОЧЬ зовано и системах уп1)ЯГзле((ия! базами дян.гы- .

11(н()ы0 II(30()»!QTQETHE! E(BHI IQTcH 1(От??»шение Li()(cTjзОДсйстниЯ ) с".тгойства .

1>а чс)зт>з f Q пpHB едена. Схет(«1 пре«д лягаемого устройства, Устройство содержь(т регистр 1 TDI(ней 1 »ани;зы -эсгис гр 2 не(эх!лей границы, регистр 3 ?(3>по)л(1,, i егнстр 4 ин())op <(««LUIH I )зыхОД? ?ОЙ 1) P »истр 5 > сумма тор 6, группы 7 11 " элементов ИЛИ» элемс".н>.ы 11.(И 9-.11, -.-лei(Q!rты И 12 и

13, генератор 14 !.актовых (л((пульсон, 1) ": (> IT) Q«I?QJIII!ЗQJIB 1 5 (Т !! r !ТII,C ОИ ) ()Holr 1 6

I!a(«f1т 1 тт» Х«е)мы j 7 т-. 1 8 ())а)н)?Ген?(я» г.т(1«пт Н 19 I «0 О> т>т (О ? (,3 ГОЕГ н"„-„оц 2„,, ЯТ?,)Q(а и;„-.;.;Б(пг ; г»;1(И :.. j, B)(0!r

23! H;!»Qc,а 1)е»хнец (; >Clif 111! (»-.",.c;I; 224 к 1(0?«т B)IОд 25 3 а(! уска» >)ход 26 !) Яз

pQ! iQ, (тт 1(ач г) !IJ) I) L>!:. з >3?(т г н:) > )э еcr(r)f(r

27 ны о.т, I)ь(.:о. 28 пр((!! II ка. Oтсутст» в!(Я пн(1)oj)r! а: т!EI » ?1(>!-:,of,i! 2 .!--3 / .;-,1?>)(О, )ег()-)J(!) j! )),»11>J: Q (="Q! .f>1 1 i) г (эo гт)ет.

С"! Ijт >!(!O Iiрr)B),(;"! 32 )! 0-1 !i 33 И Тт)аTr,;! ), >., НЬТЗ 0)гт >f ) а;„ ! )P>10 >„"H Q!тя . ), К«);е(:т 111 -> э1 lл("3) II 0 бо (эа;! «IEIiI!ë ГО с"

:(O((т,(э К!Нот(", Ef Ит(г„О!1! ТЯE!!(O! (310((ЧС(C Tlf ° .0

1jpQ1fH0Jrr1ã (! P TC i „-.I I 0;>И(1- !* (табора

Д;1:,Г-Пг>!! . HP.); (Э-(u, )> (" Я ?, O!Ol«=

Ти 0 Г 0?ЗТИ!Э! >Н(1,r!)i !i«0 130 ))а C .Т«;Ei!130 К 1(0 ,I .UQL)";. Q гг Я н«1(лтп;,,Т!» 30:-3 QIIHCEI

ЗЯДЯТ(Т ЫМ Ir)ПОЧРМ,,Г(Д) ЕГ ЯЧ«>! L>)HI((3 ЯПП си g» )! ЯЗДелЯ(оп c! ) Паб О1) Д "!Ii.".1)!r (r! Jl!i

Ос ?и!.гri! )т?З((я ча()"I) (, 1i (, 1;1 1 та(!"!!. » ?3 T(o

ТО»011 IIHХОДЦТС. ((ЛС)СО()?0(Я ":ЯП(IСТ>)

Д)зг ПРИМЕРПО Ра)ПППЕ ЧЯСТН, ПЯЗЬ!Наетс«(!зуб е)ком.

) ((»0(3? Tно »!)ботас (cJror-(y(0(ir! 0,«-1)ЯЗ ОМ.

Б ИСХОДНО СОСтОЯПИП СЧ(30 ИК(И ) 9 и 20 и. рсгистр 5 о(>нуле!(ы,, г!.-:QpaTop

1 . -3 «l » Ормо к««31! .,,"1 р L(HpQÄ(!IH ("IB 1 > устано:зпеп н исход..ое сос.. o".«(IC. (Со0 J 13Qò(,!" 1)У(0(ТТЛ " ПОП((Н«1 ()СЕ;.fQ IQ IT(«?(«О зан(13. Па н QJJ()j ?2-24 пода(отся коды адреса первой з!HJ(cli B I(«uopQ данных, ад))Оса JiccJIQдпей записи г наборе Дан. 30

ПЫХ И КЛIОЧЯ. ИСI(омой ЗCLIIHCIf Coo CBQT стне((по. По 1(ь(Г(ульсу па входе 26 разрешается запись ипфор((ации н регистры 1-.-3. 13 pQBóJII>òo.TQ .QI î код адреса >(ергой записи н наборе данных через группу J элементов Т))П) заносится

B регистр 1, код адреса последней записк н наборе данньн.- через группу 8 элементов ИП)1 эаписыгзается н реги(.тр

2, а E(oJJ ключа искомой записи — в регистр 3. После этого коды с входов

)7 72! cf(HMB(0Tcij. Fуде(л называть Яд» с пер?зой;a!Iиси н ."?!)боре ззанных п(л.к((ей гг)а!(и?ей (1 Г) ) а адрес последIlPli записп — герх(ей границей (ВГ}.

Поиск записи Н! Ициируется подачей

11:(пульса по входу 25, и результате !

1егО 3 Яп т скЯется гсчсpQTop 1 4 . Импульсы с его выхода через распредеJTHTQJ!(ь 1 пОДЯются Б разл3г(1(ь(6 . тОч

КИ У> С1 PÎHCTBЯ )

Первый импульс поянляется HLI выходе 32 расп)0еделитег(я 15. Этот имHупьс: разрешает "-гнись информацизл н

crIQ T1;E(?пз ) 9 !: 20 т. реп ((стр 2 ), .-, результ":.T=. чего су(н:а ПГ и ВГ с выходов сум (атор(- 6 сс сдв. -(гом на opEIIE наэр" r н стгз()он(> :..i !ппlх ()яз )ядов заь О сит(я н этц ))злы. Э > от код явля;.тСЯ ПЕР?3??М (Н Г>ОСПЕДУЮПТЕЬ(— ОЧЕРЕД(3(.(м) руб ен(ом « !

После этого по?1:.?л3(с:тс?(".-. fI(ульс на н)>(хоДе 33 рЯспределlгтеля 1 э, 110 ко opoJIy соде)з«)пимое =)(с?"Чик (1 9

"-(?I 13 «0. QT c EJ !Io. ед)(л:-.(Иц.>т, G c чет (нк а 2 0

УМЕI(ЬП(«ЯP TC J: Er«L Q, H:-((СП(?У ° j«PO: (Е ТОГО» за?(нcь» определ".Qÿ:)Ef рубе?Хом с ныходон блока 6 памяти заносится в регистр 4. Схема 18 осу(?.естнляет

СРЯННЕНИЕ КОДа К;Т(0)IЯ HCКОМОй ЗЯПИСИ, паходящегocfl н регистре 3» с кодом кл?Оча записи, счита(п(ой на регистр

При этом нозмоэ)(?(ь(сле,ту(оп(не ситуаJ

1 J!!011 С ИТ lHIi:Ой (3ЯПИСИ COБПЯДЯЕТ

КЧ,О,(О„ИСКО "!0! ((П>I! 8 3 TO))f

rIDQ ПОЯТ3ттЯЕ) r ?(CH!т Ттc. Ч. «Ят) 0 1>Я. БЬ(» Т)

:;-opQ 2)9 c«",QIп,(! 8, т r) ксторо(лу адрес

ИСКО:Oir .)аПИСИ и 3 a;1JjfJ(EJ IC?j .З PQBHCTрс. 21, заносится н pQ-:."Hcòð 5, а. г"Q—

fICpfETop 1 4 О T«)EIQB!II(I)«)QTCE(.

1;ХПОтl СЧИТЯIПIОЙ: 3«!HHCH,JCI(br!JQ КЛ10Ча J!C (ОМой 3R IИСИ«)) ЭТОМ СГ! ТТ(ЯЕ НОЭ (п(к((ст с((гнал "Мен?ЗГ Q" на ньг.,оде 30 схемь()8. Зтим сиг(?апо r открывается элемент И 12; ключ с (птанной записи бс)л)ыпе кчюч";:искомой записи. Зто приводит к поя )Hpf(EI;0 сигнала Бол 3?JQ Е!а выходе

II II

31 схеь(31 )8» по которому открывается элемент И 13.

После этсго появляется импульс на нь()(оде 34 распредессителя 15, который (роходит II(GO через элемент И 2 ли-. бо через элемент И 13 и paspQJ1faQT запись (лп(1)ор(лацци либо в регистр 1 из

1278891 счетчика 19 либо В регистр 2 из счетчика 20.

Таким Образо:i, если кад кл:оча записи, считанно1! из блока 15, 7!алыче кода ключа и" камой записи {т. е. 13 первой палов;и;.е набора дан?п?х искомой записи нет,1, та первый рубеж, увеличенный на единицу, записывается

В регистр 1 В качестве нижней границы нового набора данных, содержащего искомую запись; если кад ключа считанной из блока 16 записи больше искомого када кзпоча {т.е, во второй половине набора данных искомой записи нет, 3, то первый рубек, уменьше . .".,7й на eд1!«п! !У..За??ис)113(!е:i ся В «Зе«-;« - rp 2 в качестве Верхней грани!?ы навагo набора данных, содеряащегo искомую запись. Слс?;Оватсльно, после Выборки за?п?сп Ito первому рубежу и анализа 20 ее ключа раз tep пабара данны:-. Уменьшается Вдвое.

После этого снова ноя1зляется лмпульс на Выходе 32 распределптел!! 15, по которому Е3 счет ш,н 19 и 20 11 регистр 2! заш?сывается Второй рубеж, сформированный по таму же правилу, толь?(о одна из 1П" 173-и 31 не равна соотвстст?зу?още? J коду при формирова«пп!

3(3 первого рубежа.

Б даль??ейше?и устройство работает аналоги п?о аписанно:1у вьш?е.

Если искомая запись в наборе Данных отсутствует, -о наступает такой момент, когда 131 (. ане! на е71«173!В«Зэ меньше 111") Эту ситуацию фиксирует ! 7, E3,. t 13Q!t CI )e!?ал на выходе, когда са:ep..-;имое рег«!стра 2 меньше содер;?(!!могo регистра 1, Зтот сигнал астана.-л;ш«за(зт гeltepaòàp 14 и проходит на выход 28, чем зас?зидетельствует отсутствие записи с иско-мым ключом.

Последу!ощие обращсния к наиценной записи могут быть реализованы путем установки устройства В исхо..l--ное состояние и загрузки Зз регl! .:)ры

1 и 2 адреса этой записи, а. L pe гистр 3 — ее кзпоча, После этого на 73;.од 25 падается импульс, по которому на регистр будет считана требуемая запись, а генератор 14 останавливается.

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

Устройство для поиска и1«(13013ма!?ии, содержащее ре -истр I?tr:.ней грашп ы, регистр Верхней границы, регистр ключа, регистр 1!ВАар !17!j!111, Выходной регистр, сумматор, 31ь«е гру?7пы эле7!В1!тоВ 1«1?И, т1«н элемента ИЗП1, Два элемента И. j 03 ep!3",ор тактовых имl!УльсОВ p !clip(-j e«!è3 ÃI!b импульсов

6?1(;1(памяти, д?зе схемы cpa!3! teu:-.;! и !top» :. ;t с«!ет ?ик, Выходы разрядов которого соединены с первыми

Входами элементов ИЛИ первой группы, В то?111е Входы I(o ropbl?: яВля!отся Вхацам адр с-с а III!3!:I?eй 1 ра ннцы p ст13011ст13а у

Выходы элементов 1ПИ первой группы сас!!1!!? сны с ш?формационным входом регистра 1?няней грашзцы, выход кото7 Oi O )."ОСЦ. П) С 1 С !to PL«!.: !11 !3:?ОД .И«17(P

)1 : CХ(. ! (i! 11« i!--l!! ii! 1! СУ ?!7 !аl OP à ) ВЫ ." .Оттoроi О сс(., !!!!!с!! с !1!?формаL!!10ï

lib! 173?Ода?! перваl" 0 счстчикаi таl та

В:7!) Вхс«д которого соединен с пер!Зым

Выходам р!?сп13ед=пита?1,1 импульсов, El1toä ка орагo со(д шеп с выходом генератор» тактовых-.. пульсов, вход за!"., c..,,! 7;, l 01«1 0 я133lяет(я ВХОдам 3 а» усi(e устрой тла. 1!?;O» адреса верхгр(7н?!Дь? к гc"10 о со. дннен с перВ!. .1! В:,o ., 7 .1! э:1=".:сн ов !IПИ второй г р у!! и н, Б ы х а!?ьl к а т 0 р 1з1х соединены с

I!1?. 1 эр:.В?:,1!Он?)ь?3! входам регистра ВРрхно;! гршшць! Выход кото )Îга соединен с ?зторым?t Вхадамп сумматора И первой схемы ср;.В?3(«!1?-я, Выход которой сое, инен с выха)»01! признака отсутствия ш фармацни уc rрайства н с пер1«ым Входом itepL«ol o 03?Вмента ИПИ, Выход 1(ото!ага с(!(.;;ин В са Входам астапова

I ге??ср;п ар а т 11(т.:ых 117 !!7уз?ьссв, 13 t 0р oi! ?37?х«д !1 ас рсдс пlтс?711 и?!11ут)!Ьcoв

c(сд7731сн с г:.-О)-,д эап icè регистра ш.« ;ар??;?ц;?н, В . Хад котсрага соединен! с:?с .-Ым Входам второй схемы сравнения. Второй «хад которой соединен с

?зыходам регистра кп!оча, информацио .— ньп вха каторога является входом ключа устройства, вход разрешения начальпай записи которого соединен с нср?зыми Eiêo?I(cò гтор(>га и третьего эл=-.?!е!и ав И.!И и с 1зхадом записи рег«lстра !.л?о«?11, !3!?фар??ацион!?Ый! 1зхад регilc. ра ин«1?орз?;!Д?п! Саед«3неп с 1..ь7ходо3! бл ;:;.. 1?ам: т«1,, 1-е(1,:1; Вход "oropoão саад?п сп с ш?1:op:!a!!!ic!?г?!)1?! 1зхадам L«btх)1Д17О! О Pet" i(rr17а ) lзыхОД 1(OTQPOI 0 Я13

Л!1 (ЗТ(Я (3„!P C(1))!)!?! 1, В(ОДО. .! ; C1PO!!(ЗТ13 а тр(-.т!!й Выход 1! .. .ñ::1! å,t,eE!ïòå?iit и1!пуз?ь—

coL3 ссe»),.t.?е!! с пер?31:::;;1 !зхада?7!! пер.вого;1 Втор-I o элеме пав И, гыход

Э т Г)-Впа второй схeME)1 сре.ç?!e!13!1! соедин(-н с L«3(ogc!i: 1 пс?1 1)ыхр на o э ) 1 ("т1278891

Составитель А.Жеренов

Техред ..Кравчук

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

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

Заказ 6841/49

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

ВНИ1П1И Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

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