Ассоциативный запоминающий элемент

СОЮЗ СОВЕТСКИ ааимьамааех СОУБЛИК 1 С 15/О УДАРСТВЕННЫЙ КОМИТЕ ДЕЛАМ ИЗОБРЕТЕНИЙ И ГОС Т СССРГЮ ОТКРЫТИИОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ детельство СССР15/00, 1976,тельство СССР15/00, 1976 и(21) 3354085/18-24С 22) 05.11,81(54)(57) АССОЦИАТИВНЫЙ ЭАПОМИНИОЩИЙ ЭЛЕМЕНТ, содержащий элемент памяти, злементй ИЛИ, первый, второй и третий элементы И, причем первый выход элемента памяти подключен и первому входу первого элемента И, второй вход которого соединен с первым входом второго элемента И, а выход - с первым входом первого элемента ИЛИ, второй и третий входи первого элемента И и первый вход второго элемента ИЛИ являются одними.из входов ассоциативного запоминающего элемента, одними из выходов которого являются выходи первого и второго элементов ИЛИ, о т л и ч а ю щ и й с я тем, что, с целью расширения Функциональных возможностей элемента за счет реализации поиска по признакам фне больше", фне меньше", "бл жайшее большее" и "ближайшее меньшееф, в него введены четвертый и пятый элементы, И, третий и четвертый элементы ИЛИ и элементы НЕ, причем выходы четвертого и пятого элементов И соединены соответственно с первыми входами третьего и четвертого элементов ИЛИ, второй вход третьего элемента ИЛИ подключен к выходу первого элемента И и входу первого элемента НЕ, второй вход четвертого элемента ЙЛИ соединен с выходом второго элемента И, . входом второго элемента НЕ и вторым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно к первому и ко второ-му входам третьего элемента И, третий вход которого соединен с первым входом второго элемента И, второй входкоторого подключен ио второму выходу элемента памяти, третий вход второго элемента И, пер- Я вый и второй входы четвертого и пятого элементов И и второй вход первого элемента ИЛИ являются другими входами ассоциативного запоминающего элемента, другими выходами которого являются выходы третьего элемента И, третьего и четвертого элементов ЙЛИ.Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может бытьиспользовано в информационно-поисковых системах,Известен ассоциативный запоминающий элемент, который содержит суюаатор, три накопителя, три регистра,блок, контроля, блок управления, преобразователь кода и элементы И 11. 10Недостатком этого элемента является невозможность выполнения заодну команду операций поиска чисел,"ближайшего большего" и "ближайшегоменьшего" к заданному, что ограничивает его функциональные возможности.Наиболее близким к предлагаемомуизобретению является ассоциативныйзапоминающий элемент, содержащийзапоминающий элемент, схему сравнения, три элемента И и два элементаИЛИ, причем два выхода запоминающего элемента соединены с первым ивторым входами схемы сравнения, выходкоторой соединен со вторым входомпервого элемента И, второй выходзапоминающего элемента; кроме того,соединен со вторым входом второгоэлемента И, первый вход которого соединен с первым входом первого элемента И и первым логическим вхоДом,третий вход второго элемента И итретий вход схемы сравнения соединены с шиной опроса, первый и второй входы третьего элемента И соединекы соответственно со вторымлогическим входом и шиной запрета,выход третьего элемента И соединенс первым входом первого элемента ИЛИ,второй вход которого соединен с 40выходом второго элемента И и первымвходом второго элемента ИЛИ, второйвход последнего соединен с третьимлогическим входом; а выход является третьим логическим выходом, выход первого элемекта И и выход первого элемента ИЛИ являются соответственно первым и вторым логическими выходами 121.50Недостатком известного элемента является то, что он не выполняет поиск по признакам фне больше", "не меньше", "ближайшее большее (меньшее), что ограничивает его Функциональные возможности.Целью изобретения является расширение Функциональных возможностей ассоциативного запоминающего элемента за счет реализации поиска по признакам "не больше", "не меньше", 60 "ближайшее большее" и "ближайшее меньшее".ПоставленНая цель достигается тем, что в ассоциативный запоминающий элемент, содержащий элемент памяти, элементы ИЛИ и первый, второй и третий элементы И, причем пер вый выход элемента памяти подключен к первому входу первого элемента И, второй вход которого соединен с первым входом второго элемента И, а выход - с первым входом первого элемента ИЛИ, второй и третий входы первого элемента И и первый вход второго элемента. ИЛИ являются одними из входов ассоциативного запоминающего элемента, одними из выходов которого являются выходы первого и второгоэлементов ИЛИ, введены четвертый и пятый элементы И, третий и четвертый элементы ИЛИ и элементы НЕ,причем. выходы четвертого и пятогоэлементов И соединены соответственно с первыми входами третьего и четвертого элементов ИЛИ, второйвход третьего элемента ИЛИ подключен к выходу первого элемента И и входу первого элемента НЕ, второй вход четвертого элемента ЙЛИ соединен с выходом второго элемента И, входом второго элемента НЕ и вторым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно к первому и ко второму входам третьего элемента И; третий вход которого соединен с первым входом второго элемента И, второйвход которого йодключен ко второму выходу элемента памяти, третий вход второго элемента И, первый и второй входы четвертого и пятого элементов И и второй вход первого элемекта ИЛИ являются другими входами ассоциатив- ного запоминающего элемента, другими выходами которого являются выходы третьего элемента И, третьего и четвертого элементов ИЛИ.На фиг. 1 приведена структурная схема ассоциативной матрицы памяти; на фиг. 2 - Функциональная схема предлагаемого ассоциативного элемента; на фиг. 3-5 - функциональные схем блока запрета сигналов лере- носа, дешифратора признака опроса и логического блока.Ассоциативная матрица памяти содержит (Фиг. 1) СхК (где С - число строк, К - число разрядов матрицы) ассоциативных запоминающих элементов 1 (АЗЭ), блоки 2 запрета сигналов переноса, дешифратор 3 признаков поиска и логические блоки 4.Предлагаемый ассоциативный запоминающий элемент содержит (фиг. 2) элемент 5 памяти, три элемента И 68, первйй 9 и второй 10 элементы ИЛИ, четвертый 11 и пятый 12 элементы И, третий 13 и четвертый 14 элементы ИЛИ, первый 15 и второй 16 элементы НЕ.Каждый блок запрета сигналов перекоса содержит (фиг, 3) элементы И 17,и 18 и элементы НЕ 19 и 20,Дешифратор признаков поиска содержит (фиг. 4) регистр 21 признака,дешиФратор 22 и элементы ИЛИ 23-25Каждый логический блок содержит(фиг. 5) элементы И 26-28 и элемент ИЛИ 29.На фиг. 1 и 2 обозначены входы30-38 и выходы 39-43 ассоциативного запоминающего элемента, На Фиг. 1,3, 4 и 5 обозначены входы 44-46дешифратора признаков поиска, вхо Оды 47-49 и выходы 50 логических блоков.Предлагаемый ассоциативный запоминающий элемент работает следующимобразом. 5. Входная информация представляеткод числа Х, по которому производится поиск, и код вида поиска. Код числа Х поступает на входы 33 и 34(Фиг. 2), причем вход 33 соответствует "единичному" плечу соответствующего разряда, а вход 34 - фнулевомуф плечу. Код вида поиска подаетсяна вход 44 дешифратора 3 и затемна входы 37 и 38 элемента 1. Выходная информация снимается с выходов50 блоков 4 (фиг. 1).Рассмотрим работу элемента 1 напримере поиска по признакам: "равно", больше", "меньше", "не больше 3 О(больше или равно)". Для данных видов поиска дешифратор 3 формируетна входах 45 и 46 сигналы фОф. ВрезУльтате элементы И 17 и 18 всехблоков закрыты, на входах 37 и 38всех элементов 1 имеется сигнал ф 1 фи элементы И 11 и 12 (фиг. 2) открыты для сигналов, поступающих по,входам 30 и 31.В каждом из элементов 1 выполняется сравнение значения аец кодачисла А, хранящегося в элементах 5,со значением х кода числа Х. Присравнении кодов двух чисел имеет мес то соотношение: если во всех старшихразрядах вплоть до некоторого Р-гоимело место равенство а-" хк дляК Р, а в Р-ом РазРЯДе аСК Ф хК,.то если ас,хк, то АХ, еслиа сх то А ( Х, независимо от соотск кфношения ас и х, для,всех К С Р.Сравнеййе осуществляется одновременно во всех строках матрицыпоследовательно по разрядам, начиная со старшего К разряда (крайнего левого на фиг, 1). При этом навходы 30, 31, 35 и 36 подаются сигналы, соответствующие принятому длявыбранной элементной базы представлению нуля, а на входы 32 - представлению единицы. При этом на выходах элементов И 11. и 12 этогоАЗЭ 1 формируется "Оф. Сигналы навыходах 41-43 формируются благодарясигналу "1", поступающему на вход 65 32, и зависят от состояния элементовИ 6-8,Рассмотрим возможные варианты соотнощения значений ас, и х, При двоичном представлении чисел они могутпринимать значение "Оф или "1", поэтому возможны четыре варианта соотношения их значений:ац, хкО, 01 . 11 00 . 1При этом, когда ас, = О, на первом выходе элемента 5 имеет местосигнал фОф, на втором - "1", когдаас = 1, на нервом выходе элемента5 - "1", на втором - "0". Аналогичным образом определяются сигналына гходах 33 и 34, когда хк = О,на входе 33 имеем фОф, на.входе34 - "1", когда хк = 1, на входе33 - "1 ф, на входе 34 - фО".В первых двух вариантах элементыИ б и 7 закрыты, В первом вариантеэлемент И 6 закрыт сигналом ф 0",поступающим с первого выхода элемента 5, а элемент, И 7 - сигналом"0", поступающим со входа 33. Вовтором случае элемент И 6 закрытсигналом "0", поступающим с входа34, а И 7 - сигналом фОф, поступающим со второго выхода элемента 5.В результате в обоих вариантах навыходах элементов И б и 7 имеетместо сигнал фО", на обоих входахэлементов ИЛИ 13 и 14 имеются сигнала фОф и иа выходы 41 и 42 поступают сигналы "О".Снгналы фО",с выходов элементовИ 6 н 7 проходят соответственночерез элементы НЕ 15 и 16, инвертнруются в "1 ф, в результате на всехтрех входах элемента И 8 имеютсясигналы ф 1 ф и на выходе 43 формируется сигнал "1".Таким образом, если в элементе1 какого-либо разряда матрицы, начиная со старшего, зафиксированоравенство значений кодов числа А ичисла Х,то на входы 30 и 31 элемента 1 следующего разряда передаются сигналы фОф, а на вход 32 сигнал ф 1 ф с выходов 41-43 предыдущего элемента 1.В третьем варианте (аск = 1,х д 0) на всех трех входах элеКе. нмента И.б имеются сигналы 1, наего выходе форжруется "1", этотсигнал через элемеит ИЛИ 13 передается на выход 41, Кроме того, сигнал ф 1 ф с выхода элемента И б поступает на элемент НЕ 15, инвертируетсяв фОф, который поступает напервый вход элемента И 8 и в результате на выход 43 поступает "0". Элемент И 7, закрыт сигналами "Оф, поступающньы на его входы со входа 33и со второго выхода элемента 5. Навыходе элемента И 7 имеется фО",на обоих входах элемента ИЛИ 14 сигналы равны "0" и в результате навыходе 42 имеется "0".Элементы И 11 всех элементов 1строки открыты для передачи сигналов со входов 30, в результате сформированный сигналс выхода 41 элемента 1 старшего разряда беспрепятственно распространяется до выхода1041 элемента 1 самого младшего разряда и поступает на вход элементаИ 26 блока (фиг. 5) для формирования результата поиска по строке матрицы. 15Сигнал "0" с выхода 43 элемента1 (фиг. 1) старшего разряда передается на вход 32 элемента 1 следующего разряда и закрывает элементыИ 6-8 (Фиг. 2), в результате чего 2 Оисключается возможность выработкисигналов. "1 ф на выходах 42 и 43элементов 1 всех последующих разрядов строки.Таким образом, в третьем варианте формируется решение АХ, которому соответствует сигнал "1" навыходе 41,В четвертом варианте сигнал "1"имеет место на всех трех входахэлемента И 7, на его выходе Формируется сигнал "1", который черезэлемент ИЛИ 14 передается на выход 42.Схема симметрична относительносигналов на входах 30 и 32 и Формиро-З 5ванне сигналов на выходах 41 и 43 происходит аналогично третьему варианту. В результате Формируются сигналы"0" на выходах 41 и 43. Сигнал "1 фс выхода 42 элемента 1 распространяется беспрепятственно до выхода 42элемента И 28 блока 4, в результате .Формируется решение А с Х,Таким образом, в результате сравнения А; с Х формируется сигнал "1" 45на выходе 41 либо 42, либо 43 элемента 1 младшего разряда строки матрицы.В соответствии с заданным видомпоиска дешифратор формирует сигнал 5 О"меньше" - на входе 49, "не меньше"на входах 47 и 48, "не большена входах 48 и 49.55Эти сигналы подаются на первыевходы элементов И 26-28 всех блоков,разрешая прохождение через нихсоответствующей виду поиска комбинации сигналов с выходов 41-43 элемента 1 младшего разряда строки.,Цля,примера рассмотрим поиск поПризнаку ."не меньше". В этом случаесигнал ф 1" имеется на первых входахэлементов И 26 и 27 всех блоков, Если в результате сравнения окажется 5 что А 4 Х, то будет сформирован сигнал "1" на выходе 42 элементов 1 строки, т.е. на втором входе элементаЙ 28 соответствующего блока,4,но на первом его входе - фО", врезультате на выходе элемента И 28Формируется "О", элементы И 26 и 27также закрыты, так как на входах 41 и 43 имеют место сигналы "0". Таким образом, на всех трех входах элеиента ИЛИ 29 имеются сигналы "О" и на выходе 50 "Оф, что свидетельствует о том, что А не удовлетворяет условию поиска,Если же в результате сравнения фиксируется АХ или А = Х, то сигнал "1" поступает соответственно на выход 41 или на выход 43 элемента 1, т.е. на вход элемента И 26 либо элемента И 27, в результате один из этих элементов оказывается открытым и выдает на выход сигнал "1", этот сигнал через элемент ИЛИ 29 передается на выход 50,. Фиксируя, чтоАс удовлетворяет условиям поиска.Рассмотрим поиск по признаку ".ближайшее большее". В основу поиска наименьшего из чисел, превышающих заданное число, можно положитьследующий алгоритм: последовательно, начиная со старшего разряда, срав-. ниваются а с х к одновременно для всех строк матрицы.Например, рассмотрим два числа- АИ А ,такие, что ХА , ХА 2 и АА 2.Очевидно, что факт превышения А над Х должен обнаружитЬся раньше, чем Анад Х, т,е. в более старших разрядах. А так как по условиям поиска должно быть найдено самое меньшее число из тех, которые превышают Х, то программа поиска должна быть следующей если в очередном разряде обнаружено, что хК ъ а , то число исключается из рассмотрения, если х = а, та обязательно делается анализ следующего разряда, если равенство выполняется и в последующих разрядах, то фиксируется Х = А и выдается сигнал "1 ф на выход 41 младшего Разряда строки, если хкс а, то сигнал со входа 30 (выхода 41) распространяется до тех пор, пока не встретится разряд, в котором хотя бы для одного числа окажется, что во всех раэрядах до данного было хк = аск в. данном х с ас. При возникновении такой ситуацйи прерывается передача сигнала со входа 30 на выход 41 для всех чисел (по всем строкам), В результате сигнал по вхсду ЗО остается только для чисел, для которых в данном разряде (а не левее)имеет место х КасиДля выявления соотношения между числами Ас в элементе 1 использу1024987 М 38 И 1 ются элементы ИЛИ 9 и 10, позволяю-щие по сигналам, вырабатываемым блоками 2 на входах 37 и 38, прерывать передачу сигналов со входа 31 при поиске ближайшего большего" и сигналов со входа 32 при поиске 5 "ближайшего меньшего". При поиске "ближайшего большего" дешифратор 3 формирует на входе 45 сигнал фОф, в результате на входах 38 всех элементов 1 присутствуют сигналы "1", 10 вырабатываемые блоками 2, и элементы И 12 оказываются постоянно открытыми для сигналов, поступающих по входам 31. На входе 46 дешифратор 3 формирует сигнал "1", в результате чего в блоках 2 элементы И 18 открыты для сигналов, Формируемых элементами 1 на выходах 40.Если, например, в одном из разрядов одного из чисел х с а, тоск в элементе 1 на выходе элемента И б будет сформирован сигнал 11.", который с выхода 40 будет передан на вход элемента И 18 соответствующего этому разряду блока 2, с входа 37 которого сигнал "0" - на входы 37 всех элементов 1 других строк данного разряда, в результате чего элементы И 11 в них будут закрыты и сигналы со входов 30 будут прерваны, т.е. не смогут пройти в этихэлементах 1 на выходы 41. В результате сигнал ф 1" Формируется на выходе 43 элемента 1 младшего разряда строки в случае, если А с = Х и на выходе З 5 41 в случае, если Ас является наимень. шим из всех чисел, превосходящих заданное Х, Если окажется, что имеется несколько равных чисел, являющихся наименьшими из превосходящих заданное число Х, то сигналы "1" Формируются на выходах 41 всех элементов 1, расположенных в младшем разряде соответствующих строк, затем эти сигналы "1 ф поступают на выходы 50 соответствующих блоков 4, для чего на входе 47 дешифратора 3 Формируется сигнал 1"Аналогичным образом работают элементы 1 при поиске "ближайшего меньшегоф, но в этом случае дешифратор 3 формирУет "1" на входах 45 и 49, а благодаря сигнапам, проходящим че рез элементы ИЛИ 10, организуется управление элементами И 12, в результате чего прерывается передача сигналов со Входом 32 и сигнал "1" появляется на выходе 42.Таким ббразом, предлагаемый элемент ассоциативной матрицы памяти, не уступая известным по быстродействию, реализует поиск по большему числу признаков, ие требует комму" тации в элементах ассоциативной памяти при переходе от одного вида поиска к другому и не требует вмешательства программы для определе- ния результата поиска по сигналам на выходах устройства.Технико-экономическое преимущество предлагаемого ассоциативного запоминающего элемента, по сравнению с известньщ, заключается в его более широких Функциональных возможностях.,Редактор Л. Филиппова Техредд. Пекарь Корре В. Гири Филиал ППП фПатент", г. Ужгород, ул. Проектн Заказ 4406/49 ВНИИПИ по 113035, Мо