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.

In this work, we consider the problem of efficient decoding of codes from insertions and deletions. Most of the known efficient codes are codes with synchronization strings which allow one to reduce the problem of decoding insertions and deletions to that of decoding substitution and erasures. Our new approach, presented in this paper, reduces the problem of decoding insertions and deletions to that of list recovery. Specifically, any ($\rho, 2 \rho n+1, L$) -list-recoverable code is a ($\rho, L$) -list decodable insdel code. As an example, we apply this technique to Reed-Solomon (RS) codes, which are known to have efficient listrecovery algorithms up to the Johnson bound. In the adversarial insdel model, this provides efficient (list) decoding from$t$insdel errors, assuming that$t \cdot k=O(n)$. This is the first efficient insdel decoder for$[n, k]$RS codes for$k>2$. Additionally, we explore random insdel models, such as the Davey-MacKay channel, and show that for certain choices of$\rho$, a$\left(\rho, n^{1 / 2+0.001}, L\right)$-listrecoverable code of length$n$can, with high probability, efficiently list decode the channel output, ensuring that the transmitted codeword is in the output list. In the context of RS codes, this leads to a better rate-error tradeoff for these channels compared to the adversarial case. We also adapt the KoetterVardy algorithm, a famous soft-decision list decoding technique for RS codes, to correct insertions and deletions induced by the Davey-MacKay channel.

Despite their significant advantages over competing technologies, nanopore sequencers are plagued by high error rates, due to physical characteristics of the nanopore and inherent noise in the biological processes. It is thus paramount not only to formulate efficient error-correcting constructions for these channels, but also to establish bounds on the minimum redundancy required by such coding schemes. In this context, we adopt a simplified model of nanopore sequencing inspired by the work of Mao et al., accounting for the effects of intersymbol interference and measurement noise. For an input sequence of length$n$, The vector that is produced, designated as the read vector, may additionally suffer at most$t$substitution errors. We employ the well-known graph-theoretic clique-cover technique to establish that at least$t \log n-O(1)$bits of redundancy are required to correct multiple ($t \geqslant 2$) substitutions. While this is surprising in comparison to the case of a single substitution, that necessitates at most$\log \log n-O(1)$bits of redundancy, a suitable error-correcting code that is optimal up to a constant follows immediately from the properties of read vectors.

Owing to its several merits over other DNA sequencing technologies, nanopore sequencers hold an immense potential to revolutionize the efficiency of DNA storage systems. However, their higher error rates necessitate further research to devise practical and efficient coding schemes that would allow accurate retrieval of the data stored. Our work takes a step in this direction by adopting a simplified model of the nanopore sequencer inspired by Mao et al., which incorporates some of its physical aspects. This channel model can be viewed as a sliding window of length ℓ that passes over the incoming input sequence and produces the Hamming weight of the enclosed ℓ bits, while shifting by one position at each time step. The resulting (ℓ + 1)-ary vector, referred to as the ℓ-read vector, is susceptible to deletion errors due to imperfections inherent in the sequencing process. We establish that at least log$n$- ℓ bits of redundancy are needed to correct a single deletion. An error-correcting code that is optimal up to an additive constant, is also proposed. Furthermore, we find that for ℓ ≥ 2, reconstruction from two distinct noisy ℓ-read vectors can be accomplished without any redundancy, and provide a suitable reconstruction algorithm to this effect.

Sequential decoding, commonly applied to substitution channels, is a sub-optimal alternative to Viterbi decoding with significantly reduced memory costs. This work describes and analyzes a sequential decoder for convolutional codes over channels prone to insertion, deletion, and substitution errors. Our decoder expands the code trellis by a new channel-state variable, called drift state, as proposed by Davey and MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, generalizing the original Fano metric. The decoder is also extended to facilitate the simultaneous decoding of multiple received sequences that arise from a single transmitted sequence. Under low-noise environments, our decoding approach reduces the decoding complexity by multiple orders of magnitude compared to Viterbi’s algorithm, albeit at slightly higher bit error rates. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported by numerical evaluations of bit error rates and computational complexity, compared to optimal Viterbi decoding.

