Graph width reduction method and graph width reduction equipment, as well as logic synthesis method and logic circuit synthesis device

摘要

Provided is a logic circuit synthesis device capable of synthesizing an LUT logic circuit having an intermediate output for a multi-output logic function. Characteristic function binary decision graph node table storage means 8 of the multi-output logical function f (X) f (X), LUT storage means 16, and characteristic function binary decision graph are divided into lines having a predetermined height lev. The short-circuit removing means 11 that performs the short-circuit removing process by dividing into the partial graphs B0 and B1, the BDD width measuring means 12 that measures the width W in the dividing line, and the intermediate variable calculating means that calculates the number of intermediate variables based on the width W. 13, a LUT generating means 14 for generating an LUT for the subgraph B0, a binary tree having the number of control inputs equal to the number u of intermediate variables is generated, the subgraph B0 is replaced with a binary tree, and the characteristic function binary decision graph is It was set as the structure provided with the BDD reconstruction means 15 to reconfigure | reconstruct.