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

International Zurich Seminar on Communications (IZS)

Nonbinary decoding of structured LDPC codes

Daniele Capirone, Giacomo Como, Fabio Fagnani, Federica Garin

Published Mar 1, 2008• 3 citations
Publisher

Abstract

A class of serial turbo codes admitting low-density parity-check (LDPC) representation is considered. Their parity matrix has a random and a structured part. Thanks to their turbo structure, these codes are linear-time encodable, while they can be decoded as LDPC codes. An ensemble analysis for the error floor region, on the line of classical results for serial turbo codes, suggests a design parameter. Simulation results using usual LDPC message-passing show poor performance and no dependence on such parameter. A different block-wise decoding algorithm is proposed, which considerably improves performance. With this new decoding scheme, simulations confirm the theoretical design parameters in the medium-high SNR region.

DOI
10.1109/izs.2008.4497278

Related papers

Structured LDPC Codes with Linear Complexity Encoding

Vinay Bhardwaj, Nagendra Prasad Pathak, Arun R. Kumar

Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.

•Jan 1, 2009•3 citations

Memory-efficient turbo decoder architectures for LDPC codes

Mohammad M. Mansour, Naresh R. Shanbhag

In this paper, we propose a turbo decoding message-passing (TDMP) algorithm to decode regular and irregular low-density parity-check (LDPC) codes. The TDMP algorithm has two main advantages over the commonly employed two-phase message-passing algorithm. First, it exhibits a faster convergence behavior (up to 50% less iterations), and improvement in coding gain (up to an order of magnitude for moderate-to-high SNR and small number of iterations). Second, the corresponding decoder architecture has a significantly reduced memory requirement that amounts to a savings of (75 + 25n//spl Sigma/ node-degrees)% > 75% for code-length n. A decoder architecture featuring the TDNW algorithm is also presented. Furthermore, we propose a new structure on the parity-check matrix of an LDPC code based on permutation matrices aimed at reducing interconnect complexity and improving decoding throughput. In addition, we construct a wide range of LDPC codes based on Ramanujan graphs which possess this structure.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Aug 27, 2003•35 citations

Design of LDPC decoders for improved low error rate performance: quantization and algorithm choices

Zhengya Zhang, Lara Dolecek, Borivoje Nikolić +2 more

Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders

IEEE Transactions on Communications•Nov 1, 2009•113 citations

Code construction algorithm for architecture aware LDPC codes with low-error-floor

Dariusz Kania, Wojciech Sułek

The common approach for the design of an error correction system is first to construct a code and then to define the hardware structure of the encoder and decoder. However, in the case of LDPC codes (low-density parity-check) such a constructed code is generally not well suited for a hardware implementation. It has been recognized that the code construction and hardware design must be considered jointly to facilitate LDPC decoder and encoder implementation. In this paper, an efficient decoder structure for regular and irregular LDPC codes, based on TDMP (turbo-decoding message passing) scheme is designed first. The decoder has been implemented and verified in an FPGA device. Constraints for the parity check matrix of a code to be suitable for the decoder architecture are defined. Then an algorithm for LDPC parity check matrix construction subject to these constraints is presented. The algorithm aims at improving performance of the code in the low SNR region by employing irregular codes as well as in high SNR region by reducing the number of small Stopping Sets and Trapping Sets in the Tanner graph of the code making use of a computer search technique.

IEEE Region International Conference on Computational Technologies in Electrical and Electronics Engineering•Jul 1, 2008•7 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations

Ensemble Decoding Thresholds for LDPC and Turbo Codes

W.E. Ryan, Shu Wen Lin

The previous chapter examined code properties responsible for the floor region (high-SNR region) of LDPC and turbo codes. Specifically, the emphasis was on the computation of various weight enumerators for LDPC and turbo code ensembles because a poor weight spectrum leads to poor performance in a code's floor region both for iterative decoders and for maximum-likelihood decoders. That chapter also introduced ensemble enumerators for trapping sets and stopping sets, both of which can lead to poor floor performance in iterative decoders. In this chapter we examine the iterative decoding performance of LDPC and turbo code ensembles in the complementary low-SNR region, the “waterfall” region. We show that the iterative decoding of long LDPC and turbo codes displays a threshold effect in which communication is reliable beyond this threshold and unreliable below it. The threshold is a function of code ensemble properties and the tools introduced in this chapter allow the designer to predict the decoding threshold and its gap from Shannon's limit. The ensemble properties for LDPC codes are the degree distributions which are typically the design targets for the code-design techniques presented in subsequent chapters. The ensemble properties for turbo codes are the selected constituent codes. Our development borrows heavily from the references listed at the end of the chapter and our focus is on the binary-input AWGN channel. The references and the problems consider other channels. Density Evolution for Regular LDPC Codes We first summarize the main results of [1] with regard to iterative (message passing) decoding of long, regular LDPC codes.

Cambridge University Press eBooks•Sep 17, 2009•0 citations
A class of serial turbo codes admitting low-density parity-check (LDPC) representation is considered. Their parity matrix has a random and a structured part. Thanks to their turbo structure, these codes are linear-time encodable, while they can be decoded as LDPC codes. An ensemble analysis for the error floor region, on the line of classical results for serial turbo codes, suggests a design parameter. Simulation results using usual LDPC message-passing show poor performance and no dependence on such parameter. A different block-wise decoding algorithm is proposed, which considerably improves performance. With this new decoding scheme, simulations confirm the theoretical design parameters in the medium-high SNR region.
Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.
In this paper, we propose a turbo decoding message-passing (TDMP) algorithm to decode regular and irregular low-density parity-check (LDPC) codes. The TDMP algorithm has two main advantages over the commonly employed two-phase message-passing algorithm. First, it exhibits a faster convergence behavior (up to 50% less iterations), and improvement in coding gain (up to an order of magnitude for moderate-to-high SNR and small number of iterations). Second, the corresponding decoder architecture has a significantly reduced memory requirement that amounts to a savings of (75 + 25n//spl Sigma/ node-degrees)% > 75% for code-length n. A decoder architecture featuring the TDNW algorithm is also presented. Furthermore, we propose a new structure on the parity-check matrix of an LDPC code based on permutation matrices aimed at reducing interconnect complexity and improving decoding throughput. In addition, we construct a wide range of LDPC codes based on Ramanujan graphs which possess this structure.
Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders
The common approach for the design of an error correction system is first to construct a code and then to define the hardware structure of the encoder and decoder. However, in the case of LDPC codes (low-density parity-check) such a constructed code is generally not well suited for a hardware implementation. It has been recognized that the code construction and hardware design must be considered jointly to facilitate LDPC decoder and encoder implementation. In this paper, an efficient decoder structure for regular and irregular LDPC codes, based on TDMP (turbo-decoding message passing) scheme is designed first. The decoder has been implemented and verified in an FPGA device. Constraints for the parity check matrix of a code to be suitable for the decoder architecture are defined. Then an algorithm for LDPC parity check matrix construction subject to these constraints is presented. The algorithm aims at improving performance of the code in the low SNR region by employing irregular codes as well as in high SNR region by reducing the number of small Stopping Sets and Trapping Sets in the Tanner graph of the code making use of a computer search technique.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.
The previous chapter examined code properties responsible for the floor region (high-SNR region) of LDPC and turbo codes. Specifically, the emphasis was on the computation of various weight enumerators for LDPC and turbo code ensembles because a poor weight spectrum leads to poor performance in a code's floor region both for iterative decoders and for maximum-likelihood decoders. That chapter also introduced ensemble enumerators for trapping sets and stopping sets, both of which can lead to poor floor performance in iterative decoders. In this chapter we examine the iterative decoding performance of LDPC and turbo code ensembles in the complementary low-SNR region, the “waterfall” region. We show that the iterative decoding of long LDPC and turbo codes displays a threshold effect in which communication is reliable beyond this threshold and unreliable below it. The threshold is a function of code ensemble properties and the tools introduced in this chapter allow the designer to predict the decoding threshold and its gap from Shannon's limit. The ensemble properties for LDPC codes are the degree distributions which are typically the design targets for the code-design techniques presented in subsequent chapters. The ensemble properties for turbo codes are the selected constituent codes. Our development borrows heavily from the references listed at the end of the chapter and our focus is on the binary-input AWGN channel. The references and the problems consider other channels. Density Evolution for Regular LDPC Codes We first summarize the main results of [1] with regard to iterative (message passing) decoding of long, regular LDPC codes.