FR 2894738 A1 20070615 FR 0512496 A 20051209 /12 Brevet LDPC Méthode et appareil de réduction de complexité de décodage parallèle des codes LDPC (Low Density Parity Check Code) Name Date Inventeurs Nicolas FAU 7 Déc 2005 François HAMON Demandeurs R-Interface S.A.R.L. PLAN PLAN 2 LISTE DES ILLUSTRATIONS ERROR! BOOKMARK NOT DEFINED. ENVIRONNEMENT DE L'INVENTION 3 HISTORIQUE ERROR! BOOKMARK NOT DEFINED. NOTATIONS ET DÉFINITIONS 6 BIBLIOGRAPHIE 12 ETAT DE L'ART 7 DESCRIPTION DE L'INVENTION 8 REVENDICATIONS 11 2/12 /12 ENVIRONNEMENT DE L'INVENTION Le décodage canal consiste à utiliser la redondance et la corrélation du signal émis pour auto corriger d'éventuelles erreurs de transmission. Le groupe de techniques considéré concerne les systèmes de décodages itératifs dits techniques turbo. La complexité de la solution optimale au problème consistant à retrouver un message noyé dans le bruit augmente exponentiellement avec la taille du système. Les solutions dites turbo permettent de générer une complexité qui n'augmente que linéairement avec la taille du système. Les turbo codes découvert par Claude Berrou [2] sont considérés comme l'avancée la plus significative de ces vingt dernières années dans le monde des communications numériques. Ils ont été récemment introduits dans de nombreux standards (UMTS, 802.16, DVB-RCS, DVB-RCT). Aujourd'hui de nouvelles solutions itératives associées à la classe de code LDPC (Low Density Parity Check) permettent de diminuer la complexité numérique et d'améliorer les performances de ces techniques turbo. Les code LDPC sont des codes en bloc linéaires, ils furent introduits par Gallager en 1962 [3] et redécouverts récemment par MacKay[4]. Les progrès en microélectronique permettent aujourd'hui de les mettre en oeuvre. Ils sont largement pressentis pour des futurs standards de télécommunication tels que le nouveau standard de diffusion vidéo par satellite (DVBS-2), le MBWA (Mobile BroadBand Wireless Access), le standard IEEE 802.11n. Ils sont proposés par le Jet Propulsion Laboratory au CCSDS (Consultative Committee for Space Data System) ainsi que dans le standard 10 Gbps Ethernet. Et enfin, l'industrie du stockage des données a montré un vif intérêt pour l'intégration de ces techniques dans les futures générations de systèmes de stockage. Le DVB-S2 est une version avancée du standard DVB-S dont l'objectif est d'améliorer l'efficacité spectrale de la diffusion de la télévision par satellite. Le code LDPC utilisé dans ce standard est une des composantes contribuant au gain d'efficacité spectrale. L'information publique concernant ce standard est disponible sur: "http:l/www. d vb. org/" Le standard IEEE 802.an (10GBASE-T) est un standard émergent pour opérer le 10 Gbps Ethernet sur des paires de cuivre torsadées. Le code correcteur d'erreur LDPC proposé pour ce standard permet d'approcher la limite théorique de transmission sur un câble de longueur jusqu'à 100 mètres. L'information publique concernant ce standard est disponible sur: "http://www.ieee802.org/3/an/" Le standard IEEE 802.11n est le successeur du standard WLAN 802.11g . L'objectif est, au minimum, de doubler les capacités actuelles et, au maximum, d'atteindre les 500 Mbit/s. Le code LDPC utilisé dans ce standard est une des composantes contribuant au gain de performance. L'information publique concernant ce standard est disponible sur: http://www.wwise.org/ Le standard émergent MBWA (Mobile Broadband Wireless Access) ( 45 /12 Les codes LDPC sont définis comme l'espace nul d'une matrice de parité H qui a les propriétés suivantes : 1. chaque ligne de la matrice a un poids de (relatif à la régularité du code) 2. chaque colonne de la matrice a un poids ds (relatif à la régularité du code) 3. le nombre de 1s en commun entre deux colonnes est inférieur ou égale à 1 (relatif à la taille minimal des cycles) 4. de et ds sont petits comparés à la taille du code et au nombre de lignes (relatif à la densité). Le décodage souple itératif des codes LDPC peut être implémenter de différentes manières incluant l'algorithme BP (Beleif Propagation) , l'algorithme SP (Sum Product) ou l'algorithme MP (Message Passing). II existe cependant de la place pour de nombreuses variantes de ces algorithmes permettant soit d'améliorer les performances soit de réduire la complexité. Ces variantes peuvent intervenir sur des approximations mathématiques, sur le séquencement, le cadencement et l'ordonnancement des sous fonctions, ainsi que sur l'organisation mémoire. Le décodage optimal des codes LDPC met en oeuvre un algorithme itératif qui propage les informations extrinsèques et les informations à priori dans le graphe bipartite reliant les variables aux équations de parité. On considère ici une version du décodage à propagation de croyance qu'on appelle le SPA (Sum Product Algorithm) [1]. 25 30 35 40 /12 NOTATIONS ET DEFINITIONS • N : Nombre de bit nodes : nombre de colonne de H • K : nombre de check nodes : nombre de ligne de H • ds : nombre de connexions sur un bit node. • dc : nombre de connexions sur un check node. • M(n) : ensemble des check nodes connectés au ne bit node (un). • N(m) : ensemble des bit nodes connectés au me check node (cm). • M(n)/k : M(n) privé du kéme check node de M(n). • N(m)/k : N(m) privé du kéme bit node de N(m). • u=[u1iu2,...,uN] : mot de code transmis. • y=[y,,y2,...,yN] : le mot reçu correspondant au mot de code u. • anù.m(x) : message envoyé par un (nième bit node) à cm (mième check node) qnù.m(x) : Pr(un=x/c;, i E M(n)/m) avec x {0,11 rm.n(x) : message envoyé par cm (mième check node) à un (nième bit node) rm_n(x) : Pr (un=x/u;, E N(n)/m) avec x I {0,1} Par définition, le logarithme du rapport de vraisemblance LLR s'écrit : L(u)=log( P(u=0)/P(u=1)) On définit aussi les logarithmes des rapports de vraisemblance suivant : Àn-.m(un)=1og(an-•m(0)/ g.(1)) 25 nm-.n(un)= log(rn-.m(0)/ rn-.m(1)) 30 ETAT DE L'ART La PLANCHE1 représente une chaîne de communication faisant intervenir un codeur LDPC, une fonction de modulation pour la mise en forme du signal, un canal de propagation, une fonction de démodulation et la fonction de décodage LDPC. Les codes LDPC sont représentés par leur matrice de parité ou de manière équivalente par le graphe bipartite comme on peut le voir sur la PLANCHE2. Cette dernière représentation introduite par R. M. Tanner en 1981 [5], est un graphe qui structure les équations de parité définissant le code. C'est la structure de la matrice de décodage qui définit le caractère LDPC du code. Contrairement aux codes classiques qui sont définis par leur matrice ou leur polynôme générateur les codes LDPC sont définit par leur matrice de parité. La PLANCHE2 illustre la représentation en graphe des codes LDPC à partir d'une matrice de parité H donnée. Le décodage optimal des codes LDPC est une fonction complexe. Pour des applications à débits importants il est nécessaire de définir des solutions de décodage sous optimales adaptées à des implémentations parallèles ou pipelines. Ceci fait l'objet de l'invention présentée ici. La fonction de décodage LDPC peut être décomposée selon les sous fonctions décrites sur la PLANCHES. La sous fonction (31) représente le check node unit , la sous fonction (32) représente le memory controller et la sous fonction (33) représente le bit node unit . La présente invention intervient sur une amélioration de l'implémentation de la sous fonction check node unit , et sur une amélioration du passage des messages entre les sous fonctions check node unit et bit node unit La fonction CheckNodeUnit peut être implémentée de manière parallèle selon la méthode proposée par [1]. Cette méthode représente l'état de l'art des implémentations parallèles de l'algorithme de décodage Sum Product . L'algorithme de décodage SPA exposé en [1] calcul le LLR ( Log Likelyhood Ratio). Par définition, le logarithme du rapport de vraisemblance LLR s'écrit : L(u)=log( P(u=0)/P(u=1)). On calcule la probabilité qu'un bit dans un mot reçu soit un 1 sachant qu'on a effectivement transmis un 1. On calcule la probabilité que ce bit soit un 0 sachant qu'on a effectivement transmis un 0. Le LLR est le logarithme du ratio de ces deux grandeurs calculées. Le passage au logarithme permet de simplifier les calculs. L'état de l'art de l'implémentation parallèle de l'algorithme SP est le suivant: de On définie une variable binaire auxiliaire Sm = C+ un, i=1 Le calcul du LLR(Sm) est assez simple puisqu'on dispose de toutes les uni. Ceci étant, on commence par calculer nm->ni(uni). On a: dc dc L(Sm)=L( I~+ uni )=L(uni C) (D uni ), avec 1=l l=>>J~i L (U +OV)= sign[L(U)].sign[L(V)].min[IL(U)l,IL(V)l] +log ( 1 + eIL(u)+L(" )-log ( 1 + e-IL(u)-L(v)l ) En utilisant la formule démontrée dans [1], on peut écrire que de 1 + exp(L( O+ uni )) L(Sm)=log( de i=1,1+ ) exp(L( O+ uni )) + exp(L(un; )) J=>>J~i 7/12 /12 de Le terme L( E 0+ uni) est le message Am_n;(un;) que le check node m envoie à tout les bit nodes un; lorsqu'il i=l,i$i reçoit L(un,) qui n'est entre autre que Anj .m(un;). Donc, l'équation précédente est équivalente à L(Sm)=1o9( 1 + exp( A m,ni (uni) + lni >m (uni )) ) exp( A,n,ni (uni )) + exp( (uni )) ou encore Am_n;(un;)=log exp(/Iniù>m (uni ) + L(Sm )) ù 1 ù L(Sm ) .= L (Uni*Sm) exp(~ni ~m (uni ) ù L(Sm )) ù 1 On définie la loi * telle que: Amù.ni(Uni)=L(Uni* Sm) i=1,...,dc. Le calcul de cette derniere expression necessite l'utilisation de look up table memorisant les valeurs 10 echantillonnées de la fonction h(x)=loglex-1 . Dans l'état de l'art de l'implémentation parallèle de l'algorithme SP les sous fonctions L (U+V) et L (U*V) sont organisées comme sur la PLANCHE4. DESCRIPTION DE L'INVENTION 15 La présente invention propose entre autre une nouvelle implémentation parallèle du CNU(31) qui permet de réduire la complexité et d'augmenter le parallélisme. Ci dessous le détail de la première partie de l'invention. Nous revendiquons l'architecture de la fonction CNU(31) telle que décrite sur la PLANCHE 5. La fonction 20 CNU(31) est composée des sous fonctions RENDER( 51) , PIPE(52) et OUTER(53). La fonction CNU(31) prend en entrée les dc Lambdas qui sont les messages provenant des dc bit nodes connectés au check node considéré. La fonction CNU(31) sort les dc Gamma selon la règle suivante: gamma(i-4,0)=Sign(lambda(i-3,1).lambda(i-3,2).lambda(i-3,3).lambda(i-3,4)) . Min(abs(lambda(i-3,1)), 25 abs(lambda(i-3,2)), abs(lambda(i-3,3)), abs(lambda(i-3,4))) Cette règle est définie dans l'état de l'art comme le SIGN_MIN. Nous revendiquons l'architecture en arbre décrite sur la PLANCHE5 qui permet d'implémenter avec le maximum 30 de parallélisme la règle SIGN_MIN de dc combinaison de (dc-1) lambdas quelle que soit la valeur de dc. Que cette valeur de dc soit une puissance de 2 ou non et que cette valeur de dc soit constante d'un check node à un autre. Ainsi cette technique permet aussi de traiter des matrices irrégulières. Nous revendiquons l'architecture en pipeline décrite sur la PLANCHE5 qui permet de délivrer les gammas correspondant à un check node à chaque cycle d'horloge avec une latence de log(dc)+1 cycles. Cette 35 architecture permet donc le calcul de K check nodes en K+log(dc)+1 cycles. Cette architecture est basée sur la définition des sous fonctions PIPE(50), RENDER(51), OUTER(52) et SIGN(53) décrites sur les PLANCHE6 et PLANCHE7. /12 Nous revendiquons la définition et l'implémentation de la sous fonction RENDER(51) décrite sur la PLANCHE7 qui est à la base de l'amélioration de l'implémentation de la règle SIGN_MIN. La deuxième partie de l'invention concerne une amélioration du passage des messages entre les sous fonctions check node unit (31) et bit node unit (33) comme décrit sur la PLANCHE3. La présente invention propose un nouvel ordonnencement du passage des messages entre le BNU (33) et le CNU (31), qui permet de réduire la ressource en silicium et d'augmenter la cadence de traitement de l'unité de traitement élémentaire du décodeur de signaux codés LDPC. Cette unité de traitement est représentée sur la PLANCHE3. Cette unité de traitement élémentaire est composée d'une BNU(33), d'une CNU(31), d'un MemoryController(32) et de mémoires FIFO(35) et de mémoires(34) détaillés dans les sous parties suivantes. Plusieurs unités de traitements identiques peuvent être synthétisées en série afin d'augmenter la vitesse maximale du flux d'entrée traitable par le décodeur. Chaque unité de traitement élémentaire ne réalisant alors qu'une partie des itérations nécessaires au bon fonctionnement du décodeur. Tandis que l'unité de traitement i calcule les itérations (n*(i+1)-1, n*i) du block d'entrées 0, l'unité de traitement i-1 réalise les itérations (n*i-1, n*(i-1)) du block d'entrée 1...et l'unité de traitment 0 réalise les itérations (n-1, 0) du block d'entrée i. Les inconvénients majeurs d'un tel procédé étant la multiplication des ressources mémoires et logiques nécessaires, et l'augmentation de la latence de traitement pouvant être préjudiciable pour certaines applications. Nous revendiquons l'implémentation série de plusieurs unités de traitement (BNU(33)+MemoryController(32)+CNU(31)) afin d'augmenter les capacités de traitement du décodeur. Nous revendiquons le stockage des messages gammas dans des fifos(35) circulaires permettant d'obtenir sans décodage d'adresse les constituantes Gamma nécessaires au calcul des BNU(33) en entrée des opérateurs + de la PLANCHE8. Ce stockage permet aussi de récupérer la composante une deuxième fois afin de soustraire la composante pour obtenir le message Lambda en entrée des opérateurs - de la PLANCHE8. Nous revendiquons le stockage des messages Lambda dans des espaces mémoires différents (MEMO à MEMNB(34)) de ceux des Gammas (FIFOO à FIFON(35)) permettant aux unités de traitement de fonctionner en parallèle. Ainsi le traitement de certains bit nodes peut être effectué en même temps que celui de certains check nodes. Les messages GAMMA arrivant des CNU(31) sont stockés dans des fifos de longueur ds. A chaque Bit Node (i) correspond une FIFO(35) de profondeur ds(i) (le nombre de messages constituant ce bit node). L'unité Memory Controller délivre les signaux Write correspondants afin que les messages GAMMA soient stockés dans les bonnes FIFO(35). Lorsque les gammas d'une itération sont tous stockés, le pulse VALID est envoyé par le memory controller afin de signaler à la BNU(33) qu'elle peut commencer son traitement. Les Lambda, soit le contenu d'une FIFO(35), sont insérés les uns après les autres dans le pipeline du module BNU(33) composante après composante. C'est à dire qu'au cycle i après Valid le pipeline de profondeur ds reçoit ds composantes : la composantes ds-1 du bit node i-ds-1, la composante ds-2 du bit node i-ds-2,... la composante 0 du bit node i. Durant tout le process, les composantes qui sortent des FIFO(35) sont réinsérées à mesure dans la même FIFO(35) afin ensuite de pouvoir soustraitre les même composantes pour obtenir les GAMMAS. On a donc à partir du cycle ds après VALID, la SOMME des composantes d'un BitNode mise à jour. Une nouvelle somme étant ensuite obtenue à chaque cycle. Ces sommes sont stockées dans des registres : SumO, ...Sum(DS-1). DS étant le nombrfe maximale des ds(i). Au cycle ds on a la somme du bit node 0 qui est disponible. Et la composante en sortie de la FIFO 0(35) est la composante 0 du bit node O. Au cycle ds+1 on délivre donc au CNU(31) le premier message Lambda(0,0) du BitNodeO qui est la somme stockée des composantes moins Gamma(0,0), la sortie de la FifoO . En même temps on effectue une écriture dans cette fifo afin d'obtenir en sortie la composante suivante de ce même BitNode : Gamma(0,1). SumO est aussi à cet instant décalé en Sum1. / 12 Au cycle ds+1, on a maintenant 2 sommes disponibles, celle du bit node 0 en Sumlet celle du bit nodel en SumO. En sortie de la FIFOO, on a maintenant la composante 1 du Bit node 0 et en sortie de la FIFO1 on a la composante 0 du BIT Node 1. On délivre donc au cycle ds+2, le deuxième message du BitNode 0 : Lambda(0,1) et le premier message du Bitnodel : Lambda(1,0). Ainsi de suite jsuqu'à ce que l'on délivre ds Lambdas messages par cycle aux unités de traitement des CNU(31). 15 20 25 30 / 12 BIBLIOGRAPHIE Reference Name [1] Xiao Yu Hu "Efficient Implementation of the Sum Product Algorithm for Decoding LDPC Code , IBM research, IEEE 2001. [2] C. Berrou et A. Glavieux : Near Optimum Error Correcting Coding and Decoding : Turbo Codes , IEEE Trans. Corn. Vol 44 p 1261-1271 Oct. 1996. [3] RG Gallager : Low Density Parity Check Code , IRE Trans. Inform. Theory. Vol IT8 pp21-28, jan. 1962. [4] J.0 Mc Kay : Good Error Correcting Code Based on Sparce Matrices [5] R. M. Tanner. A recursive approach to low complexity codes. IEEE transaction to Information theory, IT-27(5):533-547, Septembre 1981. REVENDICATIONS 1. Procédé de reduction de complexité de décodage des codes LDPC(Low density parity check code) dans une chaîne de communication, ladite chaîne de communication comprenant un codeur LDPC, un modulateur pour la mise en formed u signal, un canal de propagation, un démodulateur et un décodeur LDPC, et chaque code LDPC se représentant sosu la forme d'une matrice de parité H, caractérisé en ce qu'il se decompose en plusieurs sous-fonctions: - La sous-focntion "Check Node Unit" U (31) - La sous-fonction "Memory Controller" (32) - La sous-fonction "Bit Node Unit" (33) La sous function "check node unit" (31) étant en outre composée des sous-fonctions RENDER (51), PIPE (52) et OUTER (53). 2. Procédé selon la revendication 1, caractérisé en ce que, selon une architecture en arbre, elle permet d'implémenter avec le maximum de parallèlismela règle SIGN_MIN du nombre de connexions sur une 15 colonne de la matrice H (dc), combinaison de (dc-1) lambdas quelle que soit la valeur du nombre dc, et que la valeur du nombre dc soit une puissance de 2 et soit constante d'une ligne de la matrice de parité H à l'autre, les dc lambdas étant des messages provenant des dc colonnes de matrice H connectées à la ligne de matrice H considérée. 3. Procédé selon la revendication 1, caractérisé en ce que, selon une architecture en pipeline, il permet de 20 délivrer les messages gammas correspondant à une ligne de matrice H à chaque cycle d'horloge avec une latence de log(dc)+1 cycles, permettant aisni le calcul de K lignes de matrice H en K+log(dc)+1 cycles, les messages gammas étant des messages provenant des CNU (31) selon la règle du SIGN_MIN. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la sous-fonction 25 RENDER (51) est à la base de l'amélioration de l'implémentation de la règle SIGN_MIN. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il permet une implementation série de plusieurs unités de traitement (BNU (33) +MEMC (32) +CNU (33)) afin d'augmenter le capacités de traitement du décodeur. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il permet un stockage de 30 messages gammas, en utilisant une FIFO circulaire permettant d'obtenir sans décodage d'adresse les constituantes gamma necessaries au calcul des BNU (33), ce stockage permettant de récupérer lesdites composantes gamma une deuxième fois afin de soustraire celles-ci pour obtenir les messages Lambdas. 7. Appareil de reduction de complexité de décodage pour la mise en oeuvre du procédé selon l'une quelconque des revendications là 6, caractérisé en ce qu'il comporte: 35 - un sous-module "Check Node Unit" (31) un sous-module "Memory Controller" (32) - La sous-fonction "Bit Node Unit" (33) Le sous module "check node unit" (31) étant en outre composé des sous-fonctions RENDER(51), PIPE(52) et OUTER(53). 40