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

 

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

СОЮЗ СОВЕТСКИХ

6Д Л М

РЕСПУБЛИК

5(Я) С 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H АВТОРСКОМУ(СВИДЕТЕЛЬСТВУ!.

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

АОДЕЛАМ ИЗОБРЕТЕНИЙ ИОТНРЫТИЙ (21) 3354085/18-24 (22) 05.11.81 (46) 23. 06. 83. Бюл. Р 23 .(72) Е.B. Гущина и Т.С. Засыпкина (53) 681. 327(088. 8) (56) 1 ° Авторское свидетельство СССР

М 649038, кл. С 11 С 15/00, 1976,.

2. Авторское свидетельство СССР

В 634372, кл. С 11 С 15/00, 1976 прототип). (54)(57) АССОЦИАТИВНЫЙ ЭАПОМИНИОЩИЙ

ЭЛЕМЕНТ, содержащий элемент памяти, элементй ИЛИ, первый, второй и третий элементы И, причем первый выход элементa памяти подключен к первому входу первого элемента И, второй вход которого соединен с первым входом второго элемента И, а выход - с первым входом первого элемента ИЛИ, второй и третий входы первого элемента И и первый вход второго элемента ИЛИ являются одними из входов ассоциативного запоминающего элемента, одними из выходов которого являются выходы первого и второго элементов ИЛИ, о т л н ч а ю шийся тем, что, с целью расширения функциональных возможностей элемента за счет реализации поиска по признакам "не больше", " не меньше", "бли;SU,, 24987 А жайшее большее" и "ближайшее меньшее", в него введены четвертый и пятый элементы, И, третий и четвертый элементы ИЛИ и элементы НЕ, причем выходы четвертого и пятого элементов И соединены соответственно с первыми входами третьего и четвертого элементов ИЛИ, второй вход третьего элемента ИЛИ подключен к выходу первого элемента И и входу первого элемента НЕ, второй вход четвертого элемента ЙЛИ соединен с выходом второго элемента И,входом второго элемента НЕ и вторым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно. к первому и ко второму входам третьего элемента И, третий вход которого соединен с первым входом второго элемента И, второй вход которого подключен ко второму выходу элемента памяти, третий вход второго элемента И, первый и второй входы четвертого и пятого элементов И и второй вход первого элемента ИЛИ являются другими входами ассоциативного запоминающего элемента, другими выходами которого являются выходы третьего элемента И, третьего и четвертого эле- . ментов ЙЛИ.

1024987

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

Известен ассоциативный запоминающий элемент, который содержит сумматор, три накопителя, три регистра, блок, контроля, блок управления, преобразователь кода и элементы И (1) . 10

Недостатком этого элемента является невозможность выполнения за одну команду операций поиска чисел, "ближайшего большего" и "ближайшего меньшего" к заданному, что ограничивает его функциональные возможности.

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

