Input Variable Partition Method in Functional Decomposition based on Shannon Expansion

• Autorzy: Morawiecki P. , Rawski M.

Warianty tytułu

PL

Metoda doboru zmiennych w dekompozycji funkcjonalnej bazująca na ekspansji Shannona

• Języki publikacji: EN

Abstrakty

EN

Functional decomposition has important applications in many fields of modern engineering and science. The practical usefulness of decomposition-based methods for very complex systems is restricted by computational complexity and memory requirements of existing algorithms. Efficiency of currently used decomposition algorithms is dependent on the size of decomposed functions. One of the crucial parts of functional decomposition is the input variable partitioning. In this paper, the "divide-and-conquer" paradigm is used to propose a new input variable partitioning method. It has to be stressed that proposed method is not the input variable partition algorithm itself. It should be treated as a general scheme, method which can be combined with the algorithms generating input variable partitions (systematically, heuristically or by algorithms based on BDD).

PL

Dekompozycja funkcjonalna ma zastosowania w wielu dziedzinach współczesnej nauki. W artykule zostaje zaproponowany algorytm, który pozwoli na skrócenie czasu obliczeń na etapie doboru zmiennych w dekompozycji funkcjonalnej. Opisana metoda bazuje na paradygmacie "dziel i rządź", wykorzystuje ekspansję Shannona. Należy podkreślić, iż zaproponowana metoda nie jest algorytmem doboru zmiennych samym w sobie. Stanowi ogólny schemat, który może być wykorzystany wraz z innymi metodami doboru zmiennych (metoda systematyczna, metody heurystyczne, metody oparte na

Słowa kluczowe

EN

functional decomposition; Shannon expansion; logic synthesis

PL

dekompozycja funkcjonalna; ekspansja Shannona; synteza logiczna

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 121--123
• Opis fizyczny: Bibliogr. 10 poz., tab., wzory

Twórcy

autor

Morawiecki P.

autor

Rawski M.

• Zakład Informatyki, Wyższa Szkoła Handlowa, Kielce,

Bibliografia

• [1] M. Burns, M. Perkowski, L. Jóźwiak, “An Efficient Approach to Decomposition of Multi-Output Boolean Functions with Large Set of Bound Variables”, Proc. Of EUROMICRO`98 Conference, Vasteras, Sweden, 1998.
• [2] J. A. Brzozowski, and T. Łuba, “Decomposition of Boolean Functions Specified by Cubes”, Journal of Multiple-Valued Logic and Soft Computing, Vol. 9, Old City Publishing, Inc., Philadelphia, 2003, pp. 377-417.
• [3] T. Łuba, H. Selvaraj, “A General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis”, VLSI Design, Special Issue on Decompositions in VLSI Design, vol. 3, Nos. 3-4, 1995, pp. 289-300.
• [4] T. Łuba, H. Selvaraj, M. Nowicka, A. Kraśniewski, „Balanced multilevel decomposition and its applications in FPGA-based synthesis”, In: Logic and Architecture Synthesis (G. Saucier, A /Vignette ed.), Chapman & Hall, 1995.
• [5] M. Nowicka, T. Łuba, and. M. Rawski, “FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation”, Proc. Of Sixth International Conference on Advanced Computer Systems, Szczecin, 1999, pp. 502-509.
• [6] M. Rawski, L. Jóźwiak, and T. Łuba, „Functional Decomposition with an Efficient Input Support Selection for Sub-functions Based on Information Relationship Measures”, Journal of Systems Architecture 47, 2001, 2001, pp. 137-155.
• [7] M. Rawski, L. Jóźwiak, M. Nowicka, T. Łuba, „Non-Disjoint Decomposition of Boolean Functions and Its Application in FPGAoriented Technology Mapping, Proc. of the EUROMICRO”97Conference, Budapest, Hungary, Sept. 1-4, 1997, pp. 24-30, IEEE Computer Society Press.
• [8] M. Rawski, H. Selvaraj, T. Łuba, “An application of functional decomposition in ROM-based FSM implementation in FPGA devices”, Journal of Systems Architecture, Vol. 51 (2005), ELSEVIER, 2005, pp. 424-434.
• [9] M. Rawski, H. Selvaraj, P. Morawiecki, “Efficient Method of Input Variable Partitioning in Functional Decomposition Based on Evolutionary Algorithms”, Proc. of EUROMICRO Symposium on Digital System Design`04, Rennes, France, 2004, pp. 136-143.
• [10] M. Rawski, P. Morawiecki, H. Selvaraj, “Decomposition of Combinational Circuits Described by Large Truth Tables”, Proceedings of Eighteenth International Conference on Systems Engineering, Coventry, United Kingdom, September 5-7 2006, pp. 401-406.