PhD proposal: Noise against Noise LDPC Decoder
Title : Noise against Noise LDPC Decoder
In natural science, noise is sometime recognized as a source of innovation and improvement (erroneous copy of DNA, random sparking of neurons, eyes micro-saccades). In operational research, noise is used to find a good solution to a complex optimization problem (simulating annealing, tabu search, genetic algorithm). In the signal processing community, the idea to use noise to resolve some particular detection and estimation problems is rather old (one bit analog-digital conversion, detectability improved by noise detection, stochastic resonance). In spite of its great potential, “noised aided signal processing” is not yet widely studied and used.
Recently, several scientists have tackled the performance evaluation of iterative decoders in stochastic architectures (in the next generation of integrated circuits with transistor size below 40 nm, every single gate can temporarily output a wrong value due to transient defects). One of the first proposed trend has been to evaluate, both theoretically and practically, the performance degradation induced by a stochastic architecture [Ngassa2015], then using wisely the redundancy to reduce the negative effects introduced by the transistor noise [Tang2013]. Through these research endeavors, an unexpected spin-off was identified: the noise inside the decoders is not necessarily an enemy to combat, but it can be used as an ally. Indeed, recent works have shown that the controlled injection of noise in an iterative error control decoder can significantly enhance the error correction performance, and thus, contribute to mitigate the effect of the transmission channel perturbations [Ngassa2015, Sundararajan2014]. In other words, and even if it may appear as a paradox at first glance, noise in an iterative decoder can help to combat the channel noise!
This new and disruptive concept is based on the following explanation. Iterative decoding of LDPC codes has strong theoretical justification that come from the application of optimal local Bayesian inference on sparse graphs (Belief Propagation principle). The theoretical results from Bayesian inference show the optimality only when the codeword length tends to infinity. When we deal with practical applications, finite-length code constructions lower the expected performance of iterative decoders. This is mainly due to the existence of an early error floor (abrupt change of slope in the error curve), that comes from oscillation behaviors of the iterative LDPC decoders. These oscillations come from the presence of local minima of the decoder which makes the decoder output a pseudo-codeword (of no interest for the application), instead of the correct codeword. Contrary to the intuition that stochastic hardware would always degrade the error correction performance, it was observed that randomness in the decoder can help to escape from the local minima, and therefore improve the error correction performance.
The PhD candidate will have to focus on the investigation of LDPC decoders which are already proposed and implemented in many practical applications and industrial products, i.e. the quantized Min-Sum (MS) algorithm. He will restrict the study on quantized MS decoders with small message alphabets constructed from typically 3 or 4 quantization bits. He will explore the potential gains of using noise on both the waterfall and the error floor regions by introducing random perturbations in the decoder. Since most of the existing results have been obtained from Monte-Carlo simulations so far, he will have to explore theoretical aspects of this technique in order to (i) develop theoretical tools to predict the performance of noisy decoders, both in the waterfall and in the error floor, (ii) use these tools to provide a more systematic analysis of the effect of noise in the quantized MS decoder, (iii) and finally design strong quantized MS decoders that rely on noise to obtain good waterfall and error floor performance. The techniques developed for LDPC decoders could also be applied to analyze the effect of noise on Turbo-Decoders.
The PhD will be funded the French ANR in the frame of the project NAND (2016-2018) that regroups academics (ETIS lab in ENSEA, Lab-STIC in Université de Bretagne Sud and IMS lab in Université de Bordeaux) and companies (Turbo-Concept, ST microelectronics and Thales). The PhD will have two supervisors: professor David Declercq (from ETIS Lab, Cergy-Pontoise) and professeur Emmanuel Boutillon (Lab-STICC Lab, Lorient). Professor Chris Winstead, from Utah State University will also tightly participate to the project.
The candidate should be fluent in English and willing to learn French. He will have a solid background in mathematics, information theory and coding theor. Knowledge in hardware implementation (FPGA or ASIC) would be also greatly appreciate.
The PhD will start in January 2016 for a period of 3 years. The net salary (with social insurance) is around 1350 euros/month.
Applications should be sent to the following contacts before Friday, November 13th, 2015.
- Emmanuel Boutillon (Emmanuel.email@example.com)
- David Declercq (firstname.lastname@example.org)
[Ngassa15] Ngassa, C.K.; Savin, V.; Dupraz, E.; Declercq, D., “Density Evolution and Functional Threshold for the Noisy Min-Sum Decoder,” IEEE Transactions on Communications, vol. 63, No 5, pp. 1497 – 1509, May 2015.
[Sundararajan2014] Sundararajan, G.; Winstead, C.; Boutillon, E., "Noisy Gradient Descent Bit-Flip Decoding for LDPC Codes," IEEE Transactions on Communications, vol. 62, No 10, pp. 3385 - 3400, October 2014.
[Tang2013]Tang Y.; Boutillon, E.; Winstead, C.; Jego, C.; Jezequel, M., "Muller C-element based Decoder (MCD): A decoder against transient faults," IEEE Int. Symp. on Circuits and Systems (ISCAS), pp.1680-83, May 2013