The benefit of a 1-bit jump-start, and the necessity of stochastic encoding, in jamming channels

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, Anand D. SarwatearXiv 2016 · arXiv

Abstract

This paper explores the communication capacity of binary channels under the influence of a malicious, causal adversary who can erase a fraction $p$ of transmitted bits. We demonstrate that a minimal "jump-start"—delaying the adversary's observations by just a single bit—allows the communication rate to jump from $1-2p$ to $1-p$. Crucially, we prove that this capacity gain is only achievable if the encoder utilizes private randomness (stochastic encoding); deterministic codes remain restricted to the lower rate. Our results bridge the gap between Shannon's statistical noise models and Hamming's worst-case adversarial models.

Introduction

Information theory traditionally distinguishes between Shannon’s approach, which treats noise as a statistical phenomenon, and Hamming’s approach, which considers a worst-case adversary. This research investigates a middle ground by modeling the channel as an adversary named "Calvin." Calvin can erase up to a fraction $p$ of transmitted bits based on his observations of the channel.

The study focuses on the impact of causality and delay:

  • Exactly Causal: Calvin observes the current bit $x_i$ before deciding whether to erase it. Previous literature established the capacity in this regime as $1-2p$.
  • 1-bit Delay: Calvin observes only up to the previous bit $x_{i-1}$ before deciding on the current bit $x_i$.

The core contribution is determining whether this 1-bit "jump-start" for the transmitter significantly alters capacity and how the nature of the code (deterministic vs. stochastic) influences the outcome.

Methods: Stochastic Encoding and Adversarial Strategies

To establish these results, the authors employ two primary mathematical frameworks:

1. Novel Stochastic Code Construction

To prove that a rate of $1-p$ is achievable with a 1-bit delay, the authors designed a code where the encoder adds "private noise" to a base codeword. The encoder partitions bit positions and applies varying levels of Bernoulli noise to different segments. Decoding involves a two-step process: first, list decoding on a message prefix to narrow down candidates, followed by list disambiguation on the suffix using the specific private noise patterns.

The stochastic encoder construction adding private noise to a base codeword.

2. The "Wait and Push" Jamming Strategy

To demonstrate the necessity of stochastic encoding, the authors developed a strategy for Calvin. In this scenario, Calvin "waits" until he has observed enough bits to narrow the possible messages to a small set. He then "pushes" by erasing bits strategically to make the received signal consistent with multiple messages, forcing a decoding error for any deterministic code.

Key Results and Insights

The research yields several striking insights into the nature of adversarial channels:

  • The Power of the Jump-start: There is a sharp asymmetry between lookahead and delay. While lookahead for the adversary provides little benefit, a single bit of delay for the adversary significantly empowers the transmitter.
  • Stochasticity is Mandatory: In binary channels, deterministic codes are too predictable. Calvin can use his knowledge of the codebook to anticipate future bits despite the delay. Stochastic encoding introduces uncertainty that Calvin cannot overcome without seeing the current bit.
  • Bridging the Capacity Gap: The results show that the $1-2p$ penalty in causal channels is specifically due to the adversary's ability to see the current bit. With a 1-bit delay and stochasticity, the capacity matches that of a channel with a completely oblivious adversary ($1-p$).
Capacity comparison between different adversary models showing the jump from 1-2p to 1-p.

Conclusion and Future Work

The paper concludes that stochastic encoding is essential to exploit an adversary's delay in binary jamming channels. While the theoretical capacity is established, several avenues for future work remain. The current stochastic codes rely on random partitions that may not be computationally efficient for real-world hardware, suggesting a need for more "structured" code versions. Additionally, it remains an open question whether stochastic encoding is strictly necessary to achieve the $1-2p$ rate in the exactly causal case, as current best-performing codes for that scenario already utilize stochasticity.

Summary updated

Abstract

We consider the problem of communicating a message $m$ in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to $pn$ bits, out of $n$ transmitted bits $(x_1,\ldots,x_n)$. The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends on his observations $(x_1,\ldots,x_i)$ was recently characterized to be $1-2p$. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends only on $(x_1,\ldots,x_{i-1})$ (and is independent of the "current bit" $x_i$) then the capacity increases to $1-p$ when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword is a deterministic function of the message $m$) then no rate asymptotically larger than $1-2p$ is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of $1-p$ against a one-bit-delayed Calvin.
BibTeX
@misc{dey2016benefit,
  author = {Bikash Kumar Dey and Sidharth Jaggi and Michael Langberg and Anand D. Sarwate},
  title = {{The benefit of a 1-bit jump-start, and the necessity of stochastic encoding, in jamming channels}},
  year = {2016},
  eprint = {1602.02384},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.02384},
}
Figure