Individual sequence limits on error rates for adaptable communication channels
Fano's Inequality and Channel Capacity in the Individual-Sequence Regime
Information Theory
Summary
This paper looks at how well data can be sent through a communication channel that might behave in any unpredictable way. The authors created a new version of a classic information theory rule (Fano's inequality) that uses a specific measure of sequence complexity instead of randomness. They show that if you want to send information reliably, the rate must not exceed a new defined capacity based on this complexity. For a certain kind of channel where output changes predictably with input and noise, they prove you can achieve this capacity without knowing the channel details in advance.
What this means in practice
- •For communications engineers: Design error correction methods for channels with unknown or changing behavior based on individual sequence complexity limits.
- •For network protocol developers: Develop universal decoding algorithms that require no prior channel knowledge and ensure reliable communication under worst-case noise conditions.
A theory result. No direct application yet.
Authors
Neri Merhav
Abstract
We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.