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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик р 11955204(51 М. Кл з Сс 11 С 15/00 Государственный комитет СССР ф по делам изобретений и открытий(72) Авторы изобретения Казанский ордена Трудового Красного Знамени авиационный институт им. А. Н, Туполева(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО2 Изобретение относится к запоминающим устройствам.Известно ассоциативное запоминающее устройство, содержащее регистр входного признака, запоминающие регистры, схемы сравнения и детекторы и выполняющее поиск по принадлежности входного признака к заданным множествам признаков 1.Устройство характеризуется повышенными требованиями к числу запоминающих регистров, необходимых для точного задания множеств признаков. Из известных устройств наиболее близким техническим решением к предлагаемому является ассоциативное запоминающее устройство, содержав 1 ее регистр входного признака, регистры верхних границ отрезков, регистры нижних границ отрезков, первые и вторые схемы сравнения, схемы И и детекторы, причем входы первых схем сравнения подключены к выходам регистра входного признака и соответствующих регистров нижних границ отрезков, входы вторых схем сравнения подключены к выходам регистра входного признака и соответствующих регистров верхних границ отрезков, выходы первых и вторых схем сравнения соединяются с входами соответствующих схемИ, выходы которых подключены к детекторам 23,5 В этом устройстве отрезки задаются указаниетл их границ, что снижаетбыстродействие устройства. В задачахдинамического распределения машиннойпамяти исходными данными являются10 нижние границы и длины отрезков, ко торые приходится пересчитывать вверхние границы отрезков.Цель изобретения - повышение быстродействия ассоциативного запоминающего устройства эа счет реализациипоиска по принадлежности входногопризнака множествам признаков, заданным в устройстве путем указания нижних границ и длин соответствующихотрезков,Поставленная цель достигается тем,что в ассоциативное запоминающее устройство, содержащее регистр признакаопроса, две группы информационныхрегистров, первую группу элементов И,выходы которых подключены к входамдетекторов, введены блоки анализаинформации и логические блоки, первыевходы которых подключены к выходурегистра признака опроса, вторые вхо"ды и выходы одноименных блоков анали 955204за информации и логических блоков соединены соответственно с выходами инФормационных регистров перВой группыи входами элементоэ И первой Группы,третьи входы логических блоков подключены к выходам информационных регистров второй группы.Каждый блок анализа информации содержит элементы НЕ, вторую группу элементовИ и триггеры, причем первые входы первого и второго элементов, Иуторбй группы 10подключены к выходам первого и второго элементов НЕ, вторые входы -к входам второго й первого элементов НЕ, третьи входы - к выходампервого и второго триггеров, первые 15входы которых соединены с выходамивторого и первого элементов И второйгруппы, вторые и третьи входы триггеров объединены соответственно иявляются одними из входов блока, 20другими входами и выходом которогоявляются соответственно входы элементов НЕ и выход первого триггера.Каждый логический блок содержиттретий, четвертый и пятый элементыНЕ, третью группу элементов И, элементы ИЛИ, третий и четвертый триггеры, причем первые входы первогои второго элементов И третьей группы подключены к выходу четвертоготриггера, первые входы третьего,четвертого и пятого элементов И треть-ей группы - к первому выходу третьего триггера, второй выход которогосоединенс первыми входами шестого,седьмого и восьмого элементов И треть З 5ей группы, вторые входы второго,шестого и восьмого элементов И третьей группы соединены с выходом третьего элемента НЕ, вторые входы первого, третьего и пятого элементов И 40третьей группы - с выходом четвертого элемента НЕ, второй вход четвертого и третьи, входы первого и третьего элементов И третьей группы -с выходом пятого элемента НЕ, тРетьи 45входы четвертого и пятого и четвертый вход первого элементов И третьейгруппы подключены ко входу третьегоэлемента НЕ, второй вход седьмогои третьи входы второго и шестогоэлементов И третьей группы - к входучетвертого элемента НЕ, третьи входы седьмого и восьмого и четвертыйвход второго элементов И третьейгруппы - к входу пятого элемента НЕ,первый и второй входы третьего триггера подключены к выходу первогоэлемента И третьей группы и выходупервого элемента ИЛИ, первый входкоторого соединен с выходом второгоэлемента И третьей группы, выходы 60элементов И третьей группы с треть-егопо восьмой соединены с входамивторого элемента ИЛИ, выход которогоподключен к первому входу четвертоготриггера, второй вход которого соеди 65 Нен с вторым входом первого элементаИЛИ, третьи входы третьего и четвертого триггеров объединены и являютсяодним из входов блока, другими входами которого являются второй входпервого элемента ИЛИ и входы третьего, четвертого и пятого элементовНЕ, а выходом - второй выход третьеготриггера. На Фиг. 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) записывается входной признак У. В регистры 2 и 3 записываются,соответственно нижние границы отрезков х ,и и длины отрезков К,(1 = 1-п) . Нройзводится установка в нулевые состояния триггеров 19 и 20 (фиг, 2) блоков 4 подачей сигнала на входы 28 и триггеров 43 и 44 (Фиг. 3) блоков 5 подачей сигнала на входы 45 блоков 5.В процессе поиска по принадлежности входного признака к заданным э устройстве отрезкам информация из регистров 1-3, которые являются, например, сдвигающими, поступает на входы 8 и 9 блоков 4 и входы 10-12 блоков 5 поразрядно, начиная со стар ших Разрядов. В каждом из блоков 4 триггеры 19 и 20 сохраняют нулевые состояния, если сигналы на входах 8 и 9 одинаковы, переходят э состояния соответственно 1 и О, если сигналы на входах 8 и 9 равны соответственно 0 и 1 и сохраняют эти состояния. при поступлении любых последующих сигналов на входи 8 и 9, переходятв состояния 0 и 1, если сигналы на входах 8 и 9 равны 1 и 0 и сохраняют эти состояния при любых последующих сигналах на входах 8 и 9.После анализа всех в разрядов чисел У и х,1, , находящихся в регистре 1 и соответствующем регистре 2, триггеры 19 и 20 будут находиться в нулевых состояниях, если У = хп 1 в состояниях соответственно 0 и 1, если У ) х, ; в состояниях 1 и О, если Ух; , Отсюда следует, чтонулевое состояние триггера 19 будет являться признаком выполнения условия У Ъ хв 1В каждом из блоков 5 при поступлении сигналов из 3-ых разрядов регистра 1 и соответствующих регистров 2 и 3 определяется значение (В 1 , фиксируемое в виде определенного состояния блока 5.Граф состояний блока 5 включает четыре состояния а,-а(фиг. 4), в том числе начальное состояние а; С-СЬ- сигналы перехода, Значение (В) = 0 Фиксируется в виде состояния, а;(В 3 = -1 - в виде состоя ия а 3. При (В)е 11,2) блок 5 переходит в конечное состояние а, при (В 3 с -2, -3)- в конечное состояние а 4,Каждое состояние Ълока 5 кодируется определенным набором состояний триггеров 43 и 44: состояние а 1 кодируется набором (О, 0), а - набором (О, 1), а- набором.(1, 0) и а, - набором (1, 1)Если блок 5 находится в состоянииа, то пои поступлении на входы 10- 12 блока 5 любого набора сигналов из множества С = (0, О, 0), (1, 0 1) (1, 1, 0)3 состояние я не меняется, при наборе С 1 = (1, О, 0) блок 5 пеоеходит в промежуточное состояние а 3, которое сохраняется при любомнаборе из множества С= (0, О, 1), (О, 1, 0), (1, 1, 1 Д . Из состоянияа 3 блок 5 переходит в начальное состояние апод действием набора С 4 = = (О, 1, 1). Любой набор из множества С= СОС 4 переводит блок 5 из состояния а в конечное состояние а, в котором блок 5 не реагирует на входные сигналы; при любом наборе из множества Сь = СО С 1 блок 5 переходит в конечное состояние а 4.После анализа всех щ разрядов чисел, записанных в регистре 1 и.соответствующих регистрах 2 и 3, триггеры 43 и 44 блока 5 будут находиться в состояниях соответственно 0 и 1, если В ) О, в состояниях 1 и О, если В = -1, в нулевых состояниях, если В = О, единичных состояниях, если В ( -1. Следовательно, нулевое состояние триггера 43 будет являться признаком выполнения условия В ) О.Детектор 7 фиксирует одновременное выполнение условий У Ъ хопи и хс 1 п,У + К ъ О, что означает вхождейие У в соответствующий отрезок.51 О Применение в предлагаемом устройстве нового вида поиска, выявляющего принадлежность входного признака к отрезкам, заданным их нижними границами и длинами, позволяет значительно повысить быстродействие ассоциативного запоминающего устройства. формула изобретения 15 65 входами шестого, седьмого и восьмого 1. Ассоциативное запоминающее устройство, содержащее регистр признакаопроса, две группы информационныхрегистров, первую группу элементов И,выходы которых подключены к входам .детекторов, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия,оно содержит блоки анализаинформации и логические блоки, первыевходы которых подключены к выходурегистра признака опроса, вторые входы и выходы одноименных блоков анализа информации и логических блоков соединены соответственно с выходами информационных регистров первой группыи входами элементов И первой группы,третьи входы логических блоков подключены к выходам информационных регистров второй группы.2. Устройство по п, 1, о т л и ч а 35 ю щ е е с я тем, что каждый блоканализа информации содержит элементыНЕ, вторую группу элементов И и триггеры, причем первые входы первогои второго элементов И второй группы40 подключены к выходам первого и второго элементов НЕ, вторые входык входам второго и первого элементовНЕ, третьи . входы - к выходам первого и второго триггеров, первые входы45 которых соединены с выходами второгои первого элементов И второй группы,вторые и третьи входь триггеров объединены соответственно и являютсяодними из входов блока, другими вхо 5 О дами и выходом которого являются соответственно входы элементов НЕ ивыход первого триггера,3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что каждый логический блок содержит третий, четвертый и пятый элементы НЕ, .третьюгруппу элементов И, элементы ИЛИ,третий и четвертый триггеры, причемпервые входы первого и второго элементов И третьей группы подключенык выходу четвертого триггера, первыевходы третьего, четвертого и пятогоэлементов И третьей группы - к первому выходу третьего триггера, второйвыход которого соединен с первымиэлементов И третьей группы, вторыевходы второго, шестого и восьмогоэлементов И третьей группы соедине,ны с выходом третьего элемента НЕ,вторые входы первого, третьего и пятогоэлементов И третьей группы - с выходом четвертого элемента НЕ, второйвход четвертого и третьи входы первого и третьего элементов И третьейгруппы - с выходом пятого элементаНЕ, третьи входы четвертого и пятого 10и четвертый вход первого элементовИ третьей группы подключены к входутретьего элемента НЕ, второй входседьмого и третьи входы второго ишестого элементов И третьей группы - 15к входу четвертого элемента НЕ,третьи входы седьмого и восьмогои четвертый вход второго элементовИ третьей группы - к входу пятогоэлемента НЕ, первый и второй входы 20третьего триггера подключены к выходу первого элемента И третьей группы и выходу первого элемента ИЛИ,первый вход которого соединен с выходом второго элемента И третьей группы, выходы элементов И третьей группы, с третьего по восьмой, соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу четвертого триггера, второй вход которого соединен с вторым входом первого элемента ИЛИ, третьи входы третьего и четвертого триггеров обьединены и являются одним из входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы третьего, четвертого и пятого элементов НЕ, а выходом - второй выход третьего триггера.Источники информации,принятые во внимание при экспертизе1, Джозеф, Каплан. Коррелированиетрасс целей с помошью памяти поиска,. Авторское свидетельство СССРМ 243659, кл. 6 11 С 15/00, 1966