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

Globecom

Optimal overlapped message passing decoding for quasi-cyclic low-density parity-check codes

Yongmei Dai, Zhiyuan Yan

Published Jan 1, 2005• 12 citations
Publisher

Abstract

In this paper, we first present a general scheduling model for the overlapped message passing (OMP) decoding of LDPC codes, and show that maximizing the throughput amounts to minimizing the intra- and inter-iteration waiting times. Then we focus on maximizing the throughput for OMP decoders of quasi-cyclic (QC) LDPC codes using a partly parallel hardware structure, which can be modelled as a data dependency and hardware constrained optimization problem. Finally, we propose a scheduling scheme, which gives the optimal solution to the optimization problem under certain conditions. In comparison to previously proposed scheduling schemes, our new scheduling scheme leads to both higher hardware utilization efficiency (HUE) and greater throughput gain.

DOI
10.1109/glocom.2005.1578092

Related papers

Optimal Overlapped Message Passing Decoding of Quasi-Cyclic LDPC Codes

Yongmei Dai, Zhiyuan Yan, Ning Chen

Efficient hardware implementation of low-density parity-check (LDPC) codes is of great interest since LDPC codes are being considered for a wide range of applications. Recently, overlapped message passing (OMP) decoding has been proposed to improve the throughput and hardware utilization efficiency (HUE) of decoder architectures for LDPC codes. In this paper, we first study the scheduling for the OMP decoding of LDPC codes, and show that maximizing the throughput gain amounts to minimizing the intra- and inter-iteration waiting times. We then focus on the OMP decoding of quasi-cyclic (QC) LDPC codes. We propose a partly parallel OMP decoder architecture and implement it using FPGA. For any QC LDPC code, our OMP decoder achieves the maximum throughput gain and HUE due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Apr 16, 2008•40 citations

Coset-based quasi-cyclic LDPC codes for optimal overlapped message passing decoding

Yongmei Dai, Zhiyuan Yan

Due to the regular structures of quasi-cyclic (QC) low-density parity-check (LDPC) codes, the message passing decoding of these codes not only has efficient hardware implementation, but also can be overlapped to improve throughput and hardware utilization efficiency (HUE). In previous work, we proposed a scheduling scheme for the overlapped message passing (OMP) decoding of the SFT codes. In this paper, we first show that our scheduling scheme produces the minimum intra-iteration waiting time for QC LDPC codes. Then we propose a coset-based construction of QC LDPC codes, and study the girth and minimum distance properties of our new codes. Given the same parameters, the ensemble of the SFT codes is a subset of the ensemble of our coset-based QC LDPC codes. Our coset-based QC LDPC codes allow the OMP decoding to achieve greater throughput gain and higher HUE while maintaining the same theoretical performances as the SFT codes.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Jan 25, 2006•2 citations

Efficient Highly-Parallel Decoder Architecture for Quasi-Cyclic Low-Density Parity-Check Codes

Daesun Oh, Keshab K. Parhi

In this paper, the authors propose an efficient highly-parallel decoder architecture using partially overlapped decoding scheme for quasi-cyclic (QC) low-density parity-check (LDPC) codes, which leads to reduction in hardware complexity and power consumption. Generally, due to the regularly structured parity-check matrix H of QC LDPC codes, the message updating computations in the check node unit (CNU) and the variable node unit (VNU) can be efficiently overlapped, which increases the decoding throughput by maximizing the hardware utilization efficiency (HUE). However, the partially overlapped decoding scheme cannot be used to design a highly-parallel decoding architecture for high-throughput applications. For (3, 5)-regular QC LDPC codes, our proposed method could reduce the hardware complexity by approximately 33% for the CNU and 20% for the VNU in the highly-parallel decoder architecture without any performance degradation. In addition, the power consumption can be minimized by reducing the total number of memory accesses for updated messages.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2007•14 citations

A High Throughput H-QC LDPC Decoder

Yi-Hsing Chien, Mong‐Kai Ku

In this paper, design of a high throughput low-density parity-check (LDPC) decoder using overlapped message passing scheduling algorithm is presented. Regular hierarchical quasi-cyclic (H-QC) LDPC code is used in this design to provide good coding performance at long code length. The two-level regular H-QC LDPC code matrix structure is exploited to parallelize the row and column decoding operations. Our scheduling algorithm re-arranges these operations across iteration boundaries to avoid memory access conflicts. The memory requirement is reduced by half compared to pipelined decoders without scheduling. A (12288, 6144) LDPC decoder implemented in FPGA achieves 298 Mbps throughput performance.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2007•12 citations

