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

 

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

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

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

РЕСПУБЛИН (19) (11) 3(51) 6 11 С 15 00

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

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

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ ю а фиг 1 (21) 3504157/18-24 (22) 25.10.82 (46) 23.12.83. Бюл. М 47 (72) В.Б. Матвеев . (71) Казанский ордена Трудового

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

Р 277857, кл. G 11 С 15/00, 1969.

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

9 780043, кл. G 11 С 15/00, 1978 (прототип). (54) (57) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО, содержащее информационные регистры, основной регистр опроса, элемент Й и блок анализа информации, одни из выходов которого являются выходами устройства, о т л ич а ю щ е е с я тем, что, с целью расширения области применения устройства путем увеличения числа критериев поиска, в него введены дополнительный регистр опроса, счетчик импульсов, селекторы и группа счетчиков импульсов, входы которых подключены к выходам селекторов, одни из входов которых соединены с выходом основного регистра опроса, а другие входы подключены к выходам информационных регистров, выходы счетчиков импульсов группы соединены с одними из входов блока анализа информации, другой вход которого подключен к выходу счетчика импульсов, входы которого соединены соответственно с выходами дополнительного регистра опроса и элемента И, первый вход которогО подключен к другому выходу блока анализа информации, а второй вход и управляющие входы счетчиков импульсов группы являются одними из управляющих входов устройства.

1062789

20

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

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

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

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

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

Целью изобретения является расширение области применения устройства путем увеличения числа критериев поиска, а именно поиска хранимых признаков, попадающих в окрестность признака опроса У с радиусом ! I

Х,+, где Х вЂ” ближайший к У хранимый признак, либо поиска хранимых З5 признаков, оказавшихся вне окрестности признака опроса У с радиусом

Х -, где Х вЂ” наиудаленный от У (I I/ хранимый признак, либо поиска хранимого признака Х, единственно по- 40 падающего в окрестность признака опроса с радиусом X +Z, либо поиска хранимого признака Х, единст/( венно оказавшегося вне окрестности признака У с радиусом X 45

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

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

Устройство содержит(фиг. 1) информационные регистры 1, основной регистр 2 опроса, селекторы 3, служащие для выделения модуля разности, группу счетчиков 4 импульсов, блок

5 анализа информации, дополнительный регистр 6 опроса, счетчик 7 импуль— сов, элемент И 8, входы 9 и 10 селекторов 3, выходы 11 селекторов 3, входы 12 блока 5, выходы 13 устройства, выход 14 и вход 15 блока 5 соответственно, входы 16 и 17.

Каждый селектор 3 содержит (фиг. 2) сумматор 18 и коммутатор 19. Блок 5 содержит (фиг. 3) элемент ИЛИ 20, элементы И 21 и индикаторы 22.

Вариант блока 5 содержит (фиг.4) формирователи 23 сигналов, элемент

ИЛИ 24, счетчик 25 импульсов, элементы И 26 и индикаторы 27.

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

Хранимые признаки Х, < = 1,A — в прямом коде и признак опро"а У вЂ” в инверсном коде поступают на вход сумматора 18; появление единицы на выходе переноса сумматора 18 означает, что Х ) У, при этом добавляется единица в младший разряд суммы и на выход селектора 3 выдается прямой код полученной суммы; в противном случае Х„с У и на выход 11 проходит инверсный код суммы, таким образом на выходе 11 формируется модуль разности Х „ и У. Полученные модули разности записываются в соответствующие счетчики 4.

Далее, в зависимости от конкретного вида поиска, тактовые импульсы со входа 16 добавляют либо вычитают единицы из содержимого счетчиков 4. Сигналы переполнения либо соответственно обнуления счетчиков 4 поступают на соответствующие входы

12 блока 5.

Первый из этих сигналов открывает элемент И 8, через который тактовые импульсы со входа 16 начинают поступать на вычитающий вход счетчика f, на который ранее занесено с регистра 6 значение 2.. Сигнал обнуления счетчика 7 поступает на вход 15 блока 5.

1062789

25 г

М

l, 74 15

При выполнении блока 5 (фиг. 3) сигнал на входе 15 закрывает элементы И 21, тем самым в индикаторах 22 оказываются отмеченными такие хранимые признаки Х„, для которых при всех R = 1,п

/Х; — У/- /Х,-У/ -2 0 при выполнении счетчиков 4 вычитающими, либо (Х, -У/ — /Х -У/ - 0, при выполнении счетчиков 4 прибавляющими.

При выполнении блока 5 (фиг. 4)

1 перед началом поиска необходимо сигналом по входу 17 привести в исходное состояние счетчик 25, характеризуемое нулевым уровнем на выходе 14.

Первый из поступающих на вход 12 сигналов переводит счетчик 25 в состояние с единичным уровнем на выходе, а второй — снова в состояние с уровнем нуля на выходе, которое остается неизменным до конца поиска.

Сигнал обнуления счетчика 7 в этом случае (если он вообще вырабатывается) представляет собой кратковременный импульс, отпирающий элементы И 26. Тем самым в индикатор х

27 оказываются отмеченными такие хранимые признаки X, для которых

1 при всех 3= -1, /Х, — У/ — /Хо — У/ +2 с0, при выполнении счетчиков 4 вычитающими, либо

/ Х; -У/ — (Х -У/ - ).0, при выполнении счетчиков 4 прибавляющими.

Признаком окончания ассоциативного поиска при выполнении блока 5 по схеме (фиг. 3) служит появление сигнала обнуления счетчика 7, а при выполнении по схеме (фиг. 4) появление сигнала обнуления счетчика 7 или перепада из единичного уровня в нулевой на выходе 14.

В предложенном устройстве поиск осуществляется параллельно для всех признаков.

Быстродействие устройства зависит от закона распределения величины признаков Х и У, а также от величины 7,. .В целом быстродействие растет с уменьшением дисперсии величины признаков Х; и У и уменьшением величины Z

1062789

gc 15

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

Редактор П. Коссей Техред A.Ач Корректор О. Билак, Тираж 594 Подписное

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

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

Заказ 10229/54

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