Back to Search
Start Over
Multiple Criss-Cross Insertion and Deletion Correcting Codes.
- Source :
-
IEEE Transactions on Information Theory . Jun2022, Vol. 68 Issue 6, p3767-3779. 13p. - Publication Year :
- 2022
-
Abstract
- This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BINARY codes
*CODECS
*ERROR-correcting codes
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 68
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 157007236
- Full Text :
- https://doi.org/10.1109/TIT.2022.3152398