Abstract
In network information theory, transmitting information through a long chain of noisy nodes—the many-hop relay problem—presents a fundamental challenge in balancing reliability, delay, and computational complexity. This paper introduces a simple, deterministic protocol that achieves a positive information velocity, where transmission time scales linearly with the number of hops. By employing a recursive hierarchy of nodes and majority-based error correction, the proposed method avoids the exponential complexity of previous tree-code-based approaches while maintaining robust performance across various noise regimes.
Introduction
The many-hop relay problem asks how quickly and reliably a bit of information can be sent through a sequence of $m$ noisy nodes. In a Binary Symmetric Channel (BSC) model, simple forwarding leads to noise accumulation that eventually obliterates the signal. To maintain signal integrity, nodes must perform error correction. However, traditional coding techniques often introduce significant delays or require exponential time to decode (e.g., tree codes).
The core objective is to achieve a positive information velocity ($v(p) > 0$), defined as the limit of the ratio of hops $m$ to transmission time $n$ as the chain length increases. This paper proposes a "middle ground" protocol: one that is mathematically optimal in its scaling laws yet simple enough to implement with linear computational complexity.
Methodology
Recursive Node Hierarchy
The protocol organizes nodes into a recursive hierarchy of "levels." A node $i$ is assigned a level $l$ based on its index (specifically, if $4^l$ divides $i$ but $4^{l+1}$ does not). This structure ensures that most nodes are Level 0 (simple repeaters), while higher-level nodes are spaced increasingly further apart to perform more complex error correction.
The processing logic is recursive:
- Level 0 nodes simply forward received bits.
- Level 1 nodes collect a block of 3 bits, perform a majority vote to estimate the original bit, and repeat that estimate 3 times.
- Higher-level nodes apply this logic to blocks of bits from lower-level nodes, effectively cleaning the signal at larger scales.
Multi-bit Extension
To transmit $k$ bits efficiently, the simple majority voting is replaced with a recursive application of Hamming codes. This allows the system to handle multiple bits in $O(m + k)$ time, maintaining the linear scaling of transmission time relative to both the number of hops and the message length.
Theoretical Analysis and Results
Information Velocity and Capacity
A key insight of this work is the characterization of information velocity $v(p)$ relative to channel capacity. In low-noise scenarios ($p \to 0$), the velocity scales as $v(p) = 1 - \Theta(p)$, which is notably higher than the standard channel capacity scaling of $1 - \Theta(p \log \frac{1}{p})$. In high-noise regimes, the velocity scales with the square of the "bias" ($\delta^2$), matching the scaling of channel capacity.
Efficiency and Error Probability
The protocol demonstrates several critical advantages:
- Linear Complexity: Each node requires only $O(n)$ computation, a significant improvement over the exponential complexity of tree codes.
- Deterministic Nature: Unlike randomized approaches, this protocol is entirely deterministic.
- Error Decay: The 1-bit protocol achieves an error probability decaying as $e^{-\Theta(\sqrt{n})}$. While not reaching the optimal $e^{-\Theta(n)}$ of tree codes, it provides a practical and efficient alternative.
Discussion
While the protocol achieves positive information velocity with linear complexity, some limitations remain. The error exponent is sub-optimal compared to tree-code methods, and the constant factors in the noise threshold (proven for $p < 1/48$) are likely conservative. Future work may focus on refining the recursive structures to achieve the true "speed limit" of information in these networks and closing the gap to optimal error exponents.
Summary updated