Over the past two decades, irregular low-density parity-check (LDPC) codes have not been able to decode information corrupted by insertion and deletion (ID) errors without markers. In this paper, we bring to light the existence of irregular LDPC codes that approach the symmetric information rates (SIR) of the channel with ID errors, even without markers. These codes have peculiar shapes in their check-node degree distributions. Specifically, the check-node degrees are scattered and there are degree-2 check nodes. We propose a code construction method based on the progressive edge-growth algorithm tailored for the scattered check-node degree distributions, which enables the SIR-approaching codes to progress in the finite-length regime. Moreover, the SIR-approaching codes demonstrate asymptotic and finite-length performance that outperform the existing counterparts, namely, concatenated coding of irregular LDPC codes with markers and spatially coupled LDPC codes.

In this paper, we propose a method for enhancing performance of a sequential version of the belief-propagation (BP) decoding algorithm, the group shuffled BP decoding algorithm for low-density parity-check (LDPC) codes. An improved BP decoding algorithm, called the shuffled BP decoding algorithm, decodes each symbol node in serial at each iteration. To reduce the decoding delay of the shuffled BP decoding algorithm, the group shuffled BP decoding algorithm divides all symbol nodes into several groups. In contrast to the original group shuffled BP, which automatically generates groups according to symbol positions, in this paper we propose a method for grouping symbol nodes which generates groups according to the structure of a Tanner graph of the codes. The proposed method can accelerate the convergence of the group shuffled BP algorithm and obtain a lower error rate in a small number of iterations. We show by simulation results that the decoding performance of the proposed method is improved compared with those of the shuffled BP decoding algorithm and the group shuffled BP decoding algorithm.

We propose a coding/decoding strategy that surpasses the symmetric information rate of a binary insertion/deletion (ID) channel and approaches the Markov capacity of the channel. The proposed codes comprise inner trellis codes and outer irregular low-density parity-check (LDPC) codes. The trellis codes are designed to mimic the transition probabilities of a Markov input process that achieves a high information rate, whereas the LDPC codes are designed to maximize an iterative decoding threshold in the superchannel (concatenation of the ID channels and trellis codes).

Two decoding procedures combined with a belief-propagation (BP) decoding algorithm for low-density parity-check codes over the binary erasure channel are presented. These algorithms continue a decoding procedure after the BP decoding algorithm terminates. We derive a condition that our decoding algorithms can correct an erased bit which is uncorrectable by the BP decoding algorithm. We show by simulation results that the performance of our decoding algorithms is enhanced compared with that of the BP decoding algorithm with little increase of the decoding complexity.

For insertion and deletion channels, there are many coding schemes based on low-density parity-check (LDPC) codes, such as spatially coupled (SC) LDPC codes and concatenated codes of irregular LDPC codes and markers. However, most of the previous works have problems, such as poor finite-length performance and unrealistic settings for codeword lengths and decoding iterations. Moreover, when using markers, the decoder receives log-likelihood (LLR) messages with different statistics depending on code bit position. In this paper, we propose a novel concatenation scheme using protograph-based LDPC code and markers that offers excellent asymptotic/finite-length performance and a structure that controls the irregularity of LLR messages. We also present a density evolution analysis and a simple optimization procedure for the proposed concatenated coding scheme. For two decoding scenarios involving decoding complexity, both asymptotic decoding thresholds and finite-length performance demonstrate that the newly designed concatenated coding scheme outperforms the existing counterparts: the irregular LDPC code with markers, the SC-LDPC code, and the protograph LDPC code, which is optimized for an additive white Gaussian noise channel, with markers.

We study a modification method for constructing low-density parity-check (LDPC) codes for solid burst erasures. Our proposed modification method is based on a column permutation technique for a parity-check matrix of the original LDPC codes. It can change the burst erasure correction capabilities without degradation in the performance over random erasure channels. We show by simulation results that the performance of codes permuted by our method are better than that of the original codes, especially with two or more solid burst erasures.

In racetrack memories (RM), a position error (insertion or deletion error) results from unstable data reading. For position errors in RM with multiple read-heads (RHs), we propose a protograph-based LDPC coded system specified by a protograph and a protograph-aware permutation. The protograph-aware permutation facilitates the design and analysis of the coded system. By solving a multi-objective optimization problem, the coded system attains the properties of fast convergence decoding, a good decoding threshold, and a linear minimum distance growth. In addition, the coded system can adapt to varying numbers of RHs without any modification. The asymptotic decoding thresholds with a limited number of iterations verify the good properties of the system. Furthermore, for varying numbers of RHs, the simulation results with both small and large number of iterations, exhibit excellent decoding performances, both with short and long block lengths, and without error floors.

In this study, spatially coupled low-density parity-check (SC-LDPC) codes on the two-dimensional array erasure (2DAE) channel are devised, including a method for generating new SC-LDPC codes with a restriction on the check node constraint. A density evolution analysis confirms the improvement in the threshold of the proposed two-dimensional SC-LDPC code ensembles over the one-dimensional SC-LDPC code ensembles. We show that the BP threshold of the proposed codes can approach the corresponding maximum a posteriori (MAP) threshold of the original residual graph on the 2DAE channel. Moreover, we show that the rates of the residual graph of the two-dimensional LDPC block code ensemble are smaller than those of the one-dimensional LDPC block code ensemble. In other words, a high performance can be obtained by choosing the two-dimensional SC-LDPC codes.

Racetrack memory (RM) has attracted much attention. In RM, insertion and deletion (ID) errors occur as a result of an unstable reading process and are called position errors. In this paper, we first define a probabilistic channel model of ID errors in RM with multiple read-heads (RHs). Then, we propose a joint iterative decoding algorithm for spatially coupled low-density parity-check (SC-LDPC) codes over such a channel. We investigate the asymptotic behaviors of SC-LDPC codes under the proposed decoding algorithm using density evolution (DE). With DE, we reveal the relationship between the number of RHs and achievable information rates, along with the iterative decoding thresholds. The results show that increasing the number of RHs provides higher decoding performances, although the proposed decoding algorithm requires each codeword bit to be read only once regardless of the number of RHs. Moreover, we show the performance improvement produced by adjusting the order of the SC-LDPC codeword bits in RM.

A new ensemble of low-density parity-check (LDPC) codes for correcting a solid burst erasure is proposed. This ensemble is an instance of a combined matrix ensemble obtained by concatenating some LDPC matrices. We derive a new bound on the critical minimum span ratio of stopping sets for the proposed code ensemble by modifying the bound for ordinary code ensemble. By calculating this bound, we show that the critical minimum span ratio of stopping sets for the proposed code ensemble is better than that of the conventional one with keeping the same critical exponent of stopping ratio for both ensemble. Furthermore from experimental results, we show that the average minimum span of stopping sets for a solid burst erasure of the proposed codes is larger than that of the conventional ones.