Zastosowanie hipergrafów w procesie selekcji implikantów prostych

• Autorzy: Wiśniewski R. , Stefanowicz Ł.

Warianty tytułu

EN

Application of hypergraphs to the prime implicant selection process

• Języki publikacji: PL

Abstrakty

PL

W referacie przedstawiona została nowa koncepcja selekcji implikantów prostych w procesie dwupoziomowej minimalizacji funkcji logicznych. Aktualnie znane metody selekcji bazują na połączeniu metod dokładnych z przybliżonymi. W artykule zaproponowana została nowatorska metoda selekcji, która w całości opiera się na algorytmach dokładnych, poprzez zastosowanie teorii hipergrafów. Najbardziej istotną zaletą proponowanego rozwiązania jest wielomianowa złożoność obliczeniowa całej operacji selekcji, która w przypadku ogólnym ma złożoność wykładniczą.

EN

: In the paper a new idea for the selection of prime implicants is proposed. The method is based on the two-level minimization process of the Boolean functions, according to the Quine-McCluskey approach. Initially, the set of prime implicants for the logic function ought to be calculated. Next, the selection process is applied to achieve the minimal formula. Such an operation is a typical covering problem and in general case it has exponential computational complexity. In the paper we propose a new prime implicants selection method. An idea is based on the hypergraph theory. The prime implicants table is formed as a selection hypergraph. If the selection hypergraph belongs to the Exact Transversal Hypergraph class (xt-class), the solution may be obtained in a polynomial time, which is not possible in a general case. The proposed method is illustrated by an example. All necessary steps are shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function.

Słowa kluczowe

PL

minimalizacja funkcji logicznych; selekcja implikantów prostych; hipergraf; transwersala dokładna

EN

minimization of Boolean functions; selection of prime implicants; hypergraph; exact transversal

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 11
• Strony: 1195--1197
• Opis fizyczny: Bibliogr. 20 poz., schem., wykr., wzory

Twórcy

autor

Wiśniewski R.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra

autor

Stefanowicz Ł.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra

Bibliografia

• [1] De Micheli G.: Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York, NY, 1994.
• [2] Coudert O.: Two-Level Logic Minimization: An Overview, Integration Vol. 17, No. 2, pp. 97-140, Oct. 1994.
• [3] Coudert O., Madre J. C., Fraisse H.: A New Viewpoint on Two-Level Logic Minimization, Proc. 30th Design Automation Conference, Dallas, TX, USA, pp. 625–630, June 1993.
• [4] Maxfield C.: The Design Warrior's Guide to FPGAs, Academic Press, Inc., Orlando, FL, 2004.
• [5] Łuba T.: Synteza układów cyfrowych, WKŁ, Warszawa, 2003.
• [6] Kania D.: Układy logiki programowalnej, PWN, Warszawa, 2012.
• [7] Barkalov A., Titarenko L.: Logic synthesis for FSM-based control units, Lecture Notes in Electrical Engineering, Vol. 53. Springer-Verlag, Berlin, 2009.
• [8] Grobelna I.: Formal verification of embedded logic controller specification with computer deduction in temporal logic, Przegląd Elektrotechniczny, 12a, 40-43, 2011.
• [9] Milik A., Hrynkiewicz E.: Synthesis and implementation of reconfigurable PLC on FPGA platform”, International Journal of Electronics and Telecommunications, 58 (1), 85–94, 2012.
• [10] Quine W. V. O.: The problem of simplifying truth functions, American Math. Monthly, Vol. 59, pp. 521–531, 1952.
• [11] McCluskey E. J.: Introduction to the Theory of Switching Circuits, McGraw-Hill, New York, 1965.
• [12] Nosrati M., Karimi R., Hariri M.: Minimization of Boolean Functions Using Genetic Algorithm, Annals. Computer Science Series, Vol. X, 2012.
• [13] Nosrati M., Hariri M.: An Algorithm for Minimizing of Boolean Functions Based on Graph DS, World Applied Programming Vol. 1 No. 3, p. 209--214, 2011
• [14] Coudert O., Sasao T.: Two-Level Logic Minimization, Logic Synthesis and Verification, S. Hassoun & T. Sasao Editors, Kluwer Academic Publishers, Chapter 1, pp. 167–196, 2001.
• [15] Rudell R. L.: Logic Synthesis for VLSI Design. Rozprawa doktorska, EECS Department, University of California, Berkeley, 1989.
• [16] Eiter T.: Exact Transversal Hypergraphs and Application to Boolean μ-Functions. Journal of Symbolic Computation, Vol. 17, No. 3, pp. 215-225, 1994.
• [17] Wiśniewska M.: Application of hypergraphs to the decomposition of the discrete systems, Lecture Notes in Control and Computer Science, Vol. 23. Univ. of Zielona Góra Press, Zielona Góra, 2012.
• [18] Berge C.: Graphs and Hypergraph. Amsterdam: North-Hols.r Mathematical Library, 1976.
• [19] Knuth D.: Dancing Links, Stanford University, 2000, http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
• [20] Adamski M., Karatkievich A., Węgrzyn M. (ed.): Design of Embeded Control Systems. NY, Springer Science, 2005.