Optimal Rate Code Constructions for Computationally Simple Channels
Optimal Rate Code Constructions for Computationally Simple Channels
复制标题
计算简单信道的最佳速率代码构造
DOI：
10.1145/2936015
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
Smith, Adam
中科院分区：
文献类型：
--
作者：
Guruswami, Venkatesan;Smith, Adam
我们考虑计算有界信道的编码方案，只要(A)误差分数由参数以高概率有界，以及(B)误差相加的过程可以用一个足够“简单”的电路来描述，它就可以引入任意一组误差。这类信道模型的编码很有吸引力，因为与标准对抗错误的编码一样，它们可以处理真实行为未知且随时间变化的信道。对于两类信道，我们提供了显式的、高效的可编码/可译码的最优码率，而以前只知道低效的可译码。在每种情况下，我们都提供了一个编码器/解码器，可以在类中的所有通道上工作。对加性错误的唯一译码：对于达到香农容量1−H(P)的加性(也称为忽略)信道，给出了一种多项式时间可编/可译码的构造方法。这些通道将任意误差向量∈{0，1}Nof权重以最大值pN添加到发送字；向量可取决于代码，但不取决于编码器或特定发送字的随机性。多项式时间信道的列表译码：对于每个常数c>；0，我们构造了具有最优码率(任意接近1−H(P))的码，对于可由mostNc的大小电路描述的信道，有效地恢复包含正确消息的短列表。我们的构造不是完全显式的，而是蒙特卡洛(我们给出了一个算法，该算法以很高的概率产生一个适用于所有时间Nc个信道的编码器/解码器对)。我们不知道在信息论文献中考虑的任何信道模型，除了纯粹的对抗性信道，它需要超过线性大小的电路来实现。我们证明了对列表译码的放宽是不可能的，结果表明，在很大的参数范围(p>；1/4)中，对于适度类别的信道(在线、无记忆、非均匀信道)唯一可译码的码不可能有正码率。
We consider coding schemes forcomputationally boundedchannels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameterpand (b) the process that adds the errors can be described by a sufficiently “simple” circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior isunknownorvaryingover time.For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where onlyinefficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works foreverychannel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel.Unique decoding for additive errors:We give the first construction of a polynomial-time encodable/decodable code foradditive(a.k.a.oblivious) channels that achieve the Shannon capacity 1 −H(p). These are channels that add an arbitrary error vectore∈ {0, 1}Nof weight at mostpNto the transmitted word; the vectorecan depend on the code but not on the randomness of the encoder or the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases.List decoding for polynomial-time channels:For every constantc> 0, we construct codes with optimal rate (arbitrarily close to 1 −H(p)) that efficiently recover a short list containing the correct message with high probability for channels describable by circuits of size at mostNc. Our construction is not fully explicit but rather Monte Carlo (we give an algorithm that, with high probability, produces an encoder/decoder pair that works for all timeNcchannels). We are not aware of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list decoding with an impossibility result showing that, in a large range of parameters (p> 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate.