Ассоциативное запоминающее устройство

О П И С А Н И Е (и) 450232ИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Соме Оеввтскик Социалистических Реелублик(22) Заявлено 12.06.73 (21) 1931423/18-24с присоединением заявки51) Л 1 с 1500 Госуларственный коми Совета Министров СС 32) Приоритетпублнковано 15. етень4тий опубликования описания 11.06.75 72) Авторы изобретения. М, Метрик и А. ье 1) Заявитель 8,т В 54) АССОЦИАТИВНОЕ ЗАПОМИНАЮ ТРОЙС входам тх приз о в уст опроса Изобретение относится к области запоминающих устройств.Известно ассоциативное запоминающее устройство, содержащее матрицу ассоциативныхпризнаков, входы которой подключены к выходам регистра маски, связанного с регистром опроса, а выходы - ко входам соответствующих первичных индикаторов совпадения,счетчики, подсоединенные к блоку формирования режима и блоку управления, и вторичные 10индикаторы,Недостатком известного устройства является то, что оно неприменимо для решения общей задачи ассоциативного поиска, если число ассоциативных признаков превышает разрядность матрицы ассоциативных признаков,Известное устройство также обладает невысоким быстродействием.Описываемое устройство отличается от известного тем, что оно содержит схемы фиксации режима по числу запоминающих ячеекматрицы, одни входы которых подключены квыходам соответствующих первичных индикаторов совпадения, другие - к блоку формирования режима, а выходы - ко входам счетчиков, дополнительную матрицу ассоциативныхпризнаков, одни входы которой подсоединены к выходам соответствующих счетчиков, авыходы - ко входам вторичных индикаторовсовладения, дополнительный регистр маски, 30 выходы которого подключены к другим дополнительной матрицы ассоциативнь иаков, а входы - к выходам введенног ройство дополнительного регистраподключенного к блоку управления.Указанные отличия позволяют расширить область применения устройства, а также повысить его быстродействие.На чертеже изображена блок-схема ассоциативного запоминающего устройства.Оно содержит матрицу 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. Вхо5 10 60 65 ды 18 счетчиков подсоединены к блоку управления 11, входы 21 - к выходам схем 3 фиксации режима, а выходы - к одним входам дополнительной матрицы 5 ассоциативных признаков, выходы которой связаны со входами индикаторов 8. Входы 22 схем 3 подключены к соответствующим выходам первичных индикаторов совпадения 2, Выходы регистра б соединены с другими входами матрицы 5, а входы - с выходами регистра 7, связанного с блоком управления 11.стройство раоотает следующим образом.Ассоциативный поиск по запросу, представляющему сооой булевую функцию от входящих в него ассоциативных признаков, выполняется за несколько циклов, причем число циклов равно числу ассоциативных признаков, входящих в запрос,11 оисковые ооразы закодированы сжатой двоичной кодовой последовательностью, полученной посредством логического сложения двоичных кодовых последовательностей ассоциативных признаков, определяющих поисковые образы объектов поиска.11 еред началом каждого цикла ассоциативного поиска в массиве поисковых образов на вход триггера знака 9 записывается О или 1 в зависимости от того, входит ли в поисковый образ запроса ассоциативный признак или его инверсия, а на вход 15 установки режима блока 1 О формирования режима подается признак первого или второго режима формирования ответа, выбираемого для запроса в целом.Введение двух режимов формирования ответа при ассоциативном поиске обусловлено тем, что ассоциативный поиск ведется в массиве поисковых образов, закодированных сжатой двоичной кодовой последовательностью, дающей поисковый шум.Выбор режима формирования ответа определяется уровнем поисквого шума в устройстве и спецификой обрабатываемой информации.При поиске в первом режиме, когда в поисковом образе, встречающемся в одной или нескольких ячейках матрицы 1 ассоциативных признаков, имеется ассоциативный признак, который входит в поисковый образ запроса со знаком инверсии, соответствующие ячейки из дальнейшего поиска по данному запросу исключаются установкой в определенное состояние схемы 3 фиксации режима, относящейся к этой ячейке, по сигналу, подаваемому на входы 16 схем 3 фиксации режима. Во втором режиме, когда в поисковом образе, записанном в одной или нескольких ячейках матрицы ассоциативных признаков, встречается ассоциативный признак, который входит в поисковый образ запроса со знаком инверсии, из соответствующего счетчика 4 по сигналу, подаваемому па входы 17, вычитаетя единица,15 20 25 30 35 40 45 50 55 При ассоциативном поиске на входы 14 регистра опроса 12 засылается двоичная кодовая последовательность, соответствующая одному из признаков, входящих в запрос, и одновременно в триггер знака 9 засылается признак наличия или отсутствия знака инверсии у соответствующего ассоциативного признака,Признаки опроса из регистра опроса 12 через регистр маски 13 подаются на входы матрицы 1 ассоциативных признаков, причем маскируются те разряды, в которых в признаке опроса записаны нули.Если ассоциативный признак входит в поисковый образ без знака инверсии, то выдается импульс на входы 18 тех счетчиков 4, которым соответствуют возбужденные индикаторы совпадения 2, и содержимое счетчиков увеличивается на единицу, Затем в регистр, опроса 12 засылается кодовая последовательность очередного ассоциативного признака, входящего в текущий запрос, и цикл ассоциативного поиска повторяется.Таким образом, в результате, полного цикла ассоциативного поиска в каждом счетчике 4 устанавливается некоторое число.Рассмотрим режим извлечения многозначного ответа после окончания цикла ассоциативного поиска по заданному запросу.Содержимое счетчиков 4 переписывается в дополнительную матрицу 5 ассоциативных признаков, после чего с помощью блока управления 11, дополнительного регистра опроса 7, дополнительного регистра маски 6 и вторичных индикаторов совпадения 8 может быть выполнен ассоциативный поиск уже в массиве результатов ассоциативного поиска в заданном диапазоне допустимых значений результата с использованием одного из известных алгоритмов упорядоченной выборки,Предмет изобретения Ассоциативное запоминающее устройство, содержащее матрицу ассоциативных признаков, входы которой подключены к выходам регистра маски, связанного с регистром опроса, а выходы - ко входам соответствующих первичных индикаторов совпадения, счетчики, подсоединенные к блоку формирования режима и блоку управления, и вторичные индикаторы совпадения, о тл и ч а ю щ ее с я тем, что, с целью повышения быстродействия устройства и расширения области его применения, оно содержит схемы фиксации режима по числу запоминающих ячеек матрицы, одни входы которых подключены к выходам соответствующих первичных индикаторов совпадения, другие - к блоку формирования режима, а выходы - ко входам счетчиков, дополнительную матрицу ассоциативных признаков, одни входы которой подсоединены к выходам соответствующих счетчиков, а выходы - ко входам вторичных индикаторов совпадения, дополниКорректор Л. Орлова Редактор Б. Капкина Заказ 1328/20 Изд, Мо 1238 Тираж 591 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5Типография, пр. Сапунова, 2 тельный регистр маски, выходы которого подключены к другим входам дополнительной матрицы ассоциативных признаков, а входы - к выходам введенного в устройство дополнительного регистра опроса, подключенного к блоку управления.