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

 

ССВОЭ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (11) 3(58 С 11 С 1 /00

f0CVQAPCTBEHHbIA H0MHTET CCCP

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К АВТОРСКОМЪР С8ИДЕТЕЛЬСТВУ (21) 3468972/18-24 (22) 12. 07.82 (46) 23 10.83. Бюл. И 39 (72) В.Б.Матвеев (71) Казанский ордена Трудового

Красного Знамени и ордена Дружбы

Народов авиационный институт им. А.H Òóïîëåâà (53) 681.327(088.8) (56) Аягаиа l О.P. Simultaneous comр1ех search in associative аепюг1ев

Conference on Computer systems and

technology.. London, 1974. 2. Авторское свидетельство СССР . II 902073, кл. G 11 C 15/ 00, 1980 (проФотип). (54)(57) БЛОК ПОИСКА ИнаОРМАЦИИ ДЛЯ

АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий триггеры, элемент

НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, элемент И-НЕ, элементы ИЛИ, элементы

НЕ с первого по третий и элементы

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

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

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

И, третий вход первого элемента И и второй вход четвертого элемента

И подключены к выходу третьего weмента НЕ, входы элемента НЕРАВНОЗНАЧНОСТЬ являются первым и вторым входами блока, вторые входы второго и восьмого элементов И и вход третьего элемента НЕ объединены и явля- ются третьим входом блока, четвертым входом которого является второй вход первого триггера, третьи входы триггеров объединены и .являются пятым входом блока, выходом которого является второй выход третьего триггера, отличающийся тем, что, с целью упрощения блока, в нем выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к третьему входу второго и вторым входам шестого и седьмого элементов И и входу первого элемента НЕ, четвертый вход первого и третий вход четвертого элементов И соединены с выходом второго элемента НЕ, третий вход пятого элемента И подключен к выходу третьего элемента НЕ, третий вход пятого элемента И подключен к выходу третьего элемента НЕ, третий вход шестого элемента И и второй вход

1049974 элемента ИЛИ-НЕ соединены с входом . и восьмого элементов К и четвертый третьего элемента, НЕ, вход второго вход второго элемента И объединены элемента НЕ, третьи входы седьмого и являются шестым входом блока, 1

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

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

ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы ИЛИ-НЕ, элементы И-НЕ (1), . Недостатками этого устройства яв ляются низкое быстродействие и не- 15 возможность ограничения окрестности экстремального признака.

Наиболее близким к изобретению по технической сущности является блок поиска информации для ассоци- 20 ативного запоминающего устройства, содержащий. три триггера, девять элементов И, два элемента ИЛИ, три. элемента НЕ, элемент НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, элемент И-НЕ и ком- 25 мутатор, причем первый вход блока подключен к первому входу элемента

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

НЕРАВНОЗНАЧНОСТЬ; выход которого под- 30 ключен к первым входам элементов

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

ИЛИ-НЕ четвертый вход блока подклюУ

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

/ входу элемента И-НЕ, выход которого подключен к первому выходу блока, выход второго элемента НЕ подключен к первому входу седьмого и вторым входам четвертого и пятого элементов И, выход четвертого элемента И подключен к третьему входу третьего триггера, у которого первый выход подключен к третьему входу пятого и вторым входам шестого и седьмого элементов, И, а второй выход подключен к первому входу восьмого и вторым входам второго и третьего элементов И и второму выходу блока, выход первого элемента И подключен к второму входу первого элемента ИЛИ, выходы элементов И второго, третьего и с пятого по восьмой подключены к соответствующим входам второго элемента ИЛИ, выход которого подключен к третьему входу второго триггера, выход которого подключен к второму входу первого и третьему входу четвертого элементов И, первый вход блока дополнительно подключен к первым входам коммутатора и девятого элемента И, у которого второй вход: подключен к выходу первого триггера, а выход подключен к третьему выходу блока, а седьмой вход блока подключен к второму входу коммутатора, у которого третий вход подключен к восьмому входу блока, первый выход подключен к второму входу восьмого И третьим входам первого и второго элементов И и входу второго элемента НЕ, а второй выход подключен к третьим входам шестого и седьмого и четвертому входу четвертого элементов И и входу третьего элемента НЕ, выход которого подключен к третьим входам третьего и восьмого и четвертому входу первого эле.ментов И (2).

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

8 исходном состоянии сигналом начальной установки по входу 12

55 (фиг. 1) триггеры 19 21 блока 2

3, 10499 или минимума с окрестностью осуществляется путем коммутации, посколь1 ку в нем не используются для настройки на вид поиска имеющиеся эле менты, инвертирующие значения разрядов хранимых признаков.

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

Поставленная цель достигается >р тем, что в блок поиска информации для ассоциативного запоминающего устройства, содержащий триггеры, элемент НЕРАВНОЗНАЧНОСТЬ, элемент

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

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

И и первые входы первого и второго элементов И соединены соответственно. с вторым входом первого элемента ИЛИ

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

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

-являются пятым входом блока, выходом

74

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

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

И и второй вход элемента ИЛИ-HE. coeр е с входом третьего элемента

НЕ, вход второго элемента НЕ, третьи входы седьмого и восьмого элементов

И и четвертый вход второго элемента

И объединены и являются шестым входом блока.

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

Устройство содержит регистры 1 хранимых признаков, блоки 2 поиска информации, регистр 3 опроса и элемент И 4, входы 5-10 блока поиска информации, установочные входы

11 и 12 и вход 13 синхронизации ассоциативного устройства, выходы

14 и 15 блока поиска информации.

Блок поиска информации (фиг. 1) содержит элемент НЕРАВНОЗНАЧНОСТЬ

16, элемент ИЛИ-НЕ 17. элемент ИНЕ 18, первый 19, второй 20 и третий

21 триггеры, первый 22 и второй 23 элементы ИЛИ, элементы И 24-31 и элементы НЕ 32-34.

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

20 и третьего 21 триггеров (слева направо) при данных состояниях блока 2. Прерывистыми линиями показаны переходы, возможные только по сигналу начальной установки с входа

12 (фиг. 1).

Блок поиска информации для ассоциативного запоминающего устройства работает следующим образом. устанавливаются в состояния, соответствующие первой вершине 35 графика (фиг. 2).

49974 б и х1 удовлетворяет условию описка, а

U„ --1>31; О;Р со и х, не удовлетворяет условию поиска.

Оле™0л1«Х q rex Х, 1

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

Из анализа условия поиска следует

X;1 = ma х ХЕ- =Ф О + 0, 15 е

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

Первая вершина 35 графика соответствует 0; =О и !

X„)» =9ах ХЕ3 е или О.; 0 и

