论文标题
具有最小无噪声反馈的二进制错误校正代码
Binary Error-Correcting Codes with Minimal Noiseless Feedback
论文作者
论文摘要
在带有反馈的错误校正代码的设置中，爱丽丝希望通过在频道上发送一系列位，同时吵闹地收到Bob的反馈，向Bob传达$ k $ bit消息$ x $。长期以来（Berlekamp，1964年），在这种模型中，鲍勃仍然可以正确确定$ x $，即使$ \ \ \ \ frac13 $的爱丽丝碎片的对手是对手的。这在不反馈的情况下改善了经典设置，在这种情况下，对于超过$ \ frac14 $的错误分数无法恢复。 原始反馈设置假定在传输每一位后，爱丽丝（通过反馈）收到了什么。在这项工作中，我们专注于有限的反馈模型，在该模型中，BOB只能以协议中的少量预指定点发送一些位。对于任何所需的$ε> 0 $，我们构建了一个编码方案，该方案可容忍$ 1/3-ε$的位flips $1/3-ε$，仅依靠$o_ε（\ log k）$ bob中的反馈，以固定的$O_ε（1）$回合。我们通过匹配的下限进行补充，表明$ω（\ log K）$的反馈是从超过$ 1/4 $的错误分数中恢复（没有任何反馈的阈值），而对于弹性的方案，可以弹性到$ 1/3-ε$的位flips flips，回合的数量必须增长为$ $ f $ε\ 0 $。 我们还研究（并解决）一个问题，以简单的擦除模型。我们表明，$o_ε（\ log k）$ invackback分布在$o_ε（1）$ rounds上，足以容忍分数$（1-ε）$的擦除。同样，我们的$ω（\ log K）$下限适用于超过$ 1/2 $的擦除分数，并且随着擦除分数接近$ 1 $，需要越来越多的回合。
In the setting of error-correcting codes with feedback, Alice wishes to communicate a $k$-bit message $x$ to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine $x$ even if $\approx \frac13$ of Alice's bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding $\frac14$. The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired $ε> 0$, we construct a coding scheme that tolerates a fraction $ 1/3-ε$ of bit flips relying only on $O_ε(\log k)$ bits of feedback from Bob sent in a fixed $O_ε(1)$ number of rounds. We complement this with a matching lower bound showing that $Ω(\log k)$ bits of feedback are necessary to recover from an error fraction exceeding $1/4$ (the threshold without any feedback), and for schemes resilient to a fraction $1/3-ε$ of bit flips, the number of rounds must grow as $ε\to 0$. We also study (and resolve) the question for the simpler model of erasures. We show that $O_ε(\log k)$ bits of feedback spread over $O_ε(1)$ rounds suffice to tolerate a fraction $(1-ε)$ of erasures. Likewise, our $Ω(\log k)$ lower bound applies for erasure fractions exceeding $1/2$, and an increasing number of rounds are required as the erasure fraction approaches $1$.
