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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 15 О 51 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРСКОМУ СВ ТЕЛЬСТ 4 24-24 расдов ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Казанский ордена Трудового Кного Знамени и ордена Дружбы нароавиационный институт им.А.Н,Туполева(56) 1.Фостер К. Ассоциативные параллельные процессоры, Нер. с англ. МЭнергоиздат, 1981, с.137, рис.5, 15.2. Сопйегепсе оп сошрпгегз аувйеша апй гесЬпо 1 о 8 у. Ьопйоп,ТЕЕ,1974, р. 180-184 (прототип),(54) (57) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ .АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий первый и второйтриггеры, элементы И с первого потретий, элемент ИЛИ и элемент НЕ,причем первый выход второго триггера подключен к первому входу первогоэлемента И, выход элемента НЕ подключен к первому входу второгоэлемента И, первые входы первого ивторого триггеров, второй вход второго элемента И и первый входтретьего элемента И являются соответственно входами блока с первого почетвертый, о т л и ч а ю щ и й с ятем, что, с целью повышения быстродействия блока, в него введены ЯО 1153359 А.элементы И с четвертого но шестой,причем третий вход второго элемента и первый вход четвертого элемента И являются пятым входом блока, выход второго элемента И подключен ко второму входу второго триггера, второй вход четвертого элемента И является шестым входомблока, а выход подключен к первому входу элемента ИЛИ, выход которого подключен к второму входу первого триггера, а второй вход - к выходу первого элемента И, второйвход которого подключен к выходутретьего элемента И, второй входкоторого является седьмым входомблока, выход первого триггера подключен к первому входу пятого элемента И, выход которого является вторымвыходом блока, а второй вход подключен к четвертому входу блока, первый вход шестого элемента Иподключен к выходу первого триггера, а выход является третьимвыходом блока, второй вход шестогоэлемента И подключен к второму выходу второго триггера, третьи входыпервого и второго триггеров подключены соответственно к второму ипервому входам блока, вход элементаНЕ подключен к шестому входу блока.11533Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и можетбыть использовано при решении задачраспознавания, обработки результатовэксперимента, анализа параметровуправляемого процесса.Известен блок поиска информации для ассоциативного запоминающего устройства, содержащий два триг гера и три элемента И 13.Нецостаток этого устройства -невозможность осуществления поиска условных экстремумов,Наиболее близким к предлагаемому по технической сущности и достигаемому результату является блокпоиска информации для ассоциативного запоминающего устройства, содержащий два триггера элементИЛИ в , элемент И-НЕ и элементНЕРАВНОЗНАЧНОСТЬ, причем первыйвход блока подключен к первому входу первого триггера, выход которогоподключен к первому выходу блока, второй вход блока подключен кпервому входу второго триггера,выход которого подключен к второмувходу первого триггера и к первому входу элемента И-НЕ, выход которого подключен к второму выходу блока, а второй вход соединен с первымвходом элемента ИЛИ-НЕ и подключенк выходу элемента НЕРАВНОЗНАЧНОСТЬ,первый и второй входы которого под -ключены к третьему и четвертомувходам блока, пятый вход блока под-ключен к второму входу элементаИЛИ-НЕ, выход которого подключенк второму входу второго триггера,третий вход которого подключен кшестому входу блока, элементНЕРАВНОЗНАЧНОСТЬ содержит, например,два элемента НЕ,два элемента И иэлемент ИЛИ,причем первый вход элемента НЕРАВНОЗНАЧНОСТЬ подключенк первому входу первого элементаИ и входу первого элемента НЕ,второй вход элемента НЕРАВНОЗНАЧНОСТЬ подключен к первому входувторого элемента И и входу второгоэлемента НЕ, выходы первого и второго элементов НЕ подключены к вторымвходам соответственно второго ипервого элемента И, а выходы элементов И подключены к входам элемента ИЛИ, выход которого подключен квыходу элемента НЕРАВНОЗНАЧНОСТЬ аэлементы И-НЕ и ИЛИ-НЕ содержат,например, последовательно соединенные, элементы И и НЕ и элементыИЛИ и НЕ 7.,Недостаток этого блока - пониженное быстродействие при поиске условных экстремумов, обусловленноетем, что поиск осуществляется задва цикла: один цикл экстремального(максимум, минимум и один цикл граничного 1 меньше, равно, больше ндр.) поиска.Цель изобретения - повышениебыстродействия блока при ассоциативном поиске условных экстремумов,Поставленная цель достигаетсятем, что в блок поиска информациидля ассоциативного запоминающегоустройства, содержащий первый ивторой триггеры, элементы И с перво -го по третий, элемент ИЛИ и элементНЕ, причем первый выход второготриггера подключен к первому входупервого элемента И, выход триггераподключен к первому входу первогоэлемента И,выход элемента НЕ подключен к первому входу второгоэлементе И, первые входы первого ивторого триггеров, второй входвторого элемента И и первый входтретьего элемента И являются соответственно входами блока с первого почетвертый, введены элементы И счетвертого по шестой, причем третийвход второго элемента И и первыйвход четвертого элемента И являются пятым входом блока, выходвторого элемента И подключен квторому входу второго триггера, второй вход четвертого элемента И является шестым входом блока, а выходподключен к первому входу элементаИЛИ, вьйсод которого подключен к второму входу первого триггера, авторой вход - к выходу первогоэлемента И, второй вход которогоявляется седьмым входом блока, вы -ход первого триггера подключен кпервому входу пятого элемента И,выход которого является вторым, выходом блока, а второй вход подключенк четвертому входу блока, первыйвход шестого элемента И подключен квыходу первого триггера, а выход является третьим выходом блока, второй вход шестого элемента Иподключен к второму выходу второготриггера, третьи входы первого;ивторого триггеров подключены соответственно к второму и первому входамблока, вход элемента НЕ подключен(к шестому входу блока,На фиг,1 изображена функциональная схема блока;на фиг,2 - схема ассоциативного запоминающего устройства, в которое входят предложенныеблоки; на фиг.3 - граф состояний ипереходов блока поиска информации,поясняющий его работу.Блок поиска информации содержитпервый 1 и второй 2 триггеры, элементы И 3-8 с первого по щестой, элемент ИЛИ 9 и элемент НЕ 10, входы11-17 блока, поиска информации с первого по седьмой и выходы 18-20 блока с первого по третий,В ассоциативном запоминающемустройстве (Фиг,2) на предложенныхблоках 21 поиска информации первые и вторые входы подключены соответственно к установочному входу 22 и входу 23 синхронизации,третьи и шестые входы подключены квыходам соответствующих регистров24 хранимых признаков, пятые и25седьмые входы подключены к выходамрегистра 25 опроса, первые и третьивыходы являются соответственно первыми 26 и вторыми 27 выходами ассоциативного запоминающего устройства, а четвертые входы и вторыевыходы объединены и подключены че. -рез резистор 28 к источнику 29опорного напряжения,Граф (Фиг3) отражает состояния30-32 с первого по третье и возможные переходы в блоке поиска информации, Рядом с вершинами графаприведены двоичные коды, соответствующие состояниям первого 1 и 4 Явторого 2 триггеров (слева направо)при данных состояниях блока поиска информации,Блок поиска информации дляассоциативного запоминающего устройства работает следующим образом.В исходном состоянии сигналомначальной установки по входу 22триггеры 1 и 2 устанавливаются в состояния, соответствующие вершине 5030 графа,Весь поиск занимает ш тактов(где т - разрядность признаков),в каждом из которых.с регистров 24и 25 считываются очередные разряды(начиная со старших), анализируютсяс учетом предыдущих состояний,вблоках 21 н по синхросигналу с входа(ц.: ц, ф ху= шх 1;11Поэтому для вычислени функцРф0; достаточно на каждом шаге итерационного процесса отмечать хранимыепризнаки, которые являются в данныймомент максимальными,С учетом изложенного для реализации итеративной процедуры предложенблок, граф состояний и переходовкоторого имеет три вершины (фиг.3)Первая вершина графа 30 соответствуе.т 0; 3.0 и ЦО. Вторая(1вершина 31 графа соответствуетц 1 ЪО и ц 11 сО, а третья вершина 32 Ц; сО или Ц; 0 (или то и другое).Переходы из вершины 32 и 31 ввершину 30 графа происходят толькопо сигналу начальной установки. Остальные переходы определяются предыдущими состояниями блоков 2 и 23 в блоках 21 Фиксируются новые состоянияРабота ассоциативного запоминающего устройства, в которое входят блоки 21, основана на итеративном вычисленчи функцийзначениями о ередных разрядов признаков. Если на входы 16 и 15 блоковподаются прямые, а на входы 1 3 и 17инверсные значения разрядов признаков, то сигналами единицы на выходах 27 отмечаются хранимые признаки, удовлетворяющие условию поиска"максимум среди хранимых признакови меньше, чем признак опроса" ана выходах 26 - условию "максимум именьше или максимум и равно", Соответственно при подаче прямых значений разрядов на входы 13 и 17и инверсных на входы 16 и 15 на выходах 27 отмечаются хранимые признаки, удовлетворяющие условию поиска минимум и больше", а на выходах26 - условию "минимум и больше"или минимум и равноПоиск безусловного максимума иминимума является частным случаемукаэанных видов поиска 1 выполняется при подаче У 0),Таким образом устройство, содер Ожащее предлагаемый блок поиска информации, по сравнению с прототипом имеет большее быстродействие, аименно осуществляет поиск условныхэкстремумов эа один цикл опроса ре 15 гистров (вместо двух)./5 Филиал ППП "Патент", г, Укгород, ул, Проектная, 4 каз 25/42 ВНИИПИ Г по д 113035, Тир осударствен елам изобре Москва, Ж аж 584ого комиений и5, Рауш Подпета СССРкрытийая наб., д 27 2 У