Finite Alphabet Iterative Decoding
In this activity, the main motivation is to develop innovative decoding algorithms, with very low complexity, to
efficiently decode binary LDPC codes. Unlike traditional belief propagation (BP) based algorithms which propagate probabilities or log-likelihoods, the new decoders, called Finite Alphabet Iterative Decoders (FAID) propagate messages that do not represent necessarily the reliabilities as Likelihoods. In particular, FAID decoders can implement non-linear operations during the decoding process, which help to avoid the attraction of fixed points known as Trapping sets, and results in quasi-error free protection of digital data (for transmission or storage applications). More importantly and surprisingly, the quasi-error-free protection requires only a very low algorithm complexity, which translates into savings in hardware implementation, chip area, and energy consumption. Since 2013, we have conducted several studies to explore the strength of this new approach, and its possible implementation in actual products for practical applications. In particular:
- in a series of papers [hal-01742709,hal-01742708,hal-01742711], we have shown that the FAID decoders can correct many more error events than the existing classical decoders, on the binary symmetric channel. We showed this superior performance by a careful analysis of the FAID performance metrics on the so-called Trapping Sets of the LDPC codes, which are known to give rise to an error floor when decoded with classical iterative decoding. Moreover, we showed that this improved error correction capability can be implemented with very low hardware resource,
- in [hal-01742719,hal-01700293], we have further analyzed the FAID decoders. We have shown that they can be robust to transient errors when implemented in a real circuit and proposed a simplified way to implement the FAID decoders for the quantized Gaussian channel.
- This invention has led to the publication of a patent [Pat3], and the creation of a startup in 2012 (https://www.codelucida.com/ ). Decoding solutions for storage applications based on FAIDs are developed in the company. David Declercq is currently on leave at this company.
Noisy Iterative Decoding
Recently, there has been a growing interest in studying the robustness of LDPC iterative message passing decoders, with the objective of making these algorithms tolerant to faulty gates defects. The main objective which was pursued in this
activity has been to measure and predict the performance loss of iterative decoding when the algorithms are implemented with faulty hardware. A side result of our study is that faulty hardware errors, modeled as a transient additional noise in the algorithm, could indeed be beneficial instead of degrading the performance. This effect has been observed mainly in the error floor region, where deterministic decoders can be stuck by the presence of the so-called pseudo-codewords, while noisy versions of the same decoders could escape from a pseudo-codeword attraction. The impressive performance of several noisy decoders, as well as of the FAID decoders are plotted on Figure 1 for a small code. As we can see, both FAID and noisy decoders surpass the classical Belief Propagation decoder (BP), and approach maximum likelihood (MLD) when the sufficient number of iteration is assumed.
In this activity, we have followed two paths:
- We have first studied the robustness of noisy LDPC iterative decoders to hardware noise. We have in particular shown that the well-known concept of density evolution threshold can be generalized to the case of decoders implemented on faulty hardware, and we have introduced a new metric–the functional threshold–suitable to predict the asymptotic performance of noisy decoders [hal-01742717]. We have further extended this work to the powerful FAID decoders and shown that the noisy-FAID can be optimized such as to minimize the error correction loss, defined by the difference between the density evolution threshold and the functional threshold [hal-01742719].
- In collaboration with team ASTRE, we have then studied the hardware implementation of noisy versions of the gradient descent bit-flipping decoder (GDBF) for LDPC codes. Although the GDBF is known to be a simple decoder with limited error correction capability compared to more powerful soft-decision decoders, it has been shown that the introduction of a random perturbation in the decoder, named PGDBF, could greatly improve the performance results, approaching and even surpassing Belief-Propagation or Min-Sum based decoders. Efficient hardware realizations (both in FPGA and ASIC) of the PGDBF algorithm have been proposed in [hal-01700290] and [hal-01695616]. Compared to the classical MinSum decoding, the proposed PGDBF implementation offers 5 to 7 times faster throughput and requires 7 to 10 times less chip area, at the cost of some performance degradation. This makes our PGDBF decoders a competitive hard-decision LDPC decoding solution for current and future applications.
Our work on noisy iterative decoding has been supported by the FP7-ICT-STREP project i-RISC (FET-OPEN, 2013-2015), the ANR International project DIAMOND (2014-2016) and the ANR project NAND (2016-2019).
Code analysis, design and applications
We have provided a new analysis of non-binary spatially-coupled LDPC codes [hal-01709699] and quantumLDPC codes [hal-00862460]. We have proposed new codes for applications including storage in data centers,
caching for 5G, and online gaming. In particular, we have proposed new erasure codes designs:
- with a low-repair cost for data center applications, including a design of data placement and balancing protocols in distributed storage systems
- with repair scheduling for 5G wireless caching applications (2016 best student conference paper award for the IEEE ITW2015 conference paper with J. Pedersen, A. Graell-i-Amat and F. Brannstrom [hal-01262869])
Other topics investigated include network codes for routing in online video gaming and code design for block-fading transmission channels (design of protograph spatially-coupled codes of given diversity order). New code designs for optical-fiber networks are being studied within ANR project MUSICO (started Fall 2017).
A novel characterization of the Voronoi cell of linear codes with trellis representation was proposed in [hal-00863895]. It can be used to optimize codes for the coded side information (bottleneck) problem.