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

(54) ЭЖМЕНТ АССОЦИАТИШОЙ МАТИЩЫ

Изобретение относится к цифровой вычислктелшой технике и прег наэначено для ассощ ативной обработки шформаций.

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

ВХОД нятого элемшга И подкшочен к четвертому flonwecKOftiQr входу и четвертому логическому выходу элемште, а вход элемента И соедиие чфез leiBepTc с четвертым лотическим входом . Выходы пятого и шескхго эяеметов И соединшы с соответствуюиа ми входами третьего элемента ИЛИ, выход которого подослюч к второму входу элеме1{та И.

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

При практическом изготовлении и испольэовании таких матриц важную роль приобретают вопросы контроля.

Известно, что для схем такого типа длина минималыюго теста на одиночные неис1фавности пропорциональна числу входов схемы, т. в. зависит от числа ячеек матрицы. Этим определяется большая длительность и сложность контроля. Цель изобретения - обеспечение эффектив ного контроля. Достигается это тем, что в элемент ассоци ативной матрицы по авт. свид. № 478297 введе ны седьмой, восьмой и девятый элементы И и пятый, шестой и седьмой логические входы, пер вый вход седьмого элемента И соединен с выходом первого элемента И, первы.е входы вось мого и девятого элементов И соединены с выходом первого элемента ИЯИ, вторые входы седьмого,, восьмого и девятого элементов И соединены соответственно с пятым, шестым и седьмым логическими входами элемента, выходы седьмого и восьмого элементов И соедин ны соответственно с первым и третьим входами второго элемента ИЛИ, а выход девятого элемента И - с первым логическим выходом элемента. Благодаря такой конструкции обеспечи- . вается эффективная контролируемость ассоциативньрс матриц: проверяющий тест не: зависит от размеров матрицы и состоит из 13 наборов На чертеже приведена функцио«ально-логи ческая схема элеме1гга ассоциативной матрицы. Элемент ассоциативной матрицы имеет логические входы 1-8 переменных z, х, у, г, s, t, u, w, соответствеш{О, логические выходы 9-16 переменных z, х у/ г/ s/ t/ u, w/ COOTветстве1шо, и содержит триггер 17 с входными элементами И 18 и 19 инвертор 20 элементы И 21-27 и элементы ИЛИ 28-30. Элемент ассоциативной матрицы реализует функции х (xvbz)t; (xvbz) svbzrvyz; b awwaw; где a - хранимый в триггере 17 бит информации, (1 иС|,о - сигналы установки единицы и нуля. Переменные r,s,t служат для контроля; В рабочем режиме г 1, s О, t 1, при этом х xvbz, z z(bvV) и элемент работает так, как описано в авт свид. № 478297. Организация контроля в ассоциативной матрице сводится к следующему. Проверяющим тестом назовем систему про верок, правильное прохождение которых свиде тельствует об отсутствии заданного перечня не исправностей (из допустимого перечня) ; диагност фующим тестом систему проверок, позволяюп ую определить неисправности (из допустимого перечня), присутствующие в схеме. УСЛОВИЯ прохождения тестов: подача входных наборов (к заданном порядке) и фиксация выхо;у ых наборов (с анализом для диагностирующего теста). Время действия каждого набора на входах должно быть больше длительности переходных процессов в проверяемой схеме. В качестве допустимого перечня неисправностей принимаются кратные константные неисправности одновременно в одном элементе ассоциативной матрицы. Известно, что при этом проверяющий тест является также практически достоверным проверяющим тестом для всей матрицы, поскольку условия компенсации неисправностей требуют очень сложного расположения совершенно определенных неисправностей, вероятность которого ничтожно мала. Для однородной матрицы, состоящей из предлагаемых элементов можно построить проверяющий тест, приведенный в табл. 1. Ниже приведены необходимые пояснения к тесту. Пара наборов |3 проверяет отсутствие обеих константных неисправностей в точке I элемента. Набор « (а°) проверяет может ли сигнал в некоторой точке принять :и1ачение I (0), т. е. отсутствие в этой точке неисправности тождественный 0(1). Для предотщзащения состязаний при перестройке в тест введены противогоночные наборы 2, 2а, 7 и 10, которые одновременно проверяют некоторые точки. При подаче наборов 11, 12 и 13 все столбцы матрицы делятся на три зоны: А, В и С. Если i - номер столбца (i 1,2, ...), то в зону А попадут столбцы для которых i . 2 (modS), в В - i 1 (mod3). и в С - (mod3). Наборы 11 а, б и в попадаются одновременно в зоны А, В и С соответственно, затем попадаются наборы 12 а, б, в и далее 13 а, б, в. При этом наборы 11 проверяют столбцы зоны А, 12 - В и 13 - С. В табл. 1 указаны только те выходы, значения которых могут быть не равны значениям входов. В. табл. 2 приведен список проверяемых точек и соответствующих им наборов с указанием типа набора. Номера наборов соответствуют номерам табл. 1. Если точка не проверяется данным типом набора, то в соответствующей графе табл. 2 ставитсЛ прочерк. Можно показать, что на основе приведенного проверяющего теста строится (с добавлением нескольких наборов) диагностирующий тест, позволяющий определить место одиночной константной неисправности в ассоциативной матрице. Дайна этого теста также не зависит от размеров матрицы.

Входы

irzi

w

0 0 0 0 0

1

10

10

0 0 0 0 0 0

00

20

01

3 a

2 0

01

3 0

00

1 1 1 1

10

4I 11

50

1 1 01

61

01

7 0

0 0 0 0 0

0

11

80

1 1

10

90

01

100

0 0 0 0 0 0 0 0 0

00

lla 0

}

01

116 1

. 0

01

llB 0

) . 0 0 0 0 0 0

01

12a 1

01

126 0

Q0

12вО

01

13a 0

00

136 0 01

13в 1

1) только для крайнего левого столбца

Таблица I

ВыходыI

, I I i Примечание

I

0 Установка в О

0 0

0 0 0 0 0

0X

1

о о о о о о

00

1

I

00

I

1

00

1

0 0

00

1

1

10

1

0 I0

1 Установка в 1

1 10

1

0 0 0 0 0 0 1

Г

0

1 I

о Установка в О

0

0 1

О

1

00

О

0

10

0

О

J

I 10

О

0

0 1 0

00

О

1

1 1 0

О О

0 0

0 0 1 0 1 0

О О

0 0

0 0

1 0

00 1 0

0Q .

О

I

1

1 0

Таблица 2

Формула изобретения Элемент ассощштивиой катрицы по авт. свид. N 478297, отличающийся тем, что, с целью обеспечения эффективного ксяггроля, в него введены седьмой, восьмой и девятый элементы И и пятый, щестс и седьмой лОгн9ескяе входы, первый вход седьмого элемента И соедниея с выходом первого элемента И, первые входы восьмого и девятого элементов И

соед1В1ены с выходом пфвого элемента ИЛИ, вторые входы седьмого; восьмого и девятого элемштов И соответстаешо с оятым шестым и седьмым логическими входами элемента, каюки седьмого и восьмото элементов И соединены соответственно с первьы и третьим, входакш вт(фого элюмшта ИЛИ, а выход девятого элемента И - с первым логическим выхо дом элемотта.