Ассоциативное запоминающее устройство Советский патент 1974 года по МПК G11C15/00 

1

Изобретение относится к области запоминающих устройств.

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

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

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

выходы (Которого подключены к другим входам дополнительной матрицы ассоциативных признаков, а входы - к выходам введенного в устройство дополнительного регистра опроса, подключенного к блоку управления.

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

Оно содержит матрицу 1 ассоциативных признаков, первичные индикаторы совпадения 2, схемы 3 фиксации режима по числу запоминающих ячеек матрицы 1, счетчики 4, осуществляющие вычитание до нуля и суммирование, дополнительную матрицу 5 ассоциативных признаков, дополнительный регистр маски 6, дополнительный регистр опроса 7, вторичные индикаторы совпадения 8, триггер

знака 9, блок 10 формирования режима, блок управления 11, регистр опроса 12, регистр маски 13, вход 14 для записи кодовых последовательностей в регистр опроса, вход 15 установки режима, входы 16 схем фиксации

режима, входы 17, 18 счетчиков.

Входы 19 и 20 болка 10 формирования режима подключены соответственно к триггеру знака 9 и к первичным индикаторам совпадения 2, а выходы - ко входам 16 схем 3 фиксации режима и ко входу 17 счетчиков 4. Входы 18 счетчиков подсоединены к блоку управления И, входы 21 -к выходам схем 3 фиксации режима, а выходы - к одним входам дополнительной матрицы 5 ассоциативных признаков, выходы которой связаны со входами индикаторов8. Входы 22 схем 3 подключены к соответствующим выходам первичных индикаторов совпадения 2. Выходы регистра 6 соединены с другими входами матрицы 5, а входы - с выходами регистра 7, связанного с блоком управления 11.

i стройство раоотает следующим образом.

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

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

Перед началом каждого цикла ассоциативного поиска в массиве поисковых образов на вход триггера знака 9 записывается О или 1 в зависимости от того, входит ли в поисковый образ запроса ассоциативный признак или его инверсия, а на вход 15 установки режима блока iO формирования режима подается признак первого или второго режима формирования ответа, выбираемого для запроса в целом.

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

Выбор режима формирования ответа определяется уровнем поисквого щума в устройстве и спецификой обрабатываемой информации.

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

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

При ассоциативном поиске на входы 14 регистра опроса 12 засылается двоичная кодовая последовательность, соответствующая одному из признаков, входящих в запрос, и одновременно в триггер знака 9 засылается признак наличия или отсутствия знака инверсии у соответствующего ассоциативного признака.

Признаки опроса из регистра опроса 12 через регистр маски 13 подаются на входы матрицы 1 ассоциативиых признаков, причем маскируются те разряды, в которых в признаке опроса записаны нули.

Если ассоциативный признак входит в поисковый образ без знака инверсии, то выдается импульс на входы 18 тех счетчиков 4, которым соответствуют возбужденные индикаторы совпадения 2, и содержимое счетчиков увеличивается на единицу. Затем в регистр, опроса 12 засылается кодовая последовательность очередного ассоциативного признака, входящего в текущий запрос, и цикл ассоциативного поиска повторяется.

Таким Образом, в результате полного цикла ассоциативного поиска в каждом счетчике 4 устанавливается некоторое число.

Рассмотрим режим извлечения многозначного ответа после окончания цикла ассоциативного поиска по заданному запросу.

Содержимое счетчиков 4 переписывается в дополнительную матрицу 5 ассоциативных признаков, после чего с помощью блока управления И, дополнительного регистра опроса 7, дополнительного регистра маски 6 и вторичных индикаторов совпадения 8 может быть выполнен ассоциативный поиск уже в массиве результатов ассоциативпого поиска в заданном диапазоне допустимых значений результата с использованием одного из известных алгоритмов упорядоченной выборки.

Предмет изобретения

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

Т

12

13