Revised: October 29, 2017

Published: April 26, 2018

**Keywords:**coding theory, error correcting codes, rateless codes, memoryless binary-input output symmetric channel, binary symmetric channel, Gaussian channel

**ACM Classification:**E.4

**AMS Classification:**68Q17, 52C07, 11H06, 11H31, 05B40

**Abstract:**
[Plain Text Version]

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 2015.