SU1686464A1 - Устройство дл поиска информации - Google Patents

Description

1

(21)4763772/24 (22)28 11.89 (16)23.10.91. Бюл. МеЗЭ

(71)Киевский политехнический институт им.50-лети  Великой Окт брьской социалистической революции

(72)Е.Бардис(СР), В.И.Корнейчук,

А.П.Марковский и Ю.Н.Чубатюк (SU) (53)681.3(088.8)

(54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ

(57) Изобретение относитс  к вычислительной технике и может быть использовано дл  реализации доступа к информации как по ее

адресу, так и по содержимому. Целью изобретени   вл етс  повышение быстродействи . Устройство содержит группу блоков 1 1-1.М пам ти, группу элементов НЕРАВНОЗНАЧНОСТЬ 3.1 З.М, регистр 4 признака опроса, группу элементов ИЛИ 5.1-5.М, регистр 6, шифратор 7, элементы И 9, 11, элементы НЕ 10, 29, элементы ИЛИ 12. 31. формирователь 13 импульсов, счетчики 15, 28 адреса, делитель 18 частоты, элемент 19 задержки, группу сдвиговых регистров 21.1-21.К. группу коммутаторов 23.1-23.М, элемент ИЛИ-НЕ 27. схему 36 сравнени , Поставленна  цель достигаетс  введением новых элементов и св зей. 2 ил.

,221

г тггпт

Иг

4-1

в

ON 00 О Јь О

Јь

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

Целью изобретени   вл етс  повышение быстродействи .

На фиг. 1 представлена функциональна  схема устройства; на фиг. 2 - временные диаграммы работы устройства в режиме поиска .

Устройство содержит группу блоков 1.1-1.М пам ти, информационный выход 2 устройства, группу элементов 3.1-З.М НЕРАВНОЗНАЧНОСТЬ , регистр 4 признака опроса, группу элементов ИЛИ 5.1-5.М, регистр 6, шифратор 7, выход 8 младших разр дов адреса устройства, элемент И 9, элемент НЕ 10, элемент И 11, элемент ИЛИ 12, формирователь 13 импульсов, выход 14 формировател  импульсов, счетчик 15 адреса , выход 16 признака обнаружени  информации устройства, выход 17 делител  18 частоты, элемент 19 задержки, вход 20 синхроимпульсов устройства, группу сдвиговых регистров 21.1-21.К, группу входов 22.1-22.L начального состо ни  устройства, группу коммутаторов 23.1-23.М адреса, вход 24 младших разр дов адреса устройства , вход 25 задани  режима функционировани  устройства, вход 26 запуска устройства, элемент ИЛИ-НЕ 27, счетчик 28 адреса, элемент НЕ 29, информационный вход 30 устройства, элемент ИЛИ 31, вход 32 инициации обращени  к пам ти устройства , вход 33 записи-чтени  устройства, вход 34 и выход 35 старших разр дов адреса устройства, схема 36 сравнени , вход 37 требуемого признака поиска устройства, выход 38 индикации окончани  работы, вход 39 номера зоны поиска устройства, М - разр дность данных, L log2M.

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

Информационные М-разр дные слова записаны в одноименных  чейках блоков 1.1-1.М по одному разр ду слова в каждом блоке 1.

В режиме адресного чтени  (записи) младшие L разр дов адреса (L log2M) подаютс  на вход 24 устройства, а старшие разр ды адреса - на вход 34. При этом единичный сигнал подаетс  на вход 25 устройства . Под действием указанного сигнала на выходах всех коммутаторов 23 формируютс  коды, идентичные коду на входе 24, которые поступают на младшие разр ды адресных входов всех блоков 1. Одновременно сигнал с входа 25 проходит через элемент ИЛИ-НЕ 27 в инверсном представлении инициирует прием кода с входов 34

на счетчик 28, с выходов которого код старших разр дов адреса поступает на старшие разр ды адресных входов всех блоков 1. Одновременно на вход 32 подаетс  единичный сигнал, который, пройд  через элемент ИЛИ 31. инициирует работу блоков 1.

При чтении по нулевому сигналу, подаваемому на вход 33. блоками 1 осуществл етс  операци  считывани  М-разр дного

0 информационного слова на выход 2 устройства .

При записи по единичному сигналу, подаваемому на вход 33, блоками 1 осуществл етс  операци  записи по адресу

5 М-разр дного информационного слова, подаваемого на вход 30 устройства.

В режиме поиска информации М-раз- р дный код признака опроса подаетс  на вход 37, на вход 34 подаетс  код номера

0 зоны Z в пам ти, с которой осуществл етс  поиск (предполагаетс , что весь объем пам ти разбит на зоны М слов в каждой), на вход 39 подаетс  код номера зоны, до которой осуществл етс  поиск, на вход 33 пода5 етс  нулевой сигнал, на вход 20 - сери  тактовых импульсов, на вход 26 - сигнал начала работы в режиме поиска. Динамика работы устройства в режиме поиска по сн етс  временными диаграммами на фиг. 2.

0Поступающа  на вход 20 последовательность тактовых сигналов (фиг. 2), которые задерживаютс  элементом 19 задержки, поступает на вход делител  18 частоты. На выходе последнего формируют5 с  импульсы внутренней синхронизации, частота которых вдвое меньше частоты импульсов на входе 20 и фронт которых сдвинут относительно импульсов на входе 20 (фиг. 2).

0 Сигнал начала работы, пройд  через элемент ИЛИ-НЕ 27. инициирует занесение кода с входа 34 на счетчик 28, с разр дных выходов которого упом нутый код номера зоны Z поступает на адресные входы (стар5 шие разр ды) всех блоков 1. Кроме того, сигнал управлени  началом работы, пройд  через элемент ИЛИ 12, поступает на вход формировател  13, формирующего на свопм выходе 14 сигнал запуска (фиг. 2), который.

0 поступа  на управл ющий вход счетчика 15, устанавливает все его разр ды в нуль, поступа  через элемент НЕ 29 на вход регистра 6, устанавливает все его разр ды в нуль, поступа  на управл ющие входы всех сдви5 говых регистров 21, инициирует прием кода на регистры 21с соответствующих входов 22. При этом в регистр 21.1 заноситс  код 010101.. 01. в регистр 21.2 - код 00110011...0011, в регистр 21.3 - код 0000111 ч ...00001111 и т.д. Соответственно с

выходов первых (старших) разр дов регистров 21 на вход коммутатора 23.1 снимаетс  код 00...О, с выходов вторых разр дов регистров 21 на вход коммутатора 23.2 снимаетс  код 00...01, с выходов К-х разр дов (К --1, М) регистров 21 на вход коммутатора 23. К снимаетс  код К-1. Упом нутые коды с входов коммутаторов 23 под действием нулевого сигнала на входе 25 коммутируютс  на их выходы и далее на младшие разр ды адресных входов соответствующих блоков 1 пам ти . Соответственно в первом блоке 1.1 пам ти адресуетс  Z-   чейка, во втором блоке 1.2 пам ти - (2Н)-   чейка, в К-м блоке 1.К пам ти - (Z+K-1)-a  чейка. Соответственно с выхода каждого k-го блока 1.К пам ти считываетс  К-й разр д (Z+K-1)-ro слова. Считывание производитс  по поступлении на вход 20 внешнего тактового импульса , который через элемент ИЛИ 31 подаетс  на управл ющие входы выборки всех блоков 1 пам ти.

На К-м элементе З.К НЕРАВНОЗНАЧНОСТЬ выполн етс  сравнение К-го разр да ()-ro слова с К-м разр дом признака опроса. В случае несовпадени  указанных битов на выходе элемента З.К НЕРАВНОЗНАЧНОСТЬ формируетс  единичный сигнал , который через элемент ИЛИ 5.К поступает на установочный вход К-го разр да регистра бис приходом тактового импульса с входа 20 (фиг. 2) К-й разр д регистра б устанавливаетс  в единицу, тем самым (Z+K-1)-e слово исключаетс  из дальнейшего процесса поиска. Операци  приема кода производитс  на регистре б при наличии импульса внутренней тактовой последовательности с выхода 17 делител  18. С приходом на вход 20 следующего тактового сигнала (при отсутствии импульса внутренней тактовой последовательности на выходе 17 и, следовательно, на управл ющем входе регистра 6) выполн етс  циклический сдвиг влево (в сторону старших разр дов) содержимого регистра 6. С приходом положительного фронта импульса с выхода 17 производитс  прибавление единицы к содержимому счетчика 15 адреса и циклический сдвиг влево содержимого всех регистров 21. С разр дных выходов одноименных разр дов регистров 21 на входы коммутаторов 23.1-23.М выдаютс  соответственно коды 1, 2, 3 М, 0, которые

коммутируютс  на младшие разр ды адресных входов соответствующих блоков 1,1- 1 .М пам ти. С выхода каждого К-го блока 1 .К пам ти считываетс  k-й разр д(г+(К)тодМ)- го слова, который сравниваетс  с К-м разр дом признака опроса элементом З.К НЕРАВНОЗНАЧНОСТЬ. Единичный сигнал

несовпадени  с выхода элемента 3 К НЕРАВНОЗНАЧНОСТЬ через элемент ИЛИ 5 К группы с приходом положительного фронта внешнего тактового импульса устанэвпива- 5 ет в единицу к и разр д регистра 6, исключа  тем самым (Zt(K)mndM)-e слово из процесса дальнейшего сравнени .

Затем вновь с поступлением тактового сигнала по входу 20 выполн етс  цикличе- 0 ский сдвиг регистра б. с поступлением сигнала на выходе 17 производитс  циклический сдвиг содержимого регистров 21, увеличение на единицу содержимого счетчика 15, и описанный цикл поразр дно5 го сравнени  повтор етс .

В общем случае на l-м цикле поиска (.М}) сравнени  с разр дных выходов регистров 21 на входы коммутаторов 23.1-23.М выдаютс  коды,

