Ассоциативное запоминающее устройство Советский патент 1984 года по МПК G11C15/00 

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

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

соответственно объединенным вторым входам второго, десятого и девятнадцатого элементов И, первым входам

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

4, Устройство по пп, 1-3, отличающееся тем, что каждый блок выбора результата-поиска содержит дополнительные элементы И и дополнительный элемент ИЛИ, выход которого является выходом блока, а входы соединены с выходами дополнительных элементов И, входы которых являются входами блока.

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

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

Недостатком этого устройства является большое количество оборудовния.

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

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

Недостатком известного устройства является большое количество оборудования .

Цель изобре1чм1ия - хтгрощение устройстна путем сокращения объема оборудования ;

Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее регистры, блоки сравнения, блок управления и регистр опроса, выход которого соединен с первыми входами бло0ков сравнения, вторые входы которых подключены к выходам регистров, входы которых и вход регистра опроса соединены с одним из выходов блока управления, другие выходы которо5го подключены к третьим и четвертым входам блоков сравнения, введены блоки выбора результата поиска и блок анализа o6iu,ero условия поиска, первый вход которого соединен с вы0ходом регистра опроса, входы с второго по пятый соединены с одними из выходов блоков сравнения, шестой и седьмой входы - с другими выходами блока управления, а выходы

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

0

Кроме того,каждый блок сравнения содержит элементы И-НЕ,группу элементов И с первого по шестой,группу элементов 1-ШН и триггеры результата сравнения, единичные входы которых сое5динены через элементы ИЛИ группы с выходами элементов И группы, прямой выход первого триггера результата сравнения подключен к первым входам первого элемента И-НЕ, пя0того и шестого элементов И группы, а инверсный выход - к первым входам второго, третьего, четвертого элеме}1тов И-НЕ и первому входу четвертого элемента И группы, прямой вы5ход второго триггера результата сравнения подключен ко второму входу третьего элемента И-НЕ. и первым входам второго и третьего элементов И группы, а инверсный выход 0ко вторым входам первого, второго, четвертого элементов И-НЕ и первому входу первого элемента И группы, третий вход второго, четвертый вход четвертого элементов И-НЕ и второй

