Probabilistic Gradient Descent Bit-Flipping Decoders for Flash Memory Channels

Fakhreddine Ghaffari, Bane Vasic

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

4 Scopus citations


Low-density parity check (LDPC) codes are an attractive error correction scheme for ensuring data integrity in new generation of NAND flash memories. A quick assessment of the iterative decoders for LDPC codes reveals a wide range of varying complexities. The simple Bit-Flipping (BF) and binary-message-passing algorithms such as the Gallager A/B algorithms occupy one end of the spectrum, while Belief Propagation (BP) and A Posteriori Probability (APP) decoders lie at the other end. The gamut of existing decoders filling the intermediate space can simply be understood as the implementation of BP (and its variants, such as the min-sum algorithm) at different levels of message precision. Decoders with low-precision messages are desirable because of their low complexity and power efficiency, but in such decoders it is highly nontrivial to prevent performance degradation known to as error floor and to guarantee fast convergence to a codeword. In this paper we present our results on a new class of low-complexity iterative decoders for flash memory channels. They involve two main innovations: global computation and randomness. Our decoding algorithm, Probabilistic Gradient Descent Bit-Flipping (PGDBF) is motivated by the analogy between Tanner graphs and the graphical models used in statistical mechanics, and prescribe a rule for flipping a bit based on the so-called energy function and a binary random sequence associated to that bit. Energy function is computationally simple, but involves all the bits. We present the PGDBF algorithm analysis, explain how it benefits from global computation and randomness, and present the hardware synthesis results as well as comparisons with the state-of-the-art decoders.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538648810
StatePublished - Apr 26 2018
Event2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Florence, Italy
Duration: May 27 2018May 30 2018

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems
ISSN (Print)0271-4310


Other2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018


  • Low-Density Parity-Check
  • NAND Flash Memory
  • Probabilistic Gradient Descent Bit Flipping
  • high decoding throughput
  • low-complexity FPGA implementation

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Probabilistic Gradient Descent Bit-Flipping Decoders for Flash Memory Channels'. Together they form a unique fingerprint.

Cite this