- Tytuł:
-
Zastosowanie grafu niezgodności i dopełnień w procesie kodowania automatów asynchronicznych
An application of the Incompatibility and Complement Graph to asynchronous FSM coding - Autorzy:
-
Kania, D.
Kulisz, J. - Powiązania:
- https://bibliotekanauki.pl/articles/156212.pdf
- Data publikacji:
- 2008
- Wydawca:
- Stowarzyszenie Inżynierów i Techników Mechaników Polskich
- Tematy:
-
problem pokrycia i dopełnienia
teoria grafów
kodowanie stanów
sekwencyjne układy asynchroniczne
covering and complement problem
graph theory
state assignment
asynchronous FSMs - Opis:
-
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.
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. - Źródło:
-
Pomiary Automatyka Kontrola; 2008, R. 54, nr 8, 8; 486-488
0032-4140 - Pojawia się w:
- Pomiary Automatyka Kontrola
- Dostawca treści:
- Biblioteka Nauki
Artykuł