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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН д 1 4 С 11 С 15/00 ОПИСАНИЕ ИЗОБРЕТЕНИЯК А АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 16 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССРУ 1049974; - кл. С 11 С 15/00, 1982,Авторское свидетельство СССРВ 1153359, кл, С 11 С 15/00, 1983,(54) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА(57) Изобретение относится к вычислительной технике и позволяет осуществлять быстрый ассоциативный поискэкстремальных величин или сортировкув массивах данных, Цель изобретения -расширение области применения .блоказа счет выполнения поиска среди чиЯО 1336116 А 1 сел, представленных в кодах Фибоначчи. Блок поиска представляет собойконечный автомат, имеющий четыре внутренних состояния, содержит триггеры1 и 2, шесть элементов И 3-8 и триэлемента ИЛИ 9-1 и имеет входы 1215 и выходы 16 и 17, Вход 12 блокаподключается к выходу соответствующего регистра признака, с которого кодпоступает побитно, начиная со старшего разряда. Вход 13 подключается квыходу внешнего элемента ИЛИ,. к входам которого подключаются выходы:17всех блоков поиска информации, используемых в ассоциативном запоминающем устройстве. По входам 14 и 15подаются сигналы синхронизации и начальной установки, Уровень логическойединицы на выходе 16 блока сигнализирует об экстремальности соответствующего признака, 3 ил., 1 табл,-г 3начальной успереходов,Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в автоматизированных си 5 стемах управления при решении задач распознавания.Цель изобретения - расширение области применения блока эа счет выполКения поиска среди чисел, представ- О ,ленных в кодах Фибоначчи.На фиг. 1 изображена функциональная схема .блока поиска информации для ассоциативного запоминающего устройства; нафиг. 2 - функциональная 5 схема ассоциативного запоминающего устройства, в которое входят предложенные блоки; на фиг. 3 - граф состояний и переходов блока .поиска информации, поясняющий его работу. 20Блок поиска информации (фиг. 1) содержит первый 1 и второй 2 триггеры, элементы И 3-8 с первого по шестой и элементы ИЛИ 9-11 с первого по третий, входы 12-15 и выходы 16 и 17, 25В ассоциативном запоминающем устройстве (фиг, 2) на блоках 18 поиска информации входы 12 блоков подключены к выходам соответствующих регистров 19 признаков, входы 13 подключены к 30 выходу элемента ИЛИ 20, входы 14 и 5 подключены соответственно к входу 21 . синхронизации и установочному входу 22; выходи 16 блоков являются выходами 23 ассоциативного запоминающего 35 устройства, а выходы 17 подключены к соответствующим входам элемента ИЛИ 20. Граф (фиг, 3) отражает состояние 40 24-27 с первого по четвертое и возможные переходы в блоке 18 поиска информации, В верхних шинах графа в виде дроби приведены значения функ ций ыиГ.Е(числитель дроби), 45 определяющих состояние блока, и двоичные коды, соответствующие состояниям первого 1 и второго 2 триггеров(знаменатель, слева направо) при дан- . ных состояниях блока поиска информации. Блок поиска информации для ассоциативного запоминающего устройства работает следующим образом.В исходном состоянии сигналом начальной установки по входу 22 триггеры 1 и 2 устанавливаются в состояние, соответствующее вершине 24 графаВесь поиск занимает ш.тактов (где ш - разрядность признаков), в каждом иэ которых с регистров 19 считываются очередные разряды (начиная со старших), анализируются с учетом предыдущих состояний в блоках 18 и по синхросигналу с входа 21,в блоках 18 фиксируются новые состояния.Работа ассоциативного запоминающего устройства, в которое входят блоки 18, основана на итеративном вычислении функций ш, = Е(со,е, оз х, х .) СЗ Г 1 Э Г 1 И л в лР(3-1)+Р(-2) при) О,1, и;1 = 1, п.(п - число признаков) .Величина х Г. "1 . представляет со 1бой запись 3-1 старших разрядов кодаФибоначчи признака х.1 х. =хР(ш-,) .Тогда ю Э Ю-сэ 1-Цц =" е +" е +х" хе ;еВсе возможные переходы в блоке поиска информации в зависимости от значений ГГ" и ыГ, г (с учетом исеходного состояния ш= ы Гг = 0), значений х , хй где х, =ша ххР 1К = 1, и, К1-12кеи значения я (сигналатановки) дает таблица(-) (-) О В связи с этим для реализации итеративной процедуры предложен блок, граф состояний и переходов которого имеет четыре вершины.Первая вершина графа 24 соответствует ЫГ"3 = ц . Е 3 = О, вторая вершина 25 соответствует ы,1 е 3 = -1, й,.е= О, третья вершина 26 ш Дб = = О, ш . = -1, а четвертая вершина 27 соответствует ГСХ 23 С 3-13.н.Если на входы 12 блоков 18 подаются прямые значения разрядов кодов признаков, сигналами единицы на выходах 23 отмечаются максимальные при-. знаки, а если инверсные значения разрядов - минимальные,формула изобретения Блок поиска информации для ассоциативного запоминающего устройства, содержащий первый и второй триггеры, с первого по шестой элементы И и первый элемент ИЛИ, причем прямой выход первого триггера подключен к первому входу третьего элемента И и является выходом результата поиска блока, второй вход третьего элемента И является признаковым входом блока, выход треФтьего элемента И - выходом состояния блока, прямой вход первого и инверсный вход второго элементов И объединены и являются информационным входом блока, прямой выход второго триггеоа соедийен с первым входом четвертогоэлемента И, выхо которого подключен к первому входу первого элемента ИЛИ,выход которого соединен с входом. асинхронной установки в "1" первоготриггера, инверсный выход второготриггера подключен к прямому входупятого элемента И, о т л и ч а ю -щ и й с я тем, что, с целью расширения области применения блока заЗ 0 счет выполнения поиска среди чисел,представленных в кодах фибоначчи, внего введены второй и третий элементы ИЛИ, причем инверсный вход первогои прямой вход второго элементов ИЗ 5 подключены к признаковому входу блока, выход первого элемента И подключен к инверсному входу шестого элемента И и первому входу второго элемента ИЛИ, второй вход которого сое 40 динен с выходом пятого элемента И,.выход второго элемента ИЛИ подключенк входу асинхронной установки в Опервого триггера, выход второго элемента И соединен с вторым входом чет 45 вертого и инверсным входом пятогоэлементов И, прямой выход первоготриггера подключен.к прямому входушестого элемента И, выход которого, соединен с первым входом третьего),50 элемента ИЛИ, выход которого подключен к входу асинхронной установки в"1" второго триггера, прямой выходкоторого соединен с.третьим входомтретьего элемента И, вход асинхронной55 установки в "О" первого триггера,подключен к инверсному выходу первоготриггера, вторые входы первого и третьего элементов ИЛИ объединены и яв.ляются установочным входом блока.1336116 Фиг.2 2 оставитель В. Рудаковехред И,Попович Корректор С. Чер едактор А. Козор аказ 4051/50 Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектна Тираж 589 ВНИИПИ Государственно по делам изобретени 113035, Москва, Ж, РПодписноекомитета СССРи открытийшская наб., д. 4/5