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

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

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

1

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

Известен блок поиска информации для осуществления последовательного по разрядам ассоциативного поиска, содержащий триггеры, элементь) И и элемент НЕ, причем первый вывод блока подключен к первому входу первого элемента И и входу элемента НЕ, выход которого подключен к первому входу второго элемента И,второй вы3вод блока подключен к вторым входам первого и второго элементов И, а тр тий, вывод блока подключен к первому входу третьего элемента И, второй вход которого подключен к выходу первого триггера, а выход подключен к входу второго триггера, выход которого подключен к третьим входам первого и второго элементов И, выходы которых подключены соответстве но к первому и второму входам первого триггера D3 Однако область примен.ения этого блока ограничена задачами, в которы требуется поиск максимального слова Наиболее близким к изобретению по технической сущности является бл поиска информации, содержащий тригтеры, элементы И, элементы ИЛИ иг элементы НЕ, в котором первый вывод блока подключен к первым входам пер вого,, второго и третьего элементов И, второй вывод-блока подключен к первым входам четвертого, пятого и шестого элементов И, третий вывод блока подключен к первому входу сед мого и вторым входам четвертого и пятого элементов И, -четвертый вывод блока подключен к первому входу вос мого и вторым входам первого и тре. тьего элементов И, пятый вывод блрка подключен к первому входу перво. элемента ИЛИ, шестой вывод блока подключен к первым входам первого и В1тороготриггеров, седьмой вывод блока подключен к вторым входам вто рого и восьмого и третьему ВХОДУ первого элементов И и выходу первого элемента НЕ, восьмой вывод блока подключен к -второму входу шестого элемента И, вь1ход первого элемента И подключен к второму входу первого триггера, третий, вход которого подключен к выходу первого элемента ИЛИ, а первый выход подключен к третьим чзходам второго, третьего и. восьмого; элементов И., .выход второго элемента ИЛИ; первый, второй, третий, четвертыйj пятый и щестой входЫ; которого подкгначены соответствен но к выходам второго, третье«го, пятого шестого, седьмого и восьмогоэлементов И, подключен к второму вхрду второго триггера, первый выход которого подключен к третьему входу четвертого элемента И, выход которого подключен к второму входу первого элемента ИЛИ 2 УЗ Недостатком известного блока является, то, что в нем выполняется поиск по небольшому числу критери- . ев, .что сужает область его применения. Цель изобретения - расширение 66ласти применения блока за счет выполнения поиска в массив хранимых признаковых;, ,п. таких приз-. маков X .Ve-M:|XK-X7 /Xe-Y/, где Ч - признак опроса. Поставленная цель достигается тем, что в блок поиска информации для ассоциативного запоминающего устройства, содержащий первый и второй триггеры, элементы И с первого по восьмой, первый и второй элементы ИЛИ, первый, второй и третий элементы НЕ, причем первые входы первого, второго и третьего элементов .1 первые входы четвер того, пятого и шестого элементов И первый .вход седьмого и вторые входы четвертого и пятого элементов И, первый вход восьмого и вторые входы первого и третьего элементов И, соответственно объединены и являются входами, блока,с перйого по четвертый, ; . первый вход первого элемента ИЛИ является пятым входом блока, первые входы первого и вторЪго триггеров, вторые входы второго и восьмого и третий вход первого элементов И соответственно объединены и являю1тся шестым и седьмым входами блока, восьмы| входом которого является второй вход шестого элемента И, выход перво- го элемента И подключён к второму входу первого триггера, третий вход Которого подключен к выходу первого элемента ИЛИ, а первый выход - к третьимвходам-второго, третьего и восьмого элементов И, выход второго элемента ИЛИ; первый, второй, третий, четвертый, пятый и шестой входи которого подключены соответственно к выходам второго, третьего, пятого, шестого седьмого и восьмого элементов И подключен- к второму входу второго триггера, первый выход которого подключен к третьему входу четвертого элемента И, выход которо- -, го подключен к второму входу пера,ого Элемента ИЛИ, введены элементы И с девятого по двадцать третий, . элементы ИЛИ с третьего по пятый, третий триггер и элементы И-НЁ с первого по четвертый, причем первые

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

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

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

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

. вторым входам девятого, триНадцатоO го, шестнадцатого и девятнадцатого -и третьему входу, десятого элементов И и первому входу четвертого и второму входу третьегр элементов И-НЁ,

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

И-НЕ, второй выход третьего три1-

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

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

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

На фиг. 1 показана структурная схема блока поиска информации; на

-„ фиг. 2 - структура ассоциативного запоминающего устройства, в состав которого входят данные блоки; на . фиг. 3 график переходов блока поиска информации. 5 лок поиска информации (фиг. 1) содержит элементы И 1-23,. элементы ИЛИ 2V-28, элементы НЕ 29--32, элементы И-НЕ 33-36, и первый 37, ВТОрой 38 и третий 39 триггеры. Блок .имеет входы и выход 51. . Ассоциативноезапоминающее устройство (фиг. 2) содержит блоки 52 поиска информации, регистр .53 признака опроса, регистры 5 хранимых признаков; Первые 0. и вторые kV входы всех блоков подключены соответственно к первому и второму выходам-регистра 53 при знака, а третий k2 и четвертый A3.входы каждого блока подключены к двум выходам одноименного регистра 5. Входы . всех блоков подключены через резисторы 55 к источнику5б опорного напряжения. Пятые входы , всех, блоков подключены к входу 57 начальной установки, а шестые входы 45 всех блоков подключены квходу 58 синхронизации. Зыходы 51 всех блоков являются логическими выхода Лпгмх/ о а IS п«ашт а пгчгыивагч/ЫЫМ ПЫКПЯЯ .ми устройства. . , График переходов ассощ ативного блока (-фиг. 3) имеет пять вершин .59-63. Под номерами вершин приведены коды состояний блока, в которых двоичные цифры соответствуют (слеванаправо) состояниям третьего 39, первого 37и второго 38 триггеров. Устройство работает следующим образом. В исходном состоянии сигналом по входу.57 все блоки 52 устанавлива ются в состояние 59. -i Ассоциативный поиск производится за т- тактов поразрядного сравнения (т-разрядность признаков). В каждом такте на блок 52 по входам kO и 1 поступают соответственно инрер ное и. прямое .значения текущего разряда признака опроса, а по входам k2 и 43 - соответственно инверсное и прямое значения текущего разряда одноименного хранимого признака. Эти сигналы поступают в порядке убы вация. их весов, , . В зависимости от предыдущего j-1-го состояния блока 52 и значеНИИ текущих J-X разрядов признака опроса и одноименного хранимого при знака, а также в зависимости от j-1-x состояний остальных блоков 52 и значений текущих разрядов признаков на их выходах, на установочныхвходах триггеров i-ro блока 52 вырабатываются следующие сигналы: S7 и Rjij; на входах первого 37,. Saij и R на входах второго 38 и и входах третьего 39 триггерЬв, которые определяются следующим образом: ,i-4 , 2. 14,5-4 S3.r ilQ24.iM(X,A,vX;..Y.D,EOv. /- - - - - .i-tV i. 1 j И R,,.TvXi.D,vQ Y C-vX iCjEjV-. v,) - R2.,;..;(. : тг п f З 2ч ,j-i И vj j) ..,. 4l Ml i iEjDO, . . где xjj - значение J-го разряда i-ro хранимого признака; У} знамение j-rb разряда признака опроса; Ц2П-1 .JM vi-1 текущие состоянияпёрвого 37, второго 38 и третьего 39 триггеров; -Т - сигнал начальной установки, а А j , S.j , Cj , Dj- и Ej определяются следующим образом: ApVQ .JM 8p,VQ,,,j.,Q,,./ .,5и ; °i YX,-Q,., Ei--VX-Q, V . 2,i-i . При поступлении сигнала на вход 58 в триггерах 37-39 фиксируются новые, j-е состояния блоков 52. и на чинается такт поиска. Результат поиска определяется, состояниями всех триггеров 37-39 блоков 52. Появление сигнала 4; на . выходах 51 некоторых блоков 52 в результате последнего такта поиска ,(,.,C . означает, что одноименные хранимые признаки удовлетворяют условию по-. иска, 9Ю в рассмотренном ассоциативном устройстве, построенном на предлагаемых блоках, аппаратурное за один поразрядный просмотр признаков, реализован новый вид ассоциативного поисЭЭУЗка - поиск хранимых признаков, наиболее удаленных от признака опроса ; по величине, благодаря чему достигается расширение области применения блоков поиска информации.

f7 5В

Фиг. г

Фиг,3