Блок поиска информации для ассоциативного запоминающего устройства Советский патент 1983 года по МПК G11C15/00 

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

входу шестнадцатого элемента И, вы ход которого подключен к второму входу шестого элемента ИЛИ, вторым :входам девятого элемента И и -первого элемента H-flE и третьим входам пятого, десятого и четырнадцатого . и четвертому входу одиннадцатого элементов И, выходы десятого, тринадцатого и четырнадцатого элементов И подключены соответственно к третьему, четвертому и пятому входам первого элемента ИЛИ, выходы второго, третьего и восьмого элементов И подключены к первому, второму и третье|Му входам седьмого элемента ИЛИ, которого подключен к третьему :входу шестого элемента ИЛИ и входу шестого элемента НЕ, выход шестого элемента ИЛИ является шестым вьисодом ,блока, а выход шестого элемента НЕ объединен с вторыми входами пятнадцатого . и иестнадцатого элементов ;И и является седьмым выходом .блока.

БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий два триггера, восемь элементов И, два элемента ИЛИ и три элемента НЕ, причем первые входы первого, второго и третьего .элементов И объединены и являются первым входом блока, первые входы четвертого, пятого и шестого элементов И, первый вход седьмого и вторые входы четвертого и пятого элементов И, первый вход восьмого и вторьте входы первого и третьего элементов И объединены соответст&енно и являются входами блока с второго по четвертый, второй вход восьмого и третий вход третьего элементов И подключены к выходу первого триггера, третий вход первого элемента И подключай к выходу второго триггера, выходы пятого и шестого элементов И подключены соответственно к первом и второму входам первого элемента ИЛИ, выходы .первых элементов И и ИЛИ подключены соответственно к первым входс1М первого и второго триггеров, выход чет вертого элемента И подключен к первому входу второго элемента ИЛИ, второй вход которого является пятым входом блока, а выход подключен к второму входу первого триггера, третий вход первого и второй вход второго триггеров объединены и являются шестым входом блока, отличающ и и с я тем, что, с целью расширения области применения блока за счет увеличения числа критериев поиска, в него введены элемента , элементы И с девятого по шестнадцатый, элементы ИЛИ, элементы НЕ с четвертого по шестой и третий триггер, при;чем первые входы первого и второго элементов И-НЕ и девятого элемента И подключены к первому входу блока, первые входы десятого, одиннадцатого и двенадцатого и второй вход седьмого элементов И подклю-, i чены к второму входу блока, первые входы тринадцатого и четырнадцатого (Л элементов И соединены с третьим входом блока, первые входы третьего и четвертого элементов ИЛИ подключены к пятому входу блока, вторые входы подключены соответственно к выходам 2 двенадцатого и седьмого элементов И, а выходы - к первому.входу третьего и третьему входу второго триггеров, второй вход третьего триггесд ра подключен к шестому входу блока, ч1 третий вход - к выходу одиннадцатого элемента И, а выход - к второму :о входу второго элемента И-НЕ, первые СХ) входы пятого элемента ИЛИ и третьего элемента И-НБ объединены и являются ;о седьмым входом блока, вторые входы подключены к выходу девятого элемента И, . а выходы являются первым и вторым выходами блока, второй вход одиннадцатого и четвертый вход первого элементов И и вход первого элемента НЕ объединены и являются вторым выходом блока, выход первого элемента НЕ подключён к второму входу тринадцатого элемента И, первого элемента И-НЕ соединен с входом второго элемента НЕ и является третьим выходом блока, выход

I

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

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

Однако область применения этого блока ограничена эадачами, в которых требуется поиск максимального (минимального) слова.

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

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

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

Цель изобретения - расширение области применения блока за счет увеличения числа критериев поиска, в частности эа счет выполнения поиска в массиве храни ос признаков

п. а о i4ciut

i xJT, i Г,п, таких признаков что

x etxii ,

Ve ,n-,4,

или

Че-VnvXg-XHtV, где Y - приз нак опроса.

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

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

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

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

