Randomness and Structure in Error-Correcting Codes

我们引入了可采样加性误差通道，并研究了在通道中纠错的可能性和局限性。“可采样”意味着错误是可有效计算的，并且“可加”意味着错误被添加到输入码字而不知道代码或码字。如果可抽样分布构成线性子空间，我们可以用线性码纠正错误。在预言机相对化的情况下，存在具有低熵的可采样错误，对于这些错误不存在有效的伴随式解码。如果可抽样分布是小偏差的，则偏差的大小与错误可纠正的信息率之间存在关系。

We have introduced samplable additive-error channels, and studied the possibilities and limitations of error correction in the channels. "Samplable" means that the errors are efficiently computable, and "additive" means that the errors are added to input codewords without the knowledge of the code or the codewords. If samplable distributions form linear subspaces, we can correct the errors by linear codes. In the situations relativized by oracles, there are samplable errors with low entropy for which no efficient syndrome decoding exists. If samplable distributions are of small-bias, there is a relation between the magnitude of the bias and the information rate on which the errors are correctable.