Motivated by duplex read sequencing developed by Oxford Nanopore Technologies, this paper proposes a concatenated coding scheme for nanopore sequencers where DNA sequences are decoded from noisy reads of the template and reverse-complement strands from the same DNA molecule, that is, a duplex read. First, we show that the double-strand pairwise error probability (PEP) bound is multiplicative with respect to the single-strand PEP bounds of the template and reverse-complement codebooks, thus giving duplex decoders significantly lower error rates compared to simplex decoders which only use the template strand. Then, we propose a decoder for multiple concatenations of short codebooks designed using the double-strand PEP bound.

Nanopore sequencing enables reading strings of A,C,G,T nucleotides in DNA strands by pulling them into nanopores with the help of motor proteins. Due to the discrete stepping of motor proteins, the signals produced by a DNA sequence tend to be piecewise-constant expansions of some underlying real-valued sequence. In this paper, we assume that every k-nucleotide sequence corresponds to a real-valued codeword of length$k$, and model the nanopore channel as a noisy duplication channel that stretches every sample of a codeword using a geometric distribution, and then adds Gaussian noise. We show that for this channel, a simpler variant of the dynamic time warping (DTW) algorithm performs maximum likelihood decoding. Next, we devise an$O(k^{2})$- algorithm for bounding the pairwise error probability between two codewords of length$k$. Finally, we use Scrappie to design codebooks with a storage efficiency of 1 bit per nucleotide and demonstrate using error simulations the accuracy of the calculated error bounds.

In this paper, we calculate a union bound for dynamic time warping (DTW)-based decoding of piecewise constant signals corrupted by additive noise and time stretching due to sample duplications, as observed in raw measurement signals obtained from nanopore sequencers. We consider both finitely- and infinitely-supported duplications with geometric-like characteristic, which include discrete uniform distributions as a special case. First, we provide explicit algorithms that calculate the union bound in O(αk2) time for the infinite-support case and in O(β2k2) for the finite-support case, where k is the codeword length, α is the minimum duplication, and β is the maximum duplication. Next, we show that a multi-read union bound exhibits a thresholding effect, where the error probability can be made arbitrarily close to zero by aggregating DTW distances from sufficiently many independent reads. Finally, we validate the calculated bounds relative to simulation results.

Non-binary low-density parity-check (NB-LDPC) codes can offer promising performance advantages but suffer from high decoding complexity. To tackle this challenge, in this paper, we consider NB-LDPC codes over finite fields as codes over subfields as a means of reducing decoding complexity. In particular, our approach is based on a novel method of expanding a non-binary Tanner graph over a finite field into a graph over a subfield. This approach offers several decoding strategies for a single NB-LDPC code, with varying levels of performance-complexity trade-offs. Simulation results demonstrate that in a majority of cases, performance loss is minimal when compared with the complexity gains.

NB-LDPC codes, a class of codes well-known for their exceptional error correcting performance, are not yet used widely in practice due to the high complexity of decoding algorithms. In this paper, we propose a low complexity decoder for these codes by means of a novel graph expansion. We view the finite field over which the code is constructed as the quadratic extension of one of its subfields, and then expand the Tanner graph of the code into a graph over that particular field. Decoding algorithm, which is tailored for this larger graph, presents significant complexity gains while the performance loss is minimal.

Staircase codes, a class of product-like codes, have been demonstrated to perform exceptionally well in optical transmission systems. Although they are predominantly used with BCH component codes and hard decision decoding, soft decision decoding has also been recently attempted, with BCH and polar code based staircase codes. We consider using LDPC codes as the component code of soft decoded staircase codes. Results demonstrate that these codes offer very good performance, with gains in the range of 0.5-1dB over soft decoded BCH-staircase codes, at a BER of 1$0^{-8}$. These can be further improved through the novel bit-flipping scheme we propose.

Non-binary low-density parity-check (NB-LDPC) codes are known to offer several advantages over their binary counterparts, but the higher complexity, and the resource-hungry nature of decoding algorithms have so far restricted their practical usage. In this paper, we propose a new decoding algorithm for NB-LDPC codes over finite fields of characteristic 2, based on a novel binary expansion of the Q-ary Tanner graph. While it offers substantial complexity gains, simulation results demonstrate that the performance loss of the new algorithm, in comparison to the best known decoder, is quite small. Furthermore, due to being based on a binary graph, it is particularly attractive for hardware implementations. We also suggest a simplified version of the algorithm, which offers even higher gains in complexity.

A novel iterative approach for soft-decision decoding of Reed-Solomon codes is presented that employs symbol-level belief propagation on an alternative parity-check matrix representation of the code. Construction of a suitable matrix is discussed from the viewpoint of iterative decoding, and certain conditions are derived on existence of structures detrimental for decoding. Simulation results demonstrate that the novel scheme performs substantially better than hard-decision decoding, especially with high rate codes, while being of much lower complexity than existing soft-decision decoding methods. Proposed method is also well-suited for efficient hardware implementations.

This paper presents a majority-logic decoding (MLgD) algorithm for non-binary LDPC codes based on a novel expansion of the Tanner graph. The expansion introduced converts the Q-ary graph into a binary one, which makes the new MLgD algorithm more attractive for hardware implementations. Proposed algorithm performs significantly better than the existing MLgD algorithms in the waterfall region, and it shows a much lower error-floor as well. Algorithm only requires integer additions, comparisons, finite field operations and some binary operations. Thus, it offers an effective trade-off between performance and complexity in decoding non-binary LDPC codes.