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

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 кодом зоны, до которой ведется поиск, фиксирует процедуры поиска.

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

Устройство для поиска информации, содержащее группу блоков памяти, группу коммутаторов адреса, первый счетчик адреса, регистр, регистр признака опроса, шифратор, первый элемент ИЛИ, первый элемент И, причем информационный вход регистра признака опроса подключен к входу требуемого признака поиска устройства, информационные входы блоков памяти группы соединены с информационным входом устройства, группа младших разрядов адресного входа К-го блока памяти подключена к выходу К-го коммутатора адреса К 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.,