%0 Report %1 TR93 %A Nöth, Winfried %A Kolla, Reiner %C Department of Computer Science %D 1994 %K myown %N 93 %T Optimal Synthesis of Fanoutfree Functions. %U http://www5.informatik.uni-wuerzburg.de/publications/techreports/tr93.ps.gz %X The problem of provable optimal synthesis of boolean functions for a given technology is still unsolved. In this paper we study the problem for the small class of fanoutfree functions. Every fanoutfree function can be uniquely represented by a Normal AND-OR-Tree. Based on this representation, we introduce algorithms for provable optimal synthesis of any n-input fanoutfree function over a given library of gates implementing the functions AND, OR, NAND and NOR with 2...k inputs. The synthesis yields a complete time-area tradeoff of the optimal fanoutfree implementations of the function. Since in worst case our algorithms have exponential run time, we show their feasibility on realistic examples of fanout free zones of circuits. Finally, ideas are outlined for the integration of complex gates into the synthesis process.

@techreport{TR93, abstract = { The problem of provable optimal synthesis of boolean functions for a given technology is still unsolved. In this paper we study the problem for the small class of fanoutfree functions. Every fanoutfree function can be uniquely represented by a Normal AND-OR-Tree. Based on this representation, we introduce algorithms for provable optimal synthesis of any n-input fanoutfree function over a given library of gates implementing the functions AND, OR, NAND and NOR with 2...k inputs. The synthesis yields a complete time-area tradeoff of the optimal fanoutfree implementations of the function. Since in worst case our algorithms have exponential run time, we show their feasibility on realistic examples of fanout free zones of circuits. Finally, ideas are outlined for the integration of complex gates into the synthesis process.}, added-at = {2015-06-18T10:00:28.000+0200}, address = {Department of Computer Science}, author = {Nöth, Winfried and Kolla, Reiner}, biburl = {https://www.bibsonomy.org/bibtex/255ca1bb173125bf6e7fe6b9125c0251c/trcsuniwue}, interhash = {cb1a4211b703e0a8d1e48107f5944349}, intrahash = {55ca1bb173125bf6e7fe6b9125c0251c}, keywords = {myown}, month = {November}, number = 93, timestamp = {2015-06-18T10:00:28.000+0200}, title = {Optimal Synthesis of Fanoutfree Functions.}, type = {Technical Report}, url = {http://www5.informatik.uni-wuerzburg.de/publications/techreports/tr93.ps.gz}, year = 1994 }