Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information Communication Technologies Conference (ICTC)

A Second Minimum Approximation Method for Layered Min-Sum Decoding of QC-LDPC Codes

Zijian Qin, Yangcan Zhou, Zhongfeng Wang

Published May 17, 2023• 1 citation
Publisher

Abstract

Low-density parity-check (LDPC) codes have attracted tremendous attention for their excellent error-correction performance and inherent fitness for high-parallelism implementation. With great complexity reduction and friendly for hardware implementation, the min-sum (MS) decoding algorithm for LDPC codes gains widespread applications in practical. In the MS decoding algorithm, finding the first two minima among input variable-to-check messages is the most complex part. To further reduce the complexity of the MS decoding algorithm, an efficient single-minimum (single-min) based layered MS decoding for quasi-cyclic LDPC (QC-LDPC) codes is proposed in this paper. It is found that statistically the difference between the first minimum and second minimum increases as the decoding becomes more convergent. Accordingly, in the proposed single-min scheme, the second minimum is approximately derived based on the first minimum and an index indicating the convergence degree. Besides, some other metrics that are easily obtained are used to refine the second minimum. Simulation results show that the proposed method can significantly improve the error-correction performance and lower the average number of iterations, compared with the state-of-the-art single-min based MS decoding algorithms.

DOI
10.1109/ictc57116.2023.10154580

Related papers

Reduced-Complexity Belief Propagation Decoding for LDPC Codes

Heping Wan, Joonyoung Cho, Min Jang +1 more

Two methods are proposed to reduce the complexity of the belief propagation (BP) decoding for low-density parity-check (LDPC) codes, with the focus on the layered decoding for quasi-cyclic LDPC (QC-LDPC) codes. The two methods can be separately incorporated into the layered decoding procedures and combined seamlessly to provide the two-fold complexity reduction. In the first method, the message updates regarding a subset of variable nodes are omitted. To construct the subset, the most reliable bit-level channels, derived fromM-ary input channels, are identified. Then, we select the variable nodes with initial log-likelihood ratios (LLRs) exceeding a threshold among the ones assigned to the most reliable bit-level channels to form the subset. The threshold is designed and adjusted based on characteristics of the most reliable bit-level channels. Our numerical results demonstrate that the first method significantly reduces the complexity with negligibly impacting the error-correcting performance. In the second method, each layer of base graphs of QC-LDPC codes uses either sum-product algorithm (SPA) or min-sum algorithm (MSA) to update LLRs. A degree-based algorithm is presented to determine the layers employing either SPA or MSA. We compare with two intuitive methods: 1) applying SPA to randomly selected layers and MSA to the remaining layers, and 2) applying SPA to the core layers of 5G NR LDPC codes and MSA to the remaining layers. According to the numerical results, the degree-based algorithm maximally reduces the complexity while maintaining the same performance. To evaluate the joint method, the first method is applied on top of the second method. Further complexity reduction is achieved without degrading the performance of the second method.

IEEE Access•Jan 1, 2026•0 citations

Reduced-Complexity Offset Min-Sum Based Layered Decoding for 5G LDPC Codes

Vladimir L. Petrović, Dragomir El Mezeni

This paper presents a novel approach for the reduced-complexity Min-Sum (MS) decoding of low density parity check (LDPC) codes in the partially parallel layered decoder architecture, which contains large number of serial check node processors. Reduced complexity is obtained by using the variant of the single-minimum Offset Min-Sum (smOMS) algorithm that approximates a second minimum with the addition of the variable weight parameter to the minimum value. Although the reduced-complexity MS algorithms primarily reduce hardware resources in fully parallel implementations, the results showed that a considerable reduction can be obtained if serial check node processors are used. Additionally, the paper proposes a better subminimum estimation for irregular codes from 5G new radio (5G NR). The method uses smaller subminimum estimation weights in check nodes with higher degree and higher weights in check nodes with smaller degree, which lead to the significant improvement in the SNR performance.

Telecommunications Forum (TELFOR)•Nov 24, 2020•17 citations

Reduced-complexity offset min-sum check node unit for layered 5G LDPC decoder

Vladimir L. Petrović, Mezeni El

This paper presents a novel approach for the reduced-complexity Min-Sum (MS) decoding of low density parity check (LDPC) codes in the partially parallel layered decoder architecture, which contains a large number of serial check node processors. Reduced complexity is obtained by using the variant of the single-minimum Offset Min-Sum (smOMS) algorithm that approximates a second minimum with the addition of the variable weight parameter to the minimum value. Although the reduced-complexity MS algorithms primarily reduce hardware resources in fully parallel implementations, the results showed that a considerable reduction can be obtained if serial check node processors are used. The paper also proposes a better subminimum estimation for irregular codes from 5G new radio (5G NR). The method uses smaller subminimum estimation weights in check nodes with a higher degree and higher weights in check nodes with a smaller degree, which leads to the significant improvement in the SNR performance. Additionally, it is shown that SNR performance can be further improved by applying offset before minimum calculation, which differs from conventional Min-Sum approaches.

