Test patterns generation for single stuckat faultsof arbitrary elements of a combinational circuit with using description of elements functions.pdf Графическое представление логических схем широко ис-пользуется при решении различных задач их анализа, связан-ных с проблемами диагностики дискретных систем. Этопредставление предполагает, что вершинам графа сопостав-ляются элементы схемы, а дугам − связи между элементами.Оно, как правило, является более компактным по сравнениюс формулами, описывающими системы булевых функций, ре-ализуемые комбинационной схемой или комбинационной ча-стью последовательностной схемы.Следует, однако, иметь в виду, что аналитическое пред-ставление булевых функций зачастую ориентировано на та-кие формулы, которые в явном виде несут информацию освойствах функции: ее единичных наборах (ДНФ), нулевыхнаборах (КНФ), однородности по переменным (произвольныеформулы над множеством { ¬, ,  } булевых функций, вкоторых инверсии опущены со скобок на переменные и т.д.Графическое представление логических схем такой инфор-мации в явном виде не содержит.ROBDD-графы (Reduced Ordered Binary Decision Diagram),предложены R.E. Bryant в 1986 г. [1]. Они, в отличии от тра-диционных графических представлений логических схем сво-ими путями (простыми цепями), соединяющими корень гра-фа с 1(0)-концевой вершиной, представляют единичные (ну-левые) наборы булевой функции, однако не содержат инфор-мации о структуре схемы, реализующей эту функцию.В задачах анализа логических схем (моделирование, по-строение проверяющих и диагностических тестов для неис-правностей логических элементов схем, вычисление оценокуправляемости и наблюдаемости и др.) необходима как ин-формация о структуре схемы, так и о единичных и нулевыхнаборах реализуемых ею функций. Эта информация содер-жится в альтернативных графах, предложенных Р.Р. Убаром[2]. Альтернативные графы в последующих работах Р.Р. Уба-ра и его коллег были названы SSBDD-графами (StructurallySynthesized BDD). Успешное их применение в задачах диаг-ностики объясняется, с одной стороны, тем, что они являютсяносителями информации как о структуре схемы, реализующейсистемуной функция обращается в константу 1(0), то вершина, вкоторую заходит дуга, соответствующая функции, объявля-ется 1(0)-концевой вершиной. В ROBDD-графе все 1-кон-цевые вершины объединяются в одну 1-концевую вершинуграфа, также как и все 0-концевые вершины [1]. Вершинаграфа, отмеченная первой по порядку переменной разложе-ния, называется корнем графа. В [1] введены операции, по-зволяющие сократить число вершин в графе. ПостроениеROBDD-графа связано с выбранным заранее для графа вцелом порядком разложения по переменным. При выбран-ном порядке разложения построенный граф оказываетсяединственным для функции, что позволяет использоватьROBDD-графы для верификации дискретных схем. Догово-римся в дальнейшем любой граф, полученный с использова-нием разложения Шеннона и совмещением 1(0)-концевыхвершин, называть просто BDD-графом, если другие особен-ности его построения нас не интересуют.При построении SSBDD-графов [3] применяется много-кратное разложение по переменной элементарных функцийалгебры логики произвольного числа переменных: И, ИЛИ,НЕ И, НЕ ИЛИ, НЕ с целью построения BDD-графа длякаждой из элементарных функций. Причем, наряду с обыч-ным представлением разложения Шеннона фрагментомBDD-графа, предложено использовать модификацию этогопредставления, в которой вершине сопоставляется перемен-ная xi . В этом случае 1-дуга соответствует фиксированиюпеременной xi функции F константой 0, а 0-дуга − констан-той 1 (это следует из формулы (1)).К булевым функциям И, ИЛИ применяется обычноепредставление разложения Шеннона, а к булевым фун-кциям НЕ И, НЕ ИЛИ, НЕ − разложение с использова-нием в качестве меток вершин инверсных переменных,что соответствует опусканию инверсии с функции навходные переменные и замене функции на двойствен-ную:  заменяется на ,  заменяется на . В результа-те каждый элемент комбинационной схемы представ-лен в системе SSBDD-графов либо элементом И, либоэлементом ИЛИ, а инвертор − инверсией переменной,сопоставляемой его входу.Рис. 1. Элементарный BDD-граф для И.h x1x2 ...xn = h x x x x xn xn 1 1 2 ... 1... −1 =   Рис. 2. Элементарныйэлементарной функции представляется 0-путями, соеди-няющими эту же корневую вершину с 0-концевой верши-ной. Всякому пути, проходимому в направлении ориента-ции дуг из корня некоторого элементарного BDD-графа вего 1(0)-концевую вершину сопоставляется конъюнкцияпеременных, отмечающих вершины этого пути. Если дугапомечена константой 1, то входящая в конъюнкцию пе-ременная имеет знак инверсии, совпадающий с меткойвершины, из которой дуга исходит, иначе эта переменнаяимеет противоположный знак инверсии.На рис. 1−5 приведены ОДНФ элементарных буле-вых функций.SSBDD-граф строится путем совмещения элемен-тарных BDD-графов элементов схемы вплоть до точекветвления схемы; точкам ветвления сопоставляютсяновые SSBDD-графы и т.д., пока не построим SSBDD-графы, зависящие только от входных переменных. За-метим, что элемент, выход которого является точкойветвления, в дальнейшем может использоваться как впрямой, так и инверсной форме.Вместо системы SSBDD-графов для одновыходнойкомбинационной схемы будем строить аналогичнымобразом единственный граф, а именно, FSSBDD-граф.Опишем процедуру его построения.Будем считать, что элементы комбинационной схемыпронумерованы в соответствие с разбиением схемы наярусы от выхода к входам схемы. Сопоставим выходамэлементов внутренние переменные. Вершины FSSBDD-графа будем нумеровать в порядке их появления.Начнем с построения элементарного BDD-графадля элемента, корень которого сопоставляется выходусхемы, а затем последовательно заменим внутренниепеременные схемы элементарными BDD-графами.Пусть часть FSSBDD-графа уже построена и представ-ляет собой граф, в котором выделен корень и 1(0)-кон-цевые вершины. В любую вершину графа (кроме кор-невой) в общем случае может заходить несколько дуг.Из любой неконцевой вершины исходит ровно две ду-ги: одна помечена символом 1, другая − символом 0.Каждой ветви точки ветвления, как и в системеSSBDD-графов, сопоставим внутренние переменные,отличающиеся друг от друга индексом, указывающимна номер ветви, а возможно, и знаком инверсии. Внут-ренние переменные с индексами и знаками инверсииотмечают вершины строящегося FSSBDD-графа.Если в уже построенном подграфе нет вершин, по-меченных внутренними переменными, процедура по-строения закончена, и FSSBDD-граф получен.Иначе выбираем очередную вершину, помеченнуювнутренней переменной. Из нее исходит 1-дуга, заходя-щая в вершину построенного графа (обозначим вершинуe1), и 0-дуга, заходящая в другую вершину построенногографа (обозначим вершину e0). В рассматриваемуювершину, помеченную внутренней переменной, в общемслучае может заходить несколько дуг. Строим элемен-тарный BDD-граф для элемента схемы, выход которогосопоставлен этой внутренней переменной.Корень этого элементарного BDD-графа замещаетвершину, отмеченную рассматриваемой внутренней пе-ременной, возможно, с индексом и знаком инверсии. Всевходящие в замещаемую вершину дуги теперь входят вкорневую вершину замещающего элементарного BDD-графа. Совмещаем 1-концевую вершину элементарногоBDD-графа с e1, а его 0-концевую вершину − с e0. Приэтом метка 1(0)-концевой вершины элементарного BDD-графа исключается, метка вершины e1(e0) сохраняется.Такая подстановка выполняется до тех пор, пока всевершины, помеченные внутренними переменными, небудут исчерпаны. В результате получим FSSBDD-графсхемы.Рис. 7. Процесс получения FSSBDD-графаНа рис. 6 приведена комбинационная схема, а нарис. 7 представлены этапы получения для этой схемыFSSBDD-графа. При каждом замещении вершины, от-меченной внутренней переменной, возможно, с индек-сом и знаком инверсии, этой переменной сопоставляет-ся номер вершины в строящемся FSSBDD-графе, яв-ляющейся корнем подставляемого элементарногоBDD-графа, и номера вершин строящегося FSSBDD-графа, совмещаемые с 1(0)-концевыми вершинами это-го BDD-графа. Последние номера снабжены индекса-ми, указывающими на тип концевых вершин. Если1(0)-концевая вершина подставляемого BDD-графасовпадает с 1(0)-концевой вершиной FSSBDD-графа(это одна и та же вершина для строящихся FSSBDD-графов и окончательного FSSBDD-графа), то номервершины FSSBDD-графа не указывается. Соответст-вующий список номеров приведен на рис. 7.1.2. Получение ОДНФдля комбинационной схемы и ее подсхемКонъюнкцию будем называть пустой, если в нейпеременная и ее инверсия присутствуют одновременно.Конъюнкцию будем называть неэлементарной, еслиона пустая или содержит несколько переменных с од-ним и тем же знаком инверсии, иначе конъюнкция счи-тается элементарной.В ROBDD-графе любой простой цепи, соединяющейкорень графа с его 1(0)-концевой вершиной, сопоставля-ется элементарная конъюнкция. Аналогичная конъюнк-ция в FSSBDD-графе может быть неэлементарной.Обозначим через Д(f) дизъюнкцию попарно ортого-нальных, не обязательно элементарных, конъюнкций од-новыходной комбинационной схемы, полученную в ре-зультате подстановки вместо внутренних переменных(например, при движении от выхода схемы к ее входам)ОДНФ элементов И, ИЛИ, НЕ И, НЕ ИЛИ, НЕ (они при-ведены на рис. 1−5) от входных переменных элементов ипоследующего раскрытия скобок. Выбрасывание пустыхконъюнкций, повторяющихся букв в непустых конъюнк-циях, поглощения и склеивания конъюнкций не допуска-ются. Такая подстановка гарантирует попарную ортого-нальность конъюнкций, не обязательно элементарных.Аналогичным образом может быть получена Д ( f )для инверсной схемы, в ней элемент, выход которого яв-ляется выходом схемы, заменен инверсным элементом. В[4] доказано, что множество 1(0)-путей FSSBDD-графапредставляет Д ( f ) Д ( f ) .Каждому 1(0)-пути FSSBDD-графа сопоставляетсяконъюнкция входных переменных. Если в конъюнкциивстречаются взаимно инверсные переменные, то такойпуть будем называть противоречивым, то есть противоре-чивый путь представляет пустую конъюнкцию. Любуюнепустую конъюнкцию можно привести к элементарной,исключив повторение одинаковых букв. Это значит, чтоиз Д ( f ) Д ( f ) можно получить (ОДНФ) функции(ОДНФ инверсии функции), исключив пустые конъюнк-ции и повторяющиеся буквы в непустых конъюнкциях сцелью превращения последних в элементарные конъюнк-ции. Обозначим ОДНФ через Д ( f ) Д ( f ) .FSSBDD-граф содержит также ОДНФ и ее инвер-сию для любой подсхемы, выход которой сопоставля-ется выходу некоторого элемента схемы, а входы −входным переменным рассматриваемой схемы [4].Выясним, как найти ОДНФ (ее инверсию) для подсхемы.Подсхеме (будем называть ее ν-подсхемой) в общемслучае может быть сопоставлено в FSSBDD-графе не-сколько подграфов, корни которых сопоставлены симво-лу одной и той же внутренней переменной ν, возможно, сразличными индексами и знаками инверсии. Обозначимсимволом H функцию, реализуемую ν-подсхемой, а черезH − инверсию этой функции. Каждый из подграфов за-дается номером вершины FSSBDD-графа, сопоставлен-ной переменной ν и являющейся корнем выделяемогоподграфа, и номерами вершин FSSBDD-графа, сопостав-ленными 1,0-концевым вершинам этого подграфа. Непро-тиворечивые пути (простые цепи), соединяющие кореньвыделяемого подграфа с его 1(0)-концевой вершиной,представляют функцию H(H) в виде ОДНФ. Номеравершин, сопоставляемых корню подграфа и его 1,0-кон-цевым вершинам были найдены при подстановке элемен-тарного BDD-графа вместо вершины, отмеченной пере-менной ν с соответствующим индексом и знаком инвер-сии. При дальнейших подстановках с целью замены дру-гих внутренних переменных элементарного BDD-графаэти вершины стали корнем и 1,0-концевыми вершинамиподграфа, представляющего рассматриваемую подсхему.Назовем выделенный подграф ν-подграфом.На рис. 7, например, подсхеме, выходом которойявляется выход элемента 6 комбинационной схемы,представленной на рис. 6, сопоставляется два подгра-фа. Корнем одного из подграфов является вершина 3FSSBDD-графа, 1-концевая вершина подграфа совпа-дает с 1-концевой вершиной FSSBDD-графа, а 0-кон-цевая вершина подграфа есть вершина 2 FSSBDD-графа. Пути, ведущие из 3 в 1-концевую вершинуFSSBDD-графа, представляют функцию H, реализуе-мую ν-подсхемой, в виде дизъюнкции соответствую-щих путям конъюнкций: a  acd , а пути из вершины 3в вершину 2 − инверсию этой функции: ac  acd . Кор-нем другого подграфа является вершина 2 FSSBDD-графа, его 1-концевая вершина есть вершина 4FSSBDD-графа, а его 0-концевая вершина совпадает с0-концевой вершиной FSSBDD-графа. Будем иметьввиду, что ν-подграфы, сопоставляемые внутреннейпеременной, возможно, с разными индексами, но од-ним и тем же знаком инверсии, изоморфны.2. ПОСТРОЕНИЕ ТЕСТОВ ДЛЯ ОДИНОЧНЫХ КОНСТАНТНЫХ НЕИСПРАВНОСТЕЙПОЛЮСОВ ЭЛЕМЕНТОВ КОМБИНАЦИОННОЙ СХЕМЫВ работе [6] предложен метод построения тестов дляодиночных константных неисправностей полюсов элемен-тов комбинационной схемы, основанный на использованииОДНФ, описывающих поведение фрагментов схемы.Пусть не исправен выход элемента схемы, сопостав-ляемый переменной ν (выход элемента может быть точкойветвления). Задана неисправность константа 0. Необходи-мо найти набор значений входных переменных схемы (тес-товый набор), обнаруживающий эту неисправность.Для этого построим [6] ОДНФ для подсхемы, выхо-дом которой является выход схемы, а входами − полюс,сопоставляемый выходу рассматриваемого элемента иобозначенный переменной ν, и входы схемы. Обозначимее Д0 (G). Разделим конъюнкции ОДНФ на три подмно-жества [6], задав ее в виде 0( ) (2) ƒ ƒ Д G = K  K  K .Здесь ОДНФ K представляет конъюнкции, не содер-жащие переменной ν, ОДНФ ƒ K представляет конъ-юнкции, содержащие переменную ν, ОДНФ ƒ K пред-ставляет конъюнкции, содержащие переменную ƒ . ЭтиОДНФ попарно ортогональны между собой.Обозначим через *ƒ K OДНФ, полученную из ƒ Kвычеркиванием переменной ν. Аналогичным образомполучим ОДНФ *ƒ K . Пусть Д0(H) есть ОДНФ функ-ции, реализуемые подсхемой, выход которой сопостав-лен переменной ν, (подсхеме сопоставляется ν-подграфв FSSBDD-графе [4] ), а Д 0(H) − ОДНФ инверсииэтой функции. Напомним, что рассматриваемые ОДНФзависят от входных переменных схемы. В [6] доказано,что набор значений входных переменных является тес-товым для константной неисправности 0, если и толькоесли он обращает в единицу выражение K* & Д 0(H) ƒ ив нуль выражение *ƒ K .Любую часть пути в графе будем называть отрезкомпути. Отрезки не противоречивы, если сопоставляемыеим непустые конъюнкции образуют при перемножениинепустую конъюнкцию.Приведенные ниже теоремы относятся к фрагмен-там упомянутых в них ОДНФ, связанных с одним и темже ν-подграфом [4].Теорема 1. Конъюнкция из *ƒ K представляется дву-мя непротиворечивыми отрезками пути FSSBDD-гра-фа. Первый из них начинается в корне графа и закан-чивается в корневой вершине рассматриваемого v-под-графа, сопоставляемой переменной v(ƒ ), а второй на-начинается в 1(0)-концевой вершине этого v-подграфаи заканчивается в 1-концевой вершине FSSBDD-графа.Доказательство. Из построения FSSBDD v-графа следу-ет, что рассматриваемая конъюнкция получается вычерки-ванием переменной v из конъюнкции, представляемой не-пустым 1-путем этого графа, проходящим через полюс,помеченный переменной v(ƒ ) и сопоставляемый рассмат-риваемому v-подграфу, а, возможно, и через полюсы, по-меченные той же переменной и сопоставляемые подчинен-ным v-подграфам. Выделим в нем два отрезка: первый − изкорня до первой вершины, помеченной переменной v(ƒ ),пропускаем 1(0)-дугу этой вершины, что соответствует вы-черкиванию переменной v, и рассматриваем второй отре-зок − из вершины, в которую эта дуга заходит, до 1-кон-цевой вершины FSSBDD v-графа. Если во втором отрезкевстречаются корневые вершины подчиненных v-под-графов, соответствующие им дуги также пропускаем. Пер-вый отрезок начинается в корне FSSBDD-графа и заканчи-вается в вершине, сопоставляемой переменной v(ƒ ) рас-сматриваемого v-подграфа. Второй начинается в 1(0)-кон-цевой вершине этого подграфа и заканчивается в 1-кон-цевой вершине FSSBDD-графа. Теорема доказана.Теорема 2. Конъюнкция из Д0(H) представляетсянепустым 1(0)-путем ƒ -подграфа (из корня подграфа,сопоставляемого в FSSBDD-графе переменнойƒ (ƒ ), в1(0)-концевую вершину этого подграфа).Доказательство. Утверждение теоремы следует изспособа построения ƒ -подграфов. Итак, конъюнкцияОДНФ, представленная выражением K* & Д 0(H) ƒ , за-дается непротиворечивыми отрезками путей FSSBDD-графа, порожденными одним и тем же ƒ -подграфомрассматриваемого фрагмента. С этим же подграфомсвязан непротиворечивый отрезок, обеспечивающийобращение в нуль выражения *ƒ K . Теорема доказана.Теорема 3. Отрезок FSSBDD-графа, соединяющий0(1)-концевую вершину рассматриваемого ƒ -подграфа,сопоставляемого в FSSBDD-графе переменной v(ƒ ), с0-концевой вершиной FSSBDD-графа, представляетконъюнкцию, ортогональную ОДНФ *ƒ K .Доказательство. Фрагмент ОДНФ *ƒ K представля-ется путями из 0(1)-концевой вершины рассматривае-мого подграфа, сопоставляемого в FSSBDD-графе пе-ременной v(ƒ ), в 1-концевую вершину FSSBDD-графа.Каждый непустой путь из 0(1)-концевой вершины под-графа в 0-концевую вершину FSSBDD-графа представ-ляет конъюнкцию, ортогональную всем конъюнкциямэтого фрагмента. Теорема доказана.Непротиворечивые отрезки, определяемые теоремами1−3, вместе представляют конъюнкцию. Обращающий еев единицу набор является тестовым набором для рассмат-риваемой неисправности. Исправная схема на этом набо-ре принимает значение один, а неисправная − нуль. Поисктаких непротиворечивых отрезков связан с перебором,однако, перебор удается сократить, во-первых, за счетрассмотрения условий существования теста для фрагмен-тов формул, а во-вторых, за счет замены перебора формул[6] перебором путей в графе. Для нахождения тестовыхнаборов, обращающих исправную схему в нуль, а неис-правную в единицу, необходимо рассмотреть ОДНФ дляинверсной схемы и переформулировать теоремы 1−3.Представим Д 0(G) в виде 0( ) ' ' ' (3)ƒ ƒ Д G = K  K  K .Здесь ОДНФ ' K , 'ƒ K , 'ƒ K , '*ƒ K , '*ƒ K аналогичны ОДНФK , ƒ K , ƒ K , *ƒ K , *ƒ K . Следовательно, для нахождениятестового набора необходимо обратить в единицу выра-жение K '* & Д 0(H) ƒ и в нуль выражение '*ƒ K .Теорема 4. Конъюнкция из '*ƒ K представляется дву-мя непротиворечивыми отрезками из FSSBDD-графа.Первый из них начинается в корне графа и заканчива-ется в корневой вершине рассматриваемого v-под-графа, сопоставляемого переменной v(ƒ ), а второйначинается в 1(0)-концевой вершине этого подграфа изаканчивается в 0-концевой вершине FSSBDD-графа.Доказательство аналогично доказательству теоремы 1.Теорема 5. Конъюнкция из Д 0(H) представляетсянепустым 0(1)-путем v-подграфа (из корня подграфа,сопоставляемого переменной v (ƒ ) в FSSBDD-графе, вего 0(1)-концевую вершину).Доказательство аналогично доказательству теоремы 2.Теорема 6. Отрезок FSSBDD-графа, соединяющий0(1)-концевую вершину рассматриваемого v-подграфа,сопоставляемую в FSSBDD-графе переменной v(ƒ ), с1-концевой вершиной FSSBDD-графа, представляетконъюнкцию, ортогональную ОДНФ '*ƒ K .Доказательство аналогично доказательству теоремы 2.3. АЛГОРИТМ ПОСТРОЕНИЯ ТЕСТОВОГО НАБОРА ДЛЯ НЕИСПРАВНОСТИ КОНСТАНТА 0НА ПОЛЮСЕ v, СОПОСТАВЛЯЕМОМ ВЫХОДУ ЭЛЕМЕНТА СХЕМЫАлгоритм приводится в предположении, чтоFSSBDD-граф построен.1. Перебираем ближайшие к корню FSSBDD-графаv-подграфы, не обращая внимания на индексы и знакиинверсии переменной v.2. Перебираем пути, определяемые выбранным v-подграфом, с тем чтобы найти непротиворечивые отрезкив соответствии с теоремами 1−3. Непротиворечивые от-резки представляют тестовые наборы для рассматривае-мой неисправности. Если непротиворечивые отрезки най-ти не удается, ищем непротиворечивые отрезки в соот-ветствии с теоремами 4−6 для того же v-подграфа.3. Если все v-подграфы просмотрены, а тестовогонабора найти не удалось, то его для рассматриваемойнеисправности не существует.Для неисправности константа 0 на входном полюсеэлемента схемы определяем индекс переменной v (номерветви точки ветвления), сопоставляемой выходу предше-ствующего элемента, соединенному с рассматриваемымнеисправным входным полюсом. При реализации вышеприведенного алгоритма перебираем только v-подграфы,сопоставляемые переменной с этим индексом.Поиск всех совокупностей непротиворечивых отрезковобеспечивает нахождение всех тестовых наборов для рассмат-риваемой неисправности и представление их в виде ОДНФ.Для неисправности константа 1 поступаем анало-гично предыдущему, обращая в единицу выражениеK* & Д 0(H) ƒ ( K'* & Д 0(H) ƒ ) и в нуль выражение*ƒK ( '*ƒ K ).При построении теста для другой константной не-исправности необходимо в FSSBDD-графе выбрать со-ответствующие неисправному полюсу v-подграфы, азатем воспользоваться описанным выше алгоритмом.4. РЕАЛИЗАЦИЯ АЛГОРИТМАСоставлены две программы, реализующие алгоритми ориентированные на схемы из произвольных логиче-ских элементов. Функция, реализуемая элементом, за-дается либо в виде ДНФ, либо в виде КНФ.Первая программа представляет каждый элемент каксхему из двухвходовых вентилей, а затем строит FSSBDD-граф, в котором каждый вентиль подсхемы заменяется со-ответствующим BDD-графом. Рассматриваются неисправ-ности на полюсах вентилей и строится тестовый набор длянеисправности согласно изложенному выше алгоритму.Результаты испытаний программы на бенч-марке9symml приведены в таблице. К сожалению, для бенч-марки С432, С499, С880, С1355 не удалось построитьFSSBDD-граф из-за его большой размерности.С целью применения алгоритма для более сложных схембыла разработана другая программа. Она представляет каж-дый элемент графа в виде SSBDD-графа. Например, пустьэлемент задан ДНФ x7 x8 x24  x6 x26  x6 x10 x11 . Тогда соот-ветствующий ему граф имеет вид, представленный на рис. 8.Рис. 8. SSBDD-графВторая программа позволяет выполнить сокращенныйобход необходимых путей (простых цепей) FSSBDD-графа без построения этого графа, используя системуSSBDD-графов, соответствующих элементам схемы.Пусть строятся отрезки непротиворечивых путей с цельюнахождения тестового набора. При заходе в вершину,соответствующую некоторому элементу схемы, выясня-ется, проходился ли SSBDD-граф этого элемента при по-строении тестового набора. Если да, то в строящихся от-резках содержится путь из корня SSBDD-графа в одну изего концевых вершин. Последнее означает, что булевойфункции, реализуемой элементом уже приписано значе-ние. Тогда нет необходимости заходить в SSBDD-графрассматриваемого элемента. Достаточно из вершины,сопоставляемой элементу, пойти по соответствующейдуге, определяемой значением функции и типом инвер-сии вершины. Если вершина отмечена переменной безинверсии, то в случае единичного (нулевого) значенияфункции движемся по 1(0)-дуге, исходящей из этой вер-шины. В случае инверсной переменной − по 0(1)-дуге.Если вершина, соответствующая элементу схемы,встречается впервые, то поиск пути продолжается внутриSSBDD-графа, корень которого отожествляется с этойвершиной, до тех пор, пока не встретится концевая верши-на этого графа. Последнее означает приписывание значе-ния функции, реализуемой рассматриваемым элементом.При построении FSSBDD-графа в явном виде мыимеем возможность воспользоваться результатом об-хода только ƒ -подграфа, для которого ищется тесто-вый набор. Прохождение одних и тех же подграфовдругих элементов схемы не учитывается, поскольку этотребует значительных дополнительных ресурсов памя-ти. Следствием этого факта является рост перебора припоиске тестового набора по FSSBDD-графу.Программа 1, составленая Плешковым А.Г., реализуеталгоритм построения тестовых наборов для константныхнеисправностей, используя систему SSBDD-графов. Резуль-таты испытаний представлены в табл. и получены на ПЭВМc 1700 МГц версией процессора AthlonXP и 256Мб памяти.Программа 2 составлена Алимасовым А.С., и реализуеталгоритм построения тестовых наборов для константныхнеисправностей по FSSBDD-графу. Результаты испытанийпредставлены в табл. 1 и получены на ПЭВМ c 150 МГцверсией процессора Pentium 1 и 64Мб памяти.Имя файлаКоличествоэлементовв схемеКоличествовходовКоличе-ствовыходовКоличествообнаруженныхобнаружимыхнеисправностейКоличествообнаруженныхнеобнаружимыхнеисправностейМаксимальноевремя поискатеста длянеобнаружи-мойнеисправностиОбщеевремяпострое-ниятестов9symml(lif/9symml)(пр-ма 2)319 9 1 1142 0 − 185,59symml(lif/9symml)(пр-ма 1)57 9 1 662 0 − 2,062С432 (С432.iscas) (пр-ма 1) 579 200 7 759 23 6523,765 131962,125С499 (С499.iscas) (пр-ма 1) 859 41 32 24 0 − 27880С880 (С880.iscas) (пр-ма 1) 1202 60 26 3230 0 − 2275,828С1355 (С1355.iscas) (пр-ма 1)1687 41 32 42 0 − 46439,6094. ЗАКЛЮЧЕНИЕПредложен и реализован метод синтеза тестовыхнаборов комбинационных схем для одиночных кон-стантных неисправностей произвольных элементов схе-мы. Метод основан на использовании ОДНФ функций,реализуемых схемой и ее подсхемами, компактнопредставленными композицией SSBDD-графов.

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