摘要：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(−Ω(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.
