Compte rendu de la journée GDR-ISIS sur les LDPC
19 décembre 2002
Organisateur : Emmanuel Boutillon
LESTER, Université de Bretagne Sud
Thématique de la journée :
Les codes correcteurs d'erreur Low Density Parity Check Code (LDPC) se posent actuellement comme une alternative aux Turbo-Codes pour les futures générations de systèmes de transmissions.
D'un point de vu performance théoriquement, les LDPC sont actuellement les plus proches de la limite de Shannon. Par contre, ils sont réputés plus complexe à décoder.
L'objectif de cette journée est de réunir une première fois la communauté en France qui travaille sur les LDPC, tant du point de vu construction et performances théoriques que du point de vu réalisation matérielle.
Programme de la journée :
10h-11 h : Juntan Zhang et Marc Fossorier (Universite d'Hawaii):, Présenté par Marc Fossorier
Methode d'acceleration de la convergence du decodage des codes LDPC.
Résumé : In this presentation, we propose a shuffled version of the belief propagation (BP) algorithm for the decoding of low-density parity-check (LDPC) codes. We show that when the Tanner graph of the code is acyclic and connected, the proposed scheme is optimal in the sense of MAP decoding and converges faster (or at least no slower) than the standard BP algorithm. Interestingly, this new version keeps the computational advantages of the forward-backward implementations of BP decoding. Both serial and parallel implementations are considered. We show by simulation that the new schedule offers a speedup factor close to two for the same error performance and decoding complexity.
Slides
11h – 12h : Giuseppe Caire (Eurecom)
Some applications of LDPC codes in hybrid ARQ systems
Résumé : LDPC codes under iterative decoding can achieve the capacity of the binary-erasure channel and offer extremely good performance limits (for large block length) on several other binary-input symmetric output channels such as the BSC and the BI-AWGN channel. In this talk we investigate the application of LDPC codes to non-standard settings. We shall consider a block-fading BI-AWGN channel and show that, in the limit for large block length, standard LDPC codes optimized for the BI-AWGN channel used as building blocks of a hybrid ARQ coding system attain an average throughput very close to the theoretical optimum. We shall discuss also some effective countermeasures to takle the performance degradation due to practical finite-length codes.
Slides
12h-12h30 : Emmanuel Boutillon (Université de Bretagne Sud)
Code "Médium Density Parity Check Code (MDPC)" : un code externe efficace pour supprimer le flatening des Turbo-Codes.
Résumé : Les Turbo-Codes sont des codes correcteurs d’erreurs très efficace mais, à fort rendement, la courbe taux d’erreur binaire comme fonction du SNR subit une rupture de pente (le " flatening). Nous proposons d’utiliser des codes LDPC à moyenne densité (d’ou le nom de code MDPC, M pour Medium) et très fort rendement comme code externe au Turbo-Code. L’idée est que la grande majorité des bits en sortie du Turbo-décodeur ayant une forte fiabilité sont décodés correctement. La suppression de ces bits permet de remplacer le code MDPC par un code LDPC à faible rendement : les erreurs résiduelles peuvent alors être corrigées efficacement.
Nous présentons une méthode pragmatique de décodage et nous comparons les résultats obtenus par rapport à un code externe classique utilisant un code de Reed-Solomon : pour des gains de correction équivalent, les codes externes MDPC proposés utilisent deux fois moins de redondance que les codes externes Reed-Solomon.
Slides
12h30-14h : Repas
14h-14h45 : Jinghu Chen et Marc Fossorier (Universite d'Hawaii):
Optimisation des decodeurs SUB-LOG-MAP pour les codes LDPC
Résumé : In this presentation, we investigate reduced complexity iterative decoding algorithms of the belief propagation (BP) algorithm for low density parity check (LDPC) codes. We particularly discuss the normalized BP-based algorithm and the offset BP-based algorithm, which can achieve performances very close to that of BP decoding with one properly selected decoder parameter introduced in the BP-based (or min-sum) decoding algorithm. Criteria to determine this optimal decoder parameter are presented and the corresponding error performances are compared for different families of LDPC codes. Finally, the quantized version of this approach is presented.
Slides
14h45-15h15 : Frédéric Guilloud (ENST Paris) :
Implémentation de LDPC sur FPGA : optimisation de l'architecture et étude de précision finie.
Si les aspects théoriques des codes LDPC sont relativement bien étudiés, peu de travaux traitent des problèmes d’intégrations matérielles de cette famille de code. Dans cette présentation, nous proposons deux approches originales pour l’implémentation des LDPC.
- Au niveau du calcul des parités, nous proposons une méthode de calcul série sous optimale de calcul des informations extrinsèques permettant un ensemble de compromis " performances-complexité ". Les simulations montrent que le schéma proposé est particulièrement efficace dans le cas des codes LDPC irréguliers.
- Au niveau architecture, nous proposons de concevoir d’abord un décodeur permettant d’utiliser un parallélisme partiel, et ensuite, de construire des codes contraints par cette architecture (méthodologie " decodeur first design "). L’architecture proposé est mixte (parallèle / série) ce qui permet de traiter efficacement les codes LDPC irrégulier.
Enfin, les problèmes d’implémentation en précision finie sont abordés.
Slides15h14-16h : François Verdier et David Declercq (ENSEA Cercy Pontoise)
Quelques aspects de l'implantation matérielle des décodeurs LDPC"
Présenté par François Verdier
Résumé : Cette présentation sera axée principalement sur les problèmes liés à la réalisation matérielle des décodeurs LDPC sur des codes de grande taille. En premier lieu, nous présenterons une certaine classe de codes LDPC réguliers qui ont l'avantage d'avoir une réalisation matérielle efficace (en termes de temps de décodage comme en occupation silicium / mémoire) : les codes congruents. En particulier, cette classe de codes autorise une implantation parallèle efficace sans perte importante de performance. Nous présenterons ensuite les caractéristiques d'une architecture FPGA parallèle réalisant le décodage de cette classe de codes. Cette architecture est peu coûteuse en réseau de communication et permet un gain sur la vitesse de décodage directement proportionnel à la quantité de resources disponibles. Elle permettra notamment l'implantation matérielle (en temps raisonnable) de codes de grande taille. Nous aborderons enfin l'effet de la réduction de précision imposée par la réalisation matérielle sur les performances de la classe de codes envisagée.
SlidesParticipants :
Un total de 21 personnes ont assisté à cette journée.