Элемент ассоциативной матрицы
Иллюстрации
Реферат
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДИТВЛЬСТВУ
Сотоэ Советских
Социалистических
Республик (11) 616б24 (61) Дополнительное к авт. сеид-ву И 478291 ! (22) Заявлено 20.01.76 (2! )2317220/18-24
2 (51) М. Кл.
О 06 Р 1/00
G 06 F 7/00 с присоединениен заявки №вЂ” (23) Приоритет— (43) Опубликовано 25,07,78. бюллетень № 27 (45) Дата опубликования опнгания 23.06.78
Гасудааственньа каинтет
Соаатв Мнннстраа СССР аа делам нзааретеннй н атнрмтнй (53) УДК
681 327 (088 8) (72) Авторы изобретения
И. В. Коган н Я. И. Фет
Институт математики Сибирскогоотдеяеняя Ан СССР (71) Заявитель (54) ЭЛЕМЕНТ АССОЦИАТИВНОЙ МАТРИЦЫ
Изобретение относится к цифровой вычислительной технике и предназначено для ассоциативной обработки информации, В основном авт. свид, И 478297 к изобретению описан элемент ассотиатнвной матрицы, содержащий триггер, ннвертор и логические элементы И и ИЛИ. Первые входы первого я второго элементов И соединены с первым логическим входом элемента. Выход первого элемента
И соединен с первыми входами первого и второго элементов ИЛИ, вторые входы которых соединены соответственно с вторым логическим входом элемента и выходом второго элемента
И, а выходы подключены соответственно к первому и второму логическньт выходам элемента, Второй вход второго э темента И соединен с третьим логическим входом и третьим логическим выходом элемента. Первые входы третьего и четвертого элементов И соединены с управляющей шиной, вторые входы с вторым и третьим логическими входами элемента, а выходы — с единичным н нулевым входами триггера соответственно. Первые входы пятого и шестого элементов И соединены соответственно с единичным и нулевым выходами триггера, второй вход пятого элемента Н подключи к четвертому логическОму входу и четвертому логическо» му выходу элемента, а второй вход шестого элемента И соединен через яивертор с четверs тым логическим входом элемента. Выходы пятого и шестого элементов И соединены с соответствующими входами третьего элемента ИЛИ, выход которого подключен к второму входу первого элемента И. l0 Однородная матрица, составленная из описанных элементов таким образом, что первый, третий и четвертый логические выходы каждого элемента соединены соответственно с вторым, третьим и четвертым логическими входами ñîседнего снизу элемента, а второй логический выход — с первым логическим входом соседнего справа элемента позволяет реализовать следующие массовые операции: запись, ситывание, ассоциативный поиск, поиск максимума.
При практическом изготовлении и исполь. зовании таких матриц важную pomr приобретают вопросы контроля.
Известно, что для схем такого типа длина минимального теста на одиночные неисправ25 ности лропорщиональна числу входов схемы, т.е.
616624
Г /;
/ «/ зависит от числа ячеек матрицы. Этим определяется большая длительность и сложность контроля.
Цель изобретения — обеспечение эффективного контроля.
Достигается зто тем, что в элемент ассоци- 5 ативной матрицы по авт. свид. !! 478297 введены седьмой, восьмой и девятый элементы И и пятый> шестой и седьмой логические входы, первый вход седьмого элемента И соединен с выходом первого элемента И, первые входы вось- !О мого и девятого элементов И соединены с выходом первого элемента HflM, вторые входы седьмого,, восьмого и девятого элементов И соединены соответственно с пятым, шестым и седьмым логическими входами элемента, вы- (5 ходы седьмого и восьмого элементов И соединены соответственно с первым и третьим входами второго элемента ИЛИ, а выход девятого элемента И вЂ” с первым логическим выходам элемента. 20
Благодаря такой конструкции обеспечивается эффективная контролируемость ассоциа. тивных матриц: проверяющий тест не: зависит от размеров матрицы и состоит из 13 наборов.
На чертеже приведена функционально-логи. 25 ческая схема элемента ассоциативной матрицы.
Элемент ассоциативной матрицы имеет логические входы 1 — 8 переменных z, х, у, r, s, т, U, w, соответственно, логические выходы
9 — 16 переменных z, х, у, г, s, t, U, w, cooT- З0 ветственно, и содержит триггер 17 с входными элементами И 18 и 19; инвертор 20 элементы
И 21 — 27 и элементы ИЛИ 28 — 30.
Элемент ассоциативной матрицы реализует функции х"* (xvbz)t;
z (xvbz) svbzI viz>
b=awviw, g> =ux, (О = 4У
40 где а — хранимый в триггере 17 бит информации, и 0,0 — сигналы установки "единицы" и "нуля".
Переменные r s t служат для контроля; 45
В рабочем режиме r = 1, s = О, t 1, при этом X = xvbz, z = г(Ьчу) и элемент работает так, как описано в авт свид. !! 478297, Организация контроля в ассоциативной матрице сводится к следующему.
Проверяющим тестом назовем систему проверок, правильное прохождение которых свидетельствует об отсутствии заданного перечня неисправностей (из допустимого перечня); диагностирующим тестом — систему проверок, позволяющую определить неисправности (из допустимого перечня), присутствующие в схеме.
Условия прохождения тестов: подача вход:ных наборов (в заданном порядке) и фиксация выхо/дных наборов (с анализом для диагностируюшего теста). Время действия каждого набора на входах должно быть больше длительности переходных процессов в проверяемой схеме.
В качестве допустимого перечня неисправностей принимаются кратные константные неисправности одновременно в одном элементе ассоциативной матрицы. Известно, что при этом проверйющий тест является также практически достоверным проверяющим тестом для всей матрицы, поскольку условия компенсации неисправностей требуют очень сложного расположения совершенно определенных неисправностей, вероятность которого ничтожно мала.
Для однородной матрицы, состоящей из предлагаемых элементов можно построить проверяющий тест, приведенный в табл. 1.
Ниже приведены необходимые пояснения к тесту.
Пара наборов !1О ф проверяет отсутствие обеих константных неисправностей в точке !. элемента. Набор а (а ) проверяет может ли сигнал в некоторой точке принять значение 1(0), т. е. отсутствие в этой точке неисправности
"тождественный О(!) .
Для предотвращения состязаний при перестройке в тест введены противогоночные наборы 2, 2а, 7 и 10, которые одновременно роверяют некоторые точки.
При подаче.наборов 11, 12 и 13 все столбцы матрицы делятся на три зоны: А, В и С, Если i — номер столбца (i = 1,2, ...), то в зону А попадут столбцы для которых i = 2 (mod3), в  — i = (пзо43) и в С вЂ” i = 0 (mod3). Наборы !1 а, б и в попадаются одно-. временно в зоны А, В и С соответственно, затем попадаются наборы 12 а, б, в и далее !
3 а, б, в. При этом наборы 11 проверяют столбцы зоны А, !2 — В и 13 — С.
В табл. 1 указаны только те выходы, значения которых могут быть не равны значениям входов, В табл. 2 приведен список проверяемых точек и соответствующих им наборов с указанием типа набора, Номера наборов соответствуют номерам табл. 1. Если точка не проверяется данным тином набора, то в соответствующей графе табл. 2 ставите@ прочерк.
Можно показать, что на основе приведенного проверяющего теста строится (с добавлением нескольких наборов) диагностирующий тест, позволяющий определить место одиночной константной неисправности в ассоциативной матрице. Длина этого теста также не зависит от размеров матрицы.
Ы б24
)аблица 1
Bxngbi х у z u w r s t )а
Выхопы
NoNo х (Примечание
z а пн
О Установка в О
О Х О.
О О О
О !
0 . 1 0
О О О 1
О О
0 О
О О
О О О
1 0
О О
3 О О 1
2 0
О 1
О О
О 1
О О
3 О
0 О
О О
О О! О I
I О О
1 О
1 О
1 О О
5 0
l О
1 О
1 Установка в 1
1 О
О 1
6 1
I О О 1
1 О 1 I
О I
7 О
8 О
О
1 1 О
1 О 1
О О Установка в О
1 О О 1 О
О ОО О
О О 1 О О
9 О
)p О О 1
l О
О
О О О О
О 1 О О
)1à О
1 О
О 1
116 1
О
О О 1 О О
О 1 1 О 1
О О 1 О 0
О I О О
О О 1 О О
0 О 1 О 0
О О
))в О О 1
О 1 О О
О!
2а 1
О
О 1 О
О О О
О 1 О
13а .О
13б О
1 О
О I
13в 1
«) только пля крайнего левого столбна
12б О О 1 О
)2s0 О О О
О О
О О
О О
О О
616624
Таблица 2
Т=
1 з
1 г
11, 12, 13
11, 12, 13
3(н), 2 (ч)
3(н), 2 (ч) 1 s
1 s
3(н), 2 (ч)
З(н), 2 (ч) 1 х
4,5
11, 12, 13
9. 10(проявл) 2, 3, 2, 3
4,5
4,5
4,5 (проявл) 9, 10(приявл) З(н), 2 (ч) 2, 3, 2, 3
20 1 4
21 1 g
22 12
23 1 g
24 1 a
25 1 с
4,5
2, 3, 2, 3
3(н),2 (ч) РР Проверяема пп точка
8 1 х
9 1 у
l0 1 у
11 1 у
12 1 z
13
14 1u
15 1 о
16 1 ц
17 Г чч
18 1 иг
19 lsd
Номера и типы наборов по табл. 1
616624
Заказ 4067/45 Тираж 82б Подписное
ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий
1l3035, Москва,, Ж-35, Раушская иаб., и. 4/5
Филиал ППП "Патент". г. Ужгород, ул. Проектная, 4
Формула нэобретения
Элемент ассоциативной матрицы по авт. свид. И 478297, отличающийся тем, что, с целью обеспечения эффективного контраля, в него введены седьмой, восьмой и девятый элементы И и пятыи, п1естой и седьмой логические входы, первый вход седьмого элемента И соединен с выходом первого элемента И, nepwe входы восьмого н девятого элементов И соединены с выходом первого элемента ИЛИ, вторые входы седьмого, восьмого и девятого элементов И соединены соответственно с пятым шестым и седьмым логнческимн входами элемента, выходы седьмого и восьмого элементов
И соединены соответственно с первым и третьим. входами второго элемента ИЛИ, а выход девятого элемента И вЂ” с первым логическим выходом элемента.
Составитель Я. Фет
Техред 3 .Фанта Корректор E. Паа