论文标题
在两个删除通道上最大似然解码的误差概率
The Error Probability of Maximum-Likelihood Decoding over Two Deletion Channels
论文作者
论文摘要
本文研究了重建单词的几个嘈杂副本的问题。该设置是由多个应用程序激励的，其中包括重建基于DNA的存储系统中的链。在此范式下，一个单词在一些固定数量的相同的独立通道上传输，解码器的目的是输出传输的单词或一些密闭近似。本文的主要重点是两个删除通道的情况，并研究了此设置下的最大可能性（ML）解码器的误差概率。首先，讨论了ML解码器的运行方式。然后，我们观察到主要的误差模式是在同一运行中的删除或交替序列引起的错误。基于这些观察结果，得出的是，ML解码器的错误概率大约是$ \ frac {3Q-1} {q-1} {q-1} p^2 $，当传输单词是任何$ q $ -ary序列，而$ p $是通道的删除概率。我们还研究了传输单词属于Varshamov tenengolts（VT）代码或移位的VT代码时的情况。最后，还研究了插入通道。这些理论结果通过相应的模拟得到验证。
This paper studies the problem of reconstructing a word given several of its noisy copies. This setup is motivated by several applications, among them is reconstructing strands in DNA-based storage systems. Under this paradigm, a word is transmitted over some fixed number of identical independent channels and the goal of the decoder is to output the transmitted word or some close approximation. The main focus of this paper is the case of two deletion channels and studying the error probability of the maximum-likelihood (ML) decoder under this setup. First, it is discussed how the ML decoder operates. Then, we observe that the dominant error patterns are deletions in the same run or errors resulting from alternating sequences. Based on these observations, it is derived that the error probability of the ML decoder is roughly $\frac{3q-1}{q-1}p^2$, when the transmitted word is any $q$-ary sequence and $p$ is the channel's deletion probability. We also study the cases when the transmitted word belongs to the Varshamov Tenengolts (VT) code or the shifted VT code. Lastly, the insertion channel is studied as well. These theoretical results are verified by corresponding simulations.
