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 and Electronic Engineering

An approach to improve parallelism inside layer in LDPC decoding

Yi Hou

Published Jan 1, 2012• 0 citations
OpenAlex

Abstract

It is hard to increase parallelism inside layer when converting a generic Quasi Cyclic-Low Density Parity Check(QC-LDPC) code to a SHIFT-structured LDPC code.The paper proposes a non-uniform layered partitioning scheme,which can efficiently increase the parallelism inside layer while maximum row(column) weight of each layer is not more than one.Corresponding shuffle network and pipeline architecture are also designed.In contrast with uniform layered partitioning scheme,the proposed scheme can enhance the parallelism inside layer by 41.3% and 32.2% respectively for two application codes,Consultative Committee for Space Data Systems(CCSDS)(5 632,4 096) code and China Digital Television Terrestrial Multimedia Broadcasting(DTMB)(7 493,6 096) code.Synthesized results of(5 632,4 096) code show that the non-uniform scheme can improve the parallelism by 41.3% comparing to uniform scheme with the same resource utilization while using the Two Phase Message Passing(TPMP) algorithm;and the maximum throughput of the decoding system can be improved by 28.2% while using Shuffled Belief Propagation Decoding(SBP) algorithm.

Related papers

A Modified Shuffling Method to Split the Critical Path Delay in Layered Decoding of QC-LDPC Codes

Alireza Hasani, Łukasz Łopaciński, Steffen Büchner +2 more

Layered (or Turbo) decoding of Low-Density Parity-Check (LDPC) codes is considered as a decoding schedule that facilitates partially parallel architectures for performing iterative algorithms based on belief propagation. It has, on one hand, reduced implementation complexity and memory overhead compared to fully parallel architectures and, on the other hand, higher convergence speed compared to both serial and parallel architectures. In this paper, we introduce a general form of shuffling of the parity-check matrix of quasi-cyclic LDPC (QC-LDPC) codes which can split the critical path delay in layered decoding and therefore improve throughput by allowing higher clock rates. We also reveal a valuable property of Latin squares QC-LDPC codes which makes them a good candidate for the proposed shuffling method. As a result of that property, no special caution of choosing offset values in the proposed generalized shuffling method is required.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2019•5 citations

A Modified Shuffling Method to Reduce Decoding Complexity of QC-LDPC Codes

Alireza Hasani, Łukasz Łopaciński, Rolf Kraemer

Abstract Layered decoding (LD) of Low-Density Parity-Check (LDPC) codes is a decoding schedule that facilitates partially parallel architectures for performing Belief Propagation (BP)-based iterative algorithms. It has reduced implementation complexity and memory overhead compared to fully parallel architectures and higher convergence speed compared to both serial and parallel architectures. In this paper, we introduce a modified form of shuffling of the Parity-Check Matrices (PCMs) of Quasi-Cyclic LDPC (QC-LDPC) codes, which is basically an interleaving operation of the rows of the PCM. The modified shuffling method just like the conventional shuffling method results in a PCM in which each layer can be produced by the circulation of its above layer one symbol to the right. However, it additionally guarantees the weights of the columns in each layer to be either zero or one. Then, we show that due to these two properties, the number of occupied Look-Up Tables (LUTs) on a Field Programmable Gate Array (FPGA) is reduced by about 93% and consumed on-chip power by nearly 80%. Nevertheless, shuffling doesn’t degrade Bit Error Rate (BER) performance compared with the non-shuffled case. Additionally, decoding throughput is not sacrificed for low SNR values and its degradation is negligible until the BER of 1e-6.

•Sep 8, 2020•1 citation

Extended layered decoding of LDPC codes

Zhiqiang Cui, Zhongfeng Wang

In this paper, we propose an extended layered decoding approach for low density parity check (LDPC) codes. Compared to conventional layered decoding algorithms, the proposed approach has no constraint in the column weight of each layer. Hence, it enables more flexibility in high-throughput LDPC decoder design with layered decoding. Simulations on structured and random LDPC codes show that the proposed decoding method achieves significantly faster convergence and slightly better error correction performance than the conventional two phase massage passing sum-product algorithm. We also propose an efficient highly parallel decoder architecture for generic quasi-cyclic LDPC codes to facilitate the practical application of the proposed decoding scheme.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 4, 2008•5 citations

Parity-Check Matrix Partitioning for Efficient Layered Decoding of QC-LDPC Codes

Teng Lu, Xuan He, Peng Kang +2 more

