An Optimal Clustering Approach Applying to Asynchronous Finite-State Machine Design

A novel concept of the optimal generation of code signatures for asynchronous finite-state machine by dint of preliminary clustering of state transition diagram is proposed and its encoding improvement by the criterion of simplifying of computational complexity under increasing of states number is theoretically proven. A three-stage combined sorting algorithm, which splits state transition diagram into set of clusters in exhaustive way and selects the optimal, finds optimal encoding configuration within a single cluster, and matches the state signatures codes between adjacent states located in different clusters, is developed and implemented as a software module. An objective function, which allow evaluating the degree clustering optimality, is composed and validated. A concept of code signature forming by concatenation of assigned cluster code during clustering and intra-cluster arc code generated according to a “differs one bit switching” rule is implemented and validated. Testing of developed algorithm on randomly generated samples is performed, and the absence of encoding errors together with the minimal encoding redundancy both on signature length and on transitional states amount is demonstrated.