In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose that the encoder transmits $n$ binary symbols one-by-one over a channel, in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about the insertions or deletions that have occurred within the previous transmission and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $\tau n$, $0<\tau<1$. We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later finished by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.
翻译:在本文中,引入了在对抗性插入删除频道上传递信息的一个新问题。 假设编码器通过一个频道逐个传送一美元二进制符号, 可以在其中删除某些符号并插入一些额外的符号。 每次传输后, 编码器将前一次传输和编码战略中出现的插入或删除通知编码器。 目标是设计一个编码器, 能够在假设删除和插入的总数受$\tau n$0 ⁇ tau < $1美元的限制的情况下, 尽可能无错误地传送尽可能多的信息。 我们展示了如何将这一问题降低到在替换频道上传递信息的问题。 因此, 完全确定了反馈插入电荷代码的最大充斥率。 Berlekamp 已经部分确定了对抗性替换频道的最大充充斥率, 后由Zigangirov 完成。 然而, Ziganggirov 对目前版本的较低约束的分析非常复杂。 We regregiganZrigang' 和当前版本的更新结果非常复杂。