| 1. |
- Lenz, Andreas, et al.
(author)
-
Concatenated Codes for Recovery From Multiple Reads of DNA Sequences
- 2021
-
In: 2020 IEEE Information Theory Workshop, ITW 2020.
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
| 2. |
- Maarouf, Issam, et al.
(author)
-
Achievable Information Rates and Concatenated Codes for the DNA Nanopore Sequencing Channel
- 2023
-
In: 2023 IEEE Information Theory Workshop, ITW 2023. ; , s. 377-382
-
Conference paper (peer-reviewed)abstract
- The errors occurring in DNA-based storage are correlated in nature, which is a direct consequence of the synthesis and sequencing processes. In this paper, we consider the memory-k nanopore channel model recently introduced by Hamoum et al., which models the inherent memory of the channel. We derive the maximum a posteriori (MAP) decoder for this channel model. The derived MAP decoder allows us to compute achievable information rates for the true DNA storage channel assuming a mismatched decoder matched to the memory-k nanopore channel model, and quantify the loss in performance assuming a small memory length - and hence limited decoding complexity. Furthermore, the derived MAP decoder can be used to design error-correcting codes tailored to the DNA storage channel. We show that a concatenated coding scheme with an outer low-density parity-check code and an inner convolutional code yields excellent performance.
|
|
| 3. |
- Maarouf, Issam, et al.
(author)
-
Concatenated Codes for Multiple Reads of a DNA Sequence
- 2023
-
In: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 69:2, s. 910-927
-
Journal article (peer-reviewed)abstract
- 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.
|
|
| 4. |
- Maarouf, Issam, et al.
(author)
-
Finite Blocklength Performance Bound for the DNA Storage Channel
- 2023
-
In: 2023 12th International Symposium on Topics in Coding, ISTC 2023.
-
Conference paper (peer-reviewed)abstract
- We present a finite blocklength performance bound for a DNA storage channel with insertions, deletions, and substitutions. The considered bound - the dependency testing (DT) bound, introduced by Polyanskiy et at. in 2010 - , provides an upper bound on the achievable frame error probability and can be used to benchmark coding schemes in the practical short-to-medium blocklength regime. In particular, we consider a concatenated coding scheme where an inner synchronization code deals with insertions and deletions and the outer code corrects remaining (mostly substitution) errors. The bound depends on the inner synchronization code. Thus, it allows to guide its choice. We then consider low-density parity-check codes for the outer code, which we optimize based on extrinsic information transfer charts. Our optimized coding schemes achieve a normalized rate of 87% to 97% with respect to the DT bound for code lengths up to 2000 DNA symbols for a frame error probability of $10^{-3}$ and code rate 1/2.
|
|
| 5. |
- Welter, Lorenz, et al.
(author)
-
Index-Based Concatenated Codes for the Multi-Draw DNA Storage Channel
- 2023
-
In: 2023 IEEE Information Theory Workshop, ITW 2023. ; , s. 383-388
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