5 вход первого и третий вход четвертого элементов И группы объединены и являются первым входом блока, третьи входы первого, третьего и чет3109вертого элементов И-НЕ, первого, второго и пятого элементов И группы, четвертый вход второго элемента И-НЕ и второй вход четвертого элемента И группы объединены и являютс вторым входом блока, третьим и четвертым входами которого являются соответственно объединенные входы синхронизации и асинхронного сброса триггеров результата сравнения, выходы элементов И-НЕ с первого по четвертый соединены соответственно с вторыми входами пятого, шестого, второго и третьего элементов И гру пы и являются одними из выходов бло ка, другими выходами которого являются выходы триггеров результата ;. сравнения. Блок анализа общего условия поис ка содержит триггеры результата поиска, элементы НЕ, элементы И с пер вого по тридцать третий и элементы ИЛИ с первого по седьмой, причем прямой выход первого триггера результата поиска соединен с первыми входами четвертого и двадцать девятого элементов И, а его инверсный выход - с первыми входами шестого и двадцать седьмого элементов И, прямой выход второго триггера результата поиска соединен с первыми входами восьмого, дцадцать второго, тридцатого и тридцать первого элементов И, а его инверсный выход с первыми входами, второго, дваддать шестого элементов И, инверсный выход третьего триггера результата поиска соединен с первыми входами пятнадцатого и девятнадцатого элементов И, прямой выход четвертого триггера результата поиска соединен с первыми входами третьего и седьмого элементов И, а его инверсный выход - с третьими входами двадцать шестого и двадцать седьмого элемен тов И, вторые входы шестого, одиннадцатого и пятнадцатого элементов И и вход первого элемента НЕ, периле входы десятого,двадцатого.тридцатого. тридцать первого и трид т. цать третьего элементов И и вход второго элемента НЕ, первый вход первого элемента И и вход третьего элемента НЕ, первые входы шестнадцатого, вторые входы пятого, восемнадцатого, двадцать девятого, трид цать второго элементов И и вход чет вертого элемента,НЕ, второй первого элемента И и вход пятого элемента Ж соответственно объединены и являются входами блока с первого по пятьй, шестым и седьмым входами которого являются соответственно объединенные одни из входов триггеров результата поиска, выходы элементов НЕ с первого по пятый подключены к соответственно объединенным вторым входам второго, десятого и девятнадцатого элементов И, первым входам пятого и семнадцатого элементов И, вторым входам седьмого, восьмого, шестнадцатого, двадцать шестого элементов И и второго элемента ИЛИ, вторым входам девятого и четырнадцатого элементов И, вторым входам третьего, четвертого, двенадцатого и двадцать седьмого элементов И и четвертого элемента ИЛИ, выход первого элемента И соединен с третьими входами второго, пятого, шестого, девятого, двадцать девятого, тридцать первого, первыми входами десятого, одиннадцатого элементов И и входом шестого элемента НЕ, выход второго элемента И соединен с вторым входом тринадцатого, первыми входами четырнадцатого и двадцать первого элементов И, выход пятого элемента И соединен с трать- им входом пятнадцатого, вторыми входами двадцать второго и двадцать третьего элементов И, выход шестого элемента И соединен с вторым входом семнаддатого, первыми входами восемнадцатого и двадцать третьего элементов И, выход девятого элемевта И соединен с третьим входом девятнадцатого, вторыми входами двадцатого и двадцать первого элементов И, выход десятого элемента И соединен с вторыми входами двадцать четвертого, тридцатого и тридцать второго элементов И, выход одиннадцатого элемента И соединен с вторыми входами двадцать пятого, двадцать восьмого, тридцать третьего элементов И, выходы элементов И через соответствующие элементы ИЛИ, а выход шестого элемента НЕ непосредственно оединены с другими входами триггеров результата поиска, выходы первого и второго триггеров результата поиска являются выходами блока. Каждьш блок выбора результата поиска содержит дополнительные элементы И и дополнительный элемент 1ШИ, выход которого является выходом, блока, а входы соединены с выходами дополнительных элементов И, входы которых являются входами блока На фиг, 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг, 2 - структурная схема части устройства, содержащей блок сравнения и блок выбора результата поиска; на фиг, 3 - структурная схема блока анализа общего условия поиска, Ассоциативное запоминающее устройство содержит (фиг, ) регистры составляющие накопитель 2, регистр 3 опроса, блоки 4 сравнения, разрядные щины 5-8, блок 9 управления. Каждый блок 4 имеет первый 10 и второй 11 входы, выходы 12-15, третий 16 и четвертый 17 входы. Устройство также содержит блок 18 анализа общего условия поиска, имеющий выходы 19 и 20, и блоки 21 выбора результата поиска. Блок 18 имеет входы 22-28 с первого по седьмой, каждый блок 4 выходы 29-32, а каждый блок 21 - выход 33, являющийся выходом устройстна. Каждый блок 4 сравнения (фиг, 2) содержит триггеры 34 и 35 результат сравнения, элементы И-НЕ 36-39, гру пу элементов И 40-45 с первого по шестой, группу элементов ИЛИ 46 и 4 Блок 21 выбора результата поиска со держит дополнительные элементы И 48 и 49 и дополнительный элемент ИЛИ 50. Блок I8 анализа общего условия поиска содержит элементы НЕ 51-56 с первого по шестой, элементы И 57-89 с первого по тридцать третий, элементы ИЛИ 90-96 с первого по седьмой и триггеры 97-100 резуль тата поиска с первого по четвертый, В предложенном устройстве выявле ние признака ближайший по значению к опросному выявляется при помо щи сравнения ()/2 су, которое .сводится к вычислению в блоке 18 8ign(x.,+X2,-2y), Ilpt} этом X Х- является ближайшим, если х +Х2-2у /О, Х|Вх является ближайшим, если x +X2-2yiO, . гдз X - признак, з аписанный в i-ом регистре 1 (i 1, п где п - число регистров); у. - опросный призна ; х (x;:x, 7у) X 2 иах(х :X у . В каждом блоке 4 выявляются признаки х-е х и х.ех (ближайшие большие и ближайшие меньшие), Блок 4 использует четыре разрядные шины 5-8 и имеет четьфе состояния : (х у)оо(х.х) - начальное состояние; а--()«( ) - состояние у 1; а -(х .у)( ) - состояние Si 1; ((x.) - состояние сброса. Окончательный выбор признаков, удовлетворяющих критерию ближайший среди , производится на соответствующих блоках 21, Устройство работает следующим образом, Под действием сигналов с блока 9 управления с регистров 1 и 3 на блоки 4 сравнения поступают разрядные значения опросного и записанных признаков (битовые слои), начиная со старших разрядов. Блоки 4 сравнения выявляют признаки: Х;е - состояние а и - состояние а,,При этом на разрядных шинах появляются сигналы, соответствующие разрядным значениям Х-, х и сигналы первых неравенств , . Используя эти сигналы и разрядные значения у, поступающие с регистра 3, блок 18 вычисляет Sign(x +х -2у) и вырабатывает сигналы: на выходе 19 - соответствующий значению х +х , на выходе 20 - соответствующий значению x +Xj-Zy O с определенной точностью при анализе каждого текущего битового слоя. Эти сигналы поступают на блоки 21 выбора результата поиска. Сигнал на выходе 33 блока 21 соответствует выполнению условия: ()(х +Х2-2у40)()(х + +Х2-2у7 0.), что соответствует критерию ближайший. После анализа всех разрядов признаков единичные сигналы на выходах 33 выявляют признаки, ближайшие по числовому значению к опросному. т,е, соответствующие min((). Технико-экономическое преимущество предложенного устройства заключается в его упрощении по сравнению с прототипом.

1. АССОЦИАТИВНОЕ ЗАПОМШШОЩЕЕ УСТРОЙСТВО, содержащее регистры, блоки сравнения, блок управления и регистр опроса, выход которого соединен с первыми входами блоков сравнения, вторые входы которых сое динень1 с-выходами регистров, входы которых и вход регистра опроса соединены с одним из выходов блока управления, другие выходы которого подключены к третьим и четвертым входам блоков сравнения, отличающееся тем, что, с целью упрощения устройства, в него введены блоки выбора результата поиска и блок анализа общего условия поиска, первый вход которого соединен с выходом регистра опроса, входы с второго по пятый соединены с одними из выходов блоков сравнения, шестой и седьмой входы - с другими выходами блока управления, а выходы подключены к одним из входов блоков выбора результата поиска, другие входы которых подключены к другим выходам блоков сравнения, а выходы являются выходами устройства. 2. Устройство по п. 1, о т ли чающееся тем, что каждый блок сравнения содержит элементы И-НЕ, группу элементов И с первого по шестой, группу элементов ИЛИ и триггеры результата сравнения, единичные входы которых соединены через элементы ИЛИ группы с выходами элементов И группы, прямой выход первого триггера результата сравнения подключен к первым входам первого элемента , пятого и шестого элементов И группы, а инверсный выход - к первым вхоцам второго, третьего, четвертого элементов И-НЕ и первому входу четвертого элеменi та И группы, прямой выход второго триггера результата сравнения под- ко второму входу третьего элемента И-НЕ и первым входам второго и третьего элементов И группы, а инверсный выход - ко вторым входам первого, второго, четвертого элемено х тов И-НЕ и первому входу первого элемента И группы, третий вход второго, четвертый вход четвертого элеrs3 мента И-НЕ и второй вход первого и сл третий вход четвертого элементов И О5 группы объединены и являются первым О) входом блока, третьи входы первого, третьего и четвертого элементов И-НЕ, первого, второго и пятого элементов И группы, четвертьп вход второго элемента И-НЕ и вход чет вертого элемента И группы объединены и являются вторым входом блока, третьим и четвертыми входами которого являотся соответственно объединенные входы синхронизации и асинхронного сброса триггеров результата сравнения, выходы элементов И-НЕ