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

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

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

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

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

В этом устройстве отрезки задаются указанием их гранит;, что снижает быстродействие устройства. 3 задачах динамического распределения машинной памяти исходными данными являются нижние границы и длины отрезкЪв, ко- торые ПРИХОДИТСЯ пересчитывать в верхние границы отрезков.

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

20

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

25 выходы которых подключены к входам детекторов, введены блоки анализа информации и логические блоки, первые входу которых подключены к выходу регистра признака опроса, вторые входы и выходы одноименных блоков анализа инфоомации и логических блоков соединены соответственно с выходами информационных регистров перйой группы и входами элементов И первой гРУППЫ, третьи входы логических блоков подклюКены к выходам информационных регистров второй группы.

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

Каждый логический блок содержит третий, четвертый и пятый элементы НЕ, третью группу элементов И, элементы ИЛИ, третий м четвертый триггеры, причем nepBbie входы первого и второго элементов И третьей группы подключены к выходу четвертого триггера, первые входы третьего, четвертого и пятого элементов И третьей группы к первому выходу третьего триггера, второй выход которого соединенс первыми входами шестого, седьмого и восьмого элементов И треть ей группы, вторые входы второго, шестого и восьмого элементов И третьей группы соединены с выходом третьего элемента НЕ, вторые входы первого, третьего и пятого элементов И третьей группы - с выходом четвертого элемента НЕ, второй вход четверто-го и третьи; входы первого и третьего элементов И третьей группы с выходом пятого элемента НЕ, третьи входы четвертого и пятого и четвертый вход первого элементов И третьей группы подключены ко входу третьего элемента НЕ, второй вход седьмого и третьи входы второго и шестогсэ элементов И третьей группы - к входу четвертого элемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов И третьей группы - к входу пятого элемента НЕ, первый и второй входы третьего триггера подключены к выходу первого элементаИ третьей группы и выходу первого элемента ИЛИ, первый вход которого соединен с выходом второго элемента И третьей группы, выходы элементов И третьей группы с треть его по ВОСЬМОЙ соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу четвертого триггера, второй вход которого соедиНен с вторым входом первого элемента ИЛИ, третьи входы третьего и четвертого тригг еров объединены и являются одним из входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы третьего, четвертого и пятого элементов НЕ, а выходом - второй выход третьего триггера.

На фиг. 1 изображена функциональная схема ассоциативного запоминающего устройства; на фиг. 2 и 3 функциональные схемы блока анализа информации и логического блока; на фиг, 4 показан граф состояний логического блока.

Ассоциативное запоминающее устройство (фиг. 1) содержит регистр 1 принака опроса, первую и вторую группы информационных регистров 2 и 3 соответственно, блоки 4 анализа информации, логические блоки 5, первую группу элементов И 6 и 7. Блоки 4 и 5. имеют входы 8-12 и выходы 13 и 14. Каждый блок 4 (фиг. 2) содержит первый 15 И второй 16 элементы НЕ, вторую группу элементов И, состоящую из первого 17 и второго 18 элементов И, первый 19 и второй 20 триггеры. Триггер 20 имеет выход 21. Триггеры имеют входы 22-27. Каждый блок 4 имеет входы 28 и 29. Каждый блок 5 (фиг. 3) содержит третий 30, четвертый 31 и пятый 32 элементы НЕ, третью группу элементов И 33-40 (с первого 33 по восьмой 40), первый 41 и второй 42 элементы ИЛИ, третий 43 и четвертый 44 триггеры. Блок 5 имеет входы 45 и 46.

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

В регистр 1 (фиг. 1) записывается входной признак Y. В регистры 2 и 3 записываются.соответственно нижние границы отрезков х.,- и длины отрезков К-(i 1-п). Производится установка в нулевые состояния триггеров 19 и 20 (фиг. 2) блоков-4 подачей сигнала на входы 28 и триггеров 43 и 44 (фиг. 3) блоков 5 подачей сигнала на входы 45 блоков 5.

В процессе поиска по принадлежности входного признака к заданным в устройстве отрезкам информация из регистров 1-3, которые являются, например, сдвигающими, поступает на входы 8 и 9 блоков 4 и входы 10-12 блоков 5 поразрядно, начин„ая со cтap ших разрядов,.В каждом из блоков 4 триггеры 19 и 20 сохраняют нулевые состояния, если сигналы на входах 8 и 9 одинаковы, переходят в состояни соответственно 1 и О, если сигналы на входах 8 и 9 равны соответственно О и 1 и сохраняют эти состояния, при. поступлении любых последующих с игналов на входы 8 и 9, переходят

