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 Symposium on Information Theory (ISIT)

Analysis of One Step Majority Logic Decoders Constructed From Faulty Gates

Shashi Kiran Chilappagari, Miloš Ivković, Bane V. Vasic

Published Jul 1, 2006• 28 citations
Publisher

Abstract

In this paper we propose an analytical method to evaluate the performance of one step majority logic decoders constructed from faulty gates. We analyze the decoder under the assumption that the gates fail independently. We calculate the average bit error probability of such a decoder and apply the method to the special case of projective geometry codes. The method, however, applies to any regular low-density parity-check code of girth at least six but the calculations are much simpler for the projective geometry codes. We present results for the bit error rate performance of four codes from projective planes

DOI
10.1109/isit.2006.261713

Related papers

Majority Logic Decoding Under Data-Dependent Logic Gate Failures

Srdan S. Brkic, Predrag Ivaniš, Bane V. Vasic

A majority logic decoder made of unreliable logic gates, whose failures are transient and data-dependent, is analyzed. Based on a combinatorial representation of fault configurations a closed-form expression for the average bit error rate for a one-step majority logic decoder is derived, for a regular low-density parity-check (LDPC) code ensemble and the proposed failure model. The presented analysis framework is then used to establish bounds on the one-step majority logic decoder performance under the simplified probabilistic gate-output switching model. Based on the expander property of Tanner graphs of LDPC codes, it is proven that a version of the faulty parallel bit-flipping decoder can correct a fixed fraction of channel errors in the presence of data-dependent gate failures. The results are illustrated with numerical examples of finite geometry codes.

arXiv:1507.07155•IEEE Transactions on Information Theory•Aug 18, 2017•6 citations

Guaranteed error correction of faulty bit-flipping decoders under data-dependent gate failures

Srdan S. Brkic, Predrag Ivaniš, Bane V. Vasic

In this paper we analyze the effect of hardware unreliability to performance of bit-flipping decoders of low-density parity-check (LDPC) codes. We apply expander arguments to show that the simple parallel bit flipping decoder, built partially from faulty gates, can correct a linear fraction of worst case channel errors, when gate failures are correlated and dependent on the switching activity of logic gates. In addition, we provide a lower bound on the guaranteed error correction of LDPC codes with left degree of at least eight.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

Performance evaluation of faulty iterative decoders using absorbing Markov chains

Predrag Ivaniš, Bane V. Vasic, David Declercq

We propose an iterative decoder made of a combination of faulty and perfect logic gates that is capable of correcting more channel errors than its counterpart made completely of perfect logic gates. We present an error probability analysis based on absorbing Markov chains, and explain how the randomness in the check node update function helps a decoder to escape to local minima associated with trapping sets. For the (155, 64) Tanner low-density parity check code, we provide a range of gate failure probabilities for which imperfect decoders perform better.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•4 citations

An Efficient Majority Error Detection in Logic Decoding with Euclidean Geometry Low Density Parity Check (Eg-Ldpc) Codes

M .Vengadapathiraj Mr, U. Maheswaran, A.Karunakaran Mr

In a recent article, a technique was proposed to step up the majority logic decoding of variation set low density parity check codes. This is helpful as majority logic decoding can be implemented serially with trouble-free hardware but requires a huge decoding time. The method detect whether a word has errors in the initial iterations of majority logic decoding, and at what time there are no errors the decoding split ends without completing the rest of the iterations. While the majority words in a memory will be error-free, the average decoding time is significantly reduced. The outcome obtained proves that the technique is also effective for EG-LDPC codes. General simulation results are given to precisely estimate the prospect of error detection for different code sizes and numbers of errors.

International Journal of Business Intelligents•Jun 11, 2019•0 citations

Near Optimum Majority-Logic Based Decoding of Low-Density Parity-Check Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.

International Conference on Communications•Jun 1, 2011•3 citations

Analysis of the Error Correction Capability of LDPC and MDPC Codes Under Parallel Bit-Flipping Decoding and Application to Cryptography

Paolo Santini, Massimo Battaglioni, Marco Baldi +1 more

