Элемент ассоциативной матрицы

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДИТВЛЬСТВУ Своз Советских Социалистических Республик(23) Приоритет -асударственньа квинт Соаата Мнннстраа ССС аа делам нзааретеннй(43) Опубликовано 25,07,78. бюллетень27 (4) Дата опубликования опнгания 23.06,78 нрмтнн 327 (088.) Авторыизобретения И. В. Коган н Я,тематики Сибирскогоотдеяе Инсти 71) Заявител 4) ЭЛЕМЕНТ АССОЦИАТИВНОЙ МАТРИЦ вход шестого ор с четверВыходы пя. дннены с соот. лемента ИЛИ,ому входуиз оии.ервый,Изобретение относится к цифровой вычислительной технике и предназначено для ассоциативной обработки информации,В основном авт. свид, Иф 478297 к изобретению описан элемент ассотиативной матриц,содержащий триггер, ннвертор и логические эле.менты И и ИЛИ, Первые входы первого я вто.рого элементов И соединены с первым логическим входом элемента. Выход первого элементаИ соединен с первыми входами первого и второго элементов ИЛИ, вторые входы которыхсоединены соответственно с вторым логическимвходом элемента и выходом второго элементаИ, а выходы подклточены соответственно к нер.вому и второму логнческньт выходам элемента,Второй вход второго з 1 емента И соединен стретьим логическим входом и третьим логическим выходом элемента. Первые входы третьегои четвертого элементов И соединены с управляющей шиной, вторые входы с вторым и третьимлогическими входами элемента, а выходы - сединичным н нулевым входами триггера соответственно. Первые входы пятого и шестогоэлементов И соединены соответственно с единичным и нулевым выходами триггера, второй вход пятого элемеиа Н подключи к четверто.му логическОму входу и четвертому логическому выходу элемента, а второйэлемента И соединен через яиверт5 тым логическим входом элемента.того и щестого элементов И соеветствувщими входами третьего эвыход которого подключен к вторпервого элемента И,1 О Однородная матрица, составленнаясанных элементов таким образом, что птретий и четвертый логические выходы каждогоэлемента соединены соответственно с вторым,третьим и четвертым логическщми входами со 15 седнего снизу элемента, а второй логическийвыход - с первым логическим входом соседнего справа элемента позволяет реализоватьследующие массовые операции: запись, сапы.ванне, ассоциативный поиск, поиск максимума,При практическом изготовлении и использовании таких матриц важную роль приобретают вопросы контроля,Известно, что для схем такого типа длина минимального теста на одиночные неисправ.25 ности пропорциональна числу входов схемы, т.е./ зависит от числа ячеек матрэээвь Этим определяется больцэая длительность и сложность коц.троля.Цель изобретения - обеспечение эффективного контроля.Достигается зто тем, что в элемент ассоциативной матрицы по авт. свид. Н 478297 введены седьмой, восьмой и девятый элементы И ипятый шестой и сельмой логические входы, пер.вый вход седьмого элемента И соединен с вы.ходом первого элемента И, первьэе входы вось. эОмого и девятого элементов И соединены с выходом первого элемента ИЛИ, вторые входыседьмого восьмого и девятого элементов Исоединены соответственно с пятым, шестым иседьмым логическими входами элемента, вы э 5ходы седьмого и восьмого элементов И соединены соответственно с первым и третьим входами второго элемента ИЛИ, а выход девятогоэлемента И - с первым логическим выходамэлемента. 20Благодаря такой конструкции обеспечивается эффективная контролируемость ассоциативных матриц: проверяющий тест не: зависитот размеров матрицы и состоит из 13 наборов,На чертеже приведена функционально-логи 25ческая схема элемента ассоциативной матрицы.Элемент ассоциативной матрицы имеет ло.гические входы 1 - 8 переменных г, х, у, г, а,т, ц, чч, соотвстствеээцо, логические выходы9 - 16 переменных г, х, у, г, а, т, О, чч,/ соответственно, и содержэп триггер 17 с входнымиэлементами И 18 и 9; инвертор 20 элементыИ 21 - 27 и элементы ИЛИ 28 - 30,Элемент ассоциативной матрицы реализуетфункциих" (хчЬг)1;г "-/(хчЬг) 5 чЬггчуг,Ь=ачччачч,сэ,=цх ,о =ду4 Огде а - хранимый в триггере 17 бит информации,и о - сигналы установки "единицы"и "нуля".Переменные г,ь,т служат для контроля; 45В рабочем режиме г = 1, а = О, т 1, приэтом х = хчЬг, г = г(Ьчу) и элемент работает так, как описано в авт свид. КО 478297,Организация контроля в ассоциативнойматрице сводится к следующему.50Проверяющим тестом назовем систему про.верок, правильное прохождение которых свиде.тельствует об отсутствии заданного перечня неисправностей (из допустимого перечня); диагцостирующим тестом - систему проверок, по.зволяюэцую определить цеиснравности (из допустимого перечня), присутствующие в схеме. Условия прохождения тестов: пода и вход:.цых наборов (в заданном порядке) и фиксациявыходных наборов (с анализом для диагцости.руюшего теста). Время действия каждого набора на вхо/тах должно быть больше длительностипереходных процессов в проверяемой схеме.В качестве допустимого перечня неисправностей принимаются кратные константные неисправности одновременно в одном элементе ассоциативной матрицы. Известно, что при этомпроверйющий тест является также практическидостоверным проверяющим тестом для всейматрицы, поскольку условия компенсации неисправностей требуют очень сложного расположения совершенно определенных неисправностей,вероятность которого ничтожно мала,Для однородной матрицы, состоящей изпредлагаемых элементов можно построить проверяющий тест, приведенный в табл. 1,Ниже приведены необходимые поясненияк тесту,Пара наборов 1 о З проверяет отсутствиеобеих константных неисправностей в точке .элемента. Набор а (а ) проверяет может лисигнал в некоторой точке принять значение 1(0),т. е. отсутствие в этой точке неисправности"тождественный 0 .Для предотвращения состязаний при перестройке в тест введены противогоночные наборы 2, 2 а, 7 и 10, которые одновременно нроверяют некоторые точки.При подаче. наборов 11, 12 и 13 все столб.цы матрицы делятся на три зоны: А, В и С,Если- номер столбца ( = 1,2, ), то взону А попадут столбцы для которых= 2(водЗ). Наборы 1 а, б и в попадаются одно.временно в зоны А, В и С соответственно, затем попадаются наборы 12 а, б, в и далее13 а, б, в. При этом наборы 11 проверяютстолбцы зоны А, 12 - В и 1.3 - С,В табл. 1 указаны только те выходы, зна. чения которых могут быть не равны значениям входов,В табл. 2 приведен список проверяемых точек и соответствующих им наборов с указанием типа набора, Номера наборов соответствуют номерам табл. 1. Если точка не проверяется данным тином набора, то в соответствующей графе табл, 2 ставится прочерк.Можно показать, что на основе приведен. ного проверяющего теста строится (с добавлением нескольких наборов) диагцостирующий тест, позволяющий определить место одиночной константной неисправности в ассоциативной мат. рице. Длина этого теста также не зависит от размеров матрицы.) только пля крайнего левого столбца 12 б 0 0 1 012 вО 0 0 0 0 0 1 О 0 0 1 1 0 1 О 0 1 0 О 0 0 1 0 О 00 1 0 0 0 0 1 0 О х гПримечаниеа 0 0 0 О О 0 0 0,3, 2,3 20 3(н),2 (ч 3 4 1 в 1 в Номера и типы наборов по табл 11, 12, 13 11, 12, 13 43(н), 2 (ч)616624 10 Составитель Я. Фет Техред З,фанта рьдактор Е. Гон р Е. Пали Заказ 4067/45ЦНИИПИ аж 82 осударственного комитета Совета Миннстро по делам изобретений н открытиЯ 1 3035, Москва Ж, гаушская набд5 лиал ППП 1 йатент", г, Ужгород, ул Проектная, 4 Формула изобретения Элемент ассоциативной матрицы по авт.свид. Иф 478297, о т л и ч а ю щ и й с я тем, что, с целью обеспечения эффективного контрали, в него введены седьмой, восьмой и девятый элементы И и пятый, щестой и седьмой логичес кие входы, первый вход седьмого элемента И соединен с выходом первого элемента И, первые входы восьмогои девятого элементов И соединены с выходом первого элемента ИЛИ,вторые входы седьмого, восьмого и девятогоэлементов И соединены соответственно с пятымшестым и седьмым логнческимн входамн элемента, выходы седьмого и восьмого элементовИ соедащщ соответственно с первым и третьим,входами второго элемента ИЛИ, а выход девятого элемента И - с первым логическим выхо.дом элемента.