A relaxed half-stochastic decoding algorithm for LDPC codes

When considering error-correction codes for applications, the most important aspect of a coding scheme becomes the ratio of error-correction performance versus cost. This work studies the decoding of LDPC codes, and presents a new iterative decoding algorithm that represents likelihood as binary stochastic streams, but uses some elements of the sum-product algorithm in its variable node. To convert the stochastic streams to a log-likelihood ratio representation, the algorithm uses the principle of successive relaxation. Because likelihood is represented as stochastic streams, processing nodes only exchange 1 bit messages, which results in a low-complexity interleaver. Simulations show that the proposed algorithm achieves excellent error-correction performance and can outperform the floating-point sum-product algorithm.We also study the problem of error floors in LDPC codes, and the manner in which it can be addressed at the level of the decoder. After reviewing existing solutions, an alternative technique for lowering error floors is presented. The technique, called redecoding, relies on the randomized progress of a decoding algorithm to successfully decode problematic frames. Simulation of one code shows that redecoding removes the floor at least down to a bit error rate of 10^-12.Lorsque des codes de correction d'erreur sont utilisés dans des applications, le ratio entre la performance de correction d'erreur et le coût devient l'aspect le plus important du système. La présente thèse se penche sur le décodage des codes LDPC, et présente un nouvel algorithme itératif de décodage qui utilise des chaînes stochastiques binaires pour représenter les probabilités tout en incorporant des éléments de l'algorithme somme-produit dans les noeuds de variables. Le principe de relaxation séquentielle est utilisé pour convertir les chaînes stochastiques `a des valeurs discrètes "LLR". Du fait de la représentation des probabilités sous forme de chaînes stochastiques, les messages échangés entre les noeuds ont un seul bit, ce qui permet de diminuer la complexité de la distribution des messages. Les simulations démontrent que l'algorithme proposé atteint une excellente performance de correction d'erreur, et qu'il peut surpasser l'algorithme somme-produit en virgule flottante. La thèse étudie également le problème des planchers d'erreur relié aux codes LDPC et se penche sur des solutions potentielles au niveau de l'algorithme de décodage. Après avoir passé en revue certaines solutions existantes, une méthode alternative qui permet d'abaisser le plancher d'erreur est présentée. La méthode, baptisée redécodage, tire avantage de la progression aléatoire de l'algorithme de décodage. Les simulations effectuées sur un code démontrent que le redécodage élimine le plancher d'erreur au moins jusqu'à un taux d'erreur par bit de 10^−12