Iterative decoders used for decoding low-density parity-check (LDPC) and moderate-density parity-check (MDPC) codes are not characterized by a deterministic decoding radius and their error rate performance is usually assessed through intensive Monte Carlo simulations. However, several applications, like code-based cryptography, need guaranteed low values of the error rate, which are infeasible to assess through simulations, thus requiring the development of theoretical models for the error rate of these codes. Some models of this type already exist, but become computationally intractable for parameters of practical interest. Other approaches approximate the code ensemble behaviour through assumptions, which may not hold true for a specific code. We propose a theoretical analysis of the error correction capability of LDPC and MDPC codes that allows deriving tight bounds on the error rate at the output of parallel bit-flipping decoders. Special attention is devoted to the case of codes with small girth. Single-iteration decoding is investigated through a rigorous approach, which does not require any assumption and results in a guaranteed error correction capability for any single code. We show an example of application of the new bound to the context of code-based cryptography, where guaranteed error rates are needed to achieve strong security levels.

arXiv:1910.00472•IEEE Transactions on Communications•Apr 14, 2020•29 citations
In this paper we propose an analytical method to evaluate the performance of one step majority logic decoders constructed from faulty gates. We analyze the decoder under the assumption that the gates fail independently. We calculate the average bit error probability of such a decoder and apply the method to the special case of projective geometry codes. The method, however, applies to any regular low-density parity-check code of girth at least six but the calculations are much simpler for the projective geometry codes. We present results for the bit error rate performance of four codes from projective planes
A majority logic decoder made of unreliable logic gates, whose failures are transient and data-dependent, is analyzed. Based on a combinatorial representation of fault configurations a closed-form expression for the average bit error rate for a one-step majority logic decoder is derived, for a regular low-density parity-check (LDPC) code ensemble and the proposed failure model. The presented analysis framework is then used to establish bounds on the one-step majority logic decoder performance under the simplified probabilistic gate-output switching model. Based on the expander property of Tanner graphs of LDPC codes, it is proven that a version of the faulty parallel bit-flipping decoder can correct a fixed fraction of channel errors in the presence of data-dependent gate failures. The results are illustrated with numerical examples of finite geometry codes.
In this paper we analyze the effect of hardware unreliability to performance of bit-flipping decoders of low-density parity-check (LDPC) codes. We apply expander arguments to show that the simple parallel bit flipping decoder, built partially from faulty gates, can correct a linear fraction of worst case channel errors, when gate failures are correlated and dependent on the switching activity of logic gates. In addition, we provide a lower bound on the guaranteed error correction of LDPC codes with left degree of at least eight.
We propose an iterative decoder made of a combination of faulty and perfect logic gates that is capable of correcting more channel errors than its counterpart made completely of perfect logic gates. We present an error probability analysis based on absorbing Markov chains, and explain how the randomness in the check node update function helps a decoder to escape to local minima associated with trapping sets. For the (155, 64) Tanner low-density parity check code, we provide a range of gate failure probabilities for which imperfect decoders perform better.
In a recent article, a technique was proposed to step up the majority logic decoding of variation set low density parity check codes. This is helpful as majority logic decoding can be implemented serially with trouble-free hardware but requires a huge decoding time. The method detect whether a word has errors in the initial iterations of majority logic decoding, and at what time there are no errors the decoding split ends without completing the rest of the iterations. While the majority words in a memory will be error-free, the average decoding time is significantly reduced. The outcome obtained proves that the technique is also effective for EG-LDPC codes. General simulation results are given to precisely estimate the prospect of error detection for different code sizes and numbers of errors.
A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.
Iterative decoders used for decoding low-density parity-check (LDPC) and moderate-density parity-check (MDPC) codes are not characterized by a deterministic decoding radius and their error rate performance is usually assessed through intensive Monte Carlo simulations. However, several applications, like code-based cryptography, need guaranteed low values of the error rate, which are infeasible to assess through simulations, thus requiring the development of theoretical models for the error rate of these codes. Some models of this type already exist, but become computationally intractable for parameters of practical interest. Other approaches approximate the code ensemble behaviour through assumptions, which may not hold true for a specific code. We propose a theoretical analysis of the error correction capability of LDPC and MDPC codes that allows deriving tight bounds on the error rate at the output of parallel bit-flipping decoders. Special attention is devoted to the case of codes with small girth. Single-iteration decoding is investigated through a rigorous approach, which does not require any assumption and results in a guaranteed error correction capability for any single code. We show an example of application of the new bound to the context of code-based cryptography, where guaranteed error rates are needed to achieve strong security levels.