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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1099-4300 |