High speed LDPC decoder design based on general overlapped message-passing architecture

Baihong Lin, Qi Lecky Li, Yukui Pei +2 more

The design of high speed decoders with traditional partly parallel architecture for non-quasi-cycle (NQC) LDPC codes is a challenging problem due to its high memory-block consumption and the low hardware utilization efficiency. In this paper, a general overlapped message passing (GOMP) decoding algorithm is proposed to improve the hardware utilization efficiency (HUE), which overcomes the limitation of overlapped message passing (OMP) decoders proposed before. On the basis of the given codes, this algorithm nearly doubles the throughput without sacrificing double memory or causing loss in performance compared to BP algorithm. Furthermore, we present a technique called cycle bus to reduce the number of block RAMs in the multi-core decoder. Moreover, an example of a rate-2/3, length-15360 irregular LDPC code with 8.43 dB coding gain for BPSK in AWGN channel is given, whose decoders features nearly double throughput, 22.22% increase in memory 8.35% reduction in logic registers cost and more reasonable distribution in block RAMs cost.

International Conference on Ubiquitous and Future Networks•Jul 1, 2014•4 citations

Design and efficient hardware implementation schemes for non-Quasi-Cyclic LDPC codes

Baihong Lin, Yukui Pei, Liuguo Yin +1 more

The design of a high-speed decoder using traditional partly parallel architecture for Non-Quasi-Cyclic (NQC) Low-Density Parity-Check (LDPC) codes is a challenging problem due to its high memory-block cost and low hardware utilization efficiency. In this paper, we present efficient hardware implementation schemes for NQCLDPC codes. First, we propose an implementation-oriented construction scheme for NQC-LDPC codes to avoid memory-access conflict in the partly parallel decoder. Then, we propose a Modified Overlapped Message-Passing (MOMP) algorithm for the hardware implementation of NQC-LDPC codes. This algorithm doubles the hardware utilization efficiency and supports a higher degree of parallelism than that used in the Overlapped Message Passing (OMP) technique proposed in previous works. We also present single-core and multi-core decoder architectures in the proposed MOMP algorithm to reduce memory cost and improve circuit efficiency. Moreover, we introduce a technique called the cycle bus to further reduce the number of block RAMs in multi-core decoders. Using numerical examples, we show that, for a rate-2/3, length-15360 NQC-LDPC code with 8.43-dB coding gain for Binary PhaseShift Keying (BPSK) in an Additive White Gaussian Noise (AWGN) channel, the decoder with the proposed scheme achieves a 23.8%-52.6% reduction in logic utilization per Mbps and a 29.0%-90.0% reduction in message-memory bits per Mbps.

