False path diagnosis.pdf С ростом уровня интеграции схем, работающих на высоких частотах и принизких напряжениях питания, возникает необходимость в тестировании неис-правностей задержек путей [1]. Различают робастные и неробастные неисправно-сти задержек путей. Противоположным перепадам значений сигналов на рассмат-риваемом пути в общем случае сопоставляются различные задержки. Каждая изних обнаруживается специальной парой тестовых наборов. Если для каждого изперепадов пути отсутствует тестовая пара, на которой неисправность проявляетсякак неробастная, то путь считается ложным, то есть на этом пути отсутствуют ус-ловия проявления одиночной неисправности задержки пути. Такие пути жела-тельно исключать из рассмотрения при вычислении задержек сигналов в схеме сцелью определения допустимой тестовых пар для неробастных неисправностейрассматриваемого пути. С этой целью используется пятизначный алфавит [2]. Вработе [3] неисправности задержек путей сведены к кратковременным неисправ-ностям литер ЭНФ. На основе анализа ЭНФ сформулированы условия, при кото-рых неисправность задержки пути проявляется как неробастная. Одним из такихусловий является существование тестового набора для соответствующего пути иперепадам значений сигналов константной неисправности литеры ЭНФ. Это зна-чит, что при отыскании ложных путей можно ограничиться проверкой существо-вания тестовых наборов для константных 0 и 1 неисправностей соответствующегопути литеры ЭНФ и противоположных перепадов значений сигналов пути. Про-тивоположным перепадам значений сигналов пути соответствуют противополож-ные константные неисправности одной и той же литеры ЭНФ. При таком подходеотпадает необходимость в использовании пятизначного алфавита. Однако исполь-зование ЭНФ при решении практических задач, как правило, требует большогообъема памяти и потому непригодно. Предлагается компактное представлениеЭНФ в виде И, ИЛИ-дерева. Построение тестовых наборов для рассматриваемыхнеисправностей сводится к решению булевых уравнений на И, ИЛИ-деревьях.В разделе 1 выявляется соответствие между неисправностями задержек путейи неисправностями литер ЭНФ. В разделе 2 вводится понятие упрощенной ЭНФ ирассматривается ее представление в виде И, ИЛИ-дерева. В разделе 3 приводятсяалгоритмы поиска тестовых наборов для неисправностей литер ЭНФ, основанныена использовании И, ИЛИ-деревьев.1. Неисправности задержек путей и константные неисправности ЭНФПуть в схеме представляет собой цепочку элементов схемы, в которой выходпредшествующего элемента является входом последующего элемента. Один извходов первого элемента цепочки является входом схемы и началом пути, а выходпоследнего элемента цепочки является выходом схемы.Будем рассматривать ЭНФ Армстронга, полученную из комбинационной схе-мы описанным в работе [4] способом. В ней переменные отмечены последова-тельностями индексов, представляющими путь в схеме. Переменная вместе сознаком инверсии и последовательностью индексов называется литерой ЭНФ. Од-на и та же литера может присутствовать в различных конъюнкциях ЭНФ. В однойи той же конъюнкции одинаковые переменные могут встречаться лишь с различ-ными последовательностями индексов, то есть в конъюнкции все литеры различ-ны. Литеры, отличающиеся только знаками инверсий над переменными, будемназывать инверсными литерами. Переменные, отличающиеся только знаками ин-версии без учета приписываемых им последовательностей индексов, будем назы-вать инверсными переменными. В ЭНФ могут встречаться инверсные перемен-ные, но не инверсные литеры. Например, для комбинационной схемы, изобра-жённой на рис. 1, имеем следующую ЭНФ Армстронга:1459 59 59 59 23459 3459 59 14689 789 234689 14689 234689 78914689 789 34689 14689 34689 789.a b e b c d e a b c a c da b d a d d    abcdeРис. 1. Комбинационная схемаРаспространим отношения поглощения и пересечения конъюнкций ДНФ наконъюнкции ЭНФ естественным образом. Конъюнкцию будем называть пустой,если в ней встречается хотя бы одна пара взаимно инверсных переменных. Такимпеременным в одной и той же конъюнкции ЭНФ сопоставляются различные по-следовательности индексов.Рассмотрим непустые конъюнкции ЭНФ. Каждая из конъюнкций после удале-ния из ее литер последовательностей индексов, а затем исключения повторяю-щихся переменных превращается в элементарную конъюнкцию. Дизъюнкция раз-личных элементарных конъюнкций образует ДНФ функции f. Будем говорить, чтоЭНФ представляет функцию f. Непустые конъюнкции ЭНФ являются импликан-тами функции f.Тестовый набор, как известно, обеспечивает распространение смены значениясигнала в присутствии неисправности от места ее возникновения до выхода схе-мы. В нашем случае - входа схемы вдоль пути, представляемого литерой ЭНФ[4].Пусть K конъюнкция ЭНФ, она может быть пустой. Будем говорить, что Kрасширяема по литере xiƒ, если выбрасывание из нее этой литеры приводит к об-разованию непустой конъюнкции K*, являющейся импликантой функции f. Иначеона не расширяема по этой литере.Будем рассматривать K* как результат склеивания по литере xiƒ конъюнкций Kи K , в том числе и для пустой конъюнкции K. Здесь K получается из K заменойлитеры xiƒ на инверсную литеру. Будем называть K дополнением K по литере xiƒили просто дополнением K.Рассмотрим сначала неисправность константа 1 литеры ЭНФ. При этой неис-правности во всех конъюнкциях, содержащих литеру, сопоставляемую рассмат-риваемому пути, эта литера заменяется константой 1. В дальнейшем будем назы-вать ее bp-неисправностью. Выберем путь ƒ и литеру xiƒ.Обозначим через K множество конъюнкций, не содержащих литеру xiƒ. Разде-лим конъюнкции, содержащие литеру xiƒ, на конъюнкции с повторяющимися пе-ременными xi (переменными с тем же знаком инверсии, но с отличными от ƒ по-следовательностями индексов) и конъюнкции без повторяющихся переменных.Конъюнкции первого множества не меняют функции, представляемой ЭНФ, вприсутствии bp-неисправности литеры xiƒ и, следовательно, не могут порождатьтестовых наборов. Обозначим конъюнкции первого множества Krxi. Оставшиесяконъюнкции обозначим Кsxi. Будем иметь в виду, что множество Кsxi содержит какпустые, так и непустые конъюнкции. Пустой конъюнкцией будем называть конъ-юнкцию, содержащую хотя бы одну пару взаимно инверсных переменных. Мно-жество наборов, на которых она обращается в единицу, пусто.1. Пусть K - непустая конъюнкция из Ksxi. Если K не расширяемая по литере xiƒконъюнкция, то замена в ней этой литеры константой 1 гарантирует существова-ние тестового набора, обнаруживающего рассматриваемую неисправность, таккак конъюнкция K пересекается с областью нулевых значений функции f. Тесто-вый набор vb обращает в ноль все конъюнкции исправной ЭНФ и в единицу конъ-юнкцию K и, следовательно, конъюнкцию K*, возможно вместе с другими конъ-юнкциями, полученными при выбрасывании литеры xiƒ исправной ЭНФ.Если K из Ksxi расширяема по xiƒ, то не существует тестового набора, обнару-живающего расширение рассматриваемой конъюнкции. Следовательно, такаяконъюнкция не порождает набора vb.2. Рассмотрим пустую конъюнкцию K из Ksxi. Если она не содержит перемен-ной xi , то замена в ней литеры xiƒ константой 1 не меняет функции, представляе-мой ЭНФ (полученная конъюнкция K* остается пустой). Такая конъюнкция непорождает тестового набора для рассматриваемой неисправности.Если конъюнкция K содержит переменную xi , возможно, повторяющуюся, ине имеет пар других взаимно инверсных переменных, тогда bp-неисправностьпревращает K в непустую конъюнкцию K*. Заметим, что в этом случае конъюнк-цию K* также можно рассматривать как результат простого склеивания конъюнк-ций K и K по литере xiƒ, причем K является непустой конъюнкцией.Если непустая конъюнкция K* не есть импликанта функции f, то существуеттестовый набор, обнаруживающий рассматриваемую неисправность. На тестовомнаборе конъюнкция K обращается в единицу. Тестовый набор vb обращает ис-правную ЭНФ в ноль, а неисправную ЭНФ, ее конъюнкцию K*, - в единицу, воз-можно, вместе с другими конъюнкциями, полученными из исправной ЭНФ вы-брасыванием литеры xiƒ.Итак, в обеих рассматриваемых ситуациях набор vb обращает в единицу конъ-юнкцию K* неисправной ЭНФ и в ноль - исправную ЭНФ.Из приведенных рассуждений следует, что тестовые наборы для bp-неисправности могут порождаться либо непустыми конъюнкциями исправнойЭНФ, содержащими рассматриваемую литеру, и не содержащими повторяющихсяпеременных xi, либо пустыми конъюнкциями, содержащими рассматриваемуюлитеру и инверсную переменную xi, при условии, что в конъюнкции присутствуетединственная пара взаимно инверсных переменных. Заметим, что в рассматри-ваемых конъюнкциях, пустых и непустых, переменные, отличные от xi, могут по-вторяться.Теперь перейдем к рассмотрению ap-неисправности. Она приводит к исчезно-вению из ЭНФ непустых и пустых конъюнкций, содержащих литеру xiƒ.Множество конъюнкций K сохраняется в неисправной ЭНФ. Конъюнкции, со-держащие литеру xiƒ, разделим на два подмножества: Kexi-подмножество пустыхконъюнкций и Knexi-подмножество непустых конъюнкций. Конъюнкции первогоподмножества не меняют функции f при исчезновении. Нас будут интересоватьконъюнкции второго подмножества.В присутствии рассматриваемой неисправности все конъюнкции, содержащиеxiƒ, исчезают из ЭНФ. Если это приводит к искажению функции f (сокращениюобласти ее единичных значений), то существует тестовый набор va, обнаружи-вающий рассматриваемую неисправность. На нем исправная ЭНФ принимаетзначение единица за счет обращения в единицу некоторого подмножества конъ-юнкций, содержащих литеру xiƒ, неисправная - значение ноль. Итак, набор va об-ращает в единицу некоторое подмножество Knexi непустых конъюнкций ЭНФ. Изприведенных рассуждений следует, что тестовые наборы для ap-неисправностимогут порождаться непустыми конъюнкциями, содержащими xiƒ .2. Представление упрощенной ЭНФ И, ИЛИ-деревомВ работе [5] показано, что все пути схемы представляются размеченнымИ, ИЛИ-деревом, причем каждой концевой вершине дерева сопоставляется един-ственный путь в схеме. Между размеченным деревом и ЭНФ имеет место взаимнооднозначное соответствие. Для отыскания тестовых наборов, об-наруживающих ap(bp) неисправность, нет необходимости исполь-зовать размеченное дерево, достаточно использовать не разме-ченное И, ИЛИ-дерево, предложенное в работе [6].Листья И, ИЛИ-дерева сопоставляются переменным, возмож-но, со знаком инверсии. Внутренние вершины отмечены симво-лом (). Если корень дерева (вершина нулевого яруса) отмеченсимволом (), то вершины первого яруса отмечены символом(), вершины второго яруса символом () и т.д. Пример та-кого дерева приведен на рис. 2.Неразмеченное дерево представляет формулу над множеством {,,¬}.В ней все символы инверсии опущены со скобок на переменные. Дерево на рис. 2представляет формулу a(bc)d. Будем иметь в виду, что любая формула буле-вой алгебры и любая одновыходная комбинационная схема может быть приведенак И, ИЛИ-дереву такого вида. Построим И, ИЛИ-дерево для схемы (рис. 3).abc12 34Рис. 3. Комбинационная схемаПеречислим все пути схемы: а,1,4; b,1,4; a,1,2,3,4; b,1,2,3,4; c,3,4. Пронумеру-ем пути числами от 1 до 5. Заменим в ЭНФ этой схемы последовательности ин-дексов номерами путей, им сопоставляемым. Назовем полученную ЭНФ упро-щенной ЭНФ. Заметим, что упрощенная ЭНФ отличается от обычной ЭНФ толькотем, что в ней не конкретизируются элементы схемы, через которые проходит тотили иной путь. Для рассматриваемой схемы упрощенная ЭНФ имеет видa1b2a3b4c5.Упрощенная ЭНФ может использоваться так же, как и обычная ЭНФ, для по-строения тестовых наборов, обнаруживающих ap,bp-неисправности. Однако онатакже оказывается чрезвычайно громоздкой для реальных схем. Поэтому тесто-вые наборы будем искать по И, ИЛИ-дереву, являющемуся компактным пред-ставлением упрощенной ЭНФ.Покажем, что И, ИЛИ-дерево сохраняет упрощенную ЭНФ. Для построенияИ, ИЛИ-дерева по схеме выполним следующую последовательность шагов.1. Исключим все ветвления, двигаясь от выхода схемы к входам, повторяя со-ответствующие точке ветвления подсхемы столько раз, какова степень ветвления.Эта операция сохраняет упрощенную ЭНФ, поскольку сохраняет пути в схеме.Для нашего примера имеем (рис. 4)ababc11 2 34Рис. 4. Комбинационная схема без ветвлений2. Исключим каждый элемент НЕ в схеме, заменив выход питающего его эле-мента или входной символ на инверсный (рис. 5). Опустим инверсии элементовНЕ И, НЕ ИЛИ на входы схемы или на выходы других элементов, двигаясь от вы-ходов к входам схемы, изменяя, если это необходимо, типы элементов (рис. 5).В результате получим схему, состоящую только из элементов И, ИЛИ; причеминверсии останутся лишь над входными переменными схемы. Эта операция со-храняет упрощенную ЭНФ, поскольку сохраняет пути в схеме, при этом на неко-торых путях образующие их элементы изменяются.abcab112 34Рис. 5. Комбинационная схема, не содержащаяэлементов НЕ, НЕ И, НЕ ИЛИ3. Каждую подсхему, состоящую только из элементов ИЛИ (И), заменим един-ственной вершиной () с числом исходящих ребер, равным числу путей в под-схеме. В результате получим И, ИЛИ-дерево (рис. 6). Эта операция сохраняет уп-рощенную ЭНФ, поскольку сохраняет пути в схеме.Итак, далее тестовые наборы будем искать поИ, ИЛИ-дереву, являющемуся компактным пред-ставлением упрощенной ЭНФ.Выделим в И, ИЛИ-дереве существенное под-дерево [6] следующим образом. Двигаемся откорня дерева к листьям. Корень включаем в суще-ственное поддерево. Если очередная включаемаявершина отмечена символом (), то в поддере-во включается одно (все) инцидентное ребро, со-единяющее ее с вершиной следующего по поряд-ку яруса вместе с вершинами этого яруса. Действуем таким образом, пока не дос-тигнем концевых вершин (листьев) И, ИЛИ-дерева. В нашем примере одно из су-щественных поддеревьев отмечено пунктиром, два других являются одноребер-ными деревьями. Будем иметь в виду, что существенным поддеревьям сопостав-ляются конъюнкции упрощенной ЭНФ, составленные из литер, отмечающих кон-цевые вершины существенного поддерева.И, ИЛИ-дерево будем называть однородным по переменной xi,( xi ), если ниодна концевая вершина дерева не отмечена переменной xi ,(xi). Дерево на рис. 6является однородным по переменной c.3. Построение тестовых наборов по И, ИЛИ-деревуПостроение тестового набора для bp-неисправности. Выбираем лист, соот-ветствующий рассматриваемому пути и отмеченный литерой xin. Здесь n - номерпути. Будем перебирать существенные поддеревья, содержащие литеру рассмат-риваемого пути. В работе [6] предложен алгоритм сокращенного перебора суще-ственных поддеревьев, основанный на построении существенных поддеревьевпри движении к корню, начиная от листьев И, ИЛИ-дерева, и выбрасывании сово-купностей существенных поддеревьев, порождающих пустые конъюнкции. Вос-aba cb12345Рис. 6. И, ИЛИ-деревопользуемся этим алгоритмом, выбрасывая совокупности конъюнкций, содержа-щие наряду с литерой xin литеры xim для m не равно n, и пустые конъюнкции, по-лученные за счёт переменных, отличных от xi.Выбираем очередную конъюнкцию, не содержащую повторяющихся перемен-ных для литеры xin.Для найденной непустой конъюнкции K находим дополнение K , заменив пе-ременную xi на инверсную. В пустой конъюнкции вычеркиваем переменную xi (вполученной конъюнкции остается xi ), для того чтобы получить дополнение K .Фиксируем в И, ИЛИ-дереве константами переменные, присутствующие в до-полнении K . В полученном в результате фиксирования дереве G требуется найтинабор, обращающий его в ноль. Поcтроим И, ИЛИ-дерево G , заменив в G всеоперации на двойственные, а все переменные на инверсные [6].Найдем один (любой) корень уравнения G = 1 методом, описанным в [6], ис-пользуя для сокращения перебора свойство однородности дерева по переменной.Представим корень в виде конъюнкции K'.Логическое произведение K K' представляет тестовый набор, обнаруживаю-щий bp-неисправность.Построение тестового набора для ap-неисправности. Перебираем сущест-венные поддеревья, содержащие литеру, сопоставляемую выбранному пути, непорождающие пустых конъюнкций, воспользовавшись уже упомянутым алгорит-мом, изложенным в [6]. Найденную конъюнкцию K используем далее для отыска-ния тестового набора. Мы должны исключить из ЭНФ конъюнкции, содержащиелитеру, сопоставляемую выбранному пути. Для этого в И, ИЛИ-дереве достаточноприписать значение ноль концевой вершине, сопоставляемой выбранному пути.Далее фиксируем переменные, присутствующие в K. Получаем дерево G. Строимдерево G и находим корень уравнения. Представляем корень конъюнкцией K'.Тогда логическое произведение KK' задает тестовый набор для ap-неисправности.Рассмотрим пример. Вернемся к схеме на рис. 1. Построим для нее И, ИЛИ-де-рево (рис. 7).Рис. 7. Дерево упрощенной ЭНФПронумеруем его концевые вершины слева направо от 1 до 10. Тогда имеемследующую упрощенную ЭНФ:a3b2e1b2c4d5e1a6b10c7 a6c7d9 a6b10d8 a6d8d9 .Рассмотрим в ней путь, сопоставляемый литере d8 . Эта литера содержится вдвух существенных поддеревьях, которым сопоставляются последняя и предпо-следняя конъюнкции упрощенной ЭНФ.Рассмотрим bp-неисправность выбранной литеры. Это значит, что d8 обраща-ется в единицу. Эту литеру содержит единственная конъюнкция K = a6b10d8 безповторяющихся переменных, представленная соответствующим порождающимдеревом на рис.7. Тестовый набор обращает дополнение K , K = a6b10d8 в едини-цу, а конъюнкции исправной ЭНФ - в ноль. Зафиксируем константами, опреде-ляемыми конъюнкцией K , переменные в полученном дереве, не обращая внима-ния на сопоставляемые переменным пути (индексы). Результат фиксированийпредставлен деревом на рис. 8.Рис. 8. Фиксирование переменных в дереведля bp-неисправностиЕсли выполнить далее преобразования над деревом, введенные в [6], соответ-ствующие элементарным тождествам булевой алгебры, получим дерево G(рис. 9), состоящее из одного ребра; набор 10010 является тестом для рассматри-ваемой неисправности.Рассмотрим ap-неисправность выбранной литеры. Это зна-чит, что d8 обращается в ноль. K = a6b10d8. Тестовый наборобращает K в единицу, возможно, вместе с другими конъюнк-циями, содержащими неисправную литеру, а остальные конъ-юнкции исправной ЭНФ должны обращаться в ноль. Осталь-ные конъюнкции представляются деревом, в котором d8 = 0 .Зафиксируем константами, определяемыми конъюнкцией K, переменные в полу-ченном дереве, не обращая внимания на сопоставляемые переменным пути (ин-дексы). Результат всех фиксирований представлен деревом на рис. 10.Рис. 10. Фиксирование переменных в дереведля ap -неисправностиЕсли выполнить далее преобразования над деревом, введенные в [6], соответ-ствующие элементарным тождествам булевой алгебры, получим дерево G, совпа-дающее с деревом на рис. 9.Представляемая деревом булева функция обращается в 0 при c = 0. Следова-тельно, булев вектор 10000 представляет тестовый набор, обнаруживающий рас-сматриваемую ap-неисправность.Итак, если для рассматриваемой литеры не существует тестовых наборов,обнаруживающих bp, ap неисправности, то сопоставляемый литере путь являет-ся ложным и не влияет на задержки в схеме.ЗаключениеВ работе предложен подход к нахождению ложных путей, основанный на по-иске тестовых наборов для константных неисправностей литер ЭНФ. Поиск тес-товых наборов сводится к отысканию корней булевых уравнений на И, ИЛИ-деревьях и не требует использования пятизначного алфавита, как при традицион-ном подходе. Если для рассматриваемой литеры не существует тестовых наборов,обнаруживающих неисправности bp, ap, то сопоставляемый литере путь являетсяложным и не влияет на задержки в схеме. Предлагаемый в работе метод можетбыть расширен на системы И, ИЛИ-деревьев, описывающих схемы произвольнойсложности. Каждое И, ИЛИ-дерево строится до ближайшей точки ветвления. Ка-ждая точка ветвления объявляется корнем следующего И, ИЛИ-дерева и т.д.

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