{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:04:38Z","timestamp":1774022678732,"version":"3.50.1"},"reference-count":36,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T00:00:00Z","timestamp":1737158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Singapore Ministry of Education Academic Research Fund Tier 2","award":["T2EP50221-0036"],"award-info":[{"award-number":["T2EP50221-0036"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we construct q-ary codes for correcting a burst of at most t deletions, where t,q\u22652 are arbitrarily fixed positive integers. We consider two scenarios of error correction: the classical error correcting codes, which recover each codeword from one read (channel output), and the reconstruction codes, which allow to recover each codeword from multiple channel reads. For the first scenario, our construction has redundancy logn+8loglogn+o(loglogn) bits, encoding complexity O(q7tn(logn)3) and decoding complexity O(nlogn). For the reconstruction scenario, our construction can recover the codewords with two reads and has redundancy 8loglogn+o(loglogn) bits. The encoding complexity of this construction is Oq7tn(logn)3, and decoding complexity is Oq9t(nlogn)3. Both of our constructions have lower redundancy than the best known existing works. We also give explicit encoding functions for both constructions that are simpler than previous works.<\/jats:p>","DOI":"10.3390\/e27010085","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T06:53:32Z","timestamp":1737442412000},"page":"85","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Some New Constructions of q-ary Codes for Correcting a Burst of at Most t Deletions"],"prefix":"10.3390","volume":"27","author":[{"given":"Wentu","family":"Song","sequence":"first","affiliation":[{"name":"Science, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, Singapore"}]},{"given":"Kui","family":"Cai","sequence":"additional","affiliation":[{"name":"Science, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, Singapore"}]},{"given":"Tony Q. S.","family":"Quek","sequence":"additional","affiliation":[{"name":"Science, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, Singapore"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,18]]},"reference":[{"key":"ref_1","unstructured":"Levenshtein, V.I. (July, January 30). Bounds for Deletion\/Insertion Correcting Codes. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Lausanne, Switzerland."},{"key":"ref_2","first-page":"845","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"163","author":"Levenshtein","year":"1965","journal-title":"Dokl. Akad. Nauk. SSR"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1109\/TIT.1984.1056962","article-title":"Nonbinary codes, correcting single deletion or insertion","volume":"30","author":"Tenengolts","year":"1984","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"6989","DOI":"10.1109\/TIT.2024.3417894","article-title":"A new version of q-ary Varshamov-Tenengolts codes with more efficient encoders: The differential VT codes and the differential shifted VT codes","volume":"70","author":"Nguyen","year":"2024","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3403","DOI":"10.1109\/TIT.2017.2746566","article-title":"Efficient low-redundancy codes for correcting multiple deletions","volume":"64","author":"Brakensiek","year":"2018","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3360","DOI":"10.1109\/TIT.2020.3028702","article-title":"On optimal k-deletion correcting codes","volume":"67","author":"Sima","year":"2021","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Sima, J., Gabrys, R., and Bruck, J. (2020, January 21\u201326). Optimal systematic t-deletion correcting codes. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9173986"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"6384","DOI":"10.1109\/TIT.2021.3069446","article-title":"Explicit two-deletion codes with redundancy matching the existential bound","volume":"67","author":"Guruswami","year":"2021","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Sima, J., Gabrys, R., and Bruck, J. (2020, January 21\u201326). Optimal codes for the q-ary deletion channel. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174241"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bitar, R., Hanna, S.K., Polyanskii, N., and Vorobyev, I. (2021, January 12\u201320). Optimal codes correcting localized deletions. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518196"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"6402","DOI":"10.1109\/TIT.2022.3177169","article-title":"Systematic codes correcting multiple-deletion and multiple-substitution errors","volume":"68","author":"Song","year":"2022","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"6470","DOI":"10.1109\/TIT.2023.3285012","article-title":"Non-binary two-deletion correcting codes and burst-deletion correcting codes","volume":"69","author":"Song","year":"2023","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Liu, S., Tjuawinata, I., and Xing, C. (2023). Explicit construction of q-ary 2-deletion correcting codes with low redundancy. arXiv.","DOI":"10.1109\/TIT.2024.3360964"},{"key":"ref_14","first-page":"293","article-title":"Asymptotically optimum binary code with correction for losses of one or two adjacent bits","volume":"19","author":"Levenshtein","year":"1967","journal-title":"Probl. Kibern."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Cheng, L., Swart, T.G., Ferreira, H.C., and Abdel-Ghaffar, K.A.S. (July, January 29). Codes for correcting three or more adjacent deletions or insertions. Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875032"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1971","DOI":"10.1109\/TIT.2017.2661747","article-title":"Codes correcting a burst of deletions or insertions","volume":"63","author":"Schoeny","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2550","DOI":"10.1109\/TIT.2017.2778143","article-title":"Codes in the damerau distance for deletion and adjacent transposition correction","volume":"64","author":"Gabrys","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Lenz, A., and Polyanskii, N. (2020, January 21\u201326). Optimal codes correcting a burst of deletions of variable length. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174288"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/TIT.2023.3340246","article-title":"Nonbinary codes for correcting a burst of at most t deletions","volume":"70","author":"Wang","year":"2024","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/18.904499","article-title":"Efficient reconstruction of sequences","volume":"47","author":"Levenshtein","year":"2001","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1006\/jcta.2000.3081","article-title":"Efficient reconstruction of sequences from their subsequences or supersequences","volume":"93","author":"Levenshtein","year":"2001","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0097-3165(03)00103-1","article-title":"Reconstruction from subsequences","volume":"103","author":"Dudik","year":"2003","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2924","DOI":"10.1109\/TIT.2018.2800044","article-title":"Sequence reconstruction over the deletion channel","volume":"64","author":"Gabrys","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"7094","DOI":"10.1109\/TIT.2018.2807480","article-title":"Coding for racetrack memories","volume":"64","author":"Chee","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7682","DOI":"10.1109\/TIT.2019.2935973","article-title":"Unique reconstruction of coded strings from multiset substring spectra","volume":"65","author":"Gabrys","year":"2019","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_26","unstructured":"Chrisnata, J., Kiah, H.M., and Yaakobi, E. (2020, January 24\u201327). Optimal reconstruction codes for deletion channels. Proceedings of the 2020 International Symposium on Information Theory and Its Applications (ISITA), Kapolei, HI, USA."},{"key":"ref_27","unstructured":"Pham, V.L.P., Goyal, K., and Kiah, H.M. (July, January 26). Sequence reconstruction problem for deletion channels: A complete asymptotic solution. Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT), Espoo, Finland."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/TIT.2021.3122798","article-title":"Coding for sequence reconstruction for single edits","volume":"68","author":"Cai","year":"2022","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"7141","DOI":"10.1109\/TIT.2022.3184868","article-title":"Correcting deletions with multiple reads","volume":"68","author":"Chrisnata","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/TIT.2022.3226296","article-title":"Correcting two-deletion with a constant number of reads","volume":"69","author":"Sun","year":"2023","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"4466","DOI":"10.1109\/TIT.2023.3250459","article-title":"Sequence reconstruction under single-burst-insertion\/deletion\/edit Channel","volume":"69","author":"Sun","year":"2023","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"3262","DOI":"10.1109\/TIT.2023.3319608","article-title":"On the Intersection of Multiple Insertion (or Deletion) Balls and Its Application to List Decoding Under the Reconstruction Model","volume":"70","author":"Yaakobi","year":"2024","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Sima, J., Gabrys, R., and Bruck, J. (2020, January 21\u201326). Syndrome compression for optimal redundancy codes. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174009"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1109\/JSAC.2010.100209","article-title":"Construction of maximum run-length limited codes using sequence replacement techniques","volume":"28","author":"Wijngaarden","year":"2010","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"5602","DOI":"10.1109\/TIT.2021.3066430","article-title":"Capacity-approaching constrained codes with error correction for DNA-based data storage","volume":"67","author":"Nguyen","year":"2021","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"5619","DOI":"10.1109\/TIT.2023.3279766","article-title":"Correcting k deletions and insertions in racetrack memory","volume":"69","author":"Sima","year":"2023","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/85\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:31:18Z","timestamp":1759919478000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,18]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["e27010085"],"URL":"https:\/\/doi.org\/10.3390\/e27010085","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,18]]}}}