Hostname: page-component-6bf8c574d5-rwnhh Total loading time: 0 Render date: 2025-02-21T19:46:27.905Z Has data issue: false hasContentIssue false
  • English
  • Français

OPTIMAL INSDEL CODES FROM ALMOST MDS CODES

Part of: Theory of error-correcting codes and error-detecting codes

Published online by Cambridge University Press:  17 February 2025

JIAHUI WANG  and
YANG DING Open the ORCID record for YANG DING [Opens in a new window]
JIAHUI WANG
Affiliation:
Department of Mathematics, Shanghai University, Shanghai, China e-mail: [email protected]
YANG DING*
Affiliation:
Department of Mathematics, Shanghai University, Shanghai, China
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Determining the insdel distance of linear codes is a very challenging problem. Recently, Ji et al. [‘Strict half-Singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes’, IEEE Trans. Inform. Theory 69(5) (2023), 2900–2910] proposed their strict half-Singleton bound for linear codes that do not include the all-one vector. A natural question asks for linear codes with both large Hamming distance and insdel distance. Almost maximum distance separable (MDS) codes are a special kind of linear code with good Hamming error-correcting capability. We present a sufficient condition for the insdel distance of almost MDS codes to be bounded by the strict half-Singleton bound. In addition, we construct a class of two-dimensional near MDS codes that achieve the strict half-Singleton bound using twisted Reed–Solomon codes. Finally, we present a construction of optimal almost MDS insdel codes from Reed–Solomon codes for large dimensions.

Keywords

insdel codesalmost MDS codenear MDS codesstrict half-Singleton boundtwisted Reed–Solomon codes

MSC classification

Primary: 94B05: Linear codes, general
Secondary: 94B60: Other types of codes
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , First View , pp. 1 - 11
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was supported by the National Natural Science Foundation of China under grant numbers 12171309 and 12271084.

References

