文章基本信息

标题：Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels
本地全文：下载
作者：Benny Applebaum ; Liron David ; Guy Even 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-29
DOI：10.4086/toc.2018.v014a004
出版社：University of Chicago
摘要：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.
关键词：coding theory; error-correcting codes; rateless codes; memoryless binary-input; output symmetric channel; binary symmetric channel; Gaussian channel