>>

Soutenance de thèse : Erbao Li

Titre de la thèse

Décodeurs Haute Performance et Faible Complexité pour les codes LDPC Binaires et Non-Binaires.
High Performance and Low Complexity Decoders for Binary and Non-Binary LDPC Codes.

Date et lieu de soutenance

Mercredi 19 décembre 2012, 10h30.
ENSEA, salle du Conseil.

Résumé

Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteur d'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliser des décodeurs de complexité faibles et de faible latence tout en garantissant de bonne performances dans la région des très faibles taux d'erreur (error floor). Dans la première partie de cette thèse, nous étudions des décodeurs itératifs sur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont été récemment proposés dans la littérature. En utilisant un grand nombre de décodeurs FAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité de corrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique. La diversité des décodeurs permet de garantir une correction d'erreur minimale sous décodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnons dans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrige tous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petite taille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènements d'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger. Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques et nous analysons les comportements de ces décodeurs sur des évènements d'erreur les plus problématiques. En nous basant sur l'observation des trajectoires périodiques pour ces cas d'étude, nous proposons un algorithme qui combine la diversité du décodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nous montrons par simulations que cette technique permet de s'approcher des performances d'un décodage optimal au sens du maximum de vraisemblance, et ce pour plusieurs codes. Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithme de décodage à complexité réduite pour les codes LDPC non-binaires. Nous avons appellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domaine de message en un domaine appelée domaine delta, nous sommes capable de choisir les déviations ligne par ligne par rapport à la configuration la plus fiable, tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviations colonne par colonne. Cette technique de sélection des déviations ligne par ligne nous permet de réduire la complexité du décodage sans perte de performance par rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoud le problème de latence des décodeurs existants. La colonne supplémentaire permet de calculer tous les messages extrinséque en parallèle, avec une implémentation matérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architectures matérielles parallèle que les architectures matérielles série pour l'exécution de notre algorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS est particulièrement adapté pour les codes LDPC non-binaires sur des corps finis de Galois de petite et moyenne dimensions.

This thesis is dedicated to the study of iterative decoders, both for binary and non-binary low density parity check (LDPC) codes. The objective is to design low complexity and low latency decoders which have good performance in the error floor region. In the first part of the thesis, we study the recently introduced finite alphabet iterative decoders (FAIDs). Using the large number of FAIDs, we propose a decoding diversity algorithm to improve the error correction capability for binary LDPC codes with variable node degree 3 over binary symmetric channel. The decoder diversity framework allows to solve the problem of guaranteed error correction with iterative decoding, beyond the pseudo-distance of the LDPC codes. We give a detailed example of a set of FAIDs which corrects all error patterns of weight 7 or less on a (N=155,K=64,Dmin=20) short structured LDPC, while traditional decoders (BP, min-sum) fail on 5-error patterns. Then by viewing the FAIDs as dynamic systems, we analyze the behaviors of FAID decoders on chosen problematic error patterns. Based on the observation of approximate periodic trajectories for the most harmful error patterns, we propose an algorithm which combines decoding diversity with random jumps in the state-space of the iterative decoder. We show by simulations that this technique can approach the performance of Maximum Likelihood Decoding for several codes. In the second part of the thesis, we propose a new complexity-reduced decoding algorithm for non-binary LDPC codes called trellis extended min sum (T-EMS). By transforming the message domain to the so-called delta domain, we are able to choose row-wise deviations from the most reliable configuration, while usual EMS-like decoders choose the deviations column-wise. This feature of selecting the deviations row-wise enables us to reduce the decoding complexity without any performance loss compared to EMS. We also propose to add an extra column to the trellis representation of the messages, which solves the latency issue of existing decoders. The extra column allows to compute all extrinsic messages in parallel, with a proper hardware implementation. Both the parallel and the serial hardware architectures for T-EMS are discussed. The complexity analysis shows that the T-EMS is especially suitable for high rate non-binary LDPC codes on small and moderate fields.

Composition du jury

  • Charly POULLIAT, Professeur, INP-ENSEEIHT, Examinateur
  • Christophe JEGO, Professeur, Laboratoire IMS - IPB/ENSEIRB-MATMECA, Rapporteur
  • Emmanuel BOUTILLON, Professeur, Lab-STICC - Université Bretagne Sud, Rapporteur
  • Valentin SAVIN, Professeur, CEA-LETI, MINATEC Campus, Examinateur
  • David DECLERCQ, Professeur, ETIS ENSEA/UCP/CNRS, Directeur de thèse

Retour