Multi-bit flipping algorithms with probabilistic gradient descent

Bane Vasic, Predrag Ivanis, Srdan Brkic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


A new class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel is proposed. The algorithms employ multiple bits at a variable node to represent its reliability, and multiple bits a check node to capture the sequence of its syndrome values. The check node update function thus requires a simple bit-shift operation, while the variable node updates require a nonlinear Boolean function. This class of multi-bit flipping (MBF) algorithms is enhanced by the probabilistic gradient descent (PGD) algorithm. The gradient descent algorithm minimizes the variable node energy function which, in addition to the classical term which quantifies the discrepancy between the variable estimate and channel value, also involves an additive term defined as a weighted sum of neighboring check node states. Only the variable nodes with the maximal value of energy are eligible for updating, but the updates are not done by default but probabilistically. The resulting probabilistic gradient descent multi-bit flipping PGD-MBF algorithm combined with rewinding improves the codeword probability of error while keeping the complexity lower than that of the state-of-the-art algorithms of comparable throughput.

Original languageEnglish (US)
Title of host publication2017 Information Theory and Applications Workshop, ITA 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509052936
StatePublished - Aug 30 2017
Event2017 Information Theory and Applications Workshop, ITA 2017 - San Diego, United States
Duration: Feb 12 2017Feb 17 2017

Publication series

Name2017 Information Theory and Applications Workshop, ITA 2017


Other2017 Information Theory and Applications Workshop, ITA 2017
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Software
  • Computational Theory and Mathematics


Dive into the research topics of 'Multi-bit flipping algorithms with probabilistic gradient descent'. Together they form a unique fingerprint.

Cite this