Ассоциативный запоминающий элемент Советский патент 1980 года по МПК G11C15/00 

Изобретение относится к запоминающим устройствам. Известен ассоциативный запоминающий элемент (АЗЭ), содержащий элементы памяти, логические элементы и блок сравнения i Недостатком этого элемента является большое количество выводов. Наиболее близким техническим реше нием к предлагаемому является АЗЭ, содержащий запоминающий элемент, схе му пробега по равенству, входы которой подключены к первому и второму в ходам запоминающего элемента, первому и второму выводам АЗЭ, а выход подключен к третьему выводу АЗЭ, пер вый элемент И, входы которого подключены через элемент НЕ к первому и непосредственно ко второму выводам АЗЭ и первому выходу запоминающего элемента, а выход подсоединен к первому входу элемента ИЛИ, выход которого подключен к четвертому выводу АЗЭ Г2. Недостатками этого АЗЭ являются о раниченные функциональные возможност не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска. Цель изобретения - расширение функциональных возможностей элемента за счет выполнения логических операций. Поставленная цель достигается тем, что в ассоциативный запоминающий элемент, содержащий элемент памяти, элементы И и ИЛИ, первый элемент НЕ и шины управления, причем первые входы элементов И подключены к первой шине управления, второй вход первого элемента И соединен с первым выходом элемента памяти, второй выход которого подключен ко вторым входам второго и третьего элементов И, Третьи входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго элемента И и второй шине управления, выходы первого и второго элементов И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход которого подключен к четвертой шине управления, введены четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов. И подключены к пятой шине управления, вторые входы четвертого и пятого элементов соединены соответственно с выходом второго элемента НЕ и первым выходом элемента памяти, выход пятого элемен та и соединен с первым входом шестог элемента И и входом второго элемента НЕ, выход которого подключен к шесто шине управления, третий вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой шиной управления, выходы третьего и четвертого элементов И подключены соответственно ко входу третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходом шес того элемента И. На фиг. 1 изображена блок-схема. АЗЭ; на фиг, 2 - структура накопителя ассоциативного запоминающего устройства, в состав которого входит этот элемент, АЗЭ (фиг. 1) содержит элемент 1 памяти, первый 2, второй 3 третий 4 четвертый 5, пятый б и шестой 7 элементы И, первый 8 и второй 9 элементы ИЛИ, первый 10,второй 11 и третий 12 элементы НЕ, первую 13, вторую 14, третью 15, четвертую 16, пятую 17, шестую 18 и седьмую 19 шины управления. Первые входы элементов И 2-4 подключены к шине 13, второй вход элемента И 2 соединен с первым выходом элемента 1 памяти, второй выход которого подключен ко вторым вхо дам элементов И 3 и 4. Третьи входы элементов И 2 и 4 соединены с выходом элемента НЕ 10, вход которого подключен ко входу элемента 1 памяти третьему входу элемента И 3 и к шине 14. Выходы элементов И 2 и 3 соед нены со входами элемента ИЛИ 8, выхо которого подключен к шине 15. Выход элемента И 4 соединен с первым входом элемента ИЛИ 9, выход которого подключен к шине 16. Первые входы эл ментов И 5 и 6 подключены к шине 17, вторые входы элементов И 5 и 6 соеди нены соответственно с выходом элемента НЕ 11 и первым выходом элемента 1 памяти. Выход элемента И 6 соединен с первым входом элемента И 7 и йхЬдом элемента НЕ 11, выход котор го подключен к шине 18. Третий вход элемента И 5 и второй вход элемента И 7 соединены с выходом элемента НЕ 12и 11ШНОЙ 19. Выходы элементов И 4 и J подключены соответственно ко вхо ду элемента НЕ 12 и второму входу элемента ИЛИ 9, третий вход которого соединен с выходом элемента И 7. Накопитель ассоциативного эапоминающего устройства содержит плт АЗЭ 20 (фиг. 1 и 2), первые 21, вторые 22 я третьи 23 разрядные шины, соединенные с одноименными АЗЭ 20. Шины 13 и 17 АЗЭ 20 (кроме первых) подключены к шинам 15 и 16 предыдущих АЗЭ 20 соответственно. В составе накопителя ассоциативного запоминающего устройства АЗЭ работает следующим образом. Запись и считывание признаков про-изводится параллельно по словам по первым разрядным шинам 21. Пример. Поиск Ближайшего большего. При этом в запоминающий элемент 1 каждого АЗЭ 20 эанесено значение (i 1 ,n, j 1 ,m) соответствующе о разряда некоторого ассоциативного признака, причем на первом выходе запоминающего элемента 1 устанавливается прямое,, а на втором инверсное значение этого разряда.Разряды ассоциативных признаков располагаются в словах начиная со старших. На каждую первую разрядную шину 21 подается значение соответствующего разряда признака опроса у. (в прямом коде), а на первых шинах 13 первых в словах АЗЭ 20 устанавливается логическая 1. Обозначим 2;, и Z; . - логические переменные на шинах 13 и 17, J-ro АЗЭ 20 i-ro слова. Тогда на шинах 22 и 23 реализуются (фиг. 2) функции соответственно ., vi Зд .V v,H 1Д а на шинах 15 и 16 этого АЗЭ 20 устанавливаются соответственно функции V . . УзЬ u Ч;.. 4,-.. : Равенство Zj 1 означает, что в пройденных j разрядах данного слова все разряды совпали с разрядами признака опроса. Равенство первого члена дизъюнкции в правой части выражения для Zll логической 1 означает, что J-1 старший разряд ассоциативного признака совпадает с разрядами признака опроса, а j-ый разряд больше, т.е. данное слово - ближайшее большее по старшим j разрядам. Второй или третий члены дизъюнкции равны 1, если данное слово является наименьшим среди ближайших больших по старшим j разрядам и ни для одного из одноименных АЗЭ 20 всех слов первая дизъюнкция не равна 1. Поиск проходит параллельно по словам и разрядам. По окончании переходных процессов состояния на шинах 16 последних в словах АЗЭ 20 фиксируются в детекторах (на чертеже не показаны) . Выполнение равенства 2 1 означает, что t-ык ассоциативный признак - ближайший больший, а выполнение равенства Zi, 1 полностью совпадает с признаком опроса. Можно показать, что АЗЕ 20 также позволяет осуществить полностью параллельный поиск по условиям Ближайший меньший, наибольший и наименьший, больший, меньший, рав ный, а также их инверсиям и комбинациям. Таким образом, испо;1ьзование описанных АЗЭ 20 в накопителе ассоциативного запоминающего устройства подволяет проводить в последнем сложны иды поиска благодаря расширению фун циональных возможностей АЗЭ. Формула изобретения Ассоциативный запоминающий элемен содержащий элемент памяти, элементы И и ИЛИ, первый элемент НЕ и шины уп равления, причем первые входы элементов И подключены к первой шине управ ления, второй вход первого элемента И соединен с первым выходом элемента памяти, второй выход которого подклю чен ко вторым входам второго и третьего элементов И, третьи входы первого и третьего элементов И соединен с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго эл мента Ни второй шине управления, вы ходы первого и второго элементов И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход

20

I I которого подключен к четвертой шине управления, отличающийся тем, что, с целью расширения функциональных возможностей элемента за счет выполнения логических операций, он содержит четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, вторые входы четвертого и пятого элементов И соединены соответственно с выходом второго элемента НЕ и первым выходом элемента памяти, выход пятого элемента и соединен с первым входом шестого элемента И и входом второго элемента НЕ, выход которого подключен к. шестой шине управления, третий вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой шиной управления, выходы третьего и четвертого элементов И подключены соответственно ко входу третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходом шестого элемента И. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 564656, кл. G 11 С 5/00, 1975.. 2.Авторское свидетельство СССР 615543, кл. G 11 С 15/00, 1976 (прототип). й| 1/2

фиг1

f/

гЗ{ 22 1/7

гг

3,