Performance and Complexity Trade-Off between Short-Length Regular and Irregular LDPC ()
1. Introduction
LDPC codes are widely specified and deployed in digital communication systems [1]. It is well known that regular LDPC codes enjoy the benefit of better weight profile and higher minimum distance, hence near-optimal performance using ML decoding with high-complexity, but face the problem of worse performance using low-complexity iterative belief propagation decoding [2]. On the contrary, irregular LDPC codes, if carefully designed, show better performance with iterative belief propagation decoding, and sub-optimal performance using ML decoding [3].
In the regime of long LDPC codes, the well-designed irregular LDPC code is able to achieve capacity-approaching performance, while enjoy the benefit of low-complexity iterative belief propagation decoding. Hence, irregular LDPC codes are suitable for the scenario demanding long code-length [4].
The story is different in the regime of short code-length. Even the well-designed irregular LDPC codes still face the problem of degraded performance using iterative belief propagation decoding and error-floor due to worse weight profile and lower minimum distance [5]. The results will be shown in this paper and a CRC-aided hybrid decoding is proposed to provide the trade-off between performance and complexity. Without the consideration of CRC-aided technique, the alternative approach is to employ the solution with regular LDPC codes. Many near-ML decodings are proposed to approach the performance with optimal ML decoding, and most of them adopt the idea of list-decoding [6] [7]. The complexity is prohibitive for long code-length, even with near-ML list decoding. However, the complexity can be controlled down to an affordable level at least for short code-length, and the “hybrid BP decoding and near-ML decoding” (Hybrid Decoding, in short) will bring-down the overall complexity considerably [8]-[10]. Hence, the regular LDPC code with near-ML list decoding could be a competitive candidate for scenario demanding short code-length and excellent decoding performance, especially the excellent low error-floor performance.
In this paper, both the high-complexity near-ML list decoding and the low complexity belief propagation decoding [11] are tested for some well-known regular and irregular LDPC codes. The complexity and performance trade-off is shown clearly and can be readily demonstrated with the paradigm of hybrid decoding. For regular LDPC code, the SNR-threshold performance and error-floor performance could be improved to the optimal level of ML decoding if the decoding complexity is progressively increased, usually corresponding to the decoding with progressively increased size of list. For irregular LDPC code, the SNR-threshold performance and error-floor performance could only be improved to a bottle-neck even with unlimited decoding complexity. However, with the technique of CRC-aided hybrid decoding, the near-ML performance could be greatly improved and approached with reasonable complexity thanks to the improved code-weight distribution from the concatenation of CRC and irregular LDPC code. Finally, CRC-aided NR LDPC code is evaluated and the capacity-approaching capability is shown.
2. System Model and Hybrid Near-ML List-Decoding
The system model is quite simple, where the BI-AWGN channel is assumed, the messages of LLR for the LDPC codeword are the input of the LDPC decoder under test. Two types of LDPC decoding algorithm are considered. The one is iterative BP decoding only, to be exactly, the low-complexity Sum-Product algorithm with layered scheduling [12] [13], the other is the hybrid decoding, i.e., the hybrid Sum-Product algorithm and near-ML list decoding. The procedure of the hybrid decoding is illustrated in the following:
1) For each decoding input, perform the iterative BP decoding firstly.
2) If the BP decoding is failed (LDPC parity-check is not satisfied), perform the near-ML list decoding with 1st-level list-size.
3) If the near-ML list decoding with ith-level list-size is failed, perform the near-ML list decoding with (i + 1)th level list-size.
4) The decoding will stop if the BP decoding is successful, or the near-ML list decoding with ith level list-size is successful, or the complexity budget is exhausted.
Note that each successful of BP decoding leads to both possibilities, one is correct reception, the other is non-detectable error (i.e., the decoding result is a legal codeword different from the transmitted codeword, if the outer code of Cyclic Redundancy Check (CRC) is not considered.).
3. Simulation Results
Only 1/2 code-rate and 504 code-length are considered in this paper. The regular LDPC code candidate is Regular (3, 6) LDPC codes constructed by D. MacKay [14]. The irregular LDPC code candidate is constructed using the well-known progressive-edge-growth (PEG) method [15].
To evaluate the performance of iterative BP decoding, the asymptotical SNR-thresholds using density-evolution analysis tool are given, which are 0.648 dB and 1.119 dB under BI-AWGN channel for the above-mentioned irregular and regular LDPC codes. The advantage of the irregular LDPC code over the regular one is clear, 0.471 dB lower SNR-threshold. Furthermore, the error-floor performance of iterative BP decoding is constrained due to trapping-set problem in short-length regime of LDPC code, whether it is regular or irregular [16].
To evaluate the performance of hybrid decoding, the low weight profiles with code-weight up to two or three times of the minimum code-weight are computed using the method proposed in [17] [18], to help determine the truncated union-bound for ML decoding. The low weight profiles for the regular and irregular LDPC code are in the following:
A(x)|regular (504, 252) = 2x20 + 22x22 + 117x24 + 480x26 + 2438x28 + 10829x30 + 38477x32 + 109104x34 + 271251x36 + 613267x38 + 1312218x40 + 2690330x42 + 4337566x44
A(x)|irregular (504, 252) = x13 + x14 + 5x15 + 11x16 + 16x17 + 28x18 + 60x19 + 121x20 + 248x21 + 465x22 + 977x23 + 1895x24 + 3748x25 + 7272x26 + 13358x27 + 24094x28 + 41582x29 + 69334x30 + 109114x31 + 164248x32 + 242839x33 + 343041x34 + 472572x35 + 638599x36 + 231041x37 + 295580x38
The bad performance of the truncated union-bound for irregular LDPC code is shown in Figure 1. The SNR-BLER curve for the irregular LDPC code is not steep due to limited minimum code-weight of 13, while the SNR-BLER curve for regular code is steeper due to improved minimum code-weight of 20. It is note-worthy that the truncated union-bound is the approximate lower bound, which may not be the tight bound, especially for the code with good weight profile.
Considering the huge computing resources for the (504, 252) code, only 1st-level list size of O(n) is adopted for near-ML list decoding in the hybrid decoding of this paper, while the performance achieved is already good enough. The other simulation parameters are listed in the following: BI-AWGN channel model, SPA decoding with layered scheduling and maximum iteration of 60.
The SNR-BLER simulation results for both LDPC codes and both iterative BP and hybrid decoding are all shown in Figure 1, where the results for BLER lower than 1e−7 are shown to help analyze the error-floor performance. At the same time, the Gaussian-approximation finite-length bound is also depicted to help understand the potential excellent ML performance of regular (504, 252) LDPC code [19] [20].
![]()
Figure 1. Performance comparison between regular and irregular (504, 252) LDPC codes with both iterative BP decoding and hybrid decoding.
4. Observations and CRC-Aided Hybrid Decoding
The observations and some important results are listed in the following:
1) For iterative BP decoding, the irregular LDPC code is consistently outperform the regular one, thanks to the asymptotically advantageous SNR-threshold (0.471 dB lower).
2) For hybrid decoding, there is a noticeable difference between low SNR region and high SNR region. In low SNR region, the irregular LDPC code performs well when BLER is lower to 2.75e−6. While in high SNR region, the regular LDPC code performs well when BLER is lower than 2.75e−6, thanks to the good weight profile and achievable ML performance.
Without the consideration of the outer code of Cyclic Redundancy Check (CRC), for scenarios and applications without critical demand of BLER, i.e., the BLER = 1e−2 to 1e−4 for eMBB, the irregular LDPC code is a good choice, which is the reason that 5G-NR specified the irregular 5GNR-LDPC for the data channel of eMBB [1]. However, for scenarios and applications with critical demand of BLER, i.e., the BLER = 1e−5 to 1e−7 for URLLC, the regular LDPC code seems a good choice and the near-ML decoding is a pre-requisite to ensure the near-ML performance even with hybrid decoding. In both scenarios and applications, the SNR-BLER performance can be improved at the cost of increased complexity. Therefore, careful trade-off between performance and complexity should be balanced. In the meantime, good trade-off between performance and complexity is offered by the regular LDPC code if the affordable complexity is high.
In general, the concatenation of the CRC outer code and the LDPC/Polar inner code is a common configuration for the channel coding scheme. If we consider the concatenated code as a whole, the minimum distance problem of irregular LDPC code could be easily solved, as demonstrated in the solution of CRC-aided SCL (CA-SCL) decoding for Polar code and the solution of CRC-aided adaptive belief propagation decoding for LDPC code [21]-[23]. Inspired by the idea of CRC concatenated code, the CRC-aided hybrid decoding is proposed in this paper to achieve the trade-off between performance and complexity for irregular LDPC code, including the 5GNR-LDPC. To be specific, the K0 raw information bits are firstly outer-encoded with cyclic redundancy check (CRC) code of (Kc + K0, K0), then the K = Kc + K0 total CRC-coded bits are secondly inner-encoded with LDPC code of (N, K). The rate of concatenated code is K0/N, instead of K/N.
The procedure of the CRC-aided hybrid decoding is illustrated in the following:
1) For each decoding input, perform the iterative BP decoding firstly.
2) If the BP decoding is failed (either the LDPC parity-check or the CRC is not satisfied), perform the near-ML list decoding with 1st-level list-size.
3) If the near-ML list decoding with ith-level list-size is failed, perform the near-ML list decoding with (I + 1)th level list-size.
4) The decoding will stop if the BP decoding is successful, or the near-ML list decoding with ith level list-size is successful, or the complexity budget is exhausted.
Note that, with the aid of CRC outer code, each successful BP decoding or near-ML list decoding lead to almost perfect correct reception, while the probability of non-detectable error (i.e., the decoding result is a legal codeword different from the transmitted codeword) is negligible, because the decoding result should pass both the LDPC parity-check and Cyclic Redundancy Check.
The SNR-BLER simulation results for irregular LDPC codes with iterative BP, hybrid decoding and CRC-aided hybrid decoding are shown in Figure 2. At the same time, the Gaussian-approximation finite-length bound is also depicted for the original (504, 252) LDPC code and the (504, 236) concatenated code, where Kc = 16. The error-floor problem is solved with CRC-aided hybrid decoding thanks to the improved code-weight distribution from the concatenated code. The cost is the SNR penalty due to rate loss, from 252/504 to 236/504 with Kc = 16, which is about 0.38 dB for N = 504.
![]()
Figure 2. Performance comparison of irregular (504, 252) LDPC codes and (512, 256) 5GNR-LDPC code with iterative BP decoding, hybrid decoding and CRC-aided hybrid decoding.
As a further demonstration of the proposed CRC-aided hybrid decoding, the concatenated code of (256, 240) CRC code and (512, 256) 5GNR-LDPC code with kz = 8, mz = 10, vz = 2, z = 32 for BG2 family is also simulated, evaluated and shown in Figure 2. The asymptotical SNR-threshold under BI-AWGN channel is 0.419dB for 5GNR-LDPC (512, 256) compared to the 0.648dB for irregular LDPC code (504, 252). Without CRC-aided decoding, the error-floor problem also exists for 5GNR-LDPC code, where the weight profile is provided in the following. The factor 32 in the weight profile is due to the quasi-cyclic property. However, with CRC-aided hybrid decoding, the BLER down to 1e-7 is achieved with SNR penalty of about 0.38dB due to rate from 256/512 to 240/512 for N = 512. The SNR gap to the finite-length bound of rate 240/512 is only 0.84dB, which is remarkable considering the obvious worse ML performance (indicated by the approximate Truncated Union Bound).
A(x)|5GNR-BG2(512, 256) = 32 * (2x14 + 2x16 + 2x17 + 6x18 + 3x19 + 13x20 + 24x21 + 68x22 + 100x23 + 267x24 + 453x25 + 912x26 + 1823x27 + 3353x28 + 6226x29 + 10903x30 + 17735x31 + 28238x32 + 42695x33 + 61134x34 + 82600x35 + 110573x36 + 139822x37 + 174403x38)
5. Conclusions
In this paper, the iterative BP decoding and hybrid decoding for regular and irregular LDPC code are tested. Simulation results show that the trade-off between performance and complexity should be carefully balanced. The hybrid decoding generally provides near-ML performance with the cost of increased complexity. Without CRC-aided decoding, good trade-off between performance and complexity is offered by the regular LDPC code if the affordable complexity is high. To solve the error-floor problem of irregular LDPC code, the concatenation of outer CRC code and inner LDPC code is recommended, and the CRC-aided hybrid decoding is proposed. As a result, good trade-off between performance and complexity could be achieved with the irregular LDPC code, including 5GNR-LDPC code.