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

한국통신학회논문지

Combined Horizontal-Vertical Serial BP Decoding of GLDPC Codes with Binary Cyclic Codes

Kyuhyuk Chung

Published Oct 31, 2014• 0 citations
Publisher

Abstract

It is well known that serial belief propagation (BP) decoding for low-density parity-check (LDPC) codes achieves faster convergence without any increase of decoding complexity per iteration and bit error rate (BER) performance loss than standard parallel BP (PBP) decoding. Serial BP (SBP) decoding, such as horizontal SBP (H-SBP) decoding or vertical SBP (V-SBP) decoding, updates check nodes or variable nodes faster than standard PBP decoding within a single iteration. In this paper, we propose combined horizontal-vertical SBP (CHV-SBP) decoding. By the same reasoning, CHV-SBP decoding updates check nodes or variable nodes faster than SBP decoding within a serialized step in an iteration. CHV-SBP decoding achieves faster convergence than H-SBP or V-SBP decoding. We compare these decoding schemes in details. We also show in simulations that the convergence rate, in iterations, for CHV-SBP decoding is about $\frac{1}{6}$ of that for standard PBP decoding, while the convergence rate for SBP decoding is about $\frac{1}{2}$ of that for standard PBP decoding. In simulations, we use recently proposed generalized LDPC (GLDPC) codes with binary cyclic codes (BCC).

DOI
10.7840/kics.2014.39a.10.585

Related papers

An Overlapped Shuffled-BP LDPC Decoding Algorithm

Ya’nan Fan, Yao Xiujuan

Shuffled-BP (SBP) decoding algorithm is a variable-node-based serial decoding algorithm, which converges faster than the original Belief-Propagation (BP) decoding algorithm. However, due to the semi-parallel processing, there is a decrease in terms of convergence speed and error performance. An Overlapped Shuffled-BP(OSBP) decoding algorithm is proposed to enhance further the performance of the Shuffled-BP algorithm. In this algorithm, more than one sub-decoders are used to execute simultaneously, every sub-decoder has different updating order from each other. Regarding each variable node, the most reliable messages are kept and used for the next iteration, thus a faster convergence can be provided. Both theoretical analysis and simulation results show that, compared with SBP algorithm, OSBP algorithm possesses a better error performance as well as a higher convergence speed and introduces no extra storage requirement. Moreover, the proposed algorithm is effective for both regular and irregular LDPC codes.

•Jan 1, 2016•1 citation

Generalized constructions, decoding and implementation of LDPC codes

Yige Wang

Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.

•Jan 1, 2008•3 citations

New group shuffled BP decoding algorithms for LDPC codes

Chi-Yuan Chang, Yu‐Liang Chen, Chang‐Ming Lee +1 more

Implementing a belief propagation (BP) based LDPC decoder requires high degrees of parallelism using many component soft-in soft-output (SISO) decoding units to perform message passing from variable nodes to check nodes or vice versa. An obvious complexity-reduction solution is to serialize the decoding process, i.e., dividing a decoding iteration into several serial sub-iterations in which a sub-iteration performs only part of the complete parallel message-passing operation. The group horizontal shuffled BP (GHSBP) and vertical shuffled BP (GVSBP) algorithms respectively partition the check and variable nodes of the code graph into groups to perform group-by-group message-passing decoding. This paper proposes new techniques to improve three key elements of a GHSBP decoding algorithm, namely, the grouping method, the decoding schedule and the log-likelihood updating formulae. The (check nodes) grouping method and decoding schedule optimize certain design criterion. The new normalized min-sum updating formula with a self-adjustable correction (scaling) factor offers better nonlinear approximation. Numerical performance of new GHSBP algorithms that include part or all three new techniques indicate that the combination of the proposed grouping and decoding schedule yields a faster convergence rate and our modified min-sum algorithm gives performance superior to that of the conventional min-sum and normalized min-sum algorithm and is very close to that of the sum-product algorithm.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•4 citations

Serially concatenated belief propagation decoder for low‐density parity‐check codes

Hua Ren Zhou, Erbao Li, Jing Lei

