A Multiple Insertion/Deletion Correcting Code for Run-Length Limited Sequences
A Multiple Insertion/Deletion Correcting Code for Run-Length Limited Sequences
复制标题
游程有限序列的多重插入/删除校正码
DOI：
10.1109/tit.2011.2172725
复制
发表时间：
2012
影响因子：
2.5
通讯作者：
W. A. Clarke
中科院分区：
文献类型：
--
作者：
F. Palunčić;K. Abdel;H. C. Ferreira;W. A. Clarke
提出了一种编码结构，为有限序列增加了多次插入/删除纠错能力。这个代码的码字本身是有长度限制的。插入/删除校正能力是通过要求码字中的若干加权和的行程长度来满足某些同余模素数来实现的。这种结构类似于Dolecek和Anantharam提出的数论代码，可以纠正多次重复错误，或者相当于多次插入零。结果表明，如果码字的码长是有限的，则该码能够纠正0和1的插入和删除。提出了一种基于多插入/删除信道的译码算法。在Dolecek和Anantharam的基础上，提出了一种系统的编码方法。此外，尽管我们的结构具有额外的运行长度约束，但所提出的结构具有比Helberg编码更高的渐近速率，Helberg编码在运行长度方面是无约束的。对能够纠正插入/删除错误的运行长度有限的代码的需求是由用于磁记录的位模式介质引起的。
A code construction is proposed to add a multiple insertion/deletion error correcting capability to a run-length limited sequence. The codewords of this code are themselves run-length limited. The insertion/deletion correcting capability is achieved by requiring several weighted sums of run-lengths in the codewords to satisfy certain congruences modulo primes. The construction is similar to the number-theoretic code proposed by Dolecek and Anantharam, which can correct multiple repetition errors or, equivalently, multiple insertions of zeros. It is shown that if the codewords in this code are run-length limited, then the code is capable of correcting both insertions and deletions of zeros and ones. An algorithm is proposed for decoding over a multiple insertion/deletion channel. Following the work of Dolecek and Anantharam, a systematic encoding method is also proposed for the codes. Furthermore, it is shown that the proposed construction has a higher rate asymptotically than the Helberg code, which is unconstrained in terms of run-lengths, even though our construction has the additional run-length constraints. The need for run-length limited codes that can correct insertion/deletion errors is motivated by bit-patterned media for magnetic recording.