Idea for symbolic iterator in BDD environment

• Autorzy: Łabiak G.

Warianty tytułu

PL

Koncepcja iteratora symbolicznego w środowisku BDD

• Języki publikacji: EN

Abstrakty

EN

In the paper the concept of symbolic iterator has been presented. The iterator has a task to proceed through a set of states symbolically represented by logic function. The whole is implemented in C/C++ language in CUDD BDD package. Every state from the set corresponds to minterm from the function which is subsequently generated by the iterator. Minterm generation consists in searching BDD tree and producing cube terms covering function minterms. Next, for each cube, the iterator algorithm generates full function minterm. Apart from minterm iterator class declaration, in the paper has been also presented a piece of C++ code demonstrating usage of the symbolic.

PL

W artykule przedstawiono koncepcję iteratora symbolicznego, którego zadaniem jest poruszanie się po zbiorze stanów, symbolicznie zapisanym funkcją logiczną. Całość zaimplementowana jest diagramami BDD z pakietu CUDD, który udostępnia zestaw funkcji i klas w języku C/C++. Zadaniem iteratora jest generowanie mintermów funkcji, co polega na przeglądaniu drzewa BDD funkcji i produkowaniu kostek. Dla każdej kostki algorytm buduje term składający się z brakujących zmiennych, tworząc w ten sposób pełny minterm. W pracy również przedstawiono klasę obiektu iteratora oraz przykładowe wykorzystanie iteratora.

Słowa kluczowe

EN

iterator; BDD; symbolic methods; set of states

PL

iterator; BDD; metody symboliczne; zbiór stanów

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2009
• Tom: R. 85, nr 7
• Strony: 207--210
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Łabiak G.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Podgórna 50, 65-246 Zielona Góra,

Bibliografia

• [1] de Mitcheli G., Synteza i optymalizacja układów cyfrowych, WNT ’98
• [2] Łuba T., Synteza układów logicznych, Wyd. WSISiZ, Warszawa 2001
• [3] Bukowiec A., Barkalov A., Synteza logiczna skończonych automatów stanów z zastosowaniem wielokrotnego kodowania stanów, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, 54(2008), no. 6, 766-769 [CD-ROM]
• [4] Wiśniewska M., Wiśniewski R., Adamski M., Usage of hypergraph theory in decomposition of concurrent automata, Pomiary, Automatyka, Kontrola, 2007, no. 7, 66-68
• [5] Wiśniewski R., Barkalov A., Janiak A., Methods of designing of compositional microprogram control units with mutual memory, Pomiary, Automatyka, Kontrola, 54(2008), no 8, 493-495 [CD-ROM]
• [6] Adamski M., Parallel Controller Implementation using Standard PLD Software, W. R. Moore, W. Luk, (red.), FPGAs, Abingdon EE&CS Books, Abingdon, England, 1991, 296-304
• [7] Biliński K., Application of Petri Nets in parallel controllers design, PhD Thesis, University of Bristol, Electrical and Electronic Engineering Department, Bristol, 1996
• [8] Łabiak G., From statecharts to FSM-description - transformation by means of symbolic methods, Discrete-Event System Design - DESDes '06, Proc. from the 3rd IFAC Workshop, Rydzyna, Polska, 2006, 161-166
• [9] Burch J. R., Clarke E. M., McMillan K. L., and Dill D., Sequential Circuit Verification Using Symbolic Model Checking, Proceedings of the 27th Design Automation Conference, June 1990, 46-51
• [10] Coudert O., Berthet C. and Madre J. C., Verification of Sequential Machines Using Boolean Functional Vectors, IMEC-IFIP Int. Workshop on App. Formal Methods for Correct VLSI Design, Nov. 1989, 111-128
• [11] Somenzi F., CUDD: CU Decision Diagram Package, http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
• [12] Gamma E., Helm R., Johnson R., Vlisslides J., Design Patterns, Addison Wesley, 1995
• [13] Rasiowa H., Wstęp do matematyki współczesnej, PWN 1998
• [14] Minato S.-I.: Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, Boston, 1996
• [15] Shannon C. A., A symbolic analysis of relay and switching circuits, Massachusetts Institute of Technology, 1937
• [16] Lipski W., Kombinatoryka dla programistów, WNT, Warszawa 1989