Блок поиска информации для ассоциативного запоминающего устройства

 

БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ . АССОЦИАТИВНОГО ЗАЛОМИНАЩЕГО УСТРОЙСТВА , содержащий первый и второй триггеры, элементы И с первого по третий, элемент ИЛИ и элемент НЕ, причем первый выход второго триггера подключен к первому входу первого элемента И, выход элемента НЕ подключен к первому входу второго элемента И, первь1е входы первого и второго триггеров, второй вход второго элемента И и первый вход третьего элемента И являются соответственно входами блока с первого по четвертый, отличающийся тем, что, с целью повьшения быстродействия блока, в него введены -элементы И с четвертого по шестой, причем третий вход второго элемента и первый вход четвертого элемента И являются пятьм входом блока , выход второго элемента И подключен ко второму входу второго триггера , второй вход четвертого элемента И является шестым входом блока, а выход подключен к первому входу элемента ИЛИ, выхор которого подключен к второму входу первого триггера, а второй вход - к выходу первого элемента И второй .вход которого подключен к выходу третьего элемента И, второй вход которого является седьмым входом блока, выход первого триггера под (Л ключен к первому входу пятого элемента И, выход которого является вторым выходом блока, а второй вход подключен к четвертому входу блока, первый вход шестого элемента И подключен к выходу первого триггера , а выход является третьим выходом блока, второй вход шестого ел элемента И подключен к второму выхосо со ду второго триггера, третьи входы первого и второго триггеров подключены соответственно к второму и ел первому входам блока, вход элемента со НЕ подключен к шестому входу блока.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

4(51) G 11 С 15 00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3625034/24-24 (22) 15.07.83 (46) 30,04.85, Бюл. У 16

;(72) В.Б.Матвеев (71) Казанский ордена Трудового Красного Знамени и ордена Дружбы народов авиационный институт им.А.Н.Туполева (53) 681.327(088.8) (56) 1.Фостер К. Ассоциативные параллельные процессоры. Пер. с англ. М,, Энергоиздат, 1981, с.137, рис.5. 15.

2. Conference on computers systems and technology. London,ТЕЕ, 1974, р. 180-184 (прототип), (54) (57) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ .

АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий первый и второй триггеры, элементы И с первого по третий, элемент ИЛИ и элемент НЕ, причем первый выход второго триггера подключен к первому входу первого элемента И, выход элемента НЕ подключен к первому входу второго элемента И, первые входы первого и второго триггеров, второй вход второго элемента И и первый вход третьего элемента И являются соответственно входами блока с первого по четвертый, отличающийся тем, что, с целью повышения быстродействия блока, в него введены

„„Я0„„1153359 А.элементы И с четвертого по шестой, .причем третий вход второго элемента и первый вход четвертого элемента И являются пятым входом блока, выход второго элемента И подключен ко второму входу второго триггера, второй вход четвертого элемента И является шестым входом блока, а выход подключен к первому входу элемента ИЛИ, выход которого подключен к второму входу первого триггера, а второй вход — к выходу первого элемента И, второй .вход которого подключен к выходу третьего элемента И, второй вход которого является седьмым входом блока, выход первого триггера подключен к первому входу пятого элемента И, выход которого является вторым выходом блока, а второй вход подключен к четвертому входу блока, первый .вход шестого элемента И подключен к выходу первого триггера, а выход является третьим выходом блока, второй вход шестого элемента И подключен к второму выхо-. ду второго триггера, третьи входы первого и второго триггеров подключены соответственно к второму и первому входам блока, вход элемента

НЕ подключен к шестому входу блока.

4 11533

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

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

Нецостаток этого устройства— невозможность осуществления поиска условных экстремумов.

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

ИЛИ вЂ , элемент И-НЕ и элемент

НЕРАВНОЗНАЧНОСТЬ, причем первый вход блока подключен к первому входу первого триггера, выход которого подключен к первому выходу бло- 25 ка, второй вход блока подключен к первому входу второго триггера, выход которого подключен к второму входу первого триггера и к перво— му входу элемента И вЂ” НЕ, выход которого подключен к второму выходу блока, а второй вход соединен с первым входом элемента ИЛИ-HЕ и подключен к выходу элемента НЕРАВНОЗНАЧНОСТЬ, первый и второй входы которого под— ключены к третьему и четвертому входам блока, пятый вход блока под †ключен к второму входу элемента

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

НЕРАВНОЗНАЧНОСТЬ содержит, например, два элемента НЕ,два элемента И и элемент ИЛИ,причем первый вход элемента НЕРАВНОЗНАЧНОСТЬ подключен к первому входу первого элемента

И и входу первого элемента НЕ, второй вход элемента НЕРАВНОЗНАЧНОСТЬ подключен к первому входу второго элемента И и входу второго элемента НЕ, выходы первого и второго элементов НЕ подключены к вторым

- входам соответственно второго и первого элемента И, а выходы элементов И подключены к входам элемента ИЛИ, выход которого подключен к выходу элемента НЕРАВНОЗНАЧНОСТЬ„ а элементы И-HE и ИЛИ-НЕ содержат, например, последовательно соединенные, элементы И и НЕ и элементы

ИЛИ и HE 2).

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

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

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

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

