Search

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., Comment: Submitted to ICASSP

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 \emph{et al.}, which incorporates some of its physical aspects. This channel model can be viewed as a sliding window of length $\ell$ that passes over the incoming input sequence and produces the Hamming weight of the enclosed $\ell$ bits, while shifting by one position at each time step. The resulting $(\ell+1)$-ary vector, referred to as the $\ell$-\emph{read vector}, is susceptible to deletion errors due to imperfections inherent in the sequencing process. We establish that at least $\log n - \ell$ 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 $\ell \geq 2$, reconstruction from two distinct noisy $\ell$-read vectors can be accomplished without any redundancy, and provide a suitable reconstruction algorithm to this effect., Comment: Accepted at IEEE ISIT'24

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 Mao \emph{et al.}, incorporating intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of length \(\ell\) over a \(q\)-ary input sequence that outputs the \textit{composition} of the enclosed \(\ell\) bits and shifts by \(\delta\) positions with each time step. In this context, the composition of a \(q\)-ary vector $\bfx$ specifies the number of occurrences in \(\bfx\) of each symbol in \(\lbrace 0,1,\ldots, q-1\rbrace\). The resulting compositions vector, termed the \emph{read vector}, may also be corrupted by \(t\) substitution errors. By employing graph-theoretic techniques, we deduce that for \(\delta=1\), at least \(\log \log n\) symbols of redundancy are required to correct a single (\(t=1\)) substitution. Finally, for \(\ell \geq 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., Comment: Submitted to Transactions on Information Theory

Sequential decoding, commonly applied to substitution channels, is a sub-optimal alternative to Viterbi decoding with significantly reduced memory costs. In this work, a sequential decoder for convolutional codes over channels that are prone to insertion, deletion, and substitution errors, is described and analyzed. 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 a couple orders of magnitude in comparison 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 with numerical evaluations of bit error rates and computational complexity, which are compared with respect to optimal Viterbi decoding.

Synthetic polymer-based 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 the \emph{composition}, i.e. the number of $1$s and $0$s 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, called \emph{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 builds on this research by generalizing 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 \emph{et al.} is indeed robust to such errors, and if not, propose new coding constraints to remedy this.