Ассоциативное запоминающее устройство

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК С 11 С 15/О Трудовогоена Дружбьститут того элеменпервого, вт тов И-НЕ и элемента И че ду первоготий вход втоетвертого элеод первого и ервому вхруппы, тртый входвторой в рого, четвмента И-НЕ вертого элемент ети входобъедблока ены и являются пе третьи входы перв вертого элементов уппь одом го,го и чет ретье-НЕ,ентов эле- втоетг ертоены треть рого я ненные еди -та- - НЕ хронн та ср ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬ(71) Казанский орденаКрасного Знамени и ордНародов авиационный иним. А.Н. Туполева(56) 1. Авторское свидетельство СССР В 332502, кл. С 11 С 15/00 ф 1970 ф2. Авторское свидетельство СССР Ф 780043, кл. Ь 11 С 15/00, 1980 (прототип).(54)(57) 1, АССОЦИАТИВНОЕ ЗАПОМИ 11 А 10- 1 ЦЕЕ УСТРОЙСТВО, содержащее регистры, блоки сравнения, блок управления и регистр опроса, выход которого соединен с первыми входами блоков сравнения, вторые входы которых соединены с выходами регистров, входы которых и вход регистра опроса соединены с одним из выходов блока управления, другие выходы которого подключены к третьим и четвертым входам блоков сравнения, о т л и - ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены блоки выбора результата поиска и блок анализа общего условия поиска, первый вход которого соединен с выходом регистра опроса, входы с второго по пятый соединены с одними из выходов блоков сравнения, шестой и седьмой входы - с другими выходами блока управления, а выходы подключены к одним иэ входов блоков выбора результата поиска, другие входы которых подключены к другим выходам блоков сравнения, а выходы являются выходами устройства. Я 010925 2, Устройство по п, 1, о т ли - ч а ю щ е е с я тем, что каждый блок сравнения содержит элементы И-НЕ, группу элементов И с первого по шестой, группу элементов ИЛИ и триггеры результата сравнения, единичные входы которых соединены через элементы ИЛИ группы с выходами элементов И группы, прямой выход первого триггера результата сравнения подключен к первым входам первого элемента И-НЕ, пятого и шестого элементов И группы, а инверсный выхоц - к первым входам второго, третьего, четвертого элементов И-НЕ и первому входу четвертого элемента И группы, прямой выход второго триггера результата сравнения подключей ко второму входу третьего элемента И - НЕ и первым входам второго и третьего элементов И группы, а инверсный выход - ко вторым входам первого, второго и пятого И группы, четвертый вход лемента И-НЕ и второй вхо о элемента И группы объе являются вторым входом б м и четвертыми входами ко вляются соответственно об входы синхронизации и ас го сброса триггеров резул внения, выходы элементовпервого по четвертый соединены соответственно с вторыми входами пятого, шестого, второго и третьего элементов И группы и являются одними из выходов блока, другими выходами которого являются выходы триггеров результатов сравнения.3. Устройство по пп1 и 2, о т - л и ч а ю щ е е с я тем, что блок анализа общего условия поиска содержит триггеры результата поиска, элементы НЕ, элементы И с первого по тридцать третий и элементы ИЛИ с первого по седьмой, причем прямой выход первого триггера результата поиска соединен с первыми входами четвертого и двадцать девятого элементов И, а его инверсный выход - с первыми входами шестого и двадцать седьмого элементов И, прямой выход второго триггера результата поиска соединен с первыми входами восьмого, двадцать второго, тридцатого и тридцать первого элементов И, а его инверсный выход - с первыми входами второго, двадцать шестого элементов И, инверсный выход третьего триггера результата поиска соединен с первыми входами пятнадцатого и девятнадцатого элементов И, прямой выход четвертого триггера результата поиска соединен с первыми входами третьего и седь" мого элементов И, а его инверсный выход " с третьими входами двадцать шестого и двадцать седьмого элементов И, вторые входы шестого, одиннадцатого и пятнадцатого элементов И и вход первого элемента НЕ, первые входы десятого, двадцатого,тридцатого, тридцать первого и трид. цать третьего элементов И и вход второго элемента НЕ, первый вход первого элемента И и вход третьегоэлемента НЕ, первые входы шестнадцатого, вторые входы пятого, восемнадцатого, двадцать девятого, тридцать второго элементов И и вход четвертого элемента НЕ, второй вход первого элемента И и вход пятого элемента НЕ соответственно объединены и являются входами блока с первого по пятый, шестым и седьмым входами которого являются соответственно объединенные одни из входов триггеров результата поиска, выходы элементов НЕ с первого по пятый подключены к . соответственно объединенным вторым входам второго, десятого и девятнадцатого элементов И, первым входампятого и семнадцатого элементов И, вторым входам седьмого, восьмого, шестнадцатого, двадцать шестого элементов И и второго элемента ИЛИ, вторым входам девятого и четырнадцатого элементов И, вторым входам третьего, четвертого, двенадцатого и двадцать седьмого элементов И и четвертого элемента ИЛИ, выход первого элемента И соединен с третьими входами второго, пятого, шестого, девятого, двадцать девятого, тридцать первого, первыми входами десятого, одиннадцатого элементов И и входом шестого элемента НЕ, выход второго элемента И соединен с вторым входом тринадцатого, первыми входа" ми четырнадцатого и двадцать первого элементов И, выход пятого элемен 1 та И соединен с третьим входом пятнадцатого, вторыми входами двадцать второго и двадцать третьего элементов И, выход шестого элемента И соединен с вторым входом семнадцатого, первыми входами восемнадцатого и двадцать третьего элементов И, выход девятого элемента И соединен с третьим входом девятнадцатого, вторыми входами двадцатого и двадцать первого элементов И, выход десятого элемента И соединен с вторыми входами двадцать четвертого, тридцатого и тридцать второго элементов И, выход одиннадцатого элемента И соединен с вторыми входами двадцать пятого, двадцать восьмого, тридцать третьего элементов И, вьжоды элементов И через соответствующие элементы ИЛИ, а выход шестого элемента НЕ непосредственно соединены с другими входами триггеров результата поисКа, выходы Первого и второго триггеров результата поиска являются выходами блока. 4. Устройство по пп, 1-3 о т - л и ч а ю щ е е с я тем, что каждый блок выбора результата поиска содержит дополнительные элементы И и дополнительный элемент ИЛИ, выход которого является выходом блока, а входы соединены с выходами дополнительных элементов И, входы которых являются входами блока.Изобретение относится к вычислительной технике, в частности, к запоминающим устройствам (ЗУ).Известно ассоциативное запоминающее устройство, содержащее накопитель, входы которого подключены к выходу регистра опроса и первому выходу блока управления, второй выход которого соединен с входом регистра опроса, разрядные шины 1.1 1.Недостатком этого устройства является большое количество оборудования.Наиболее близким к предлагаемому является ассоциативное запоминающее устройство, содержащее накопитель, входы которого подключены к выходу регистра опроса и первому входу бло" ка управления, второй выход которого соединен с входом регистра опроса, разрядные шины, группу элементов И, блоки местного управления, дополнительные накопители и блоки вывода результата поиска - по числу запоминающих ячеек накопителя, причем вхЬды дополнительных накопителей подключены к выходам соответствующих блоков местного управления, а выходы - соответственно ко входам блоков вывода результата поиска, одним из входом элементов И и. входам первой группы блоков местного управления, разрядные шины соединены с выходами элементов И и входами второй группы блоков местного управления, другие входы элементов И и входы третьей группы блоков местного управления подключены к выходам накопителя, третий выход блока .управления соединен с выходами четвертой группы блоков местного управления 1 2).В этом ассоциативном ЗУ производится поиск информации по критерию "ближайший" при помощи поразрядного сравнения признаков, начиная со старших разрядов, на словарных устройствах сравнения. Каждое словарное устройство сравнения состоит из группы элементов И, блока местного управления, дополнительных накопителей, блока вывода результата поиска. Разрядные шины являются шинами межсловарного объединения разрядных сигналов. Недостатком известного устройства является большое количество оборудования. Цель изобретения - упрощение устройства путем сокращения объема оборудования;Поставлеццая цель достигаетсятем, что в ассоциативное запоминающее устройство, содержащее регистры, блоки сравнения, блок управления и регистр опроса, выход которого соединен с первыми входами блоков сравнения, вторые входы которых подключецы к выходам регистроввходы которых и вход регистра опроса соединены с одним из выходов блока управления, другие выходы которого подключены к третьим и четвертымвходам блоков сравнения, введеныблоки выбора результата поиска иблок анализа общего условия поиска, 20 первый вход которого соединен с выходом регистра опроса, входы с второго по пятый соединены с однимицэ выходов блоков сравнения, шестой и седьмой входы - с другими выходами блока управления, а выходыподключены к одним из входов блоковвыбора результата поиска, другиевходы которых подключены к выходамблоков сравнения, а выходы являютсявыходами устройстваКроме того, каждый блок сравнения содержит элементы И-НЕ, группу элементовИ с первого по шестой, группу элементов ИЛИ и триггеры результата сравнения, единичные входы которых соединены через элементы ИЛИ группыс выходами элементов И группы, прямой выход первого триггера результата сравнения подключен к первымвходам первого элемента И-НЕ, пятого и шестого элементов И группы,а инверсный выход - к первым входамвторого, третьего, четвертого элементов И-НЕ и первому входу четвертого элемента И группы, прямой выход второго триггера результатасравнения подключен ко второму входу третьего элемента И-НЕ. и первымвходам второго и третьего элементов И группы, а инверсный выход -ко вторым входам первого, второго,четвертого элементов И-НЕ и первомувходу первого элемента И группы,третий вход второго, четвертый входчетвертого элементов И-НЕ и второйвход первого и третий вход четвертого элементов И группы объединены иявляются первым входом блока, третьи входы первого, третьего и чет10925 бб 3вертого элементов И-НЕ, первого,второго и пятого элементов И группы, четвертый вход второго элементаИ-НЕ и второй вход четвертого элемента И группы объединены и являютсявторым входом блока, третьим и четвертым входами которого являютсясоответственно объединенные входысинхронизации и асинхронного сбросатриггеров результата сравнения, выходы элементов И-НЕ с первого почетвертый соединены соответственнос вторыми входами пятого, шестого,второго и третьего элементов И группы и являются одними из выходов блока, другими выходами которого являются выходы триггеров результатасравнения,Блок анализа общего условия поиска содержит триггеры результата поиска, элементы НЕ, элементы И с первого по тридцать третий и элементы ИЛИ с первого по седьмой, причемпрямой выход первого триггера результата поиска соединен с первымивходами четвертого и двадцать девятого элементов И, а его инверсныйвыход - с первыми входами шестогои двадцать седьмого элементов И,прямой выход второго триггера результата поиска соединен с первь 1 мивходами восьмого, дцадцать второго,тридцатого и тридцать первого элементов И, а его инверсный выход -с первыми входами, второго, двадцать шестого элементов И, инверсныйвыход третьего триггера результатапоиска соединен с первыми входамипятнадцатого и девятнадцатого элементов И, прямой выход четвертоготриггера результата поиска соединенс первыми входами третьего и седьмого элементов И, а его инверсныйвыход - с третьими входами двадцатьшестого и двадцать седьмого элементов И, вторые входы шестого, одиннадцатого и пятнадцатого элементовИ и вход первого элемента НЕ, первые входы десятого. двадцатого.тридцатого. тридцать первого и трид 1цать третьего элементов И и входвторого элемента НЕ, первый входпервого элемента И и вход третьегоэлемента НЕ, первые входы шестнадцатого, вторые входы пятого, восемнадцатого, двадцать девятого, тридцать второго элементов И и вход четвертого элемента,НЕ, второй входпервого элемента И и вход пятого элемента НЕ соответственно объединены и являются входами блока с пер.ного по пятьп, шестым и седьмым входами которого являются соответственно объединенные одни из входовтриггеров результата поиска, выходыэлементов НЕ с первого по пятый подключены к соответственно объединенным вторым входам второго, десятого О и девятнадцатого элементов И, первымвходам пятого и семнадцатого элементов И, вторым входам седьмого,восьмого, шестнадцатого, двадцатьшестого элементов И и второго эле мента ИЛИ, вторым входам девятогои четырнаццатого элементов И, вторым входам третьего, четвертого,двенадцатого и двадцать седьмогоэлементов И и четвертого элемента ро ИЛИ, выход первого элемента И соединен с третьими входами второго, пятого, шестого, девятого, двадцатьдевятого, тридцать первого, первымивходами десятого, одиннадцатого эла 25 ментов И и входом шестого элементаНЕ, выход второго элемента И соединен с вторым входом тринадцатого,первыми входами четырнадцатого идвадцать первого элементов И, выход Зо пятого элемента И соединен с третьим входом пятнадцатого, вторыми входами двадцать второго и двадцатьтретьего элементов И, выход шестогоэлемента И соединен с вторым входомсемнадцатого, первыми входами восемнадцатого и двадцать третьегоэлементов И, выход девятого элемевта И соединен с третьим входом девятнадцатого, вторыми входами двад О цатого и двадцать первого элементов И, выход десятого элемента Исоединен с вторыми входами двадцатвчетвертого, тридцатого и тридцатьвторого элементов И, выход одиннад".цатого элемента И соединен с вторыми входами двадцать пятого, двадцатьвосьмого, тридцать третьего элементов И, выходы элементов И через соответствующие элементы ИЛИ, а выходшестого элемента НЕ непосредственно соединены с другими входами триггероврезультата поиска, выходы первогои второго триггеров результата поиска являются выходами блока. 5Каждый блок выбора результатапоиска содержит дополнительные элементы И и дополнительный элементИЛИ, выход которого является выходом блока, а входы соединены с выхо 109256635 дами дополнительных элементов И,входы которых являются входами блока.На фиг. 1 изображена структурнаясхема ассоциативного запоминающегоустройства; на фиг, 2 - структурная 5схема части устройства, содержащейблок сравнения и блок выбора резуль-.тата поиска; на фиг. 3 - структурнаясхема блока анализа общего условияпоиска.Ассоциативное запоминающее устройство содержит (фиг. 1) регистры 1,составляющие накопитель 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 с первого по З 0шестой, группу элементов ИЛИ 46 и 47,Блок 21 выбора результата поиска содержит дополнительные элементы И 48и 49 и дополнительный элементИЛИ 50,Блок 18 анализа общего условияпоиска содержит элементы НЕ 51-56с первого по шестой, элементыИ 57-89 с первого по тридцать третий, элементы ИЛИ 90-96 с первого 40по седьмой и триггеры 97-100 результата поиска с первого по четвертый.В предложенном устройстве выявление. признака "ближайший" по значению к опросному выявляется при помощи сравнения (х+х )/2 с у, котороеБлок 4 использует четыре разрядные шины 5-8 и имеет четыре состояния:а-(х=у) о(х=х) - начальноесостояние;аг (х ) у)(х =х ) состояниеУ,= 11а - (х (у)сб(х =х ) - состояние3Я =1лфа - (ху, фо(х е х Ох ) - состояниесброса,Окончательный выбор признаков, удовлетворяющих критерию "ближайший"среди х; е х и х е х, производит сяна соответствующих блоках 21.Устройство работает следующимобразом,Под действием сигналов с блока9 управления с регистров 1 и 3 наблоки 4 сравнения поступают разрядные значения опросного и записанных признаков ( битовые слои 1,начиная со старших разрядов. Блоки 4 сравнения выявляют признаки:лх Е 2 - состояние а и х Ех - сог 1 гстояние а .При этом на разрядныхшинах 5-8 появляются сигналы, соответствующие разрядным значениямх., х и сигналы первых неравенствХ 1)уу х(у. Используя эти сигналыи разрядные значения у, поступающие с регистра 3, блок 18 вычисляет Яцп(х +х -2 у) и вырабатывает12сигналы: на выходе 19 - соответствующий значению х +х - 2 у), О, на2выходе 20 - соответствующий значению х 1+х -2 уО с определенной точностью при анализе каждого текущегобитового слоя. Эти сигналы поступают на блоки 21 выбора результата.поиска. Сигнал на выходе 33 блока21 соответствует выполнению условия:+Х 2-2 у0), что соответствует критерию "ближайший", После анализа всехразрядов признаков единичные сигналы на выходах 33 выявляют признаки, ближайшие по числовому значению к опросному. т.е. соответствующие ш 1 п(1 х -у 1).Технико-экономическое преимущество предложенного устройства заключается в его уприцении по сравнению с прототипом.1092566Составитель В, Рудаковдактор К. Волощук Техред Л,Коцюбняк Корректор Г. Решетник Заказ 3262/3Тираж 575 Подписно ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д,Филиал ЛЛП "Патент", г. Ужгород, ул, Проектная, ч