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

 

АССОЦИАТИВНЫЙ ЗАПОМИНАЮЩИЙ ЭЛЕИданТ, содержащий триггер, шесть элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего элементов И, первые входы четвертого и пятого элементов И соответственно объединены и являются первым и вторым входами элемента вход первого элемента НЕ, выход которого подключен к второму входу первого элемента И, является третьим входсда элемента, второй вход четвертого элемента И является четвертым входом элемента, выход первого элемента ИЛИ, первый и второй входы которого подключены соответственно к выходам первого и второго элементов И, лвляется первым выходом элемента, выход второго элемента ИЛИ, первый, второй и третий входы котброго. подключены соответственно к выходам третьего,.четвертого и шестого элементов И, является, вторым выходом элемента, первый выход триггера подключен к вторым входам второго и третьего элементов И, отличающийся тем, что, с делью повышения быстродействия элемента, в него введены элементы И-НЕ, элементы И с седьмого по двадцать восьмой, третий и четвертый элементы ИЛИ и элементы НЕ с четвертого по одиннадцатый, причем первые входы седьмого, восьмого, девятого , десятого и одиннадцатого элементов И и первого элемента. И-НЕ второй вход шестого элемента .И,вход Третьего элемента НЕ и вход четвертого элемента БЕ, выход которого подключен к первому входу двенадцатого элемента И, соединены с первым входом элемента, первые входы тринадцатого и четырнадцатого элементов И и второго элемента И-НЕ и вход второго элемента НЕ подключены к второму входу элемента, первьае входа пятнадцатого, шестнадцатого, семнадцатого , восемнадцатого, девятнадцатого , двадцатого, двадцать первого и двадцать второго, вторые входы «Л восьмого, девятог.о и десятого и третьи входы четвертого и шестого элементов И и выходы третьего и чет .вертого элементов И-НЕ соединены с третьим входом элемента, вторые входы пятого, тринадцатого, шестнад-. цатого, семнадцатого, восемнадцатого , двадцатого и двадцать второго, третьи входы первого, восьмого, девя-того .и десятого и четвертый вход on шестого элементов и, выходы первого Ч и второго элементов И-НЕ и вход пятого элемента НЕ, выход которого подключен к вторым входам пятнадцатого 00 и девятнадцатого элементов И сое динены с четвертым входом элемента, первые входы двадцать третьего, двадцать четвертого и двадцать пятого, вторые входы одиннадцатого и двенадцатого , третьи входы третьего, семнадцатого и двадцатого и четвертый вход девятого элементов и, выходшестого элемента НЕ и вход седьмого элемента НЕ, выход которого подключен к первому входу двадцать шестого, второму входу седьмого, третьему входу шестнадцатого и четвертому входу восьмого элементов И, соедине

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

»

