Logiksynthese mit Funktionaler Dekomposition

| project staff | project description | publications |

The basic problem when designing a circuit is to convert a given circuit specification into a correct circuit implementation. A partial stage of this design flow is logic synthesis which generates an appropriate implementation starting from the specification which the functional layout provides. The result of the logic synthesis is a netlist description using a library of basic cells.

The main topics treated in this project basically belongs to combinational logic synthesis, which means the automatic synthesis of combinational partial functions (without registers).

The analyzed method for multi-level combinational logic synthesis is based on recursive decomposition of the boolean function to be realized. A disjoint decomposition of a boolean function f with the input variables x1, …, xn is a construction of the following form:


Now the blocks specified by alpha and g are decomposed recursively. In order to reduce the costs of the realization solutions which have a small number of partial functions are desireable.

One application of the proposed method is (but not exclusively) the synthesis of LUT (=look up table)-based FPGAs, for which boolean functions can be realized up to a certain amount of inputs by a single look up table. The main characteristics of the decomposition method developed in this project are the following:

Identification of partial functions which can be used with advantage in several circuit components. This works by exploiting some degrees of freedomu when selecting decomposition functions. When realizing functions with multiple outputs one must have in mind that as many common decomposition functions as possible are computed.

Exploiting symmetries.

Exploiting don't cares in partial functions.