Patent ID: 7844924

Claim:
A “Device for Reducing a Width of Graph” which reduces a width of a Binary Decision Diagram for Characteristic Function (BDD_for_CF), where BDD_for_CF is a characteristic function χ(X,Y) defined in Equation (1), X=(x 1 , . . . , x n ) (nεN, N is a set of natural numbers) denotes input variables, Y=(y 0 , . . . , y m−1 ) (m≧2, mεN) denotes output variables of a multiple-output logic function F(X), and F(X)=(f 0 (X), . . . , f m−1 (X)) is an incompletely specified function to an output including don't care, said device comprising: (A) “Means to Store Node Table” storing the node table which is a table of node data that consists of labels of variables and pairs of edges e 0 (v i ) and e 1 (v i ), where the labels of variables are labels given to variables z i (z i ε(X∪Y)) corresponding to each non-terminal node v i in the BDD_for_CF of the multiple-output logic function F(X), and a pair of edges e 0 (v i ) and e 1 (v i ) that points to next transition child node(s) when input values of z i (z i ε(X∪Y)) are 0 and 1; (B) “Means to Find Dividing Lines” setting a height of the partition lev which partitions BDD_for_CF represented by said node table stored in said “Means to Store Node Table”; (C) “Means to Generate Column Functions” generating a column function which represents a column of a decomposition chart derived by a functional decomposition from said node table stored in said “Means to Store Node Table”, where the decomposition is obtained by partitioning said BDD_for_CF by said height of the partition lev set by said “Means to Find the Dividing Lines”; and (D) “Means to Reconstruct Assigned BDD” which assigns constants to don't care in compatible column functions of column function generated by said “Means to Generate Column Functions”, and consequently assigns these compatible column functions to the identical column functions, and reconstructs said BDD_for_CF using new assigned column function, and finally updates the node table in said “Means to Store Node Table”, wherein Equation (1) is defined as follows: [Equation 1] χ ⁡ ( X , Y ) = ⩓ m - 1 i = 0 ⁢ { y _ i ⁢ f i_ ⁢ 0 ⋁ y i ⁢ f i_ ⁢ 1 ⋁ f i_d } ( 1 ) where f i — 0 , f i — 1 , f i — d are OFF function, the ON function and DC function defined in Equation (2), respectively, wherein Equation (2) is defined as follows: [Equation 2] f i_ ⁢ 0 ⁡ ( X ) = { 1 ( X ∈ f i - 1 ⁡ ( 0 ) ) 0 ( otherwise ) , f i_ ⁢ 1 ⁡ ( X ) = { 1 ( X ∈ f i - 1 ⁡ ( 1 ) ) 0 ( otherwise ) , f i_d ⁡ ( X ) = { 1 ( X ∈ f i - 1 ⁡ ( d ) ) 0 ( otherwise ) . ( 2 )