GENERALIZATION OF THE SHANNON EXPANSION FOR INCOMPLETELY SPECIFIED FUNCTIONS: THEORY AND APPLICATION
Abstract
The well known Shannon expansion is not applicable to incompletely specified functions. We propose a theory that merges Boolean and partial algebras and provides creation of new representations and expansions of partially specified functions. A powerful property of the expansions is the reduction of definiteness level of expansion products. This is a source of enlargement of possibilities for synthesis, parallelization and optimization of completely and incompletely specified logical software/hardware systems. A result of proposed theory is a new type of decision diagram. It is shown on the parallelization of adders that the throughput of the system grows rapidly while the system complexity grows slowly.
References
1. Prihozhy, A.A. Methods of Partial Logic and If-Decision Diagrams for Synthesis and Formal Verification of Digital Circuits / A.A. Prihozhy, B. Becker // DAAD Research Report. – Freiburg University, Germany, 2000. – 30 P.
2. Prihozhy, A.A. If-Diagrams: Theory and Application / A.A. Prihozhy // Proc. of the European Conference PATMOS’97. – UCL, Belgium, 1997. – P. 369 – 378.
3. Prihozhy, A.A. Parallel Computing with If-Decision-Diagrams / A.A. Prihozhy, P.U. Brancevich // Proc. of the Int. Conference PARELEC’98. – Poland, Technical University of Bialystok, 1998. – P. 179 – 184.
4. Prihozhy, A.A. If-Decision Diagram Based Modeling and Synthesis of Incompletely Specified Digital Systems / A.A. Prihozhy, B. Becker // Electronics and communications, Special Issue on Electronics Design. – Kyiv, 2005. – P. 103 – 108.
5. Прихожий, А.А. Преобразование ifдиаграмм решений в пространстве параметров время-сложность / А.А. Прихожий // Автоматизация проектирования дискретных систем, Материалы Седьмой межд. конф. CAD’10. – Минск: ОИПИ НАН Беларуси, 2010. С. 15-22.
Review
For citations:
Prikhozhy A.A. GENERALIZATION OF THE SHANNON EXPANSION FOR INCOMPLETELY SPECIFIED FUNCTIONS: THEORY AND APPLICATION. . 2013;(1-2):6-11. (In Russ.)
