Элемент ассоциативной матрицы памяти
Иллюстрации
Реферат
Союз Советских
Социалистимеских
Республик 634372 (6!) Дополнительное к авт, свил-ву (22) Заявлено14.06.76 (21) 2872218/18-24 с присоединением заявки № (23) Приоритет— (43) Опубликовано 25.11.783юллетень № 43 (45) Дата опубликования описания 08.-12.78 (51) М. Кл.
Ст 11 С 15/00
Ст 06 F 7/04
Государственный намитет
Совета Министров СССР оо делам изобретений и открытий (53) УДК 681. 827 (088.8) (72) Автор изобретения
Я. И. Фет (71) Заявитель
Институт математики Сибирского отделения
AH СССР (54) ЭЛЕМЕНТ АССОБИАТИВНОЙ МАТРИБЫПАМЯТИ
Изобретение относится к области цифровой вычислительной техники.
Известен элемент ассоциативной матрицы памяти, содержащий двоичный запоминающий элемент, схему сравнения, шину опроса, причем входы схемы сравнения соединены с выходами .запоминающего элемента и с шиной опроса f1(.
Недостатком этого элемента является невозможность выполнения за одну микрокоманду часто встречающейся операции по- 1О иска числа, ближайшего к заданному. Наиболее близким техническим решением к данному является элемент ассоциативной мат» рицы памяти, содержащий двоичный запоминающий элемент, схему сравнения, два эле- мента И, два элемента ИЛИ, причем к первому и второму входам схемы сравнения подключены соответственно единичный и нулевой выходы запоминающего элемента, третий вход является первым логическим входом элемента, выход схемы сравнения соединен с первым входом первого элемента И, второй вход которого является вторым логическим входом элемента и подключен к первому входу второго элемента
И, выход которого подключен к первому входу первого элемента ИЛИ, причем первый вход второго элемента ИЛИ является третьим логическим входом элемента (2J.
Недостатком его является невозможность выполнения за одну микрокоманду операции поиска числа ближайшего к заданному.
Белью изобретения является расширение функциональных возможностей за счет реализации поиска ближайшего большего или меньшего.
Бель достигается тем, что в него введен третий двухвходовой элемент И, причем четвертый и пятый логические входы элемента соединены соответственно с первым и вторым входом третьего элемента
И, выход которого соединен со вторым входом первого элемента ИЛИ, второй и третий входы втооого элемента И соединены, соответственно, с первым логическим входом элемента и нулевым входом запоминающего элемента, а выход второго элемента И соединен со вторым входом
634372
9 =Ич ах, w = >vzax, z =zb, (() (2) (3) где Х вЂ” значение двоичной переменной 36 не шине опроса; — значение двоичной переменной на шине запрета;
O — состояние двоичного запоминаюmего элемента; 33 ) — значение двоичной переменной на выходе схемы сравнения (предполе гается, что (= (при Х =a) .
Матрица, составленная из предлагаемых элементов, может работать в двух @ режимах: поиск равного и поиск ближайmего.
Поиск равного.
В этом режиме на все входы Z левой границы матрицы подаются константы 1, не все входы Ч левой границы - константы О. На все шины 4 подеются константы 1. Состояния входов Ъ несуществен. ны е
Ю
По шинам опроса х поступает пораз рядно (старшими разрядами слева) код признака опроса.
Так кяк, согласно (3), в каждом элеI менте Z = z 4 сигнал проходит по цепи 2 в каждой строке матрицы до тех пор, пока разряды соответствующих чисел эквивалентны разрядам признака опроса.
В частном случае, в той строке (или невторого элемента ИЛИ, выход первого .элементе И соединен с первым логическим выходом элементе, выходы первого и второго элементов ИЛИ соединены, соответственно, сэ втэрым и третьим логическими Я выходами элемента.
Устройство представлено на чертеже.
П эименяются следующие обозначения: двоичный запоминающий элемент с цепями записи и считывания (не показанными ня 16 чертеже) -1,схема сравнения- 2, шина опроса- 3, шина запрета- 4, элементы И-5, 6,7, элементы ИЛИ-8, 9, входы логических переменных М,М, Z — соответственно 1 О, 1 1, 1 2, выходы логических переменных v, Y, Z И
13,14,15 соответственно.
При соединении элементов в матрицу выходы 13 и 15 каждого элемента соединяются со входами 10 и 12 соседнего справа элемента, а выход 14 — со входом 26
11 соседнего снизу элемента.
Г
Из чертежа и описания видно, что пред.лагаемый элемент реализует следующие логические функции: скольких строках), где содержится число, равное признаку, появится сигнал 1 на ! выходе Z пр вой границы матрицы.
Предположим, что какое-либо число совпадает с признаком опроса не по всем разрядам, а лишь по нескольким (старшим), после чего имеется разряд, в котором Q = О, Х = (. Ясно, чтэ такэе число меньше признака опроса, независимо от соотношения дальнейших: (младших) разрядов. В том элементе, где впервые
С =О, Х = (, схема сравнения выработает ф = О, что приведет к Z = О, го есть сигнал в цепи z исчезнет. Однако, согласно (1), в этом элементе появится
/ сигнал v = ), который по цепи v пройдет до правой границы матрицы и выдаст там ч = 1.
Итак, в любой строке матрицы, содержащей число, меньшее признака опроса, нд правой границе будет z = О, ч = 1
Третий случай — число больше признака опроса. При этом нарушение эквива.— лентности при просмотре слева направо произойдет впервые за счет разряда, в котором O = М, Х = О . В таком элементе тоже исчезнет сигнал в цепи Z,,гак как 3 = О, но сигнал в цепи V не появится.
Следовательно, в любой строке, содержащей число, большее признака опроса, не правой границе будет Z = О, ч = Q
Таким образом, в режиме поиска равного матрица, построенная из предлагаемых элементов, позволяет не только выделить строки, содержащие числа, равные заданному признаку, но также одновременно отметить все строки, содержащие числа, меньшие признака, и строки, содержащие числа, большие признака.
Поиск ближайшего.
В этом режиме на все входы левой границы матрицы также подаются консган» ты 2 = " V = () . Кроме того, на все входы у верхней границы подаются константы О, а выходы нижней границы
/ соединяются через инверторы с шинами соо гве гс твующи х р азр ядов.
По шинам х поступает код признака
oHpoc8 °
В тех строках, где содержатся числя, равные признаку, по-прежнему на вы-! ходах Z правой границы вырабатывается сигнал 1.
Любой элемент, в котором после «ескольких совпядеций впервые окажется прервет прохождение сигнала по пеги Z и возбудит -.èãíàë в цепи v . Однако в денном режиме, кро634372
Составитель E. Пупырев
Редактор Д. Мепуришвили Техред 3. Фанта Корректор А. Власенко
Заказ 6772/52 Тираж 675 Подписное
ЦНИИПИ Государственного. комитета Совета Министров СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5.
Филиал ППП Патент, r. Ужгород, ул. Проектная, 4