Modeling and Analysis of Communication Circuit Performance using Markov Chains and Efficient Graph Representations

Tuesday, August 29, 2000 - 9:50am - 10:25am
Keller 3-180
Alper Demir (Alcatel-Lucent Technologies Bell Laboratories)
In high-speed data networks, the bit-error-rate specification on the system can be very stringent, i.e., 10-14. At such error rates, it is not feasible to evaluate the performance of a design using straightforward, simulation based, approaches. Nevertheless performance prediction before actual hardware is built is essential for the design process. This talk describes a stochastic model and an analysis-based, non-Monte-Carlo method for performance evaluation of digital data communication circuits. The analyzed circuit is modeled by a number of interacting finite state machines with inputs described as functions on a Markov chain state-space. The composition of these elements results in a typically very large Markov chain. System performance measures, such as probability of bit errors and rate of synchronization loss, can be evaluated by solving linear problems involving the large Markov chain's transition probability matrix. First, a dedicated multi-grid method used to solve these very large linear problems will be described. The principal bottleneck in such an approach is the size of the Markov chain state-space, which grows exponentially with system complexity. The second part of the talk describes a graph based data structure capable of efficiently storing and manipulating transition probability matrices for several million state Markov chains. The methods are illustrated on a clock-recovery circuit design.