Standard decoding approaches for convolutional codes, such as the Viterbi and BCJR algorithms, entail significant complexity when correcting synchronization errors. The situation worsens when multiple received sequences should be jointly decoded, as in DNA storage. Previous work has attempted to address this via separate-BCJR decoding, i.e., combining the results of decoding each received sequence separately. Another attempt to reduce complexity adapted sequential decoders for use over channels with insertion and deletion errors. However, these decoding alternatives remain prohibitively expensive for high-rate convolutional codes. To address this, we adapt sequential decoders to decode multiple received sequences jointly over the syndrome trellis. For the short blocklength regime, this decoding strategy can outperform separate-BCJR decoding under certain channel conditions, in addition to reducing decoding complexity. To mitigate the occurrence of a decoding timeout, formally called erasure, we also extend this approach to work bidirectionally, i.e., deploying two independent stack decoders that simultaneously operate in the forward and backward directions.

We consider error-correcting coding for DNA-based storage. We model the DNA storage channel as a multi-draw IDS channel where the input data is chunked into M short DNA strands, which are copied a random number of times, and the channel outputs a random selection of N noisy DNA strands. The retrieved DNA strands are prone to insertion, deletion, and substitution (IDS) errors. We propose an index-based concatenated coding scheme consisting of the concatenation of an outer code, an index code, and an inner synchronization code, where the latter two tackle IDS errors. We further propose a mismatched joint index-synchronization code maximum a posteriori probability decoder with optional clustering to infer symbolwise a posteriori probabilities for the outer decoder. We compute achievable information rates for the outer code and present Monte-Carlo simulations for information-outage probabilities and frame error rates on synthetic and experimental data, respectively.

Decoding sequences that stem from multiple transmissions of a codeword over an insertion, deletion, and substitution channel is a critical component of efficient deoxyribonucleic acid (DNA) data storage systems. In this paper, we consider a concatenated coding scheme with an outer nonbinary low-density parity-check code or a polar code and either an inner convolutional code or a time-varying block code. We propose two novel decoding algorithms for inference from multiple received sequences, both combining the inner code and channel to a joint hidden Markov model to infer symbolwise a posteriori probabilities (APPs). The first decoder computes the exact APPs by jointly decoding the received sequences, whereas the second decoder approximates the APPs by combining the results of separately decoded received sequences and has a complexity that is linear with the number of sequences. Using the proposed algorithms, we evaluate the performance of decoding multiple received sequences by means of achievable information rates and Monte-Carlo simulations. We show significant performance gains compared to a single received sequence. In addition, we succeed in improving the performance of the aforementioned coding scheme by optimizing both the inner and outer codes.

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of non-binary single-deletion$s$-substitution correcting codes is derived, showing that the non-asymptotic redundancy of such a code of length$n$has to be at least$(s+1) \log _{q} n$. An explicit construction of binary single-deletion single-substitution correcting codes with at most$6 \log n + 8$redundancy bits is presented.

We consider the problem of correcting insertion and deletion errors in the d-dimensional space. This problem is well understood for vectors (one-dimensional space) and was recently studied for arrays (two-dimensional space). For vectors and arrays, the problem is motivated by several practical applications such as DNA-based storage and racetrack memories. From a theoretical perspective, it is interesting to know whether the same properties of insertion/deletion correcting codes generalize to the d-dimensional space. In this work, we show that the equivalence between insertion and deletion correcting codes generalizes to the d-dimensional space. As a particular result, we show the following missing equivalence for arrays: a code that can correct trand tcrow/column deletions can correct any combination of $t_{\text{r}}^{{\text{ins}}} + t_{\text{r}}^{{\text{del}}} = {t_{\text{r}}}{\text{ and }}t_{\text{c}}^{{\text{ins}}} + t_{\text{c}}^{{\text{del}}} = {t_{\text{c}}}$ row/column insertions and deletions. The fundamental limit on the redundancy and a construction of insertion/deletion correcting codes in the d-dimensional space remain open for future work.

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 deletionsdefined 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.

This paper investigates the problem of correcting multiple criss-cross deletions in arrays. More precisely, we study the unique recovery of$n\times n$arrays affected by 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 refer to these type of deletions as t-criss-cross deletions. We show that the asymptotic redundancy of a code correcting t-criss-cross deletions is at least$tn+t\log n-\log(t!)$. Then, we present an existential construction of a code capable of correcting t-criss-cross deletions where its redundancy is bounded from above by$tn+\mathcal{O}(t^{2}\log^{2}n)$. The main ingredients of the presented code are systematic binary t-deletion-correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the deleted rows and columns, thus transforming the deletion-correction problem into an erasure-correction problem which is then solved using the second ingredient.

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 deletionsif${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 forcriss-cross insertionsare 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.

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of singledeletion single-substitution correcting codes is derived, showing that the redundancy of such a code of length n has to be at least 2 log n. The bound is presented both for binary and non-binary codes while an extension to single deletion and multiple substitutions is presented for binary codes. An explicit construction of single-deletion single-substitution correcting codes with at most 6 log n + 8 redundancy bits is derived. Note that the best known construction for this problem has to use 3-deletion correcting codes whose best known redundancy is roughly 24 log n.

Decoding sequences that stem from multiple transmissions of a codeword over an insertion, deletion, and substitution channel is a critical component of efficient deoxyribonucleic acid (DNA) data storage systems. In this paper, we consider a concatenated coding scheme with an outer low-density parity-check code and either an inner convolutional code or a block code. We propose two new decoding algorithms for inference from multiple received sequences, both combining the inner code and channel to a joint hidden Markov model to infer symbolwise a posteriori probabilities (APPs). The first decoder computes the exact APPs by jointly decoding the received sequences, whereas the second decoder approximates the APPs by combining the results of separately decoded received sequences. Using the proposed algorithms, we evaluate the performance of decoding multiple received sequences by means of achievable information rates and Monte-Carlo simulations. We show significant performance gains compared to a single received sequence.

A new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Assume that the encoder transmits $$n$$ binary symbols one by one over a channel in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about insertions or deletions that have occurred within the previous transmission, and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $$\tau n$$ , $$0<\tau<1$$ . We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later completed by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof.