Rateless codes for AVC models

Anand D. Sarwate, Michael Gastpar

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


The arbitrarily varying channel (AVC) is a channel model whose state is selected maliciously by an adversary. Fixed-blocklength coding assumes a worst-case bound on the adversary's capabilities, which leads to pessimistic results. This paper defines a variable-length perspective on this problem, for which achievable rates are shown that depend on the realized actions of the adversary. Specifically, rateless codes are constructed which require a limited amount of common randomness. These codes are constructed for two kinds of AVC models. In the first the channel state cannot depend on the channel input, and in the second it can. As a by-product, the randomized coding capacity of the AVC with state depending on the transmitted codeword is found and shown to be achievable with a small amount of common randomness. The results for this model are proved using a randomized strategy based on list decoding.

Original languageEnglish (US)
Article number5485014
Pages (from-to)3105-3114
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Adversarial models
  • Arbitrarily varying channels (AVCs)
  • Randomization
  • Rateless coding


Dive into the research topics of 'Rateless codes for AVC models'. Together they form a unique fingerprint.

Cite this