Performance modeling and evaluation

At ZRL there is extensive knowledge of and simulation experience with graphical models, including factor graphs and Bayesan belief networks.

In particular this means probabilistic inference in graphical models using the probability propagation approach known as the "belief propagation algorithm" or the "sum product algorithm".

The applications of such graphical models with sometimes millions of nodes are

The team at ZRL has particularly vast experience with the latter application.

Deep Computing technology is used for performance evaluation in terms of probability of error or failure of communication and storage systems. The ZRL team has particular expertise with Monte Carlo simulations of such complex systems. These extensive simulations involve adaptive structures and complex algorithms that must be validated over extremely long sequences of excitation signals.

There are many examples of graphical models, including Markov random fields, Bayesian networks, chain graphs, and factor graphs. Not only does the graphical representation capture the probabilistic structure, it forms a framework for computing useful probabilities.

A particular application of graphical models is the probabilistic decoding of channel codes to enhance the performance of digital communications systems or to increase the reliability of data retrieval in a data storage system. Probabilistic decoders are designed to make as much use as possible of the real-valued signal. The goal of probabilistic decoding is either maximum-likelihood sequence detection or maximum a posteriori bit detection.

The IBM Zurich Research Laboratory has developed algorithms for decoding novel channel codes such as low-density parity-check codes and turbo codes. We have shown how graphical models can be used to describe probabilistic structures for channel coding schemes, and how the inference algorithm, such as "belief propagation", that make use of this structure can be used for probabilistic decoding.

A graphical model representing the parity check matrix of a low-density parity-check code is shown in the illustration (code example from D. Hösli, E. Svensson, and D. Arnold, "High-Rate Low-Density Parity-Check Codes: Construction and Application," in Proc. of 2nd International Symposium on Turbo Codes & Related Topics, Brest, France, Sept. 4-7, 2000, pp. 447 - 450).