Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions
In this paper, we construct <i>q</i>-ary codes for correcting a burst of at most <i>t</i> deletions, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>t</mi><...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/1/85 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588497313071104 |
|---|---|
| author | Wentu Song Kui Cai Tony Q. S. Quek |
| author_facet | Wentu Song Kui Cai Tony Q. S. Quek |
| author_sort | Wentu Song |
| collection | DOAJ |
| description | In this paper, we construct <i>q</i>-ary codes for correcting a burst of at most <i>t</i> deletions, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>t</mi><mo>,</mo><mi>q</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>log</mi><mi>n</mi><mo>+</mo><mn>8</mn><mi>log</mi><mi>log</mi><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>log</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bits, encoding complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>q</mi><mrow><mn>7</mn><mi>t</mi></mrow></msup><mi>n</mi><msup><mrow><mo>(</mo><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> and decoding complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>. For the reconstruction scenario, our construction can recover the codewords with two reads and has redundancy <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>8</mn><mi>log</mi><mi>log</mi><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>log</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bits. The encoding complexity of this construction is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mrow><mn>7</mn><mi>t</mi></mrow></msup><mi>n</mi><msup><mrow><mo>(</mo><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup></mfenced></mrow></semantics></math></inline-formula>, and decoding complexity is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mrow><mn>9</mn><mi>t</mi></mrow></msup><msup><mrow><mo>(</mo><mi>n</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup></mfenced></mrow></semantics></math></inline-formula>. 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. |
| format | Article |
| id | doaj-art-974b12c42742491e9ee9dcba8ac49af3 |
| institution | Kabale University |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-974b12c42742491e9ee9dcba8ac49af32025-01-24T13:31:57ZengMDPI AGEntropy1099-43002025-01-012718510.3390/e27010085Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> DeletionsWentu Song0Kui Cai1Tony Q. S. Quek2Science, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, SingaporeScience, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, SingaporeScience, Mathematics and Technology (SMT) Cluster, Singapore University of Technology and Design, Singapore 487372, SingaporeIn this paper, we construct <i>q</i>-ary codes for correcting a burst of at most <i>t</i> deletions, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>t</mi><mo>,</mo><mi>q</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>log</mi><mi>n</mi><mo>+</mo><mn>8</mn><mi>log</mi><mi>log</mi><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>log</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bits, encoding complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>q</mi><mrow><mn>7</mn><mi>t</mi></mrow></msup><mi>n</mi><msup><mrow><mo>(</mo><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> and decoding complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>. For the reconstruction scenario, our construction can recover the codewords with two reads and has redundancy <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>8</mn><mi>log</mi><mi>log</mi><mi>n</mi><mo>+</mo><mi>o</mi><mo>(</mo><mi>log</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> bits. The encoding complexity of this construction is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mrow><mn>7</mn><mi>t</mi></mrow></msup><mi>n</mi><msup><mrow><mo>(</mo><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup></mfenced></mrow></semantics></math></inline-formula>, and decoding complexity is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mrow><mn>9</mn><mi>t</mi></mrow></msup><msup><mrow><mo>(</mo><mi>n</mi><mi>log</mi><mi>n</mi><mo>)</mo></mrow><mn>3</mn></msup></mfenced></mrow></semantics></math></inline-formula>. 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.https://www.mdpi.com/1099-4300/27/1/85deletion correcting codessequence reconstructionreconstruction codesburst-deletion |
| spellingShingle | Wentu Song Kui Cai Tony Q. S. Quek Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions Entropy deletion correcting codes sequence reconstruction reconstruction codes burst-deletion |
| title | Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions |
| title_full | Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions |
| title_fullStr | Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions |
| title_full_unstemmed | Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions |
| title_short | Some New Constructions of <i>q</i>-ary Codes for Correcting a Burst of at Most <i>t</i> Deletions |
| title_sort | some new constructions of i q i ary codes for correcting a burst of at most i t i deletions |
| topic | deletion correcting codes sequence reconstruction reconstruction codes burst-deletion |
| url | https://www.mdpi.com/1099-4300/27/1/85 |
| work_keys_str_mv | AT wentusong somenewconstructionsofiqiarycodesforcorrectingaburstofatmostitideletions AT kuicai somenewconstructionsofiqiarycodesforcorrectingaburstofatmostitideletions AT tonyqsquek somenewconstructionsofiqiarycodesforcorrectingaburstofatmostitideletions |