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

 

Изобретение относится к вычислительной технике, преимущественно к запоминающим устройствам, построенным на ассоциативном принципе и применяемым для реализации комбинаторных задач, задач анализа графов, задач оценки надежности сложных систем, задач эквивалентных преобразований булевых функций и в ряде других случаев. Цель изобретения - расширение области применения элемента за счет увеличения числа критериев поиска. Ассоциативный запоминающий элемент содержит элемент ИЛИ 1, элемент И 2, элемент И-НЕ 3 и элемент 4 памяти. В устройстве, построенном из данных ассоциативных запоминающих элементов, реализуется поиск по признакам "равно", "больше", "меньше", принадлежность множества единичных разрядов хранимого числа подмножеству множества единичных разрядов поискового признака. 2 ил, 1 табл.

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (5)) 4 G 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТИ-ЦЩ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Il0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР

1 (2)) 4345359/24-24 (22) 17,13.87 (46) 30.1.1 ° 89. Бюл. У 44 (72) О,П.Орлов, Ю,А.Бурмистрова и С.Ю.Шоркина (53) 681.327{088.8) (56) Кохонен Т. Ассоциативные заноминающие устройства. М.: Мир, 1982, с. )59.

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

)) 5)3392, кл. С 11 С 15/00, 1973. (54) АССОЦИАТИВНЬП) ЗАПОМИНАЮЩИЙ ЭЛЕМЕНТ (57) Изобретение относится к вычислительной технике, преимущественно к запоминающим устройствам, построенным на ассоциативном принципе и применяемым для реализации комбина„„ЯК„,.1525745 д1

2 торных задач, задач анализа графов, задач оценки надежности сложных систем, задач эквивалентных преобраэо— вателей булевых функций и в ряде других случаев. Цель изобретения— расширение области применения элемента за счет увеличения числа критериев поиска..Ассоциативный запоминающий элемент содержит элемент ИПН

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

1525745

Зн ач ение кодов

Результаты сравнен .я

"i I

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

Цель изобретения — расширение области применения элемента за счет увеличения числа критериев поиска.

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

Ассоциативный запоминающий эле мент (фиг. 1) содержит элемент ИЛИ 1, . элемент И 2, элемент H-НЕ 3, элемент, 4.памяти, инверсный вход 5 маски,, вход 6 переноса, вход 7 признака по:иска, прямой вход 8 маски, выход 9 переноса и выход.10 результата поис: ка.

Ассоциативная матрица памяти (фиг. 2) содержит. мартрицу из пмтп ассоциативных запоминающих..элементов

11 (где и - количество слов; m — количество разрядов), парафазные разрядные шины 12, 13 маски соответственно, разрядную шину 14 признака

;поиска, шину 15, выход 16 переноса и выход 17 результата поиска, Ассоциативный запоминающий элемент 11 матрицы ассоциативного запоминающего устройства работает следующим образом.

Запись и считывание признаков производятся с помощью цепей записи— считывания, которые строятся так же, как и при использовании известных ассоциативных ячеек памяти (на фиг,l не показаны).

Признак поиска (число А) в прямом коде поступает с шины 14 на вход 7 элемента, само слово (число В) из памяти поступает на элемент ИЛИ 1 в .элемент И-НЕ 3 в инверсном коде с элементом 4 памяти, При маскировании разряда на соответствуюцую шину 12 поступает код уровня единицы, а на шину 13 — код уровня нуля. Если маскирование не требуется, то на данные шины подаются сигналы, инверсные указанным выше. На шину 15 подается код уровня единицы.

В каждом из элементов 11 выполняется сравнение значения кода числа В хранящегося в элементах 4 памяти, со" значением признака поиска А.

Сравнение осуществляется одновременно во всех строках матрицы после-; довательно, по разрядам, начиная со старшего разряда.

При сравнении кодов двух чисел имеют место соответствующие комбинации сигналов на выходах 16, 17 ассоциативной запоминаюц|ей матрицы, при.веденные в таблице, При этом, если A) В и i " номер старшего разряда (i l, m), в котором сравниваемые числа различаются, то на выходе 17 матрицы формируется

II l t

0, которыи определяется кодом нуля на выходе 10 i-ro элемента 11. Этот нулевой код вызван тем, что на оба входа соответствующего. элемента И 2 поступают коды .уровня "1" с выхода

И 2 (i-1)-ro разряда и с выхода ИЛИ1

25 данного разряда. Коды уровня единицы, установленные на входе элемента И-HE

3, формируют "0" на его выходе и, соответственно, на выходе 10 i-ro элемента 11, 35

0 1 А В ВсА

0 0 . А>В BgÀ

1 0 А<В ВФА

1 1 А=В ВфА

Если А < В, то на выходе 17 матрицы формируется код уровня "1", а на выходе 16 — "0", так как с выхода элемента ИЛИ 1 на вход элемента И 2

45 пОступает уровень нуля кОтОРый формирует нулевой код на выходе элемента И 2 i-ro элемента 11, Этот сигнал переносится по цепи элементов И 2 всех более младших разрядов на выход

l7 матрицы, а с выходов всех соответствующих элементов И-НЕ 3 поступает код уровня единицы, так как на одном из их входов всегда будет "0", что определит единичный код -на выходе 17 матрицы.

Пусть А = В, в этом случае во всех разрядах с выхода элемента ИЛИ 1 код уровня единицы поступает на вход элемента И 2, а на другой его вход пос-1525745

6 тупает уровень единицы с выхода И 2 предыдущего разряда. Таким образом, на выходе 17 и, соответственно, на выходе 16 будет.код уровня "1", Принадлежность множества единичных разрядов хранимого чиспа В подмножеству единичных разрядов признака поиска А рассматривается следующим образом. 1О

Наличие кода уровня единицы на выходе 16 свидетельствует о том, что во всех сравниваемых разрядах не встречается случай, где В 1, а А = 0 сопровождающийся, как указывалось 15 ранее, кодом уровня "О" на выходе 16.

Следовательно, при любом уровне кода на выходе 17 матрицы можно утверждать, что "1" на выходе 16 означает Вс А, Нулевой уровень на выходе

16 соответствует В ФА.

Формула изобретения

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

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

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