Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Math Modeling »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

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

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

Bell Labs

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.

Modeling and Analysis of Noise in Integrated Circuits and Systems