A REGION-BASED THEORY FOR STATE ASSIGNMENT IN SPEED-INDEPENDENT CIRCUITS

State assignment problems still need satisfactory solutions to make as ynchronous circuit synthesis more practical, A well-known example of s uch a problem is that of complete state coding (CSC), which happens wh en a pair of different states in a specification has the same binary e ncoding, A standard way to approach state coding conflicts is to inser t new state signals into the original specification in such a way that the original behavior remains intact, This paper proposes a method wh ich improves over existing approaches by coupling generality, optimali ty, and efficiency, The method is based on the use of a class of ''gro und objects,'' called regions, that play the role of a bridge between state-based specifications (transition systems, TS's) and event-based specifications (signal transition graphs, STG's). We need to deal with both types of specification because designers usually prefer a timing diagram-like notation, such as STG, while optimization and cost analy sis work better at the state level, A region in a transition system is a set of states that corresponds to a place in an STG (or the underly ing Petri net), Regions are tightly connected with a set of properties that are to be preserved across the state encoding process, namely, 1 ) trace equivalence between the original and the encoded specification , and 2) implementability as a speed-independent circuit, We will buil d on a theoretical body of work that has shown the significance of reg ions for such property-preserving transformations, and describe a set of algorithms aimed at efficiently solving the encoding problem, The a lgorithms have been implemented in a software tool called petrify, Unl ike many existing tools, petrify represents the encoded specification as an STG, This significantly improves the readability of the result ( compared to a state-based description in which concurrency is represen ted implicitly by interleaving), and allows the designer to be more cl osely involved in the synthesis process, The efficiency of the method is demonstrated on a number of ''difficult'' examples.