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

 

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (я)s G 06 F 15/40

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ба 1 (21) 4763772/24 (22) 28.11.89 (46) 23.10.91, Бюл, N 39 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) Е,Бардис (GR), В.И.Корнейчук, А.П.Марковский и Ю.Н.Чубатюк (SU) (53) 681,3(088.8) (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано для реализации доступа к информации как по ее

„„5Q „„1686464 А1 адресу. так и по содержимому. Целью изобретения является повышение быстродействия. Устройство содержит группу блоков

1.1-1.Мпамяти,,группу элементов НЕРАВНОЗНАЧ НОСТЬ 3.1-3.М, регистр 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 ил.

1686464

30

40

50

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

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

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

Устройство содержит группу блоков

1.1-1.M памяти, информационный выход 2 устройства, группу элементов 3.1-3.M НЕРАВНОЗНАЧНОСТЬ, регистр 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 начального состояния устройства, группу коммутаторов ?3.1 — 23.M адреса, вход 24 младших разрядов адреса устройства, вход 25 задания режима функционирования устройства, вход 26 запуска устройства, элемент ИЛИ-НЕ 27, счетчик 28 адреса, элемент НЕ 29, информационный вход 30 устройства, элемент.ИЛИ 31. вход

32 инициации обращения к памяти устройства, вход 33 записи-чтения устройства, вход 34 и выход 35 старших разрядов адреса устройства, схема 36 сравнения. вход 37 требуемого признака поиска устройства, выход 38 индикации окончания работы, вход 39 номера зоны поиска устройства, М разрядность данных, L = logzM

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

Информационные M-разрядные слова записаны в одноименных ячейках блоков

1,1 — 1.М по одному разряду слова в каждом блоке 1.

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

Одновременно на вход 32 подается единичный сигнал, который, пройдя через элемент

ИЛИ 31, инициирует работу блоков 1.

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

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

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

Поступающая на вход 20 последовательность тактовых сигналов (фиг. 2), которые задерживаются элементом 19 задержки, поступает на вход делителя 18 частоты. На выходе последнего формируются импульсы внутренней синхронизации, частота которых вдвое меньше частоты импульсов на входе 20 и фронт которых сдвинут относительно импульсов на входе 20 (фиг. 2), Сигнал начала работы, пройдя через элемент ИЛИ-НЕ 27, инициирует занесение кода с входа 34 на счетчик 28, с разрядных выходов которого упомянутый код номера зоны 2 поступает на адресные входы (старшие разряды) всех блоков 1. Кроме того, сигнал управления началом работы, пройдя через элемент ИЛИ 12, поступает на вход формирователя 13, формирующего на своем выходе 14 сигнал запуска (фиг, 2). который, поступая на управляющий вход счетчика 15, устанавливает все его разряды в нуль, поступая через элемент НЕ 29 на вход регистра 6, устанавливает все его разряды в нуль, поступая на управляющие входы всех сдвиговых регистров 21, инициирует прием кода на регистры 21 с соответствующих входов

22. При этом в регистр 21.1 заносится код

010101, .01. в регистр 21,2 — код

00110011...0011, в регистр 21.3 — код

0000111 ...00001111 и т.д. Соответственно с

1686464 выходов первых(старших) разрядов регист- несовпадения с выхода элемента 3.К HF.— ров 21 на вход коммутатора 23.1 снимается РАВНОЗНАЧНОСТЬ через элемент ИЛИ 5. К код 00...0, с выходов вторых разрядов реги- группы с приходом положительного фронта стров 21 на вход коммутатора 23.2 снимает- внешнего тактового импульса устанавливася код 00...01, с выходов К-х разрядов (К =1, М) 5 ет в единицу к-й разряд регистра 6, исклюрегистров21навходкоимутатора23,Кснима- чая тем самым (Z+(K)moqM)-å слово из ется код К-1, Упомянутые коды с входов ком- процесса дальнейшего сравнения. мутаторов 23 под действием нулевого Затем вновь с поступлением тактового сигнала на входе 25 коммутируются на их сигнала по входу 20 выполняется цикличевыходы и далее на младшие разряды адрес- 10 ский сдвиг регистра 6, с поступлением сигных входов соответствующих блоков 1 па- нала на выходе 17 производится мяти, Соответственно в первом блоке 1.1 циклический сдвиг содержимого регистров памяти адресуется Z-я ячейка, во втором 21, увеличение на единицу содержимого блоке 1.2 памяти — (Z+1)-я ячейка, в К-м бло- счетчика 15, и описанный цикл порэзрядноке 1.К памяти — (Z+K-1)-я ячейка. Соответст- 15 го сравнения повторяется. венно с выхода каждого k-ro блока 1,К В общем случае на I-м цикле поиска памяти считывается К-й разряд (Z+K-1)-ro (IC(1,M}) сравнения с разрядных выхослова.Считываниепроизводитсяпопоступ- дов регистров 21 на входы коммутэтолении на вход 20 внешнего тактового им- ров 23.1 — 23.М выдаются коды, пульса, который через элемент ИЛИ 31 20 -соответственно равные (I+M-1) « М, котоподается на управляющие входы выборки рые коммутируются на младшие разряды всех блоков 1 памяти. адресных входов соответствующих блоков

На К-м элементе 3.К НЕРАВНОЗНАЧ- 1.1-1.M памяти. С выхода каждого К-го блоНОСТЬ выполняется сравнение К-го разря- ка 1.К памяти считывается К-й разряд (Zt да (Z+K-1)-го слова с К-м разрядом признака 25 К вЂ” 2+l)mod М)-го слова, который сравнивается с опроса. В случае несовпадения указанных К-м разрядом признака опроса с регистра 4 битов на выходе элемента З,К НЕРАВНОЗ- на элементе 3.К НЕРАВНОЗНАЧНОСТЬ, НАЧНОСТЬ формируется единичный сиг- при этом сигнал несовпадения, пройдя ченал, который через элемент ИЛИ 5.К резэлементИЛИ5.К,устанавливаетвединипоступает на установочный вход К-го разря- 30 цу k-й разряд регистра 6, исключая тем самым да регистра 6 и с приходом тактового им- (Z4(k-2>I)modM)å слово из процесса дальнейпульса с входа 20 (фиг, 2) К-й разряд шего сравнения, так как вне зависимости от регистра 6 устанавливается в единицу, тем совпадения исключаемого слова в остальных самым (Z+K-1)-е слово исключается из даль- разрядах с признаком опроса единица в разнейшего процесса поиска. Операция при- 35 ряде регистра 6, соответствующем (Z+(0ема кода производится на регистре 6 при -2+l)modM)-му слову, перезэписывается с наличии импульса внутренней тактовой по- выхода соответствующего разряда регистра следовательности с выхода 17 делителя 18, 6 через элемент ИЛИ 5.К при каждой операС приходом на вход 20 следующего тактово- ции записи в регистре 6. го сигнала (при отсутствии импульса внут- 40 Если все слова в зоне с адресами от Z-го ренней тактовой последовательности на до(2+М-1)-й нэ I-м цикле сравнения окажутвыходе 17 и, следовательно, на управляю- ся исключенными(т.е, все разряды регистра щем входе регистра 6) выполняется цикли- 6 окажутся установленными в единицу), то ческий сдвиг влево (в сторону старших единичный сигнал формируется на выходе разрядов) содержимого регистра 6. С прихо- 45 элемента И 9 и этим сигналом инициируется дом положительного фронта импульсас вы- переход к новой зоне: сигнал увеличивает хода 17 производится прибавление на единицу содержимое счетчика 28, обесединицы ксодержимомусчетчика15адреса печивая переход к (Z+1)-й зоне, пройдя даи циклический сдвиг влево содержимого лее через элемент ИЛИ 12, поступает на всех регистров 21. С разрядных выходов 50 вход формирователя 13 импульса запуска, одноименных разрядов регистров 21 на вхо- которым устанавливаются в нуль все рэзды коммутаторов 23.1 — 23,М выдаются соот- ряды регистра 6 и счетчика 15, устанавливаветственно коды 1, 2, 3, ..., М, О, которые ются в исходное состояние разряды коммутируются на младшие разряды адрес- регистров 21 (посредством приема кода с ных входов соответствующих блоков 1.1 — 55 входов 22).

