Badanie heurystycznego podejścia do minimalizacji niezupełnych wielowartościowych funkcji logicznych w klasie wielomianów Reeda-Mullera

• Autorzy: Grzegorz Hołowiński

Warianty tytułu

Examination of Heuristic Approach for Minimization of Incompletely Specified Multi-valued Functions in Reed-Muller Domain

• Języki publikacji: PL

Abstrakty

Opisano heurystyczne podejście do minimalizacji wielowartościowych funkcji logicznych. Zaproponowano zastosowanie algorytmu heurystycznego do wyszukiwania quasi-optymalnych form wielomianowych Reeda-Mullera. Szybkie przeszukiwanie heurystyczne umożliwia minimalizację niezupełnych wielowartościowych funkcji logicznych o dużej liczbie zmiennych (kilkaset) i wartości określonych już na komputerach klasy PC. (abstrakt oryginalny)

EN

One of the phases of combination circuits design is logic functions optimization. In this paper the heuristic approach for multi-valued logic function is shown. Approach to seek for quasi-optimal Reed-Muller polynomials with using of heuristic algorithm is proposed. This quick heuristic search allows to minimize incompletely specified multi-valued logic functions with great number (hundreds) of variables and specified values of function on standard PC. (original abstract)

Słowa kluczowe

PL

Logika wielowartościowa; Algorytmy

EN

Many-valued logic; Algorithms

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2000
• Numer: nr 1
• Strony: 35--56

Twórcy

autor

Grzegorz Hołowiński

• Politechnika Szczecińska

Bibliografia

