This paper presents novel soft-decision decoding (SDD) of error correction codes (ECCs) that substantially improve the reliability of DNA-based data storage system compared with conventional hard-decision decoding (HDD). We propose a simplified system model for DNA-based data storage according to the major characteristics and different types of errors associated with the prevailing DNA synthesis and sequencing technologies. We compute analytically the error-free probability of each sequenced DNA oligonucleotide (oligo), based on which the soft-decision log-likelihood ratio (LLR) of each oligo can be derived. We apply the proposed SDD algorithms to the recently proposed DNA Fountain scheme. Simulation results show that SDD achieves an error rate improvement of two to three orders of magnitude over HDD, thus demonstrating its potential to improve the information density of DNA-based data storage systems.

This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.

The weighted bit-reliability-based (wBRB) algorithm for nonbinary LDPC codes suffers certain loss of symbol-reliability. Thus, this paper enhances its soft-decision version by passing multiple symbol-reliability instead of bit-reliability. Furthermore, it demonstrates that plurality robustly indicates symbol-reliability of extrinsic information-sums. Thus, this paper enhances the hard-decision version by introducing symbol-reliability from plurality. Analysis results show that these two enhanced decoding algorithms significantly outperform the wBRB algorithm with reasonable overhead.

This paper presents two packings derived from balanced incomplete block designs to construct quasi-cyclic spatially coupled LDPC convolutional codes (SC-LDPC-CCs). The construction gives time-invariant codes, since the sub-blocks corresponding to each time instant of the parity-check matrix are identical. Moreover, it provides flexible design rates and constraint lengths. Simulation results show that the proposed packing-based SC-LDPC-CCs outperform the existing time-invariant codes and perform closely to the time-varying protograph-based codes.

The traditional majority-logic decoding (MLgD) based algorithms suffer error-floors for decoding non-binary LDPC codes with small column weights. This paper presents a bit-reliability based MLgD (BRB-MLgD) algorithm with low error-floors for non-binary LDPC codes. The proposed algorithm is carried out based on the binary representations of non-binary symbols. The reliability update along each edge of the Tanner graph of a non-binary LDPC code is in terms of bits rather than symbols. Thus, its computational complexity and memory consumption are less than those of the existing MLgD based algorithms. Simulation results indicate that the proposed algorithm can significantly reduce error-floors with small performance degradation in the waterfall region.

The efficient encoding of quasi‐cyclic (QC) low‐density parity‐check (LDPC) codes is based on generator matrices in systematic‐circulant (SC) form. The cost of the encoders of QC‐LDPC codes mainly depends on the number of non‐zero entries in the SC generator matrices. This study introduces a novel construction of SC generator matrices based on matrix transformations via Galois Fourier transform. By revealing the structure of SC generator matrices in the transform domain, an algorithm is proposed to reduce the density of the generator matrices of QC‐LDPC codes. Furthermore, a tight upper bound on ranks of QC matrices is derived. Based on the bound, rank distributions of parity‐check matrices and generator matrices in the transform domain illustrate the efficiency of the proposed algorithm. Simulation results show that the density of their SC generator matrices can be significantly decreased with moderate computational complexity.

This paper presents bit-reliability based majority-logic decoding (MLgD) algorithms for non-binary LDPC codes. The proposed algorithms pass only one Galois field element and its reliability along each edge of the Tanner graph of a non-binary LDPC code. Since their reliability updates are in terms of bits rather than symbols, they are more efficient than traditional MLgD based decoding algorithms. By weighting the soft reliability of the extrinsic information-sums based on their hard reliability, the proposed algorithms can achieve good error performance for non-binary LDPC codes with various column weights. Moreover, their computational complexity and memory consumption are remarkably reduced compared with existing MLgD based decoding algorithms. As a result, they provide effective tradeoffs between error performance and complexity for decoding of non-binary LDPC codes.