×

On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability. (English) Zbl 1468.94475

Summary: Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability [V. Guruswami and M. Sudan, IEEE Trans. Inf. Theory 45, No. 6, 1757–1767 (1999; Zbl 0958.94036)] in the classical setting. This interest also translates to other metric setting, including the insertion and deletion (insdel for short) setting which is used to model synchronization errors caused by positional information loss in communication systems. Such interest is supported by the construction of a deletion correcting algorithm of insdel Reed-Solomon code which is based on the Guruswami-Sudan decoding algorithm [loc. cit.]. Nevertheless, there have been few studies [T. Do Duc et al., “Explicit constructions of two-dimensional Reed-Solomon codes in high insertion and deletion noise regime”, Preprint, arXiv:1909.03426] on the insdel error-correcting capability of Reed-Solomon codes.
In this paper, we discuss a criterion for a 2-dimensional insdel Reed-Solomon codes to have optimal asymptotic error-correcting capabilities, which are up to their respective lengths. Then we provide explicit constructions of 2-dimensional insdel Reed-Solomon codes that satisfy the established criteria. The family of such constructed codes can then be shown to extend the family of codes with asymptotic error-correcting capability reaching their respective lengths provided in [Do Duc et al., loc. cit., Theorem 2] which provide larger error-correcting capability compared to those defined in [D. Tonien et al., Des. Codes Cryptography 42, No. 2, 227–237 (2007; Zbl 1148.94015)].

MSC:

94B50 Synchronization error-correcting codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brill, E.; Moore, R. C., An improved error model for noisy channel spelling correction, (Proceedings of the 38th Annual Meeting on Association for Computational Linguistics (ACL ’00) (2000), Association for Computational Linguistics: Association for Computational Linguistics Stroudsburg, PA, USA), 286-293
[2] Chee, Y. M.; Kiah, H. M.; Vardy, A.; Vu, V. K.; Yaakobi, E., Codes correcting position errors in racetrack memories, (2017 IEEE Information Theory Workshop (ITW). 2017 IEEE Information Theory Workshop (ITW), Kaohsiung (2017)), 161-165
[3] Do Duc, T.; Liu, S.; Tjuawinata, I.; Xing, C., Explicit constructions of two-dimensional Reed-Solomon codes in high insertion and deletion noise regime (2019), available at
[4] Guruswami, V., Bridging Shannon and Hamming: list error-correction with optimal rate, (Proceedings of the International Congress of Mathematicians 2010. Proceedings of the International Congress of Mathematicians 2010, ICM 2010 (2010)) · Zbl 1230.94013
[5] Guruswami, V.; Li, R., Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes, (IEEE International Symposium on Information Theory (ISIT) (2016)), 620-624
[6] Guruswami, V.; Sudan, M., Improved decoding of Reed Solomon and algebraic geometry codes, IEEE Trans. Inf. Theory, 45, 1757-1767 (1999) · Zbl 0958.94036
[7] Guruswami, V.; Vardy, A., Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’05) (2005)), 470-478 · Zbl 1297.94128
[8] Guruswami, V.; Wang, C., Optimal rate list decoding via derivative codes, (Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (2011)), 593-604 · Zbl 1343.94101
[9] Haeupler, B.; Shahrasbi, A., Synchronization strings: codes for insertions and deletions approaching the singleton bound, (Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing (2017)) · Zbl 1370.94602
[10] Haeupler, B.; Shahrasbi, A., Synchronization strings: explicit constructions, local decoding, and applications, (Proceedings of the 50th Annual Symposium on Theory of Computing (STOC) (2018)), 841-854 · Zbl 1446.94203
[11] Haeupler, B.; Shahrasbi, A.; Sudan, M., Synchronization strings: list decoding for insertions and deletions, (45th International Colloquium on Automata, Languages and Programming (ICALP) (2018)) · Zbl 1512.94171
[12] Hamming, R. W., Error detecting and error correcting codes, Bell Syst. Tech. J., 29, 2, 147-160 (1950) · Zbl 1402.94084
[13] Hayashi, T.; Yasunaga, K., On the list decodability of insertions and deletions, (IEEE International Symposium on Information Theory (2018)), 86-90
[14] Jain, S.; Hassanzadeh, F. F.; Schwartz, M.; Bruck, J., Duplication-correcting codes for data storage in the DNA of living organisms, IEEE Trans. Inf. Theory, 63, 8, 4996-5010 (2017) · Zbl 1372.94471
[15] Koetter, R.; Vardy, A., Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 49, 11, 2809-2825 (November 2003) · Zbl 1301.94159
[16] Levenshtein, V., Binary codes capable of correcting deletions, insertions and reversals, Dokl. Akad. Nauk SSSR, 163, 4, 845-848 (1965) · Zbl 0149.15905
[17] Levenshtein, V., Asymptotically optimum binary code with correction for losses of one or two adjacent bits, Probl. Kibern., 19, 293-298 (1967) · Zbl 0189.19302
[18] Liu, S.; Tjuawinata, I.; Xing, C., On list decoding of insertion and deletion errors (2019)
[19] McAven, L.; Safavi-Naini, R., Classification of the deletion correcting capabilities of Reed-Solomon codes of dimension 2 over prime fields, IEEE Trans. Inf. Theory, 53, 6, 2280-2294 (June 2007) · Zbl 1325.94165
[20] Och, F. J., Minimum error rate training in statistical machine translation, (Proceedings of the 41st Annual Meeting on Association for Computational Linguistics (ACL ’03), vol. 1 (2003), Association for Computational Linguistics: Association for Computational Linguistics Stroudsburg, PA, USA), 160-167
[21] Roth, R. M.; Ruckenstein, G., Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inf. Theory, 46, 1, 246-257 (Jan. 2000) · Zbl 1001.94046
[22] Safavi-Naini, R.; Wang, Y., Traitor tracing for shortened and corrupted fingerprints, (Proc. ACM-DRM’02. Proc. ACM-DRM’02, LNCS, vol. 2696 (2003)), 81-100 · Zbl 1327.94072
[23] Sudan, M., Decoding of Reed Solomon codes beyond the error-correction bound, J. Complex., 13, 180-193 (1997) · Zbl 0872.68026
[24] Tenengolts, G. M., Nonbinary codes, correcting single deletion or insertion (Corresp.), IEEE Trans. Inf. Theory, 30, 5, 766-769 (1984) · Zbl 0554.94013
[25] Tonien, J.; Safavi-Naini, R., Construction of deletion correcting codes using generalized Reed-Solomon codes and their subcodes, Des. Codes Cryptogr., 42, 227-237 (2007) · Zbl 1148.94015
[26] Varshamov, R. R.; Tenengolts, G. M., Codes which correct single asymmetric errors, Avtom. Telemeh., 161, 3, 288-292 (1965), (in Russian)
[27] Wang, Y.; McAven, L.; Safavi-Naini, R., Deletion correcting using generalized Reed-Solomon codes, (Progress in Computer Science and Applied Logic, vol. 23 (2004)), 345-358 · Zbl 1059.94041
[28] Xu, R.; Wunsch, D., Survey of clustering algorithms, IEEE Trans. Neural Netw., 16, 3, 645-678 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.