• [1] BRAYTON R.K., HACHTEL G.D., MCMULLEN C.T., SANGIOVANNI-VINCENTELLI A., Logic Minimization Algorithms for VLSI Synthesis, Boston, MA, Kluwer, 1984.
• [2] BRAYTON R.K., RUDELL R., SANGIOVANNI-VINCENTELLI A.L., and WANG A.R., MIS: A Multiple-level Logic Minimization, IEE Trans. CAD, 1987, pp. 1062-1081.
• [3] CHANG C.C., FALKOWSKI B.J., Flexible Optimization of Fixed Polarity Reed-Muller Expansions for Multiple output Completely and Incompletely Specified Boolean Functions, Proc. of the Asia and South Pacific Design Automation Conf., Chiba, Japonia, 1995, pp. 335-340.
• [4] CHEN LIANG-CHIA, TWU HONG-TAY, Synthesis of Multilevel NAND Gate Circuits For Incompletely Specified Multi-Output Boolean Functions and CAD Using Permissible Cubes and PCRM Graphs, Int. J. Electronics, Vol. 78, No. 2, 1995, pp. 303-316.
• [5] FALKOWSKI B.J., CHANG C.H., Efficient Algorithms for the Calculation of Arithmetic Spectrum from OBDD and Synthesis of OBDD from Arithmetic Spectrum for Incompletely Specified Boolean Functions, Proc. 27th IEEE Int. Symp. on Circuits and Systems, London, UK, 1994, Vol. 1, pp. 197-200.
• [6] FALKOWSKI B.J., HOŁOWIŃSKI G., MAŁECKI K., Effective Minimization of Logic Functions in Reed-Muller Domain, Proc. of the Int. Conf. on Applications of Computer Systems (ACS'97), Szczecin, Polska, 1997.
• [7] FALKOWSKI B.J., RAHARDJA S., Fast Construction of Polarity Coefficient Matrices for Fixed Polarity Quaternary Reed-Muller Expansions, Proc. Fifth Int. Workshop on Spectral Techniques, Eds. C. Moraga, etc., China, 1994, pp. 220-225.
• [8] HOŁOWIŃSKI G., Algorytmy minimalizacji nie dokładnie określonych wielowartościowych funkcji logicznych w klasie Reeda-Mullera i ich porównanie, XIX Międzynarodowe sympozjum naukowe studentów i młodych pracowników nauki, Zielona Góra, Polska, 1997.
• [9] HOŁOWIŃSKI G., SHMERKO V., YANUSHKEVICH S., Parallel and Distributed Realization of Irredundant Minimization of MVL Functions, Proc. Of the International Workshop on Post Binary Ultra-Large Scale Integration, Antigonish, Nova Scotia, Kanada, 1997, pp. 51-52.
• [10] HOŁOWIŃSKI G., YANUSHKEVICH S., Fast Heuristic Minimization of MVL Functions in Generalized Reed-Muller Domain, Proc. of the Int. Conf. on Applications of Computer Systems (ACS'96), Editor: J. Sołdek, Szczecin, Polska, 1996, pp. 57-64.
• [11] HOŁOWIŃSKI G., Algorytmy syntezy kombinacyjnych układów logicznych na elementach wielowartościowych, Praca doktorska, Instytut Informatyki Politechniki Szczecińskiej, 1998, 155.
• [12] HOŁOWIŃSKI G., KOŁODZIEJCZYK J., Zastosowanie techniki obliczeń genetycznych w algorytmie minimalizacji funkcji logicznych w klasie wielomianów Reeda-Mullera na etapie doboru optymalnego produktu, Materiały IV Sesji Naukowej Informatyki, Szczecin, 241-248.
• [13] JAIN A.K., BOLTON R.J., ABD-EL-BARR М.H., CMOS Multiple-Valued Logic Design. Part I: Circuit Implementation. Part II: Function Realization, IEEE Trans. Circuits and Systems, Vol. 40, No. 8, 1993, pp. 503-522.
• [14] JAROSZEWICZ S., SHMERKO V., YANUSHKEVICH S., Exact Irredundant Minimal Searching for a Reed-Muller Expansion for an Incompletely Specified MVL Functions, Proc. of the 3rd Int. Conf. on Applications of Computer Systems, Szczecin, Polska, Nov, 1996, pp. 65-74.
• [15] KALGANOVA T., KOCHERGOV E., ZAITSEVA E., YANUSHKEVICH S., A Genetic Approach to Optimise Polynomial Forms of Incompletely Specified MVL Functions, Proc. of the Int. Workshop on Evolutionary Computing, Brighton, UK, 1996, pp. 89-102.
• [16] LEVASHENKO V., ZAITSEVA E., SHAKIRIN A., HOŁOWIŃSKI G., Synthesis of Logic Circuits in Reed-Muller Logic Domain, Proc. of the International Conference on Pattern Recognition and Information Processing (PRIP'97), Minsk, Belarus, 1997, pp. 350-355.
• [17] MILLER J.F., LUCHIAN H., BRADBEER P.G., BARCLAY P.J., Using a Genetic Algorithm for Optimizing Fixed Polarity Reed-Muller Expansions of Boolean Functions, Int. J. Electronics, Vol. 76, No. 4, 1994, pp. 601-609.
• [18] MILLER J., THOMSON P., Minimisation of Reed-Muller Expansions of Boolean Functions using Modern Optimization Methods, Proc. of the Int. Conf. on Computer Aided Design of Discrete Devices, Minsk, Belarus, 1995, pp. 59-68.
• [19] PERKOWSKI M., CHRZANOWSKA-JESKE M., An Exact Algorithm to Minimize Mixed-radix Exclusive Sums of Products for Incompletely Specified Boolean functions, Proc. on ISCAS Int. Symp. on Circuits and Systems, New Orlean, USA, 1990, pp. 1652-1655.
• [20] PERKOWSKI M., A Fundamental Theorem for Exor Circuits, Proc. of IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1993, pp. 52-60.
• [21] ROSZAK T., MAŁECKI K., CHIMIAK J., Some Experiments with Zakrevskij's Algorithm for Minimization Weakly Specified Logic Functions in Arithmetic Polynomials Domain, Proc. of the International Conference on Pattern Recognition and Information Processing (PRIP'97), Mińsk, Belarus, 1997, pp. 340-349.
• [22] SHMERKO V., HOŁOWIŃSKI G., SONG N., KAREN M.D., GANGULY K., SAFRANEK R.J., PERKOWSKI M.A., High-Quality Minimization of Multi-Valued-Input, Binary Output EXOR Sum of Product Expressions for Incompletely Specified Logic Functions, Proc. of the Int. Conf. on Applications of Computer Systems (ACS'97), Szczecin, Polska, 1997.
• [23] SOŁDEK J., YANUSHKEVICH S., Genetic Algorithms in Logic Design, Proc. of the International Conference on Computer-Aided Design of Discrete Devices (CADDD'95), Minsk, Belarus, 1995, pp. 17-25.
• [24] SONG N., PERKOWSKI M., EXORCISM-MV-2: Minimization of Exclusive Sum of Products Expressions for Multiple-Valued Input Incompletely Specified Functions, Proc. of 23-rd Int. Symp. on Multiple-Valued Logic, Sacramento, CA, USA, 1993, pp. 132-137.
• [25] YANUSHKEVICH S., Methods and Algorithms to Synthesize Parallel-Pipelining Processors for Logic Differential Calculus, Dissertation, Minsk Radioengineering Institute, Mińsk, Belarus, 1992, 209 p. (w języku rosyjskim).
• [26] YANUSHKEVICH S., MAŁECKI K., ROSZAK T., HOŁOWIŃSKI G., Modern Achievements in Multi-Valued Logic and Education Aspects of MVL-Design, Editor: V. Shmerko, J. Sołdek, etc., Proc. of the Int. Conf. on New Information Technologies in Education (NITE'96), Minsk, Belarus, 1996, pp. 317-327.
• [27] ZAITSEVA E., HOŁOWIŃSKI G., SHARKIN A., POPEL D., Optimization of Incompletely Specified MVL Functions Using Genetic Algorithm, Proc. of the Int. Conf. on Design Metodologies for Signal Processing (DMSP'96), Zakopane, Polska, 1996, pp. 101-108.
• [28] ZAKREVSKIJ A., TOROPOV N., Optimizing Polynomial Implementation of Incompletely Specified Boolean Functions, Proc. of the Int. Conf. on CAD DD, Minsk, 1995, pp. 93-98.
• [29] ZAKREVSKIJ A., Search Space Reducing: a Superfast Algorithm for Minimum AND/EXOR Implementation of Systems of Weakly Specified Boolean Functions, Proc. of the International Conference on Pattern Recognition and Information Processing (PRAIR'97), Minsk, Belarus, 1997, pp. 327-331.
• [30] ZENG X., PERKOWSKI M., DILL K., SARABI A., Approximate Minimization of Generalized Reed-Muller Forms, Proc. of IFIP WG 10.5 Workshop on Application of the Reed-Muller Canonical Expansion in Circuit Design, Japan, 1995, pp. 221-230.
• [31] ZILIC Z., Towards Spectral Synthesis: Field Expansions for Partial Functions and Logic Modules for FPGAs, Doctor Thesis, 1997, University of Toronto, Canada.
• [32] VARMA D., TRACHTENBERG E., Computation of Reed-Muller Expansions of Incompletely Specified Boolean Functions from Reduced Representations, IEE Proc.-E, Vol. 138, No. 2, 1991, pp. 85-92.