Theory of Computing
-------------------
Title     : Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels
Authors   : Benny Applebaum, Liron David, and Guy Even
Volume    : 14
Number    : 4
Pages     : 1-29
URL       : https://theoryofcomputing.org/articles/v014a004

Abstract
--------

A rateless code encodes a finite-length information word into an
infinitely long codeword such that longer prefixes of the codeword can
tolerate a larger fraction of errors. A rateless code approaches
capacity for a family of channels if, for every channel in the family,
reliable communication is obtained by a prefix of the code whose rate
is arbitrarily close to the channel's capacity. The encoder is
universal in the sense that same encoder is used for all channels in
the family.

So far, all known constructions of rateless codes were randomized,
giving rise to _ensembles_ of such codes. In this paper, we construct
the first _explicit_ rateless code for memoryless binary-input output-
symmetric (MBIOS) channels. Our code achieves an almost exponentially
small error probability (e.g., $\exp(-\Omega(k/\log^* k))$ for $k$-bit
information word), and can be encoded in almost constant time per-bit
(e.g., $O(\log^* k)$). Over binary symmetric channels, the running
time of decoding is similar. Previous ensemble-based rateless codes
for the binary symmetric channel have polynomial asymptotic error
probabilities and the running time of decoding is polynomial only
under some conditions.

Our main technical contribution is a constructive proof for the
existence of an infinite generating matrix with the property that each
of its prefixes induces a weight distribution that approximates the
expected weight distribution of a random linear code.

---------

A preliminary version of this paper appeared in the
Proceedings of the 6th Conference on Innovations in Theoretical
Computer Science, ITCS.