Decomposition of Boolean function sets

• Autorzy: Rawski M.
• Języki publikacji: EN

Abstrakty

EN

The functional decomposition is recognized as very efficient synthesis method of digital circuits. Logic circuits have usually many outputs. Independent synthesis of each output is inefficient. There are several methods that allow decomposing multiple-output function. One of them is decomposition based on blanket calculus. However this method requires the multiple-output function to be represented as single truth table. This limits in the great degree the synthesis strategies that can be used. In this paper new method o functional decomposition based on blanket calculus is presented. This method allows the multiple-output function to be represented as a set of separate truth tables for each output. This allows the designer to apply a much wider range of synthesis strategies.

Słowa kluczowe

EN

Boolean function sets; logic synthesis; functional decomposition

PL

logiczna synteza; funkcjonalny rozpad; funkcja boolowska

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2007
• Tom: Vol. 53, No 3
• Strony: 231--251
• Opis fizyczny: Bibliogr. 16 poz., rys., tab., wykr.

Twórcy

autor

Rawski M.

• Warsaw University of Technology, Institute of Telecommunications, Nowowiejska 15/17, Warszawa, Poland,

Bibliografia

• 1. J. A. Brzozowski, T. Łuba: Decomposition of Boolean Functions Specified by Cubes. Journal of Multi-Valued Logic and Soft Computing 9 (2003): 377-417.
• 2. S. C. Chang, M. Marek-Sadowska, T. T. Hwang: Technology Mapping for TLU FPGAs Based on Decomposition of Binary Decision Diagrams. IEEE Trans, on CAD 15, no. 10 (October 1996): 1226-1236.
• 3. G. De Micheli: Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
• 4. Y. Lai, K. R. Pan, M. Pedram: OBDD-based function decomposition: algorithms and implementation. IEEE Trans, on CAD of Integrated Circuits and Systems 15, no. 8 (1996): 977-990.
• 5. T. Łuba, H. Selvaraj: General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis. VLSI Design, Special Issue on Decompositions in VLSI Design 3(3-4) (1995): 289-300.
• 6. M. Nowicka, T. Luba, M. Rawski: FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation. Sixth International Conference on Advanced Computer Systems. Szczecin, 1999. 502-509.
• 7. M. Perkowski, et al.: Decomposition of Multiple-Valued Relations. Proc. of International Symposium on Multiple-Valued Logic. Antigonish, 1997. 13-18.
• 8. M. Perkowski: A Survey of Literature on Function Decomposition. Final Report for Summer Faculty Research Program, Air Force Office of Scientific Research, Wright Laboratory, 1994.
• 9. M. Rawski, L. Jóźwiak, T. Łuba: Functional Decomposition with an Efficient Input Support Selection for Sub-functions Based on Information Relationship Measures. Journal of Systems Architecture 47 (2001): 137-155.
• 10. P. Sapiecha, H. Selvaraj, M. Pleban: Decomposition of Boolean Relations and Functionsin Logic Synthesis and Data Analysis. Edited by Wojciech Ziarko and Y Y Yao. Rough Sets and Current Trends in Computing. Springer, 2000. 487-494.
• 11. T. Sasao, M. Matsuura, Y. Iguchi, S. Nagayama: Compact BDD Representations for Multiple-Output Functions and Their Application. ISMVL. 2001. 207-212.
• 12. T. Sasao, M. Fujita: Representations of Discrete Functions. Kluwer Academic Publishers, 1996.
• 13. C. Scholl: Functional Decomposition with Application to FPGA Synthesis. Kluwer Academic Publisher, 2001.
• 14. H. Selwaraj, P. Sapiecha, T. Łuba: Functional Decomposition and Its Applications in Machine Learning and Neural Networks. International Journal of Computational Intelligence and Applications 1, no. 3 (2001): 259-271.
• 15. M. Venkatesan, H. Selvaraj, R. Bignall: Character Recognition using Functional Decomposition. Edited by H. Selvaraj and B. Verma. International Conference on Computational Intelligence and Multimedia Applications. Singapore, 1998. 721-726.
• 16. B. Wurth, U. Schlichtmann, K. Eckl, K. Antreich: Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs. ACM Trans. Design Autom. Electr. Syst. 4, no. 3 (1999): 313-350.