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

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.