Error correction by structural simplicity: correcting samplable additive errors
Error correction by structural simplicity: correcting samplable additive errors
复制标题
通过结构简单进行纠错：纠正可采样的加性误差
DOI：
10.1093/comjnl/bxy100
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kenji Yasunaga
中科院分区：
文献类型：
--
作者：
Li Xinjun;Sundquist Jan;Hamano Tsuyoshi;Sundquist Kristina;Kenji Yasunaga
本文从错误机制的结构简单性出发，探讨了纠错的可能性和局限性。具体来说，我们考虑信道模型，称为samplable添加剂的渠道，其中（i）错误有效地采样的编码方案或传输的码字的知识，（ii）的熵的错误分布是有界的;和（iii）引入的信道的错误的数量是无界的。对于通道，提供了几个负面和正面的结果。假设单向函数的存在，对于ε∈（0，1），存在伪随机的熵nε的可采样加性误差，因此不能通过有效的编码方案校正。它表明，有一个预言算法，导致在{0，1}n的熵m=ω（logn）的抽样分布不是伪随机的，但不可纠正的有效方案的速率小于1−m/n−o（1）。结果表明，限制错误机制是有效的采样，而不是伪随机的错误校正是不够的。作为积极的结果，提供了一些条件下，有效的纠错是可能的。
This paper explores the possibilities and limitations of error correction by the structural simplicity of error mechanisms. Specifically, we consider channel models, calledsamplable additive channels, in which (i) errors are efficiently sampled without the knowledge of the coding scheme or the transmitted codeword; (ii) the entropy of the error distribution is bounded; and (iii) the number of errors introduced by the channel is unbounded. For the channels, several negative and positive results are provided. Assuming the existence of one-way functions, there are samplable additive errors of entropy nε for ε∈(0,1) that are pseudorandom, and thus not correctable by efficient coding schemes. It is shown that there is an oracle algorithm that induces a samplable distribution over {0,1}n of entropy m=ω(logn) that is not pseudorandom, but is uncorrectable by efficient schemes of rate less than 1−m/n−o(1). The results indicate that restricting error mechanisms to be efficiently samplable and not pseudorandom is insufficient for error correction. As positive results, some conditions are provided under which efficient error correction is possible.