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

Mesaj aktarımlı çözümleme algoritmalarının iki ve çok değişkenli düşük yoğunluklu eşlik kontrol (DYEK) kodlarında başarım karşılaştırması.

Uzunoğlu, Cihan

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

In this thesis, we investigate the basics of Low-Density Parity-Check (LDPC) codes over binary and non-binary alphabets. We especially focus on the message passing decoding algorithms, which have different message definitions such as a posteriori probabilities, log-likelihood ratios and Fourier transforms of probabilities. We present the simulation results that compare the performances of small block length binary and non-binary LDPC codes, which have regular and irregular structures over GF(2),GF(4) and GF(8) alphabets. We observe that choosing non-binary alphabets improve the performance with careful selection of mean column weight by comparing LDPC codes with variable node degrees of 3, 2.8 and 2.6, since it is effective in the order of GF(2), GF(4) and GF(8) performances.

Related papers

Düşük yoğunluklu eşlik denetim kodları için kod çözme algoritmalarının karşılaştırılması.

Kolaylı, Mert

Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.

•Jan 1, 2006•0 citations

A class of non-binary LDPC codes

Deepak Gilra

In this thesis we study Low Density Parity Check (LDPC) and LDPC like codes over \nnon-binary fields. We extend the concepts used for non-binary LDPC codes to generalize \nProduct Accumulate (PA) codes to non-binary fields. We present simulation results that \nshow that PA codes over GF(4) performs considerably better than binary PA codes at \nsmaller block lengths and slightly better at large block lengths. We also propose a trellis \nbased decoding algorithm to decode PA codes and show that its complexity is \nconsiderably lower than the message-passing algorithm. \nIn the second part of the thesis we study the convergence properties of non-binary PA \ncodes and non-binary LDPC codes. We use EXIT-charts to study the convergence \nproperties of non-binary LDPC codes with different mean column weights and show why \ncertain irregularities are better. Although the convergence threshold predicted by EXIT-charts \non non-binary LDPC codes is quite optimistic we can still use EXIT-charts for \ncomparison between non-binary LDPC codes with different mean column weights.

•Sep 30, 2004•1 citation

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,034 citations

이진 LDPC 부호를 위한 저복잡도 복호 알고리즘

민우홍

Low-density parity-check (LDPC) codes can be efficiently decoded with high performance. Especially, sum-product algorithm can achieve excellent performance, but high complexity. Min-sum algorithm is low complexity, but less performance. So, low complexity and high performance decoding algorithm is needed. \n \n In this thesis, we consider low complexity, high performance decoding algorithms. First, we introduce various decoding algorithms for binary LDPC codes. Second, we propose normalized min-sum algorithm with three normalization factors. This algorithm outperforms the existing normalized min-sum algorithm, normalized min-sum algorithm with two normalization factors. Third, we introduce finite alphabet iterative decoders (FAID) which is a new paradigm for finite precision iterative decoding. But existing FAID algorithm only considers binary LDPC codes with column weight three. So, we propose FAID for binary LDPC codes with column weight five. Our proposed algorithms have low-complexity and good error correcting performance.

•Jan 1, 2018•0 citations

Analysis of Binary and Ternary Message Passing Decoding for Generalized LDPC Codes

Emna Ben Yacoub, Gianluigi Liva

Binary and a ternary message passing decoding algorithms for generalized low-density parity-check codes are defined and analyzed. In all algorithms, the variable nodes exploit soft channel information. However, the exchanged messages between variable and check nodes are binary or ternary. Two types of local decoders are assumed at the check nodes, namely an optimum a-posteriori probability soft-input soft-output decoder, and a more practical bounded distance decoder. A density evolution analysis for irregular code ensembles is developed for all the introduced algorithms, which allows obtaining the scaling coefficients needed for the variable node operation. Finite-length simulation results confirm the validity of the asymptotic analysis.

International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)•Oct 25, 2021•2 citations

Irregular Generalized LDPC codes in Practical Communication Scenarios

Irina E. Bocharova, Boris D. Kudryashov, Sander Mikelsaar

High-rate irregular Generalized LDPC (GLDPC) codes with low-complexity constituent codes are studied. The main area of focus is the optimization of the underlying irregular binary LDPC codes and their matching with constituent codes. Finite length random coding bound on the maximum-likelihood decoding error probability of a random ensemble of irregular GLDPC codes is derived and compared with a similar bound for non-binary (NB) LDPC codes over small alphabets.A new algorithm for assigning columns of the parity-check matrix of a constituent code to nonzero elements of a base matrix of the quasi-cyclic (QC)-GLDPC code is presented. Examples of the constructed QC-GLDPC codes are given. The simulation results for frame error rate (FER) performance of the belief-propagation (BP) decoding for the QC-GLDPC codes are presented and compared with the same performance of NB QC-LDPC codes over small alphabets and binary LDPC codes in the WiFi and 5G standards.Both GLDPC codes and NB LDPC codes with sufficiently low decoding complexity are shown to outperform their binary LDPC counterparts, while GLDPC codes appear to be more advantageous in terms of decoding complexity.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•1 citation
In this thesis, we investigate the basics of Low-Density Parity-Check (LDPC) codes over binary and non-binary alphabets. We especially focus on the message passing decoding algorithms, which have different message definitions such as a posteriori probabilities, log-likelihood ratios and Fourier transforms of probabilities. We present the simulation results that compare the performances of small block length binary and non-binary LDPC codes, which have regular and irregular structures over GF(2),GF(4) and GF(8) alphabets. We observe that choosing non-binary alphabets improve the performance with careful selection of mean column weight by comparing LDPC codes with variable node degrees of 3, 2.8 and 2.6, since it is effective in the order of GF(2), GF(4) and GF(8) performances.
Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.
In this thesis we study Low Density Parity Check (LDPC) and LDPC like codes over \nnon-binary fields. We extend the concepts used for non-binary LDPC codes to generalize \nProduct Accumulate (PA) codes to non-binary fields. We present simulation results that \nshow that PA codes over GF(4) performs considerably better than binary PA codes at \nsmaller block lengths and slightly better at large block lengths. We also propose a trellis \nbased decoding algorithm to decode PA codes and show that its complexity is \nconsiderably lower than the message-passing algorithm. \nIn the second part of the thesis we study the convergence properties of non-binary PA \ncodes and non-binary LDPC codes. We use EXIT-charts to study the convergence \nproperties of non-binary LDPC codes with different mean column weights and show why \ncertain irregularities are better. Although the convergence threshold predicted by EXIT-charts \non non-binary LDPC codes is quite optimistic we can still use EXIT-charts for \ncomparison between non-binary LDPC codes with different mean column weights.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.
Low-density parity-check (LDPC) codes can be efficiently decoded with high performance. Especially, sum-product algorithm can achieve excellent performance, but high complexity. Min-sum algorithm is low complexity, but less performance. So, low complexity and high performance decoding algorithm is needed. \n \n In this thesis, we consider low complexity, high performance decoding algorithms. First, we introduce various decoding algorithms for binary LDPC codes. Second, we propose normalized min-sum algorithm with three normalization factors. This algorithm outperforms the existing normalized min-sum algorithm, normalized min-sum algorithm with two normalization factors. Third, we introduce finite alphabet iterative decoders (FAID) which is a new paradigm for finite precision iterative decoding. But existing FAID algorithm only considers binary LDPC codes with column weight three. So, we propose FAID for binary LDPC codes with column weight five. Our proposed algorithms have low-complexity and good error correcting performance.
Binary and a ternary message passing decoding algorithms for generalized low-density parity-check codes are defined and analyzed. In all algorithms, the variable nodes exploit soft channel information. However, the exchanged messages between variable and check nodes are binary or ternary. Two types of local decoders are assumed at the check nodes, namely an optimum a-posteriori probability soft-input soft-output decoder, and a more practical bounded distance decoder. A density evolution analysis for irregular code ensembles is developed for all the introduced algorithms, which allows obtaining the scaling coefficients needed for the variable node operation. Finite-length simulation results confirm the validity of the asymptotic analysis.
High-rate irregular Generalized LDPC (GLDPC) codes with low-complexity constituent codes are studied. The main area of focus is the optimization of the underlying irregular binary LDPC codes and their matching with constituent codes. Finite length random coding bound on the maximum-likelihood decoding error probability of a random ensemble of irregular GLDPC codes is derived and compared with a similar bound for non-binary (NB) LDPC codes over small alphabets.A new algorithm for assigning columns of the parity-check matrix of a constituent code to nonzero elements of a base matrix of the quasi-cyclic (QC)-GLDPC code is presented. Examples of the constructed QC-GLDPC codes are given. The simulation results for frame error rate (FER) performance of the belief-propagation (BP) decoding for the QC-GLDPC codes are presented and compared with the same performance of NB QC-LDPC codes over small alphabets and binary LDPC codes in the WiFi and 5G standards.Both GLDPC codes and NB LDPC codes with sufficiently low decoding complexity are shown to outperform their binary LDPC counterparts, while GLDPC codes appear to be more advantageous in terms of decoding complexity.