РЕСПУЬЛИН (392 (И2

3(59 G 11 С 15 00

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

Го ДЕЛАМ ИЗОБРЕТЕ)4ИЙ И ОТКРЫТИЙ с

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2 1) 3497753/18- 24 (22) 29. 09 82 (46) 30,11.83.. Вюл. 22 44 (72) В.Б. Матвеев (71) Казанский ордена Трудового

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

22 424141 кл. G ll С 15/00 1972.

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

22 788177 кл. G 11 С 15/ОО 1979 (прототип) ° (.54)(57) АССОЦИАТИВНЫЙ ЗАПОМИНАЮЩИЙ

ЭЛЕМЕНТ, содержаший триггер,.шесть элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего элементов И, первые входы четвертого и пятого элементов И соответственно объединены и являются первым и вторым входами элемента вход первого элемента НЕ, выход-которого подключен к второму входу первого элемента

И, является третьим входом элемента, второй вход четвертого- элемента И является четвертым входом элемента, выход первого элемента ИЛИ, первый и второй входы которого подключены соответственно к выходам первого и второго элЕментов И, является первым выходом элемента, выход второго элемента ИЛИ, первый, второй и третий входы которого подключены соответственно к выходам третьего,.четвертого и шестого элементов И, является. вторим выходом элемента, первый выход триггера подключен к вторым входам второго и третьего элементов

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

I второму входу элемента, первые входы пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнад- + цатого., двадцатого, двадцать первого !9 и двадцать второго, вторые входы восьмого, девятого и десятого и третьи входы четвертого и шестого элементов И и выходы третьего и четвертого элементов И-НЕ соединены с третьим входом элемента, вторые входы пятого, тринадцатого, шестнадцатого, семнадцатого, восемнадцатого, двадцатого и двадцать второго, третьи входы первого, восьмого, девя-того .и десятого и четвертый вход шестого элементов И, выходы первого и второго элементов И-НЕ и вход пятого элемента НЕ, выход которого под-.. ключен к вторым входам пятнадцатого и девятнадцатого элементов И; соединены с четвертым входом элемента, первые входы двадцать третьего, двадцать четвертого и двадцать пятого, вторые входы одиннадцатого и двенадцатого, третьи входы третьего, сем- Ъ) надцатого и двадцатого и четвертый вход девятого элементов И, выход шестого элемента HE и вход седьмого элемента НЕ, выход которого подключен к первому входу двадцать шестого, второму входу седьмого, третьему входу шестнадцатого и четвертому входу восьмого элементов И, соедине1057988 ны с пятым входом элемента, вторые входы двадцать третьего и двадцать четвертого элементов И, выход третьего элемента НЕ и вход восьмого элемента НЕ, выход которого подключен к третьему входу восемнадцатого и первому входу двадцать седьмого элементов И, объединены и являются шестым входом элеменга, третьи входы одиннадцатого и двенадцатого элемен-, тов И, выход девятого элемента НЕ и вход десятого элемента НЕ, выход которого подключен к третьему входу второго и четвертому входу десятого

/ элементов И объединены и чвляются седьмым входом элемента, первый вход третьего элемента И-НЕ, . торые входы двадцать пятого, двадцать шестого и двадцать седьмого, третьи входы пятнадцатого и двадцать четвертого и четвертые входы шестнадцатого,сем надцатого, восемнадцатого и двадцатого элементов И, вход девятого элемента НЕ и вход одиннадцатого эле-„ мента НЕ, выход которого подключен к третьему входу двадцать третьего элемента И, объединены и являются восьмым входом элемента, первый вход двадцать восьмого, второй вход двадцать первого и третьи входы девятнадцатого и двадцать второго элементов И, первый вход четвертого элемента И- IE и выход шестого элемента НЕ объединены и являются девятыМ входом элемента, третьи входы тринадцатого, двадцать первого, двадцать пятого и двадцать шестого, четвертые входы второго, двенадцатого и пятнадцатого и пятые входы девятого, десятого, > шестнадцатого и двадцатого элементов

И объединены и являются десятым axодом элемента, третьи входы пятого, седьMoro и двадцать седьмого, четвертые входы первого, третьего, девятнадцатого и двадцать третьего и пятые входы шестого, восьмого, семнад1

Изобретение относится к автоматике и вычислительной технике, s частности к ассоциативным запоминающим устройствам.

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

И, выход четвертого элемента ИЛИ является четвертым выходом элемента, первый, второй, третий, четвертый, пятый и шестой входы четвертого элемента ИЛИ подключены соответственно к выходам двадцатого, двадцать первого, двадцать второго, двадцать четвертого, двадцать пятого и двадцать восьмого элементов И, первый выход триггера подключен к второму входу четырнадцатого, четвертым входом седьмого и одиннадцатого и пятому входу двадцать третьего элементов

