Блок поиска информации для ассоциативного запоминающего устройства Советский патент 1983 года по МПК G11C15/00 

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

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

Известен блок поиска информации для ассоциативного запоминающего устройства, содержащийгэлементы ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы ИЛИ-НЕ, элементы И-НЕ ij .

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

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

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

Недостатком известного устройства является повышенная сложность, обусловленная тем, что настройка на поиск максимума с окрестностью или минимума с окрестностью осуществляется путем коммутации, посколь|ку в нем не используются для настройки на вид поиска имеющиеся элементы, инвертирующие значения разрядов хранимых признаков. Цель изобретения - упрощение блока поиска информации .для ассоциативного запоминающего устройства. Поставленная цель достигается тем, что в блок поиска информации для ассоциативного запоминающего устройства, содержащий триггеры, элемент НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ-НЕ, элемент И-НЕ, элементы ИЛИ, элементы НЕ с первого по третий и элe 4eнты И, причем выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к первым входам элемента ИЛИ-НЕ и элемента И-НЕ, второй вход котор эго соединен с выходом первого триггера, первый и второй входы которого подключены соответственно к выходу элемента ИЛИ-НЕ и к первым входам второго триггера и первого элемента ИЛИ, выход которого соединен с первым входом третьего триггера, второй вход которого подключен к выходу первого элемента И, выход второго элемента И и первые входы первого и второго элементов И соединены соответственно с вторым входом первого элемента ИЛИ fi с выходом второго триггера, второй вход которого подключен к выходу второго элемента ИЛИ, входы которого соединены с выходами элементов И с третьего по восьмой, первые входы, .третьего,.четвертого и пятого элемен. тов И подключены к первому выходу третьего триггера, второй выход которого соединен с первыми входами ше стого, седьмого и восьмого элементов И, вторые входы первого, третьего и пятого элементов И гюдключены к выхо ду первого элемента НЕ, выход второго элемента НЕ соединен с третьим входом третьего элемента И, третий вход первого элемента И и второй вход четвертого элемента И подключены к выходу третьего элемента НЕ, входы элемента НЕРАВНОЗНАЧНОСТЬ явля ются первым и вторым входами блока, вторые входы второго и восьмого элементов И и вход третьего элемента НЕ объединены и являются третьим входом блока, четвертым входом которого является второй вход первого триггера, третьи входы триггеров объединены и -являются пятым входом блока, выходом T .которого является второй- выход третьего триггера, выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к Третьему входу второго и вторым входам шестого и седьмого элементов И и входу первого элемента НЕ, четвертый вход первого и третий вход четвертого элементов И соединены с .выходом второго элемента НЕ, третий вход пятого элемента И подключен к выходу третьего элембн-; та НЕ, третий вход шестого элемента И и второй вход элемента ИЛИ-НЕ. соединены с входом третьего элемента НЕ, вход второго элемента НЕ, третьи входы седьмого и восьмого элементов И и четвертый вход второго элемента И объединены и являются шестым входом блока. На фиг. 1 изображена функциональная схема ассоциативного запоминающего устройства; на фиг. 2 - график состояний блока поиска информации. Устройство содержит регистры 1 хранимых признаков, блоки 2 поиска информации, регистр 3 опроса и элемент И , входы 5-10 блока поиска информации, установочные входы 11и 12 и вход 13 синхронизации ассоциативного устройства, выходы 1 и 15 блока поиска информации. Блок поиска информации (фиг. 1) содержит элемент НЕРАВНОЗНАЧНОСТЬ 16, элемент ИЛИ-НЕ 17. элемент ИНЕ 18, первый 19, второй 20 и третий 21 триггеры, первый 22 и второй 23 элементы ИЛИ, элементы И и элементы НЕ 32-3. График, изображенный на фиг. 2, отражает состояния предлагаемого блока и возможные переходы состояний. Под номерами вершин графика приведены двоичные коды, соответствующие состояниям первого 19, второго 20 и третьего 21 триггеров (слева направо) при данных состояниях блока 2. Прерывистыми линиями показаны переходы, возможные только по сигналу начальной установки с входа 12(фиг. 1). Блок поиска информации для ассоциативного запоминающего устройства работает следующим образом. В исходном состоянии сигналом начальной установки по входу 12 (фиг. 1) триггеры 19-21 блока 2 устанавливаются а состояния, соответствующие первой вершине 35 графика (фиг. 2). Состояние на входе 11 задает один из двух возможных видов поиска, т.е. уровень логического нуля, который задает поиск максимума с окрестностью. Зесь поиск занимает m тактов (гд m - разрядность признаков), в каи 1дом из которых с регистров 1 и 3 считываются очередные разряды, ана лизируются с учетом предыдущих сос тояний а блоках 2 и по синхросигнал с входа 13 в блоках 2 фиксируются новые состояния. Работа ассоциативного запоминаю щего устройства, в которое входят предлагаемые блоки, основана на ит ративном вычислении функций U,.lb где для поиска максимума с окрестностьюie..HHj- - гдеj- Х,,,,Г Х,2 У -Т Y 9-- v.j.-,r,t-, где i,l,(n - число хранимых признаков) ; ,m(m - разрядность признако х,р- значение г-го разряда k-r хранимого признака; у., - значение г-го разряда пр нака опроса. Тогда U;p.2U;|)j+.,4dipj, , Если в процессе итеративного вы числения некоторой и(п на любом ш ге процесса окажется, что U4 0,т можно утверждать, что . Ана .логично U. и,р,. Значения Uipj и Dip: -1 не позв ют сделать каких-либо выводов о зн ке U,em. Чтобь;-г,е вычислять все п фунции Ujfj для всех значений Р, достаточ но вычислять такую, что U,j уп. u,. t« и X/ удовлетворяет условию поиска. и и х не удовлетворяет условию поиска, U;; Хв; гзх X; -u«j pj ГРХ V,,, Поэтому для вычисления функций достаточно на каждом шаге итерационного процесса отмечать хранимые признаки, которые являются в данный момент максимальными. Из анализа условия поиска следуетX,j maxXp- U--5:0. С учетом этого для реализации описанной процедуры предлагается описываемый блок, график которого имеет шесть вершин (фиг. 2). Первая вершина 35 графика соответствует и, 0 и X;;. maxXgj или и та« Xjj. Причем на каком-то из предыдущих шагов имеет место ситуация i. г-1 е.гU, -%а е,; ...,, где ,. Вторая Зб графика соответствует и, и X pmotxXg(за исключением случая, соответствующего вершине 35). Вершинам графика соответствуетX-|iftmax; e3, а также, соответственно, вершине 37 - U,j 0; 38 - О,; О вершине 39 - -1 и вершине 40 -1. Признак X, удовлетворяет условию поиска, если , что соответствует нулевому состоянию третьего триггера 21 в-i -ом блоке 2, т,е, установлению единичного уровня на выходе 15 этого блока 2.

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

соответствует X, попадает в окрестность максимума в массиве с размером , то выполнение для всех с

(,(7 -хе-)

означает, что для всех 6 i-Xg-Y O,

Т.е. Х| попадает в окрестность минимума .

Поиск максимума и минимума в массиве является частным случаем указанных видов поиска и выполняется при подачеY О.

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