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

1 Изобретение относится к вычисли тельной технике, в частности к запоминаюац1м устройствам, и может быть использовано при решении зада распознавания, обработки результат эксперимента, анализа параметров управляемого процесса. Известен блок поиска информации для ассоциативного запоминающего устройства, содержащий два тр гера и три элемента И Til. Недостаток этого устройства невозможность осуществления поиска условных экстремумов. Наиболее близким к предлагаемому по технической сущности и дости гаемому результату является блок поиска информации для ассоциативного запоминающего устройства, содержаищй два триггера элемент ИЛИ-НЕ, элемент И-НЕ и элемент НЕРАВНОЗНАЧНОСТЬ, причем первый вход блока подключен к первому вхо ду первого триггера, выход которог подключен к первому выходу блока, второй вход блока подключен к первому входу второго триггера, выход которого подключен к второму входу первого триггера и к первому входу элемента И-НЕ, выход кото го подключен к второму выходу блока, а второй вход соединен с первы входом элемента ИЛИ-HR и подключе к выходу элемента НЕРАВНОЗНАЧНОСТ первый и второй входы которогопод ключены к третьему и четвертому входам блока, пятый вход блока по ключен к второму входу элемента ИХШ-НЕ, выход которого подключен к второму входу второго триггера, третий вход которого подключен к шестому входу блока, элемент НЕРАВНОЗНАЧНОСТЬ содержит, наприм два эле-ме.нта НЕ,два элемента И и элемент ИЛИ,причем первый вход эле мента НЕРАВНОЗНАЧНОСТЬ подключен к-первому входу первого элемента И к входу первого элемента НЕ, второй вход элемента НЕРАВНОЗНАЧНОСТЬ подключен к первому входу второго элемента И и входу второг элемента НЕ, выходы первого и зт.о го элементов НЕ подключены к втор - входам соответственно второго и первого элемента И, а выходы элем тов И подключены к входам элемента ИЛИ, выход которого подключен выходу элемента НЕРАВНОЗНАЧНОСТЬ И-НЕ и ИЛИ-НЕ содержат, 93 например, последовательно соединенные , элементы И и НЕ и элементы РШИ и НЕ C2J. Недостаток этого блока - пониженное быстродействие при поиске условных экстремумов, обусловленное тем, что поиск осуществляется за два цикла; один цикл экстремального (максимум, минимум и один цикл граничного (меньше, равно, больше, и др.) поиска. Цель изобретения - повышение быстродействия блока при ассоциативном поиске условных экстремумов, Поставленная цель достигается тем, что в блок поиска информации для ассоциативного запоминающего устройства, содержащий первый и второй триггеры, элементы И с первого по третий, элемент ШШ и элемент НЕ, причем первый выход второго триггера подключен к первому входу первого элемента И, выход триггера подключен к первому входу первого элемента И,выход элемента НЕ подключен к первому входу второго элемента И, первые входы первого и второго триггеров, второй вход второго элемента И и первый вход третьего элемента И являются соответственно входами блока с первого по четвертый, введены элементы И с четвертого по шестой, причем третий вход второго элемента И,и первый вход четвертого элемента И являются пятым входом блока, выход второго элемента И подключен к второму входу второго триггера, второй вход четвертого элемента И является шес1Ъ1м входом блока, а выход подключен к первому входу элeJ4eнтa ИЛИ, вьйсод которого подключен к второму входу первого триггера, а второй вход - к выходу первого элемента И, второй вход которого является седьмым входом блока, выход первого триггера подключен к первому входу пятого элемента И,выход которого является вторым, выходом блока, а второй вход подключен к четвертому входу блока, первый вход шестого элемента И подключен .-к выходу первого триггера, а вълход является третьим выходом блока, в торой вход шестого элемента И подключен к второму выходу второго триггера, тр(.тьк входы первого ,и второго триггеров подключены .соответственно к второму и первому входам блока, вход элемента НЕ подключен к шестому входу блока. На фиг.1 изображена функциональная схема блока;на фиг.2 - схема а социативного запоминающего устройс ва в которое входят предложенные блоки; на фиг.З - граф состояний и переходов блока поиска информации, поясняющий его работу. Блок поиска информации содержит первый 1 и второй 2 триггеры, элем ты И 3-8 с первого по щестой, элемент ИЛИ 9 и элемент НЕ 10, входы 11-17 блока, поиска информации с пе вого по седьмой и выходы 18-20 бло ка с первого по третий. В ассоциативном запоминающем устройстве (фиг,2) на предложенных блоках 2 поиска информации первые и вторые входы подключены соответственно к установочному входу 22 и входу 23 синхронизации, третьи и шестые входы подключены к выходам соответствующих регистров 24 хранимых признаков, пятые и седьмые входы подключены к выходам регистра 25 опроса, первые и третьи выходы являются соответственно первыми 26 и вторыми 27 выходами ассоциативного запоминающего устройства, а четвертые входы и вторые выходы объединены и подключены через резистор к источнику 29 опорного напряжения. Граф (фиг.З) отражает состояния 30-32 с первого по третье и возможш 1е переходы в блоке поиска информации. Рядом с вершинами графа приведены двоичные коды, соответствующие состояниям первого I и второго 2 триггеров (слева направо) при данных состояниях блока поиска информации. Блок поиска информации для ассоциативного запоминающего устрой ства работает следующим образом. В исходном состоянии сигналом начальной установки по входу 22 триггеры 1 и 2 устанавливаются в со тояния, соответствуннцие верпшне. 30 графа. Весь поиск занимает m тактов (где га - разрядность признаков), в каждом из которых с регистров 24 и 25 Считываются оче.р едные разряды (начиная со старших), анализируются с учетом предыдущих состояний,в блоках 21 и по синхросигналу с вход 23 в блоках 21 фиксируются новые состояния . Работа ассоциативного запоминающего устройства, в которое входят блоки 21, основана на итеративном вычислении функций u,ej f.,(u;e,,,.); fz(u,j-t). где ,jH м-Г «,j- 5 и,,j-i i,H . J ri i,l,k 1,n (n - число хранимых призна ков); j 1 ,m (m - разрядность признаков); X. - значение r-го разряда Vr , k-го хранимого признака;у. - значение г-го разряда признака опроса. Цг 2 г -ii - .) Рассмотрим случай поиска макси11ум и меньше Можно показать, что .iej 5 Г J Поэтому для вычисления функций j достаточно на каждом шаге итераионного процесса отмечать хранимые ризнаки, которые являются в данный омент максимальными. С учетом изложенного для реализаии итеративной процедуры предложен лок, граф состояний и переходов оторого имеет три вершины (мг.З). Первая вершина графа 30 соответтвует и U;i «О. Вторая ершина 31 графа соответствует ipO и , а третья вершина 32 ,-; to или (или то и другое). Переходы из вершины 32 и 31 в ершину 30 графа происходят только о сигналу начальной установки. Осальные переходы определяются преыдущими состояниями блоков 21 и

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

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

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

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

ФигЛ

Фиг. 2