Zero-Error Capacity of P-ary Shift Channels and FIFO Queues

Mladen Kovacevic, Milos Stojakovic, Vincent Y. F. Tan

TL;DR

This paper investigates the theoretical limits of communication over channels where "noise" primarily manifests as symbol shifts, like in magnetic recording or packet queues. The authors introduce two models, the P-ary Shift Channel and a FIFO Queue channel, and derive their zero-error capacities and zero-error detection capacities using novel code constructions. This work provides fundamental insights into reliable communication under these specific, yet common, noise conditions.

What Problem Does This Paper Address?

In many communication and data storage systems, the primary source of error isn't random bit flips, but rather the displacement or delay of symbols. Think of magnetic storage where bits can "smear" or network routers where packets experience unpredictable delays. These "shift" and "queueing" phenomena pose unique challenges for reliable information transmission. Traditional information theory often assumes simpler noise models. This paper aims to characterize the ultimate limits of error-free communication (zero-error capacity) and error detection (zero-error detection capacity) in systems dominated by these shift-based noise mechanisms. They specifically focus on two models: one where particles in a register can be shifted, and another where packets move through a First-In-First-Out (FIFO) queue with random processing times.

Methods

The core of the paper lies in the construction of optimal zero-error codes for the proposed channel models. For the P-ary Shift Channel (Model A), they show that the problem can be reduced to a simpler case with only one type of particle (P=1) and specific shift parameters. They then construct optimal codes by focusing on constant-weight binary sequences and leveraging a geometric interpretation of the problem, relating it to lattice structures. For the FIFO Queue channel (Model B), they adapt similar techniques, again focusing on constant-weight inputs and using a greedy construction for optimal codes. The analysis involves deriving explicit formulas for the sizes of these optimal codes and then taking limits to find the zero-error capacity. They also extend their analysis to include additional noise types and continuous-time versions of these channels.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Shift-based noise is fundamental: The paper highlights that symbol shifts and queueing delays are not niche problems but represent common and important noise models in various real-world systems.
  • Geometric interpretation is powerful: The authors elegantly use geometric representations (simplices, hypercubes) to visualize and construct optimal codes for shift channels, simplifying complex combinatorial problems.
  • Constant-weight codes are key: For these shift-dominated channels, optimal zero-error codes can often be constructed from constant-weight binary sequences, which significantly simplifies the analysis.
  • Capacity depends on shift range and alphabet size: The derived capacities for the shift channels are directly related to the range of possible shifts (K1, K2) and the number of particle types (P).
  • Queueing delays introduce a different trade-off: For FIFO queues, the capacity is influenced by both the processing time distribution and the alphabet size, showing a different behavior than simple shift channels.
  • Zero-error detection is distinct from correction: The paper distinguishes between detecting an error and correcting it, showing that the capacity for detection can be higher than for correction in shift channels.

Key Results

  • P-ary Shift Channel (Model A): The zero-error capacity is determined by a unique positive root of a polynomial equation involving the alphabet size (P) and the shift range (K). Specifically, for ShC(P; K), the capacity is log(r), where r is the root of $x^{K+1} - Px^K - 1 = 0$.
  • FIFO Queue Channel (Model B): The zero-error capacity is given by a formula involving the alphabet size (P), the maximum processing time (K), and the expected processing time ($E[\phi[\kappa]]$). For a P-ary FIFO queue with bounded processing time K and a probability distribution $\phi$, the capacity is $\max\{\frac{\log(P+1)}{E[\phi[\kappa]]+1}, \frac{\log P}{K+1}\}$.
  • Zero-Error Detection: For shift channels, the zero-error detection capacity is shown to be related to the zero-error correction capacity of a related channel with a more restricted shift range. For FIFO queues, the detection capacity is simply $\log(P+1)$, implying that simple counting can detect errors.
  • Continuous-Time Extensions: The paper also provides characterizations for the continuous-time versions of these channels, showing how their capacities behave with respect to emission times and residence/processing times.

Limitations and Future Work

  • Additional Noise: The paper briefly touches upon channels with additional noise (e.g., discrete memoryless channels acting on particles) and provides some results, but a more comprehensive analysis of these compound channels could be explored.
  • Deletions and Reordering: The authors explicitly suggest future work on models that include packet deletions (e.g., due to buffer overflow) or allow for packet reordering. These are noted as being more complex and requiring different analytical tools, especially for multi-type particles.
  • Finite-Length Performance: While the paper focuses on asymptotic capacities, a deeper understanding of finite-length performance and the "penalty" associated with using specific code constructions (like constant-weight codes) could be beneficial.
  • Practical Implementations: The theoretical results provide fundamental limits. Bridging the gap between these theoretical capacities and practical achievable rates in real-world systems would be a valuable next step.

Summary updated

Abstract

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zeroerror capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an n-cell register, where each cell is either empty or contains a particle of one of P possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a P-ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.
BibTeX
@article{kovacevic2017zero,
  author = {Mladen Kovacevic and Milos Stojakovic and Vincent Y. F. Tan},
  title = {{Zero-Error Capacity of P-ary Shift Channels and FIFO Queues}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=cXtzgPHVdV},
}
Figure