Ассоциативное запоминающее устройство Советский патент 1983 года по МПК G11C15/00 

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

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

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

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

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

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

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

На фиг. 1 показана структурная схема устройства; на фиг. 2 - селектор, пример выполнения;на фиг. 3 - блок анализа информации и соответствующий ему .логический блок; на фиг. 4 - вариант блок анализа информации, вариант; на фиг. 5 - логический блок; на фиг. 6 - инверти-. 10 рующий пороговый элемент; на фиг.7 временная диаграмма работы устройства, Устройство содержит (фиг. 1) Ц информационных регистров 1, основной регистр 2 опроса, ц селекторов 3, п 15 блоков 4 анализа информации, логический блок 5, дополнительный регистр б опроса, элементы И 7, элемент ИЛИ 8 и регистр 9 сдвига. Селекторы 3 имеют входы 10-12 и выхоQ ды 13. Элемент ИЛИ 8 имеет выход 14. Устройство имеет входы 15-17. Блок 5 имеет выход 18. Блоки 4 имеют выходы 19 и 20, блок 5 и регистр 9 - соответственно выходы 21 и 22 и вход 23. 5 Селектор 3, служащий для выделения модуля разности, содержит(фиг. 2) сумматор 24, коммутатор 25, элемен- ты И 26 и элемент ИЛИ 27.

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

Другой вариант блока.4 содержит (фиг. 4) триггеры 48-50, элементы И 51-67, элементы ИЛИ 68-74, элементы НЕ 75-78 и элемент НЕРАВНО0 ЗНАЧНОСТЬ 79.

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

На временной диаграмме (фиг. 7) показаны последовательности сигналов при ассоциативном поиске сиг нал 88 - на входе 15; сигнал 89 на входе 16; сигнал 90 - на входе 23; сигнал 91 - на входе 17;. сигналы 92 и 93 - соответственно на выходах 21 и 22 блока 5, сигналы 945 96 - возможные длительности ассоциативного поиска.

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

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

0 записаны числа Xj ,,Х.| , . .. . ,Xf),

в регистре 2 - число У и в регистре 6 -- число 7, .

При этом у каждого -го селектбра 3 на вход 10 поступает число Х| 5 в прямрм коде, а на вход 11 - число У в инверсном коде. Если , то на сумматоре 24 появляется сигнал переноса, который npH6aBjjHeT единицу к полученной сумме и пропус кает на выход коммутатора 25 прямой код суммы; в противном случае на выход коммутатора 25 проходит инвер ный код суммы и, таким образом, на выходе коммутатора 25 всегда устанавливается параллельный код модуля разности Xj и У. По сигналу на входе 15 устанавливаются в начальное состояние триг геры блоков 4 и регистр 9. По первому, тактовому импульсу на входе 23 в одном из разрядов регист ра 9 появляется единица, разрешающая прохождение на выходы 13 селекторов 3 значений старших разрядов полученных модулей разности. В это же время на выходе 14 элемента ИЛИ появляется значение старшего разряда числа у; . . По синхросигналу с входа 17 в триггерах блоков 4 фиксируются новы состояния. Процедура поиска занимает в обш случае ГП тактов, где m - число раз рядов признаков, в каждом из которых происходит сдвиг единицы в регистре 9, поступление на блоки 4, следующих в порядке убывания разряд ного веса значений разрядов модулей разности, и фиксация нового состояния (длительность 96 на фиг. При этом выбранное в результате поиска хранимые признаки отмечаютс единичными сигналами на выходах 20 соответствующих блоков 4. При выполнении блоков 4 (фиг. f) оиск может быть прекращен при повлении сигнала логического нуля на ыходе 21 блока 5 (длительность 94 а фиг. 7) или при появлении сигнаа логической единицы на выходе 22 лока 5 ( длительность 95 на фиг. 7) обоих случаях дальнейшая процедуа не изменяет результата поиска. Логический уровень на входе 16 устанавливается до начала поиска. Если блоки 4 выполнены как на фиг, 3, и на входе 16 уровень нуля, то в результате поиска выбираются хранимые признаки такие, что для всех 6 - 1 ,П /X;-y/-|Xg-y/+Z7-0 При уровне единицы на входе 16 |x,-y/-/Xg-y/-2iO. Если блоки 4 выполнены как на фиг. 4 (и, соответственно, блок 5 выполнен как на фиг. 5), и на входе 16 - уровень нуля, то в результате поиска выбирается, если он есть, хранимый признак такой, что для всех Е- ГТп, /X;-y/-/Xj-y/-Z O При уровне единицы на входе 16. /X,-y/-/Xj-y/+ZsO Таким образом, поиск указанных видов осуществляется за один параллельный по словам и последовательный по разрядам опрос.

10 л

13

f6

фиг 2

15 17 фиг.З

16

1317

Фаг.

21 22

фиг.5

l8fy

фиг 6

фиг 7