>>

Codage correcteur d’erreurs

Mots-clés:

codes LDPC non-binaires, décodeurs itératifs, belief propagation, décodage source-canal conjoint, stockage distribué

Description

Décodeurs LDPC à très faible complexité

L'objectif de cette activité est de développer des algorithmes de construction de codes LDPC binaires et non-binaires et les décodeurs associés, à la fois d’un point de vue théorique, mais également du point de vue de leur application pratique dans les systèmes et normes de communication actuels. Une part importante de cette activité consiste à proposer des méthodes originales de décodage à complexité réduite de ces codes.
En particulier, notre équipe a une forte expertise internationale dans le domaine des codes LDPC non-binaires et de leurs algorithmes de décodage itératifs. Les codes LDPC non-binaires ont été identifiés comme l’une des technologies de correction d’erreur les plus prometteuses pour le développement des futures générations de systèmes de communication et de stockage. En effet, les codes LDPC non-binaires montrent des performances de loin supérieures aux codes de Reed-Solomon, qui constituent la classe de codes non-binaires la plus employée dans les produits de haute-technologie d’information actuels.

 

 

Capacité de correction des décodeurs itératifs sur les Trapping Sets dominants d’un code LDPC binaire.

files/site-etis/images/ici/Communications/Codage_Correcteur/StoppingSets.png

 

Solutions approchées de problèmes complexes par inférence probabiliste itérative

Cette activité porte sur la simplification de problèmes complexes de théorie du codage et de traitement du signal, grâce à l’étude des comportements dynamiques des algorithmes itératifs du type BP (Belief Propagation), couplé à la théorie des graphes. Cela permet de proposer des nouveaux algorithmes très efficaces pour des problèmes non-polynomiaux qui sont difficiles à résoudre avec les moyens de calculs actuels, à savoir:

  • l’estimation du spectre des distances d’un code linéaire,
  • la prédiction de très faibles taux d’erreur bloc.

 

Décodage Source/Canal conjoint

Cette activité traite de l’optimisation des algorithmes de constructions de codes source-canal conjoints, et en particulier des codes correcteurs à longueur variable (VLEC).
Le principe de séparation entre les codage de source et de canal de Shannon implique que le traitement séparé de ces deux problèmes est optimal sous certaines conditions asymptotiques. Cependant, pour des applications pratiques incluant des contraintes de délai et de complexité, il peut être bénéfique de traiter conjointement le codage de source et de canal (et leur décodages).
En collaboration avec le laboratoire LSS d'Orsay, nous développons des outils et algorithmes avancés pour le calcul des spectres de distance de ces codes conjoints.

 

Codage pour les réseaux de stockage distribué

Le stockage distribué de l’information sur des réseaux de mémoires est un des domaines de recherche les plus actifs de nos jours. Les raisons sont les suivantes :

  • les solutions utilisées actuellement dans les réseaux de stockage utilisent des codes algébriques, comme les codes de Reed-Solomon, et ont atteint leur limites en terme d’efficacité,
  • de nouveaux réseaux de stockage, plus puissants et efficaces voient le jour, pour lesquels les limites de correction ne sont pas connus, de même que des algorithmes pratiques pour leur traitement.

Dans le cas des data-center actuels comprenant un grand nombre de disques durs, la technologie RAID6 est sous-optimale, principalement en raison de la complexité de décodage des codes de Reed-Solomon de grande taille. Nous avons donc proposé de remplacer ces codes par des codes LDPC, qui améliorent grandement les performances. De plus, nous proposons une simplification du protocole d’accès des données. Nous évaluons les solutions proposées au travers des métriques suivantes:

  • mise-à-jour de données déjà présentes sur le réseau,
  • équilibrage de la charge de stockage sur les différents disques,
  • allocation optimale des ressources de stockage dans le cas d’utilisateurs à accès limités

files/site-etis/images/ici/Communications/Codage_Correcteur/network-storage-model.png

Participants :

  • Permanents : David Declercq, Charly Poulliat, Iryna Andriyanova, Sylvain Reynal, Claudio Weidmann.

  • Membre associé : Marc Fossorier.

  • Doctorants/Temporaires : Auguste Venkiah (2008), Shahkar Kakakhail (2010), Bilal Shams (2010), Pham Sy Lam (2012), Mattheo Gorglione (2012), Ludovic Danjean (2012), Shiva Planjery (2012), Erbao Li (2012), A.Diallo (2012), Jean-Christophe Sibel (2013), Alan Julé, Madiagne Diouf, Christiane Kameni-Ngassa.

Collaborations majeures :

  • Nationales: M. Kieffer (LSS), V. Savin (CEA-LETI)

  • Internationales: B. Vasic (Tucson, USA), F. Herrero (Valencia, Espagne).