In this thesis we study Low Density Parity Check (LDPC) and LDPC like codes over \nnon-binary fields. We extend the concepts used for non-binary LDPC codes to generalize \nProduct Accumulate (PA) codes to non-binary fields. We present simulation results that \nshow that PA codes over GF(4) performs considerably better than binary PA codes at \nsmaller block lengths and slightly better at large block lengths. We also propose a trellis \nbased decoding algorithm to decode PA codes and show that its complexity is \nconsiderably lower than the message-passing algorithm. \nIn the second part of the thesis we study the convergence properties of non-binary PA \ncodes and non-binary LDPC codes. We use EXIT-charts to study the convergence \nproperties of non-binary LDPC codes with different mean column weights and show why \ncertain irregularities are better. Although the convergence threshold predicted by EXIT-charts \non non-binary LDPC codes is quite optimistic we can still use EXIT-charts for \ncomparison between non-binary LDPC codes with different mean column weights.
In this thesis we study Low Density Parity Check (LDPC) and LDPC like codes over \nnon-binary fields. We extend the concepts used for non-binary LDPC codes to generalize \nProduct Accumulate (PA) codes to non-binary fields. We present simulation results that \nshow that PA codes over GF(4) performs considerably better than binary PA codes at \nsmaller block lengths and slightly better at large block lengths. We also propose a trellis \nbased decoding algorithm to decode PA codes and show that its complexity is \nconsiderably lower than the message-passing algorithm. \nIn the second part of the thesis we study the convergence properties of non-binary PA \ncodes and non-binary LDPC codes. We use EXIT-charts to study the convergence \nproperties of non-binary LDPC codes with different mean column weights and show why \ncertain irregularities are better. Although the convergence threshold predicted by EXIT-charts \non non-binary LDPC codes is quite optimistic we can still use EXIT-charts for \ncomparison between non-binary LDPC codes with different mean column weights.
In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.
In this thesis, we investigate the basics of Low-Density Parity-Check (LDPC) codes over binary and non-binary alphabets. We especially focus on the message passing decoding algorithms, which have different message definitions such as a posteriori probabilities, log-likelihood ratios and Fourier transforms of probabilities. We present the simulation results that compare the performances of small block length binary and non-binary LDPC codes, which have regular and irregular structures over GF(2),GF(4) and GF(8) alphabets. We observe that choosing non-binary alphabets improve the performance with careful selection of mean column weight by comparing LDPC codes with variable node degrees of 3, 2.8 and 2.6, since it is effective in the order of GF(2), GF(4) and GF(8) performances.
Non-binary LDPC codes can outperform binary LDPC codes using sum-product algorithm with higher computation complexity. Non-binary LDPC codes based on protographs have the advantage of simple hardware architecture. In the first part of this thesis, we will use EXIT chart analysis to compute the thresholds of different protographs over GF(q). Based on threshold computation, some non-binary protograph-based LDPC codes are designed and their frame error rates are compared with binary LDPC codes. For maximum-likelihood decoder, weight enumerator can predict frame error rate of an LDPC code. In the second part of this thesis, we calculate weight enumerators of protograph-based non-binary LDPC code ensembles both for finite length case and asymptotic case. In addition, the trapping set and stopping set enumerators are presented.
Non-binary low-density parity-check(LDPC) codes defined over the finite field GF(q=2p) are an extension of binary LDPC codes and have demonstrated improved performance over binary LDPC codes with the same frame length and rate.This paper introduces the principle of extrinsic information transfer(EXIT) charts,analyzes the convergence behavior of non-binary LDPC codes on AWGN channel,and confirms the thresholds of non-binary LDPC codes,which provides the foundation for analysis and design of real communication system using EXIT tool in future work.Simulation result shows that the performance of quaternary LDPC codes is better than that of binary LDPC codes in the same channel,and validates the superiority of using EXIT chart for iterative research.
This dissertation presents new methods for the analysis, design and decoding of low-density parity-check (LDPC) codes. We start by studying the simplest class of decoders: the binary message-passing (BMP) decoders. We show that the optimum BMP decoder must satisfy certain symmetry and isotropy conditions, and prove that Gallager's Algorithm B is the optimum BMP algorithm. We use a generalization of extrinsic information transfer (EXIT) charts to formulate a linear program that leads to the design of highly efficient irregular LDPC codes for the BMP decoder. We extend this approach to the design of irregular LDPC codes for the additive white Gaussian noise channel. We introduce a "semi-Gaussian" approximation that very accurately predicts the behaviour of the decoder and permits code design over a wider range of rates and code parameters than in previous approaches. We then study the EXIT chart properties of the highest rate LDPC code which guarantees a certain convergence behaviour. We also introduce and analyze gear-shift decoding in which the decoder is permitted to select the decoding rule from among a predefined set. We show that this flexibility can give rise to significant reductions in decoding complexity. Finally, we show that binary LDPC codes can be combined with quadrature amplitude modulation to achieve near-capacity performance in a multitone system over frequency selective Gaussian channels.
In this thesis, we propose low-complexity designing algorithms for non-binary low-density
parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding
algorithms for binary LDPC codes.
We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q)
based on message-passing algorithms. Short cycles in an NB-LDPC code may be even
more harmful to its performance if they do not satisfy the so-called full rank condition
(FRC). This is because they may induce low-weight codewords or absorbing sets in that
case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as
the number of short cycles for analyzing the performance of an NB-LDPC code. In order to
count those cycles, we first develop a novel message-passing algorithm and identify how it
is related to the FRC.We then propose a low-complexity algorithmfor counting the number
of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short
cycles. The proposed algorithm is not only theoretically validated, but its computational
and storage complexities are also computed. It does not require cycle enumeration with
high complexity, and therefore is still feasible even in the case of large code length, say
≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal
rule to choose a nonzero element for a given edge and propose a low-complexity algorithm
for designing an NB-LDPC code with low error floor. Furthermore, several design examples
are presented to verify the validity of the proposed design algorithm.
Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over
the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding
algorithm for binary LDPC codes and has lower computational complexity than the
sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it
has performance degradation. Furthermore, reducing the number of bits for representing
messages to two in a decoding algorithm for further reducing computational and storage
complexities, causes significant performance losses. In order to minimize the performance
degradation and computational and storage complexities, we propose a low-complexity
decoding algorithm which uses several decoders with two-bit precision for binary LDPC
codes over the BSC. The proposed algorithm adaptively changes decoders according to
the number of unsatisfied check nodes at each iteration. Compared with the SPA using
floating-point operations, the proposed decoding algorithm greatly reduces computational
and storage complexities with negligible performance losses. Numerical results show that
the proposed decoding algorithm has similar performance to the SPA with floating-point
operations over the BSC.
In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes
for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms
…