Test generation for single and multiple stuck-at faults of a combination cir-cuit designed by covering shared free BDD with CLBs .pdf Известно, что построение тестового набора для неисправности требует большого объема вычислений [1 - 4]. Объем вычислений может быть сокращен, если на этапе проектирования схемы обеспечить ее контролепригодность: существование достаточно простой процедуры построения тестового набора для каждой из рассматриваемых неисправностей, возможно, в условиях расширения класса допустимых неисправностей. В этом отношении перспективным является синтез комбинационных схем по системе BDD-графов.В частности, схемы, построенные по системе ROBDD-графов из мультиплексоров, оказались контролепригодными для широкого класса неисправностей [5 -8]. В [9] для таких схем был предложен метод синтеза, гарантирующий 100% полноту проверяющего теста для одиночных константных неисправностей на полюсах элементов (мультиплексоров) схемы и неисправностей задержек путей схемы. Контролепригодность рассматриваемых схем обеспечивалась введением дополнительного входа.В [10] доказано, что для схемы, построенной путём покрытия системы ROBDD-графов программируемыми логическими блоками, для каждой одиночной константной неисправности на полюсах ПЛБ существует обнаруживающий её тестовый набор. Показано, что проверяющий тест для кратных неисправностей на полюсах программируемых логических блоков комбинационной схемы строится расширением проверяющего теста для одиночных неисправностей на полюсах блоков этой схемы.В данной работе обсуждаются контролепригодные свойства схемы, построенной по системе Free BDD (Freely-ordered Binary Decision Diagram)-графов покрытием ее программируемыми логическими блоками (ПЛБ). Такой синтез ориентирован на ПЛИС (программируемые логические интегральные схемы) - технологии, называемые в англоязычной литературе FPGA (Field Programmable Gate Ar-rаy)-технологиями. Схемы, полученные путём покрытия логическими блоками системы Free BDD-графов, в ряде случаев могут быть проще, чем аналогичные схемы, построенные по системе ROBDD-графов.Результаты, полученные в [10] для систем ROBDD-графов, частично распространяются на системы Free BDD-графов. В данной работе показано, что не для каждой одиночной константной неисправности на полюсах ПЛБ схемы, построенной по системе Free BDD-графов, существует обнаруживающий её тестовый набор. С учетом этого факта предложен метод построения тестового набора для кратной неисправности, являющийся модификацией метода, приведенного в [10]. Устанавливается, что проверяющий тест для кратных неисправностей на полюсах ПЛБ комбинационной схемы, полученной по системе Free BDD-графов, строится предложенным в работе [10] расширением проверяющего теста для одиночных неисправностей этой схемы на полюсах ПЛБ.Во втором разделе статьи описывается подход к синтезу комбинационных схем по системе Free BDD-графов. В третьем разделе вводятся базовые модели неисправностей системы графов и предлагаются методы построения для них тестовых наборов. В четвертом разделе устанавливается связь между базовыми неисправностями и одиночными константными неисправностями комбинационной схемы. В пятом разделе предлагается метод синтеза тестового набора для кратной неисправности системы Free BDD-графов, представляемой объединением базовых неисправностей. В шестом разделе приводится алгоритм построения проверяющего теста для кратных неисправностей комбинационной схемы на базе проверяющего теста для ее одиночных неисправностей.1. Синтез комбинационной схемы покрытием системы Free BDD-графов программируемыми логическими блокамиBDD-граф это ориентированный ациклический граф, основанный на использовании разложения Шеннона в каждой нетерминальной вершине v:fv = Xjx =0 + Xjx =\(11fx=0 = fv (xi = 0,..., xn),fvXi =l = fv (xi,..., x = 1,..., xn ).Здесь функция fx=0 сопоставляется вершине, в которую заходит левая дуга, исходящая из v, а функция 1 сопоставляется вершине, в которую заходит правая дуга.Нетерминальная вершина v BDD-графа отмечается индексом i переменной, по которой выполняется разложение функции fv. Функция fv представлена простыми цепями, соединяющими v с 1-концевой вершиной BDD-графа. (Под простыми цепями здесь и далее будем понимать последовательность дуг графа, проходимых в направлении ориентации, не содержащую повторяющихся вершин.) Простая цепь представляет конъюнкцию, составленную из переменных, индексы которых записаны в проходимых простой цепью вершинах. Если из вершины, помеченной индексом i, простая цепь проходит далее по левой дуге, отмечаемой нулем, то переменной с этим индексом приписывается в конъюнкции знак инверсии, если по правой, отмеченной единицей, то знак инверсии у переменной отсутствует. Одновременно вершине v сопоставляется инверсия функции fv, представленная аналогичным образом простыми цепями, соединяющими v с 0-концевой вершиной. Итак, каждой нетерминальной вершине BDD-графа наряду с индексом переменной, по которой выполняется разложение, сопоставляется пара взаимно инверсных булевых функций; терминальным, 1, 0-концевым вершинам, сопоставляются соответственно константы 1, 0.При построении Free BDD-графа (в отличии от .ROBDD-графа) порядок переменных, по которым проводиться разложение, заранее не фиксирован. Free BDD-граф является сокращённым, т.е. он не содержит ни изоморфных подграфов, ни вершин v, левая и правая дуги которых заходят в один и тот же подграф. В каждой нетерминальной вершине переменная разложения выбирается по тому или иному критерию независимо от других нетерминальных вершин.Любая простая цепь, соединяющая корень BDD-графа с 1-концевой вершиной представляет конъюнкцию ортогональной дизъюнктивной нормальной формы (ОДНФ) для функции f которую задает BDD-граф в целом. ОДНФ - это логическая сумма попарно ортогональных конъюнкций.Любая простая цепь, соединяющая корень BDD-графа с 0-терминальной вершиной, образует конъюнкцию ОДНФ для инверсии функции f Разложение Шеннона также может быть выполнено для fv :fv = x~JvXi=0 + xf=1,(2)гдеTv =1 = fv - Xi =Xn ) .Пусть F = (fl,..., fm} есть система булевых функций, описывающих поведение комбинационной схемы. Построим Free BDD-граф для каждой булевой функции из F. Исключим изоморфные подграфы из Free BDD-графов, оставив по одному представителю. Совместим 1-концевые вершины различных функций в одну 1-концевую вершину и их 0-концевые вершины в одну 0-концевую вершину. В результате получим граф с m корневыми вершинами и двумя терминальными вершинами. Этот граф представляет систему m булевых функций. Назовем его системой Free BDD-графов.Удалим из системы Free BDD-графов все дуги, заходящие в 0-концевую вершину, и получим Free BDD-граф, представляющий поведение комбинационной схемы. Назовем его Free BDD-графом схемы. Покроем его ПЛБ, создаваемыми на базе LUT (Look up Тай^-технологий. Непременным условием покрытия является сохранение системы ОДНФ, порожденной Free BDD-графом схемы. Это значит, что, выполнив суперпозицию по полученной схеме с учетом запрета на поглощение и склеивание конъюнкций, а также запрета на удаление повторяющихся букв в конъюнкциях и повторяющихся конъюнкций, получим систему ОДНФ, содержащую все конъюнкции, порожденные простыми цепями, соединяющими корни Free BDD-графа схемы с его 1-концевой вершиной, и только их.Один из возможных способов покрытия заключается в следующем.1..Просматриваем Free BDD-граф схемы, начиная с наиболее удаленных от его корней нетерминальных вершин и заканчивая корневыми вершинами. Каждой вершине приписываем число переменных, от которых зависит сопоставляемая вершине функция.2.Пусть к - максимальное число входных переменных (входных полюсов) ПЛБ. Двигаемся от наиболее удаленных от корней нетерминальных вершин. Находим вершины, в которых число переменных не более к, а каждая соседняя с ней и более близкая к корням вершина зависит не менее чем от (к + 1) переменной. Найденным вершинам сопоставляем ПЛБ, которые реализуют функции, соответствующие этим вершинам. Функция ПЛБ представляется в виде ОДНФ, порожденной покрытым фрагментом Free BDD-графа схемы.3.Выходам ПЛБ сопоставляем внутренние переменные строящейся комбинационной схемы. Обозначим их wb...,ws. Эти же переменные объявляются концевыми (терминальными) вершинами усеченного Free BDD-графа схемы наряду с его 1-концевой вершиной. Все простые цепи, соединяющие вершины wb...,ws с 1-концевой вершиной Free BDD-графа схемы и покрытые ПЛБ строящейся схемы, удаляются. Если простая цепь начинается в некоторой нетерминальной вершине усеченного графа и заканчивается в его концевой вершине типа wi, то в соответствующую ей конъюнкцию добавляется переменная wi без знака инверсии.4.Продолжаем покрытие усеченного Free BDD-графа схемы, выполняя шаги 1 - 3 и получая все более простые усеченные графы, пока множество непокрытых вершин не окажется пустым. В результате получаем комбинационную схему С. Отметим некоторые ее свойства.а)Выход любого ПЛБ сопоставлен либо нетерминальной вершине, либо одно-му из корней Free BDD-графа.б)Входам ПЛБ в общем случае сопоставлены как нетерминальные вершиныFree BDD-графа схемы, соответствующие внутренним переменным схемы С, таки входные переменные функций системы, реализуемой Free BDD-графом схемы.в)Если две или более дуги входят в нетерминальную вершину Free BDD-графа схемы, тогда фрагменты подграфа, корнем которого она является, могутодновременно входить в различные ПЛБ.Free BDD-граф для системы из одной функции представлен на рис. 1, Free BDD-граф схемы изображен на рис. 2.Выполним покрытие Free BDD-графа схемы ПЛБ.Пусть число входных переменных ПЛБ равно 4. Сначала выберем подграф, представленный на рис. 3, a, сопоставив ему ПЛБ!. ПЛБ2 соответствует подграфу, изображенному на рис. 3, b, и т.д.Рис 3. Подграфы, соответствующие ПЛБ] (a), ПЛБ2 (b), ПЛБ3 (с), ПЛБ4 (d), ПЛБ5 (e), ПЛБ6 (f) и ПЛБ7 (g)_Г_ПЛБ 7ПЛБ5ПЛБ 6ПЛБ!ПЛБ3 ПЛБ2ПЛБ4AAAi , A i i i k i Г » f - i1234 6Рис. 4. Схема С52. Построение тестовых наборов для базовых моделей неисправностей системы Free BDD-графовСначала рассмотрим традиционные одиночные константные неисправности нетерминальных вершин (полюсов) системы.Заметим, что любой нетерминальной вершине v системы Free BDD-графа соответствуют две функции: f = xj*'=° + xj;*' =1 и f = хг fV ° + xjl' 1.Неисправность константа 1 вершины v означает, что функция fv обращается в константу 1 и fv обращается в константу °. Неисправность константа ° означает, что функция fv обращается в константу ° и fv - в константу 1. Эти неисправности изменяют функцию f системы F, если j-й корень соединен с вершиной v. А именно: неисправность константа 1 расширяет область единичных значений функции f, а неисправность константа ° уменьшает область единичных значений f.Пусть вершина v соединяется с j-м корнем системы Free BDD-графа.Будем говорить, что набор а значений входных переменных x1,..., xn представляется некоторой простой цепью системы Free BDD-графов, если он обращает в единицу конъюнкцию к, сопоставляемую этой простой цепи.Неисправность проявляет себя в j-м корне системы Free BDD-графов, если в ее присутствии меняется значение j-й функции системы F.Утверждение 1. Тестовый набор для неисправности константа 1 в нетерминальной вершине v представляется простой цепью, соединяющей j-й корень системы Free BDD-графов с ее °-концевой вершиной и проходящей через нетерминальную вершину v. Тестовый набор всегда существует, на нем в присутствии неисправности изменяется значение j-й функции системы F с ° на 1.Доказательство следует из способа построения системы Free BDD-графов.Разобьем простую цепь, представляющую тестовый набор, на два отрезка е и Z. Здесь е - простая цепь, соединяющая j-й корень системы Free BDD-графов с нетерминальной вершиной v, а Z - простая цепь, соединяющая вершину v с °-конце-вой вершиной.Утверждение 2. Тестовый набор для неисправности константа ° в нетерминальной вершине v представляется простой цепью, соединяющей j-й корень системы Free BDD-графов с ее 1-концевой вершиной и проходящей через полюс v . Тестовый набор всегда существует, на нем в присутствии неисправности изменяется значение j-й функции системы F с 1 на °.Доказательство. Доказательство следует из способа построения системы Free BDD-графов.Простая цепь аналогично предыдущему разбивается на отрезки е и Z.Далее рассмотрим неисправности °1(1°) дуг, исходящих из одной и той же нетерминальной вершины v системы Free BDD-графов. Будем называть их в дальнейшем °1(1°)-неисправностями нетерминальной вершины v. Иногда уточнение, к какой вершине относится °1(1°)-неисправность, будем опускать. Эти неисправности вместе с константными неисправностями нетерминальных вершин системы Free BDD-графов в дальнейшем будем называть базовыми неисправностями системы; дугу, заменяемую в системе Free BDD-графов константой будем называть °(1)-дугой.Заметим, что левой дуге, исходящей их вершины v, соответствует переменная X', где ' - индекс вершины v, а правой дуге соответствует переменная х-.Неисправность 1° означает, что переменная xt заменяется константой 1, а переменная xt - константой ° в выражениях (1), (2). В результате функция fvобращается в fx=°, а функция fv обращается в fx . Аналогичным образомнеисправность °1 обращает функцию fv в f^' 1 и функцию fv в fx .Во Free BDD-графе возможно существование вершины v, отмеченной индексом ', для которой f*'=° = fx 1. Неисправность 1° в вершине такого типа несущественна, так как при замене соответствующими константами переменных xt и xi в выражениях (1), (2) значения функций fv и fv не изменится, что следуетиз выражений (1), (2).Рассмотрим Free BDD-граф, изображённый на рис. 1. Разложение Шеннона для вершины v1, отмеченной индексом 1, имеет видЗдесьx2 x3 x4 x6 V x2 x3 x4 V x2 x3 x4 x5 x6 V x2 x3 x4 x5 V x2 x3 x4 V x2 x3 x4 x5 V x3 x4иcx, =1x2 x3 x4 x6 V x2 x4 V x2 x3 x4 x5 x6 V x2 x4 x5 V x2 x5Функции и f 11 1 представлены матрицами в коде Грея на рис. 5 и 6 соответственно. По представлениям функций f*1 =°, f*1 1 в коде Грея видно, чтоfv1x1=°= fv1x1=1 и соответствующие подграфы реализуют одну и ту же булеву функцию, но при этом не изоморфны. Для данного примера 1° (°1)-неисправность в вершине v1 является несущественной.ex.x4x2fa x4 x2x6 x5x6 x5Рис. 5. Представление fxРассмотрим вершину v , для которой f^' ° ф f*' 1.Пусть вершина v соединена с j-м корнем системы Free BDD-графов. Kx (K-)представляют ОДНФ, конъюнкции которых задаются простыми цепями, соединяющими j-й корень и 1-концевую вершину через вершину v и дугу xt (xt). В каждую конъюнкцию из Kx (K-) входит переменная xt (xt).xВыберем из K* (Kx*;) такие ОДНФ K**(K-***), которые соответствуют толькоодной простой цепи р, соединяющей j-й корень с вершиной v.Пусть KXj () получается из K**(Kx*) удалением переменной xt (xi).Теорема 1. а есть тестовый набор для существенной °1-неисправности нетерминальной вершины v, причем неисправность проявляется на этом наборе в j-м корне системы Free BDD-графов, f (а) = 1, если и только если Kx*(a) = 1 и KXi (а) = °.Доказательство. Если простая цепь е выбрана и K- (а) = 1, то существуетxпростая цепь из вершины v в 1-концевую вершину системы .ROBDD-графов, сопоставляемая одной из конъюнкций множества K- (а), то есть fj (а) = 1. В при-xсутствии неисправности имеем: K- (а) = °, и Kx (а) превращается в Kx . Некоторые конъюнкции из Kx могут быть не ортогональны конъюнкциям из K- .Для проявления неисправности на наборе а необходимо выполнение условия Kx' (а) = ° : оно гарантирует смену значения функции f с 1 на ° в присутствии неисправности. Это условие обеспечивается подходящей простой цепью из вершины v через дугу, сопоставляемую x, в °-концевую вершину системы ROBDD-графов.Пусть имеем: K*-*^) = 1 и Kx (а) = ° . Тогда f (а) = 1. В присутствии неисправности дуга, сопоставляемая x' , обращается в ° и, следовательно, fj (а) = °, так как Kx (а) = ° . Теорема доказана.Теорема 2. а есть тестовый набор для существенной 1°-неисправности нетерминальной вершины v, причем неисправность проявляется на этом наборе в j-м**корне системы Free BDD-графов, fj (а) = 1, если и только если Kx (а) = 1 и K- (а) = °.Л'Доказательство аналогично доказательству предыдущей теоремы.**Пусть Kx (Kx:) представляют ОДНФ, конъюнкции которых задаются простыми цепями, соединяющими j-й корень и °-концевую вершину через вершину v и дугу xt (xt). Выберем из K*х (K*:) такие ОДНФ K** (K**), которые соответствуют только одной простой цепи р, соединяющей j-й корень с вершиной v.Пусть Kx (Kx) получается из Kx* (K**) удалением переменной xt (xt).Теорема 3. а есть тестовый набор для существенной °1-неисправности нетерминальной вершины v, причем неисправность проявляется на этом наборе в j-м**корне системы Free BDD-графов, fj (а) = °, если и только если Kx (а) = 1 иK 'Xi (а) = °.Доказательство аналогично доказательству теоремы 1.Теорема 4. а есть тестовый набор для существенной 1°-неисправности нетерминальной вершины v, причем неисправность проявляется на этом наборе в j-м**корне системы Free BDD-графов, fj (а) = °, если и только если Kx. (а) = 1 и K-(а)=°.Доказательство аналогично доказательству теоремы 1.Теорема 5. Для любой существенной неисправности и простой цепи е, соединяющей j-й корень системы Free BDD-графов с нетерминальной вершиной v, существует тестовый набор а, обнаруживающий °1(1°)-неисправность дуг, исходящих из вершины v.Доказательство. Сопоставляемая нетерминальной вершине функция fv существенно зависит от переменной x . Это следует из построения системы ROBDD-графов. Следовательно, существует булев вектор а, такой, что:1..fvx' =1(а) = 1, fvx'=°(а) = ° и / или2..fvx' =1(а) = °, fvx'=°(а) = 1.Условие 1 выполняется, когда тестовый набор а для 1°-неисправности находится по теореме 2, а условие 2 выполняется, когда тестовый набор а находится для °1-неисправности по теореме 1. Аналогично, условие 1 выполняется, когда тестовый набор а для °1-неисправности находится по теореме 3, а условие 2 выполняется, когда тестовый набор а для 1°-неисправности находится по теореме 4. Теорема доказана.Приведём пример построения тестового набора для существенной неисправности °1 дуг, исходящих из вершины 2, сопоставляемой переменной разложения x2 (рис. 7).Множество конъюнкций, удовле-**творяющих условию Kxr (а) = 1, представляется в виде x1 x2 x3 x4, x1 x2 x3 x4 x6, а множество конъюнкций, удовлетворяющих условию K (а) = °, представляется в виде x5, x5 x4, x3x4x5 x6. Одна из простых цепей, соединяющих дугу x2 с °-концевой вершиной, порождаетсяконъюнкцией x1 x2x3x4 и отмечена на рис. 7. Построение тестового наборарис. 7 жирной линией. Одна из простыхдля неисправности °1 вершины 2цепей, соединяющая вершину 5 с 1-кон-цевой вершиной, на рис.7 обозначена штриховой линией и представляется конъ-юнкцей x5.Пересечение рассматриваемых двух конъюнкций не пусто и представляется выражением x1x2 x3 x4 x5. Любой набор а, обращающий эту конъюнкцию в 1, является тестовым набором для данной неисправности.3. Построение тестового набора для одиночной неисправности комбинационной схемыОтметим, что из способа построения комбинационной схемы по системе Free BDD-графов следует, что одиночная константная неисправность выходного полюса v ПЛБ соответствует базовой неисправности подходящей нетерминальной вершины системы Free BDD-графов.Одиночная неисправность входного полюса v ПЛБ, сопоставляемого внутреннему полюсу комбинационной схемы, также соответствует базовой неисправности подходящей нетерминальной вершины системы. В этом случае тестовый набор представляется простой цепью е, соединяющей j-й корень системы Free BDD-графов с нетерминальной вершиной системы, сопоставляемой выходу неисправного ПЛБ, затем с нетерминальной вершиной, сопоставляемой рассматриваемому неисправному входному полюсу v этого ПЛБ, и простой цепью Z, соединяющей полюс v с одной из концевых вершин системы.Одиночная неисправность входного полюса ПЛБ, непосредственно связанного с входом x' комбинационной схемы, представляется базовыми неисправностями °1(1°), т. е. неисправностями дуг, исходящих из нетерминальных вершин системы Free BDD-графов, помеченных индексом '. Речь идет о нетерминальных вершинах, покрытых этим ПЛБ.Может оказаться недостаточным рассматривать только одну вершину, помеченную индексом ' и покрытую ПЛБ, как это делается для схем, полученных покрытием системы ROBDD-графов программируемыми логическими блоками. Если построение теста для очередной рассматриваемой вершины невозможно, то не обходимо перейти к следующей вершине, помеченной тем же индексом, если таких вершин больше нет, то данная неисправность несущественна, т.е. она не влияет на функционирование подсхемы, сопоставляемой j-му выходу соответствующего ПЛБ. Итак, не для каждой одиночной неисправности входного полюса ПЛБ существует тестовый набор, ее обнаруживающий.Тестовый набор для существенной °1(1°)-неисправности представляется простой цепью е, соединяющей j-й корень системы Free BDD-графов с нетерминальной вершиной v, простой цепью Z, соединяющей вершину v через °-дугу с ° или 1-концевой вершиной системы Free BDD-графов, и простой цепью п, соединяющей вершину, в которую заходит 1-дуга с инверсной концевой вершиной этой системы. Здесь имеется в виду разметка символом дуги в присутствии неисправности.Если в случае неисправности входного полюса ПЛБ, непосредственно соединенного с входом схемы, из соответствующей вершины v Free BDD-графа схемы, покрытой ПЛБ, исходит единственная дуга, то возможны две ситуации.Неисправность сводится к обращению в константу 1 переменной, сопоставляемой этой дуге. Тогда тестовый набор задается простой цепью е, соединяющей j-й корень системы графов с вершиной v простой цепью Z, состоящей из единственной дуги, соединяющей v с °-концевой вершиной системы Free BDD-графов, и простой цепью п, начинающейся в вершине, в которую заходит неисправная дуга, и заканчивающейся в 1-концевой вершине. Будем иметь в виду, что в исправном состоянии на j-м корне системы достигается значение °, а в неисправном - значение 1.Если неисправность сводится к обращению в константу ° переменной, сопоставляемой этой дуге, то тестовый набор задается простой цепью е, соединяющей j-й корень с нетерминальной вершиной v, и простой цепью Z, соединяющей v с 1-концевой вершиной системы Free BDD-графов и проходящей через рассматриваемую дугу. Заметим, что в исправном состоянии на j-м корне системы достигается значение 1, а в неисправном - значение °.Покажем, что проверяющий тест для всевозможных кратных неисправностей, представленных совокупностью одиночных неисправностей на полюсах ПЛБ комбинационной схемы, можно получить расширением проверяющего теста для одиночных неисправностей. Длина проверяющего теста для кратных неисправностей есть линейная функция длины проверяющего теста для одиночных неисправностей.4. Построение тестового набора для кратной неисправности, являющейся объединением базовых моделей неисправностей системы Free BDD-графовРассмотрим кратную неисправность Укр, составленную из произвольного множества vb..., vs базовых неисправностей системы Free BDD-графов. Составляющие неисправности множества представляются °(1)- и °1(1°)-неисправностями системы.Базовой °1(1°)-неисправности сопоставлена нетерминальная вершина, из которой исходят неисправные дуги. Будем говорить, что эта вершина представляет неисправность в системе Free BDD-графов и называть неисправные дуги °(1)-дугами в соответствии с их разметкой в присутствии неисправности. Некоторые из базовых °1(1°)-неисправностей могут быть несущественными. При рассмотрении базовых °(1)-неисправностей нетерминальных вершин системы Free BDD-графов будем иметь в виду, что сами вершины являются представителями этих неисправностей. Неисправности и представляющие их вершины в дальнейшем будем отождествлять, используя термин «неисправная вершина», если это удобно.Пара базовых неисправностей связана отношением подчинения, если представляющие эти неисправности вершины лежат на одной и той же простой цепи, соединяющей некоторый корень системы Free BDD-графов с ее 1(°)-концевой вершиной.Базовая неисправность, представленная ближайшей к корню вершиной, называется подчиняющей; неисправность, представленная более удаленной вершиной, - подчиненной.Базовую подчиняющую неисправность v' будем называть доминирующей по отношению к подчиненной базовой неисправности vj, если в присутствии неисправности vt система Free BDD-графов представляет ту же систему булевых функций, что и в присутствии кратной неисправности (v', vj). Последнее означает, что одиночная и кратная неисправности эквивалентны и, следовательно, множества обнаруживающих их тестовых наборов совпадают. Если доминирующая неисправность v' является несущественной, то кратная неисправность (v', vj) также несущественна.Из сказанного следует, что построение тестового набора для существенной кратной неисправности (v', vj) можно заменить построением тестового набора для неисправности v'. Если доминирующая неисправность v' является несущественной, то множество тестовых наборов для кратной неисправности (v', vj) пусто.Вместо подчиненной базовой неисправности vj можно рассматривать подмножество подчиненных базовых неисправностей Vj, введя аналогичное отношение доминирования между vt и Vj.Рассмотрим базовую °(1)-неисправность vt из Укр. Ее проявление в системе Free BDD-графов приводит к совмещению вершины vt с °(1)-концевой вершиной системы.Пусть Vi - множество подчиненных vt одиночных неисправностей из Укр, не содержащее v . Вершина v является корневой для подграфа, в пределах которого находятся неисправности из V .Теорема 6. Базовая °(1)-неисправность vt является доминирующей по отношению к любой базовой неисправности из V .Доказательство. Поскольку неисправность из V вносит изменение в поддерево с корнем в вершине v , а рассматриваемое поддерево исчезает в присутствии неисправности v, то утверждение теоремы очевидно. Теорема доказана.Следствие. Базовая °(1)-неисправность vt является доминирующей по отношению к кратной неисправности V .Рассмотрим базовую °1(1°)-неисправность v;. Ее проявление приводит к отсоединению от v , путем обрыва °-дуги, подграфа, корнем которого является вершина, в которую эта дуга заходит, и совмещению вершины v' c вершиной, в которую заходит 1-дуга неисправности v'. Это означает, что при возникновении °1-неисправности вместо функции f = xjx'=° + xjx'=1 (f = xtfv + xj^ ) вx =1 -x'=1вершине vt реализуется функция fx' = (f ' ), при этом для несущественной неисправности имеем fv = fvx'=1 (fv = fx' 1).Аналогичная ситуация имеет место для 1°-неисправности.Из построения системы Free BDD-графов следует, что отсоединяемый за счет рассматриваемой неисправности подграф может остаться связанным с корневыми вершинами системы Free BDD-графов через вершины, отличные от v'. Обозначимчерез V ° множество неисправностей из V , лежащих в отсоединяемом подграфе.Будем говорить, что подграф подчинен °-дуге.Обозначим через V1 множество неисправностей из V, подчиненных 1-дуге неисправности v*. Неисправности множества V1 лежат в подграфе, корнем которого является вершина, в которую заходит 1-дуга. Множества V 1 , V ° могут пересекаться при наличии общих вершин в соответствующих им подграфах. Заметим, что если V1 пусто, то базовые неисправности из V° не подчинены 1-дуге.Теорема 7. Базовая °1(1°)-неисправность vt является доминирующей по отношению к множеству неисправностей V ° , если V 1 пусто.Доказательство. Так как V 1 пусто, то в присутствии неисправности из графаудаляются все вершины, соответствующие неисправностям из V ° , значит V ° не влияет на поведение неисправной функции. Теорема доказана.Теорема 8. Кратная неисправность (v,, V1) является доминирующей по отношению к кратной неисправности (v , V 1 , V ° ).Доказательство. Функция и ее инверсия, полученные из fx' = (f' ) для °1-неисправности (из f (f) для 1°-неисправности) внесением неисправностей из V 1 , совпадают с функциями, полученными аналогичным образом для кратной неисправности (V°, V1), так как неисправности из V°, не совпадающие с неисправностями из V 1 , на функцию fx =1(fx =°) никакого влияния не оказывают. Таким образом, в присутствии обеих неисправностей реализуется одна и та же функция и соответствующая ей инверсия. Теорема доказана.Из теорем 7, 8 заключаем, что неисправности множества Vt° можно исключитьиз рассмотрения при анализе влияния подчиненных неисправностей на °1(1°)-неисправность v .Напомним, что тестовый набор, обнаруживающий базовую существенную °1(1°)-неисправность, представляется простой цепью е, соединяющей корень системы Free BDD-графов с вершиной v, простой цепью Z (основной), соединяющей °-дугу с 1(°)-концевой вершиной системы Free BDD-графов, и простой цепью п (дополнительной), соединяющей вершину, в которую заходит 1-дуга, с инверсной концевой вершиной. Дополнительная простая цепь порождает конъюнкцию, ортогональную каждой конъюнкции, представленной простой цепью, соединяющей вершину, в которую заходит 1-дуга, с 1(°)-концевой вершиной системы Free BDD-графов.Будем говорить, что неисправность vj разрушает тестовый набор а для существенной неисправности v , если тестовый набор для v перестает быть таковым, когда к v добавляется неисправность vj.Для несущественной подчиняющей неисправности построение тестового набора невозможно, однако в паре с существенной подчиненной неисправностью кратная неисправность может оказаться существенной.Теорема 9. Базовая, подчиненная °(1)-неисправность или подчиненная существенная °1(1°)-неисправность нетерминальной вершины vj из V 1 может быть об-наружима в присутствии несущественной базовой, подчиняющей °1(1°)-неис-правности v .Доказательство. В рассматриваемом случае, за счёт °1(1°)-неисправности v, происходит совмещение вершины v и вершины, в которую заходит 1-дуга. Это значит, что наличие существенной неисправности из V 1 может изменить некоторые функции (сопоставляемые этим функциям корни системы соединены с вершиной v') системы Free BDD-графов. Теорема доказана.Теорема 10. Базовая подчиненная °(1)-неисправность нетерминальной вершины vi из V1 может разрушить тестовый набор а для существенной базовой, подчиняющей °1(1°)-неисправности v .Доказательство. Пусть тестовый набор а, обнаруживающий существенную °1(1°)-неисправность, обращает в единицу основную простую цепь Z, соединяющую °-дугу с 1-концевой вершиной, и дополнительную простую цепь п, соединяющую вершину, в которую заходит 1-дуга, с °-концевой вершиной. Наличие в простой цепи, начинающейся в вершине, в которую заходит 1-дуга, и заканчивающейся в 1-концевой вершине, базовой 1-неисправности может нарушить условие ортогональности конъюнкций, сопоставляемых неисправному пути (за счет исчезновения некоторых букв в сопоставляемой этому пути конъюнкции) и пути п. Теорема доказана.Теорема 11. Базовая, существенная, подчиненная °1(1°)-неисправность vj изV 1 может разрушить тестовый набор для существенной базовой, подчиняющей°1(1°)-неисправности v .Доказательство. Доказательство аналогично предыдущему с той лишь разницей, что в конъюнкции, сопоставляемой неисправному пути, может исчезнуть только одна буква. Теорема доказана.Теорема 12. Тестовый набор а, построенный для базовой, подчиненной, или существенной °1(1°)-неисправности v , может быть разрушен другой базовой, подчиняющей неисправностью vi из V^,, если представляющая последнюю неисправность вершина принадлежит простой цепи е, соединяющей vt c j-м корнем системы Free BDD-графов, и эта простая цепь участвует в представлении тестового набора а.Доказательство. Пусть в присутствии неисправности v значение функции fj меняется на наборе а с 1 на °, и vi есть базовая 1-неисправность, представляемая вершиной простой цепи е (простая цепь участвует в представлении тестового набора), тогда последняя неисправность разрушает тестовый набор а. Теорема доказана.Вернемся к заданному множеству кратных неисправностей V^. Если в этом множестве содержится базовая °(1)-неисправность vs, не подчиненная никакой другой неисправности этого множества на некоторой простой цепи е, соединяющей vs с одним из корней системы Free BDD-графов, то тестовый набор а, обнаруживающий эту неисправность и представленный, в том числе, простой цепью е, является тестовым набором для неисправности V^,.Если не существует базовой °(1)-неисправности с такими свойствами, то выбираем базовую °1(1°)-неисправность v , не подчиненную никакой другой неисправности на некоторой простой цепи е, соединяющей v с одним из корней системы Free BDD-графов. Для нее строим Gvi граф следующим образом.Построение Gvi графа:1..Исключаем °-дугу, исходящую из v вместе со всеми подчиненными ей вершинами и дугами, не подчиненными одновременно 1-дуге, исходящей из v'. Объявляем v' корнем подграфа, выделяемого из системы Free BDD-графов.2..В полученном подграфе рассматриваем ближайшие к v' вершины, представляющие базовые °1(1°)-неисправности из V . Исключаем в каждой из них °-дугу вместе с подчиненными ей дугами и вершинами, не подчиненными одновременно подграфам с корнями, в которые заходят 1-дуги рассматриваемого подмножества неисправностей. Будем говорить, что вершины этих неисправностей образуют первый уровень близости к v . Далее аналогичным образом поступаем с вершинами второго, третьего и т. д. уровней близости, представляющими базовые °1(1°)-неисправности из V , пока не исчерпаем все из них. В результате построим граф Gv .Теорема 13. Граф Gvi связен и содержит °,1-концевые вершины.Доказательство. Утверждение теоремы следует из того факта, что в очередном связном подграфе, с корнем в вершине v и °,1-концевыми вершинами, при рассмотрении очередной вершины, представляющей °1(1°)-неисправность из V , с целью построения Gv , сохраняется одна из двух дуг вместе с подграфом, соединяющим эту дугу с °,1-концевыми вершинами. Теорема доказана.Отметим, что граф Gv определяется только парой v , V и не зависит от выбранной простой цепи е.Алгоритм построения тестового набора с использованием Gvi графа:1. В графе Gv' находим вершину vs, представляющую базовую °(1)-неисправ-ность из V', если она существует, и простую цепь 5, соединяющую эту вершину с v , в пределах графа Gv . Отметим, что эта простая цепь может содержать вершины, сопоставляемые базовым °1(1°)-неисправностям из V . Их наличие приводит к исключению некоторых букв из конъюнкции, сопоставляемой простой цепи 5 в присутствии неисправности V^,.2..Находим простую цепь Z, соединяющую vs с 1(°)-концевой вершиной. Если построение Z по Gvi невозможно, цепь строиться по системе Free BDD-графов. Эта цепь также может содержать вершины, сопоставляемые базовым °1(1°)-неисправностям, их наличие приводит к исключению некоторых букв из конъюнкции, сопоставляемой простой цепи Z в присутствии неисправности V^,.3..Вектор а, представляемый цепями 5, е, Z, является тестовым набором для неисправности V^,.4.Если V' не содержит базовых °(1)-неисправностей в графе Gvi, то находим в нем ближайшую к °(1)-концевой вершине базовую °1(1°)-неисправность vs, для которой в подграфе с корнем в vs не содержится неисправностей из V.5..Для нее отыскиваем простую цепь 5, соединяющую vs с в дереве Gvi. Заметим, что эта простая цепь может содержать вершины, сопоставляемые базовым °1(1°)-неисправностям из V . Их наличие приводит к исключению некоторых букв из конъюнкции, сопоставляемой простой цепи 5 в присутствии неисправности V^.6..Далее находим по системе Free BDD-графов основную простую цепь Z, соединяющую °-дугу, исходящую из vs, с 1(°)-концевой вершиной. Дополнительная простая цепь п, соединяющая вершину, в которую заходит 1-дуга, исходящая из vs, с инверсной концевой вершиной, содержится в Gvi. Если выбранная неисправность несущественна, т.е. построение тестового набора невозможно, то рассматривается следующая за vs ближайшая к °(1)-концевой вершине базовая неисправность. Дополнительная простая цепь п для таких неисправностей проходит через 1-дугу несущественной подчинённой неисправности. Цепь п не содержит вершин, сопоставляемых базовым существенным неисправностям из V'. В результате либо будет найдет тестовый набор, обнаруживающий кратную неисправность, либо кратная неисправность оказывается несущественной.7..Вектор а, представляемый цепями 5, е, Z, п, является тестовым набором для неисправности V^,.Рассмотрим пример (рис. 8).Здесь темные вершины 4 и 5 представляют 1°- и 1-неисправности соответственно. 1°-неисправность v4 не подчинена ни одной неисправности вдоль простойцепи, обозначенной жирной линией. 1-неисправность v5 принадлежит V41 . Эта неисправность может разрушить тестовый набор для 1°-неисправности v4. Следовательно, нужно строить тестовый набор для 1-неисправности v4, используя граф Gv4 (рис. 9). Простая цепь Z (x5 x6) этого графа, отмеченная штриховыми линиями, вместе с простой цепью е (x1 x2x3) Free BDD-графа (рис. 8), отмеченной жирной линией, и простой цепью 5, соединяющей вершины 4 и 5 графа Gv4 , представляют тестовые наборы для рассматриваемой кратной неисправности, соответствующая конъюнкция имеет вид x1 x2x3x4x5x6. В частности, булев вектор, обращающий в 1 все вышеперечисленные цепи, имеет видx1 x2 x3 x4 x5 x6 ° 1 1 ° ° 1.Заметим, что любая рассматриваемая кратная константная неисправность на полюсах ПЛБ комбинационной схемы представляется соответствующей кратной неисправностью системы Free BDD-графов. Следовательно, тестовый набор для является тестовым набором для кратной константной неисправности этой комбинационной схемы.5. Построение проверяющего теста для кратных неисправностей комбинационной схемыКратная неисправность на полюсах комб

Скачать электронную версию публикации