Ассоциативный запоминающий элемент
Патент 788177
Авторы
Классы МПК
Ассоциативный запоминающий элемент
Иллюстрации
Реферат
ад1 ..;..а, .::;СЫ .Й бнвпыоте Ива
Союз Советских
Социалистических
Республик
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ о»788177 ю ф
// (61) Дополнительное к авт. свид-ву (22) Заявлено 27. 07. 78 (21) 2649840/18-24 (51)М. Кл. с присоединением заявки ¹(23) Приоритет
6 11 С 15/00
Государственный комитет
СССР
llo делам изобретений и открытий
Опубликовано 151280 Бюллетень № 46 (53) УДК 681. 327 (088.8) Дата опубликования описания 1 1 80 (72) Авторы изобретения
В. Б. Матвеев и В. М. Трусфус
Казанский ордена Трудового Красного Знамени авиационный институт им. A. Н. Туполева (71) Заявитель (54) АССОЦИАТИВНЫЙ ЗАПОМИНАЮЩИЙ ЭЛЕМЕНТ
Изобретение относится к запоминающим устройствам.
Известен ассоциативный запоминающий элемент (АЗЭ), содержащий элементы памяти, логические элементы и блок сравнения g1) .
Недостатком этого элемента является большое количество выводов.
Наиболее близким техническим решением к предлагаемому является АЗЭ, содержащий запоминающий элемент, схему пробега по равенству, входы которой подключены к первому и второму выходам запоминающего элемента, первому и второму выводам АЗЭ, а выход 15 подключен к третьему выводу АЗЭ, первый элемент И, входы которого подключены через элемент НЕ к первому и непосредственно ко второму выводам
АЗЭ и первому выходу запоминающего 20 элемента, а выход подсоединен к первому входу элемента ИЛИ, выход которого подключен к четвертому выводу
АЗЭ 2
E)
Недостатками этого АЗЭ являются ограниченные функциональные возможности, не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска. 30
Цель изобретения — расширение функциональных возможностей элемента за счет выполнения логических операций.
Поставленная цель достигается тем, что в ассоциативный запоминающий элемент, содержащий элемент памяти, элементы И и ИЛИ, первый элемент HE u шины управления, причем первые входы элементов И подключены к первой шине управления, второй вход первого элемента И соединен с первым выходом элемента памяти, второй выход которого подключен ко вторым входам второго и третьего элементов И, третьи входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго элемента И и второй шине управления, выходы первого и второго элементов
И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход которого подключен к четвертой шине управления, введены четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов И подклю788177 чены к пятой шине управления, вторые входы четвертого и пятого элементов И соединены соответственно с выходом второго элемента НЕ и первым выходом элемента памяти, выход пятого элемента И соединен с первым входом шестогО алемента И и входом второго элемента;
НЕ, выход которого подключен к шестой шине управления, третий вход четвертого и второй вход шестого элементов
И соединены с выходом третьего элемента HE и седьмой шиной управления, выходы третьего и четвертого элементов И подключены соответственно ко вхОду третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходом шес- 15 того элемента И.
На фиг. 1 изображена блок-схема.
АЗЭ; на фиг. 2 — структура накопителя ассоциативного запоминающего устройства„ в состав которого входит щ этот элемент.
АЗЭ (фиг. 1) содержит элемент 1 памяти, первый 2, второй 3, третий 4, четвертый 5, пятый 6 и шестой 7 элементы И, первый 8 и второй 9 элементы ИЛИ, первый 10, второй 11 и третий 12 элементы НЕ, первую 13, вторую 14, третью 15, четвертую 16, пятую 17, шестую 18 и седьмую 19 шины управления. Первые входы элементов
И 2-4 подключены к шине 13, второй ЗО вход элемента И 2 соединен с первым выходом элемента 1 памяти, второй выход которого подключен ко вторым входам элементов И 3 н 4. ТрЕтьи входы элементов И 2 и 4 соединены с выхо- 35 дом элемента HE 10, вход которого подключен ко входу элемента 1 памяти, третьему входу элемента И 3 и к шине 14. Выходы элементов И 2 и 3 соединены со входами элемента ИЛИ 8, выход 4g которого подключен к шине 15. Выход элемента И 4 соединен с первым входом элемента ИЛИ 9, выход которого подключен к шине 16. Первые входы эле" ментов И 5 и 6 подключены к шине 17, вторые входы элементов И 5 и 6 соеди" 45 иены соответственно с выходом элемента НЕ 11 и первым выходом элемента 1 памяти. Выход элемента И б соединен с первым входом элемента И 7 и входом элемента НЕ 11, выход которо-50 го подключен к шине 18. Третий вход элемента И 5 и второй вход элемента
И 7 соединены с выходом элемента HE
12 и шиной 19. Выходы элементов И 4 и ф подключены соответственно ко вхо- $$ ду элемента НЕ 12 и второму входу элемента ИЛИ 9, третий вход которого соединен с выходом элемента И 7.
Накопитель ассоциативного эапоми- 40 нающего устройства содержит num
АЗЭ 20 (фиг. 1 и 2), первые 21, вторые 22 и третьи 23 разрядные шины, соединенные с одноименными А33 20.
Шины 13 и 17 АЗЭ 20 (кроме первых) 45 подключены к шинам 15 и 16 предыдущих АЗЭ 20 соответственно.
В составе накопителя ассоциативного запоминающего устройства АЗЭ работает следующим образом.
Запись и считывание признаков про" изводится параллельно по словам по первым разрядным шинам 21.
Пример. Поиск "Ближайшего большего". При этом в запоминающий элемент 1 каждого АЗЭ 20 занесено значение х. (i = 1,n, j = 1,m) соответI ствующего разряда некоторого ассоциативного признака, причем на первом выходе запоминающего элемента 1 устанавливается прямое „ а на втором— инверсное значение этого разряда.Разряды ассоциативных признаков располагаются в словах начиная со старших.
На каждую первую разрядную шину 21 подается значение соответствующего разряда признака опроса у (в пряб мом коде), а на первых шинах 13 первых в словах АЗЭ 20 устанавливается логическая "1". Обозначим 2; > и
Ц
Z — логические переменные на ши1 нах 13 и 17, j-ro A33 20 i-го слова.
Тогда на шинах 22 и 23 реализуются (фиг. 2) функции соответственно
I
5 =Л, 2„х„. у
34 = . J 2„- х;, а на шинах 15 и 16 этого АЗЭ 20 устанавливаются соответственно функции г
;, = Z,. (x;,,урx; у >
2;„х..у-ч 2 . х Цч;Я3
Равенство 2 = 1 означает, что
Ф,Д в пройденных j разрядах данного слова все разряды совпали с разрядами признака опроса. Равенство первого члена диэъюнкции в правой части выражения для 2 логической "1" ознаЪ ф чает, что j-1 старший разряд ассоциативного признака совпадает с разрядами признака опроса, а j-ый разряд— больше, т.е. данное слово — ближайшее большее по старшим разрядам.
Второй или третий члены дизъюнкции равны "1", если данное слово является наименьшим среди ближайших больших по старшим ) разрядам и ни для одного из одноименных АЗЭ 20 всех слов первая дизъюнкция не равна "1".
Поиск проходит параллельно по словам и разрядам. По окончании переходных процессов состояния на шинах
16 последних в словах А33 20 фиксируются в детекторах (на чертеже не показаны). Выполнение равенства Z". = 1
4Л означает, что -ый ассоциативный признак — ближайший больший, а выполнеI ние равенства Z > = 1 полностью совпадает с признаком опроса.
Можно показать, что А3Е 20 также позволяет осуществить полностью параллельный поиск по условиям "Ближайший меньший", "наибольший" и "наи788177 меньший", "больший", "меньший", "равный", а также их инверсиям и комбинациям.
Таким образом, использование описанных АЗЭ 20 в накопителе ассоциативного запоминающего устройства позволяет проводить в последнем сложные иды поиска благодаря расширению функциональных возможностей АЗЭ.
Формула изобретения (О
Ассоциативный запоминающий элемент, содержащий элемент памяти, элементы
И и ИЛИ, первый элемент HE и шины управления,причем первые входы элементов И подключены к первой шине управления, второй вход первого элемента
И соединен с первым выходом элемента памяти, второй выход которого подключен ко вторым входам второго и тре- 20 тьего элементов И, третьи входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго эле мента И и второй шине управления, выходы первого и второго элементов И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход
27
I
Л >82
1 которого подключен к четвертой шине управления, отличающийся тем, что, с целью расширения функциональных возможностей элеМента за счет выполнения логических операциЯ, он содержит четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, вторые входы четвертого и пятого элементов
И соединены соответственно с выходом второго элемента НЕ и первым выходом элемента памяти, выход пятого элемента И соединен с первым входом шестого элемента И и входом второго элемента НЕ, выход которого подключен к шестой шине управления, третий вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента HE и седьмой шиной управления, выходы третьего и четвертого элементов И подключены соответственно ко входу третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходом шестого элемента И.
Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР
9 564656, кл. G 11 С 5/00, 1975.
2. Авторское свидетельство СССР
9 615543, кл. G 11 С 15/00, 1976 (прототип).
788177
Э ° °
° ° °
Фие.2
Составитель В. Рудаков
Редакто A. Гук Техред И.Табакович Ко ктор Е. Папп
Заказ 8361/60 Тираж 662 Подииоиоа
BHHHlIH Государственного комитета СССР по делам изобретений и открытий .
113035, Москва, Ж-35 Раушская б 4 5
75 i
1 I
I !
I !
I?7 I
I zai
I
1 !