APPLICATION OF BIPARTITE GRAPHS FOR ACHIEVING RACE-FREE STATE ASSIGNMENTS

Achieving race-free state assignments is an important objective in the synthesis of asynchronous sequential logic circuits (ASLCs). Traditio nally, adjacency diagrams are used to help identify and resolve race c onditions; however, this approach has a high degree of computational c omplexity. This paper presents an efficient state assignment algorithm that utilizes a pattern matching technique to predict races and to el iminate the need for enumerative searches. More specifically, the race -free state assignment problem is formulated as the embedding of a bip artite connected graph onto an n-cube and achieves a near minimum numb er of state variables. This algorithm has been evaluated using several representative examples. Results show that the developed algorithm pr ovides better performance than existing algorithms. Due to the simplic ity of the bipartite representation of an n-cube, the developed algori thm is suitable for ASLC synthesis that may involve a relatively large number of states.