Computing Information Rates by Particle Methods

Introduction

We propose a numerical method to compute the information rate of continuous channels with memory [1]. The latter channel models describe (physical) communications channels that occur a.o. in magnetic storage devices and in wireline (e.g., ISDN) and wireless (e.g., CDMA, 3G) communications systems. Those physical channels are typically affected by phenomena such as phase noise, timing jitter, and fading, which often significantly limit the amount of information that can be communicated through those channels. In practice, it is important to know how much information can maximally be transmitted over a given (physical) channel: until recently, such theoretical limits were mostly of academic interest, since practical communications systems operated far less efficiently. The recent advent of iterative detection and estimation algorithms, however, has dramatically boosted the efficiency of practical communications systems, and state-of-the-art communications systems often operate close to optimally; theoretical performance bounds are now more relevant than ever. And here come information rates into the picture: information rates quantify the maximal amount of information (in bits per channel use) that can be transmitted over a given channel (model) for a given input distribution.

Method

Our algorithm is an extension of a method independently proposed by Arnold et al. [2], Sharma et al. [3], and Pfister et al. [4] for computing the information rate of discrete channels with memory (see also [5] ). That method consists of three steps: (i) one simulates very long channel input and output sequences x and y; (ii) one computes the logarithmic normalization factors ("log-partition functions") log p(y) and log p(y|x); (iii) one concludes with the estimate of the information rate:

Î(X;Y) = 1/n log p(y|x) - 1/n log p(y),

where n is the length of the sequences x and y. The expressions log p(y) and log p(y|x) can be computed by a forward sum-product recursion [6], which may be regarded as forward message passing in the factor graph [6] of the channel model (see Figure 1).

Figure 1: Message passing through the factor graph of the channel model; X and Y denote the input and output of the channel respectively, S stands for the state of the channel.

The key to the extension to continuous channels is particle filtering (a.k.a. "sequential Monte Carlo filtering"). In this type of algorithms, distributions are approximated by a list of particles, as illustrated in Figure 2. In particular, we represent the forward messages in Figure 1 by particle lists.

Figure 2: A probability density function f and its representation as a list of particles.

The statistical properties of our algorithm are well understood: it yields unbiased estimates of the information rates, and the mean squared error of those estimates is upper bounded by an expression that is inversely proportional to the number of particles. This follows directly from the statistical analysis by Del Moral and Doucet [7, Theorem 2, Corollary 2] of particle-based approximations of log partition functions (a.k.a. "logarithmic Lyapunov exponents") .

Examples

As an illustration, we apply the method to a communications channel with phase noise. In particular, we consider the model

Y_k = X_k exp(jΘ_k) + N_k,

where X_k is the complex channel input symbol at time k, Y_k is the corresponding channel output symbol, Θ_k  is the unknown phase, and N_k is white Gaussian noise with known variance σ. For the sake of definiteness, we assume that the channel input alphabet is a 4-PSK constellation, and that the channel input process is independently and uniformly distributed (i.u.d.). We consider two dynamical models for the phase:

• Random-walk phase model:

Θ_k = (Θ_k-1+W_k) mod 2π,

where W_k is white Gaussian noise.

• ARMA phase model:

  Z_k = a₁ Z_k-1+ a₂ Z_k-2 + ... + a_s Z_k-s + b₀ W_k+ b₁ W_k-1 + ... + b_r W_k-r

  Θ_k = Z_k mod 2π,

  where W_k is white Gaussian noise.

Numerical Results

Figure 3 shows the results for the random-walk phase model. Those results where verified by computing the information rates of a model where the phase is quantized (5000 bins); those results agree with the ones of Figure 3 up to the accuracy of the plot.

Figure 4 depicts the estimate of the information rate (for the random-walk phase noise model) as a function of the sequence length n.

Figure 5 shows the results for the ARMA phase model.

Figure 3: Information rates for the random-walk phase noise channel. From top to bottom:  σ = 0 and σ = 0.01 (on top of each other), σ = 0.1, σ = 0.5, and σ = 1.

Figure 4: Estimated information rate (for the random-walk phase noise channel) as a function of the sequence length n, for 10 simulation runs of the particle method (dashed lines) and ten runs of the quantized-phase method (solid lines), for SNR = 10dB and σ = 0.5.

Figure 5: Information rates for the ARMA phase noise channel  with s = 1, r = 2, a₁ = 0.4, and (b_0, b_1, b₂) = (0.3, 0.2, 0.1). From top to bottom:  σ = 0, σ = 0.01, σ = 0.1 (on top of each other), σ = 0.5, and σ = 1.

References

1. J. Dauwels and H.-A. Loeliger, Computation of information rates by particle methods, IEEE Transactions on Information Theory, vol. 54, no. 1, pp. 406–409, Jan. 2008. PDF file, 366kB.

2. D. Arnold and H.-A. Loeliger, On the information rate of binary-input channels with memory, Proc. 2001 IEEE Int. Conf. on Communications, Helsinki, Finland, June 11-14, 2001, pp. 2692-2695.

3. V. Sharma and S. K. Singh, Entropy and channel capacity in the regenerative setup with applications to Markov channels, Proc. 2001 IEEE Int. Symp. Information Theory, Washington, DC, USA, June 24-29, 2001, p. 283.

4. H. D. Pfister, J. B. Soriaga, and P. H. Siegel, On the achievable information rates of finite-state ISI channels, Proc. 2001 IEEE Globecom, San Antonio, TX, Nov. 25-29, 2001, pp. 2992-2996.

5.  D. Arnold, H.-A. Loeliger, P. O. Vontobel, A. Kavčić, and W. Zeng, Simulation-based computation of information rates for channels with memory, IEEE Transactions on Information Theory vol. 52, no. 8, pp. 3498-3508, August 2006.

6. H.-A. Loeliger, An introduction to factor graphs,  IEEE Signal Processing Magazine, Jan. 2004, pp. 28-41.

7. P. Del Moral and A. Doucet, Particle motions in absorbing medium with hard and soft obstacles, Stochastic Analysis and Applications, 2004, vol. 22., no. 5, pp. 1175-1207.

Source Code

We have implemented our particle based algorithm in the programming language C. The source code for each of the two phase models can be downloaded here:

• Random-walk phase model: ZIP file, 108kB.
• ARMA phase model: ZIP file, 109kB.

Installation: open a shell, unzip the files, go to the directory /bin, and type make to compile the source. Use the script start to run the program.

More information can be found in README.txt (contained in each of the two zip-archives).

Please feel free to contact me for further information.

Email: justin(at)dauwels(dot)com

Last updated on  Dec 9, 2008.  Justin Dauwels ©

Back to top