Exact and approximate methods for calculating signal and transition probabilities in FSMs

In this paper, we consider the problem of calculating the signal and transition probabilities of the internal nodes of the combinational logic part of a finite state machine (FSM). Given the state transition graph (STG) of the FSM, we first calculate the state probabilities by iteratively solving the Chapman-Kolmogorov equations. Using these probabilities, we then calculate the exact signal and transition probabilities by an implicit state enumeration procedure. For large sequential machines where the STG cannot be explicitly built, we unroll the next state logic k times and estimate the signal probability of the state bits using an OBDD-based approach. The basic computation step consists of solving a system of nonlinear equations. We then use these estimates to approximately calculate signal and transition probabilities of the internal nodes. Our experimental results indicate that the average errors of transition probabilities and power estimation (compared to the exact method) are only 5% and 0.6% respectively when k = 3. This is an order of magnitude improvement in computation accuracy compared to the existing approaches.