Simple Coding Techniques for Many-Hop Relaying

Yan Hao Ling, Jonathan Scarlett

TL;DR

This paper presents a simple, deterministic, and computationally efficient protocol for relaying information across a long chain of noisy channels. By using a recursive hierarchy of "levels" and majority voting, the authors demonstrate that it is possible to maintain a constant "information velocity"—meaning the transmission time scales linearly with the number of hops—without the exponential complexity required by previous state-of-the-art methods.

What Problem Does This Paper Address?

In network information theory, the "many-hop relay" problem asks: how quickly and reliably can we send a bit of information through a sequence of $m$ noisy nodes?

If each node simply forwards what it receives, the noise (modeled here as a Binary Symmetric Channel or BSC) accumulates, eventually destroying the signal. To prevent this, nodes must perform some form of error correction. However, traditional coding techniques often introduce significant delays. The core challenge is to achieve a positive information velocity ($v(p) > 0$), where the ratio of hops $m$ to transmission time $n$ remains non-vanishing as the chain gets longer.

Prior solutions relied on "tree codes," which are theoretically powerful but practically problematic because they require exponential time to decode. Other simpler methods failed to achieve a truly linear scaling of time versus hops. This paper seeks a "middle ground": a protocol that is both mathematically optimal in its scaling laws and simple enough to implement in linear time.

Methods

The authors introduce a recursive, level-based relaying protocol.

  1. Node Hierarchy: Nodes are assigned "levels" based on their index. A node $i$ is assigned level $l$ if $4^l$ divides $i$ (but $4^{l+1}$ does not). This means most nodes are Level 0, a smaller fraction are Level 1, and so on.
  2. Recursive Processing:
    • Level 0 nodes simply forward the bits they receive.
  3. Level 1 nodes collect 3 bits, perform a majority vote to estimate the original bit, and then repeat that estimate 3 times.
  4. Higher-level nodes perform this logic recursively, processing blocks of bits from lower-level nodes to "clean" the signal at increasingly larger scales.
  5. Multi-bit Extension: To send $k$ bits instead of just one, the authors replace simple majority voting with a recursive application of Hamming codes. This allows the system to handle $k$ bits in $O(m + k)$ time.
  6. Deterministic & Efficient: Unlike some previous randomized approaches, this protocol is entirely deterministic and requires only $O(n)$ computation per node.

Datasets

This is a theoretical paper in information theory; therefore, no physical datasets were used. The results are established through mathematical proofs and asymptotic analysis of the Binary Symmetric Channel (BSC) model.

Key Insights and Ideas

  • The "Sparsity" of Coding: A major insight is that not every node needs to be "smart." By having most nodes act as simple repeaters and only a few nodes (the higher-level ones) perform error correction, the protocol minimizes "propagation delay" while still keeping the error probability in check.
  • Information Velocity vs. Capacity: The authors show that in low-noise scenarios, the information velocity $v(p)$ can actually be higher than the standard channel capacity. Specifically, as noise $p \to 0$, the velocity $v(p) = 1 - \Theta(p)$, whereas capacity scales as $1 - \Theta(p \log \frac{1}{p})$.
  • Scaling Laws: The paper characterizes the optimal scaling in both low-noise and high-noise regimes. In the high-noise limit (where the channel is nearly pure noise), the velocity scales with the square of the "bias" ($\delta^2$), which matches the scaling of the channel capacity.

Key Results

  • Linear Time Complexity: The protocol achieves a positive information velocity with a total transmission time $n = O(m)$ for 1 bit and $n = O(m + k)$ for $k$ bits.
  • Error Probability: The 1-bit protocol achieves an error probability that decays as $e^{-\Theta(\sqrt{n})}$. With slight modifications, this can be improved to $e^{-\Theta(n^{1-\epsilon})}$.
  • Computational Efficiency: Each node incurs only linear computational complexity $O(n)$, a massive improvement over the exponential complexity of tree-code-based relaying.
  • Asymptotic Bounds: The authors provide tight bounds on $v(p)$. For example, they prove that $v(p) \le (1-2p)^2$ for all $p$, providing a concrete upper bound on how fast information can possibly travel through such a chain.

Limitations and Future Work

  • Sub-optimal Error Exponent: While the error probability decays rapidly, it does not reach the "optimal" exponential decay $e^{-\Theta(n)}$ achieved by the (computationally inefficient) tree code methods. Closing this gap with a simple protocol remains an open challenge.
  • Constant Factors: The authors acknowledge they did not optimize the constant factors in their analysis. For instance, the protocol is proven to work for noise levels $p < 1/48$, but the actual threshold is likely much higher.
  • Exact Velocity: The paper proves the velocity is positive and establishes scaling laws, but it does not determine the exact value of $v(p)$ for a given noise level $p$. Future work could involve more refined protocols to hit the true "speed limit" of information in these networks.

Summary updated

Abstract

In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops $m$ , the transmission time $n$ , and the error probability. We introduce a simple, efficient, and deterministic protocol that attains positive information velocity (i.e., a non-vanishing ratio $\frac {m}{n}$ and small error probability) and is significantly simpler than existing protocols that do so. In addition, we characterize the optimal low-noise and high-noise scaling laws of the information velocity, and we adapt our 1-bit protocol to transmit $k$ bits over $m$ hops with $\mathcal {O}(m+k)$ transmission time.
BibTeX
@article{ling2022simple,
  author = {Yan Hao Ling and Jonathan Scarlett},
  title = {{Simple Coding Techniques for Many-Hop Relaying}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=ROItiZHDas},
}
Figure