Stuck-at fault detection, controllability and observability functions of the combinational circuit gate pole.pdf В настоящее время цифровые устройства используются повсеместно, и обеспечение их надежного функционирования является актуальной проблемой. Сегодня существует достаточно много моделей неисправностей, но классическая модель константной неисправности на полюсе элемента схемы остается по-прежнему популярной и исследователи продолжают искать эффективные методы решения различных задач, связанных с константной неисправностью [1]. Для константной неисправности исследуются такие задачи, как построение одного теста, некоторого подмножества тестов или всех тестов, оценка управляемости и наблюдаемости полюса элемента схемы и т.д. Исследования, выполненные в данной работе, позволяют решать совместно ряд задач, связанных с константной неисправностью. В настоящей статье исследуются функции обнаружения константной неисправности, наблюдаемости и управляемости для некоторого полюса элемента комбинационной схемы. Функция обнаружения константной неисправности представляет все тестовые наборы для обнаружения одиночной константной неисправности на полюсе; функция наблюдаемости представляет множество тех наборов входных переменных, которые обеспечивают смену значения на выходе схемы при смене значения на рассматриваемом полюсе; функция управляемости представляет наборы входных переменных, устанавливающие на полюсе значений а, ае{0,1}. Также исследуются эффективные способы получения этих функций в виде BDD и ортогональной дизъюнктивной нормальной формы (ОДНФ). ОДНФ и BDD представления булевой функции характерны тем, что по ним легко получить множество наборов значений входных переменных, обращающих функцию в единицу, так как конъюнкции ОДНФ взаимно ортогональны и, следовательно, любой набор значений входных переменных может обратить в единицу не более одной конъюнкции ОДНФ; в BDD все пути от корня к некоторой терминальной вершине также представляют взаимно-ортогональные конъюнкции. То есть, например, ОДНФ функции обнаружения некоторой константной неисправности представляет множество тестов для этой неисправности, а каждая конъюнкция ОДНФ представляет подмножество этого множества, и подмножества, соответствующие разным конъюнкциям, не пересекаются. Кроме того, имея ОДНФ или BDD представление булевой функции, легко вычислить вероятность единичного значения функции на случайном входном наборе, и, следовательно, получение одного из этих представлений для рассмотренных функций позволяет вычислить меры тестопригодности: вероятность обнаружения неисправности, управляемость и наблюдаемость. Данная работа является продолжением исследований, выполненных в работах [2-4]. 1. Основные определения Пусть имеется комбинационная схема S с n входами и m выходами. В данной работе будем рассматривать только одиночные константные неисправности. Пусть константная неисправность ае {0,1} присутствует в полюсе v схемы; tyi(X), i = 1,m , - функция, реализуемая i-м выходом исправной схемы и зависящая от входных переменных множества X, X = {x1, ..., xn}, а фа(X), ае{0,1}, - функция, реализуемая i-м выходом схемы, в которой присутствует неисправность константа а в полюсе v. Будем говорить, что булева функция представляет некоторое множество входных наборов тогда, когда она принимает значение 1 на всех наборах из этого множества и только на них. Будем называть функцией обнаружения неисправности а, ае {0,1}, Da(X), функцию вида Da (X) = (фх(Х) 0фа (X))v... v^m (X) 0фт (X) )= Df (X) v... v Dm (X), (1) Df (X)=фг (X) е фа (X), i=1m. (2) Здесь Df (X) - функция обнаружения неисправности а, ае {0,1}, на i-м выходе схемы. Функция обнаружения неисправности Da'(X) представляет все тестовые наборы для константной неисправности а. Будем называть функцией наблюдаемости B(X) функцию вида B(X) = (ф1 (X) еф0( X ))v... v(ф1m (X) ефm (X))= b1 v... v Bm, (3) в, (X) = ф1 (X) еф0( X), i = 1m. (4) Здесь Bi - функция наблюдаемости полюса v на i-м выходе схемы. Функция B(X) представляет наборы входных переменных, на которых смена значения в полюсе v приводит к смене значения хотя бы на одном из выходов схемы. Функцию, реализуемую полюсом v схемы, будем называть функцией 1-управляемости, а инверсию этой функции - функцией 0-управляемости. Обозначим функцию 1-управляемости через C!(X), а 0-управляемости через C0(X); обозначим через f(XX) функцию, реализуемую полюсом v схемы. Тогда C:(X) = fX), C 0( X) = f(X). (5) Получение функции обнаружения неисправности и функции наблюдаемости непосредственно по формулам (1)-(4) в некотором известном в настоящее время представлении при больших размерах исходной схемы S может оказаться достаточно трудоемким. Например, если получать их по структурному описанию схемы, то необходимо рассмотреть схему практически двойного размера относительно исходной. Исследуем возможности сокращения трудоемкости при получении представлений данных функций. Рассмотрим получение этих функций в виде двух представлений: ОДНФ и BDD. Напомним, что ОДНФ называется ДНФ, в которой конъюнкции попарно ортогональны. Графовое представление булевых функций в виде BDD является одним из широко используемых в настоящее время, так как позволяет компактно представлять функции и эффективно выполнять операции над ними. Начнем рассмотрение с функции наблюдаемости, а затем рассмотрим функцию обнаружения неисправности, поскольку она выражается через функцию наблюдаемости. 2. Функция наблюдаемости 2.1. ОДНФ-представление функции наблюдаемости Сопоставим рассматриваемому полюсу схемы переменную v. Затем получим функцию ^(X, v), i = 1, m , реализуемую i-м выходом схемы, рассматривая переменную v в качестве входной. ^i(X, v) порождает функции ф,^ и фа (X) для неисправности константа ае {0, 1}. Для неисправности константа 1 ф1 (X) = П; (X ,1); для неисправность константа 0 ф0( X) = П; (X ,0). Пусть fX) - булева функция, реализуемая полюсом v схемы и зависящая от входных переменных множества X. Тогда Ф, (X) = ц, (X, f (X)). Заметим, что Bt(X) - это булева производная функции ^(X, v) по переменной v (B,(X) = ) [5]. ov Получим функции ^(X, v), ц t(X,v) и fX) в виде ОДНФ по структурному описанию схемы. ОДНФ функции ц(X, v) может быть представлена в виде цДX, v) = Kt v KJ • v v KJ • v , (6) здесь Kt, KJ, KJ - ДНФ, не зависящие от переменной v. Очевидно, что ДНФ Kt, KJ, KJ являются ОДНФ. Тогда ОДНФ функции для неисправности константа 1 примет вид Ф1( X) = ц , (X ,1) = Kt v KJ ; ОДНФ функции для неисправности константа 0 примет вид Ф0(X) = ц . (X,0) = K. v KJ . Функция исправной схемы примет вид Ф. (X) = ц (X, f (X)) = Kt v KJ • f (X) v KJ • f(X). Представление функции ц t(X, v) в виде (6) предложено в работе [6]. ОДНФ функции ц t(X, v) может быть представлена в виде ц t(X, v) = Kt v KJ • v v KJ • v . Такое представление функции ц.(X, v) также предложено в работе [6]. K t, KJ, KJ - ОДНФ, не зависящие от переменной v. Тогда для неисправности константа 1 ф1(X) = ц(X,1) = K, v KJ; для неисправность константа 0 Ф0(X) =Ц(X,0) = K, v KJ; и для функции исправной схемы Ф (X) =^(X, f (X)) = K, v KJ • f (X) v KJ • f(X). Преобразуем формулу (4) для функции наблюдаемости Bt(X) полюса v на t-м выходе: B t (X) = ф1 (X) 0 ф0 (X) = ф1 (X)ф0 (X) v ф1 (X)ф0 (X) = = [кг v KJ)• (K, v KJ)v K v KJ)• [k, v KJ )= (7) = K, • Kt v Kt • KJ v KJ • Kt v KJ • KJ v Kt • Kt v Kt • KJ v KJ • Kt v KJ • KJ. Две ДНФ ортогональны друг другу, если любая конъюнкция одной ДНФ ортогональна любой конъюнкции другой ДНФ. Две конъюнкции к\ и к2 ортогональны, если к\ л к2 = 0. Если две конъюнкции ортогональны, то некоторая переменная входит в одну из них с инверсией, а в другую - без инверсии. Утверждение 1. 1. ОДНФ K ортогональна ОДНФ KJ и KJ . 2. ОДНФ K, ортогональна ОДНФ KJ и KJ . Доказательство. Рассмотрим конъюнкции к'е KJ и к"е Kt; конъюнкция к = к'• v принадлежит ОДНФ (6) функции цt(X, v) и, следовательно, к" и к ортогональны. Поскольку к" не зависит от переменной v по построению, то к и к ортогональные конъюнкции. Так как это верно для любых конъюнкций к' е KJ и к" е Kt, то ОДНФ K и KJ ортогональны друг другу. Остальные выводы утверждения доказываются аналогично. Утверждение 2. 1. ОДНФ К, ортогональна ОДНФ Kt, Kv и KJ . 2. ОДНФ К, ортогональна ОДНФ К, К] и KJ . Доказательство. ОДНФ ^,(X, v) и ^ ,(X,v) ортогональны друг другу. Следовательно, ОДНФ Кг ортогональна ОДНФ Кг. Рассмотрим конъюнкции k' е KJ и к" е Kt. Конъюнкция к = к' • v принадлежит построенной ОДНФ функции ^ (X, v), следовательно, конъюнкции к" и к ортогональны друг другу. Поскольку конъюнкция к" по построению не содержит переменной v, то к" ортогональна конъюнкции к'. Так как это верно для любых конъюнкций к" е Kt и к' е Kv , то ОДНФ Кг и Kv ортогональны друг другу. Остальные положения утверждения доказываются аналогично. Утверждение 3. 1. ОДНФ К J и Kv ортогональны друг другу. 2. ОДНФ KJ и Kv ортогональны друг другу. Доказательство аналогично доказательству утверждения 2. Принимая во внимание утверждения 1-3 и учитывая, что произведение ортогональных друг другу ДНФ равно 0, преобразуем выражение (7) и получим (8) B, (X) = KJ • KV v KV • KJ . Согласно утверждению 3 ОДНФ KJ и KJ ортогональны друг другу, ОДНФ KJ и KJ также ортогональны друг другу. Следовательно, произведения KJ • Kv и Kv • KJ ортогональны друг другу. Поскольку KJ , KJ , Kv , Kv являются ОДНФ, то произведения KJ • Kv и Кг • KJ также являются ОДНФ. Итак, получив произведение ОДНФ KJ и Kv, а также ОДНФ Kv и KJ из (8), получаем ОДНФ для функции B,(X). Если предположить, что все ДНФ K, Кг, KJ , KJ , KJ , KJ состоят из одного и того же числа конъюнкций, то применение формулы (8) вместо (7) позволяет в четыре раза сократить число перемножаемых конъюнкций. Функция наблюдаемости B(X) полюса v для схемы в целом, согласно формуле (3), имеет вид B(X) = B1(X) v B2(X) v... v Bm(X). Поскольку полученные по формуле (8) ОДНФ B,(X), i = 1,m , не обязательно ортогональны друг другу, то дизъюнкция ОДНФ B,(X), i = 1, m , в общем случае не является ОДНФ. Ортогонализируем (3) следующим образом: (9) (10) B(X) = B (X) v B2(X) v... v Bm (X) = Bx(X) v B1(X) • B2(X) v ... v B1(X) • B2(X) •... • Bm-!(X) • Bm (X). Чтобы по этой формуле получить ОДНФ функции B(X), необходимо представить B,(X) и Bt (X) в виде ОДНФ. Функция B,(X) в виде ОДНФ уже получена. Получим функцию Bt(X) также в виде ОДНФ. 0 0 0 B, (X) = 91(X) 0 90(X) = 91(X)q>0(X) v ф1(X)^(X) = = ( v KJ )• ) v KJ )v (k, v KJ )• (k, v KJ )= = Kt • Kt v Kt • KJ v Kt • KJ v KJ • KJ v Кг • К, v Кг • KJ v Kt • KJ v KJ • KJ . Пользуясь утверждением 1, сократим полученную формулу: B, (X) = К, v Kv • Kv v Кг v KJ • KJ . Выполнив произведение ОДНФ KJ и KJ , а также K_J и KJ из (10), согласно утверждениям 1-3, получим ОДНФ функции Bt (X). Если предположить, что все ДНФ Ki, K_i, KJ, KJ, KJ, KJ состоят из одного и того же числа конъюнкций, то применение формулы (10) вместо (9) позволяет в четыре раза сократить число перемножаемых конъюнкций. Пример 1. Для иллюстрации предложенного метода получения функции наблюдаемости в виде ОДНФ рассмотрим схему Q (заимствована из [6]), изображенную на рис. 1. Рис. 1. Схема Q Сопоставим числа 5, ..., 10 выходам элементов. Пусть u5, ..., u10 - внутренние переменные, соответствующие этим выходам. Рассмотрим полюс j схемы. Получим ОДНФ функции наблюдаемости для этого полюса. Получим ОДНФ функции ^(X,j): ^(X, j) = u10 = u8u9 = u8 v u8 • u9 = x1 © J V (x1 © j)(u7 v x4) = = X{V V XJ V (x1v v xJ • x4u7 = = x{V V x1v V (x1v V xJ • x4J = x{V V x1 J V x1x4J . Получим ОДНФ K, Kv , KJ: K = 0, Kv = x1 v x1x4 , KJ = x1. Получим ОДНФ функции X, j) : X, j) = u10 = u8u9 = (x1 © j) • (x4 v x4u7) = (xJJ v x1j) • (x4 v x4u7) = = (xJ v x1j) • (x4 v x4v) = x1x4v v x1x4v V x1x4J . Получим ОДНФ K , Kv , KJ : K = 0 , KJ = x1x4, KJ = x1x4 v x1x4 = x1. Получим ОДНФ функции наблюдаемости по формуле (8): B(X) = Kv • Kv v Kv • Kv = (x1 v x1x4) • x1 v x1x4 • x1 = x1 v x1x4 . 2.2. BDD-представление функции наблюдаемости Binary Decision Diagram (BDD) - это ориентированный граф с корнем и множеством вершин W [7]. Множество W содержит два типа вершин: терминальные и нетерминальные. Нетерминальная вершина w имеет две дочерние вершины low(w) е W и high(w) е W. В дочернюю вершину low(w) ведет левое ребро, исходящее из вершины w, а в вершину high(w) - правое ребро. Терминальная вершина w имеет значение value(w) е {0, 1}. Нетерминальной вершине BDD сопоставляется некоторая переменная x, от которой зависит булева функция, представляемая BDD. Иногда будем переменную, сопоставляемую вершине w, обозначать x(w). BDD G с корнем w сопоставляется булева функция fw, определяемая следующим образом: 1. Если w является терминальной вершиной, то а) если value(w) = 1, то fw = 1; б) если value(w) = 0, то fw = 0. 2. Если w - нетерминальная вершина, которой сопоставляется переменная xг, то fw (x1,..., xn ) = xi • flow(w)(x1,..., xn ) v xi • fh,gh(w)(x1,..., xn ) . Будем обозначать через G(h(x)) BDD-представление функции h(X). Здесь под BDD мы будем понимать reduced BDD, как они определены в [7]. Ориентированной цепи BDD сопоставляется конъюнкция, состоящая из переменных, соответствующих нетерминальным вершинам, через которые проходит цепь; причем если ребро в цепи является левым ребром, исходящим из вершины w, то переменная x(w) входит в конъюнкцию с инверсией, иначе - без инверсии. Конъюнкции, сопоставленные различным ориентированным цепям BDD, ведущим из корня в одну из терминальных вершин, ортогональны друг другу. В дальнейшем слово «ориентированные» будем опускать. Пусть ti, ..., ts - цепи BDD G(h(X)), ведущие из корня в терминальную вершину 1, а k(ti), ..., k(ts) -конъюнкции, сопоставленные этим цепям; t[,..., t's" - цепи BDD G(h(X)), ведущие из корня в терминальную вершину 0, и к(t[),..., к(t's") - конъюнкции, сопоставленные цепям t[,..., t's". Тогда из определения BDD следует, что h(X) = k(t1) v ... v k(ts), h (X) = k(t[) v ... v k(f^). Представим функцию ^(X, v) в виде BDD. Выберем переменную v в качестве последней переменной, по которой будет производиться разложение при построении BDD для ^(X, v). Извлечем из G(^(X, v)) ОДНФ ^(X, v) и цг (X, v). Представим, как и ранее, ОДНФ ^(X, v) в виде ц, (X, v) = Kt v Kv • v v KJ • v и ОДНФ ^"(X, v) в виде ^"(X, v) = Kt v KJ • v v KJ • v . Утверждение 4. ДНФ KJ v KJ и KJ v KJ , извлеченные из G(цi(X, v)), состоят из тех и только тех конъюнкций, которые соответствуют цепям в G(^(X, v)), ведущим из корня графа в вершины, сопоставленные переменной v. Если из некоторой вершины w, сопоставленной переменной v, в терминальную вершину 1 ведет правое ребро, то конъюнкции, соответствующие цепям, ведущим из корня в вершину w, принадлежат ДНФ KJ и KJ . Если же из этой вершины в терминальную вершину 1 ведет левое ребро, то конъюнкции принадлежат ДНФ KJ и KJ . Утверждение 5. 1. ДНФ KJ и KJ , извлеченные из G(^(X, v)), совпадают. 2. ДНФ KJ и KJ , извлеченные из G(^(X, v)), совпадают. Утверждение 6. ДНФ Кг (Кг), извлеченная из G(^(X, v)), состоит из тех и только тех конъюнкций, которые соответствуют цепям в G(^(X, v)), ведущим из корня графа в терминальную вершину 1(0) и не проходящим через вершины, сопоставленные переменной v. Имея в виду утверждение 5, формулу (8) для функции B,(X) преобразуем к виду B, = KJ • KJ v KJ • KJ = KJ v KJ . (11) Б, (X) = K, v Kv • Kv v K, v K] • K] = = K, v K] • K] v K , v K] • K] = K, v K,. В формулах (11) и (12) ДНФ K] , K] , K] , , K,, K, извлечены из G(^,(X, ])). Из утверждений 4 и 6 и формул (11) и (12) получим следующую процедуру построения BDD G(B,(X)) из BDD G(r[,(X, ])). Процедура 1. Получение BDD G(B,(X)) из BDD G(rl,(X, ])). 1. Последние ребра всех цепей BDD G(^ ,(X, ])), ведущих из корня в терминальные вершины и не проходящих через вершины, сопоставленные переменной ], направляются в терминальную вершину 0. 2. Удаляются все вершины, сопоставленные переменной ] вместе с исходящими из них ребрами, а ребра, ведущие в эти вершины, направляются в терминальную вершину 1. Итак, установлено, что BDD G(B,(X)) получается простой модификацией BDD G(^,(X, ])) и не превосходит последней по сложности. BDD G(B(X)) для функции B(X) строится как дизъюнкция BDD G(B,(X)) для функций B,(X), Рис. 2. BDD G(-q(X, ])) i = 1, m . Рис. 3. BDD G(B(X)), где B(X) - функция наблюдаемости полюса v схем^1 Q Пример 2. Построим BDD G(B(X)) для функции наблюдаемости полюса ] схемы Q (рис. 1). Построим BDD G(^(X, ])) для функции, реализуемой выходом схемы, полученной из схемы Q, в которой полюсу v сопоставлена входная переменная ], выполнив разложение по переменной ] в последнюю очередь. Полученный граф представлен на рис. 2. В графе на рис. 2 курсивом выделены цепи, представляющие конъюнкции из ДНФ B(X) = Kv v Kv . Это конъюнкции kx = x1x4 и k2 = xb Из формулы (10), утверждения 3 и утверждения 5 получим На рис. 3 показан BDD G(B(X)), полученный из BDD G(^(X, ])) по процедуре 1. 3. Функция обнаружения неисправности Представим функции 9,(X), фДX), i = 1,m , в следующем виде: Ф, (X) = л i (X, f (X)) = п, (X ,1) • f (X) V л i (X ,0) • f (X) = ф1 (X) • f (X) Vф0( X) • f (X), ф (X) = ъ, (X, f (X)) = ч (X ,1) • f (X) V ^ (X ,0) • f (X) = ф1( X) • f (X) Vф0( X) • f (X). (13) (14) Рассмотрим неисправность константа 1 и функцию D)( X) обнаружения константной неисправности 1 на ,-м выходе, , = 1, m . Подставим формулы (13) и (14) в (2), получим D)(X) = ф, (X) © ф} (X) = ф, (X) • ф1 (X) v^. (X) • ф} (X) = = (ф1 (X) • f (X) v ф0( X) • f (X ))^ф!( X) v v (ф!( X) • f (X) v ф0( X) • f(X ))• q>1(X) = (15) = Ф0 (X) • ф1 (X) • f (X) v ф0 (X) • ф1 (X) • f (X) = = (ф0( X) 9ф! (X) )• f (X). Аналогичными преобразованиями получим формулу для неисправности константа 0: D0(X) = ф, (X) 0 ф0(X) = (ф0 (X) 0 ф1 (X))• f (X). (16) Имея ввиду формулы (15) и (16), запишем общую формулу для неисправности константа а, ае{0, 1}: Da (X) = (ф0( X) 0ф1 (X ))• fа (X), где f 1( X) = f (X), а f 0(X) = f(X). Функция обнаружения неисправности для многовыходной схемы принимает вид Da (X) = Da (X) v Da (X) v... v Da (X) = = ((ф1( X) 0ф0( X)) v ( ф2 (X) 0ф2( X) )v... v(фa (X) 0фа (X) ))• f a (X). Согласно формуле (3) выражение в скобках соответствует функции наблюдаемости B(X), а согласно формуле (5) fa (X) - это функция а -управляемости Ca (X). Следовательно, Da (X) = B( X) • Ca (X). (17) Таким образом, функция обнаружения неисправности константа 1 есть произведение функции наблюдаемости и функции 0-управляемости, а функция обнаружения неисправности константа 0 есть произведение функции наблюдаемости и функции 1-управляемости. Формула (17) позволяет выделить общую часть при получении функций обнаружения неисправностей константа 1 и константа 0. Согласно формуле (17) ОДНФ или BDD представления функции обнаружения неисправности a Da(X) можно получить как произведение ОДНФ или BDD представлений, соответственно, функции наблюдаемости B(X) и функции a -управляемости Ca (X). Напомним, что произведение двух ОДНФ есть также ОДНФ. Эффективные методы получения ОДНФ и BDD представлений для функции наблюдаемости B(X) описаны выше. ОДНФ и BDD представления для функции Ca (X) можно получить по структурному описанию схемы, имея ввиду, что C1(X) - это функция, реализуемая выходом подсхемы, соответствующей полюсу v, а C0(X) - функция, реализуемая этой подсхемой, к выходу которой добавлен инвертор. Отметим, что при решении некоторых задач можно не находить полное произведение, а ограничиться частичным произведением формул для функций B(X) и Ca (X). Например, при поиске одного тестового набора. Формула (17) соответствует результату, полученному в работе [5], где показано, что тестовые наборы для константной неисправности 1(0) являются решениями системы из двух уравнений: fX) = 0(1) и B(X) = 1. В работе [5] функция B(X) рассматривается как булева производная функции цХ, v) по переменной v. Здесь мы записали формулу (17) в терминах данной работы для многовыходной схемы. В работе [1] отмечается, что метод построения тестов, предложенный в работе [5], не широко используется из-за трудоемкости построения булевой производной. В данной работе предложены методы, позволяющие сократить трудоемкость построения функции B(X). Заключение В данной работе исследуются функции обнаружения константной неисправности, управляемости и наблюдаемости для полюса элемента комбинационной схемы. Разработаны эффективные методы получения функции наблюдаемости в виде ОДНФ и BDD. Предложенная формула для получения ОДНФ функции наблюдаемости позволяет приблизительно в 4 раза сократить объем вычислений по сравнению с получением ОДНФ по исходной формуле (3). Сложность получения BDD для функции наблюдаемости предложенным в работе методом сопоставима со сложностью построения BDD для подсхемы исходной схемы, в которой рассматриваемому полюсу сопоставлена входная переменная. ОДНФ и BDD представления функции обнаружения константной неисправности а, ае{1, 0}, предлагается получать как произведение ОДНФ и BDD соответственно функции наблюдаемости и функции а -управляемости. Использование этой формулы позволяет выделить общую часть при получении функций обнаружения неисправностей константа 1 и константа 0. При решении некоторых задач достаточно выполнить лишь частичное произведение формул, представляющих две функции. Выполненные исследования позволяют решить совместно ряд задач, связанных с константной неисправностью на полюсе элемента схемы. Так, например, ОДНФ и BDD функции обнаружения неисправности представляют множество всех тестовых наборов для данной константной неисправности. Построив ОДНФ или BDD рассмотренных функций легко вычислить меры тестопригодности: вероятность обнаружения неисправности, управляемость и наблюдаемость.

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