And-Exor Expressions and their Optimization
作者： Tsutomu Sasao
DOI: 10.1007/978-1-4615-3154-8_13
关键词: Polarity symbols 、 Polarity (physics) 、 ExOR 、 Ternary operation 、 Pure mathematics 、 Arithmetic function 、 Mathematics 、 Kronecker delta 、 Expression (mathematics)
摘要: This chapter consists two parts: the first part presents 7 classes of AND-EXOR expressions:positive polarity Reed-Muller expressions, fixed Kronecker pseudo generalized expressions and exclusive-or sum-of-products (ESOPs). Relations between these are shown. The number products to realize several functions analyzed. Optimization programs for were developed, statistical results arithmetic functions, randomly generated all 4 5 bariables obtained. second an optimization method pseudo-ronecker using ternary decision diagrams (TDDs). conventional requires memory O(3n) simplify n-variable expression, is only practical up n = 14 variables. presented here uses TDDs, can optimize considerably larger problems. Experimental 39 variables
springer.com
sci-hub.st 参考文章(35)
G. Bioul, Minimization of ring-sum expansion of Boolean functions Philips Res. Rpts.. ,vol. 28, pp. 17- 36 ,(1973)
Jean-Pierre Deschamps, Marc Davio, André Thayse, Discrete and switching functions ,(1978)
Michael A. Harrison, Introduction to switching and automata theory ,(1978)
Raymond J. Nelson, Review: D. E. Muller, Application of Boolean Algebra to Switching Circuit Design and to Error Detection Journal of Symbolic Logic. ,vol. 20, pp. 195- 195 ,(1955) , 10.2307/2266958
Tsutomu Sasao, On the Complexity of Some Classes of AND-EXOR Expressions 京都大学数理解析研究所. ,(1992)
M. Perkowski, M. Chrzanowska-Jeske, An exact algorithm to minimize mixed-radix exclusive sums of products for incompletely specified Boolean functions international symposium on circuits and systems. pp. 1652- 1655 ,(1990) , 10.1109/ISCAS.1990.112455
Saburo Muroga, Logic design and switching theory ,(1979)
Fleisher, Tavel, Yeager, A Computer Algorithm for Minimizing Reed-Muller Canonical Forms IEEE Transactions on Computers. ,vol. 36, pp. 247- 250 ,(1987) , 10.1109/TC.1987.1676890
T. Sasao, EXMIN: a simplification algorithm for exclusive-OR-sum-of-products expressions for multiple-valued input two-valued output functions international symposium on multiple-valued logic. pp. 128- 135 ,(1990) , 10.1109/ISMVL.1990.122597
L. Csanky, M. Perkowski, I. Schaefer, Canonical restricted mixed-polarity exclusive sums of products international symposium on circuits and systems. ,vol. 1, pp. 17- 20 ,(1992) , 10.1109/ISCAS.1992.230025