Two-bit bit flipping algorithms for LDPC codes and collective error correction

Dung Viet Nguyen, Bane Vasić

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


A new class of bit flipping algorithms for lowdensity parity-check codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

Original languageEnglish (US)
Article number6750416
Pages (from-to)1153-1163
Number of pages11
JournalIEEE Transactions on Communications
Issue number4
StatePublished - Apr 2014


  • Bit flipping algorithms
  • error floor
  • low-density parity-check codes
  • trapping set

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Two-bit bit flipping algorithms for LDPC codes and collective error correction'. Together they form a unique fingerprint.

Cite this