Sequence Compaction for Probabilistic Analysis of Finite-State Machines

Diana Marculescu, Radu Marculescu, Massoud Pedram

Abstract

The objective of this paper is to provide aneffective technique for accurate modeling of the externalinput sequences that affect the behavior of Finite StateMachines (FSMs). The proposed approach relies on adaptivemodeling of binary input streams as Markov sources of fixed-order.The input model itself is derived through a one-passtraversal of the input sequence and can be used to generatean equivalent sequence, much shorter in length compared tothe original sequence. The compacted sequence can besubsequently used with any available simulator to derive thesteady-state and transition probabilities, and the total powerconsumption in the target circuit. As the results demonstrate,large compaction ratios of orders of magnitude can beobtained without a significant loss (less than 3% on average)in the accuracy of estimated values.
BibTeX
@inproceedings{marculescu1997sequence,
  author = {Diana Marculescu and Radu Marculescu and Massoud Pedram},
  title = {{Sequence Compaction for Probabilistic Analysis of Finite-State Machines}},
  booktitle = {DAC},
  year = {1997},
  doi = {10.1145/266021.266027},
}

Loading related content...

Figure