0 соответственно равные (l+M-1)modM. которые коммутируютс  на младшие разр ды адресных входов соответствующих блоков 1.1-1.М пам ти. С выхода каждого К-го блока 1.К пам ти считываетс  К-й разр д (Zt

5 K-2+l)mod М)-го слова, который сравниваетс  с К-м разр дом признака опроса с регистра 4 на элементе З.К НЕРАВНОЗНАЧНОСТЬ, при этом сигнал несовпадени , пройд  через элемент ИЛИ 5.К, устанавливает в едини0 цу К-й разр д регистра б, исключа  тем самым (Z fk -2tl)modM)-e слово из процесса дальнейшего сравнени , так как вне зависимости от совпадени  исключаемого слова в остальных разр дах с признаком опроса единица в раз5 р де регистра б, соответствующем (Z+(k - -2+l)modM)-My слову, перезаписываетс  с выхода соответствующего разр да регистра 6 через элемент ИЛИ 5.К при каждой операции записи в регистре 6.

0Если все слова в зоне с адресами от Z-ro

до р+М-1)-й на l-м цикле сравнени  окажутс  исключенными (т.е. все разр ды регистра 6 окажутс  установленными в единицу), то единичный сигнал формируетс  на выходе

5 элемента И 9 и этим сигналом инициируетс  переход к новой зоне: сигнал увеличивает на единицу содержимое счетчика 28, обеспечива  переход к (Z+1)-u зоне, пройд  далее через элемент ИЛИ 12, поступает на

