OKFDD minimization by genetic algorithms with application to circuit design

✍ Scribed by Rolf Drechsler; Bernd Becker; Nicole Drechsler

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 261 KB
• Volume: 28
• Category: Article
• ISSN: 0167-9260
• DOI: 10.1016/s0167-9260(99)00017-6

✦ Synopsis

A genetic algorithm (GA) is applied to minimize ordered Kronecker functional decision diagrams (OKFDDs), i.e. a graph-based representation of Boolean functions. OKFDDs are then used to derive circuits by substituting the nodes in the graph.

The GA is "rst used to minimize the size of OKFDDs by choosing a good variable ordering and decomposition type list in parallel. Various GA parameters are studied, including population size and several genetic operators. Then the GA is used for the construction of OKFDD circuits that dependent on the chosen parameters trade o! area e$ciency versus testability. It is shown by experiments that the algorithm outperforms the best previously published heuristic approach. Finally, we apply our minimization algorithm to technology mapping for FPGAs. Also for this application experimental results are given to show the e$ciency of our approach.