Telfor Journal•Jan 1, 2021•0 citations

Reduced-Complexity Min-Sum Algorithm for Decoding LDPC Codes With Low Error-Floor

F. Angarita, Javier Valls, Vicenç Almenar +1 more

This paper proposes a low-complexity min-sum algorithm for decoding low-density parity-check codes. It is an improved version of the single-minimum algorithm where the two-minimum calculation is replaced by one minimum calculation and a second minimum emulation. In the proposed one, variable correction factors that depend on the iteration number are introduced and the second minimum emulation is simplified, reducing by this way the decoder complexity. This proposal improves the performance of the single-minimum algorithm, approaching to the normalized min-sum performance in the water-fall region. Also, the error-floor region is analyzed for the code of the IEEE 802.3an standard showing that the trapping sets are decoded due to a slow down of the convergence of the algorithm. An error-floor free operation below BER=10-15is shown for this code by means of a field-programmable gate array (FPGA)-based hardware emulator. A layered decoder is implemented in a 90-nm CMOS technology achieving 12.8 Gbps with an area of 3.84 mm2.

IEEE Transactions on Circuits and Systems I Regular Papers•Feb 18, 2014•72 citations

Improved Layered Minimum Sum Decoding Algorithm Based on Overestimation

Liu Yu, Lin Bai, Yaohui Hao

Quasi-cyclic low-density parity-check (QC-LDPC) codes are linear block codes with performance close to the Shannon limit. The layered minimum sum (LMS) decoding algorithm speeds up the decoding convergence by layering the check matrix and updating the nodes according to the layers. However, the MS algorithm has the problem of over estimation and affects the decoding performance due to its simplified strategy of MS algorithm updating the message of check nodes. Therefore, this paper proposes a layered minimum sum decoding algorithm based on overestimation. By setting the correction threshold and updating the check nodes by the conditions, the decoding performance is improved. When the code length is 2048 and the bit error rate is , the proposed algorithm can improve the decoding convergence speed by about 25% and obtain a coding gain of about 0.1 dB.

•Sep 23, 2022•0 citations

A Low Complexity Decoding Algorithm Design Based on Quasi-Cyclic LDPC Codes

Cai Honghao, Yingkun Yang, Yi Qu

Entering the 5G era, the hardware design of low-density parity-check (LDPC) codes under the new standard has increasingly higher requirements on throughput. According to the geometric characteristics of the check matrices of the quasi-cyclicQC) LDCP codes under the CCSDS standard, this paper designs a layered dynamic normalized minimum sum algorithm(LDNMSA) under the pre-termination decoding based on de-layering scheme. The check matrix structure of this code is easy for hardware design and the storage resource consumption is low. The approximate replacement of the minimum sum algorithm(MSA) reduces the computational complexity of the check node update process. The determination of correction factors and inter-layer deletion thresholds through computer simulation improves the decoding performance and the speed of a single iteration, and adopt the layered scheduling scheme with optimized update order reduces the number of iterations required for decoding. Experimental results show that when the bit error rate(BER) is 10-5, the designed algorithm has a gain of approximately 0.5 dB compared to the MSA. The speed and calculation amounts to a single iteration are much lower than the log-likelihood-ratio(LLR) belief propagation(BP) algorithm and the performance is only less than 0.1dB.