In this paper, we consider how to partition the parity-check matrices (PCMs) to reduce the hardware complexity and increase decoding throughput for the row layered decoding of quasi-cyclic low-density parity-check (QC-LDPC) codes. First, we formulate the PCM partitioning as an optimization problem, which targets to minimize the maximum column weight of each layer while maintaining a block cyclic shift property among different layers. As a result, we derive all the feasible solutions for the problem and propose a tight lower bound ωLBon the minimum possible maximum column weight to evaluate a solution. Second, we define a metric called layer distance to measure the data dependency between consecutive layers and further illustrate how to identify the solutions with desired layer distance from those achieving the minimum value of ωLB= 1, which is preferred to reduce computation delay. Next, we demonstrate that up-to-now, finding an optimal solution for the optimization problem with polynomial time complexity is unachievable. Therefore, both enumerative and greedy partition algorithms are proposed instead. After that, we modify the quasi-cyclic progressive edge-growth (QC-PEG) algorithm to directly construct PCMs that have a straightforward partition scheme to achieve ωLBor the desired layer distance. Simulation results showed that the constructed codes have better error correction performance and achieve less average number of iterations than the underlying 5G LDPC codes.

arXiv:2208.13022•IEEE Transactions on Communications•Mar 24, 2023•5 citations

Reduced-complexity decoding implementation of QC-LDPC codes with modified shuffling

Alireza Hasani, Łukasz Łopaciński, Rolf Kraemer

Abstract Layered decoding (LD) facilitates a partially parallel architecture for performing belief propagation (BP) algorithm for decoding low-density parity-check (LDPC) codes. Such a schedule for LDPC codes has, in general, reduced implementation complexity compared to a fully parallel architecture and higher convergence rate compared to both serial and parallel architectures, regardless of the codeword length or code-rate. In this paper, we introduce a modified shuffling method which shuffles the rows of the parity-check matrix (PCM) of a quasi-cyclic LDPC (QC-LDPC) code, yielding a PCM in which each layer can be produced by the circulation of its above layer one symbol to the right. The proposed shuffling scheme additionally guarantees the columns of a layer of the shuffled PCM to be either zero weight or single weight. This condition has a key role in further decreasing LD complexity. We show that due to these two properties, the number of occupied look-up tables (LUTs) on a field programmable gate array (FPGA) reduces by about 93% and consumed on-chip power by nearly 80%, while the bit error rate (BER) performance is maintained. The only drawback of the shuffling is the degradation of decoding throughput, which is negligible for low values of $$E_b/N_0$$ Eb/N0 until the BER of 1e−6.

EURASIP Journal on Wireless Communications and Networking•Oct 9, 2021•7 citations

High throughput layered decoding of LDPC codes

Mohamed Ismail, Justin P. Coon, Imran Ahmed +2 more

