Analysis of decoding error probability for finite length LDPC codes ; 有限長の低密度パリティ検査符号の復号誤り率の解析

隆之 野崎

Takayuki Nozaki

Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.

R. Yazdani, Masoud Ardakani

An efficient method for finite-length low-density parity-check (LDPC) code analysis is proposed. This method is based on studying the channel variations when observed during a finite-length codeword. To this end, channel parameters are interpreted as random variables and their distributions are found. Assuming that a decoding failure is the result of an observed channel worse than the code's decoding threshold, the block error probability of finite-length LDPC codes is estimated. Using an extrinsic information transfer chart analysis, bit error probability is obtained from the block error probability. Our results suggest that by considering only the channel variations around its expected behavior and even ignoring the effects of cycles, one can closely predict the performance of LDPC codes of a few thousand bits or longer in the waterfall region.

Michael Lentmaier, Dmitri V. Truhachev, Daniel J. Costello +1 more

Michaelraj Kingston Roberts, Parthibaraj Anguraj

Yang Liu, Sha Sun, Yuzhi Zhang +1 more

Spatially coupled low density parity check (SC-LDPC) are prominent candidates for future communication standards due to their "threshold saturation" properties. To evaluate the finite-length performance of SC-LDPC codes, a general and efficient finite-length analysis from the perspective of the base matrix is proposed. We analyze the evolution of the residual graphs resulting at each iteration during the decoding process based on the base matrix and then derive the expression for the error probability. To verify the effectiveness of the proposed finite-length analysis, we consider the SC-LDPC code ensembles constructed by parallelly connecting multiple chains (PC-MSC-LDPC). The analysis results show that the predicted error probabilities obtained by using the derived expression for the error probability match the simulated error probabilities. The proposed finite-length analysis provides a useful engineering tool for practical SC-LDPC code design and for analyzing the effects of the code parameters on the performances.