Nanopore sequencing, superior to other sequencing technologies for DNA storage in multiple aspects, has recently attracted considerable attention. Its high error rates, however, demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Maoet al., incorporating intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of lengthlover aq-ary input sequence that outputs thecompositionof the enclosedlbits, and shifts by δ positions with each time step. In this context, the composition of aq-ary vectorxspecifies the number of occurrences inxof each symbol in {0,1,...,q- 1}. The resulting compositions vector, termed theread vector, may also be corrupted bytsubstitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log lognsymbols of redundancy are required to correct a single (t= 1) substitution. Finally, forl≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is of optimal redundancy up to a (small) additive constant for this setting. This construction is also found to be optimal for the case of reconstruction from two noisy read vectors.

Nanopore sequencers, being superior to other sequencing technologies for DNA storage in multiple aspects, have attracted considerable attention in recent times. Their high error rates however demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Mao et al., that incorporates intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of length ℓ over an input sequence, that outputs the L1-weight of the enclosed ℓ bits and shifts by δ positions with each time step. The resulting (ℓ + 1)-ary vector, termed the read vector, may also be corrupted by t substitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log log n bits of redundancy are required to correct a single (t = 1) substitution. Finally for ℓ ≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is optimal up to an additive constant for this setting.

Synthetic polymer-based data storage seems to be a particularly promising candidate that could help to cope with the ever-increasing demand for archival storage requirements. It involves designing molecules of distinct masses to represent the respective bits {0,1}, followed by the synthesis of a polymer of molecular units that reflects the order of bits in the information string. Reading out the stored data requires the use of a tandem mass spectrometer, that fragments the polymer into shorter substrings and provides their corresponding masses, from which thecomposition, i.e. the number of 1s and 0s in the concerned substring can be inferred. Prior works have dealt with the problem of unique string reconstruction from the set of all possible compositions, calledcomposition multiset. This was accomplished either by determining which string lengths always allow unique reconstruction, or by formulating coding constraints to facilitate the same for all string lengths. Additionally, error-correcting schemes to deal with substitution errors caused by imprecise fragmentation during the readout process, have also been suggested. This work builds on this research by extending previously considered error models, mainly confined to substitution of compositions. To this end, we define new error models that consider insertions of spurious compositions and deletions of existing ones, thereby corrupting the composition multiset. We analyze if the reconstruction codebook proposed by Pattabiraman et al. is indeed robust to such errors, and if not, propose new coding constraints to remedy this.

Synthetic polymer-based storage promises to accommodate the ever-increasing demand for archival storage. It involves designing molecules of distinct masses to represent the respective bits {0, 1}, followed by the synthesis of a polymer of molecular units that reflects the order of bits in the information string. The stored data can be read by means of a tandem mass spectrometer, that fragments the polymer into shorter substrings and provides their corresponding masses, from which the composition, i.e., the number of 1s and 0s in the concerned substring can be inferred. Prior works tackled the problem of unique string reconstruction from the set of all possible compositions, called the composition multiset. This was accomplished either by determining which string lengths always allow unique reconstruction, or by formulating coding constraints to facilitate the same for all string lengths. Additionally, error-correcting schemes to deal with substitution errors caused by imprecise fragmentation during the readout process, have also been suggested. This work extends previously considered error models that were mainly confined to substitutions of compositions. Our new error models consider insertions and deletions of compositions. The robustness of the reconstruction codebook proposed by Pattabiraman et al. to such errors is examined, and whenever necessary, new coding constraints are proposed to ensure unique reconstruction.

In this work, a sequential decoder for convolutional codes over channels that are vulnerable to insertion, deletion, and substitution errors, is described and analyzed. The decoder expands the code trellis by introducing a new channel state variable, called drift state, as proposed by Davey-MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, in a manner that generalizes the original Fano metric. Under low-noise environments, this approach reduces the decoding complexity by a couple orders of magnitude in comparison to Viterbi’s algorithm. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported with numerical evaluations of bit error rates and computational complexity, which are compared with respect to optimal Viterbi decoding.