Extractor codes
Extractor codes
复制标题
DOI：
10.1145/380752.380800
复制
发表时间：
2001-07
影响因子：
2.5
通讯作者：
A. Ta-Shma;David Zuckerman
中科院分区：
文献类型：
--
作者：
A. Ta-Shma;David Zuckerman
我们研究高噪声信道的纠错码。例如，信道中的每个接收信号可以源自字母表中的某一半符号。我们的主要概念的贡献是这样的通道和提取器的纠错码之间的等价性。我们的主要技术贡献是一个新的显式纠错码的基础上Trevisan的提取器，可以处理这样的通道，甚至噪音的。我们的新码具有多项式时间编码和多项式时间软判决译码。我们注意到，Reed-Solomon码不能处理这样的信道，我们的研究暴露了Reed-Solomon码的列表解码的一些限制。我们的等价性的另一个优点是，当约翰逊界被重述的提取器，它成为著名的剩余哈希引理。这产生了一个新的证明约翰逊界适用于大字母和软解码。我们的显式代码是有用的，在几个应用程序。首先，它们产生了使用少量辅助随机位提取许多核心位的算法。其次，它们是最近一个方案中的关键工具，该方案以一种方式压缩存储一组元素，该组中的成员可以通过仅查看表示的一位来确定。最后，它们是最近在大字母表上构造高噪声、几乎最优速率列表可解码码的基础。
We study error-correcting codes for highly noisy channels. For example, every received signal in the channel may originate from some half of the symbols in the alphabet. Our main conceptual contribution is an equivalence between error-correcting codes for such channels and extractors. Our main technical contribution is a new explicit error-correcting code based on Trevisan's extractor that can handle such channels, and even noisier ones. Our new code has polynomial-time encoding and polynomial-time soft-decision decoding. We note that Reed-Solomon codes cannot handle such channels, and our study exposes some limitations on list decoding of Reed-Solomon codes. Another advantage of our equivalence is that when the Johnson bound is restated in terms of extractors, it becomes the well-known Leftover Hash Lemma. This yields a new proof of the Johnson bound which applies to large alphabets and soft decoding. Our explicit codes are useful in several applications. First, they yield algorithms to extract many hardcore bits using few auxiliary random bits. Second, they are the key tool in a recent scheme to compactly store a set of elements in a way that membership in the set can be determined by looking at only one bit of the representation. Finally, they are the basis for the recent construction of high-noise, almost-optimal rate list-decodable codes over large alphabets.