Very powerful long low-density parity-check (LDPC) codes, such as the ITU G.975.1 Standard (32643, 30592) LDPC Code [1], have been considered for optical communications. Traditional implementations of such long codes result in circuits requiring millions of interconnections, which are not affordable. This thesis investigates the performance of the hard-decision differential decoding with binary message-passing (DD-BMP) algorithm [2], a low-complexity algorithm requiring a minimal number of wires due to its binary messages. Our simulation results for the ITU G.975.1 standard demonstrate that hard-decision DD-BMP algorithm outperforms the results provided in the standard, and that the gap between the decoding performance of hard-decision DD-BMP and hard-decision sum-product is small at high signal-to-noise ratios (SNR). We also present a novel design methodology for implementing a soft-decision decoder by exploiting the code's structure. An implementation-efficient architecture is presented using a partially-parallel adaptation of the min-sum algorithm known as the line-passing algorithm. The line-passing algorithm makes soft-decision decoding available while requiring a minimal number of interconnections, which is attractive for long-haul optical communication systems.
Very powerful long low-density parity-check (LDPC) codes, such as the ITU G.975.1 Standard (32643, 30592) LDPC Code [1], have been considered for optical communications. Traditional implementations of such long codes result in circuits requiring millions of interconnections, which are not affordable. This thesis investigates the performance of the hard-decision differential decoding with binary message-passing (DD-BMP) algorithm [2], a low-complexity algorithm requiring a minimal number of wires due to its binary messages. Our simulation results for the ITU G.975.1 standard demonstrate that hard-decision DD-BMP algorithm outperforms the results provided in the standard, and that the gap between the decoding performance of hard-decision DD-BMP and hard-decision sum-product is small at high signal-to-noise ratios (SNR). We also present a novel design methodology for implementing a soft-decision decoder by exploiting the code's structure. An implementation-efficient architecture is presented using a partially-parallel adaptation of the min-sum algorithm known as the line-passing algorithm. The line-passing algorithm makes soft-decision decoding available while requiring a minimal number of interconnections, which is attractive for long-haul optical communication systems.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.
This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.
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
…
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.
Recent advances in coding theory have uncovered the previously forgotten power of Low-Density Parity-Check (LDPC) codes. Their popularity can be related to their relatively simple iterative decoders and their potential to achieve high performance close to shannon limit. These make them an attractive candidate for error correcting application in communication systems. In this thesis, we focus our research on the iterative decoding algorithms for Low-Density Parity-Check codes and present an improved decoding algorithm. First, the graph structure of LDPC codes is studied and a graph-based search algorithm to find the shortest closed walk and shortest cycle for each node of the graph is proposed. Then, the Deterministic schedule is applied on nodes of the graph with the objective of preserving the optimality of the algorithms. Finally, Hybrid Switch-Type technique is applied on the improved algorithms to provide a desirable complexity/performance trade-off. Hybrid Technique and Deterministic schedule are combined for decoding regular and irregular LDPC codes. The performance and complexity of the decoder is studied for Sum-Product and Gallager A algorithms. The result is a flexible decoder for any available LDPC code and any combination of decoding algorithms based on the communication systems need. In this technique, we benefit the high performance of soft-decision algorithms and low complexity of hard-decision algorithms by changing the decoding rule after a few iterations. Hence, a desirable performance can be obtained with less average number of soft iterations. Moreover, all the nodes do not update messages in each iteration. As a result, the total number of computations is reduced considerably