ИЛИ, причем два выхода запоминающего элемента соединены с первым и вторым входами схемы сравнения, выход которой соединен со вторым входом первого элемента И, второй выход запоминающего элемента; кроме того, соединен со вторым входом второго элемента И, первый вход которого соединен с первым входом первого элемента И и первым логическим входом, третий вход второго элемента И и третий вход схемы сравнения соединены с шиной опроса, первый и второй входы третьего элемента И сое- Ç5 динекы соответственно со вторым логическим входом и шиной запрета, выход третьего элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с 40 выходом второго элемента И и первым входом второго элемента ИЛИ, второй вход последнего соединен с третьим логическим входом; а выход является третьим логическим выходом, вы- 45 ход первого элемекта И и выход первого элемента ИЛИ являются соответственно первым и вторым логическими выходами (2j .

Недостатком известного элемента является то, что он не выполняет поиск по признакам "не больше", "не меньше", "ближайшее большее (меньшее), что ограничивает его функциональные возможности.

Целью изобретения является расширение функциональных возможностей ассоциативного запоминающего элемента за счет реализации поиска по признакам "не больше", "не меньше", 60

"ближайшее большее" и "ближайшее меньшее".

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

rrepsozo элемента И и первый вход второго элемента. ИЛИ являются одними из входов ассоциативного запоминающего элемента, одними из выходов которого являются выходы первого и второго элементов ИЛИ, введены четвертый и пятый элементы И, третий и четвертый элементы ИЛИ и элементы НЕ, причем. выходы четвертого и пятого элементов И соединены соответственно с первыми входами третьего и четвертого элементов ИЛИ, второй вход третьего элемента ИЛИ подключен к выходу первого элемента И и входу первого элемента НЕ, второй вход четвертого элемента ЙЛИ соединен с выходом второго элемента И, входом второго элемента НЕ и вто рым входом второго элемента ИЛИ, выходы элементов НЕ подключены соответственно к первому и ко второму входам третьего элемента И; третий вход которого соединен с первым входом второго элемента И, второй вход которого йодключен ко второму выходу элемента памяти, третий вход второго элемента И, первый и второй входы четвертого и пятого элементов

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

На фиг. 1 приведена структурная схема ассоциативной матрицы памяти; на фиг. 2 — функциональная схема предлагаемрго ассоциативного элемента; на фиг. 3-5 — функциональные схема блока запрета сигналов лереноса, дешифратора признака опроса и логического блока.

Ассоциативная матрица памяти содержит (фиг. 1) СхК (где С - число строк, К - число разрядов матрицы) ассоциативных запоминающих элементов 1 (АЗЭ), блоки 2 запрета сигналов переноса, дешифратор 3 признаков поиска и логические блоки 4.

Предлагаемый ассоциативный запоминающий элемент содержит (фиг. 2) элемент 5 памяти, три элемента И

6«8, первйй 9 и второй 10 элементы

ИЛИ, четвертый 11 и пятый 12 элементы Й, третий 13 и четвертый 14 элементы ИЛИ, первый 15 и второй 16 элементы НЕ.

Каждый блок запрета сигналов перекоса содержит (фиг. 3) элементы

И 17,и 18 и элементы HE 19 и 20, 1024987

Дешифратор признаков поиска содержит (фиг. 4) регистр 21 признака, дешифратор 22 и элементы ИЛИ 23-25 °

Каждый логический блок содержит (фиг. 5) элементы И 26-28 и элемент ИЛИ 29.

На фиг. 1 и 2 обозначены входы

30-38 и выходы 39-43 ассоциативного запоминающего элемента. На Фиг. 1, 3, 4 и 5 обозначены входы 44-46 дешифратора признаков поиска, вхо- 10 ды 47-49 и выходы 50 логических блоков.

Предлагаемый ассоциативный запоминающий элемент работает следующим образом. 15

- Входная . информация представляет код числа Х, по которому производится поиск, и код вида поиска. Код числа Х поступает на входы 33 и 34 (Фиг. 2), причем вход 33 соответст- 20 вует "единичному" плечу соответствующего разряда, а вход 34 — "нулевому" плечу. Код вида поиска подается на вход 44 дешифратора 3 и затем на входы 37 и 38 элемента 1. Выход- 25 ная информация снимается с выходов

50 блоков 4 (фиг. 1).

Рассмотрим работу элемента 1 на примере поиска по признакам: "равно", больше", "меньше", "не больше 3р (меньше или равноj", "не меньше (больше или равно)". Для данных видов поиска дешифратор 3 формирует на входах 45 и 46 сигналы "О". В

РезУльтате элементы И 17 и 18 всех блоков закрыты, на входах 37 и 38 всех элементов 1 имеется сигнал "1" и элементы И 11 и 12 (фиг. 2) открыты для сигналов, поступающих по, входам 30 и 31. !

В каждом из элементов 1 выполняется сравнение значения а к кода числа А, хранящегося в элементах 5, со значением х кода числа Х . При сравнении кодов двух чисел имеет мес-45 то соотношение: если во всех старших разрядах вплоть до- некоторого P-го имело место равенство а „ -" х для

a P-ом Разряде а ск Ф х« то если аск хк, то А > Х, если 5© а i x то A (Х, независимо от соотск к ношения аск и х, для,всех К C P

Сравнеййе осуществляется одновременно во всех строках матрицы последовательно по Разрядам, начиная со старшего К разряда (крайнего левого на фиг. 1). При этом на входы 30, 31, 35 и 36 подаются сигналы, соответствующие принятому для выбранной элементной базы представлению нуля, а на входы 32 - представлению единицы. При этом на выходах элементов И 11. и 12 этого .. АЗЭ 1 формируется "О". Сигналы на выходах 41-43 формируются благодаря сигналу "1", поступающему на вход 65

32, и зависят от состояния элементов

И 6-8.

Рассмотрим возможные варианты соотнощения значений а к, и х„. При двоичном представлении чисел они могут принимать значение "О" или "1", поэтому возможны четыре варианта соотношения их значений: а к хк

О, О

1 . 1

1 О

0 1

При этом, когда а« О, на первом выходе элемента 5 имеет место сигнал "О", на втором - "1", когда ас„ = 1, на нервом выходе элемента

5 - "1", на втором - "О". Аналогичным образом определяются сигналы на гходах 33 и 34, когда хк = О, на входе 33 имеем "О", на.входе

34 - "1", когда хк = 1, на входе

33 — "1", на входе 34 - "О".

В первых двух вариантах элементы

И 6 и 7 закрыты. В первом варианте элемент И 6 закрыт сигналом "О", поступающим с первого выхода элемента 5, а элемент, И 7 — сигналом

"О", поступающим со входа 33. Во втором случае элемент И 6 закрыт сигналом "О", поступающим с входа

34, а H 7 — сигналом "О", поступающим со второго выхода элемента 5.

В результате в обоих вариантах на выходах элементов И 6 и 7 имеет место сигнал "0", на обоих входах элементов ИЛИ 13 и 14 имеются сигналы «О" и иа выходы 41 и 42 поступают сигналы "0".

Сигналы "О",с выходов элементов

И 6 н 7 проходят соответственно через элементы HE 15 и 16, инвертнРуются в "1", в результате на всех трех входах элемента И 8 имеются сигналы "1" и на выходе 43 Формируется сигнал "1".

Таким образом, если в элементе

1 какого-либо разряда матрицы, начиная со старшего, зафиксировано равенство значений кодов числа А и числа Х, то на входы 30 и 31 элемента 1 следующего разряда переда ются сигналы "О", а на вход 32сигнал "1" с выходов 41-43 предыдущего элемента 1.

В третьем варианте (a« = 1, х О) на всех трех входах элеК е н мента И.6 имей гся сигналы 1, на его выходе форжруется "1", этот сигнал через элемеит ИЛИ 13 передается на выход 41. Кроме того, сигнал "1" с выхода элемента И 6 поступает на элемент ИЕ 15, инвертируется в "О", который поступает на первый вход элемента И 8 и в результате на выход 43 поступает "О". Элемент И 7, saxp сигналами "О", поступающньы íà его входы со входа 33

1024987 и со второго выхода элемента 5. На выходе элемента И 7 имеется "О", на обоих входах элемента ИЛИ 14 сигналы равны "О" и в результате на выходе 42 имеется "О".

Элементы И 11 всех элементов 1 строки открыты для передачи сигналов со входов 30, в результате сформированный сигнал с выхода 41 элемента 1 старшего разряда беспрепятственно распространяется до выхода 10

41 элемента 1 самого младшего разряда и поступает на вход элемента

И 26 блока (фиг. 5) для формирования результата поиска по строке матрицы. 15

Сигнал "О" с выхода 43 элемента

1 (фиг. 1) старшего разряда передается на вход 32 элемента 1 следующего разряда и закрывает элементы

И 6-8 (фиг. 2), в результате чего 2п исключается возможность выработки сигналов. "1" на выходах 42 и 43 элементов 1 всех последующих разрядов строки.

Таким образом, в третьем варианте формируется решение А > Х, которому соответствует сигнал "1" на выходе 41.

В четвертом варианте сигнал "1" имеет место на всех трех входах элемента И 7, на его выходе Формируется сигнал "1", который через элемент ИЛИ 14 передается на выход 42.

Схема симметрична относительно сигналов на входах 30 и 32 и формиро-З ванне сигналов на выходах 41 и 43 происходит аналогично третьему варианту. В результате формируются сигналы

"О" на выходах 41 и 43. Сигнал "1" с выхода 42 элемента 1 распростра- 40 няется беспрепятственно до выхода 42 элемента И 28 блока 4, в результате формируется решение А с Х.

Таким образом, в результате сравнения А; с Х формируется сигнал "1" 45 на выходе 41 либо 42, либо 43 элемента 1 младшего разряда строки матрицы.

В соответствии с заданным видом поиска дешифратор Формирует сигнал щ

"1" по признакам: "больше" — на входе 47, "равно" — на входе 48, "меньше" - на входе 49, "не меньше" на входах 47 и 48, "не больше на входах 48 и 49.

Эти сигналы подаются на первые входы элементов И 26-28 всех блоков, разрешая прохождение через них соответствующей виду поиска комбинации сигналов с выходов 41-43 элемента 1 младшего разряда строки.

Для,примера рассмотрим поиск по

Признаку ."не меньше". В этом случае сигнал "1" имеется на первых входах элементов И 26 и 27 всех блоков, Если в результате сравнения окажется Я что A < Х, то будет сформирован сигнал "1" на выходе 42 элементов 1 строки, т.е. на втором входе элемента..Й 28 соответствующего блока .4, но на первом его входе — "О", в результате на выходе элемента И 28 формируется "О", элементы И 26 и 27 также закрыты, так как на входах 41 и 43 имеют место сигналы "О". Таким образом, на всех трех входах элеиента ИЛИ 29 имеются сигналы "О" и на выходе 50 "О", что свидетельствует о том, что Ag не удовлетворяет условию поиска.

Если же в результате сравнения фиксируется Ac > Х или А = Х, то сигнал "1" поступает соответственно на выход 41 или на выход 43 элемента

1, т.е. на вход элемента И 26 либо элемента И 27, в результате один из этих элементов оказывается открытым и выдает на выход сигнал "1", этот сигнал через элемент ИЛИ 29 передается на выход 50,- фиксируя, что

А удовлетворяет условиям поиска.

Рассмотрим поиск по признаку

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

Например, рассмотрим два числаA И А <.,такие, что Х A «X o A2 и А >А

Очевидно, что факт превышения

A над Х должен обнаружитЬся рань( ше, чем А над Х, т.е. в более старших разрядах. A так как по условиям поиска должно быть найдено самое меньшее число из тех, которые превышают Х, то программа поиска должна быть следующей если в очередном разряде обнаружено, что хК ъ а „, то число исключается из рассмотрения, если х = а, то обязательно делается анализ следующего разряда, если равенство выполняется и в последующих разрядах, то фиксируется Х = А и выдается сигнал "1" на выход 41 младшего Разряда строки, если ха< а, то сигнал со входа

30 (выхода 41) распространяется до тех пор, пока не встретится разряд, в котором хотя бы для одного числа окажется, что во всех разрядах до данного было x„= a«в. данном ху, а ас„. При возникновении такой ситуацйи прерывается передача сигнала со входа 30 на выход 41 для всех чисел (по всем строкам), В результате сигнал по вхсду ЗО остается только для чисел, для которых в данном разряде (а не левее) имеет место х К < а „.

Для выявления соотношения между числами Ас в элементе 1 использу1024987

ОЗЮ 373е ИМ

° ° ются элементы ИЛИ 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 на выходе элемента И б будет сформирован сигнал "1.", который с выхода 40 будет передан на вход элемента И 18 соответствующего этому разряду блока 2, с входа 37 которого сигнал "0" — на входы 37 всех элементов 1 других строк данного разряда, в результате чего элементы И 11 в них будут закрыты и сигналы со входов 30 будут прерваны, т.е. не смогут пройти в этих элементах 1 на выходы 41. 8 результате сигнал "1" Формируется на выходе 43 элемента 1 младшего разряда строки в случае,,если А с = Х и на выходе З5

41 в случае, если Ас является наименьшим из всех чисел превосходящих заданное X Если окажется, что имеется несколько равных чисел, являющихся наименьшими из превосходящих заданное число х, то сигналы "1" Формируются на выходах 41 всех элементов 1, расположенных в младшем разряде соответствующих строк, затем эти сигналы

"1" поступают на выходы 50 соответствующих блоков 4, для чего на входе

47 дешифратора 3 формируется сигнал "1".

Аналогичным образом работают элементы 1 при поиске "ближайшего меньшего", но в этом случае дешифратор

3 формирует "1" на входах 45 и 49, а благодаря сигналам, проходящим че рез элементы ИЛИ 10, организуется управление элементами И 12, в результате чего прерывается передача сигналов со входом 32 и сигнал "1" появляется на выходе 42.

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

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

10249&7

1024987

Составитель В Гордонова

Редактор Л. Филиппова ТехредЛ, Пекарь Корректор р. Гирняк

Заказ 4406/49 Тираж 594 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, МоскЬа, 3-35, Раушская наб., д. 4/5 ю

Филиал ППП "Патент"-, г. Ужгород, ул. Проектная, 4