И и вторым входам первого и второго элементов И-НЕ, второй выход триггера подключен к второму входу двадцать восьмого, четвертым входам двадцать четвертого, двадцать пятого, двадцать шестого и двадцать седьмого и пятому входу двенадцатого элементов И и вторым входам третьего и четвертого элементов И-НЕ, выходы седьмого, восьмого, девятого, десятого, тринадцатого и двадцать третьего элементов И подключены соответственно к третьему, четвертому, пятому, шестому, седьмому и восьмому входам первого элемента ИЛИ, выходы пятого, одиннадцатого и четырнадцатого элементов И подключены соответственно к четвертому, пятому и шестому входам второго элемента ИЛИ, а четвертый вход тринадцатого элемента И, подключен к выходу первого элемента НЕ.

2 мента подклк>чен к второму входу второго элемента ИЛИ, выход которого подключен к четвертому выводу элемента, а пятый вывод элемента подклю5 чен к входу элемента НЕ, выход которого подключен к второму входу nepsoro элемента И, выход которого под.ключен к второму входу первого элемента ИЛИ, выход которого подключен о к шестому выводу элемента (1) .

Недостатком элемента является пониженное быстродействие при выполнении более сложных видов поиска, чем поиск максимума или минимума.

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

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

Поставленная цель достигается тем, что в ассоциативный запоминающий элемент, содержащий триггер, шесть элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего элементов И,. первые входы четвертого и пятого .элементов И соответственно объединены и являются первым и вторым. входами элемента, вход первого элемента НЕ, выход которого подключен к второму входу первого элемента И, является третьим входом элемента, второй вход четвертого элемента И является четвертым входом элемента, выход первого элемента ИЛИ, первый и второй входы которого подключены соответственно к выходам первого и второго элементов И, является первым выходом элемента, выход второго элемента ИЛИ, первый, второй и третий входы которого подключены соответственно к выходам третьего, четвертого и шестого элементов И, яв. ляется вторым выходом элемента, пер вый выход триггера подключен к вторым входам этараго и третьего элементов И, введены элементы H-НЕ,элементы И с седьмого па двадцать socbмой; третий и четвертый элементы ИЛИ и элементы НЕ с четвертага по одиннадцатый, ричем первые входы седьмого, восьмага, девятого, десятого и одиннадцатого элементов И и первого элемента И-HE второй вход шес10 того элемента И, вход третьего элемента НЕ и вход четвертого элемента НЕ, выход которого подключен к первому входу двенадцатого элемента И соединены с первым входом эле15 мента, первые входы тринадцатого и четырнадцатого элементов И и второго элемента И-НЕ и вход второго элемента НЕ подключены к второму входу элемента, первые входы пятнад цатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двадцатого, двадцать первого и двадцать второго, вторые входы восьмого, девятого и десятого и третьи входы четвертого н шестого элементов И и выходы третьего и четвертого элементов И-НЕ, соединены с третьим вхо дом элемента, вторые входы пятого, тринадцатого, шестнадцатого, семнадцатога, восемнадцатого, двадцатого и двадцать второго, третьи входы первого, восьмого, девятого и десятого и четвертый вход шестого элементов И, выходы первого и второго элементов И-НЕ и вход пятого элемен35 та НЕ, выход которого подключен к вторым входам пятнадцатого и девятнадцатога элементов И соединены с четвертым входом элемента, первые входы двадцать третьего, двадцать

4п четвертого и двадцать пятого, вторые входы одиннадцатого и двенадцатого, третьи входы третьего, семнадцатого и двадцатого и четвертый вход девятого элементов И, выход шестого эле45 мента НЕ и вход седьмого элемента НЕ, выход которого подключен к первому входу двадцать шестого, второму входу седьмого, третьему входу шестнадцатого и четвертому входу восьмого элементов И соединены с пятым входом элемента, вторые входы двадцать третьего и двадцать четвертого элементов И, выход третьего элемента НЕ и вход восьмого элемента НЕ, выход которого подключен к третьему входу

55 восемнадцатого и первому входу двадцать седьмого элементов И объединены и являются шестым входом элемента, третьи. входы одиннадцатого и двенадцатого элементов И, выход де60 вятага элемента НЕ и вход десятого элемента НЕ, выход которого подключен к третьему входу второго и четвертому входу десятого элементов И объединены и являются седьмым вха65 дам элемента, первый вход третьего

