Ассоциативное запоминающее устройство

 

(19) (11) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН

3(59 G 11 С 15 О..

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITMA

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3504162/18-24 (22) 25 ° 10. 82 (46) 23.12..83. Бюл. 9 47 (72) В.Б. Матвеев (71) Казанский ордена Трудового

Красного Знамени и ордена Дружбы народов авиационный институт им. A.Н. Туполева (53) 681.327.6(088.8) (56) 1. Авторское свидетельство СССР

Ф 27 1.857 кл. G 11 С 15/00 1969.

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

М 780043, кл. 6 11 С 15/00, 1978 (прототип). (54)(57) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блоки анализа информации, подключенные к логическому блоку, информационные регистры, основной регистр опроса, элементы И и элемент ИЛИ, о т л ич а ю щ е е с я тем, что, с целью расширения области применения устройства путем увеличения числа критериев поиска, в него введены дополнительный регистр опроса, регистр сдвига и селекторы, первые входы которых подключены к выходу основного регистра опроса, вторые входы — к выходам информационных регистров, третьи входы — к выходу регистра сдвига, одни из входов элементов И соединены с выходом дополнительного регистра опроса, другие — с выходом регистра сдвига, а выходы подключены к входу элемента ИЛИ, выход которого подклю чен к одним из входов блоков анализа информации, другие входы которых подключены к Выходам селекторов, причем управляющие входы регистра сдвига являются одними из управляющих. входов устройства.

1062791

Изобретение относится к вычислительной технике.

Известно ассоциативное запоминающее устройство, содержащее регистры хранимых признаков, регистр опроса, детекторы (11 .

Однако в этом устройстве аппаратурно осуществляется только граничный поиск (больших, меньших или равных опросному хранимых признаков). Все остальные виды поиска осуществляются только алгоритмически, т.е. с пониженным быстродействием.

Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство, содержащее накопитель, реГистр опроса, блок управления, группы элементов И, блоки местного управления, дополнительные накопители и блоки вывода результата, в котором осуществляется поиск в массиве чисел, ближайших к заданному (2} .

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

Целью изобретения является расширение области применения устройства путем увеличения числа критериев поиска, в частности путем обеспечения поиска хранимых признаков, попадающих в окрестность ближайшего к признаку Опроса хранимого признака или наиудаленного от признака опроса хранимого признака, симметричную относительно признака опроса, или поиска ближайших или наиудаленных хранимых признаков — таких, что в указанных окрестностях они единственны.

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

На фиг. 1 показана структурная схема устройства; на фиг. 2 — селек5 тор, пример выполнения на фиг. 3

I блок анализа информации и соответствующий ему.логический блок; на фиг. 4 — вариант блок анализа информации, вариант; на фиг. 5 — логический блок; на фиг. 6 — инверти- .

10 рующий пороговый элемент; на фиг,7 временная диаграмма работы устройства.

Устройство содержит (фиг. 1) я информационных регистров 1, основной регистр 2 опроса, } селекторов 3, п

15 блоков 4 анализа информации, логический блок 5, дополнительный регистр 6 опроса, элементы И 7, элемент ИЛИ 8 и регистр 9 сдвига. Селекторы 3 имеют входы 10-12 и выхо20 ды 13. Элемент ИЛИ 8 имеет выход 14.

Устройство имеет входы 15-17. Блок 5 имеет выход 18. Блоки 4 имеют выходы 19 и 20, блок 5 и регистр 9 — соответственно выходы 21 и 22 и вход 23.

Селектор 3, служащий для выделения модуля разности, содержит(фиг. 2) сумматор 24, коммутатор 25, элементы И 26 и элемент ИЛИ 27.

Каждый блок 4 содержит (фиг. 3}

30 триггеры 28-30, элементы И 31-38, элементы НЕ 39-41, элементы ИЛИ 42 и 43, элемент НЕРАВНОЗНАЧНОСТЬ 44, элемент ИЛИ вЂ  45 и элемент И-НЕ 46, Блок 5 в этом случае представляет со35 бой элемент И 47.

Другой вариант блока.4 содержит (фиг. 4) триггеры 48-50, элементы

И 51-67, элементы ИЛИ 68-74, элементы НЕ 75-78 и элемент НЕРАВНО40 ЗНАЧНОСТЬ 79 °

В этом случае блок 5 (фиг. 5) содержит элементы ИЛИ-НЕ 80-82, элемент ИЛИ 83 и инвертирующий пороговый элемент 84, который может содержать (фиг. 6) р -1 элемент И 85, и-2 элемента ИЛИ 86 и элемент

ИЛИ-НЕ 87.

На временной диаграмме (фиг. 7) показаны последовательности сигналов при ассоциативном поиске сигнал 88 — на входе 15; сигнал 89— на входе 16; сигнал 90 — на входе

23; сигнал 91 — на входе 17; сигналы 92 и 93 — соответственно на выходах 21 и 22 блока 5, сигналы 9455 96 — возможные длительности ассоциативного поиска.

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

В исходном состоянии в регистрах 1

60 записаны числа Х(,.....,Х„,....,Хп, в регистре 2 — число У и в регистре 6 = число 7,.

При этом у каждого -го селекто ра 3 на вход 10 поступает число Х; в прямом коде, а на вход 11 — чис1062791 ло У в инверсном коде. Если Х„ у, то на сумматоре 24 появляется сигнал переноса, который прибавляет единицу к полученной сумме и пропускает на выход коммутатора 25 прямой код суммы; в противном случае на выход коммутатора 25 проходит инверс ный код суммы и, таким образом, на выходе коммутатора 25 всегда устанавливается параллельный код модуля разности X и У.

По сигналу на входе 15 устанавливаются в начальное состояние триггеры блоков 4 и регистр 9.

По первому тактовому импульсу на входе 23 в одном из разрядов регистра 9 появляется единица, разрешающая прохождение на выходы 13 селекторов 3 значений старших разрядов полученных модулей разности. В это же время на выходе 14 элемента ИЛИ 8 появляется значение старшего разряда числами

По синхросигналу с входа 17 в триггерах блоков 4 фиксируются новые состояния»

Процедура поиска занимает в общем случае а тактов, где — число разрядов признаков, в каждом из которых происходит сдвиг единицы в регистре 9, поступление на блоки 4, следующих в порядке убывания разрядного веса значений разрядов модулей разности, и фиксация нового состояния (длительность 96 на фиг. 7)

При этом выбранные в результате поиска хранимые признаки отмечаются единичными сигналами на выходах 20 соответствующих блоков 4.

При выполнении блоков 4 (фиг. 4 ) поиск может быть прекращен при появлении сигнала логического нуля на выходе 21 блока 5 (длительность 94 на фиг. 7) или при появлении сигнала логической единицы на выходе 22 блока 5 (длительность 95 на фиг. 7) в обоих случаях дальнейшая процедура не изменяет результата поиска.

Логический уровень на входе 16 устанавливается до начала поиска.

Если блоки 4 выполнены как на фиг. 3, и на входе 16 уровень нуля, то в результате поиска выбираются хранимые признаки Х; такие, что для всех 0 = 1,ь

/Х; -У/ — /Х -У/+ 0

3() При уровне единицы на входе 16 (X; -У/ — /Х -У/ -2= 0.

Если блоки 4 выполнены как на фиг. 4 (и, соответственно, блок 5

25 выполнен как на фиг. 5), и на входе

16 — уровень нуля, то в результате поиска выбирается, если он есть, хранимый признак Х, такой, что для всех К= 1,в, 30 /x„-v/ — /x, -у/ -z> o

При уровне единицы на входе 16.

/ х; -у/ - /х -у/+z< о

Таким образом, поиск укаэанных видов осуществляется за один параллельный по словам и последовательный по разрядам опрос.

1062791

Фиг. 2

15 17

<Ри8З

1062791

f81

19

191

193

1062791

21 22

181

182.

10б2791

8У

40иг. 7

Составитель В. Рудаков

Редактор П. Коссей Техред И,Тепер Корректор О. Билак

Заказ 10229/54 Тираж 594 Подписное

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

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

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4