Zastosowanie grafu niezgodności i dopełnień w procesie kodowania automatów asynchronicznych

• Autorzy: Kania D. , Kulisz J.

Warianty tytułu

EN

An application of the Incompatibility and Complement Graph to asynchronous FSM coding

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono przykład zastosowania nowego rodzaj grafu - grafu niezgodności i dopełnień. Specyficzną cechą tego grafu jest to, że zawiera on dwa rodzaje krawędzi: krawędzie skojarzone z relacjami niezgodności oraz krawędzie skojarzone z relacjami dopełniania. Graf może być wykorzystywany w szeregu problemów optymalizacyjnych, w których rozważane są relacje niegodności i dopełniania wzorców bitowych. W artykule zaprezentowano wykorzystanie grafu w procesie kodowania stanów asynchronicznych układów sekwencyjnych. Przedstawiono też odpowiednie algorytmy tworzenia grafu i kolorowania jego wierzchołków.

EN

The paper presents an application of a novel concept of graph - the Incompatibility and Complement Graph. A specific feature of the graph is that it contains two kinds of edges: connecting mutually incompatible nodes, and connecting mutually complementing nodes [3, 4]. The graph can be useful in certain class of optimization problems, in which compatibility of bit patterns in both the true and the complemented form has to be analyzed [5]. An example of such a problem is covering analysis in asynchronous FSM coding. The relevant coding method was presented by Tracey [1]. The method consists of several steps. In one of the steps a Boolean matrix is built, describing partitions of the relevant state set, which are required to provide coding free form critical races. In the subsequent step the Boolean matrix has to be reduced. During this step compatibility of the matrix rows both in the true, and the complemented form has to be analysed. For this purpose the Row Incompatibility and Complement graph can be used. The paper presents a simple example explaining the method. Appropriate algorithms for the graph building (Fig. 3) and colouring (Fig. 4) are also presented.

Słowa kluczowe

PL

problem pokrycia i dopełnienia; teoria grafów; kodowanie stanów; sekwencyjne układy asynchroniczne

EN

covering and complement problem; graph theory; state assignment; asynchronous FSMs

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 486--488
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Kania D.

autor

Kulisz J.

• Instytut Elektroniki, Politechnika Śląska w Gliwicach,

Bibliografia

• [1] J. Tracey, Internal state assignments for asynchronous sequential machines, IEEE Transactions on Electronic Computer, Vol. EC-15, NO. 4, August 1966, pp. 551-560.
• [2] D. Kania, Synteza logiczna przeznaczona dla matrycowych struktur programowalnych typu PAL, Zeszyty Naukowe Politechniki Śląskiej, Nr 1619, Wydawnictwo Politechniki Śląskiej, Gliwice 2004.
• [3] D. Kania, J. Kulisz, Logic synthesis for PAL-based CPLD-s based on two-stage decomposition, The Journal of Systems and Software 80, 2007, pp. 1129-1141.
• [4] D. Kania, J. Kulisz, A. Milik, A novel method of two-stage decomposition dedicated for PAL-based CPLDs, Proceedings of Euromicro Symposium on Digital System Design, IEEE Computer Society Press, Porto, September, 2005, pp. 114-121.
• [5] D. Kania, J. Kulisz, The row incompatibility and complement graph – a novel concept of graph for decomposition, Programmable Devices and Embedded Systems, PDES 2006, Brno 14-16 February, 2006, pp. 169-173.
• [6] D. Kania, W. Grabiec, Synteza logiczna przeznaczona dla struktur CPLD z elementami XOR, Pomiary, Automatyka, Kontrola vol. 53, nr 7, 2007, ss. 54-56.
• [7] D. Kania, W. Grabiec, Synteza logiczna dla struktur CPLD typu PAL wykorzystująca elementy XOR, Biuletyn WAT, Vol. LVI 3, Nr 3, (647), 2007, ss. 229-241.