A new decoding strategy of belief propagation (BP) for low‐density parity‐check codes is presented by serially concatenating the traditional simultaneous decoding (also known as flooding) and the informed dynamic decoding (IDD) (e.g. node‐wise residual belief propagation (NW RBP) or informed variable‐to‐check (IVC) RBP). The frame error rates (FER) and bit error rates (BER) of the concatenated BP decoder outperform that of the non‐concatenated single decoder. In addition, as the signal‐to‐noise ratio (SNR) increases, the average number of decoding iterations required for the concatenated BP decoder decreases, and tends to merge with that of the first sub‐decoder in the high SNR region. Moreover, since the IDD strategies concerned in this paper require extra effort for the residual computation, and the sequential updating of IDD is much more time consuming than the simultaneous updating of flooding. Therefore, compared with using a single IDD, serially concatenating flooding and IDD reduces both the approximate decoding complexity and the decoding latency because the concatenated decoder is still dominated by the sub‐decoder flooding.

IET Communications•Jul 17, 2017•1 citation

Fast decoding of low density parity check codes

Nassib Laouini, Larbi Ben Hadj Slama, Ammar Bouallègue

The Layered Belief Propagation L-BP algorithm is is a modified Belief Propagation BP algorithm, where the check nodes are divided in subgroups called layers and each iteration is broken into multiple sub-iterations. In this paper, we consider layered belief propagation decoding and propose an efficient variable node layering for decoding LDPC codes that performs well. We compare the performance of the first introduced LDPC decoding algorithm BP and Layered BP using check node layering with Layered BP using variable node layering in terms of bit error rate (BER). We show that the convergence for decoding LDPC codes is increasing by using a simple and efficient layering strategy.

International Symposium on High-capacity Optical Networks and Enabling Technologies•Dec 1, 2012•5 citations

Improved Decoding of Binary and Non-Binary LDPC Codes by Probabilistic Shuffled Belief Propagation

Moritz Beermann, Laurent Schmalen, Peter Vary

Low-density parity-check (LDPC) codes have proved to be very powerful channel coding schemes with a broad range of applications. However, as maximum-likelihood decoding is utterly complex, suboptimal decoders have to be employed. One of the most popular decoding algorithms of LDPC codes is belief propagation (BP) decoding. In this paper, we present a novel scheduling for belief propagation decoding of LDPC codes. The new approach combines probabilistic scheduling with the known shuffled and check-shuffled serial scheduling algorithms. The resulting probabilistic shuffled and probabilistic check-shuffled decoders show a superior performance in terms of residual bit error rate. The drawback is that the convergence speed is slightly decreased. However, the convergence is still faster than for the standard and probabilistic flooding algorithms. Furthermore, we have adapted the probabilistic flooding schedule and the proposed probabilistic shuffled schedule to the non-binary case. We show that the aforementioned effects on the binary decoder can similarly be observed when applying the different schedules to the decoding of LDPC codes over higher order Galois fields.

