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

IEEE International New Circuits and Systems Conference (NEWCAS)

Controlled start-up stochastic decoding of LDPC codes

Mountassar Maamoun, Rafik Bradai, Ali Naderi, Rachid Beguenane, Mohamad Sawan

Published Jun 1, 2013• 6 citations
Publisher

Abstract

This paper concerns a new and powerful Low-Density Parity-Check (LDPC) stochastic decoding algorithm, called Controlled Start-up Stochastic (CSS) decoding, to implement fully parallel LDPC decoders. The proposed algorithm uses a clever starting point computing method to improve the convergence as well as to reduce the latency of the decoding process, without a significant hardware complexity cost. Using this stochastic method, in low signal-to-noise ratio (SNR) region, a short LDPC code can outperforms the fixed point state-of-the-art (2048, 1723) LDPC code. To validate the performance of the proposed algorithm, a (48, 24) LDPC code are implemented on Xilinx Virtex-6 VLX240T field programmable gate array device, with and without the CSS method. The new algorithm provides a decoding speed seven times faster and a Bit Error Rate (BER) hundred times better at E3/N0=4.5 dB. In addition, the results provide a BER better than the 6 bits offset min-sum algorithm (OMSA) and better than the 6 bits sum-product algorithm (SPA) for the (2048, 1723) LDPC code, below E3/N0=3.9 dB and Eb/N0=4.3 dB respectively. The obtained results show that, the proposed algorithm is the first stochastic algorithm which can outperform the OMSA and SPA algorithms, with less hardware complexity.

DOI
10.1109/newcas.2013.6573662

Related papers

Improved controlled start-up stochastic LDPC decoder for efficient FPGA-based implementation

Ghania Zerari, Abderrezak Guessoum

This paper introduces a new and an improved controlled start-up stochastic (CSS) architecture of Low-Density Parity-Check (LDPC) decoding, to implement fully parallel FPGA-based decoders. The developed architecture uses a new variable nodes structure with larger internal memory lengths, to improve the convergence, without significant additional field programmable gate array (FPGA) resource. To validate the advantage of the proposed approach, a medium (1024, 512) and short (200, 100) codes are implemented. The results of Xilinx Virtex-6 VLX240T FPGA shoes that the variable node internal memories lengths can be increased from 2-bit, used in CSS and Delayed Stochastic (DS) decoders, to 64-bit without addition resource.

•Dec 1, 2015•1 citation

Fully Parallel Stochastic LDPC Decoders

Saeed Sharifi Tehrani, Shie Mannor, Warren J. Gross

Stochastic decoding is a new approach to iterative decoding on graphs. This paper presents a hardware architecture for fully parallel stochastic low-density parity-check (LDPC) decoders. To obtain the characteristics of the proposed architecture, we apply this architecture to decode an irregular state-of-the-art (1056,528) LDPC code on a Xilinx Virtex-4 LX200 field-programmable gate-array (FPGA) device. The implemented decoder achieves a clock frequency of 222 MHz and a throughput of about 1.66 Gb/s at$E_{b}/N_{0}={\hbox {4.25~dB}}$(a bit error rate of$10^{-8}$). It provides decoding performance within 0.5 and 0.25 dB of the floating-point sum-product algorithm with 32 and 16 iterations, respectively, and similar error-floor behavior. The decoder uses less than 40% of the lookup tables, flip-flops, and IO ports available on the FPGA device. The results provided in this paper validate the potential of stochastic LDPC decoding as a practical and competitive fully parallel decoding approach.

IEEE Transactions on Signal Processing•Aug 20, 2008•204 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.

•Jan 1, 2007•2 citations

Adaptive Multiset Stochastic Decoding of Non-Binary LDPC Codes

Alexandru Ciobanu, Saied Hemati, Warren J. Gross

