Элемент ассоциативной матрицы памяти Советский патент 1978 года по МПК G11C15/00 G06F7/04 

второго элемента ИЛИ, выход первого -элемента И соединен с первым логически выходом элемента, выходы нового и вто рого элементов ИЛИ соединены, соответственно, со вторым и третьим логическими выходами элемента. Устройство представлено на чертеже, Применяются следующие обозначения: двоичный запоминающий элемент с цепям записи и считывания (не показанными на чертеже)-,схема сравнения- 2, шина опроса- 3, шина запрета- 4, элементы И-5,6,7, элементы ИЛИ-8,9, входы логических переменных V,V,Z - соответственно 10,11,12 выходы логических переменных v , z 13,14,15 соответственно. При соединении элементов в матрицу выходы 13 и 15 каждого элемента соеди няются со входами 1О и 12 соседнего справа элемента, а выход 14 - со входом 11 соседнего снизу элемента. Из чертежа и описания видно, что пре .лагаемый элемент реализует следующие логические функции: v vtvzax , у v2ax, z-zb, где X - значение двоичной переменной на шине опроса; значение двоичной переменной на шине запрета; состояние двоичного запоминаю щего элемента| значение двоичной переменной на выходе схемы сравнения (пре папа гается, что Ь -i ). Матрица, составленная из предлагаемых элементов, может работать в двух режимах: поиск равного и поиск ближайшего. Поиск равного. В этом режиме на все входы z левой границы матрицы подаются константы 1, на все входы V левой границы - константы О. На все шины t подаются константы 1. Состояния входов У несуществен ны По шинам опроса X поступает поразрядно (старшими разрядами слева) код признака опроса. Так как, согласно (3), в каждом элементе 2 2 b I сигнал проходит по це пи Z в каждой строке матрицы до тех пор, пока разряды соответствующих чисе эквивалентны разрядам признака опроса. В частном случае, в той строке (или не кольких строках), где содержится число, авное признаку, появится сигнал 1 на ыходе Z пр.чвой границы матрицы. Предположим, что какое-либо число совпаппет с признаком опроса не по всем разрядам, а Лишь по нескольким (стар- ), после чого имеется разряд, в котоом а - О, X -f . Ясно, что такое число меньше признака опроса, независимо от соотношения дальнейших: (младших) разрядов. В том элементе, где впервые С О, , схема сравнения выработает t)O , что приведет к z О , то есть сигнал в цепи z исчезнет. Однако, согласно (1), в этом элементе появится сигнал V - , который по цепи пройдет до правой границы матрицы и выдаст там V 1. Итак, в любой строке матрицы, содержащей число, меньшее признака опроса, н правой границе будет z O, Третий случай - число больше признака опроса. При этом нарушение эквива.- лентносги при просмотре слева направо произойдет впервые за счет разряда, в котором О -/, Л О . В таком элементе тоже исчезнет сигнал в цепи Z , так как t) О , но сигнал в цепи V не появится. Следовательно, в любой строке, содержащей число, большее признака опроса, на правой границе будет 2 О, v О Таким образом, в режиме поиска равного матрица, построенная из предлагаемых элементов, позволяет не только выделить строки, содерхсащие числа, равные заданному признаку, но также одновременно отметить все строки, содержащие числа, меньшие признака, и строки, содержащие числа, большие признака. Поиск ближайшего. В этом режиме на все входы левой границы матрицы также подаются константы j V О . Кроме того, на все входы верхней границы подаются константы О, а выходы V нижней границы соединяются через инверторы с шинами t соответствующих разрядов. По шинам X поступает кои признака опроса. В тех строках, где Содержатся числа, равные признаку, по-прежнему на выходах 2 правой границы вырабатывается сигнал 1, Любой элемент, в котором после нескольких совпапетшй впервые окажется Cf 0, X прервет прохождение сигнала по цепи Z и возбудит сигнал в цепи V . Однако в /данном режиме, кроме того, используется воаиикающий в этом же элементе в соответствии с (2) сигнал , который по цепи V проходит до нижиой границы матрицы, инвертируется и устанавливает шину t соответствующего разряда в состояние О. Вследствие ЭТО1Х) во всех строках, где сигнал V / возник раньше (то есть в старших разря- /i/ix), прохождение этого сигнала по цепи V бупет прервано. Следовательно, сиг нал может появиться на правой границе матрицы в некоторой строке лишь в том случае, если во всей матрице нет ни одной строки, в которой ситуация Gf О, впервые возникает правее, чем в данной. Такая строка, очевидно, содержит число, ближайшее меньшее в заданному. Если в матрице содерг.ситея несколько (равных)чисел, ближайших меньших к заданному, го все они отмечаются сигналом V { на правой границе. До сих пор рассматрквался вариант предлагаемого элемента ассоциативной матрицы, обеспечивающий поиск числа, ближайшего меньшего к заданному. Пля поиска ближайшего большего достаточно внести следующие изменения: второй вход элемента И 7 соединить с прямым выходом запоминающего элемента 1, а третий - через инвертор - с шиной опроса 3, При этом вьфажении (1) и (2) примут вид: v vtvzc8K, (4) yv2ax .(5) В этом варианге сигналы v, V дут возникать в том элементе в котором впервые после ряпа совпадений возникает ситуация ей , к О . Ясно, что при этом в режиме поиска равною сигналом v i на правой границе будут отмечать-. ся строки, содержащие числа, большие заданного, а в режиме поиска ближайшего строка (или строки), содержащая число. ближайшее большее к заданному. Если матрица должна выполнять по оче реди. оба вида поиска, то можно организовать переключение второго и третьего входов элементов И 7, например, по си1 на/Ту из устройства управления. Ассоциативная матрица памяти, построенная из элементов предлагаемой конструкции, приобретает следующие новые положительные свойства: 1. Операция поиска числа, ближайиюго к заданному, выполняется за олну MHKfx 6бу- 26 команду (одно обращение к памяти) при полном отсутствии избыточности. 2. При выполнении операции поиска числа, равного заданному (обычный ассоциативный поиск), весь массив обрабаты.ваемых чисел разделяетсяне на два подмножества (числа, равные и неравные заданному), как в известных ассоциативных матрицах, а на три: равные, большие и меньшие заданного. Формула изобретения Элемент ассоциативной матрицы памяти, содержащий двоичный запоминающий элемент, схему сравнения, два элемента И, два элемента ИЛИ, причем к первому и второму входам схемы сравнения подключены соответственно единичный и нулевой выходы запоминающего элемента, третий вход является первым логическим входом элемента, выход схемы сравнения соединен с первым входом первого элемента И, второй вход .которого является вторым логическим входом элемента и подключен к первому входу второго элемента И, выход которого подключен к первому входу первого элемента ИЛИ, причем первый вход второго элемента ИЛИ яЕШяется третьим логическим входом элемента, отличающийся тем, что, с целью расширения функциональных возможностей за счет реализации поиска ближайшего большего или меньшего, в него введены третий двухвходовый элемент И, причем четвертый и пятый логические входы элемента соединены соответственно с первым и вторым входом третьего элемента И, выход которого соединен со вторым входом первого элеменга ИЛИ, второй и третий входы второго элемента И соединены, соответственно, с первым логическим входом элемента и нулевым выходом запоминающего элемента, а выход второго элемента И соединен со вторым входом второго элемента ИЛИ, выход пер- вого элемента И соединен с первым логическим выходом элемента, выходы первого и второго элементов ИЛИ соединены соответственно, со вторым и третьим логическими выходлмн элемента. Источники и{Г(}.Орма1ши, принятые во внимание при экспе)тизе: 1.И. В. Прангишвили и др. Однородные микроэлектронные ассоциативные- процессоры, М., Сов. Радио, 1973, стр, 17. 2.Авторское свядегольство СССР 478297, кл., Q Об F 1/ОО, О6.07.73.

}

12

fid

z

w

L.

.J

n

%