Содержание к диссертации
Введение
Глава I. СОСТОЯНИЕ ИССЛЕДОВАНИЙ В ОБЛАСТИ ТЕСТОВОГО
ДИАГНОСТИРОВАНИЯ ПЛМ 10
I.I. Математические модели исправных и неисправных ПЛМ 10
1.2. Краткий обзор методов построения проверяющих тестов для одиночных неисправностей ПЛМ 24
1.3. Анализ подходов к диагностированию кратных неисправностей ПЛМ 34
- 1.4. Выводы к главе 1 50
Глава II. СИНТЕЗ КОНТРОЛЕПРИГОДНЫХ ПЖ ПЕРВОГО РОДА 52
2.1. Постановка задачи 52
2.2. Компенсация неисправностей и устранение компенсации 54
2.3. Построение ПЖ с ( к , 7)-свойством при 7 И {1,2,3,4} 65
2.4. Синтез ПЖ, чувствительных ко всем одиночным коммутационным неисправностям 68
2.5. Заключение к главе II 89
Глава III. СИНТЕЗ КОНТРОЛЕПРИГОДНЫХ ПЖ ВТОРОГО РОДА И ПОСТРОЕНИЕ ДЛЯ НИХ ПОЛНЫХ ТЕСТОВ. 91
3.1. Длина минимального полного теста 91
3.2. Класс контролепригодных ПЛМ второго рода 93
3.3. Метод синтеза контролепригодных ПЛМ второго рода 104
3.4. Проверка синхронизированной ПЖ с "окном" 116
3.5. Заключение к главе III 124
Глава ІУ. МОДИФИКАЦИЯ ПЖ ДЛЯ УДОБСТВ КОНТРОЛЯ 126
4.1. Построение полного теста для ШІМ, не содержащей входного буфера из дешифраторов 126
4.2. Модифицированные ПЛМ 137
4.3. Заключение к главе ІУ 145
Заключение 147
Литература 151
Приложение 1 166
Приложение 2 169
Приложение 3 176
Приложение 4 179
Приложение 5 ' 183
Приложение б 188
- Математические модели исправных и неисправных ПЛМ
- Компенсация неисправностей и устранение компенсации
- Длина минимального полного теста
- Построение полного теста для ШІМ, не содержащей входного буфера из дешифраторов
Математические модели исправных и неисправных ПЛМ
Комбинационная ПЛМ образуется из четырех последовательно соединенных под схем, выполненных на одном кристалле. На входные полюсы первой подсхемы (рис. I ) , называемой входным буфером ГОІМ [16] , подаются входные переменные ПЛМ х± , х , , х , составляющие в совокупности множество X. Входной буфер состоит из одно- или двухвходовых дешифратов, не связанных между собой.
Выходные переменные cj , и , Угп, пеРвй подсхемы образуют множество Y. Если входной буфер выполнен из одновходовых дешифраторов, то Схематическое изображение ШШ I) входной буфер; 2) подсхема 2; 3) подсхема 3; 4) выходной буфер.
В практике проектирования дискретных устройств наиболее широко распространены ІШМ, в которых входной буфер состоит из од-новходных дешифраторов [17] . В диссертации рассматриваются именно такие ШІМ.
Вторая и третья подсхемы несут основную функциональную нагрузку. Каждая из них представляет собой элементарцую транзисторную или диодную матричную схему, предназначенную для реализации на всех своих выходных полюсах элементарных булевых функций вида: положительная, т.е. не содержащая отрицаний входных переменных подсхемы, элементарная конъюнкция (в этом случае будем говорить, что подсхема имеет тип Неположительная элементарная дизъюнкция (тип ИЛИ ) ; отрицание положительной элементарной дизъюнкции (тип ИЖ-НЕ). Существуют ГОШ типов (И, ИЛИ ) и (ИЛИ-НЕ, ИЛИ-НЕ) [17-20] . Первым в скобках указан тип подсхемы 2, вторым - тип подсхемы 3.
Четвертая подсхема, называемая выходным буфером, позволяет, если это необходимо, получать инверсии некоторых своих входных переменных. Эта подсхема может отсутствовать [211 .
Рассмотрим детально структуру подсхем 2 и 3. При изготовлении ГОШ в настоящее время используют биполярные и МОП-элементы
[22] . ШІМ на МОП-элементах имеют более низкую потребляемую мощность, более высокую плотность размещения и более простую технологию изготовления, однако они уступают схемам на биполярных элементах по быстродействию [17] .
Компенсация неисправностей и устранение компенсации
Нас будут интересовать условия, которым должна удовлетворять J-чувствительная схема, чтобы в любой кратной неисправности f из для любого (І, У -теста т существовала одиночная неисправность, которая не компенсируется на г комбинацией остальных неисправностей из f .
Для представления ПЛМ воспользуемся сжатой матричной моделью С Т , Е , , ТИП ). Будем считать, что неисправная ПЛМ описывается четверкой (ST, Ь , , ТИП ) .
Критические неисправности. Такими будем называть кратные неисправности, в которых возможна компенсация любой одиночной неисправности типа , возникновение которой отображается изменением у -й строки матрицы Т или -S .
Прежде всего отметим, что 7 -чувствительная схема является -чувствительной, где 1 с J. Примем во внимание, что 7 -чувствительная схема обладает (А , 7) -свойством при 7± с-&± . В этой связи любой (I, 7)-тест проверяет любую неисправность из множества, где Z є в-jt. Рассмотрим кратную неисправность f из мно-жества 5j \ . Она обязательно включает в себя одиночную неис-правность f1. или {. . Согласно CI23], неисправности f . (соответ-ственно . ) могут компенсироваться только неисправностями, содержащими 2 или cf3 (соответственно р г ), где /=/ , а неисправнос 2. L l L ти {в . и - могут компенсироваться только неисправностями . и if. , где і Iі J . Поэтому к критическим отнесем только неисправности tp , вхождение f- fyj) в которые обязательно сопровождает-ся вхождением f. или (f . ( соответственно f / ). При этом крити-ческой не будем считать неисправность одной промежуточной шины.
Компенсация неисправностей типа 2 и 3. Обозначим через Г. двоичный набор, который поглощается троич-ной вектр - строкой t- матрицы Т (т.е. получается из нее некоторой заменой значений "-" на 0 или I) и не поглощается никакой другой строкой матрицы Т . Этот набор будем называть собственным для строки і,- по матрице Т . Пусть неисправность f. (или tp ) проверяется набором Г . Найдем необходимые и доста J J 2 3 точные условия для компенсации if- с f) на наборе Г,- комбинаци J j J ей остальных неисправностей из f .
Для определенности будем считать, что ПЛМ имеет тип СИ, ИЛИ), а все компоненты вектора & сжатой матричной модели равны I. Рассмотрим троичный вектор t . Он порождает интервал всех двоичных векторов, которые можно получить, заменяя неопределенные значения компонент вектора t на определенные - 0 или I. Будем говорить, что совокупность троичных векторов (возможно состоящая из одного вектора) поглощает троичный вектор ± , если объединение интервалов, порождаемых векторами из этой совокупности, включает в себя интервал, порождаемый вектором t_ .
Если приложить набор Г/ к входным полюсам исправной ПЛМ, то на ее выходных полюсах будет получена вектро-строка /у , в то время как на выходных полюсах ПЛМ с неисправностью у будет реализован нулевой вектор, а на выходных полюсах ПЛМ с неисправностью будет получена строка & матрицы -В , отличная от 4j . Ком-пенсация неисправности f . или f; совокупностью остальных не исправностей из if будет иметь место на наборе Т,- тогда и только тогда, когда в состав войдут неисправности у. , при водящие к тому, что некоторые
Длина минимального полного теста
В данной главе множество всех одиночных и кратных коммутационных неисправностей будем обозначать через "р Положим / -длина минимального полного теста, проверяющего все обнаружимые неисправности из множества Р конкретной ПЛМ. Введем обозначение ПЛМ" " для такой ПЛМ, у которой все промежуточные шины являются задействованными, а система ДНФ D алгебраической модели оказывается кратчайшей. Иначе будем использовать обозначение ПЛМ . В работе [121] отмечалось, что для ПЛМ" полный тест практически не отличается от исчерпывающего, содержащего 2 наборов. Уточним это утверждение.
Обозначим через // подмножество всех элементов булева пространства М наборов значений входных переменных ПЛМ, на которых в I обращается каждая ДНФ системы Z). Будем считать, что система ДШ D представляет систему / полностью определенных булевых функций. Введем обозначение Р для подмножества Р , состоящего из всех тех неисправностей, которые действуют в сторону сжатия характеристических множеств [19] функций из Г и делают это только за счет удаления элементов множества М . Пусть с -длина минимального теста, проверяющего все неисправности из + .
Теорема 15. Для ПЛМ I = 2 - Ъ(П ) + Є .
Отсюда следует, что если величинаЪ(ґі±ч) мала, а такая ситуация для ПЛМ является типичной, то "короткий" полный тест может существовать только для схемной реализации г на ПЛМ . Как известно С138 3, задача построения кратчайшей системы ДН5 для произвольной системы булевых функций является А Лполной, и к настоящему времени отсутствуют практически приемлемые средства ее решения. Далее, когда потребуется, будем преобразовывать ПЛМ к ПЛМ путем добавления к ней дополнительных входных и выходных полюсов.
Областью определения системы F булевых функций, заданных в булевом пространстве М (возможно не полностью определенных), назовем подмножество М пространства /7, на котором определена по крайней мере одна функция системы F .
Теорема 16. [121]. Подмножество Г М является полным тестом для ПЛМ , если и только если это подмножество служит областью определения системыF (возможно не полностью определенных) булевых функций, любая кратчайшая система ДНФ которой удовлетворяет двум условиям: I) содержит столько же элементарных конъюнкций, сколько их входит в систему]); 2)реализует ту же саму систему полностью определенных булевых функций, какую задает D.
Следствие 5. Для ПЛМ =min oCtl ), где минимум берется по мощностям областей определения всех систем F .
Построение полного теста для ШІМ, не содержащей входного буфера из дешифраторов
В разделе І.І.І. отмечалось, что обычная ПЛМ представляет собой последовательное соединение четырех подсхем (см.рис.1), первая из которых, называемая входным буфером, состоит из нескольких дешифраторов. Выделим входные полюсы второй подсхемы, подключенные к выходам одного и того же дешифратора. На эти полюсы подаются зависимые переменные - если один из полюсов находится в состоянии 0. Допустим, входной буфер отсутствует. Тогда на входные полюсы второй подсхемы ПЛМ будут подаваться независимые переменные У , Ц ,....,{/ . Такую ПЛМ обозначим как ГОІМ.?. Цель настоящего параграфа - показать, что для ПШ&э легко построить короткий полный тест.
Математические модели исправных и неисправных ПЛМр. При рассмотрении структурно-функциональных свойств ffilMg будем ссылаться на рис.1, мысленно опуская входной буфер. Главной особенностью ПШ? являются ее функциональные свойства. В WM% типа (И,ИДИ) на выходных полюсах подсхемы 3 реализуется система положительно монотонных ДНФ, т.е. таких ДНФ, все элементарные конъюнкции которых являются положительными (раздел І.І.І). На таких же выходных полюсах в ПШ типа (И,ИЛИ-НЕ) (соответственно (ИЛИ-НЕ, ИДИ-НЕ)) реализуется система отрицаний положительно (соответственно отрицательно) монотонных ДНФ.
Можно представить IUffi так же, как и обычную ШМ, в алгебраической модели, в сжатой и развернутой матричных моделях. Отличие будет только в том, что в алгебраической модели в зависимости от типа ШІМ2 система Ъ будет содержать не любые, а положительно или отрицательно монотонные ДНФ. По этой причине в сжатой матричной модели троичная матрица Т будет удовлетворять условию поляризации, т.е. ни один из ее столбцов не сможет одновременно содержать 0 и I. Таким образом, матрица Т7 вырождается в двоичную матрицу. Нетрудно заметить, что она будет совпадать с булевой матрицей В 2 развернутой матричной модели после замены каждой черточки "-" на 0, а каждого определенного элемента на I.
Универсальный полный тест. Под полным тестом в данном параграфе ив разделе 4.2.2 будем понимать проверяющий тест для множества всех одиночных коммутационных, константных неисправностей и для всех кратных неисправностей, состоящих из этих одиночных. Такой тест проверяет многие мостиковые неисправности, сводящиеся к кратным коммутационным. Понятие полного теста здесь несколько шире, чем в главе III, где полный тест предназначался для проверки коммутационных неисправностей. Проверяющий тест будем называть универсальным для системы булевых функций F , если он является полным для любой ШШІ2, реализующей F и имеющей столько же выходных полюсов, сколько функций содержит эта система. Прежде,чем перейти к вопросам о построении универсальных тестов, введем некоторые определения и обозначения.
Рассмотрим булево пространство ҐІ наборов значений входных переменных ПЖ). Элемент о є ҐІ находится в отношении больше или равно " " с элементом JI є At , если это отношение выдерживается покомпонентно, а если при этом Д , то большеД , что записывается как Л . Булеву функцию / , заданную в пространстве ҐІ , назовем монотонно возрастающей, или кратко монотонной. когда для любого элемента , обращающего f в I, и для любого элемента у± справедливо f(jz)= I. Элемент сС. называется нижней ( соответственно верхней ) единицей для булевой функции/Tl39], если -f()= I и не существует элемента у такого, что У)= I и Ji (соответственно уз JL). Аналогично, элемент dC , обращающий в 0, называется верхним ( нижним ) нулем для -f , когда любой элементу ?С( С Ji) придает значение I. Обозначим через /У - и ft множества всех нижних единиц и верхних нулей функции f соответственно. Очевидно, пара (/, /Л однозначно задает монотонную булеву функцию -f .