We propose a non-binary stochastic decoding algorithm for low-density parity-check (LDPC) codes over GF(q) with degree two variable nodes, called Adaptive Multiset Stochastic Algorithm (AMSA). The algorithm uses multisets, an extension of sets that allows multiple occurrences of an element, to represent probability mass functions that simplifies the structure of the variable nodes. The run-time complexity of one decoding cycle using AMSA is O(q) for conventional memory architectures, and O(1) if a custom memory architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two (192,96) (2,4)-regular codes over GF(64) and GF(256), both achieving a maximum clock frequency of 108 MHz. The GF(64) decoder has a coded throughput of 65 Mb/s at Eb/N0=2.4 dB when using conventional memory, while a decoder using the custom memory version can achieve 698 Mb/s at the same Eb/N0. At a frame error rate (FER) of 2×10-6the GF(64) version of the algorithm is only 0.04 dB away from the floating-point SPA performance, and for the GF(256) code the difference is 0.2 dB. To the best of our knowledge, this is the first fully parallel non-binary LDPC decoder over GF(256) reported in the literature.

IEEE Transactions on Signal Processing•May 23, 2013•17 citations

Modification in the Construction of Non-Binary LDPC Decoder using Stochastic Computation

R. Kalaiarasan, M. Anbuselvi

Low-Density Parity Check (LDPC) codes are linear block codes which perform closer to Shannon"s limit.It is defined by the parity check matrix (PCM) which contains only a few ones in comparison to the number of zeros (sparsity).Stochastic based computation is a method to design lowprecision digital circuits.In stochastic computing, probabilities are encoded by random sequences of bits.In this paper, we focus on the design of Relaxed Half Stochastic (RHS) based algorithm for Non-Binary LDPC decoder, with reduced hardware complexity and optimal decoding performance.Here Sum Product Algorithm (SPA) based variable nodes and stochastic based check nodes are integrated.Thereby the convergence speed of the algorithm is improved.The limitation of the complete stochastic decoder is based on the field order and the degree of variable node.This could be overcome by the method of RHS algorithm.The PCM (Parity Check Matrix) which defines the strength of the LDPC codes contains the non-zero elements.Increasing the sparsity of the PCM, helps in reducing the computation complexity.We propose two modifications in the PCM namely, LDM (Lower Diagonal Matrix) and DDM (Doubly Diagonal Matrix).Decoding performance measured in terms of bit error rate shows that non binary LDPC decoder outperforms than binary LDPC decoder.

International Journal of Computer Applications•Apr 18, 2014•0 citations

Design and implementation of decoders for error correction in high-speed communication systems.

Joan Marc Català Pérez

This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.

•Jul 7, 2017•0 citations
This paper concerns a new and powerful Low-Density Parity-Check (LDPC) stochastic decoding algorithm, called Controlled Start-up Stochastic (CSS) decoding, to implement fully parallel LDPC decoders. The proposed algorithm uses a clever starting point computing method to improve the convergence as well as to reduce the latency of the decoding process, without a significant hardware complexity cost. Using this stochastic method, in low signal-to-noise ratio (SNR) region, a short LDPC code can outperforms the fixed point state-of-the-art (2048, 1723) LDPC code. To validate the performance of the proposed algorithm, a (48, 24) LDPC code are implemented on Xilinx Virtex-6 VLX240T field programmable gate array device, with and without the CSS method. The new algorithm provides a decoding speed seven times faster and a Bit Error Rate (BER) hundred times better at E3/N0=4.5 dB. In addition, the results provide a BER better than the 6 bits offset min-sum algorithm (OMSA) and better than the 6 bits sum-product algorithm (SPA) for the (2048, 1723) LDPC code, below E3/N0=3.9 dB and Eb/N0=4.3 dB respectively. The obtained results show that, the proposed algorithm is the first stochastic algorithm which can outperform the OMSA and SPA algorithms, with less hardware complexity.
This paper introduces a new and an improved controlled start-up stochastic (CSS) architecture of Low-Density Parity-Check (LDPC) decoding, to implement fully parallel FPGA-based decoders. The developed architecture uses a new variable nodes structure with larger internal memory lengths, to improve the convergence, without significant additional field programmable gate array (FPGA) resource. To validate the advantage of the proposed approach, a medium (1024, 512) and short (200, 100) codes are implemented. The results of Xilinx Virtex-6 VLX240T FPGA shoes that the variable node internal memories lengths can be increased from 2-bit, used in CSS and Delayed Stochastic (DS) decoders, to 64-bit without addition resource.
Stochastic decoding is a new approach to iterative decoding on graphs. This paper presents a hardware architecture for fully parallel stochastic low-density parity-check (LDPC) decoders. To obtain the characteristics of the proposed architecture, we apply this architecture to decode an irregular state-of-the-art (1056,528) LDPC code on a Xilinx Virtex-4 LX200 field-programmable gate-array (FPGA) device. The implemented decoder achieves a clock frequency of 222 MHz and a throughput of about 1.66 Gb/s atEb/N0=4.25 dBE_{b}/N_{0}={\hbox {4.25~dB}}Eb​/N0​=4.25 dB(a bit error rate of10−810^{-8}10−8). It provides decoding performance within 0.5 and 0.25 dB of the floating-point sum-product algorithm with 32 and 16 iterations, respectively, and similar error-floor behavior. The decoder uses less than 40% of the lookup tables, flip-flops, and IO ports available on the FPGA device. The results provided in this paper validate the potential of stochastic LDPC decoding as a practical and competitive fully parallel decoding approach.
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.
We propose a non-binary stochastic decoding algorithm for low-density parity-check (LDPC) codes over GF(q) with degree two variable nodes, called Adaptive Multiset Stochastic Algorithm (AMSA). The algorithm uses multisets, an extension of sets that allows multiple occurrences of an element, to represent probability mass functions that simplifies the structure of the variable nodes. The run-time complexity of one decoding cycle using AMSA is O(q) for conventional memory architectures, and O(1) if a custom memory architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two (192,96) (2,4)-regular codes over GF(64) and GF(256), both achieving a maximum clock frequency of 108 MHz. The GF(64) decoder has a coded throughput of 65 Mb/s at Eb/N0=2.4 dB when using conventional memory, while a decoder using the custom memory version can achieve 698 Mb/s at the same Eb/N0. At a frame error rate (FER) of 2×10-6the GF(64) version of the algorithm is only 0.04 dB away from the floating-point SPA performance, and for the GF(256) code the difference is 0.2 dB. To the best of our knowledge, this is the first fully parallel non-binary LDPC decoder over GF(256) reported in the literature.
Low-Density Parity Check (LDPC) codes are linear block codes which perform closer to Shannon"s limit.It is defined by the parity check matrix (PCM) which contains only a few ones in comparison to the number of zeros (sparsity).Stochastic based computation is a method to design lowprecision digital circuits.In stochastic computing, probabilities are encoded by random sequences of bits.In this paper, we focus on the design of Relaxed Half Stochastic (RHS) based algorithm for Non-Binary LDPC decoder, with reduced hardware complexity and optimal decoding performance.Here Sum Product Algorithm (SPA) based variable nodes and stochastic based check nodes are integrated.Thereby the convergence speed of the algorithm is improved.The limitation of the complete stochastic decoder is based on the field order and the degree of variable node.This could be overcome by the method of RHS algorithm.The PCM (Parity Check Matrix) which defines the strength of the LDPC codes contains the non-zero elements.Increasing the sparsity of the PCM, helps in reducing the computation complexity.We propose two modifications in the PCM namely, LDM (Lower Diagonal Matrix) and DDM (Doubly Diagonal Matrix).Decoding performance measured in terms of bit error rate shows that non binary LDPC decoder outperforms than binary LDPC decoder.
This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.