International Conference on Communications•Jun 1, 2011•4 citations
It is well known that serial belief propagation (BP) decoding for low-density parity-check (LDPC) codes achieves faster convergence without any increase of decoding complexity per iteration and bit error rate (BER) performance loss than standard parallel BP (PBP) decoding. Serial BP (SBP) decoding, such as horizontal SBP (H-SBP) decoding or vertical SBP (V-SBP) decoding, updates check nodes or variable nodes faster than standard PBP decoding within a single iteration. In this paper, we propose combined horizontal-vertical SBP (CHV-SBP) decoding. By the same reasoning, CHV-SBP decoding updates check nodes or variable nodes faster than SBP decoding within a serialized step in an iteration. CHV-SBP decoding achieves faster convergence than H-SBP or V-SBP decoding. We compare these decoding schemes in details. We also show in simulations that the convergence rate, in iterations, for CHV-SBP decoding is about 16\frac{1}{6}61​ of that for standard PBP decoding, while the convergence rate for SBP decoding is about 12\frac{1}{2}21​ of that for standard PBP decoding. In simulations, we use recently proposed generalized LDPC (GLDPC) codes with binary cyclic codes (BCC).
Shuffled-BP (SBP) decoding algorithm is a variable-node-based serial decoding algorithm, which converges faster than the original Belief-Propagation (BP) decoding algorithm. However, due to the semi-parallel processing, there is a decrease in terms of convergence speed and error performance. An Overlapped Shuffled-BP(OSBP) decoding algorithm is proposed to enhance further the performance of the Shuffled-BP algorithm. In this algorithm, more than one sub-decoders are used to execute simultaneously, every sub-decoder has different updating order from each other. Regarding each variable node, the most reliable messages are kept and used for the next iteration, thus a faster convergence can be provided. Both theoretical analysis and simulation results show that, compared with SBP algorithm, OSBP algorithm possesses a better error performance as well as a higher convergence speed and introduces no extra storage requirement. Moreover, the proposed algorithm is effective for both regular and irregular LDPC codes.
Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.
Implementing a belief propagation (BP) based LDPC decoder requires high degrees of parallelism using many component soft-in soft-output (SISO) decoding units to perform message passing from variable nodes to check nodes or vice versa. An obvious complexity-reduction solution is to serialize the decoding process, i.e., dividing a decoding iteration into several serial sub-iterations in which a sub-iteration performs only part of the complete parallel message-passing operation. The group horizontal shuffled BP (GHSBP) and vertical shuffled BP (GVSBP) algorithms respectively partition the check and variable nodes of the code graph into groups to perform group-by-group message-passing decoding. This paper proposes new techniques to improve three key elements of a GHSBP decoding algorithm, namely, the grouping method, the decoding schedule and the log-likelihood updating formulae. The (check nodes) grouping method and decoding schedule optimize certain design criterion. The new normalized min-sum updating formula with a self-adjustable correction (scaling) factor offers better nonlinear approximation. Numerical performance of new GHSBP algorithms that include part or all three new techniques indicate that the combination of the proposed grouping and decoding schedule yields a faster convergence rate and our modified min-sum algorithm gives performance superior to that of the conventional min-sum and normalized min-sum algorithm and is very close to that of the sum-product algorithm.
A new decoding strategy of belief propagation (BP) for low‐density parity‐check codes is presented by serially concatenating the traditional simultaneous decoding (also known as flooding) and the informed dynamic decoding (IDD) (e.g. node‐wise residual belief propagation (NW RBP) or informed variable‐to‐check (IVC) RBP). The frame error rates (FER) and bit error rates (BER) of the concatenated BP decoder outperform that of the non‐concatenated single decoder. In addition, as the signal‐to‐noise ratio (SNR) increases, the average number of decoding iterations required for the concatenated BP decoder decreases, and tends to merge with that of the first sub‐decoder in the high SNR region. Moreover, since the IDD strategies concerned in this paper require extra effort for the residual computation, and the sequential updating of IDD is much more time consuming than the simultaneous updating of flooding. Therefore, compared with using a single IDD, serially concatenating flooding and IDD reduces both the approximate decoding complexity and the decoding latency because the concatenated decoder is still dominated by the sub‐decoder flooding.
The Layered Belief Propagation L-BP algorithm is is a modified Belief Propagation BP algorithm, where the check nodes are divided in subgroups called layers and each iteration is broken into multiple sub-iterations. In this paper, we consider layered belief propagation decoding and propose an efficient variable node layering for decoding LDPC codes that performs well. We compare the performance of the first introduced LDPC decoding algorithm BP and Layered BP using check node layering with Layered BP using variable node layering in terms of bit error rate (BER). We show that the convergence for decoding LDPC codes is increasing by using a simple and efficient layering strategy.
Low-density parity-check (LDPC) codes have proved to be very powerful channel coding schemes with a broad range of applications. However, as maximum-likelihood decoding is utterly complex, suboptimal decoders have to be employed. One of the most popular decoding algorithms of LDPC codes is belief propagation (BP) decoding. In this paper, we present a novel scheduling for belief propagation decoding of LDPC codes. The new approach combines probabilistic scheduling with the known shuffled and check-shuffled serial scheduling algorithms. The resulting probabilistic shuffled and probabilistic check-shuffled decoders show a superior performance in terms of residual bit error rate. The drawback is that the convergence speed is slightly decreased. However, the convergence is still faster than for the standard and probabilistic flooding algorithms. Furthermore, we have adapted the probabilistic flooding schedule and the proposed probabilistic shuffled schedule to the non-binary case. We show that the aforementioned effects on the binary decoder can similarly be observed when applying the different schedules to the decoding of LDPC codes over higher order Galois fields.