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

EXIT ChartAnalysisof Binary

Gottfried Lechner, Troels Pedersen, Frederik Bajers Vej, Gerhard G. Kramer

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

Binary message-passing decoders forLDPC codes areanalyzed using EXITcharts. Fortheanalysis, thevariable nodedecoder performs allcomputations intheL-value domain. Forthespecial caseofa harddecision channel, thisleadsto thewell-know Gallager B algorithm, whiletheanalysis canbe extended tochannels withlarger output alphabets. Byincreasing theoutput alphabet fromharddecisions tofoursymbols, again ofmorethan1.0dBisachieved using optimized codes. Forthis codeoptimization, themixing property ofEXITfunctions hasto bemodified tothecaseofbinary message-passing decoders.

Related papers

LDPC碼之信息傳遞解碼演算法—調適性選擇位元節點之分析; Message Passing Decoding Algorithm of LDPC Codes—Analysis of Adaptively Selecting Bit Nodes

林仕元, Shih-yuan Lin

•Jul 14, 2008•0 citations

EXIT Chart Analysis of Binary Message-Passing Decoders

Gottfried Lechner, Troels Pedersen, Gerhard G. Kramer

Binary message-passing decoders for LDPC codes are analyzed using EXIT charts. For the analysis, the variable node decoder performs all computations in the L-value domain. For the special case of a hard decision channel, this leads to the well-know Gallager B algorithm, while the analysis can be extended to channels with larger output alphabets. By increasing the output alphabet from hard decisions to four symbols, a gain of more than 1.0 dB is achieved using optimized codes. For this code optimization, the mixing property of EXIT functions has to be modified to the case of binary message-passing decoders.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•8 citations

Analysis and Design of Binary Message Passing Decoders

Gottfried Lechner, Troels Pedersen, Gerhard G. Kramer

Binary message passing decoders for low-density parity-check codes are studied by using extrinsic information transfer charts. The channel delivers hard or soft decisions and the variable node decoder performs all computations in the log-likelihood ratio (L-value) domain. A hard decision results in the Gallager B algorithm and examples show that increasing the channel output alphabet to two bits gains more than 1.0 dB in signal to noise ratio when using optimized codes. Finally, it is shown that errors on cycles consisting only of degree two and three variable nodes cannot be corrected and a necessary and sufficient condition for the existence of a cycle-free subgraph is derived.

arXiv:1004.4020•IEEE Transactions on Communications•Dec 29, 2011•50 citations

A Survey of Recent Information Combining Bounds for Iterative Decoding of LDPC codes

Bobak Nazer

In this survey paper, we cover two very recent papers on bounds for EXIT chart analysis of LDPC codes that make minimal assumptions on the probability distribution of the messages passed between decoders. It is shown that the BEC and the BSC are always the maximizing and minimizing distributions on messages. From this, analytical bounds on EXIT charts are given. 1

•Jan 1, 2005•0 citations

Algorithmic Optimization of Non-Binary Decoders

Joseph Jabour

Optimisation algorithmique des décodeurs non-binaires Les codes non binaires sont des codes correcteurs d'erreurs très efficaces pour les petites tailles de message. Ils sont de plus naturellement adapté aux modulations codées et permettent ainsi de s'approcher de la capacité du canal. Toutefois, les décodeurs non binaires construit sur des ensembles de cardinalité élevée (supérieure ou égale à 64) sont encore marginalement utilisés dû à leur grande complexité de décodage. Cette thèse étudie et propose de nouveaux algorithmes de simplification du traitement des nœuds de parités pour deux types de codes correcteurs d'erreur Non-Binaire : les codes Low Density Parity Check non-binaire (NB-LDPC) et les codes polaire Non- Binaire (NB-PC). Pour les codes NB-LDPC, une nouvelle technique de décodage appelée "algorithme Best- Request-Default" (BRD) a été proposée. Dans un contexte d'échange de messages tronquées, il devient intéressant de relaxer le principe d'information extrinsèque et de rendre interdépendants les messages échangés sur une connexion entre un nœud de variable et un nœud de parité. Plus précisément, une partie du traitement du nœud de parité sera dédié pour fournir une réponse aux symboles "demandés" par le nœud de variable (terme "request" de l'algorithme). L'algorithme BRD permet de réduire très significativement la taille des messages échangés, et donc, la complexité du décodeur, et ce, sans dégradation significative de performances. Le décodage de code NB-PC de grande cardinalité est un domaine encore très peu exploré et l'état de l'art consiste à l'adaptation de l'algorithme Extended Min-Sum développé pour les codes NB-LDPC aux codes NB-PC. Nous proposons deux optimisations nouvelles : d'une part, une réduction de la complexité du traitement nœud de parité par un traitement asymétrique de ses entrées basés sur un critère de fiabilité relative (algorithme Asymmetrical Extended Min-Sum), d'autre part, une simplification ad-hoc de chaque contrainte de parité en fonction de la polarisation des messages lui arrivant (Polarisation Aware Polar Code Decoder). La combinaison de ces deux optimisations permet de réduire la complexité d'un facteur 2 par rapport à l'état de l'art, de nouveau sans dégradation notable des performances de décodage.

•Dec 14, 2023•0 citations

Properties of Optimum Binary Message-Passing Decoders

Masoud Ardakani, Frank R. Kschischang

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

IEEE Transactions on Information Theory•Sep 26, 2005•14 citations
Binary message-passing decoders forLDPC codes areanalyzed using EXITcharts. Fortheanalysis, thevariable nodedecoder performs allcomputations intheL-value domain. Forthespecial caseofa harddecision channel, thisleadsto thewell-know Gallager B algorithm, whiletheanalysis canbe extended tochannels withlarger output alphabets. Byincreasing theoutput alphabet fromharddecisions tofoursymbols, again ofmorethan1.0dBisachieved using optimized codes. Forthis codeoptimization, themixing property ofEXITfunctions hasto bemodified tothecaseofbinary message-passing decoders.
Binary message-passing decoders for LDPC codes are analyzed using EXIT charts. For the analysis, the variable node decoder performs all computations in the L-value domain. For the special case of a hard decision channel, this leads to the well-know Gallager B algorithm, while the analysis can be extended to channels with larger output alphabets. By increasing the output alphabet from hard decisions to four symbols, a gain of more than 1.0 dB is achieved using optimized codes. For this code optimization, the mixing property of EXIT functions has to be modified to the case of binary message-passing decoders.
Binary message passing decoders for low-density parity-check codes are studied by using extrinsic information transfer charts. The channel delivers hard or soft decisions and the variable node decoder performs all computations in the log-likelihood ratio (L-value) domain. A hard decision results in the Gallager B algorithm and examples show that increasing the channel output alphabet to two bits gains more than 1.0 dB in signal to noise ratio when using optimized codes. Finally, it is shown that errors on cycles consisting only of degree two and three variable nodes cannot be corrected and a necessary and sufficient condition for the existence of a cycle-free subgraph is derived.
Optimisation algorithmique des décodeurs non-binaires Les codes non binaires sont des codes correcteurs d'erreurs très efficaces pour les petites tailles de message. Ils sont de plus naturellement adapté aux modulations codées et permettent ainsi de s'approcher de la capacité du canal. Toutefois, les décodeurs non binaires construit sur des ensembles de cardinalité élevée (supérieure ou égale à 64) sont encore marginalement utilisés dû à leur grande complexité de décodage. Cette thèse étudie et propose de nouveaux algorithmes de simplification du traitement des nœuds de parités pour deux types de codes correcteurs d'erreur Non-Binaire : les codes Low Density Parity Check non-binaire (NB-LDPC) et les codes polaire Non- Binaire (NB-PC). Pour les codes NB-LDPC, une nouvelle technique de décodage appelée "algorithme Best- Request-Default" (BRD) a été proposée. Dans un contexte d'échange de messages tronquées, il devient intéressant de relaxer le principe d'information extrinsèque et de rendre interdépendants les messages échangés sur une connexion entre un nœud de variable et un nœud de parité. Plus précisément, une partie du traitement du nœud de parité sera dédié pour fournir une réponse aux symboles "demandés" par le nœud de variable (terme "request" de l'algorithme). L'algorithme BRD permet de réduire très significativement la taille des messages échangés, et donc, la complexité du décodeur, et ce, sans dégradation significative de performances. Le décodage de code NB-PC de grande cardinalité est un domaine encore très peu exploré et l'état de l'art consiste à l'adaptation de l'algorithme Extended Min-Sum développé pour les codes NB-LDPC aux codes NB-PC. Nous proposons deux optimisations nouvelles : d'une part, une réduction de la complexité du traitement nœud de parité par un traitement asymétrique de ses entrées basés sur un critère de fiabilité relative (algorithme Asymmetrical Extended Min-Sum), d'autre part, une simplification ad-hoc de chaque contrainte de parité en fonction de la polarisation des messages lui arrivant (Polarisation Aware Polar Code Decoder). La combinaison de ces deux optimisations permet de réduire la complexité d'un facteur 2 par rapport à l'état de l'art, de nouveau sans dégradation notable des performances de décodage.
We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.