Bit Flipping Moment Balancing Schemes for Insertion, Deletion and Substitution Error Correction

L Cheng, HC Ferreira - arXiv preprint arXiv:1901.07769, 2019 - arxiv.org
arXiv preprint arXiv:1901.07769, 2019arxiv.org
In this paper, two moment balancing schemes, namely a variable index scheme and a fixed
index scheme, for either single insertion/deletion error correction or multiple substitution
error correction are introduced for coded sequences originally developed for correcting
substitution errors only. By judiciously flipping bits of the original substitution error correcting
code word, the resulting word is able to correct either a reduced number of substitution
errors or a single insertion/deletion error. The number of flips introduced by the two schemes …
In this paper, two moment balancing schemes, namely a variable index scheme and a fixed index scheme, for either single insertion/deletion error correction or multiple substitution error correction are introduced for coded sequences originally developed for correcting substitution errors only. By judiciously flipping bits of the original substitution error correcting code word, the resulting word is able to correct either a reduced number of substitution errors or a single insertion/deletion error. The number of flips introduced by the two schemes can be kept small compared to the code length. It shows a practical value of applying the schemes to a long substitution error correcting code for a severe channel where substitution errors dominate but insertion/deletion errors can occur with a low probability. The new schemes can be more easily implemented in an existing coding system than any previously published moment balancing templates since no additional parity bits are required which also means the code rate remains same and the existing substitution error correcting decoder requires no changes. Moreover, the work extends the class of Levenshtein codes capable of correcting either single substitution or single insertion/deletion errors to codes capable of correcting either multiple substitution errors or single insertion/deletion error.
arxiv.org