1057988 элемента И-НЕ, вторые входы двадцать пятого, двадцать шестого и двадцать седьмого, третьи входы пятнадцатого и двадцать четвертого и четвертые входы шестнадцатого,. семнадцатого, восемнадцатого и двадцатого элементов И, вход девятого элемента HE u вход одиннадцатого элемента НЕ, выход которого подключен к третьему входу двадцать третьего элемента И, объединены и являются восьмым входом элемента, первый вход двадцать восьмого, второй вход двадцать первого и третьи входы девятнадцатого и двадцать второго элементов И, первый вход четвертого элеме |та И-HE u

f0

)5 выход шестого элемента H? объединены и являются девятым входо элемента, третьи входы тринадцатого, двадцать первого, двадцать пятого и двадцать шестого, четвертые входы второго, двенадцатого и пятнадцатого и пятые

20 цать седьмого элементов И, выход чет-40 входы девятого, десятого, шестнадцатого и двадцатого элементов И объединены и являются десятым входом элемента, третьи входы пятого, седьмого и двадцать седьмого, четвертые входы первого, третьего, девятнадцатого и двадцать третьего и пятые входы шестого, восьмого, семнадцатого и восемнадцатого элементов И объединены и являются одиннадцатым входом элемента, выход третьего элемента

ИЛИ является третьим выходом-элеменчены соответственно к выходам двенадцатого, пятнадцатого, шестнадцатого, семнадцатого, восемнадцатого, девятнадцатого, двадцать шестого и двадвертого элемента ИЛИ является четвер тым выходом элемента, первый, второй третий, четвертый, пятый и шестой входы четвертого элемента ИЛИ подклю рого, двадцать четвертого, двадцать пятого и двадцать восьмого элементов

И, первый выход триггера подключен к второму входу четырнадцатого, четвертым входам седьмого и одиннадцатого и пятоМу входу двадцать третьего элементов И и вторым входам первоro и второго элементов И-НЕ, .второй выход триггера подключен к второму входу двадцать восьмого, четвертым входам двадцать четвертого, двадцать пятого, двадцать шестого и двадцать

55 седьмого и пятому входу двенадцатого элементов И и вторым входам третьего и четвертого элемен гов И-НЕ, выходы

60 седьмого, восьмого, девятого, десятого, тринадцатого и двадцать третьего . элементов И подключены соответственно к третьему, четвертому, пятому, шестому, седьмому и восьмому входам чены соответственно к выходам двадца 45 того, двадцать первого, двадцать втопервого элемента ИЛИ, выходы пятого, одиннадцатого и четырнадцатого элементов И подключены соответственно к четвертому, пятому и шестому входам

t второго элемента ИЛИ, а четвертый вход тринадцатого элемента И подклю чен к выходу первого элемента HE.

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

Ассоциативный запоминающий элемент (фиг.1) содержит триггер 1, элементы

И 2-29 с первого по двадцать восьмой, элементы ИЛИ 30-33 с первого по четвертый, элементы HE 34-44 с первого по одиннадцатый и элементы

И-НЕ 45-48 с первого по четвертый.

Элемент имеет входы 49-53 с первого по пятый, первый 54 и второй

55 выходы, входы 56-61 с шестого по одиннадцатый, третий 62 и четвертый

63 выходы.

Накопитель ассоциативного запоминающего устройства содержит h ° m . элементов 64 (фиг.2), = 1,Л, j.= 1, Входы 49, 50, 58 и 59 всех элементов, кроме первых в словах (j=1), подключенЫ соответственно к выходам

54, 55, 62 и 63 предыдущих в словах элементов. Входы 57, 56, 53, 51, 52, 60 и 61 подключены соответственно к первым 65, вторым 66, третьим 67, четвертым 68, пятым 69, шестым 70 и седьмым 71 .одноименным (no j ) разрядным шинам.

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

