Device for reducing the width of graph and a method to reduce the width of graph, and a device for logic synthesis and a method for logic synthesis

摘要

A device for logic synthesis that can be used to synthesize LUT logic circuit having intermediate outputs for multiple-output logic functions. The device includes means to store node table 8 storing Binary Decision Diagram for Characteristic Function (BDD_for_CF) of the characteristic function χ(X, Y) of the multiple-output logic function f(X), means to store LUTs 16, means to reduce by shorting 11 partitioning BDD_for_CF into the subgraphs B₀ and B₁ at the partition line in the height lev of the partition and executing shorten-processing, means to measure the width W of BDDs 12 calculating the width W at the partition line, means to compute the intermediate variables 13 calculating the number of the intermediate variables u according to the width W, means to generate an LUT 14 generating the LUT for the sub-graph B₀, and means to reconstruct BDDs 15 generating a binary tree that has the same number of control inputs as that of the intermediate variables u, replacing the sub-graph B₀ with the binary tree and reconstructing the BDD_for_CF.