Ассоциативный запоминающий элемент Советский патент 1983 года по МПК G11C15/00 

Изобретение относится к вычисли тельной технике, в частности к зап минающим устройствам, и может быть использовано в информационно-поисковых системах. Известен ассоциативный запоминаю щий элемент, который содержит тор, три накопителя, три регистра, блок контроля, блок управления, пре образователь кода и элементы И ij Недостатком этого элемента является невозможность выполнения за одну команду операций поиска, чисел ближайшего большего и ближайшего меньшего к заданному, что ограничи вает его функциональные возможности. Наиболее близким к предлагаемому изобретению является ассоциативный запоминающий элемент, содержащий запоминающий элемент, схему сравнения, три элемента И и два элемента ИЛИ, причем два выхода запоминающего элемента соединены с первым и вторым входами схемы сравнения, вых которой соединен со втор«лм входом первого элемента И, второй выход запоминающего элемента, кроме того, соединен со вторым входом второго элемента И, первый вход которого со динен с первым входом первого элемента И и первым логическим входом, третий вход второго элемента И и третий вход схемы сравнения соединены с шиной опроса, первый и второй входы третьего элемента И соединены соответственно со вторым логическим входом и шиной запрета, выход третьего элемента И соединен с первым входом первого элемента ИЛ вторюй вход которого соединен с выходом второго элемента И и первым входом второго элемента ИЛИ, второй вход последнего соединен с третьим логическим входом, а выход является третьим логическим выходсян, выход первого элемента И и выход первого элемента ИЛИ являются соответс венно первым и вторым логическими в ходами . Недостатком известного элемента является то, что он не выполняет по иск по признакам не больше, не меньше, ближайшее большее (меньшее), что ограничивает его функциональные возможности. Целью изобретения является расширение функциональных возможностей ассоциативного запоминающего элемен та за счет реализации поиска по признакам не больше, не меньше, ближайшее большее и ближайшее меньшее. Поставленная цель достигается тем, что в ассоциативный запоминающий элемент, содержащий элемент памяти, элементы ИЛИ и первый, второй и третий элементы И, причем первый выход элемента памяти подключен к первому входу первого элемента И, второй вход которого соединен с первым входом второго элемента И, а выход - с первым входом первого элемента ИЛИ, второй и третий входы Первого элемента И и первый вход второго элемента ИЛИ являются одними из входов ассоциативного запоминаниаего элемента, одними из выходов которого являются выходы первого и второго элементов ИЛИ, введены четвертый и пятый элементъа И, третий и четвертый элементы ИЛИ и элементы НЕ, причем выходы четвертого и пятого элементов И соединены соответственно с первыми входс1ми третьего и четвертого элементов ИЛИ, второй вход третьего элемента ИЛИ подключен к выходу первого элемента И и входу первого элемента НЕ, второй ,вход четвертого элемента ИЛИ соединен с выходом второго элемента И, входом второго элемента НЕ и вторым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно к первому и ко второму входам третьего элемента И/ третий вход которого соединен с первым входом второго элемента И, второй вход которого подключен ко второму выходу элемента памяти, третий вход второго элемента И, первый и второй входа четвертого и пятого элементов Ни второй вход первого элемента ИЛИ являются другими входами ассоциативного запоминающего элемента, другими выходами которого являются выходы третьего элемента И, третьего и четвертого элементов ИЛИ. На фиг, 1 приведена структурная схема ассоциативной матрицы памяти/ на фиг. 2 - функциональная схема предлагаемрго ассоциативного элемента; на фиг. 3-5 - функциональные схемы блока запрета сигналов переноса, дешифратора признака опроса и логического блока. Ассоциативная матрица памяти содержит (фиг. 1) СхК (где G - число строк, К - число разрядов матрицы), ассоциативных запоминаюйях элементов 1 (АЗЭ), блоки 2 запрета сигналов переноса, дешифратор 3 признаков поиска и логические блоки 4. Предлагаелалй ассоциативный запоминающий элемент содержит (фиг. 2) элемент 5 памяти, три элемента И 6-8, первый 9 и второй 10 элементы ИЛИ, четвертый 11 и пятый 12 элементы И, третий 13 и четвертый 14 элементы ИЛИ, первый 15 и второй 16 элементы НЕ. Каждый блок запрета сигналов переноса содержит, (фиг. 3) элементы И 17 и 18 и элементы НЕ 19 и 20. Дешифратор признаков поиска содержит (фиг. 4) регистр 21 признака, дешифратор 22 и эле|и1еиты ИЛИ 23-25. Каждый логический блок содержит (фиг. 5) элементы И 26-28 и элемент ИЛИ 29. На фиг. 1 и 2 обозначены входы 30-38 и выходы 39-43 ассоциативного запоминающего элемента. На ф.иг. 3, 4 и 5 обозначены входы 44-46 дешифратора признаков поиска, входы 47-49 и выходы 50 логических бло ков. Предлагаемый ассоциативный запоминающий элемент работает следующим образом. Входная информация представляет код числа Х по которому производит ся поиск, и код вида поиска. Код чи ла X поступает на входы 33 и 34 (фиг. 2), причем вход 33 соответствует единичному hлечу соответствующего разряда, а вход 34 - нулев му плечу. Код вида поиска подается на вход 44 дешифратора 3 и затем на входы 37 и 38 элемента 1. Выходмая информация снимается с выходов 50 блоков 4 (фиг. 1). Рассмотрим работу элемента 1 на примере поиска по признакам: равно , больше, меньше, небольше (меньше или равнр) , не меньше ({Больше или равно). Для данных ви дов поиска дешифратор 3 формирует на входах 45 и 46 сигналы О. В результате элементы И 17 и 18 всех блоков закрыты, на входах 37 и 38 всех элементов 1 имеется сигнал 1 и элементы И 11 И 12 (фиг. 2) отк рыты для сигналов, поступающих по, BJxpдaм.ЗO и 31. В каждом из элементов 1 выполняется сравнение значения кода числа А, хранящегося в элементах 5, со значением у. кода числа X. При сравнении кодов двух чисел имеет ме то соотношение: если во всех старши разрядах вплоть до некоторого Р-го имело место равенство а Хц для , а в Р-ом разряде а (.. Xj, то если а х, то , если Xj, то , независимо от соот ношения и х для ,всех КС Р. Сравнение ocsщecтвляeтcя одновременно во всех строках матрицы последовательно по разрядам, начиная со старшего К разряда (крайнего левого на фиг. 1). При этом на входы 30, 31, 35 и 36 подаются сигналы, соответствующие принятому для выбранной элементиой базы представ лению нуля, а ни входы 32 - представлению единицы. При этом на выходах элементов И 11 и 12 этого АЗЭ 1 формируется О. Сигналы на выходах 41-43 формируются благодар поступающему на вход сигналу 32, и зависят от состояния элементов И 6-8. Рассмотрим возможные варианты соот- ношения значений а, и х,. При двоичном представлении чисел они могут принимать значение О или 1, поэтому возможны четьфе варианта соотношения их значений: и к 0О 11 1О О1 При этом, когда а О, на первом выходе элемента 5 имеет место сигнал О, на втором - 1, когда 1, на первом выходе элемента 5 - 1, на ВТОРСН4 - О. Аналогич ным образом ся1ределяются сигналы на гходгьх 33 и 34, когда Х((. О, на входе 33 имеем О, на.входе 34 - 1, когда XK 1 на входе 33 - 1, на входе 34 - О. В первых двух вариантах элементы И 6 и 7 закрыты. В первом варианте элемент И 6 закрыт сигналом О, поступающим с первого выхода элемента 5, а элемент, И 7 - сигналом О, поступающим со входа 33. Во втором случае элемент И 6 закрыт сигналом О, поступающим с входа 34, а И 7 - сигнёшом О, поступающим со второго выхода элемента 5. В результате в обоих вариантах на выходах элементов И 6 и 7 имеет место сигнал О, на обоих входах ИЛИ 13 и 14 имеются .сигналы 0 и на выходы 41 и 42 поступают сигналы О. Сигналы О .: выходов элементов И 6 и 7 проходят соответственно через элементы НЕ 15 и 16/ инверти руются в 1, в результате на всех трех входах элемента И 8 имеются сигналы 1 и на выходе 43 формируется сигнал 1. Таким образом если в элементе 1 какого-либо разряда матрицы, начиная со старшего, зафиксировано равенство значений кодов числа А и числа Х то на входы 30 и 31 элемента 1 след оощего разряда передаются сигнатш О, а на вход 32 сигнгш 1 с выходов 41-43 предыдущего а 1. В третьем ва{ 1аите (а 1, х 0) на всех трех входах элемента И 6 имею ся сигналы 1, на его выходе формируется 1, этот , сигнал через элемеит ИЛИ 13 передается на выход 41. Креме того, сигнал 1 с выхода элемента И б поступает на 3|Лемент НЕ 15, инвертируетсяв О, поступает на первый вход элемента И 8 и в результате на выход 43 поступает О. Элемент И 7 закркг сигналами О, поступающикб на его входа со входа 33 и со второго выхода элемента 5. На выходе элемента И 7 имеется О, на обоих входах элемента ИЛИ 14 си налы равны О и в результате на выходе 42 имеется О. Элементы И 11 всех элементов 1 строки открыты для передачи сигналов со входов 30, в результате сфо мированный сигнал с выхода 41 элемента 1 старшего разряда беспрепят ственно распространяется до выхода 41 элемента 1 самого младшего разряда и поступает на вход элемента И 26 блока (фиг. 5) для формирования результата поиска по строке ма рицы. Сигнал О с выхода 43 элемента 1 (фиг. 1) старшего разряда переда ется на вход 32 элемента 1 следующего разряда и закрывает элементы И 6-8 (фиг. 2), в результате чего исключается возможность выработки сигналов 1 на выходах 42 и 43 элементов 1 всех последующих разря дов строки. Таким образом, в третьем варианте формируется решение А(- X, которому соответствует сигнал I на выходе 41.. В четвертом варианте сигнал 1 имеет место на всех трех входах элемента И 7, на его выходе формируется сигнал 1, который через элемент ИЛИ 14 передается на выход 42. Схема симметрична относительно сигналов на входах 30 и 32 и формир вание сигналов на выходах 41 и 43 происходит, аналогично третьему варианту. В результате формируются сигнал О на выходах 41 и 43. Сигнал 1 с выхода 42 элемента 1 распространяется беспрепятственно до выхода 4 элемента И 28 блока 4, в результат формируется решение А Х. Таким образом, в результате срав нения А с X фо1 иру€тся сигнал 1 на выходе 41 либо 42, либо 43 элемента 1 младшего разряда строки мат рицы. В соответствии с заданным видом поиска дешифратор формирует сигнал по признакам: больше - на входе 47, равно - на входе 48, меньше - на входе 49, не меньше на входах 47 и 48, не больше на входах 48 и 49. Эти сигналы подаются на первые входы элементов И 26-28 всех блоков разрешая прохождение через них соответствующей виду поиска комбина ции сигналов с выходов 41-43 элемен та 1 младшего разряда строки. Для,примера рассмотрим поиск по признаку не меньше. В этом случае игнёл 1 имеется на первых входах элементов И 26 и 27 всех блоков. Ес ли в результате сравнения окажется что АС X, то будет сформирован сигнал 1 на выходе 42 элементов 1 строки, т.е. на втором входе элемента -.И 28 соответствующего блока .4, но на первом его входе - О, в результате на выходе элемента И 28 формируется О, элементы И 26 и 27 также закрыты, так как на входах 41 и 43 имеют место сигналы О. Таким образом, на всех трех входах элеиента ИЛИ 29 имеются сигналы О и на выходе 50 О, что свидетельствует о том, что АС не удовлетворяет условию поиска. Если же в результате сравнения фиксируется или А. X, то сигнал 1 поступает соответственно на выход 41 или на выход 43 элемента 1, т.е. на вход элемента И 26 либо элемента И 27, в результате один из этих элементов оказывается открытым и выдает на выход сигнал 1, этот сигнал через элемент ИЛИ 29 передается на выход 50,- фиксируя, что А(; удовлет воряет условиям поиска. Рассмотрим поиск по признаку ближайшее большее. В основу поиска наименьшего из чисел, превышающих заданное число, можно положить следующий алгоритм: последовательно, начиная со старшего разряда, срав--. ниваются ас)4 с х ц одновременно для всех- строк матрицы. Например, расс.мотрим два числа А И А такие, что X А , X Ag и А,| А Очевидно, что факт превышения AJ над X должен обнаружиться раньше, чем А J. над X, т.е. в более старших разрядах. А так как по условиям поиска должно быть найдено самое меньшее число из тех, которые преввюают X, то программа поиска должна быть следующей: если в очередном разряде обнаружено, что хц а., , то число исключается из рассмотрения, если X j; ас|, то обязательно делается анализ следующего разряда, если равенство вьшолняется и в последуюищх разрядах, то фиксируется X А и выдается сигнал 1 на выход 41 младшего разряда строки, если Хц иск;, то сигнал со входа , 30 (выхода 41) распространяется до тех пор, пока не встретится разряд, в котором хотя бы для одного числа окажется, что во всех разрядах до данного было х в. данном XIJ а(.|/ . При возникновении такой ситуации прерывается передача сигнала со входа 30 на выход 41 для всех чисел (по всем строкам). В результате сигнал по входу 30 остается только для чисел, для которых в данном разряде (а не левее) меет место х . а . Для выявления соотношения между ислами АС в элементе 1 используются элементы ИЛИ 9 и 10, позволяющие по сигналам, вырабатываемым блоками 2 на входах 37 и 38, прерывать передачу сигналов со входа 31 при поиске ближайшего большего и сигналов со входа 32 при поиске ближайшего меньшего. При поиске ближайшего большего дешифратор 3 формирует на входе 45 сигнал 0., в результате на входах 38 всех эле ментов 1 присутствуют сигналы 1, вырабатываемые блокеми 2, и элементы И 12 оказываются постоянно открытыми для сигналов, поступаю 1ДИХ по входам 31. На входе 46 дешифратор 3 формирует сигнал 1, в результате чего в блоках 2 элементы И 18 открыты для сигналов, формируемых элементами 1 на выходах 40. Если, например, в одном из разрядов одного иэ чисел xj. , то в элементе 1 на выходе элемента И будет сформирован сигнал , который с выхода 40 будет передан на вход элемента И 18 соответствующег эхому разряду блока 2, с входа 37 которого сигнал О - на входы 37 всех элементов 1 других строк данн го разряда, в результате чего элементы И 11 в них будут закрыты и сигналы со входов 30 будут прерваны, т.е. не смогут пройти в этих эл ментах 1 на выходы 41. В результат сигнал 1 формируется на выходе 4 элемента 1 младаего разряда строки в случае, если Л с; X и на выходе 41 в случае, если Ас является наим шим из всех чисел, превосходящих заданное X. Если окажется, что имеется несколько равных чисел, являющихся наименьшими из превосходящих заданное число X, то сигналы 1 формируются на выходах 41 iscex элементов 1, расположенных в младшем разряде соответствующих строк, затем эти сигнашы 1 поступают на выходы 50 соответствующих блоков 4, для чего на входе 47 дешифратора 3 формируется сигнал 1. Аналогичным образом работают элементы 1 при поиске ближайшего меньшего , но в этом случае детиифратор 3 формирует 1 на входах 45 и 49, а благодаря сигналам, проходящим че рез элементы ИЛИ 10, организуется управление элементами И 12, в результате чего прерывается передача сигнсшов со входом 32 и сигнал 1 появляется на выходе 42. Таким Образом, предлагаемый элемент ассоциативной матрицы памяти, не уступая известным по быстродействию, реализует поиск по большему числу признаков, не требует коммутации в элементйх ассоциативной памяти при переходе от одного вида поиска к и не требует вмешательства програмлвл для определения результата поиска по сигналам на выходах устройства. Технико-экономическое преимущество предлагаемого асссадиативного запоминакядего элемента, по сравнению с известным, заключается в его более широких функциональных возможностях.

пунтяах

tinn

umn

пт

LlJ

Л J« J7 38 О О Q О

О О О С JJ

39

39 37

40

АССОЦИАТИВНЫЙ ЗАПОМИНМОЩНЙ ЭЛЕМЕНТ, содержащий элемент памяти, элементы ИДИ, первый, второй и третий элементы И, причем первый выход элемента памяти подключен к первому входу первого элемента И, второй вход которого соединен с первым входом второго элемента И, а выход - с первым входом первого элемента ИЛИ, второй и третий входы первого элемента И и первый вход второго элемента ИЛИ являются одними из входов ассоциаT iBHoro эапоминакяцего элемента, ОДНИКФ1 из выходов которого являются выходы первого и второго элементов ИЛИ, отличающийся тем, что, с целью расширения функциональных возможностей элемента эа счет реализации поиска по признакам не больше, не кюньше, ближайшее большее и ближайшее меньшее , в него введены четвертый и пятый элементы. И, третий и четвертый элементы ИЛИ и элементы НЕ, причем выходы четвертого и пятого элементов И соединены соответственно с первыми входами третьего и четвертого элементов ИЛИ, второй вход третьего элемента ИЛИ подклю-. чен к выходу первого элемента И и входу первогоэлемента НЕ, второй вход четвертого элемента ИЛИ соединен с выходом второго элемента И, входом второго элемента НЕ и вторым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно к первому и ко второму входам третьегоэлемента И, тре(Л тий вход которого соединён с первым входом второго элемента И, втоС рой вход которого подключен ко второму выходу элемента памяти, третий вход второго элемента И, пер- 2 вый и второй входы четвертого и пятого элементов И и второй вход первого элемента ИЛИ являются другими входагл ассоциативного запоминающего элемента, другими выходами которого являются выходы третьего элемента И, третьего и четвертого элемёнто:в ИЛИ.

фигЗ