Zero-Error Capacity of a Class of Timing Channels

Abstract

We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) Time is slotted, 2) at most $N$ "particles" are sent in each time slot, 3) every particle is delayed in the channel for a number of slots chosen randomly from the set $\{0,1,\dots ,K\}$, and 4) the particles are identical. It is shown that the zero-error capacity of this channel is $\log r$, where $r$ is the unique positive real root of the polynomial $x^{K+1}-x^K-N$. Capacity-achieving codes are explicitly constructed, and a linear-time decoding algorithm for these codes devised. In the particular case $N=1$, $K=1$, the capacity is equal to $\log \varphi$, where $\varphi =(1+\sqrt{5})/2$ is the golden ratio, and the constructed codes give another interpretation of the Fibonacci sequence.

5 pages (double-column), 3 figures. v3: Section IV.1 from v2 is replaced with Remark 1, and Section IV.2 is removed. Accepted for publication in IEEE Transactions on Information Theory

References in corpus (1)

• Interactive Joint Transfer of Energy and Information

Cited by in corpus (10)

• A Comprehensive Survey of Recent Advancements in Molecular Communication
• Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
• Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues
• Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences
• A Note on Parallel Asynchronous Channels with Arbitrary Skews
• Optimal Error-Detecting Codes for General Asymmetric Channels via Sperner Theory
• Variable-Length Coding for Zero-Error Channel Capacity
• The Crossover-Distance for ISI-Correcting Decoding of Convolutional Codes in Diffusion-Based Molecular Communications
• Information Theory of Molecular Communication: Directions and Challenges
• Master's thesis: Permutations With Restricted Movement