l)53359 блока, вход элемента НЕ подключен( к шестому входу блока, На фиг.l изображена функциональная схема блока;на фиг,2 — схема ассоциативного запоминающего устройст— ва, в которое входят предложенные блоки, на фиг.3 — граф состояний и переходов блока поиска информации, поясняющий его работу.

Блок поиска информации содержит первый 1 и второй 2 триггеры, элементы И 3-8 с первого по шестой, эле— мент ИЛИ 9 и элемент HE 10, входы

ll-l7 блока, поиска информации с первого по седьмой и выходы 18-20 блока с первого по третий.

В ассоциативном запоминающем устройстве (фиг,2) на предложенных блоках 21 поиска информации первые и вторые входы подключены соответственно к установочному входу 22 и входу 23 синхронизации, третьи и шестые входы подключены к выходам соответствующих регистров

24 хранимых признаков, пятые и

25 седьмые входы подключены к выходам регистра 25 опроса, первые и третьи выходы являются соответственно первыми 26 и вторыми 27 выходами аесоциативного запоминающе(го устрой- 30 ства, а четвертые входы и вторые выходы объединены и подключены че.—

/ рез резистор 28 к источнику 29 опорного напряжения.

Граф (фиг ° 3) отражает состояния

30-32 с первого по третье и возможные переходы в блоке поиска информации. Рядом с вершинами графа приведены двоичные коды, соответствующие состояниям первого 1 и 4Q второго 2 триггеров (слева направо) при данных состояниях блока поиска информации, Блок поиска информации для ассоциативного запоминающего устрой- 45 ства работает следующим образом.

В исходном состоянии сигналом начальной установки по входу 22 триггеры 1 и 2 устанавливаются в состояния, соответствующие вершине 50

30 графа, Весь поиск занимает ш тактов (где m — разрядность признаков), в каждом из которых.с регистров 24 и 25 считываются очередные разряды (начиная со старших), анализируются с учетом предыдущих состояний,в блоках 21 н по синхросигналу с входа ((Ц ) Ц 1()) i) 1-4) и ((=й (U;1 ), I где U;, j= Х;,— 3(у, (f

U„, Х;,;; ;1

j-1

Х = х 2

1, >-1 %r

}-1- r

2 где 1,1,1с (n — число хранимых признаков);

l m (m — разрядность признаков); значение r-ro разряда

k-го хранимого признаK8" значение r-го разряда признака опроса, l,ï х

)((.

Тогда (, (Цф = 2 0!у.,+ х;. — х !(. 1

1 ((-1 (t ((U. =2U. +х. — у.

j3 (J j 1) )

Рассмотрим случай поиска "максимум и меньше", Можно показать, что

UH = О, x it max X111

Поз тому для вычисления функций

«(U; достаточно на каждом mare итерационного процесса отмечать хранимые признаки, которые являются в данный момент максимальными.

С учетом изложенного для реализации итеративной процедуры предложен блок, граф состояний и переходов которого имеет три вершины (фиг.3) °

Первая вершина графа 30 соответствуе.т 0;> >.0 и U. О, Вторая () вершина 31 графа соответствует

U>1 (0 и U;. <0, а третья вершина 32Ц; с0 или 0; 0 (или то и другое).

Переходы из вершины 32 и 31 в вершину 30 графа происходят олько по сигналу начальной установки. Остальные переходы определяются предыдущими состояниями блоков 2! и

23 в блоках 21 фиксируются новые состояния

Работа ассоциативного запоминающего устройства, в которое входят блоки 21, основана на итеративном вычисленчи функций! 153359 значениями о ередных разрядов признаков. Если на входы 16 и 15 блоков подаются прямые, а на входы 13 и 17 инверсные значения разрядов признав ков, то сигналами единицы на выходах 27 отмечаются хранимые признаки, удовлетворяющие условию поиска

"максимум среди хранимых признаков и меньше, чем признак опроса",, а на выходах 26 — условию "максимум и меньше или максимум и равно", Соответственно при подаче прямых зна- . чений разрядов на входы 13 и 17 и инверсных на входы 16 и 15 на выходах 27 отмечаются хранимые признаки, удовлетворяющие условию поиска минимум и больше", а на выходах

26 - условию "минимум и больше" или "минимум и равно".

Поиск безусловного максимума и минимума является частным случаем укаэанных видов поиска (выполняется при подаче. У 0), Таким образом устройство, содер10 жащее предлагаемый блок поиска информации, по сравнению с прототипом имеет большее быстродействие, а именно осуществляет поиск условных экстремумов эа один цикл опроса ре гистров (вместо двух).

1 1.5335)

27

ZT !

2б

27

2У

ФиГ. 2

0 ил

01

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

Редактор И.Ковальчук Техред С.Мигунова Корректор О.Билак

Заказ 25!1/42 Тираж 584 Подписное

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

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

Филиал ППП "Патент", г, Ужгород, ул. Проектная, 4