Х; = Мах ХЕ е

Причем на каком"то из предыдущих шагов имеет место ситуация

ЗО U< 0; Х;,, „=„тах ХЕ„„> и

0„ „о 0;

Х;„=iа Х, е

35 Y.»Ó ° „Y «0

d е = ",, — Х е " .

1 5 1. 4

Если в процессе итеративного вычисления некоторой U qnI на любом шаге процесса окажется, что 0;Е > О, то можно утверждать, что 0„ > О. Аналогично

UлЕ -1 1 ;р а0. л

Значения О о и U p =-1 не позволя1 I1 ют сделать каких-либо выводов о знаке и;Е,„.

Чтобы-.,е вычислять все и фунции

U;II для всех значений Р, достаточно вычислять U такую, что

U, -min 0лр

Р

Тогда

0 0 = У Uit >0

3 10

Состояние на входе ll задает один из двух возможных видов поиска т.е. уровень логического нуля, KoTopblN задает поиск максимуиа с окрестностью.

З.есь поиск занимает m тактов (где е - разрядность признаков), в каждом из которых с регистров 1 и 3 считываются очередные разряды, ана- лизируются с учетом предыдущих состояний в блоках 2 и по синхросигналу с входа 13 в блоках 2 фиксируются новые состояния.

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

»

О;Е;-с(ол „.„) . где для поиска максимума с окрестностью

0Е Х „Хр l i+11 л У где

Х =Z x 2jК41 МГ ) п-л л-Л

»

YI, „=X. Yn2

К31-I. 1 где 1,1,1сГ,п(п - число хранимых признаков);

j l m(m - разрядность признаков); х„„- значение г-го разряда к-Io хранимого признака; у„ - значение r-ro разряда признака опроса.

Тогда 0;р =2U; >+I+д;р, где где r=l,j.

Вторая вершина 36 графика соответствует О" >О и (1

Х;. = тахX q. з (за исключением случая, соответствующего вершине 35).

Вершинам графика 37-40 соответствует

Х„1 ф тпах Х р

5 > а также, соответственно, вершине

37 - U<> =О; вершине 38 - U;l ) 0 вершине 39 - U =-1 и вершине 40

Ui> ("l°.

- Признак X„ удовлетворяет условию поиска, если U,»> 0, что соответствует нулевому состоянию третьего триггера 21 в л -ом блоке 2, т,е. установлению единичного уровня на выходе 15 этого блока 2.

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

Х -Хр+Ч > О соответствует Х; попадает в окрест" ность максимума в массиве с размером Ч, то выполнение для всех Ф (2 - x,-q)-(g -х -<) Y > О означает, что для всех

5 -x g-Y O, 1049974 т.е. Х; попадает в окрестность минимума.

Поиск максимума и минимума в массиве является частным случаем укаэанных видов поиска и выполняется при подаче f 0.

Таким образом, устройство, со-!

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

15 исключению элементоа И, коммутаторов и многовходового элемента ИЛИ.

1049974

10 49974

Составитель Т.Зайцева

Редактор О. Черниченко Техред M.Ãåðãåëü Корректор Т.Вашкович

Заказ 8436/49 Тираж 594 Подписное

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

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

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