Graph representations of the sets of all reachable reactions of the combinational circuit.pdf При решении ряда задач диагностики и тестирования логических схем полезными оказываются особые функции для внутренних полюсов, которые зависят от некоторого подмножества предшествующих полюсов схемы. Эти функции являются частично определенными. Область их определения состоит из таких наборов предшествующих полюсов, что смена значения сигнала на соответствующем набору внутреннем полюсе вызывает смену значений сигналов хотя бы на одном из выходов схемы. Такие функции могут использоваться для маскирования неисправностей и вредоносных подсхем [1, 2], верификации частичных реализаций схем [3, 4], структурного кодирования («обфуска-ции») [5, 6], защиты схем со структурной избыточностью (троирование) [7, 8]. Такие функции могут вычисляться либо с помощью частично определенных функций внутренних полюсов, зависящих от входов схемы (область определения таких функций - множество тестовых наборов для одиночной константной неисправности в соответствующем полюсе) [9, 10], либо без использования таких функций. Второй способ более предпочтителен, так как построение частично определенной функции внутренних полюсов, зависящей от входов схемы, возможно далеко не всегда, поскольку в некоторых случаях размеры ROBDD-графов, требуемых для построения функции, растут экспоненциально. Алгоритм построения, реализующий этот способ, приведен в работе [11]. На первом шаге алгоритма вычисляется множество наборов, которые могут появиться на некотором подмножестве внутренних полюсов схемы. Эта задача эквивалентна задаче получения множества всех возможных выходных реакций некоторой известной комбинационной схемы. В работе [11] данная задача решается путем перебора всех возможных наборов (выходных реакций на подмножестве полюсов) с проверкой их на достижимость. При маскировании неисправностей число переменных, от которых зависит частично определенная функция, обычно достигает одного-двух десятков, и поэтому полный перебор выполняется за приемлемое время. Однако при решении других задач, например при верификации частичных реализаций логических схем, число переменных может достигать нескольких десятков, а число возможных реакций, как известно, увеличивается экспоненциально с ростом числа переменных. Поэтому желательно иметь алгоритмы, которые определяют множество достижимых реакций схемы без полного перебора и компактно их представляют. В данной работе предлагается алгоритм построения ROBDD-графа, представляющего множество всех достижимых реакций комбинационной логической схемы. Получаемый граф содержит внутренние вершины, которые помечены только выходными переменными схемы. Алгоритм предлагается использовать в тех случаях, когда ROBDD-граф, зависящий от входных и выходных переменных, не может быть построен из-за экспоненциального роста количества его внутренних вершин. 1. Основные определения и постановка задачи Комбинационная логическая схема - модель устройства без памяти. У таких устройств состояния выходов однозначно определяются набором входных сигналов (булевым вектором на множестве входных переменных). Состояние выходов комбинационной схемы (булев вектор на множестве выходных переменных схемы) при подаче на входы определенного набора называется реакцией схемы на этот входной набор. Например, рассмотрим комбинационную схему (рис. 1), реализующую систему булевых функций: Уі = ХіХ2 V Х3, У2 = Х1Х2 Х3. У3 = x3 V x4 V x5, У4 = X3 (X4 V x5). Если на входы схемы поступает набор 10101, то на выходах схемы достигается набор 1100, т.е. набор 1100 является реакцией схемы на входной набор 10101. Булев вектор в пространстве выходных переменных называется достижимой реакцией, если существует набор, при подаче на входы которого заданный булев вектор появляется в качестве реакции схемы. 129 Дискретные функции и автоматы / Discrete function and automatons Рис. 1. Пример комбинационной схемы Fig. 1. Example of combinational circuit Формально задача может быть поставлена следующим образом. Имеется многовыходная комбинационная схема С, реализующая систему булевых функций fj(xl,x2....,xtJ), і = \\.....т , Требуется найти такое множество N = {(Pj, Р2, • • •, Р,„ )} с: Щ • что для каждого (рх,Р2, • • •,Р,„ ) е N существует непустое множество, такое что для каждого {cLl,cL2,...,cLfJ)^M fj(cLl,cL2,...,cLtJ) = $j, i = l,...,m. Элементы множества УѴ = {(Р, ,Р2,.. .,Ртс Вт будем называть достижимыми реакциями схемы. Множество М = |(а|,а2,...,аи)|сбудем называть полным прообразом реакции (Pj,Р2,• • •,Р,„ ) е N. Отметим, что для различных наборов (р},Р2,...,Pj„) е N и (р^,Р2,...,Р^) е N соответствующие множества M1 и M2 не пересекаются (их пересечение означало бы, что подача одного набора на входы схемы приводит к двум разным реакциям одновременно, что невозможно). 2. Определение функции, содержащей информацию о достижимых реакциях комбинационной схемы, и ее свойства Пусть задана многовыходная комбинационная схема С, реализующая систему булевых функций ух = f (xj, х2,..., х„ ), у2 = /2 (xj, х2,..., х„ ), ..., ут = fm (xj, х2,..., х„ ) . Рассмотрим следующую функцию, которая зависит от входных и выходных переменных комбинационной схемы: т / (Ху, х2,..., х„, Уі, у2,..., ут ) = ЛJ Уі ~ ft (Д, х2,..., х„) J , 1= Iй- ^ где - логическая операция «эквивалентность». Эта функция обладает следующими свойствами: 1. Если вместо входных переменных подставить константы из {0, 1}, то получим функцию, которая принимает единичное значение на единственном наборе. Этот набор является реакцией схемы на данный входной набор. На остальных наборах полученная функция принимает нулевое значение. Пусть (а1;а2,...,ая) - некоторый входной набор, тогда существует один и только один выходной набор (Р!,Р2,...,Рт) такой, что = 1, причем Pj = f (a^cu,...,^,), Р2 =/2(ai,a2,...,a„), ..., Pm =/m(a1,a2,...,a„) . Для всякого набора (у1;у2,...,ут) * (Р1;Р2,...,Рт) /(a1,a2,...,a„,y1,y2,...,yIII) = 0. 2. Если вместо выходных переменных подставить константы из {0, 1}, то получится функция, которая принимает единичное значение на всех наборах, которые обеспечивают проявление заданной реакции на выходах схемы. В частном случае, если заданная реакция недостижима, то полученная функция тождественно равна 0. Рассмотрим некоторый выходной набор (Р15Р2, - ,Р,„) - Тогда 130 Провкин В.А., Матросова А.Ю. Графовые представления множеств всех достижимых реакций /(а1,а2,...,ая,Р1,Р2,...,РЯІ) = 1 для любого набора (а1;а2,...,ая) такого, что Pj = fx (а1;а2,...,ая), Р2 =/2(аі,а2,...,ая), Р„ = /я(а1;а2!...,ая). Если таких наборов не существует, то /(а1,а2,...,а„,у1 = Ра,3’2 =Р2,=Р,„) = 0 для всех наборов (су,^,...,^) . Для получения всех достижимых реакций схемы можно построить ROBDD-граф функции f(xl,x2,...,xn,yl,y2,...,ym) , причем выбираем следующий порядок переменных при использовании формулы разложения Шеннона: }\\,у2,...,ут, х1,х2,...,хп. Полученный граф будет обладать следующими свойствами. Утверждение 1. Каждая простая цепь, заканчивающаяся в вершине со значением 0 и не содержащая вершин, помеченных входными переменными, соответствует недостижимому набору (возможно, некоторому множеству наборов). Доказател ьство. Корневой вершине графа соответствует функция / (х,. х2..... хп. у, .у,..... ут). и этой вершине приписана переменная ѵі. При переходе из корневой вершины по дуге, помеченной значением 1(0), попадаем в вершину, которой соответствует функция f(xl,x2,...,xri,\\,y2,...,ym) ( /(х1,х2,...,хя,0,у2,...,уиі) ). Эта вершина помечена переменной ѵз. Перейдя из нее по дуге, помеченной значением 1 (0), получаем функцию, которая построена из функции, соответствующей предыдущей вершине, подстановкой значения 1 (0) в переменную уг. Продолжим этот процесс до тех пор, пока не дойдем до 0-концевой вершины. Так как в цепи присутствуют только вершины, помеченные выходными переменными, то это значит, что подстановки значений выполнялись только в те аргументы функции, которые соответствуют выходным переменным схемы. Поскольку цепь заканчивается в 0-концевой вершине, то /(су,а2,...,ая, yl = Pj, у2 = Р2,..., ут = Р„;) = 0 для всех наборов (оу,оц,...,ося) и, следовательно, набор (Pj,P2,...,Pm) недостижим. Утверждение 2. Каждая простая цепь, содержащая вершины, помеченные входными переменными схемы, и заканчивающаяся в 1-терминальной вершине графа, соответствует некоторой достижимой реакции, представленной всеми выходными переменными схемы, за счет отрезка цепи, связывающего рассматриваемую простую цепь с корнем графа. Доказательство. Если пройти по отрезку цепи из корневой вершины до первой вершины v простой цепи, помеченной входной переменной, то этой вершине сопоставляется функция /(х1,х2,...,хя,у1 = Pj,з’2 =Р2,...,_ут =Рт) , которая принимает единичное значение на таких наборах (а1;а2,...,ая), для которых справедливы равенства Pj = fx (а15а2,...,ая), Р2 = /2(а1;а2,...,ая), ..., Р™ = fm (ai,a2■ Иными словами, граф с корнем в вершине ѵ представляет функцию, являющуюся полным прообразом реакции (Pj,Р2,...,Ря;) . Пусть задана комбинационная схема, поведение которой описывается следующей таблицей истинности (табл. 1). Таблица 1 Пример таблицы истинности, описывающей поведение комбинационной схемы Х1 Х2 Х3 Х4 У У2 Уз 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 131 Дискретные функции и автоматы / Discrete function and automatons Окончание табл. 1 Х1 Х2 Х3 Х4 У1 У2 Уз 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 ROBDD-граф функции f ( xj, x2, x3, x4, yj, y2, y3) представляется следующим образом (рис. 2). Рис. 2. ROBDD-граф функции f (x,x2,x3,x4,y,y2,у ) Fig. 2. ROBDD of function f (xj, x2, x3, x4, yj, y2, y3 ) Будем искать в ROBDD-графе пути, начинающиеся в корневой вершине, до первой вершины, помеченной входной переменной схемы. На рис. 2 видно, что таких путей три: 18-16-13-10, 18-16- 15-11 и 18-17-15-12. Им сопоставляются двоичные векторы 101, 110 и 011 соответственно. Выделив подграфы с корневыми вершинами 10, 11 и 12, получаем входные наборы, поступление которых на входы схемы приводит к появлению соответствующей реакции на выходах. Так, для реакции 101 это наборы 0010, 0101, 1000, 1011 и 1110, для реакции 110 - наборы 0001, 0100, 0111, 1010 и 1101, а для реакции 011 - наборы 0000, 0011, 0110, 1001, 1100 и 1111. 3. Модификация общего алгоритма построения ROBDD-графа для построения графа реакций С помощью ROBDD-графа, построенного по функции f (х1,х2,...,хп,у1,у2,...,ут), можно получить все достижимые реакции схемы. Однако часто в задачах требуется найти только достижимые реакции схемы, и не требуется знать, какие входные наборы дают соответствующие реакции. Например, для предыдущего примера граф, который представляет только достижимые реакции схемы, выглядит следующим образом (рис. 3). 132 Провкин В.А., Матросова А.Ю. Графовые представления множеств всех достижимых реакций Рис. 3. ROBDD-граф достижимых реакций схемы Fig. 3. ROBDD of reachable circuit patterns Этот граф, назовем его в дальнейшем графом достижимых реакций, получается из исходного следующим образом: если 1(0)-дуга из вершины, помеченной выходной переменной схемы, ведет в вершину, помеченную входной переменной схемы, то из вершины, помеченной выходной переменной схемы, проводится 1(0)-дуга в 1-терминальную вершину графа. Затем из графа удаляются все вершины, помеченные входными переменными схемы. Далее в графе выполняются соответствующие для ROBDD операции упрощения. Очевидно, что граф достижимых реакций содержит существенно меньше внутренних вершин, чем граф функции f(xl,x2,...,xn,yl,y2,...,ym) (7 вершин вместо 19). Хотя граф достижимых реакций может быть получен из графа функции f(xl,x2,...,xn,yl,y2,...,ym), желательно иметь алгоритм его построения без предварительного получения графа функции f Такой алгоритм может быть использован в тех случаях, когда, например, построение графа функции f невозможно из-за экспоненциального роста количества его вершин. Предлагаемый алгоритм построения ROBDD-графа, представляющего все достижимые реакции схемы, основан на алгоритме построения ROBDD-графа произвольной булевой функции. В графе сначала выполняется разложение по выходным переменным схемы, а затем по ее входным переменным. Модификация этого алгоритма основана на следующем правиле. Пусть в графе дуга из некоторой вершины, помеченной выходной переменной схемы, ведет в вершину, помеченную входной переменной схемы. Тогда вершина, помеченная входной переменной схемы, представляет функцию f(xl,x2,...,xri) = f(xl,x2,...,xri,yl=$l,y2=$2,...,ym=$m), причем эта функция не равна тождественно ни константе 0, ни константе 1 (так как в противном случае эта вершина была бы 1 - или 0-терминальной вершиной графа). Эта функция принимает значение 1 на таких двоичных векторах, подача которых на входы схемы приводит к появлению на ее выходах реакции (Pj,P2,...,P„;). Если важна только достижимость реакции, но нет необходимости знать, на каких входных наборах она достигается, то значение функции /(х1,х2,...,х„) = /(х1,х2,...,х„,у1 =р15у2 =p2,...,ym=pj можно положить равным 1. Это значит, что в соответствующем ROBDD-графе достижимых реакций дуга из вершины, помеченной выходной переменной схемы, должна вести в 1 -терминальную вершину. На основе вышесказанного предлагается поступать следующим образом. Если в процессе построения графа на множестве входных и выходных переменных обнаружено, что функция f принимает значение 1 на некотором наборе, то соответствующая 0- или 1 -дуга из последней вершины v, помеченной выходной переменной схемы, ведет в 1-терминальную вершину графа реакций, а граф с корнем в вершине v, состоящий из вершин, помеченных входными переменными схемы, удаляется. Если для функции f такого набора не существует, т.е. она тождественно равна нулю, то соответствующая 0- или 1-дуга из вершины v ведет в 0-терминальную вершину строящегося графа. 133 Дискретные функции и автоматы / Discrete function and automatons Далее в полученном графе, состоящем из вершин, помеченных только выходными переменными, выполняются операции упрощения с целью получения ROBDD-графа достижимых реакций. Утверждение 3. Если для двух схем при одном и том же порядке разложения выходных переменных графы достижимых реакций различны, то схемы реализуют различные системы булевых функций. Доказательство следует из свойств ROBDD-графов, полученных при одном и том же порядке разложения переменных. Покажем работу алгоритма на примере. Рассмотрим комбинационную схему с четырьмя входами и тремя выходами, поведение которой описывается системой булевых функций: У1 = /1 (Х\\, Х2, Х3, Х4 ) = (Х1 Х2 Ѵ Х1Х2 )(Х3 Х4 Ѵ Х3 Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 ), У2 = /2 (Х1, х2, х3, х4 ) = (Х1 Х2 Ѵ Х1Х2 )( х3 Ѵ х4 ) Ѵ Х1Х2 ( х3 Ѵ х4 ) Ѵ Х1 х2 (Х3Х4 Ѵ х3 х4 ), У3 = /3 (Х1, х2, х3, х4 ) = (х1 х2 Ѵ Х1Х2 ) (х3 Ѵ x4 ) Ѵ Х1Х2 ( х3 х4 Ѵ x3 х4 ) Ѵ x1 х2 ( х3 Ѵ x4 ). Тогда функция f ( Х1, Х2> Х3> Х4, У1, У2, У3 ) = ( У1~ /1 ( Х1, Х2> Х3> Х4 ))(У2 ~ f2 (Х1, Х2, Х3, Х4 ))(У3 ~ f3 (Х1, Х2, Х3, Х4 )) = Л Л У1 ~ (( Х1Х2 Ѵ Х1Х2 )(Х3 Х4 Ѵ Х3 Х4 )Ѵ Х1Х2 (Х3 Ѵ Х4 )Ѵ Х1 Х2 (Х3 Ѵ Х4 )) У2 ~ (( Х1 Х2 Ѵ Х1Х2 ) (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3Х4 Ѵ Х3 Х4 )) У3 ~ (( Х1Х2 Ѵ Х1Х 2 ) (Х3 Ѵ Х4 ) Ѵ Х1Х 2 (Х 3Х 4 Ѵ Х3 Х4 ) Ѵ ^Х2 (Х3 Ѵ Х4 )) Л Л Пусть переменные yi, y2 и уз имеют номера 1, 2 и 3 соответственно, переменные xi, Х2, хз и Х4 -номера 4, 5, 6 и 7. Число входных переменных n = 4, число выходных переменных m = 3. Номер текущей переменной i = 1. Подставляем в переменную yi значение 0: Л f ( Х1,Х2,Х3,Х4Л У2, У3 ) = [((Х1 Х2 Ѵ Х1Х2 ) (Х 3Х 4 Ѵ Х3 Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 )) У2 ~ (( Х1Х2 Ѵ Х1Х 2 ) (Х3 Ѵ Х4 ) Ѵ Х1Х 2 (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3Х 4 Ѵ Х3 Х4 )) У3 ~ (( Х1Х2 Ѵ Х1Х 2 ) (Х3 Ѵ Х4 ) Ѵ Х1Х 2 (Х3Х 4 Ѵ Х3 Х4 ) Ѵ Х1 Х2 (Х3 Ѵ Х4 )) Переходим к переменной у2 (i = i + 1 = 2) - подставляем в эту переменную значение 0: /(Х1,Х2,Х3,Х4,0,0,У3 ) = [(( Х1Х2 Ѵ Х1Х2 ) (Х3Х 4 Ѵ Х3 Х 4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 )) ((х Х2 Ѵ ХгХ2 ) (х3 Ѵ х4 ) Ѵ ХгХ2 (х3 Ѵ x4 ) Ѵ Xj x2 (x3x4 Ѵ x3 х4 )) У3 ~ (( Х1 Х2 Ѵ Х1Х2 ) (Х3 Ѵ Х4 ) Ѵ Х1Х2 (Х3Х 4 Ѵ Х3 Х 4 ) Ѵ Х1Х2 (Х3 Ѵ Х4 )) Переходим к переменной уз (i = i + 1 = 3) - подставляем в эту переменную значение 0: / ( Х1,Х2,Х3,Х4,0,0,0 ) = ^(( Х1Х2 Ѵ Х1Х 2 ) (Х3Х 4 Ѵ Х3 Х4 ) Ѵ Х1Х 2 (Х3 Ѵ Х4 ) Ѵ ^Х2 (Х3 Ѵ Х4 )) Л ((x x2 ѴХ,Х2| (x3 Ѵ x4 ) Ѵ Х3Х2 (х3 Ѵ x4 ) Ѵ Xj x2 (x ;))] Л ((х х2 ѵ xx2) (X ѵ x4) ѵ XX (ХзХ ѵ XX) ѵ х X (X ѵ х4 )) Переходим к переменной xi (i = i + 1 = 4) - подставляем в эту переменную значение 0: Х2, ^ X4, Л Л /(0,x2,x3,х4,0,0,0)= (x2 (x3х4 ѵ x3х4) ѵ x2 (x3 ѵ x4)) Л (х2 (х3 Ѵ x4 ) Ѵ x2 (х3 Ѵ x4 )) (х2 (х3 Ѵ x4 ) Ѵ x2 (X )) 134 Провкин В.А., Матросова А.Ю. Графовые представления множеств всех достижимых реакций Переходим к переменной Х2 (і = f ( 0,0, Х3, x4, Переходим к переменной хз (i = 0: 0: i + 1 = 5) - подставляем в эту переменную значение 0,0,0) = (x3х4 ѵ x3 x4 )(х3 ѵ x4 )(х3 ѵ х4 ). i + 1 = 6) - подставляем в эту переменную значение f ( 0,0,0, x 4,0,0,0) = 0. При подстановке в переменную Х4 и значения 0, и значения 1 значение функции равно 0. Поэтому функции f ( 0,0,0, x4,0,0,0 ) соответствует 0-терминальная вершина. Подставляем в переменную хз значение 1: f (0,0,1, x4,0,0,0) = x4 x4 = 0. При подстановке в переменную Х4 и значения 0, и значения 1 значение функции равно 0. Поэтому функции f ( 0,0,1, x4,0,0,0) соответствует 0-терминальная вершина. Следовательно, и функции f (0,0, x3, x4,0,0,0) соответствует 0-терминальная вершина. Возвращаемся к переменной Х2 (і = 5) и подставляем в эту переменную значение 1: f (0,1, x3, x4,0,0,0) = (x3 ѵ x4)(x3 ѵ x4)(x3x4 ѵ x3x4). Переходим к переменной хз и подставляем в нее значения 0 и 1: f ( 0,1,0, x4,0,0,0) = 0, f ( 0,1,1, x4,0,0,0 ) = 0. Получаем, что функции f (0,1, x3, x4,0,0,0) соответствует 0-терминальная вершина. Возвращаемся к переменной Х2: получаем, что f (0,0,x3,x4,0,0,0) = f (0,1,x3,x4,0,0,0) = 0 . Поэтому функции f ( 0, x2, x3, x4,0,0,0) также соответствует 0-терминальная вершина. Возвращаемся к переменной хі (і = 4) и подставляем в эту переменную значение 1: A f (1, x2, x3, x4,0,0,0) = (x2 (x3x4 ѵ x3 x4 ) ѵ x2 (x3 ѵ x4 )) A (x2 (x3 ѵ x4 ) ѵ x2 (x3x4 ѵ x3 x4 ))J^(x2 (x3 ѵ x4 ) ѵ x2 (x3 ѵ x4 )) f (1,0, x3, x4,0,0,0) = (x3 ѵ x4 )(x3x4 ѵ x3 x4 )(x ѵ x4 ) = 0, f (1,1, x3, x4,0,0,0) = ( x3x4 ѵ x3 x4 )( x3 ѵ x4 )( x3 ѵ x4 ) = 0. В результате получили, что f (x1,x2,x3,x4,0,0,0) = 0 , т. е. функции f (x1,x2,x3,x4,0,0,0) соответствует 0-терминальная вершина. Вернувшись к переменной уз (і = 3) и подставив в нее значение 1, получим, что f (x1,x2,x3,x4,0,0,1) = 0 . Таким образом, имеем f (x1,x2,x3,x4,0,0,y3) = 0 . Теперь вернемся к переменной у2 (і = 2) и подставим в нее значение 1. Далее подставим значение 0 в переменную уз. Получим, что f (x1, x2, x3, x4,0,1,0) = 0 . Подставим значение 1 в переменную уз: A A f ( x1, x2, x3, x4,0,1,1)= (( x1 x2 ѵ x1x2 ) (x3x4 ѵ x3 x4 ) ѵ x1x2 (x3 ѵ x4 ) ѵ x1 x2 (x3 ѵ x4 )) A ((x1 x2 ѵ x1x2 )(x3 ѵ x4 )ѵ x1x2 (x3 ѵ x4 )ѵ x1 x2 (x3x4 ѵ x3 x4 )) A A ((x1 x2 ѵ x1x2 )(x3 ѵ x4 )ѵ x1x2 (x3 x4 ѵ x3 x4 )ѵ x1 x2 (x3 ѵ x4 )) . Переходим к переменной х1 - подставляем в эту переменную значение 0: f (0, x2, x3, x4,0,1,1)= (x2 (x3 x4 ѵ x3 x4 ) ѵ x2 (x3 ѵ x4 )) (x2 (x3 ѵ x4 ) ѵ x2 (x3 ѵ x4 )) A ^(^ (x ѵ x4) ѵ x2 (x3x4 ѵ x3x4))J. із5 Дискретные функции и автоматы / Discrete function and automatons Подставим значение 0 в переменную Х2: f (0,0,x3,x4,0,1,1) = (x3x4 v x3x4)(x3 v x4)(x3 v x4 ). Подставим значение 0 в переменную Подставим значение 1 в переменную Х4 и получим, что f (0,0,0,0,0,1,1) = 1, т.е. функции f (0,0,0,0,0,1,1) соответствует 1-терминальная вершина. Это значит, что функциям f ( 0,0,0, x4,0,1,1), f (0,0,x3,x4,0,1,1), f (0,x2,x3,x4,0,1,1) и f (x1,x2,x3,x4,0,1,1) также соответствует 1-терминальная вершина. Ранее мы получили, что функции f (x1, x2, x3, x4,0,1,0) соответствует 0-терминальная вершина. Поэтому функции f (x1, x2, x3, x4,0,1, y3) соответствует внутренняя вершина, помеченная переменной уз, из которой 0-дуга ведёт в 0-терминальную вершину, а 1-дуга - в 1-терминальную вершину. Добавим в ROBDD-граф такую вершину (рис. 4). Рис. 4. ROBDD-граф функции f (у,x2,x,х,0,1,у ) Рис. 5. ROBDD-граф функции f (у,x2,x,х,0,у2,y ) Fig. 4. ROBDD of function f (x1, x2, x3, x4,0,1, y3 ) Fig. 5. ROBDD of function f (x1, x2, x3, x4,0, y2, y3 ) Ранее мы получили, что f (x1, x2, x3, x4,0,0, y3) = 0 . Поэтому функции f (x1, x2, x3, x4,0, y2, y3) соответствует внутренняя вершина, помеченная переменной у2, из которой 0-дуга ведет в 0-терми-нальную вершину, а 1-дуга - в ранее добавленную внутреннюю вершину. Теперь граф примет вид, представленный на рис. 5. Далее подставим значение 1 в переменную у1 и продолжим работу алгоритма. В результате получаем ROBDD-граф, изображенный на рис. 6. Рис. 6. ROBDD-граф, представляющий все достижимые реакции Fig. 6. ROBDD representing all reachable patterns 4. Экспериментальное сравнение размеров полного и сокращённого графов Разработана программа, реализующая алгоритм. Проведено сравнение количества вершин графа функции f и графа достижимых реакций схемы на контрольных примерах схем из набора LGSynth89. Результаты сравнения приведены в табл. 2. 136 Провкин В.А., Матросова А.Ю. Графовые представления множеств всех достижимых реакций Т аблица 2 Экспериментальные результаты: сравнение числа вершин в полном и сокращенном графах Название схемы Число входов Число выходов Число достижимых реакций Число вершин в графе функции f Число вершин в графе реакций alu2 10 6 38 736 10 alu4 14 8 146 8 174 12 C432 36 7 128 2 608 1 x2 10 7 14 107 24 Из таблицы видно, что предлагаемый алгоритм позволяет строить ROBDD-графы достижимых реакций схемы, содержащие существенно меньше, иногда на порядки, внутренних вершин, чем графы соответствующих функций f зависящих от входных и выходных переменных схемы. В частности, если все возможные двоичные наборы достижимы на выходах схемы, то получается граф реакций, состоящий из одной терминальной вершины 1 (схема C432). Заключение Предложен алгоритм построения ROBDD-графа, представляющего множество всех достижимых реакций комбинационной логической схемы, зависящего только от выходных переменных схемы. При построении графа реакций не требуется получения предложенного в работе более громоздкого графа функции f, представляющей входные наборы схемы вместе с порождаемыми ими реакциями. Проведено сравнение количества вершин в графе функции f и соответствующем графе реакций схемы. Эксперименты показали, что предлагаемый алгоритм позволяет строить графы достижимых реакций схемы, значительно более компактные, чем графы функций f.

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