Back to Search
Start Over
Criss-Cross Insertion and Deletion Correcting Codes.
- Source :
- IEEE Transactions on Information Theory; Dec2021, Vol. 67 Issue 12, p7999-8015, 17p
- Publication Year :
- 2021
-
Abstract
- This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]
- Subjects :
- DECODING algorithms
HUFFMAN codes
ERROR-correcting codes
ENCODING
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731593
- Full Text :
- https://doi.org/10.1109/TIT.2021.3111450