В составе накопителя ассоциативного запоминающего устройства запоминающий элемент работает следующим образом.

Хранимые признаки записываются в словах накопителя в порядке убывания разрядных весов: на первом выходе триггера 1 элемента 64 устанавливается прямое х;, а на второминверсное ij /x значения -го разряда

1--ro хранимого признака. На шестые

70 и седьмые .71 разрядные шины подаются прямые у и инверсные у значения разрядов признака опроса также и порядке убывания разрядных весов. На входы l9, 50, 58 и 59 первых в словах элементов подается уровень логического нуля. Разрядные шины 65-69 через резисторы (не показаны) подключаются к источнику опорного напряжения, тем самым на них реализуется функция монтажное. ИЛИ-НЕ

Накопитель ассоциативного запоминающего устройства (за исключением

1057988 триггеров 1, которые в процессе поис ка своего состояния не меняют) представляет собой итеративную комбинационную логическую сеть, в которой ассоциативный поиск осуществляется за один такт,- причем поиск иницииру. ется изменением логической переменной на любом из входов накопителя или изменением состояния любого триггера 1. При этом на выходах 54, 55, 62 и 63 -го элемента « --го сло ва вырабатываются соответственно .функции ot.,>, P,>, ;« и о, а на

j-1-ых первой 65, второй 66, третьей ,67, четвертой 68 и пятой 69 разряд,ных шинах вырабатываются соответственно функции Aj « Вj-« С j-,. Dj « и Е, которые определяются следующими выражениями«

« « = 3«i$-« "« >) 8) «С -«ч«х«, -«("« 1 С -«ч чх«)3)4) «ч 9 «Е «ч« )С -«)) «Е «Ч

" С)-«О; «Е;«ч 4.,0 «Еj-«1чp««Ч Эф ;,, p >=««t,1.« Х; 4 .«Cj « «ÕфС .,Ч С; 0 «

"E>-«1Ч.p, 1,(х; Ч р .,ч Э «

/.

Ц % g««y J$ $ «$«ЦА«1 3)Cj«

Ч Х; p) «ч) О .«Е,ч Cj.«Ý., Еj. Ч ч JJ)Cj «D) « ч Cg «D)«E)«Ч ч 6 0 .«Е j« Ч 6;,у р

Ч «3-« Ч )« «Ч 3-» 4 ) Ñ) «0j«Ej«)V 8< - «(Я; Ч Q V

ЧР;,Е 1

4Ь= 1;,;, «1

«,1-««

С.,=Ч (; -,ч8; «., Е5, Ч X«3(g«13«рч-(1Ъ

I где о ;,> «,P« « ",;, и 8,, „- логи-

1О ческие Функции соответственно на выходах 54, 55, 62 и 63 соответствен- . но « -1-ro элемента « --го слова.

Результат поиска определяется как Функция состояний на выходах 54, 55, 62 .и 63 последнего в слове элемента, а также на последних первой

65, второй 66 и третьей 67 разрядных шинах: (; =Р; Ч,8; ч (Р; ч У„„, С„„V A,„В„,С,„, причем равенство (f« логической едини.це означает, что признак Х, удовлет,воряет условию поиска.

Отметим, что в накопителе, пост«роенном на предлагаемых элементах, может быть осуществлен и просто поиск максимальных и минимальных хранимых признаков. Для этого первые

65, вторые бб и третьи 67 разрядные шины подключаются к источнику пита30 ния логического нуля, а на шестые

70 и седьмые 71 разрядные шины и на входы 49 и. 58 цервых в словах элементов подается уровень логической единицы. Появление логической едини35 цы на выходах 54 или 62 последнего в слове элемента означает, что в данном слове записан соответственно максимальный или минимальный в масси. ве хранимый признак.

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

1057988

1057988 бд б7 бб

Фиа2

Составитель В. Рудаков .Редактор О. Сопко Техред g, Тепер Корректор А. Ференц

Заказ 9586/53 Тираж 594 Подписное

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

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

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