Dekompozycja symboliczna wielowartościowych funkcji implementowanych w technologii FPGA

• Autorzy: Wiśniewski M. , Deniziak S.

Warianty tytułu

EN

Symbolic decomposition of multi-valued functions implemented in FPGAs

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono metody dekompozycji wielowartościowych funkcji logicznych z przeznaczeniem do implementacji w układach FPGA opartych o komórki LUT. Zaprezentowana metodologia obejmuje algorytmy dekompozycji oraz kodowania funkcji symbolicznych, omówione zostały również zastosowania tej techniki do kodowania stanów oraz logicznej sieci wielowartościowej.

EN

The paper presets methods used in decomposition of multi-valued logic functions for LUT-based FPGAs. The methodology consists of algorithm of decomposition and coding technique of symbolic functions as well as using of this method for state encoding and decomposition of multi-valued logic network is presented.

Słowa kluczowe

PL

dekompozycja; FPGA; kodowanie; logika wielowartościowa

EN

decomposition; encoding; FPGA; multi-valued logic

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Informatyka
• Rocznik: 2011
• Tom: R. 108, z. 1-I
• Strony: 109--128
• Opis fizyczny: Bibliogr. 28 poz.,Rys., wz., tab.,

Twórcy

autor

Wiśniewski M.

autor

Deniziak S.

• Katedra Informatyki, Wydział Elektrotechniki, Automatyki i Informatyki, Politechnika Świętokrzyska

Bibliografia

• [1] Brzozowski J., Łuba T., Decomposition of Boolean Functions Specified by Cubes, Journal of Mult.-Valued Logic & Soft Computing, Vol. 9, 2003, 377-417.
• [2] Deniziak S., Wiśniewski M., A symbolic RTL synthesis for LUT-based FPGAs, Design and Diagnostics of Electronic Circuits & Systems, 102-107.
• [3] Ashar P., Devadas S., Newton A.R., Sequential Logic Synthesis, Kluwer Academic Publisher, Norwell 1992.
• [4] Brayton R.K., Khatri S., Multi-valued Logic Synthesis, Proc. of the International Conference on VLSI Design, 1999, 196-205.
• [5] Deniziak S., Wiśniewski M., An Integrated Input Encoding and Symbolic Functional Decomposition for LUT-Based FPGAs, IEEE DDECS 2008, 22-25.
• [6] Saldanha A., Villa T., Brayton R.K., Sangiovanni-Vincentelli A., Satisfaction of input and output encoding constraints, IEEE Trans. on CAD, Vol. 13, No. 5, 1994, 589-602.
• [7] Martinez M., Avedillo M., Quintana J., Huertas J., COPAS: A New Algorithm for the Partial Input Encoding Problem, VLSI Design, Vol. 14 (2), 2002, 171-181.
• [8] Martinez M., Avedillo M., Quintana J., Huertas J., An Algorithm for Face-Constrained Encoding of Symbols Using Minimum Code Length, Proc of the DATE, 1999.
• [9] Yang S., Cieselski M., Optimum and suboptimum algorithms for input encoding and its relationship to logic minimization, IEEE Trans. on CAD 10(1), 1991, 4-12.
• [10] Malik S., Lavagno L., Brayton R.K., Symbolic Minimization of Multilevel Logic and the Input Encoding Problem, IEEE Trans. on CAD, Vol. 11, No. 7, 1992.
• [11] Brzozowski J., Lou J., Blanket algebra for multiple-valued function decomposition, Intern. Workshop on Formal Languages and Computer Systems 1997, in. Algebraic Engineering, C.L. Nehaniv and M. Ito, eds. World Scientific, 1999, 262-276.
• [12] Murgai R., Brayton R.K., Sangiovanni-Vincentelli A., Optimum Functional Decomposition Using Encoding, Proc. of the DAC, 1994, 408-414.
• [13] Burns M., Perkowski M., Grygiel S., Jóźwiak L., An Efficient and Effective Approach to Column-Based Input/Output Encoding in Functional Decomposition, Proc. of the 3rd International Workshop on Boolean Problems, 1998, 19-29.
• [14] Muthukumar V., An Improved Input-Output Encoding Approach for Functional Decomposition, Proc. of the Euromicro DSD, 2001.
• [15] Mishchenko A., Brayton R.K., A Boolean Paradigm in MultiValued Logic Synthesis, Proc. of the IWLS, 2002.
• [16] Mishchenko A., Sasao T., Encoding of Boolean Functions and Its Application to LUT Cascade Synthesis, Proc. of the IWLS, 2002.
• [17] Deniziak S., Kodowanie stanów dla układów FPD o architekturze opartej o komórki LUT, VII Krajowa Konferencja Reprogramowalne Układy Cyfrowe, 2004, 19-26.
• [18] Rawski M., Selvaraj H., Łuba T., Szotkowski P., Application of Symbolic Functional Decomposition Concept in FSM Implementation targeting FPGA devices, 6th International Conference on Computational Intelligence and Multimedia Applications, ICCIMA 2005, Las Vegas, Nevada, August 16–18, 2005, 153-158.
• [19] Szotkowski P., Rawski M., Symbolic Functional Decomposition Algorithm for FSM Implementation, Int. Conf. on ,,Comuter as a Tools”, EUROCON, 2007.
• [20] Szotkowski P., Rawski M., A Graph-Based Symbolic Functional Decomposition Algorithm for FSM Implementation, Int. Conf. on Human System Interactivus, 2008, 34-39.
• [21] Szotkowski P., Rawski M., Improvements to Symbolic Functional Decomposition Algorithm for FSM Implementation in FPGA Devices, Electronics and Telecomunications Quarterly, 55(2), 2009, 335-354.
• [22] Szotkowski P., Rawski M., Selvaraj H., A Graph-Based Approach to Symbolic Functional Decomposition of FSM, System Science, 35(2), 2009, 41-47.
• [23] Nowicka M., Łuba T., Rawski M., FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation, Proc. of the 6th Intern. Conf. on ACS, Szczecin 1999.
• [24] Altera Corporation, Quartus II Software.
• [25] Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification (http://www.eecs.berkeley.edu/ ~alanmi/abc/).
• [26] Lin B., Newton A.R., Synthesis of Multiple-Level Logic from Symbolic High-Level Description Languages, IFIP International Conference on VLSI, 1989, 187-196.
• [27] Villla T., Sangiovanni-Vincentelli A., NOVA: State Assignment for Finite State Machines for Optimal Two-level Logic Implementation, IEEE Transactions on CAD/ICAS, Vol. C-9, No. 9, 1990, 905-924.
• [28] Hartmanis J., Stearns R.E., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Englewood Cliffs, New Jersey 1966.