0 вход формировател  13 импульса запуска, которым устанавливаютс  в нуль все разр ды регистра 6 и счетчика 15. устанавливаютс  в исходное состо ние разр ды регистров 21 (посредством приема кода с

5 входов 22).

Если за М циклов сравнени  не все слова в зоне исключены (т.е. один из разр дов регистра 6 установлен в нуль), то нулем в регистре 6 отмечена позици  в зоне слова, совпадающего с признаком опроса всеми М

разр дами. На выходе эпемента И 9 при этом присутствует нулевой сигнал, который, инвертиру сь элементом НЕ 10, открывает дл  прохождени  сигнала переполнени  со счетчика 15 элемент И 11, с выхода которого на выход 16 устройства выдаетс  сигнал признака обнаружени  информации. Старшие разр ды адреса искомого слова при этом считываютс  с выходов 35 устройства, а младшие - с выходов 8.

Если искомое слово отсутствует в пам ти , то сигнал, по вл ющийс  на выходе 38 при равенстве кода на счетчике 28 с подаваемым на входы 39 кодом зоны, до которой ведетс  поиск, фиксирует процедуры поиска .

Claims (1)

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

   Устройство дл  поиска информации, содержащее группу блоков пам ти, группу коммутаторов адреса, первый счетчик адреса , регистр, регистр признака опроса, шифратор , первый элемент ИЛИ, первый элемент И, причем информационный вход регистра признака опроса подключен к входу требуемого признака поиска устройства, информационные входы блоков пам ти группы соединены с информационным входом устройства, группа младших разр дов адресного входа К-го блока пам ти подключена к выходу К-го коммутатора адреса К 1...М, где М - разр дность данных, старшие разр ды адресного входа каждого блока пам ти соединены с выходом первого счетчика адреса, информационный вход которого подключен к входу старших разр дов адреса устройства, выход признака обнаружени  информации подключен к выходу первого элемента И.отличающе- е с   тем, что, с целью повышени  быстродействи , в него введены группа сдвиговых регистров , второй счетчик адреса, группа элементов ИЛИ. второй элемент ИЛИ, второй элемент И, два элемента НЕ, группа элементов НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, формирователь импульсов, элемент задержки, делитель частоты, схема сравнени , причем информационный выход К-го блока пам ти подключен к первому входу К-го элемента НЕРАВНОЗНАЧНОСТЬ группы, второй вход и выход которого подключены соответственно к выходу К.-го разр да регистра признака и к первому входу К-го элемента ИЛИ группы, выход которого подключен к входу начальной установки К- го разр да регистра, выход старшего разр да и вход заполнени  при сдвиге младшего разр да которого соединены, выход К-го разр да регистра подключен к второму входу к-го элемента ИЛИ группы, к К-му входу шифратора и к k-му входу второго элемента И, выход которого подключен к первому входу первого элемента ИЛИ и через первый

   элемент НЕ подключен к первому входу первого элемента И, выход первого элемента ИЛИ подключен к счетному входу первого счетчика адреса и входу формировател  импульса , выход которого подключен к входам

   0 записи сдвиговых регистров и к входу установки в О второго счетчика адреса, выход переполнени  которого подключен к второму входу первого элемента.И, выход делител  частоты подключен к счетному входу

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

   0 регистра и через элемент задержки с входом делител  частоты, установочный вход К то сдвигового регистра группы подключен к К-му входу начального состо ни  группы устройства, выход старших разр дов К-го

   5 сдвигового регистра группы соединен с входом заполнени  при сдвиге младшего разр да К-го сдвигового регистра группы, а выхсщ К-го разр да j-ro сдвигового регистра О 1, L) подсоединен к j-му разр ду первого

   0 входа k-ro коммутатора адреса группы, второй вход которого подключен к входу младших разр дов адреса устройства, управл ющий вход коммутаторов адреса группы подключен к входу задани  режима

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

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

   5 инициации обращени  к пам ти устройства, входы управлени  записью-чтением блоков пам ти группы соединены с входом записи чтени  устройства, первый и второй входы и выход схемы сравнени  подключены соот0 ветственно к выходу первого счетчика адреса , входу номера зоны поиска устройства и к выходу индикации окончани  работы устройства , выход и вход начальной установки первого счетчика адреса подключены соот5 ветственно к выходу старших разр дов адреса устройства и к выходу второго элемента И, выход К-го блока пам ти группы подключен к К-му разр ду информационного выхода устройства, выход формировател  импульсов через второй элемент НЕ

   подключен к входу начальной установкивыходу младших разр дов адреса устройстрегистра , выход шифратора подключен к вэ

   Uto

   и,-,

   и,

   4i 4

   ЛЛ

   nv

   ГV

   прием кода. с96иг

   -ffV-

   . .- V v« ---A---

   коОо. нснАвьна устлмАиу V-f

   L/zxzir -

   м

   CL

   Фиг.2

   Л

   -4

   nv.,