Dr. Winstead delivered a presentation at Bretagne Telecom, titled "Recent results on bit-flipping LDPC decoders." The slides and associated article links are available at the bottom of this announcement. This presentation offered a summary of our work on the Noisy Gradient Descent Bit Flipping (NGDBF) algorithm, which was invented by PhD student Gopal Sundar.
Abstract --- Low-density parity check (LDPC) codes are a key part of many high-performance communication standards. Thanks to sophisticated decoding algorithms, such as belief propagation and the "min-sum" method, LDPC codes are able to approach the theoretical Shannon limit in performance. These advanced algorithms, however, require resource-intensive implementations that lead to high power consumption, and make them unsuitable for some applications. An alternative family of algorithms, collectively termed "bit-flipping" methods, perform decoding by exchanging single-bit messages, which gives them very low complexity. Although bit-flipping algorithms have been known for some time, they have had limited application due to their comparatively poor performance. Researchers recently began to develop new types of bit-flipping algorithms that achieve superior performance while maintaining low complexity. This presentation offers a review of bit-flipping algorithms and their applications. We consider various decoding algorithms and their possible application to communication systems, solid-state memories and fault-tolerant computing. The presentation will conclude with a discussion of a recently developed bit-flipping algorithm, known as "Noisy Gradient Descent Bit Flipping" (NGDBF), which has performance close to the advanced min-sum algorithm, while maintaining low complexity similar to earlier bit-flipping methods. Possible implementation architectures are examined. The algorithm's tolerance to internal faults is discussed, and we conclude with a discussion of open research problems related to the NGDBF algorithm.
Readers interested in this presentation may wish to read these related articles and presentations:
- Gopalakrishnan Sundararajan, Chris Winstead and Emmanuel Boutillon, "Noisy Gradient Descent Bit-Flip Decoding for LDPC Codes," arXiv:1402.2773.
- Chris Winstead and Christian Schlegel, "Energy Limits of Message-Passing Error Control Decoders," IZS 2014, available here or in the IZS proceedings.
- Chris Winstead, Gopalakrishnan Sundararajan and Emmanuel Boutillon, "A Case Study in Noise Enhanced Computing: Noisy Gradient Descent Bit Flip Decoding," presented at York Workshop on Designing with Uncertainty, 2014. Abstract and Poster available here.
Additional bibliography and article links are provided in the slides attached below.