в состояния о и 1, если сигналы на входах 8 и 9 равны 1 и О и сохраняют эти состояния при любых последующих сигналах на входах 8 и 9.

После анализа всех m разрядов чисел У и х,-„, находящихся в регистре 1 и. соотаетствуюкем регистре 2, триггеры 19 и 20 будут находиться р нулевых состояниях, если Y Xniini в состояниях соответственно О и 1, если Y X(T,ini состояниях 1 и О,

если Y

. Отсюда следует, что

(тч п 1

нулевое состояние триггера 19 будет являться признаком выполнения условия Y - .

В каждом из блоков 5 при поступлении сигналов из j-ых разрядов регистра 1 и соответствующих регистров 2 и 3 определяется значение В, фиксируемое в виде определенного состояния блока 5.

Граф состояний блока 5 включает четыре состояния . 4, в том числе начальное состояние а.,; с -Сесигналы перехода. Значение О фиксируется в виде состояния, B3j -1 - в виде состояния а. При ,2 блок 5 переходит в конечное состояние arj, при В.), -3Jв конечное состояние а4

Каждое состояние блока 5 кодируется определенным набором состояний триггеров 43 и 44: состояние а кодируется набором (О, 0), а, набором f О , 1), а J - набором.. (1, 0) и а - набором (1, l)v

Если блок 5 находится в состоянии а, то при поступлении на входы 1012 блока 5 любого набора сигналов из множества С-, ((0, О, 0), (1, О, 1), (1, 1, 0) состояние а не меняется, при наборе С- (1, О, 0) блок 5 пепеходит в промежуточное состояние Bj, которое сохраняется при любом наборе из множества Сз {(О, О, 1), (О, 1, 0), (1, 1, 1)}. Из состояния aj блок 5 переходит в начальное состояние а под действием набора С4 (О , 1, 1). Любой набор из множества С5 CjUC переводит блок 5 из состояния а в конечное состояние а,, в котором блок 5 не реагирует на входные сигналы; при любом наборе из множества С, ,j блок 5 переходит в конечное состояние а4.

После анализа всех m разрядов чисел, записанных в регистре 1 и. соответствующих регистрах 2 и 3, триггеры 43 и 44 блока 5 будут находиться в состояниях соответственно О и 1, если В О, в состояниях 1 и О, если В -1, в нулевых состояниях, если В О, единичных состояниях, если В -1. Следовательно, нулевое состояние триггера 43 будет являться приэ наком выполнения условия В О.

Детектор 7 фиксирует одновременное выполнение условий Y -г/ х,- и Хп, + К 7/ О, что означает вхождение в соответствующий отрезок.

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

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

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

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

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

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

к выходу четвертого триггера, первые входы третьего, четвертого и пятого элементов И третьей группы - к первому выходу третьего триггера, второй выход которого соединен с первыми входами шестого, седьмого и восьмого элементов И третьей группы, вторые входы второго, шестого и восьмого элементов И третьей группы соедине.ны с выходом третьего элемента НЕ,в рые входы первого, третьего и пятог элементов И третьей группы - с выхо .дом четвертого элемента НЕ, второй вход четвертого и третьи входы перв го и третьего элементов И третьей группы - с выходом Пятого элемента НЕ, третьи входы четвертого и пятог и четвертый вход первого элементов И третьей группы подключены к входу третьего элемента НЕ, второй вход седьмого и третьи входы второго и шестого элементов И третьей группы к входу четвертого элемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов И третьей группы - к входу пятого элемента НЕ, первый и второй входы третьего триггера подключены к выходу первого элемента И третьей тру пы и выходу первого элемента ИЛИ, первый вход которого соединен с выходом второго элемента И .третьей группы, выходы элементов И третьей группы, с третьего по восьмой, соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу четвертого триггера, второй вход которого соединен с вторым входом первого элемента ИЛИ, третьи входы третьего и четвертого триггеров объединены и являются одним из входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы третьего, четвертого и пятого элементов НЕ, а выходом - второй выход третьего триггера. Источники информации, принятые во внимание при экспертизе 1.Джозеф,Каплан. Коррелирование трасс целей с помощью памяти поиска, Зарубежная радиоэлектроника, 1964, № 1. 2.Авторское свидетельство СССР № 243659, кл. G 11 С 15/00, 1966 (прототи т .