Блок поиска информации содержит (фиг.1) элементы И 1-16 с первого по естнадцатый,элементы ИЛИ 17-23 с первого по седьмой, элементы НЕ 24-29 с первого по шестой, первый 30, вто- . рой 1 и третий 32 элементы И-НЕ и первый 33, второй 34 и третий 35 триггеры. Блок имеет входы 36-42 с первого по седьмой, выходы 43-49 & первого по седьмой,.Ассоциативное запоминающее устройство (фиг.2) может содержать ft блоков 50ij-50.t поиска информации/ П регистров 5i-51f хранимых призна-ков с первыми 52 и вторыми 53 выходами и регистр 54 признака опроса с 15 первым 55 и вторым 56 выходами. Выходы 44-47, 49 блоков 50,j-50j, объединены соответственно и через резисторы 57 подключены к шине 58 опорного напряжения. Кроме того, вц.- 20 ходы 49, 47 и 48 блока являются соответственно выходами 59, 60 и б1;(61 у устройства, входами которого являются входы 62-64.

Граф переходов блока поиска ин- 25 формации (фиг.З) имеет четыре вершины 65-68. Рядом с вершинами графа приведены коды состояний блока, в которых двоичные цифры соответствуют (слева направо) состояниям вто- on рого 34., первого 33 и третьего 35 триггеров. М - безразличное состояние второго 34 триггера.

Блок работает следующим образом.

В исходн.ом состоянии сигналом по входу 63 все блоки устанавливаются в состояние 65.

Ассоциативный поиск производится не более чем за tn тактов поразрядного сравнения (т - число разрядов признаков). В каждом j -ом такте 40 (J l,2,,..,J4m) поступают: прямое У) - на вход 38 блока и инверсное У-. - на вход 39 блока значения j -го разряда признака опроса, прямоеZ j на вход 36 и инверсное - на 45 вход 37 блока значения j -го разряда регистра 51, хранимого признака. Признаки в регистрах располагаются таким образом, что веса их разрядов убывают с ростом j .50

В каждом j -ом такте на установочных входах триггеров в&рабатываются сигналы: и RiiV - на входах второго 34, на входах первого 33 и 8- л 55 на входах третьего 35 триггеров, которые определяются следующим образом: 5,..-rvQ,..Zi.fjCj., .,V

60

Ц,)м)-л;,

..,.)v vz j8HvVjAj.,y;

R2,-j-Tv2 - 4iCj.,,

. Rsij- ijCjM,

гда5.14й-1 , - текущие состояния второго 34, первого 33 и третьего 35 триггеров, Т - сигнал начальной установки, А, Bj.f и С|- - текущие состояния на объединенных выходах 44,, 45 и 4.6 блока:

.b,ei П

b.Oi,, - м -учн чПри поступлении, сигнала на вход 64 в триггерах фиксируются новые j-ые состояния блока и начинается j +1-ЫЙ такт поиска.

Результат поиска определяется сигналами на выходах 59-61 устройства. Появ1ление единичного значения функции tp- :

. ,)Dn,, и

,

на выходе 61 означает, что признак х удовлетвор)яет условию поиска.

Результат поиска может быть снят с устройства по окончании Ю тактов поиска, однако в ряде случаев, в зависимости от численных значений признаков, он может быть получен и ранее. Признаком того, что поиск может быть прекращен является появление логического нуля на выходе 59 устройства или логической, единицы на выходе 60 устройства. В первом случае независимо от значений оставшихся, младших разрядов признаков, условию поиска удовлетворяет тот хранимый признак , у которого на соответствующем выходе 61, в данный момент зафиксирована логическая единица (,44j l) Во втором случае появление единичного значения функции

i-iV--i« i

означает, что н1езависимо от оставшихся разрядов условию поиска не удовлетворяет ни один хранимый признак.

Если хранимые признаки записаны в прямсж коде, T.e.2,j x,j , где X ,у - значение j -го разряда признак х,- то в результате поиска выбираются такие признаки х, что

Ч8 Т;«;х;-че Ч.

Если хранимые признаки записаны в инверсном коде, T.e.Vj хл, то в резу|ПЬтате поиска выберутся такие признаки х{, что

Yt