Cycle-Based Decomposition of Markov Chains With Applications to Low-Power Synthesis and Sequence Compaction for Finite State Machines

This paper advances the state of the art by presenting a well-founded mathematical framework for modeling and manipulating Markov processes. The key idea is based on the fact that a Markov process can be decomposed into a collection of directed cycles with positive weights, which are proportional to the probability of the cycle traversals in a random walk. Two applications of this new formalism in the computer-aided design area are studied. In the first application, the authors present a new state assignment technique to reduce dynamic power consumption in finite state machines. The technique comprises of first decomposing the state machine into a set of cycles and then performing a state assignment by using Gray codes. The proposed encoding algorithm reduces power consumption by an average of 15%. The second application is sequence compaction for improving the efficiency of dynamic power simulators. The proposed method is based on the cycle decomposition of the Markov process representing the given input sequence and then selecting a subset of these cycles to construct the compacted sequence