1.М памяти. С выхода каждого К-го блока1.К Если за M циклов сравнения не все слопамяти считывается k-й paap n(Z+(K)mooM)- ва в зоне исключены (т.е. один из разрядов го слова, который сравнивается с К-м разря- регистра 6 установлен s нуль), то нулем в дом признака опроса элементом З,К регистре 6 отмечена позиция в зоне слова, НЕРАВНОЗНАЧНОСТЬ. Единичный сигнал совпадающего с признаком опроса всеми M

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

Если искомое слово отсутствует в памяти, то сигнал, появляющийся на выходе 38 и ри равенстве кода на счетчике 28 с подаваемым на входы 39 кодом зоны, до которой ведется поиск, фиксирует процедуры поиска. ду К-го элемента ИЛИ группы, к К-му входу шифратора и к k-му входу второго элемента

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

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

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

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

K-ro блока памяти подключен к первому входу K-ro элемента НЕРАВНОЗНАЧНОСТЬ группы, второй вход и выход которого подключены соответственно к выходу К-го разряда регистра признака и к первому входу

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

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

K-ro сдвигового регистра группы подключен к К-му входу начального состояния группы устройства, выход старших разрядов К-ro сдвигового регистра группы соединен с входом заполнения при сдвиге младшего раз30

55 ряда K-го сдвигового регистра группы, а выход K-го разряда )-ro сдвигового регистра

O = 1, L) подсоединен к j-му разряду первого входа k-го коммутатора адреса группы, второй вход которого подключен к входу младших разрядов адреса устройства, управляющий вход коммутаторов адреса группы подключен к входу задания режима функционирования устройства и к первому входу элемента ИЛИ-НЕ,. выход которого подключен к входу записи первого счетчика адреса, второй вход элементов ИЛИ-НЕ, синхровход регистра признака опроса и второй вход первого элемента ИЛИ подключены к входу запуска устройства, входы управления выборкой блоков памяти группы подключены к выходу второго элемента

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

1686464

9Риг,2

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

Техред М.Моргентал Корректор М.Шароши.

Редактор И.Шмакова

Заказ 3599 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 подключен к входу начальной установки регистра, выход шифратора подключен к выходу младших разрядов адреса устройства.