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

 

п1 4708б2

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

> " толик (61) Зависимое от авт. свидетельства (22) Заявлено 18.04.74 (21) 2016694/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15 05.75. Бюллетень ¹ 18

Дата опубликования описания 27.08.75 (51) М. 11л. G 11с 15, 00

Гастдарственнье камнтет

Севвта Мннистрав СССР аа делам изааретеннй и аткрытий

,53) УДК 681.327.6 (088.8) (72) Авторы изобретения

Л. М. Метрик и А. Ю. Гурьев (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

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

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

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

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

На чертеже представлена блок-схема предлагаемого устройства.

Устройство содержит первую матрицу 1 ассоциативных признаков, первичные индикато1о ры совпадения 2, счетчики 3, вторую матрицу

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

10 подсчета числа ответов, второй регистр опроса 11, второй регистр маски 12, входы для записи кода состояний 13, условий переходов 14, элементы «ИЛИ» 15, основные 16 и дополнительные 17 элементы «И» и блок па2О мяти 18.

Вход каждой ячейки блока памяти 18 соединен с выходом соответствующего элемента

«ИЛИ» 15, один вход которого подключен к элементу «И» 16, а другой — к элементу «И»

25 17.

Информационные входы элементов «И» 16 соединены с выходами вторичных индикаторов совпадения 5, информационные входы элементов «И» 17 соединены с выходами счетчиЗо ков 3, управляющие входы элементов «И» 16

470862

3 и 17 соединены с блоком управления 7, Выходы блока памяти 18 подключены ко входам !3 регистра опроса 8. лементы «И» 1б, 17, «ИЛИ» 15 и блок памяти 18 образуют блок

19 формирования признака перехода.

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

13 матрицу i ассоциативпых признаков записывается информация о последовательности функционирования устройства управления автоматом (на чертеже это устроистыо не показано) . Каждое слово ы ма грице ассоциативных признаков соответствует переходу автомата из одного состояния в другое по некоторому значению входного сигнала, определяемому конъюнкцl:åé сигналоы, поступающих на входы 13 для записи кодов состояний и на входы 14 для записи условий переходов регистра опроса 8. и ячеики блока памяти 15 заносятся коды состояний автомата. 1 ак как в - -автомате функция выхода и функция перехода задают соответственно Fмножество на множестве выходных сигналов и Е-множество на множестве состояний, то для того, чтобы определить функциопироыание

1" -автомата, надо задать спосоо выбора элемента в i -ìíîæåñòâå состояний, определяющего состояние, в которое переходит Е-автомат на каждом такте.

11римем следующий способ выбора: выбор по максимальному числу, записанному в счетчиках 3 в результате ассоциативного поиска по заданному поисковому образу запроса.

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

Двоичные кодовые последовательности ассоциативных признаков, соответствующих внешним условиям, поступают на входы 14 регистра опроса 8 и через регистр маски 9 — на входы матрицы i ассоциативных признаков, а на входы 13 регистра опроса поступает из блока 19 формирования признака перехода двоичная кодовая последовательность ассоциативного признака, определяемая состоянием автомата, по которой выполняется последний цикл поиска для заданного поискового образа запроса, причем счетчики 3 для всех строк матриц 1 и 4, кроме тех, для которых фиксируется совпадение в этом цикле поиска, устанавливаются в нуль по сигналу из блока управления 7.

Следовательно, в счетчиках 3, соответствуюгцих строкам матрицы 1 ассоциативных признаков, в которых зафиксировано совпадение с кодом состояния, к окончанию цикла поиска по заданному поисковому образу запроса накапливается число, равное сумме весов ассоциативных признаков.

Затем в зависимости от результата работы блока 10 подсчета числа ответов возможны три режима дальнейшей работы.

Первый режим.

Если число счетчиков 3, изменивших свое состояние, равно нулю, то в этом случае принимается, что переход в F-автомате по заданному поисковому. образу запроса невозможен, и, следовательно, поисковый образ запроса должен быть изменен.

Второй режим. 1 олько один счетчик 3 меняет свое состояние. В этом случае Е-множество состояний переходов вырождается до одного элемента, и код состояния перехода определяется непосредственно, минуя вторую матрицу ассоциативных признаков 4. 11о сигналу из блока управления 7 выходы счетчиков 3 подсоединяются через элементы «И» 17 и элементы

«ИЛИ» 15 ко входам блока памяти 18, и выбирается соответствующая ячейка блока памяти, определяющая состояние, в которое пер еходит F- авто м ат.

1 р етий режим.

Число счетчиков, изменивших свое состояние, больше 1. Ы этом случае содержимое с.етчиков 3 переписывается во вторую матрицу. ассоциативных признаков 4, после чего с помощью блока управления 7, второго регистра опроса 11, второго регистра маски 12 и вторичных индикаторов совпадения 5 выполняется ассоциативный поиск по максимуму в массиве, переписанном во вторую матрицу ассоциативных признаков 4, После окончания поиска сигнал с соответствующего вторичного индикатора совпадения 5, поступающий через элемент «И» 16 и элемент «ИЛИ» 15 в блок памяти 18, определяет в соответствии с принятым выше способом выбора состояние, в которое переходит F-автомат.

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

Лссоциативное запоминающее устройство, содержащее первую и вторую матрицы ассоциативных признаков, входы которых подключены к выходам соответствующих регистров маски, связанных с регистрами опроса, а выходы — ко входам первичных и вторичных индикаторов совпадения соответственно, счетчики, выходы которых подключены ко второй матрице ассоциативных признаков и блоку подсчета числа ответов, о т л и ч а ю щ е е с я тем, что, с целью расширения области примеvåïèÿ, оно содержит элементы «ИЛИ» и основные и дополнительные элементы «И» по количеству счетчиков и блок памяти, выходы которого подключены ко входам первого регистра опроса, а входы — к выходам элементов «ИЛИ», входы которых соединены с выходами элементов «И», управляющие входы которых подключены к блоку управления, информационные входы основных элементов «И» соединены с соответствующими выходами вторичных индикаторов совпадения, а информационные входы дополнительных элементов

«И» — с выходами соответствующих счетчиков.

470862

Составитель В. Рудаков

Техред 3. Тараненко Корректор И. Позняковская

Редактор B. Нанкина

Типография, пр. Сапунова, 2

Заказ 1992/12 Изд. № 1446 Тираж 648 Подписное

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

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