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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

< >955204 (61) Дополнительное к авт. свид-ву— (22) Заявлено 15. 01. 81 (21) 3229541/18-24 с присоединением заявки М— (23) Приоритет—

Опубликовано 30.08.82 ° Бюллетень М9 32

Дата опубликования описания 30 ° 08 ° 82 (51)М Кл з

Сс 11 С 15/00

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681. 327 (088.8) с

В. М. Трусфус, P. Р. Бикмухаметов и С. Л. ТаХаутдинова (72) Авторы изобретения

Казанский ордена Трудового Красного Знамени авиационный институт им. A. Н, Туполева (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

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

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

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

И, выходы которых подключены к детекторам (23.

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

10 нижние границы и длины отрезков, ко-> торые приходится пересчитывать в верхние границы отрезков.

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

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

Каждый блок анализа информации содержит элементы НЕ, вторую группу элементов

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

Каждый логический блок содержит третий, четвертый и пятый элементы

НЕ, третью группу элементов И, элементы ИЛИ, третий и четвертый триггеры, причем первые входы первого и второго элементов И третьей группы подключены к выходу четвертого триггера, первые входы третьего, четвертого и пятого элементов И треть- ей группы — к первому выходу третьего триггера, второй выход которого соединен с первыми входами шестого, седьмого и восьмого элементов И треть З5 ей группы, вторые входы второго, шестого и восьмого элементов И третьей группы соединены с выходом третьего элемента НЕ, вторые входы первого, третьего и пятого элементов И 40 третьей группы — c выходом четвертого элемента НЕ, второй вход четвертого и третьи, входы первого и третьего элементов И третьей группы— с выходом пятого элемента НЕ, третьи 45 входы четвертого и пятого и четвертый вход первого элементов И третьей группы подключены ко входу третьего элемента НЕ, второй вход седьмого ! и третьи входы второго и шестого элементов И третьей группы — к входу четвертого элемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов И третьей группы — к входу пятого элемента НЕ, первый и второй входы третьего триг- 55 гера подключены к выходу первого элемента И третьей группы и выходу первого элемента ИЛИ, первый вход которого соединен с выходом второго элемента И третьей группы, выходы элементов И третьей группы с третьего no восьмой соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу четвертого триггера, второй вход которого соеди 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) записывается входной признак Y. В регистры 2 и 3 записываются. соответственно нижние границы отрезков х „,и„. и длины отрезков K;(i = 1-n) . Нройзводится установка в нулевые состояния триггеров

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, переходят

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

После анализа всех m разрядов чисел Y и xù„ „, находящихся в регист ре 1 и соответствующем регистре 2, триггеры 19 и 20 будут находиться в нулевых состояниях, если Y = x ;„, в состояниях соответственно О и 1, если Y y х,„„.„„ ; в состояниях 1 и О, если Y < х„„„.„; . Отсюда следует, что нулевое состояние триггера 19 будет являться признаком выполнения условия

Y Ъ хпЧп,.

В каждом из блоков 5 при поступлении сигналов из j-ûõ разрядов регистра 1 и соответствующих регистров 2 и

3 определяется значение (В)-, фиксируемое в виде определенного состояния блока 5.

Граф состояний блока 5 включает четыре состояния а,-а4(фиг. 4), в том числе начальное состояние а„; Cq-С сигналы перехода, Значение (В j> = О

Фиксируется в виде состояния, а (В3 = -1 — в виде состоя ия а3. При

Ще11, 2) блок 5 переходит в конечное состояние а, при (В)-с -2, -3)в конечное состояние а4.

Каждое состояние Ълока 5 кодируется определенным набором состояний триггеров 43 и 44: состояние а1 кодируется набором (О, О), а — набором (О, 1), а — набором. (1, О) и а4 — набором (1 1) .

Если блок 5 находится в состоянии а, то пои поступлении на входы 1012 блока 5 любого набора сигналов из множества С„= ((О, О, О), (1, О, 1), (1, 1, 0)3 состояние а„не меняется, при наборе С = (1, О, О) блок 5 переходит в промежуточное состояние а, которое сохраняется при любом наборе из множества С = ((0, О, 1), (О, 1, О), (1, 1, 1) . Из состояния а3 блок 5 переходит в начальное состояние а „под действием набора С 4 =

= (О, 1, 1). Любой набор из множества

С = С UC4 переводит блок 5 из состояния а в конечное состояние а, в котором блок 5 не реагирует на входные сигналы; при лобом наборе из множества С = C О С блок 5 переходит в конечное состояние а4.

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

В = -1, в нулевых состояниях, если

В = О, единичных состояниях, если

В (-1. Следовательно, нулевое состояние триггера 43 будет являться приз< наком выполнения условия В ) О.

Детектор 7 фиксирует одновременное выполнение условий У 7 х,;„„. и х,„,„;—

Y + К > О, что означает вхождейие

Y в соответствующий отрезок .

10

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

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

65. входами шестого, седьмогс и восьмого

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

2. Устройство по п. 1, о т л и ч аЗ5 ю щ е е с я тем, что каждый блок анализа информации содержит элементы

НЕ, вторую группу элементов И и триггеры, причем первые входы первого и второго элементов И второй группы

40 подключены к выходам первого и второго элементов НЕ, вторые входы к входам второго и первого элементов

НЕ, третьи . входы — к выходам первого и второго триггеров, первые входы

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

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

955204 элементов И третьей группы, вторые входы второго, шестого и восьмого элементов И третьей группы соедине,ны с выходом третьего элемента НЕ,вто рые входы первого, третьего и пятого элементов И третьей группы — с выходом четвертого элемента НЕ, второй вход четвертого и третьи входы первого и третьего элементов И третьей группы — с выходом пятого элемента

НЕ, третьи входы четвертого и пятого 10 и четвертый вход первого элементов

И третьей группы подключены к входу третьего элемента НЕ, второй вход седьмого и третьи входы второго и шестого элементов И третьей группы — 15 к входу четвертого элемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов

И третьей группы — к входу пятого элемента НЕ, первый и второй входы 20 третьего триггера подключены к выходу первого элемента И третьей группы и выходу первого элемента ИЛИ, первый вход которого соединен с выходом второго элемента И третьей группы, выходы элементов И третьей группы, с третьего по восьмой, соединены с входами второго элемента

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

Источники информации, принятые во внимание при экспертизе

1. Джозеф, Каплан. Коррелирование трасс целей с помощью памяти поиска, "Зарубежная радиоэлектроника", 1964, Р 1.

?. Авторское свидетельство СССР

М 243659, кл. G 11 С 15/00, 1966 (прототип).