ε-Capacities and Second-Order Coding Rates for Channels with General State

Marco Tomamichel, Vincent Yan Fu Tan

Abstract

This paper investigates the second-order coding rates for channels with general state information available at both the encoder and decoder. Moving beyond the asymptotic Shannon capacity, the authors characterize the dispersion of such channels under finite blocklength constraints. By employing the information spectrum method and applying the Berry-Esseen theorem to both channel noise and state sequences, they derive general formulas for the second-order backoff from capacity.

Introduction

In information theory, the Shannon capacity represents the maximum rate for reliable communication over a channel given infinite blocklength. However, practical systems operate with finite blocklengths, where performance inevitably deviates from this theoretical limit. This work by Marco Tomamichel and Vincent Y. F. Tan provides a rigorous "second-order" analysis for channels where the environment (the "state") varies over time and is known to both the sender and receiver.

The primary objective is to determine the "dispersion" $V$, which characterizes the rate of convergence to capacity $C$ as the blocklength $n$ increases. Specifically, the maximum achievable rate $R$ for a given error probability $\epsilon$ is approximated as $R \approx C - \sqrt{V/n} \Phi^{-1}(1-\epsilon)$.

System Model

The study focuses on state-dependent channels where the state sequence is arbitrary—potentially non-stationary or non-ergodic.

Block diagram of a channel with state information $S$ available at both the encoder $e$ and decoder $d$.

As shown in the figure above, the message $M$ is encoded into $X$ using knowledge of the state $S$. The channel $W$ produces output $Y$ based on $X$ and $S$. Finally, the decoder $d$ uses both $Y$ and $S$ to reconstruct the message $M'$.

Methods

The authors utilize the Information Spectrum Method, a framework developed by Han and Verdú for analyzing channels that do not necessarily satisfy standard i.i.d. assumptions. Key technical steps include:

  • One-Shot Bounds: Deriving error probability bounds for a single channel use, subsequently extended to sequences of length $n$.
  • Generalized Feinstein’s Lemma: Extending the direct part of the coding theorem to incorporate state information.
  • Berry-Esseen Theorem: Applying this theorem to demonstrate that the distribution of information density—the measure of information a channel output provides about the input—converges to a Gaussian distribution.
  • Double Berry-Esseen Application: A novel contribution involving the application of the Berry-Esseen theorem twice: once for channel noise and once for the randomness of the state sequence itself.

Key Insights and Ideas

A central finding is the Decoupling Effect in the total dispersion $V_{total}$. For i.i.d. states, the dispersion is the sum of the average dispersion of the channel noise and the variance of the capacity across different states: $$V_{total} = E[V(S)] + Var[C(S)]$$

This reinforces the concept of dispersion as "operational variance." In state-dependent channels, performance jitter arises not only from noise but also from the inherent variability in channel quality across different states.

Furthermore, the paper identifies conditions for the Strong Converse Property, providing a simple criterion based on the first and second-order statistics of the state process. This allows engineers to predict if a complex channel will exhibit a sharp capacity threshold.

Key Results

The research establishes several fundamental results:

  1. General Second-Order Rate: The maximum number of bits $M^*$ transmittable with error $\epsilon$ is given by: $$\log M^*(n, \epsilon) \approx nC + \sqrt{n V_{total}} \Phi^{-1}(\epsilon)$$
  2. Markov State Dispersion: A closed-form expression for dispersion in Markovian states is derived, accounting for the sequence's mixing time.
  3. Mixed Channel Discontinuity: The authors demonstrate that for mixed channels, the $\epsilon$-capacity can be discontinuous, exhibiting jumps at values corresponding to the probability weights of sub-channels.

Limitations and Future Work

While the paper provides a comprehensive framework, several avenues for future research remain. The current analysis assumes non-causal knowledge of the state, whereas many real-time systems only possess causal information. Additionally, the results are derived for finite state alphabets; extending these to continuous spaces, such as Gaussian fading channels, is a logical next step. Finally, incorporating second-order cost constraints (e.g., power limits) into these specific state-dependent models remains an open challenge.

Summary updated

BibTeX
@article{tomamichel2014capacities,
  author = {Marco Tomamichel and Vincent Yan Fu Tan},
  title = {{ε-Capacities and Second-Order Coding Rates for Channels with General State}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=MQEayons5TR},
}
Figure