Tsinghua Science & Technology•Jan 26, 2017•5 citations
In this paper, we first present a general scheduling model for the overlapped message passing (OMP) decoding of LDPC codes, and show that maximizing the throughput amounts to minimizing the intra- and inter-iteration waiting times. Then we focus on maximizing the throughput for OMP decoders of quasi-cyclic (QC) LDPC codes using a partly parallel hardware structure, which can be modelled as a data dependency and hardware constrained optimization problem. Finally, we propose a scheduling scheme, which gives the optimal solution to the optimization problem under certain conditions. In comparison to previously proposed scheduling schemes, our new scheduling scheme leads to both higher hardware utilization efficiency (HUE) and greater throughput gain.
Efficient hardware implementation of low-density parity-check (LDPC) codes is of great interest since LDPC codes are being considered for a wide range of applications. Recently, overlapped message passing (OMP) decoding has been proposed to improve the throughput and hardware utilization efficiency (HUE) of decoder architectures for LDPC codes. In this paper, we first study the scheduling for the OMP decoding of LDPC codes, and show that maximizing the throughput gain amounts to minimizing the intra- and inter-iteration waiting times. We then focus on the OMP decoding of quasi-cyclic (QC) LDPC codes. We propose a partly parallel OMP decoder architecture and implement it using FPGA. For any QC LDPC code, our OMP decoder achieves the maximum throughput gain and HUE due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE.
Due to the regular structures of quasi-cyclic (QC) low-density parity-check (LDPC) codes, the message passing decoding of these codes not only has efficient hardware implementation, but also can be overlapped to improve throughput and hardware utilization efficiency (HUE). In previous work, we proposed a scheduling scheme for the overlapped message passing (OMP) decoding of the SFT codes. In this paper, we first show that our scheduling scheme produces the minimum intra-iteration waiting time for QC LDPC codes. Then we propose a coset-based construction of QC LDPC codes, and study the girth and minimum distance properties of our new codes. Given the same parameters, the ensemble of the SFT codes is a subset of the ensemble of our coset-based QC LDPC codes. Our coset-based QC LDPC codes allow the OMP decoding to achieve greater throughput gain and higher HUE while maintaining the same theoretical performances as the SFT codes.
In this paper, the authors propose an efficient highly-parallel decoder architecture using partially overlapped decoding scheme for quasi-cyclic (QC) low-density parity-check (LDPC) codes, which leads to reduction in hardware complexity and power consumption. Generally, due to the regularly structured parity-check matrix H of QC LDPC codes, the message updating computations in the check node unit (CNU) and the variable node unit (VNU) can be efficiently overlapped, which increases the decoding throughput by maximizing the hardware utilization efficiency (HUE). However, the partially overlapped decoding scheme cannot be used to design a highly-parallel decoding architecture for high-throughput applications. For (3, 5)-regular QC LDPC codes, our proposed method could reduce the hardware complexity by approximately 33% for the CNU and 20% for the VNU in the highly-parallel decoder architecture without any performance degradation. In addition, the power consumption can be minimized by reducing the total number of memory accesses for updated messages.
In this paper, design of a high throughput low-density parity-check (LDPC) decoder using overlapped message passing scheduling algorithm is presented. Regular hierarchical quasi-cyclic (H-QC) LDPC code is used in this design to provide good coding performance at long code length. The two-level regular H-QC LDPC code matrix structure is exploited to parallelize the row and column decoding operations. Our scheduling algorithm re-arranges these operations across iteration boundaries to avoid memory access conflicts. The memory requirement is reduced by half compared to pipelined decoders without scheduling. A (12288, 6144) LDPC decoder implemented in FPGA achieves 298 Mbps throughput performance.
The design of high speed decoders with traditional partly parallel architecture for non-quasi-cycle (NQC) LDPC codes is a challenging problem due to its high memory-block consumption and the low hardware utilization efficiency. In this paper, a general overlapped message passing (GOMP) decoding algorithm is proposed to improve the hardware utilization efficiency (HUE), which overcomes the limitation of overlapped message passing (OMP) decoders proposed before. On the basis of the given codes, this algorithm nearly doubles the throughput without sacrificing double memory or causing loss in performance compared to BP algorithm. Furthermore, we present a technique called cycle bus to reduce the number of block RAMs in the multi-core decoder. Moreover, an example of a rate-2/3, length-15360 irregular LDPC code with 8.43 dB coding gain for BPSK in AWGN channel is given, whose decoders features nearly double throughput, 22.22% increase in memory 8.35% reduction in logic registers cost and more reasonable distribution in block RAMs cost.
The design of a high-speed decoder using traditional partly parallel architecture for Non-Quasi-Cyclic (NQC) Low-Density Parity-Check (LDPC) codes is a challenging problem due to its high memory-block cost and low hardware utilization efficiency. In this paper, we present efficient hardware implementation schemes for NQCLDPC codes. First, we propose an implementation-oriented construction scheme for NQC-LDPC codes to avoid memory-access conflict in the partly parallel decoder. Then, we propose a Modified Overlapped Message-Passing (MOMP) algorithm for the hardware implementation of NQC-LDPC codes. This algorithm doubles the hardware utilization efficiency and supports a higher degree of parallelism than that used in the Overlapped Message Passing (OMP) technique proposed in previous works. We also present single-core and multi-core decoder architectures in the proposed MOMP algorithm to reduce memory cost and improve circuit efficiency. Moreover, we introduce a technique called the cycle bus to further reduce the number of block RAMs in multi-core decoders. Using numerical examples, we show that, for a rate-2/3, length-15360 NQC-LDPC code with 8.43-dB coding gain for Binary PhaseShift Keying (BPSK) in an Additive White Gaussian Noise (AWGN) channel, the decoder with the proposed scheme achieves a 23.8%-52.6% reduction in logic utilization per Mbps and a 29.0%-90.0% reduction in message-memory bits per Mbps.