Abdel-Ghaffar, K. A. S., Ferreira, H. C. and Cheng, L., ‘Correcting deletions using linear and cyclic codes’, IEEE Trans. Inform. Theory 56(10) (2010), 5223–5234.CrossRefGoogle Scholar
Brill, E. and Moore, R. C., ‘An improved error model for noisy channel spelling correction’, in: Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ed. H. Iida) (Association for Computational Linguistics, Kerrville, TX, 2000), 286–293.Google Scholar
Chee, Y. M., Kiah, H. M., Vardy, A., Yaakobi, E. and Vu, V. K., ‘Codes correcting position errors in racetrack memories’, in: 2017 IEEE Information Theory Workshop, Kaohsiung, Taiwan, 2017 (eds. P.-N. Chen, G. Kramer and C.-P. Li) (IEEE, New York, 2018), 161–165.Google Scholar
Chen, B. and Zhang, G., ‘Improved Singleton bound on insertion-deletion codes and optimal constructions’, IEEE Trans. Inform. Theory 68(5) (2022), 3028–3033.CrossRefGoogle Scholar
Chen, H., ‘Coordinate-ordering-free upper bounds for linear insertion-deletion codes’, IEEE Trans. Inform. Theory 68(8) (2022), 5126–5132.CrossRefGoogle Scholar
Cheng, K., Guruswami, V., Haeupler, B. and Li, X., ‘Efficient linear and affine codes for correcting insertions/deletions’, SIAM J. Discrete Math. 37(2) (2023), 748–778.CrossRefGoogle Scholar
Cheng, K., Jin, Z., Li, X. and Wu, K., ‘Deterministic document exchange protocols and almost optimal binary codes for edit errors’, in: IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris France (ed. M. Thorup) (IEEE, New York, 2018), 200–211.CrossRefGoogle Scholar
Con, R., Guo, Z., Li, R. and Zhang, Z., ‘Random Reed–Solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets’, Preprint, 2024, arXiv:2407.07299.Google Scholar
Con, R., Shpilka, A. and Tamo, I., ‘Reed–Solomon codes against adversarial insertions and deletions’, in: 2022 IEEE International Symposium on Information Theory (ISIT), Espoo, Finland (eds. T. Charalambous, C. Hollanti and D. Tirkkonen) (IEEE, New York, 2022), 2940–2945.CrossRefGoogle Scholar
Con, R., Shpilka, A. and Tamo, I., ‘Optimal two-dimensional Reed–Solomon codes correcting insertions and deletions’, IEEE Trans. Inform. Theory 70(7) (2024), 5012–5016.CrossRefGoogle Scholar
Dodunekov, S. M. and Landgev, I. N., ‘Near MDS codes over some small fields’, Discrete Math. 213(1) (2000), 55–65.CrossRefGoogle Scholar
Duc, T. D., Liu, S., Tjuawinata, I. and Xing, C., ‘Explicit constructions of two-dimensional Reed–Solomon codes in high insertion and deletion noise regime’, IEEE Trans. Inform. Theory 67(5) (2021), 2808–2820.CrossRefGoogle Scholar
Erdős, P. and Turán, P., ‘On a problem of Sidon in additive number theory, and on some related problems’, J. Lond. Math. Soc. (2) 16(4) (1941), 212–215.CrossRefGoogle Scholar
Haeupler, B., ‘Optimal document exchange and new codes for insertions and deletions’, in: IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD (ed D. Zuckerman) (IEEE, New York, 2019), 334–347.CrossRefGoogle Scholar
Haeupler, B. and Shahrasbi, A., ‘Synchronization strings: codes for insertions and deletions approaching the Singleton bound’, J. ACM 68(5) (2021), Article no. 36, 39 pages.CrossRefGoogle Scholar
Han, D. and Fan, C., ‘Roth–Lempel NMDS codes of non-elliptic-curve type’, IEEE Trans. Inform. Theory 69(9) (2023), 5670–5675.CrossRefGoogle Scholar
Huang, D., Yue, Q., Niu, Y. and Li, X., ‘MDS or NMDS self-dual codes from twisted generalized Reed–Solomon codes’, Des. Codes Cryptogr. 89(9) (2021), 2195–2209.CrossRefGoogle Scholar
Jain, S., Hassanzadeh, F., Schwartz, M. and Bruck, J., ‘Duplication-correcting codes for data storage in the DNA of living organisms’, IEEE Trans. Inform. Theory 63(8) (2017), 4996–5010.CrossRefGoogle Scholar
Ji, Q., Zheng, D., Chen, H. and Wang, X., ‘Strict half-Singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes’, IEEE Trans. Inform. Theory 69(5) (2023), 2900–2910.CrossRefGoogle Scholar
Levenshtein, V. I., ‘Binary codes capable of correcting deletions, insertions, and reversals’, Soviet Phys. Dokl. 10 (1965), 707–710.Google Scholar
Liu, S. and Xing, C., ‘Bounds and constructions for insertion and deletion codes’, IEEE Trans. Inform. Theory 69(2) (2023), 928–940.CrossRefGoogle Scholar
Liu, S., Xing, C. and Zhang, Y., ‘Codes with biochemical constraints and single error correction for DNA-based data storage’, Preprint, 2023, arXiv:2307.00221.Google Scholar
Magma Computer Algebra System. http://magma.maths.usyd.edu.au/.Google Scholar
Roth, R. and Lempel, A., ‘A construction of non-Reed–Solomon type MDS codes’, IEEE Trans. Inform. Theory 35(3) (1989), 655–657.CrossRefGoogle Scholar
Schoeny, C., Wachter-Zeh, A., Gabrys, R. and Yaakobi, E., ‘Codes correcting a burst of deletions or insertions’, IEEE Trans. Inform. Theory 63(4) (2017), 1971–1985.CrossRefGoogle Scholar
Xie, C., Chen, H., Qu, L. and Liu, L., ‘New dimension-independent upper bounds on linear insdel codes’, Adv. Math. Commun. 18(6) (2024), 1575–1589.CrossRefGoogle Scholar