On the achievable information rates of finite-state input two-dimensional channels with memory

The achievable information rate of finite-state input two-dimensional (2-D) channels with memory is an open problem, which is relevant, e.g., for inter-symbol-interference (ISI) channels and cellular multiple-access channels. We propose a method for simulation-based computation of such information rates. We first draw a connection between the Shannon-theoretic information rate and the statistical mechanics notion of free energy. Since the free energy of such systems is intractable, we approximate it using the cluster variation method, implemented via generalized belief propagation. The derived, fully tractable, algorithm is shown to provide a practically accurate estimate of the information rate. In our experimental study we calculate the information rates of 2-D ISI channels and of hexagonal Wyner cellular networks with binary inputs, for which formerly only bounds were known

• Publication year

  2005

• Venue

  Proceedings. International Symposium on Information Theory, 2005. ISIT 2005.

• Publication date

  2005-02-18

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2005.1523769arXiv cs/0502077
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Simulation-Based Computation of Information Rates for Channels With Memory

  2006cited by this paper
• On the symmetric information rate of two-dimensional finite-state ISI channels

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Constructing free-energy approximations and generalized belief propagation algorithms

  2005cited by this paper
• Generalized belief propagation receiver for near-optimal detection of two-dimensional channels with memory

  2004cited by this paper
• On the symmetric information rate of two-dimensional finite state ISI channels

  2003influential reference
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors

  2002cited by this paper
• Markov sources achieve the feedback capacity of finite-state machine channels

  2002cited by this paper
• On the capacity of Markov sources over noisy channels

  2001cited by this paper
• The intersymbol interference channel: lower bounds on capacity and channel precoding loss

  1996cited by this paper
• Shannon-theoretic approach to a Gaussian cellular multiple-access channel

  1994cited by this paper
• Maximum-likelihood estimation for hidden Markov models

  1992cited by this paper
• Information Rates For A Discrete-time Gaussian Channel With Intersymbol Interference And Stationary Inputs

  1991cited by this paper
• Capacity and information rates of discrete-time channels with memory

  1988cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)

  1974cited by this paper
• Optimal decoding of linear codes for minimizing symbol error rate

  1974cited by this paper

• Energy-Efficient and Reliable Deployment Models for Hybrid Underwater Acoustic Sensor Networks with a Mobile Gateway

  2024cites this paper
• Solutions for Underwater Communication and Positioning Network Development

  2019cites this paper
• Optimal Detector for Multilevel NAND Flash Memory Channels with Intercell Interference

  2014cites this paper
• Linear programming based detectors for two-dimensional intersymbol interference channels

  2011cites this paper
• Discrete-Input Two-Dimensional Gaussian Channels With Memory: Estimation and Information Rates Via Graphical Models and Statistical Mechanics

  2008cites this paper
• Simulation-based estimation of the partition function and the information rate of two-dimensional models

  2008cites this paper
• Towards Efficient Detection of Two-Dimensional Intersymbol Interference Channels

  2008cites this paper
• Comments on Why Generalized BP Serves So Remarkably in 2-D Channels

  2007cites this paper
• Simulation-Based Computation of Information Rates for Channels With Memory

  2006cites this paper
• Information-Theoretic Limits of Two-Dimensional Optical Recording Channels

  2006cites this paper
• On graphical models for communications and machine learning: algorithms, bounds, and analog implementation

  2006cites this paper
• Computation of Information Rates by Particle Methods

  2004cites this paper