Brevet FR2904499A1 — publié le 20080201

PROCÉDÉ DE DÉCODAGE À PASSAGE DE MESSAGES AVEC ORDONNANCEMENT SELON UNE FIABILITÉ DE VOISINAGE DESCRIPTION 5 DOMAINE TECHNIQUE La présente invention concerne le décodage de codes correcteurs d'erreurs dans le domaine des télécommunications ou de l'enregistrement de données. Plus précisément, l'invention est relative à une 10 méthode de décodage itératif à passage de messages de codes correcteurs d'erreurs susceptibles d'une représentation par graphe bipartite, tels que les codes LDPC (Low Density Parity Check) ou les turbocodes. ÉTAT DE LA TECHNIQUE ANTÉRIEURE 15 Les codes correcteurs d'erreurs susceptibles de représentation par graphe bipartite recouvrent une large variété de codes, notamment les codes LDPC, initialement décrits par R. Gallager dans son article 20 intitulé Low density parity check codes publié dans IEEE Trans. Inform. Theory, vol. IT-8, pages 21-28, 1962, dont les intéressantes propriétés ont été redécouvertes récemment, et les turbocodes introduits par C. Berrou et al. dans son article fondateur Near 25 optimum error correcting coding and decoding : turbo-codes paru dans IEEE Trans. Inform. Theory, vol. 44, N 10, pages 1261-1271, 1996. On appelle graphe bipartite un graphe non orienté dont l'ensemble des noeuds est constitué de deux sous- 30 ensembles disjoints tels que deux noeuds quelconques 2904499 2 d'un même sous-ensemble ne sont pas reliés entre eux par une arête du graphe. Certains codes correcteurs d'erreurs sont susceptibles d'une représentation par graphe bipartite. Le graphe est partitionné en un premier sous-ensemble de noeuds associés aux symboles constituant un mot de code et un second sous-ensemble de noeuds associés aux contraintes du code, typiquement aux contrôles de parité. Un graphe bipartite associé à un groupe de contraintes est encore appelé graphe de Tanner. Les symboles du mot de code sont en général des éléments du corps de Galois F244, autrement dit des bits, mais ils peuvent plus généralement être des éléments d'un corps de caractéristique 2 quelconque F2p et par conséquent d'un alphabet 2"-aire. Dans la suite, nous nous limiterons sans perte de généralité au cas p =l, c'est-à-dire aux codes binaires. Les codes susceptibles de représentation par graphe bipartite peuvent être décodés au moyen d'un décodage itératif à passage de messages, dit aussi de type MP (Message Passing) ou BP (Belief Propagation). On trouvera une description générique de cette méthode de décodage dans la thèse de N. Wiberg intitulée Codes and decoding on general graphs , 1996. Le décodage itératif de type MP est en fait une généralisation d'algorithmes bien connus dans le domaine du décodage à savoir l'algorithme forward-backward utilisé pour les turbocodes et l'algorithme de Gallager pour les codes LDPC. Dans un souci de simplification, nous rappellerons ci-après le principe du décodage itératif par passage 2904499 3 de messages dans le cadre d'un code LDPC. Nous considérons un code linéaire (K,N) où K est la dimension du code représentant le nombre de bits d'information et N est la longueur du code, 5 représentant le nombre de bits codés. M = N ù K correspond au nombre de bits de parité ou, de manière équivalente, le nombre de contraintes de parité. On a illustré en Fig. 1 le graphe de Tanner d'un code linéaire (K,N). On a fait figurer à gauche du 10 graphe les noeuds correspondant aux bits du code, encore dénommés noeuds de type variable ou encore plus simplement variables et à droite les noeuds correspondant aux contrôles de parité, encore dénommés 15 nœuds de type contrôle ou encore plus simplement contrôles . La matrice d'incidence du graphe correspond à la matrice de parité du code qui est de 20 dimension M xN. Ainsi, le graphe bipartite comprend N noeuds de type variable et M nœuds de type contrôle , un noeud n de variable étant relié à un noeud m de contrôle si et seulement si h,,,n =1 . Par exemple, le graphe de la Fig. 1, correspond à un code (10,5) possédant la matrice de parité suivante: '1 1 1 1 0 0 0 0 0 0\ 1 0 0 0 1 1 1 0 0 0 H= 0 1 0 0 1 0 0 1 1 0 (1) 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1, 25 On rappelle de manière générale qu'un code linéaire est défini par une matrice génératrice G dont les 2904499 4 éléments sont des valeurs binaires et qu'un mot de code x = (xl,x2,..,xN) est obtenu à partir d'un mot de bits d'information a = (al,a2,..,aK) au moyen de 5 x=aG (2) Puisque tous les mots de code vérifient les contrôles de parité, on a la relation : 10 H.GT =0 (3) où l'on a noté GT la transposée de la matrice G. Le mot de code x est transmis sur un canal de communication ou enregistré sur un support de données. 15 A la réception ou à la lecture du support, on récupère un version bruitée de x, soit y = (y1,y2,..,yN) . L'opération de décodage consiste à retrouver x et donc a à partir de l'observation y. Nous conviendrons des notations suivantes avant de 20 décrire le principe du décodage itératif à passage de messages: H(n) désigne l'ensemble des contrôles reliés à la variable n dans le graphe bipartite, autrement dit l'ensemble des noeuds adjacents au noeud n; 25 H(m) est l'ensemble des variables reliées au contrôle m dans le graphe bipartite, autrement dit l'ensemble des noeuds adjacents au noeud m ; an représente l'information a priori concernant la variable n du graphe bipartite, autrement 30 dit l'information a priori concernant le nième bit du 2904499 5 mot de code. Cette information prend en compte le signal reçu et les caractéristiques du canal de transmission. Elle constitue l'entrée du décodeur et est généralement fournie par le démodulateur sous la 5 forme de valeurs souples, soit en termes de probabilités: an =(p ,pä) 10 où pn = Pr(xn= alyn), a e {0,1} , soit, plus commodément sous la forme logarithmique de probabilités ou LLR : Ainsi, pour un bruit BBCG (bruit blanc centré gaussien) et une modulation BPSK, le démodulateur calcule simplement : 15 an =1n ( Pr(xn =OYn)\ Pr(xn =1Yn)~ 20 (6) où a2 est la variance du bruit. 25 amn représente le message transmis par la variable n au contrôle m E H(n). Par référence aux turbocodes, amn est encore appelée information extrinsèque ; 2904499 6 P. représente de manière symétrique le message transmis par le contrôle m à la variable n E H(m). Il est également qualifié d'information extrinsèque ; ân représente l'information a posteriori relative 5 à la variable n elle prend en compte à la fois l'information a priori aä et les messages P. reçus par la variable n de ses contrôles adjacents pendant le décodage ; ~x est la valeur dure correspondant à la valeur 10 souple ân, autrement dit la décision prise pour le bit Le principe du décodage itératif par passage de messages est illustré en Fig. 2. A l'étape 210, on procède à l'initialisation des 15 messages am,,, pour chaque couple de variable n et de contrôle m E H(n). Les messages amn sont généralement initialisés par les informations a priori c'est-à-dire : amn = an , Vm e H(n) . On initialise également le compteur d'itérations Iter à 0. 20 L'étape d'initialisation est suivie d'une boucle d'itération comprenant les étapes suivantes : En 220, on procède au traitement des contrôles. Plus précisément, pour chaque contrôle m, on calcule les messages P mn du contrôle m à destination des 25 variables respectives n E H(m), soit : Nmn = Fc\tamn,In'E H(m)ù{n}}) (7) 2904499 7 où l'on a noté Fc la fonction de traitement des contrôles. Pour un couple de noeuds m , n E H(m) quelconque donné, le message /amn est calculé en fonction des messages qu'a lui-même reçu le contrôle m 5 des variables n'E H(m)-{n}. On constate par conséquent qu'il n'y a pas renvoi d'information extrinsèque d'un noeud de variable sur lui-même. L'étape de traitement des contrôles est aussi appelée étape horizontale. En 230, on procède symétriquement au traitement 10 des variables. Plus précisément, pour chaque variable n, on calcule les messages amn à destination des contrôles respectifs m E H(n), soit : amn Fv ({/3m'n l m' E H(n) - {m}}) (7' ) où l'on a noté FV la fonction de traitement des variables. Pour un couple de noeuds n, m e H(n) donné, le message amn est calculé en fonction des messages qu'a elle-même reçu la variable n des contrôles m'EH(n)-{m}, 20 de sorte que, comme précédemment, il n'y a pas renvoi d'information extrinsèque d'un noeud sur lui-même. L'étape de traitement des variables est aussi appelée étape verticale. En 240, on estime l'information a posteriori ân à 25 partir de l'information a priori an et des messages /.3mn reçus par la variable n de la part de ses nœuds de contrôle adjacents m E H(n), ce que l'on exprime symboliquement par : 15 2904499 ân = FAP(ken }u {Pmn lm e H(n)1) 8 (8) où l'on a noté FAP la fonction d'estimation a posteriori. En 250, on prend une décision sur les valeurs dures ân à partir des valeurs souples ân, soit : an = FF(â,) (8') 10 où l'on a noté Fä la fonction de décision. Typiquement, pour une modulation BPSK, la décision est prise sur le signe de la valeur souple, c'est-à-dire àn = sgn(ân) . On identifiera dans la suite pour raison de commodité la 15 valeur d'un bit avec sa valeur modulée. On représentera conventionnellement le bit 0 par la valeur +1 et le bit 1 par la valeur -1 . En 260, on vérifie si le vecteur â=(ÇC,,ce2,..' N) est 20 un mot de code, c'est-à-dire s'il satisfait aux contrôles de parité. Dans l'affirmative, on sort de la boucle en 265, le mot décodé étant U. Dans la négative, on incrémente le nombre d'itérations en 267 et on compare en 270, si le nombre d'itérations 25 effectuées Iter a atteint une valeur de seuil Iter max . Si ce n'est pas le cas, on poursuit le décodage itératif en rebouclant à l'étape 220. A défaut, on conclut à l'échec de l'opération de décodage et on sort en 275. 5 2904499 9 L'ordre des étapes dans la boucle d'itération peut différer de celui exposé en Fig. 2. En particulier, on peut intervertir l'ordre de traitement des variables et des contrôles et alors commencer par une initialisation 5 des messages /"mn : Pmn = 0 , f/n E {1,...N} et Vm E H(n) . Selon le principe de décodage itératif présenté en Fig. 2, on procède au traitement de tous les contrôles puis de toutes les variables ou bien, comme mentionné ci-dessus, au traitement de toutes les variables puis 10 de tous les contrôles. On parle alors d' ordonnancement parallèle ou encore d' ordonnancement par inondation (flooding scheduling). D'autres types d'ordonnancements ont été proposés dans la littérature ; ils peuvent être classés en deux 15 catégories : - ordonnancement de type série, catégorie dans laquelle on peut ranger les ordonnancements dénommés serial scheduling , shuffled-BP , horizontal 20 shuffled 10U vertical shuffled . L'ordonnancement de type série est applicable aussi bien aux contrôles qu'aux variables. Pour une application aux contrôles, le décodage utilise la stratégie suivante : • on procède tout d'abord au traitement d'un seul 25 contrôle m en calculant les messages I"mn à destination des variables n E H(m) ; • on met à jour et on transmet les messages am,,, de chaque variable n e H(m) à destination des contrôles m'EH(n)-{m}. On met également à jour 2904499 10 les informations a posteriori âä relatives à ces mêmes variables; • on procède au traitement du contrôle suivant et l'on itère les deux étapes précédentes jusqu'à 5 épuisement des contrôles. De manière duale, on peut effectuer un traitement variable par variable au lieu d'effectuer un traitement contrôle par contrôle. Selon le cas envisagé, on 10 parlera d'ordonnancement horizontal shuffled ou d'ordonnancement vertical shuffled . On peut aussi hybrider les deux ordonnancements précités sous la forme d'un ordonnancement dit mixte ou group-shuffled . On trouvera une 15 description de la stratégie de décodage correspondant à un ordonnancement mixte dans l'article de J. Zhang et al. intitulé Shuffled iterative decoding paru dans IEEE Trans. on Comm., Vol. 53, 1\1 2, Février 2005, pages 209-213. La stratégie est basée sur une partition 20 des noeuds par groupes, le traitement étant en parallèle au sein d'un groupe et en série d'un groupe au suivant. Plus précisément, pour une partition en groupes de contrôles: • on procède au traitement d'un premier groupe G 25 formé par les contrôles 4l,m2,..,mg} en calculant les messages /3m,, à destination des variables nEH(m;), pour i=1,...,g; • on met à jour et on transmet les messages am.n de chaque variable n E H(m,) , i =1,...,g à destination 30 des contrôles respectifs m'c H(n)-{m;} . On met 2904499 11 également à jour les informations a posteriori âä relatives à ces mêmes variables ; • on procède au traitement du groupe de contrôles suivant et l'on itère les deux étapes 5 précédentes jusqu'à épuisement des groupes de contrôles. De manière duale, on peut opérer sur la base d'une partition par groupes de variables au lieu d'une 10 partition par groupes de contrôles. On a illustré schématiquement dans les Figs. 3, 4 et 5 le mécanisme de passage de messages respectivement pour un ordonnancement parallèle, un ordonnance série 15 et un ordonnancement mixte. On a supposé que l'on procédait au traitement des contrôles avant le traitement des variables. En Fig. 3 on a fait figurer la première étape de traitement des contrôles (a) et la première étape de traitement des variables (b). En 20 Figs. 4 et 5 on a fait figurer la première (a) et la seconde étape (c) de traitement des contrôles ainsi que la première étape (b) et la seconde étape de traitement des variables (d). En Fig. 5, l'ensemble des noeuds de contrôle a été partitionné en deux groupes notés G, et 25 G2 qui sont traités séquentiellement. On remarquera que l'ordonnancement série et l'ordonnancement parallèle peuvent être vus en fait comme des cas particuliers d'ordonnancement mixte, le premier correspondant au cas où les groupes sont 30 réduits à des singletons, le second correspondant au 2904499 12 cas où un groupe comprend l'ensemble de tous les noeuds de contrôle (resp. de variable). On connaît deux algorithmes principaux de décodage 5 itératif à passage de messages pour les codes LDPC : l'algorithme SPA (Sum Product Algorithm), encore appelé log-BP et l'algorithme Min-Sum , encore appelé based BP . On trouvera une description détaillée de ces deux algorithmes dans l'article de W.E. Ryan 10 intitulé An introduction to LDPC codes , publié dans CRC Handbook for coding and signal processing for recording systems, et disponible sous le lien www.csee.wvu.edu/wcrl/ldpc.htm. 15 Les algorithmes SPA et Min-Sum ne diffèrent que par l'étape de traitement des contrôles qui sera détaillée plus loin. Les autres étapes sont identiques, à savoir : L'étape 230 de traitement des variables consiste à 20 calculer les messages amn comme suit : / Pr(xn = 0 Yn , Bmn , C. n Pr(xn =lYn,Bmn,Cmn amn = In (10) où B,,nn représente l'ensemble des messages /3m,n reçus par 25 la variable n de la part des contrôles m'E H(n)-{m} et C. représente l'évènement correspondant à un contrôle de parité vérifié pour chacun de ces contrôles. Sous réserve de l'indépendance des yn, on montre que amn peut s'exprimer sous forme de LLR par : 2904499 amn = an + Ej f m'n m'EH (n){m } L'étape 240 d'estimation de l'information a 5 posteriori consiste à calculer : Pr(xn =0 yn' Bn' Cn Pr(xn ll.yn, Bn , Cn , où Bn représente les messages reçus par la variable n 10 de tous les contrôles de H(n) et Cn représente l'évènement correspondant à un contrôle de parité vérifié pour chacun de ces contrôles. Sous la même hypothèse que précédemment, on montre que ân peut s'exprimer sous forme de LLR par : 15 an =an+ ES mn meH(n) On remarque d'après (11) et (13) que : 20 amn =ânùJ3mn (14) L'étape 230 de traitement des variables peut par conséquent être placée en fin d'itération, après l'estimation de l'information a posteriori. 25 L'expression (14) traduit le fait que l'on ne retourne pas l'information extrinsèque (ici /amn) envoyée par un noeud (m) vers lui-même. 13 (12) (13) 2904499 14 L'étape 250 de décision des valeurs dures est simplement réalisée par : an = sgn(an) (15) 5 où sgn(x)=1 si x est positif et sgn(x)=ù1 sinon. La vérification en 260 des contrôles de parité sur les valeurs dures passe par le calcul des contrôles' de 10 parité : cm = nan , m =1,...,M (16) neH(m) Les contrôles de parité sont tous satisfaits si et 15 seulement si : m l cm = M (17) m=l L'étape de traitement des contrôles 220 consiste à 20 calculer, pour l'algorithme SPA Pr(cm =1x,, =O,Am)\ Pr(cm =1xn =1,Amn)i f3mn ù 1r1 (18) où cm=1 signifie une condition de parité satisfaite 25 pour le contrôle m et Amn représente l'ensemble des messages amn, reçus par le contrôle m de la part des 2904499 15 variables n'E H(m)-{n} . On montre que P. peut s'exprimer par : n sgn (amn') .11) 4mn' (19) \n'eH(m)-{n} / \.n'eH(m)-{n} ex+1'\ ( (x avec (D(x) = ln = -ln tanh ù ex -1) 2 Le traitement des contrôles selon l'algorithme Min-Sum correspond à une simplification de l'expression 10 (19). Du fait de la décroissance rapide de la fonction q)(x) et de l'égalité de c(x) avec sa réciproque, i. e. (D(x))= x, on peut légitimement effectuer l'approximation suivante : 5 15 i J sgn (amn' ) vn'EH(m)-{n} n'emin (n )Vamn'I (20) L'algorithme de décodage Min-Sum est sensiblement plus simple que l'algorithme de décodage SPA car il n'effectue que des additions, comparaisons et 20 changements de signe. En outre, les performances de l'algorithme Min-Sum sont indépendantes de l'estimation de la variance du bruit a2. Bien que les performances de l'algorithme de décodage SPA soient meilleures que celles de 25 l'algorihme Min-Sum, elles peuvent sévèrement se dégrader dans le cas d'une mauvaise estimation de la puissance de bruit. 2904499 16 L'objet général de la présente invention est de proposer un algorithme de décodage itératif de type à passage de messages permettant de décoder un code 5 correcteur d'erreurs susceptible de représentation par graphe bipartite, possédant de meilleures performances en termes de taux d'erreur et de vitesse de convergence que les algorithmes de même type connus de l'état de la technique. 10 Un premier objet de l'invention est de proposer un algorithme de décodage itératif de type à passage de messages permettant de décoder un code LDPC avec une complexité nettement inférieure à celle de l'algorithme SPA tout en présentant, pour un rapport signal à bruit 15 donné, des performances comparables, voire supérieures, en termes de taux d'erreur, et, de surcroît, ne nécessitant pas une estimation de la puissance de bruit. Un autre objet particulier de la présente 20 invention est de proposer un algorithme de décodage de type à passage de messages permettant le décodage de codes LDPC avec une vitesse de convergence plus élevée que celle des algorithmes SPA ou Min-Sum. 25 EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode de décodage itératif de type à passage de messages pour décoder un code correcteur d'erreurs susceptible de représentation par un graphe bipartite comprenant une 30 pluralité de nœuds de variable et une pluralité de nœuds de contrôle, ladite méthode étant telle que, pour 2904499 17 chaque itération d'une pluralité d'itérations de décodage : - on effectue un classement des noeuds de variable ou bien des noeuds de contrôle en fonction des degrés de 5 fiabilité respectifs des informations de décodage disponibles en des voisinages de ces noeuds, un noeud possédant un degré de fiabilité élevé étant classé avant un noeud possédant un faible degré de fiabilité ; - les noeuds ainsi classés passent chacun au moins 10 un message à un noeud adjacent, dans l'ordre défini par ledit classement. Selon un premier mode de réalisation, ledit classement comprend, pour chaque noeud à classer, le calcul d'une mesure de fiabilité des informations 15 présentes, envoyées ou reçues par les noeuds situés à moins d'une distance prédéterminée de ce dernier au sein du graphe bipartite, et le tri des valeurs des mesures ainsi obtenues. Pour chaque itération de ladite pluralité, on opère 20 alors séquentiellement sur les noeuds classés dans l'ordre défini par ledit classement et, pour chaque noeud classé, on calcule les messages à destination des noeuds qui lui sont adjacents et, pour chacun desdits noeuds adjacents, les messages à destination des noeuds 25 eux-mêmes adjacents à celui-ci. Selon un second mode de réalisation, ledit classement comprend, pour chaque noeud à classer, le calcul d'une mesure de fiabilité des informations présentes, envoyées ou reçues par les noeuds situés à 30 moins d'une distance prédéterminée de ce noeud au sein 2904499 18 du graphe bipartite. Les noeuds sont groupés par intervalles de valeurs de ladite mesure. Si la mesure de fiabilité est à valeurs entières, on stocke pour chacune desdites valeurs entières, dans 5 une zone de mémoire qui est associée à cette valeur, les indices des nœuds dont la mesure de fiabilité est égale à cette dernière. Pour chaque itération de ladite pluralité, on opère séquentiellement sur les groupes de noeuds dans l'ordre 10 défini par ledit classement et, pour chaque groupe de noeuds, on calcule les messages à destination des noeuds qui leur sont adjacents et, pour chacun desdits noeuds adjacents, les messages à destination des noeuds eux-mêmes adjacents à ces derniers. 15 Selon une variante, chaque itération de ladite pluralité comprend en outre, pour chaque noeud de variable dudit graphe bipartite, une étape de calcul d'une information a posteriori en fonction d'une information a priori déjà présente dans ce nœud et des 20 messages reçus par ce noeud en provenance des noeuds de contrôle adjacents. L'étape de calcul d'information a posteriori peut être suivie d'une étape de décision sur la valeur dure de ladite variable. 25 On teste alors si les valeurs dures des variables ainsi obtenues vérifient les contrôles de parité associés à tous les nœuds de contrôle du graphe et, dans l'affirmative, on fournit comme mot décodé le mot constitué desdites valeurs dures. 30 2904499 19 Avantageusement, le classement est interrompu après un nombre d'itérations de décodage prédéterminé, la méthode de décodage poursuivant ensuite ses itérations de décodage en absence dudit classement desdits noeuds 5 de variables ou bien desdits noeuds de contrôle. Le classement est interrompu si le minimum, en valeur absolue, des différences entre les valeurs a posteriori et des valeurs a priori desdites variables est supérieur à une valeur de seuil prédéterminé, la 10 méthode de décodage poursuivant ensuite ses itérations de décodage en absence dudit classement desdits noeuds de variables ou bien desdits noeuds de contrôle. Dans une première application, ledit code correcteur d'erreurs est un turbocode. 15 Dans une seconde application, ledit code correcteur d'erreurs est un code LDPC (K,N) représenté par un graphe bipartite à N noeuds de variable et M = NùK noeuds de contrôle. Dans ce dernier cas, le message /"mn d'un noeud de 20 contrôle d'indice m E {1,..,M} à un noeud de variable d'indice n E {1,..,N} pourra être calculé par : /"mn f sgn(amn') cl) ~j~~amn'I n'{H(m)-{n} / ~n'EH(m)-{n} où amn, désigne le message du noeud de variable d'indice n' au noeud de contrôle d'indice m, H(m) l'ensemble des 25 noeuds de variable adjacents au noeud de contrôle d'indice m , sgn(x)=1 si x est positif et sgn(x)=ù1 sinon, et (D(x)=In (ex +1 ex -1 2904499 20 Alternativement, le message fmn d'un noeud de contrôle d'indice m e {1,..,M} à un noeud de variable d'indice n e {1,..,N} pourra être calculé par : fJsgn(amn.) . min (a I) vn'eH(m)ù{n} nEH(m)ù{n} mn où amn, désigne le message du noeud de variable d'indice n' au noeud de contrôle d'indice m, H(m) l'ensemble des noeuds de variable adjacents au noeud de contrôle 10 d'indice m, sgn(x) =1 si x est positif et sgn(x) = -1 sinon. Selon un exemple de réalisation, le classement porte sur les noeuds de contrôle et ladite distance prédéterminée est égale à 2. La mesure de fiabilité 15 d'un noeud de contrôle d'indice m est alors calculée par : f (m) = c+ Emin(1,Card {nie H(n)-{m}cm, _ -1}) neH(m) 20 où H(m) désigne l'ensemble des noeuds de variable adjacents au noeud de contrôle d'indice m, H(n) l'ensemble des noeuds de contrôle adjacents au noeud de variable d'indice n, Card(.) désigne le cardinal d'un ensemble, avec c=0 si cm=+1 et c=Vm.+1 si cm=-1 où 25 Smax est le degré maximal des noeuds de contrôle dans le graphe bipartite, et où cm =+1 / cm =-1 signifient respectivement que le contrôle de parité est 5 Ymn = 2904499 21 vérifié/n'est pas vérifié, pour le nœud de contrôle d'indice m. L'invention concerne enfin un programme d'ordinateur comprenant des moyens logiciels adaptés à 5 mettre en œuvre les étapes de la méthode de décodage définie plus haut lorsqu'il est exécuté par un ordinateur. BRÈVE DESCRIPTION DES DESSINS 10 La Fig. 1 représente un exemple de graphe de Tanner pour un code (K,N) ; La Fig. 2 illustre de manière schématique le principe d'un décodage itératif par passage de messages connu de l'état de la technique ; 15 La Fig. 3 représente les premières itérations d'un décodage itératif à passage de messages selon un ordonnancement de type parallèle ; La Fig. 4 représente les premières itérations d'un décodage itératif à passage de messages selon un 20 ordonnancement de type série ; La Fig. 5 représente les premières itérations d'un décodage itératif à passage de messages selon un ordonnancement de type mixte ; Les Figs. 6A et 6B représentent respectivement le 25 voisinage d'ordre 1 et d'ordre 2 d'un nœud ; La Fig. 7 représente le principe d'un décodage itératif par passage de messages selon l'invention ; La Fig. 8 représente une méthode de décodage itératif par passage de messages selon un premier mode 30 de réalisation de l'invention ; 2904499 22 La Fig. 9 représente une méthode de décodage itératif par passage de messages selon un second mode de réalisation de l'invention ; La Fig. 10 représente un exemple d'application de 5 la méthode de décodage selon l'invention pour décoder un code LDPC ; La Fig. 11 indique le taux d'erreur obtenu par la méthode de décodage selon l'invention par comparaison aux méthodes de l'état de la technique, pour un code 10 LDPC particulier. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS On considère à nouveau un code correcteur d'erreurs 15 susceptible d'une représentation par un graphe bipartite avec N variables et M contrôles. On appelle distance entre deux nœuds v, du graphe et l'on note D(v, ) la longueur, exprimée en nombre d'arêtes, du plus court chemin reliant ces noeuds à 20 travers le graphe. Compte tenu de la définition même d'un graphe bipartite, on en déduit que la distance entre deux noeuds de même type est un nombre pair et que la distance entre deux noeuds de types différents est un nombre impair. 25 On définit le voisinage d'ordre d d'un noeud v quelconque d'un graphe F, l'ensemble Vd) des nœuds situés à une distance inférieure ou égale à d de v, soit : 30 v(d)={/iEFD(u,v) -fa(mi)...L(mM,) et pour une mesure négative on les trie en sens inverse. Si la mesure est un produit cartésien (cf. par exemple (32)) on utilise la 10 relation d'ordre lexicographique ou la relation d'ordre lexicographique inverse suivant que la mesure est négative ou positive. On initialise d'autre part un compteur de noeuds de contrôle, j=0. On sélectionne en 825 le contrôle courant m = mi et 15 l'on traite en 830 les variables neH(m), autrement dit on calcule amn = Fv({i3m.n m'e H(n)-{m}}) . On passe ensuite en 835 à un traitement du contrôle courant m, autrement dit on calcule Ymn = Fc({amn,ln'e H(m)-{n}}) pour ne H(m) . 20 Selon une variante de réalisation les étapes 830 et 935 sont interverties. On incrémente le compteur de noeuds de contrôle en 837 et l'on teste en 839 s'ils ont tous été traités. Dans la négative, on reboucle à l'étape 825, sinon l'on 25 poursuit par les étapes 840 à 860, représentant respectivement le calcul d'information a posteriori, la décision sur les valeurs dures et la vérification des contrôles de parité. Les étapes 840, 850, 860, 865, 2904499 33 867, 870, 875 sont respectivement identiques aux étapes 240, 250, 260, 265, 267, 270, 275 de la Fig. 2. Selon un mode alternatif de réalisation, on procède au tri des variables en lieu et place du tri des 5 contrôles. La boucle interne 825 à 839 porte alors sur une variable à la fois et, de même que précédemment, le traitement de la variable courante peut être effectué avant ou après le traitement des contrôles qui lui sont adjacents. 10 La Fig. 9 illustre un mode de réalisation de l'invention utilisant un ordonnancement mixte. A l'étape 910, on effectue une initialisation des messages a,,,,, et P. comme en l'étape 810 de la Fig. 8. 15 En 920, on partitionne l'ensemble des noeuds de contrôle ou des nœuds de variable en groupes, correspondant chacun à une classe de fiabilité différente. Une classe de fiabilité est définie par exemple au moyen d'un intervalle de valeurs d'une 20 mesure de fiabilité. Ce mode de réalisation est particulièrement avantageux lorsque la mesure est à valeurs entières. En effet, on peut alors allouer une tranche à une valeur entière ou à une pluralité de valeurs entières contiguës et ranger les indices des 25 noeuds dans un tableau en fonction de leurs classes respectives. On notera par la suite (po,(p,,...eU, les différentes classes de fiabilité, yoo étant la classe de plus haut degré de fiabilité et (pu, la classe de plus faible degré de fiabilité, et GO,G,,...,GW les groupes de 2904499 34 noeuds correspondants. On suppose dans la suite que la partition a été effectuée sur les noeuds de contrôle. On initialise d'autre part le compteur de classes de fiabilité à j=0. 5 En 925, on sélectionne le groupe de noeuds correspondant à la classe de fiabilité courante (pi, soit G1 . A l'étape 930, on effectue en parallèle le traitement des variables n e H(m), Vm e Gj, c'est-à-dire 10 que l'on calcule les messages amn = Fv({j3mnlm'E H(n)û{m}}), VmeGj, `dneH(m). A l'étape 935, on effectue en parallèle le traitement des contrôles m E G1, c'est-à-dire que l'on calcule les messages Nmn = Fc({amn.ln'e H(m)ù{n}}), Vm e G1 , 15 Vn e H(m) . Selon une variante de réalisation les étapes 930 et 935 sont interverties. On incrémente en 937 le compteur de classes et l'on teste en 939 si elles ont toutes été traitées. Dans la 20 négative, on reboucle à l'étape 925, sinon on poursuit par les étapes 940 à 960, représentant respectivement le calcul d'information a posteriori, la décision sur les valeurs dures et la vérification des contrôles de parité. Les étapes 940, 950, 960, 965, 967, 970, 975 25 sont respectivement identiques aux étapes 240, 250, 260, 265, 267, 270, 275 de la Fig. 2. La Fig. 10 illustre une application particulière de l'invention au décodage d'un code LDPC au moyen d'un 2904499 35 ordonnancement mixte, sur la base d'une mesure de fiabilité à valeurs entières. On a choisi ici la mesure négative sur les noeuds de contrôle définie en (36). A l'étape 1010, on effectue l'initialisation des 5 valeurs souples a posteriori ân par les observations correspondantes : ân = an et des messages P. par O. On initialise également le compteur d'itérations à 0. En 1015, on prend une décision sur les valeurs 10 dures soit Un = sgn(ân) . M On calcule en 1020 la valeur X _ Ecm où les cm sont m=1 les contrôles de parité cm = n n , m =1,...,M neH(m) On teste en 1023 si x=M, c'est-à-dire si tous les contrôles de parité sont vérifiés. Dans l'affirmative 15 on sort de l'algorithme de décodage en 1025 en fournissant le mot de 1027 par le calcul des de contrôle au moyen de cette mesure prend 20 0,1,..,2Sm + 1 où Smax est code. A défaut on poursuit en mesures de fiabilité des noeuds la mesure (36). On rappelle que des valeurs entières parmi le degré maximal des noeuds de contrôle. Dans le cas présent, on attribue une classe de fiabilité par valeur entière, soit (po,yoi,...,(po, avec w = 2Smx +1 où la classe (pl correspond à la valeur de mesure j e {0,1,.., 2Smx +1} . 25 En 1029, on sélectionne le groupe de noeuds correspondant à la classe de fiabilité courante çp~, soit G]. 2904499 36 En 1030, on effectue en parallèle le traitement des variables n e H(m) , Vm e G1 , c'est-à- dire que l'on calcule les messages , amn = ân ùNmn Vm E G1 . A l'étape 1035, on effectue en parallèle le 5 traitement des contrôles m e Gj, c'est-à-dire que l'on calcule les messages à destination des variables nEH(m), VmEG., soit mn 1 1sgn(amn'). Eamn'I) ' \n'EH((m))-{n} / \,n'EH(m)-in} / pour un traitement SPA et //mn = ~sgn(a ,) . min a '1) \n'eH(m)-{n} mn n'EK(m)-{n} mn r pour un traitement simplifié de type Min-Sum comme 10 indiqué ici sur la Figure. On calcule ensuite les informations a posteriori en 1040 grâce à ân =an+ E/3mn mEH(n) On notera qu'une partie des contrôles m e H(n) intervenant dans la sommation peuvent ne pas faire partie du groupe Gj et que donc les messages P. qui 15 proviennent de ces contrôles n'ont pas été recalculés en 1035. En outre, la variable n étant adjacente à plusieurs contrôles m e H(n), le calcul de ân se fera plusieurs fois au fur et à mesure que l'on traite les contrôles de H(n). Afin d'éviter que la somme en 1040 20 ne soit calculée plusieurs fois et qu'à chaque fois certains messages /- mn n'ayant pas varié ne soient recalculés, on pourra avantageusement remplacer les étapes 1035 et 1040 par une étape comprenant les opérations suivantes: 25 VmeGi,VnEH(m) 2904499 37 - soustraction de l'ancien message, soit : an = an û J3mn - calcul du nouveau message, soit : i ll f sgn(amn') .min~LCmn Il \n'EH(m)-{n} n'EH(m)-{n} 5 - actualisation de l'information a posteriori par addition du nouveau message : an =an+I3mn De cette manière on met à jour l'information a posteriori âä au fur et à mesure que l'on calcule les 10 nouveaux messages envoyés par les contrôles m E H(n) à la variable n. Cela permet de réduire sensiblement le nombre d'opérations effectuées pour le calcul des informations a posteriori. On incrémente ensuit en 1043 le compteur de classes 15 de fiabilité et l'on teste en 1045 si toutes les classes ont été traitées. Dans la négative, on retourne à l'étape 1029 pour traiter la classe de fiabilité suivante. Dans l'affirmative, on incrémente le compteur d'itérations en 1050. En 1053, on teste si le critère 20 d'arrêt est vérifié, c'est-à-dire si le nombre maximal d'itérations est atteint. Si c'est le cas, on sort de la boucle en 1055 en concluant à l'échec du décodage. A défaut, on reboucle à l'étape 1015 pour une nouvelle itération. 25 On remarque qu'en Fig. 10, les étapes de décision sur les valeurs dures ainsi que de vérification du contrôle de parité précèdent celles de calcul de fiabilité et de traitement des noeuds. Ceci est dû au fait que la mesure de fiabilité utilisée ici fmn= 2904499 38 (expression (36)) fait appel aux décisions dures cm et nécessite par conséquent leur calcul préalable. L'algorithme illustré en Fig. 10 ne présente qu'une 5 faible complexité additionnelle par rapport aux algorithmes SPA ou MinSum de l'état de la technique. En contrepartie, l'ordonnancement par fiabilité de voisinage accélère la convergence et permet d'atteindre un taux d'erreur (BER) plus faible pour un même rapport 10 signal à bruit (SNR). Alternativement, pour un même taux d'erreur de consigne, la méthode de décodage selon l'invention permet d'utiliser des codes à plus faible gain de codage. 15 La Fig. 11 permet de comparer les performances en termes de taux d'erreur binaire (BER) des algorithmes Min-Sum et SPA conventionnels avec l'algorithme Min-Sum utilisant un ordonnancement par fiabilité de voisinage, noté Min-Sum-FV, ce pour une plage importante de 20 rapports signal à bruit. Les codes utilisés sont des codes LDPC irréguliers [1008,20161 et [4032,8064, et donc de rendementl/2. Le nombre d'itérations effectuées est égal à 200 pour les trois algorithmes. On remarque que l'algorithme Min-Sum-FV selon 25 l'invention surpasse l'algorithme SPA conventionnel bien que sa complexité soit sensiblement moindre. Dans la méthode de décodage selon l'invention telle que représentée en Figs. 7 à 10 on a supposé que l'on 30 utilisait l'ordonnancement par fiabilité de voisinage pendant toute la durée du décodage. Selon une variante, 2904499 39 on peut n'appliquer cet ordonnancement que lors des premières itérations, de manière à débruiter les observations, puis basculer sur un traitement conventionnel. Le critère de basculement peut être 5 libellé en un nombre d'itérations Iterf ou bien, avantageusement, être basé sur une comparaison en valeur absolue des informations extrinsèques avec un seuil de référence. Par exemple, dès que dans le décodage itératif : 10 min l an ùa n 1>T f n=1,.., N où Tf représente un seuil minimal de fiabilité, on pourra revenir à un traitement Min-Sum ou SPA 15 conventionnel. Cette variante permet d'éviter le tri ou le classement des nœuds dès que les valeurs décodées sont suffisamment fiables et que la convergence est assurée. 20 La présente invention s'applique au décodage de codes correcteurs d'erreurs susceptibles de représentation par graphe bipartite, notamment des codes LDPC ou des turbocodes. Elle peut être utilisée dans le domaine de l'enregistrement de données ou des 25 télécommunications, en particulier pour les systèmes de télécommunications utilisant déjà des codes LDPC, par exemple ceux obéissant aux normes IEEE 802.3a (Ethernet l0Gbits/s), DVB-S2 (diffusion de vidéo par satellite), IEEE 802.16 (WiMAX), ou susceptibles de les utiliser, 30 par exemple les systèmes obéissant aux normes IEEE (37) 2904499 40 802.11 (WLAN) et IEEE 802.20 (Mobile Broadband Wireless Access). REVENDICATIONS 1. Méthode de décodage itératif de type à passage de messages pour décoder un code correcteur d'erreurs susceptible de représentation par un graphe bipartite comprenant une pluralité de nœuds de variable et une pluralité de nœuds de contrôle, caractérisée en ce qu'à chaque itération d'une pluralité d'itérations de décodage : - on effectue un classement (720) des nœuds de variable ou bien des noeuds de contrôle en fonction des degrés de fiabilité respectifs des informations de décodage disponibles en des voisinages (Te),V,;,d)) de ces noeuds, un noeud possédant un degré de fiabilité élevé 15 étant classé avant un nœud possédant un faible degré de fiabilité ; - les noeuds ainsi classés passent (725) chacun au moins un message (amn,/"mn) à un nœ ud adjacent, dans l'ordre défini par ledit classement. 20 2. Méthode de décodage selon la revendication 1, caractérisée en ce que ledit classement comprend, pour chaque noeud à classer, le calcul d'une mesure de fiabilité (fd(n), fd(m)) des informations présentes, 25 envoyées ou reçues par les noeuds situés à moins d'une distance prédéterminée (d) de ce dernier au sein du graphe bipartite, et le tri des valeurs des mesures ainsi obtenues. 30 2904499 42 3. Méthode de décodage selon la revendication 2, caractérisée en ce que, pour chaque itération de ladite pluralité, elle opère séquentiellement sur les noeuds classés dans l'ordre défini par ledit classement, et 5 que, pour chaque noeud classé (825), on calcule les messages à destination des noeuds qui lui sont adjacents (835) et, pour chacun desdits noeuds adjacents, les messages à destination des noeuds eux-mêmes adjacents à celui-ci (830). 10 4. Méthode de décodage selon la revendication 1, caractérisée en ce que ledit classement comprend, pour chaque noeud à classer, le calcul d'une mesure de fiabilité (fd(n), fd(m)) des informations présentes, envoyées ou reçues par les noeuds situés à moins d'une distance prédéterminée (d) de ce noeud au sein du graphe bipartite, et que l'on groupe les noeuds par intervalles de valeurs de ladite mesure. 5. Méthode de décodage selon la revendication 4, caractérisée en ce que la mesure de fiabilité est à valeurs entières et que pour chacune desdites valeurs entières on stocke dans une zone de mémoire qui lui est associée les indices des noeuds dont la mesure de fiabilité est égale à cette valeur. 6. Méthode de décodage selon la revendication 4 ou 5, caractérisée en ce que, pour chaque itération de ladite pluralité, on opère séquentiellement sur les groupes de noeuds dans l'ordre défini par ledit classement, et que, pour chaque groupe de noeuds (G , 2904499 43 on calcule les messages à destination des noeuds qui leur sont adjacents (935) et, pour chacun desdits noeuds adjacents, les messages à destination des noeuds eux-mêmes adjacents à ces derniers (930). 5 7. Méthode de décodage selon l'une des revendications précédentes, caractérisée en ce que chaque itération de ladite pluralité comprend en outre, pour chaque noeud de variable dudit graphe bipartite, 10 une étape de calcul (740,840,940) d'une information a posteriori (ân) en fonction d'une information a priori (an) déjà présente dans ce noeud et des messages reçus (Pmn) par ce noeud en provenance des noeuds de contrôle adjacents. 8. Méthode de décodage selon la revendication 7, caractérisée en ce que l'étape de calcul d'information a posteriori est suivie d'une étape de décision (750,850,950) sur la valeur dure (ân) de ladite 20 variable. 9. Méthode de décodage selon la revendication 8, caractérisée en ce qu'on teste (760,860,960) si les valeurs dures des variables ainsi obtenues vérifient 25 les contrôles de parité associés à tous les noeuds de contrôle du graphe et que, dans l'affirmative, on fournit comme mot décodé le mot constitué desdites valeurs dures. 30 10. Méthode de décodage selon l'une des revendications précédentes, caractérisée en ce que le 15 2904499 44 classement est interrompu après un nombre d'itérations de décodage prédéterminé (Iterf), la méthode de décodage poursuivant ensuite ses itérations de décodage en absence dudit classement desdits noeuds de variables ou 5 bien desdits nœuds de contrôle. 11. Méthode de décodage selon la revendication 7, caractérisée en ce que le classement est interrompu si le minimum, en valeur absolue, des différences entre 10 les valeurs a posteriori et des valeurs a priori desdites variables est supérieur à une valeur de seuil prédéterminé (Tf), la méthode de décodage poursuivant ensuite ses itérations de décodage en absence dudit classement desdits noeuds de variables ou bien desdits 15 noeuds de contrôle. 12. Méthode de décodage selon l'une des revendications précédentes, caractérisée en ce que ledit code correcteur d'erreurs est un turbocode. 20 13. Méthode de décodage selon l'une des revendications 1 à 11, caractérisée en ce que ledit code correcteur d'erreurs est un code LDPC (K,N) représenté par un graphe bipartite à N noeuds de 25 variable et M = N ù K nœuds de contrôle. 14. Méthode de décodage selon la revendication 13, caractérisée en ce que le message I3mä d'un noeud de contrôle d'indice m E {1,..,M} à un noeud de variable 30 d'indice n E {1,..,N} est calculé par : 2904499 45 où amn' désigne le message du noeud de variable d'indice n' au nœud de contrôle d'indice m, H(m) l'ensemble des 5 noeuds de variable adjacents au noeud de contrôle d'indice m , sgn(x) =1 si x est positif et sgn(x) =ù1 Ymn = flsgn(amn').(1) n'eH(m)-{n} / ~n'eH(m)-{n} sinon, et cb(x) =1n (ex +1\ 15. Méthode de décodage selon la revendication 13, 10 caractérisée en ce que le message f3mn d'un noeud de contrôle d'indice m E {1,..,M} à un nœud de variable d'indice n E {1,..,N} est calculé par : Nmn i fJ sgn (amn' ) ~n'eH(m)-{n} J . min ~amn' n'EH (m)-{n} 15 où amn' désigne le message du noeud de variable d'indice n' au noeud de contrôle d'indice m, H(m) l'ensemble des noeuds de variable adjacents au nœud de contrôle d'indice m, sgn(x) =1 si x est positif et sgn(x) =ù1 20 sinon. 16. Méthode de décodage selon les revendications 5 et 15, caractérisée en ce que le classement porte sur les noeuds de contrôle, en ce que ladite distance 25 prédéterminée est égale à 2 et en ce que la mesure de 2904499 46 fiabilité d'un noeud de contrôle d'indice m est calculée par : fù2(m)=c+ E min (1,Card{m' eH(n)ù =ù1}) neH(m) 5 où H(m) désigne l'ensemble des noeuds de variable adjacents au noeud de contrôle d'indice m, H(n) l'ensemble des noeuds de contrôle adjacents au noeud de variable d'indice n, Card(.) désigne le cardinal d'un 10 ensemble, avec c=0 si cm=+1 et c=S,,,+1 si cm=ù1 où 5,,,ax est le degré maximal des noeuds de contrôle dans le graphe bipartite, et où cm =+1 / cm =ù1 signifient respectivement que le contrôle de parité est vérifié/n'est pas vérifié, pour le nœud de contrôle 15 d'indice m. 17. Programme d'ordinateur comprenant des moyens logiciels adaptés à mettre en oeuvre les étapes de la méthode de décodage selon l'une des revendications 20 précédentes, lorsqu'il est exécuté par un ordinateur.