Ассоциативный запоминающий элемент

Союз Советских Социалистических РеспубликОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ н 11788177Ф(51)М. Кл. с присоединением заявки Мо(23) Приоритет С 11 С 15/00 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 17180(72) Авторы изобретения В. Б. Матвеев и В. М. Трусфус Казанский ордена Трудового Красного Знамени авиационный институт им. А. Н, Туполева(54) АССОЦИАТИВНЫЙ ЗАПОМИНАЮЩИЙ ЭЛЕМЕНТ Изобретение относится к запоминающим устройствам.Известен ассоциативный запоминающий элемент (АЗЭ), содержащий элементы памяти, логические элементы и блок сравнения 1 .Недостатком этого элемента является большое количество выводов.Наиболее близким техническим решением к предлагаемому является АЗЭ, 1 О содержащий запоминающий элемент, схему пробега по равенству, входы которой подключены к первому и второму выходам запоминающего элемента, первому и второму выводам АЗЭ, а выход 15 подключен к третьему выводу АЗЭ, пер" вый элемент И, входы которого подключены через элемент НЕ к первому и непосредственно ко второму выводам АЗЭ и первому выходу запоминающего 20 элемента, а выход подсоединен к первому входу элемента ИЛИ, выход которого подключен к четвертому выводу АЗЭ 2 Недостатками этого АЗЭ являются ограниченные функциональные возможности, не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска. ЗО 2Цель изобретения - расширение функциональных возможностей элемента за счет выполнения логических операций.Поставленная цель достигается тем, что в ассоциативный запоминающий элемент, содержащий элемент памяти, элементы И и ИЛИ, первый элемент НЕ и шины управления, причем первые входы элементов И подключены к первой шине управления, второй вход первого элемента И соединен с первым выходом элемента памяти, второй выход которого подключен ко вторым входам второго и третьего элементов И, третьи входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго элемента И и второй шине управления, выходы первого и второго элементов И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входомвторого элемента ИЛИ, выход которого подключен к четвертой шине управления, введены четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, вторые входычетвертого и пятого элементов И соединены соответственно с выходом второго элемента НЕ и первым выходом элемента памяти, выход пятого элемента И соединен с первым входом шестого алемента И и входом второго элемента, НЕ, выход которого подключен к шестой шине управления, третий вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой шиной управления, 10 выходы третьего и четвертого элементов И подключены соответственно ко вхОду третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходом шес того элемента И.На фиг. 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 соединены с выхо дом элемента НЕ 10, вход которого подключен ко входу элемента 1 памяти, третьему входу элемента И 3 и к шине 14. Выходы элементов И 2 и 3 соединены со входами элемента ИЛИ 8, выход 4 О которого подключен к шине 15. Выход элемента И 4 соединен с первым входом элемента ИЛИ 9, выход которого подключен к шине 16. Первые входы эле" ментов И 5 и 6 подключены к шине 17, вторые входы элементов И 5 и 6 соеди" 4 иены соответственно с выходом элемента НЕ 11 и первым выходом элемента 1 памяти. Выход элемента И б соединен с первым входом элемента И 7 и входом элемента НЕ 11, выход которого подключен к шине 18. Третий вход элемента И 5 и второй вход элемента И 7 соединены с выходом элемента НЕ 12 и шиной 19. Выходы элементов И 4 и ф подключены соответственно ко вхо- Я ду элемента НЕ 12 и второму входу элемента ИЛИ 9, третий вход которого соединен с выходом элемента И 7. Накопитель ассоциативного эапоми нающего устройства содержит паАЗЭ 20 (фиг. 1 и 2), первые 21, вторые 22 и третьи 23 разрядные шины, соединенные с одноименными АЗЭ 20.Шины 13 и 17 АЗЭ 20 (кроме первых) б 5 подключены к шинам 15 и 16 предыдущих АЗЭ 20 соответственно.В составе накопителя ассоциативного запоминающего устройства АЗЭработает следующим образом.Запись и считывание признаков про"изводится параллельно по словам попервым разрядным шинам 21.П р и м е р, Поиск "Ближайшегобольшего". При этом в запоминающийэлемент 1 каждого АЗЭ 20 занесено значение х (1 = 1,и, 1 = 1,в) соответствующего разряда некоторого ассоциативного признака, причем на первом выходе запоминающего элемента 1устанавливается прямоеа на втором -инверсное значение этого разряда.Разряды ассоциативных признаков располагаются в словах начиная со старших.На каждую первую разрядную шину 21подается значение соответствующегоразряда признака опроса у (в прямом коде), а на первых шинах 13первых в словах АЗЭ 20 устанавливается логическая 1 Обозначим 2, иЦ2,- логические переменные на ши нах 13 и 17, 1-го АЗЭ 20 -го слова,Тогда на шинах 22 и 23 реализуются(фиг. 2) функции соответственноо15 = Л , 2 хух;а на шинах 15 и 16 этого АЗЭ 20 устанавливаются соответственно функцииг; д - 2(х, у.,ч ху, ),2 хуч 2 х Цч 5 3Равенство 2 = 1 означает, чтоФ 5в пройденных ) разрядах данного слова все разряды совпали с разрядамипризнака опроса. Равенство первогочлена диэъюнкции в правой части выражения для 2" логической "1" озна 4чает, что -1 старший разряд ассоциативного признака совпадает с разрядами признака опроса, а -ый разряд -больше, т,е. данное слово - ближайшее большее по старшимразрядам.Второй или третий члены дизъюнкцииравны "1", если данное слово является наименьшим среди ближайших боль"ших по старшим ) разрядам и ни дляодного из одноименных АЗЭ 20 всехслов первая дизъюнкция не равна "1".Поиск проходит параллельно по словам и разрядам. По окончании переходных процессов состояния на шинах16 последних в словах АЗЭ 20 фиксируются в детекторах (на чертеже не показаны). Выполнение равенства 2" = 1цЧозначает, что -ый ассоциативный признак - ближайший больший, а выполнение равенства 2 = 1 полностью совпадает с признаком опроса.Можно показать, что АЗЕ 20 такжепозволяет осуществить полностью параллельный поиск по условиям "Ближайший меньшийф, "наибольший" и "наи 788177меньший", "больший", "меньший", "равный", а также их инверсиям и комбинациям.Таким образом, использование описанных АЗЭ 20 в накопителе ассоциативного запоминающего устройства позволяет проводить в последнем сложные иды поиска благодаря расширению функциональных возможностей АЗЭ.Формула изобретенияОАссоциативный запоминающий элемент, содержащий элемент памяти, элементы И и ИЛИ, первый элемент НЕ и шины управления,причем первые входы элементов И подключены к первой шине управления, второй вход первого элемента И соединен с первым выходом элемента памяти, второй выход которого подключен ко вторым входам второго и тре тьего элементов И, третьи входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен ко входу элемента памяти, третьему входу второго эле мента И и второй шине управления, выходы первого и второго элементов И соединены со входами первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выходЯ 7 1го Ь 3Е 21 которого подключен к четвертой шинеуправления, о т л и ч а ю щ и й с ятем, что, с целью расширения функциональных возможностей элеМента засчет выполнения логических операциЯ,он содержит четвертый, пятый и шестой элементы И и второй и третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, вторыевходы четвертого и пятого элементовИ соединены соответственно с выходомвторого элемента НЕ и первым выходомэлемента памяти, выход пятого элемента И соединен с первым входом шестого элемента И и входом второго элемента НЕ, выход которого подключен к.шестой шине управления, третий входчетвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой шиной управления, выходы третьего и четвертогоэлементов И подключены соответственноко входу третьего элемента НЕ и второму входу второго элемента ИЛИ, третий вход которого соединен с выходомшестого элемента И.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9 564656, кл. С 11 С 5/00, 1975.2. Авторское свидетельство СССР9 615543, кл. С 11 С 15/00, 1976788177Составитель В. РудаковГук Техред И,Табакович Ко ректор Е. Паппб Редак Заказ 62 Подписноеного комитета СССРений и открытийРаушская б 4 58361/60 Тираж ВНИИПИ Государствпо делам изобре 113035, Москва, Ж