Layered decoding of Low Density Parity Check (LDPC) codes has been shown to give faster convergence and use less storage than the conventional Two Phase Message Passing (TPMP) algorithm in decoding such codes. To achieve higher throughput, multiple rows of the parity check matrix may be decoded in parallel, as in the Parallel-Turbo Decoding Message Passing (P-TDMP) algorithm. However, contention for globally shared memory permits only a subset of rows to be decoded in parallel thus limiting overall throughput. This paper uses a near optimal scheduling algorithm, based on graph colouring, to overcome memory contention, allowing processing of multiple rows without code modification, resulting in significant throughput gains over the standard P-TDMP algorithm. For the LDPC codes studied, throughput gains compared to the P-TDMP algorithm, of between ten and fifteen are shown to be possible.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2009•0 citations
It is hard to increase parallelism inside layer when converting a generic Quasi Cyclic-Low Density Parity Check(QC-LDPC) code to a SHIFT-structured LDPC code.The paper proposes a non-uniform layered partitioning scheme,which can efficiently increase the parallelism inside layer while maximum row(column) weight of each layer is not more than one.Corresponding shuffle network and pipeline architecture are also designed.In contrast with uniform layered partitioning scheme,the proposed scheme can enhance the parallelism inside layer by 41.3% and 32.2% respectively for two application codes,Consultative Committee for Space Data Systems(CCSDS)(5 632,4 096) code and China Digital Television Terrestrial Multimedia Broadcasting(DTMB)(7 493,6 096) code.Synthesized results of(5 632,4 096) code show that the non-uniform scheme can improve the parallelism by 41.3% comparing to uniform scheme with the same resource utilization while using the Two Phase Message Passing(TPMP) algorithm;and the maximum throughput of the decoding system can be improved by 28.2% while using Shuffled Belief Propagation Decoding(SBP) algorithm.
Layered (or Turbo) decoding of Low-Density Parity-Check (LDPC) codes is considered as a decoding schedule that facilitates partially parallel architectures for performing iterative algorithms based on belief propagation. It has, on one hand, reduced implementation complexity and memory overhead compared to fully parallel architectures and, on the other hand, higher convergence speed compared to both serial and parallel architectures. In this paper, we introduce a general form of shuffling of the parity-check matrix of quasi-cyclic LDPC (QC-LDPC) codes which can split the critical path delay in layered decoding and therefore improve throughput by allowing higher clock rates. We also reveal a valuable property of Latin squares QC-LDPC codes which makes them a good candidate for the proposed shuffling method. As a result of that property, no special caution of choosing offset values in the proposed generalized shuffling method is required.
Abstract Layered decoding (LD) of Low-Density Parity-Check (LDPC) codes is a decoding schedule that facilitates partially parallel architectures for performing Belief Propagation (BP)-based iterative algorithms. It has reduced implementation complexity and memory overhead compared to fully parallel architectures and higher convergence speed compared to both serial and parallel architectures. In this paper, we introduce a modified form of shuffling of the Parity-Check Matrices (PCMs) of Quasi-Cyclic LDPC (QC-LDPC) codes, which is basically an interleaving operation of the rows of the PCM. The modified shuffling method just like the conventional shuffling method results in a PCM in which each layer can be produced by the circulation of its above layer one symbol to the right. However, it additionally guarantees the weights of the columns in each layer to be either zero or one. Then, we show that due to these two properties, the number of occupied Look-Up Tables (LUTs) on a Field Programmable Gate Array (FPGA) is reduced by about 93% and consumed on-chip power by nearly 80%. Nevertheless, shuffling doesn’t degrade Bit Error Rate (BER) performance compared with the non-shuffled case. Additionally, decoding throughput is not sacrificed for low SNR values and its degradation is negligible until the BER of 1e-6.
In this paper, we propose an extended layered decoding approach for low density parity check (LDPC) codes. Compared to conventional layered decoding algorithms, the proposed approach has no constraint in the column weight of each layer. Hence, it enables more flexibility in high-throughput LDPC decoder design with layered decoding. Simulations on structured and random LDPC codes show that the proposed decoding method achieves significantly faster convergence and slightly better error correction performance than the conventional two phase massage passing sum-product algorithm. We also propose an efficient highly parallel decoder architecture for generic quasi-cyclic LDPC codes to facilitate the practical application of the proposed decoding scheme.
In this paper, we consider how to partition the parity-check matrices (PCMs) to reduce the hardware complexity and increase decoding throughput for the row layered decoding of quasi-cyclic low-density parity-check (QC-LDPC) codes. First, we formulate the PCM partitioning as an optimization problem, which targets to minimize the maximum column weight of each layer while maintaining a block cyclic shift property among different layers. As a result, we derive all the feasible solutions for the problem and propose a tight lower bound ωLBon the minimum possible maximum column weight to evaluate a solution. Second, we define a metric called layer distance to measure the data dependency between consecutive layers and further illustrate how to identify the solutions with desired layer distance from those achieving the minimum value of ωLB= 1, which is preferred to reduce computation delay. Next, we demonstrate that up-to-now, finding an optimal solution for the optimization problem with polynomial time complexity is unachievable. Therefore, both enumerative and greedy partition algorithms are proposed instead. After that, we modify the quasi-cyclic progressive edge-growth (QC-PEG) algorithm to directly construct PCMs that have a straightforward partition scheme to achieve ωLBor the desired layer distance. Simulation results showed that the constructed codes have better error correction performance and achieve less average number of iterations than the underlying 5G LDPC codes.
Abstract Layered decoding (LD) facilitates a partially parallel architecture for performing belief propagation (BP) algorithm for decoding low-density parity-check (LDPC) codes. Such a schedule for LDPC codes has, in general, reduced implementation complexity compared to a fully parallel architecture and higher convergence rate compared to both serial and parallel architectures, regardless of the codeword length or code-rate. In this paper, we introduce a modified shuffling method which shuffles the rows of the parity-check matrix (PCM) of a quasi-cyclic LDPC (QC-LDPC) code, yielding a PCM in which each layer can be produced by the circulation of its above layer one symbol to the right. The proposed shuffling scheme additionally guarantees the columns of a layer of the shuffled PCM to be either zero weight or single weight. This condition has a key role in further decreasing LD complexity. We show that due to these two properties, the number of occupied look-up tables (LUTs) on a field programmable gate array (FPGA) reduces by about 93% and consumed on-chip power by nearly 80%, while the bit error rate (BER) performance is maintained. The only drawback of the shuffling is the degradation of decoding throughput, which is negligible for low values of Eb/N0E_b/N_0Eb​/N0​ Eb/N0 until the BER of 1e−6.
Layered decoding of Low Density Parity Check (LDPC) codes has been shown to give faster convergence and use less storage than the conventional Two Phase Message Passing (TPMP) algorithm in decoding such codes. To achieve higher throughput, multiple rows of the parity check matrix may be decoded in parallel, as in the Parallel-Turbo Decoding Message Passing (P-TDMP) algorithm. However, contention for globally shared memory permits only a subset of rows to be decoded in parallel thus limiting overall throughput. This paper uses a near optimal scheduling algorithm, based on graph colouring, to overcome memory contention, allowing processing of multiple rows without code modification, resulting in significant throughput gains over the standard P-TDMP algorithm. For the LDPC codes studied, throughput gains compared to the P-TDMP algorithm, of between ten and fifteen are shown to be possible.