International Conference on Computing, Electronics & Communications Engineering (iCCECE)•Aug 17, 2020•2 citations
Low-density parity-check (LDPC) codes have attracted tremendous attention for their excellent error-correction performance and inherent fitness for high-parallelism implementation. With great complexity reduction and friendly for hardware implementation, the min-sum (MS) decoding algorithm for LDPC codes gains widespread applications in practical. In the MS decoding algorithm, finding the first two minima among input variable-to-check messages is the most complex part. To further reduce the complexity of the MS decoding algorithm, an efficient single-minimum (single-min) based layered MS decoding for quasi-cyclic LDPC (QC-LDPC) codes is proposed in this paper. It is found that statistically the difference between the first minimum and second minimum increases as the decoding becomes more convergent. Accordingly, in the proposed single-min scheme, the second minimum is approximately derived based on the first minimum and an index indicating the convergence degree. Besides, some other metrics that are easily obtained are used to refine the second minimum. Simulation results show that the proposed method can significantly improve the error-correction performance and lower the average number of iterations, compared with the state-of-the-art single-min based MS decoding algorithms.
Two methods are proposed to reduce the complexity of the belief propagation (BP) decoding for low-density parity-check (LDPC) codes, with the focus on the layered decoding for quasi-cyclic LDPC (QC-LDPC) codes. The two methods can be separately incorporated into the layered decoding procedures and combined seamlessly to provide the two-fold complexity reduction. In the first method, the message updates regarding a subset of variable nodes are omitted. To construct the subset, the most reliable bit-level channels, derived fromM-ary input channels, are identified. Then, we select the variable nodes with initial log-likelihood ratios (LLRs) exceeding a threshold among the ones assigned to the most reliable bit-level channels to form the subset. The threshold is designed and adjusted based on characteristics of the most reliable bit-level channels. Our numerical results demonstrate that the first method significantly reduces the complexity with negligibly impacting the error-correcting performance. In the second method, each layer of base graphs of QC-LDPC codes uses either sum-product algorithm (SPA) or min-sum algorithm (MSA) to update LLRs. A degree-based algorithm is presented to determine the layers employing either SPA or MSA. We compare with two intuitive methods: 1) applying SPA to randomly selected layers and MSA to the remaining layers, and 2) applying SPA to the core layers of 5G NR LDPC codes and MSA to the remaining layers. According to the numerical results, the degree-based algorithm maximally reduces the complexity while maintaining the same performance. To evaluate the joint method, the first method is applied on top of the second method. Further complexity reduction is achieved without degrading the performance of the second method.
This paper presents a novel approach for the reduced-complexity Min-Sum (MS) decoding of low density parity check (LDPC) codes in the partially parallel layered decoder architecture, which contains large number of serial check node processors. Reduced complexity is obtained by using the variant of the single-minimum Offset Min-Sum (smOMS) algorithm that approximates a second minimum with the addition of the variable weight parameter to the minimum value. Although the reduced-complexity MS algorithms primarily reduce hardware resources in fully parallel implementations, the results showed that a considerable reduction can be obtained if serial check node processors are used. Additionally, the paper proposes a better subminimum estimation for irregular codes from 5G new radio (5G NR). The method uses smaller subminimum estimation weights in check nodes with higher degree and higher weights in check nodes with smaller degree, which lead to the significant improvement in the SNR performance.
This paper presents a novel approach for the reduced-complexity Min-Sum (MS) decoding of low density parity check (LDPC) codes in the partially parallel layered decoder architecture, which contains a large number of serial check node processors. Reduced complexity is obtained by using the variant of the single-minimum Offset Min-Sum (smOMS) algorithm that approximates a second minimum with the addition of the variable weight parameter to the minimum value. Although the reduced-complexity MS algorithms primarily reduce hardware resources in fully parallel implementations, the results showed that a considerable reduction can be obtained if serial check node processors are used. The paper also proposes a better subminimum estimation for irregular codes from 5G new radio (5G NR). The method uses smaller subminimum estimation weights in check nodes with a higher degree and higher weights in check nodes with a smaller degree, which leads to the significant improvement in the SNR performance. Additionally, it is shown that SNR performance can be further improved by applying offset before minimum calculation, which differs from conventional Min-Sum approaches.
This paper proposes a low-complexity min-sum algorithm for decoding low-density parity-check codes. It is an improved version of the single-minimum algorithm where the two-minimum calculation is replaced by one minimum calculation and a second minimum emulation. In the proposed one, variable correction factors that depend on the iteration number are introduced and the second minimum emulation is simplified, reducing by this way the decoder complexity. This proposal improves the performance of the single-minimum algorithm, approaching to the normalized min-sum performance in the water-fall region. Also, the error-floor region is analyzed for the code of the IEEE 802.3an standard showing that the trapping sets are decoded due to a slow down of the convergence of the algorithm. An error-floor free operation below BER=10-15is shown for this code by means of a field-programmable gate array (FPGA)-based hardware emulator. A layered decoder is implemented in a 90-nm CMOS technology achieving 12.8 Gbps with an area of 3.84 mm2.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are linear block codes with performance close to the Shannon limit. The layered minimum sum (LMS) decoding algorithm speeds up the decoding convergence by layering the check matrix and updating the nodes according to the layers. However, the MS algorithm has the problem of over estimation and affects the decoding performance due to its simplified strategy of MS algorithm updating the message of check nodes. Therefore, this paper proposes a layered minimum sum decoding algorithm based on overestimation. By setting the correction threshold and updating the check nodes by the conditions, the decoding performance is improved. When the code length is 2048 and the bit error rate is , the proposed algorithm can improve the decoding convergence speed by about 25% and obtain a coding gain of about 0.1 dB.
Entering the 5G era, the hardware design of low-density parity-check (LDPC) codes under the new standard has increasingly higher requirements on throughput. According to the geometric characteristics of the check matrices of the quasi-cyclicQC) LDCP codes under the CCSDS standard, this paper designs a layered dynamic normalized minimum sum algorithm(LDNMSA) under the pre-termination decoding based on de-layering scheme. The check matrix structure of this code is easy for hardware design and the storage resource consumption is low. The approximate replacement of the minimum sum algorithm(MSA) reduces the computational complexity of the check node update process. The determination of correction factors and inter-layer deletion thresholds through computer simulation improves the decoding performance and the speed of a single iteration, and adopt the layered scheduling scheme with optimized update order reduces the number of iterations required for decoding. Experimental results show that when the bit error rate(BER) is 10-5, the designed algorithm has a gain of approximately 0.5 dB compared to the MSA. The speed and calculation amounts to a single iteration are much lower than the log-likelihood-ratio(LLR) belief propagation(BP) algorithm and the performance is only less than 0.1dB.