Brevet FR2951339A1 — publié le 20110415

PROCÉDÉ DE DÉCODAGE DE CODES NON BINAIRES DESCRIPTION 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 méthode de décodage à passage de messages de codes non binaires, en particulier de codes LDPC (Low Density Parity Check) non binaires. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Les codes LDPC ont été introduits par R. Gallager dans son article intitulé « Low density parity check codes » publié dans IEEE Trans. Inform. Theory, vol. IT-8, pages 21-28, 1962, et leurs intéressantes propriétés n'ont été redécouvertes que récemment, lorsque la puissance du décodage itératif a été mise en évidence dans les turbocodes. On trouvera une description du décodage itératif des turbocodes dans l'article fondateur de C. Berrou et al. intitulé « Near optimum error correcting coding and decoding : turbo-codes » paru dans IEEE Trans. Inform. Theory, vol. 44, N° 10, pages 1261-1271, 1996. Les codes LDPC tout comme les turbocodes sont susceptibles d'une représentation par graphe bipartite. On appelle graphe bipartite un graphe non orienté dont l'ensemble des noeuds est constitué de deux sous- 2 ensembles disjoints tels que deux noeuds quelconques d'un même sous-ensemble ne sont pas reliés entre eux par une arête du graphe. De manière générale, certains codes correcteurs d'erreurs sont susceptibles d'une représentation par graphe bipartite. Ce graphe est partitionné en un premier sous-ensemble de noeuds associés aux symboles constituant un mot de code, dits noeuds de variable, et un second sous-ensemble de noeuds associés aux contraintes du code, encore appelés noeuds de contrôle. Un graphe bipartite associé à un groupe de contraintes est encore appelé graphe de Tanner. Lorsque les symboles du mot de code sont binaires, les contraintes du code sont appelées contrôles de parité. Ainsi, dans la suite, par souci de clarté, nous utiliserons le terme spécifique de contrôle de parité dans le cas où il s'agira d'un code binaire et le terme plus général de contrainte dans le cas où il s'agira d'un code non-binaire. Les symboles du mot de code sont en général des éléments du corps de Galois F2={0,1}, autrement dit des bits, mais ils peuvent plus généralement être des éléments d'un alphabet de taille q-2, par exemple d'un corps Fr de caractéristique 2 quelconque, c'est-à-dire d'un alphabet 2v-aire (donc q=2p) . 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. Le décodage par passage de messages d'un code non binaire diffère de celui d'un code binaire. En effet pour les codes binaires tels que les codes LDPC binaires, chaque noeud de variable représente un bit codé. Lorsqu'il y a incertitude sur la valeur d'un bit, celle-ci s'exprime en termes de probabilité des valeurs 0 ou 1, ou plus fréquemment comme un rapport de vraisemblance logarithmique, dit LLR (Log Likelihood Ratio), défini comme le logarithme du rapport de ces probabilités. Les messages échangés entre les noeuds du graphe bipartite sont alors libellés, selon le cas, en termes de probabilité ou de LLR. Pour les codes non binaires, chaque noeud de variable représente un symbole codé, c'est-à-dire un élément de l'alphabet du code. Lorsqu'il y a incertitude sur la valeur d'un symbole, cette incertitude peut être représentée par un vecteur de qû1 probabilités, où q est la taille de l'alphabet (qû1 probabilités suffisent puisque la somme des q probabilités vaut 1), ou qû1 valeurs de LLR. Les messages échangés entre les noeuds du graphe bipartite sont également exprimés, selon le cas, sous forme de vecteurs de qû1 valeurs de probabilité ou de qû1 valeurs de LLR. On a représenté en Fig. 1, un exemple de graphe bipartite pour un code non binaire, plus précisément un code LDPC défini sur F8 ayant pour matrice de parité une matrice de taille M x N où N=6 est le nombre de variables et M=3 est le nombre de contraintes (1 3 4 6 0 01 H=0 2 0 7 1 5 ~5 0 1 0 2 4J 10 On remarquera que les coefficients de la matrice sont des éléments de F8. On a fait figurer dans la partie gauche du graphe les noeuds de variable et dans la partie droite les noeuds de contrainte Y,,...,YM . 15 Dans le cas présent : Y : X1 +3X2 +4X3 +6X4 = 0 Y2 : X2 +7X4 +X5 +5X6 = 0 (2) Y3 : 5X1 + X3 + 2X5 + 4X6 = 0 Les messages des variables et des contraintes 20 Y,,...,Y3 peuvent être chacun exprimé comme un vecteur de probabilités de dimension 7. La matrice d'incidence du graphe correspond à la matrice de parité du code, en d'autres termes les poids affectés aux arêtes du graphe représentent les 25 coefficients de la matrice H. Par convention lorsque le poids est nul, l'arête correspondante est omise dans le graphe. (1) Si les codes LDPC non binaires présentent de meilleures capacités de correction que les codes LDPC binaires, ils sont en revanche sensiblement plus 5 difficiles à décoder. En effet la complexité de l'algorithme de décodage est en général proportionnelle à q2, c'est-à-dire au carré de la taille de l'alphabet. Une méthode de décodage des codes LDPC non binaires a été décrite par exemple dans l'article de V. Savin intitulé « Min-Max decoding for non binary LDPC codes », publié dans IEEE Int. Symp. on Information Theory (ISIT), Toronto, Canada, 2008. L'homme du métier pourrait penser qu'une manière naturelle de décoder des codes non binaires serait d'utiliser une représentation binaire équivalente de la matrice de parité. Toutefois, comme nous allons le voir, cette représentation binaire « naturelle » conduirait à des performances de décodage médiocres et un taux d'erreurs élevé. On sait que les codes LDPC tant binaires que non binaires ont pour propriété de présenter une faible densité de coefficients non nuls dans la matrice de parité. Cette propriété se traduit par une faible nombre de cycles courts dans le graphe bipartite. Ces cycles ont tendance à engendrer une auto-confirmation des variables et des contrôles dans le processus de décodage itératif. On entend par là qu'une valeur erronée d'un noeud peut se voir confirmée par le simple fait que les messages que lui transmettent ses voisins 6 dépendent eux-mêmes des messages que ce noeud leur transmet. Pour combattre ce phénomène d'auto-confirmation, le décodage doit respecter le principe dit d'information extrinsèque : un message transmis par un noeud expéditeur à un noeud destinataire est calculé à partir de tous les messages reçus par le noeud expéditeur à l'exception de celui en provenance du noeud destinataire. Toutefois, le respect du principe d'information extrinsèque n'exclut pas des auto- confirmations à des ordres plus élevés, dus aux cycles présents dans le graphe bipartite, ces auto-confirmations étant d'autant plus fréquentes que les cycles sont courts. Le principe de l'information extrinsèque a été schématiquement illustré en Fig. 2. On a représenté ici une portion d'un graphe bipartite dans lequel Y,YZ,Y sont des noeuds de contrôle et X1,...,X4 sont des noeuds de variable. Le message du noeud de contrainte Y à destination du noeud de variable X1 est calculé à partir des messages reçus par Y des noeuds de variable X2,X3,X4, sans tenir compte du message reçu de Xl. Réciproquement, le message du noeud de contrôle X1 à destination du noeud de contrôle Y est calculé à partir des messages reçus par X1 des noeuds de contrôle Y et Y sans tenir compte du message reçu de Y. La Fig. 3 illustre le phénomène d'auto-confirmation dû à la présence d'un cycle dans un graphe bipartite. 7 On a représenté comme précédemment une portion de graphe, les noeuds de variable par des cercles et les noeuds de contrôle par des carrés. Le cycle dans le graphe a été représenté en traits gras. En parcourant ce cycle on se rend compte que le message m6 reçu par le noeud de variable X5 dépend indirectement du message m1 transmis par ce même noeud quelques itérations de décodage auparavant, via les messages successifs m2 à m5. On considère ci-après un alphabet A à q éléments. Les éléments de A seront appelés des « symboles ». Nous supposerons dans un souci de simplification mais sans perte de généralité que q=2p est une puissance de 2. Il existe alors une bijection de A sur Fp : w:A~Fp (3) où F2 ={0,1} est le corps à deux éléments . Un vecteur 20 binaire x=(xo,xl,..,xp_1)E Fp est appelé « image binaire » d'un symbole Xe A si w(X)=x . La bijection CO munit A d'une structure de F2-espace vectoriel. On note L = LF, (A) l'algèbre des F2-endomorphismes de A, c'est-à-dire des endomorphismes de 25 A munie de sa structure de F2-espace vectoriel. L'évaluation des éléments de L sur les symboles de A définit une action de L sur A, qui sera notée multiplicativement : 30 LxA-*A:(h,X)HhX (4) 8 Soit He MMN(L), c'est-à-dire soit H une matrice de taille M x N dont les éléments sont de L. On définit un code non-binaire C c AN par: 5 On appellera H la matrice de contrainte du code C. A l'aide de la bijection (O, on peut faire correspondre à 10 chaque séquence de symboles (X1,...,XN)E ANune séquence binaire ko,x,,1,...,x,,p_I, xN,o,xN,1,...,xN,pjE FzP en remplaçant chaque symbole Xn par son image binaire. Cette séquence binaire (de longueur Np) sera dénommée l' « image binaire » de la séquence (X1,...,XN)E AN . Les 15 images binaires de tous les mots de code (XI,...,XN)E Cc AN forment un code binaire Cbn cFNp dénommé « image binaire de C ». L'isomorphisme O) entre A et Fp induit un isomorphisme entre 4,(A) et £y,(F';): 20 L=£F2(A)~ÇF2(F)=Mp(F2) (6) Ainsi, en remplaçant chaque élément hmn de la matrice H par son image via l'identification (6) ci-dessus, on 25 obtient une matrice binaire Hb;n E MMPNP(F2) . Cette matrice est la matrice de parité du code binaire Coin. C = Ker(H) c AN N ~/ (X1,...,XN )E AN Lhm nXn = 0, Vm = 1,..,M n=1 (5) 9 On notera que les codes non binaires définis sur Fq, c'est-à-dire sur le corps fini à q éléments, représentent un cas particulier de codes non binaires. L'alphabet d'un tel code est A=F, et sa structure de F2-espace vectoriel est induite par l'addition interne sur F. En outre, l'opération de multiplication sur F définit un plongement de F comme sous-espace vectoriel de L=1z(A) (i.e. F îL) . On dit que « le code C est défini sur F » s'il est défini comme le noyau d'une matrice HE MMN(Fq)îMMN(L). Dans ce cas là, tous les éléments de la matrice H appartiennent à F, hmnE F , et les multiplications hmnXn dans (5) sont simplement des multiplications internes dans le corps F. Dans un but d'illustration, nous donnerons un exemple de représentation binaire d'un code non binaire simple. Nous considérerons un alphabet A à 8 éléments, isomorphe par conséquent à f',. Nous adopterons classiquement une représentation primitive de F8. Plus précisément, Fg est isomorphe à F2[D]/P(D) anneau quotient de F2[D] par l'idéal engendré par le polynôme irréductible P(D)=1+D+D3 . L'addition et la multiplication dans Fg sont définies par l'addition et la multiplication des polynômes, modulo P(D). Pour simplifier, nous supposerons que F8 ={0,1,...,7}. Ainsi, l'image binaire d'un symbole Xe F8 ={0,1,...,7} est la séquence binaire (xo,x1,x2) correspondant à l'expression p-1 polynomiale X =Lx12`) . De manière générale, X est Z=o p-1 représenté par le polynôme X(D)=LxZD`, dont les Z=o coefficients sont donnés par son image binaire. La somme de deux symboles X,YE F8 ={0,1,...,7} correspond à la somme bit-à-bit de X et Y. Leur produit est défini par le reste modulo P(D) du produit des deux polynômes p-1 p-1 X(D)=LxZD` et Y(D)=LyZD` . Z=o Z=o Nous allons considérer un code non-binaire défini par une unique contrainte linéaire sur F8: 3X+4Y+6Z =0 (7) On rappelle que dans ce cas L = A = F8 . En utilisant la représentation binaire des éléments de F8 et plus précisément l'isomorphisme (6) pour représenter 3,4,6E L et l'isomorphisme (3) pour représenter X,Y,Z E A, l'égalité ci-dessus devient (1 + D)(xo + x1D+ x2D2) +D2 (yo + y1D+y2D2) (8) +(D2 + D) (zo + z1D + z2D2 )= 0 soit encore, en tenant compte de D3=1+D [P(D] xo+xz+y1+z1+z2=0 xo+x1+x2+y1+y2+zo+z1 =0 x1+x2+yo+y2+zo+z1+z2=0 L'expression (10) peut donc aussi se traduire de manière matricielle : 1 0 1 xo 0 1 0 yo 0 1 1 zo 1 1 1 x1+0 1 1 y1+1 1 0 z1 = 0 ~0 1 11x4) 1\1 0 1)\y2 J 1\1 1 11z2 J La matrice de contrainte H E M13(F8) et son image binaire Hbin E M39(F2) s'obtiennent respectivement à partir des équations (7) et (10). On a en définitive H=(3 4 6) (11) r1 0 1 0 1 0 0 1 11 Hbfn = 1 1 1 0 1 1 1 1 0 1 ~0 1 1 1 0 1 1 1 1J Les graphes bipartites correspondant respectivement à la matrice de contrainte H du code non-binaire et à la matrice de parité Hb;n de son image binaire sont 20 respectivement illustrés en Figs. 4A et 4B. On notera dans la présence dans le graphe binaire de nombreux cycles courts (de longueur 4) alors que le graphe non-binaire est acyclique. De manière générale, l'image binaire d'un code non-25 binaire, acyclique ou à faible nombre de cycles, peut 11 (9) (10) et (12) 12 comprendre un nombre important de cycles du simple fait de la représentation binaire choisie. L'homme du métier comprendra que certaines représentations binaires puissent être équivalentes du point de vue algébrique mais conduire à des performances différentes en termes de décodage. Le problème à la base de l'invention est par conséquent de proposer une méthode de décodage d'un code non binaire susceptible de représentation par graphe bipartite, par exemple d'un code LDPC non binaire, qui ne présente pas les inconvénients précités, c'est-à-dire qui allie une faible complexité de décodage à un faible taux d'erreurs. EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode de décodage d'un code non binaire, en particulier d'un code LDPC non binaire, susceptible d'une représentation par graphe bipartite avec N noeuds de variables et Al noeuds de contraintes, les variables prenant leurs valeurs dans un alphabet A non binaire et étant linéairement contraintes au moyen d'une matrice de contraintes, chaque variable étant représentée par une pluralité p de valeurs binaires. Selon cette méthode : - on génère pour chaque variable une pluralité p > p de valeurs binaires, dites valeurs binaires étendues, obtenues par p combinaisons linéaires distinctes à coefficients dans F2 desdites p valeurs binaires, hormis la combinaison nulle ; 13 - on calcule une matrice de parité, Hbin, dite matrice de parité étendue, représentant des contrôles de parité sur les valeurs binaires étendues des variables, dits contrôles de parité étendus, lesdits contrôles de parité étendus étant induits par les contraintes sur lesdites variables ; - on effectue un décodage itératif à passage de messages à l'aide d'un second graphe bipartite, dit graphe étendu, représentant la matrice de parité étendue et reliant les contrôles de parité étendus aux valeurs binaires étendues des variables ; - on détermine les valeurs binaires de chaque variable à partir de ses valeurs binaires étendues, obtenues au terme du décodage itératif. Par exemple, l'alphabet A pourra être constitué de q=2p éléments et p=q-1. On complète avantageusement ladite matrice de parité étendue, Hbin, en ajoutant des lignes supplémentaires, lesdites lignes supplémentaires étant obtenues au moyen de combinaisons linéaires distinctes à coefficients dans F2 des lignes existantes, hormis la combinaison nulle, chaque ligne de la matrice ainsi complétée définissant un contrôle de parité étendu, le graphe étendu reliant alors l'ensemble des valeurs binaires étendues des variables à l'ensemble des contrôles de parité étendus de la matrice Hbin ainsi complétée. Par exemple, le nombre de lignes supplémentaires ajoutées sera de q-p-1.30 14 De préférence, au moins une partie des valeurs binaires étendues de chaque variable est initialisée à l'aide des valeurs binaires de celle-ci. Selon une première variante, pour au moins une itération du décodage itératif, les valeurs binaires étendues de chaque variable sont soumises à un décodage à maximum de vraisemblance pour obtenir des valeurs binaires étendues estimées vérifiant un ensemble de contraintes induites par lesdites p combinaisons linéaires. On remplace alors, pour chaque variable, lesdites valeurs binaires étendues par lesdites valeurs binaires étendues estimées pour poursuivre le décodage itératif. Selon une seconde variante, pour au moins une itération du décodage itératif, les messages transmis par les valeurs binaires étendues de chaque variable sont corrigés au sens du maximum de vraisemblance pour vérifier un ensemble de contraintes induites par lesdites p combinaisons linéaires. On remplace alors, pour chaque variable, lesdits messages transmis au moyen des dits messages corrigés pour poursuivre le décodage itératif. Selon une troisième variante, pour au moins une itération du décodage itératif, les messages reçus par les valeurs binaires étendues de chaque variable sont corrigés au sens du maximum de vraisemblance pour vérifier un ensemble de contraintes induites par lesdites p combinaisons linéaires. On remplace alors, pour chaque variable, lesdits messages reçus au moyen des dits messages corrigés pour poursuivre le décodage itératif. 15 Selon un mode de réalisation particulier, on utilise en outre un graphe auxiliaire reliant les valeurs binaires aux valeurs binaires étendues des variables, ledit graphe auxiliaire représentant les combinaisons linéaires permettant de générer les secondes à partir des premières. Dans ce cas, l'étape de décodage itératif peut comprendre au moins une première phase de passage de messages entre les valeurs binaires et les valeurs binaires étendues des variables, à travers ledit graphe auxiliaire, et une seconde phase de passage de messages entre les valeurs binaires des variables et les contrôles de parité étendus, à travers ledit graphe étendu. BRÈVE DESCRIPTION DES DESSINS La Fig. 1 représente le graphe bipartite d'un exemple de code LDPC non binaire ; La Fig. 2 représente schématiquement le principe de l'information extrinsèque dans un décodage itératif à passage de messages; La Fig. 3 représente un exemple de cycle dans un graphe bipartite ; Les Figs. 4A et 4B représentent respectivement un graphe bipartite d'un code non binaire et le graphe bipartite correspondant de son image binaire ; La Fig. 5 représente les matrices de parité respectives d'un exemple de code non binaire, de son image binaire et de son image binaire étendue ; 16 La Fig. 6 représente schématiquement une méthode de décodage d'un code non-binaire utilisant une représentation binaire étendue, selon un mode de réalisation de l'invention. La Fig. 7 représente un premier exemple de graphe bipartite associé à une représentation binaire étendue d'un code non binaire et permettant un décodage selon la méthode de la Fig. 6. La Fig. 8 représente un second exemple de graphe bipartite associé à la même représentation binaire étendue du code non binaire et permettant également un décodage selon la méthode de la Fig. 6. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS On considère à nouveau un code correcteur d'erreurs, non binaire, défini sur un alphabet A, corps de cardinal q, et susceptible d'une représentation par un graphe bipartite avec N variables et Al contraintes. Nous supposerons dans la suite, sans perte de généralité, que ce code correcteur est un code LDPC non binaire. Par définition, le code non binaire est défini par un ensemble de Al équations linéaires (ou contraintes) à N inconnues (ou variables) prenant leurs valeurs dans A. On supposera, là encore sans perte de généralité, que q=2p. On peut alors identifier chaque symbole du code à un vecteur de p valeurs binaires, c'est-à-dire un élément de Fp, grâce à l'isomorphisme d'espace vectoriel (3). Le vecteur ou p-uplet de valeurs binaires donne la représentation binaire d'un 17 symbole de l'alphabet non-binaire. La multiplication d'un symbole de A par un coefficient appartenant à L au sein d'une équation linéaire peut être identifiée à un F2-endomorphisme sur A, conformément à la convention (4). Ce coefficient de L et donc cet F2-endomorphisme sur A peut être représenté de manière générale par une matrice de taille pxp à coefficients dans F2. L'idée principale à la base de l'invention est d'utiliser une représentation binaire étendue des symboles de A ainsi que des F2-endomorphismes sur A. Par représentation binaire étendue d'un élément du corps A, on entend de manière générale une représentation binaire redondante de cet élément utilisant un nombre p de bits strictement supérieur à p (de manière générale supérieur à log2(q)). Chacun des p bits de cette représentation binaire étendue s'exprime avantageusement comme une combinaison linéaire des p valeurs binaires de la représentation binaire avec des coefficients dans F2. Par exemple un symbole X de A pourra être représenté par (x0xl,.. dans la représentation binaire et par dans la représentation binaire étendue avec : p-1 al=Es'x1, s'EF2 (13) l=o où les (s°,si,...,sp'~ i=1,...,q-1 décrivent les q-1 combinaisons possibles de p bits (q combinaisons 18 hormis la combinaison nulle). Dans ce cas là, on a p=qù1. La relation (13) peut encore s'exprimer sous forme matricielle : (14) où Sp est la matrice de taille px(qù1) dont les colonnes sont qù1 combinaisons possibles de p bits. 10 Autrement dit, Sp est la matrice génératrice du code Toute représentation binaire étendue de A induit de manière canonique une représentation binaire étendue 15 des endomorphismes sur A. En effet, soit un vecteur ue de dimension p une représentation binaire étendue d'un élément X E A, (p(X) est un élément de A qui possède également un représentation binaire étendue, ve. L'endomorphisme cp peut ainsi être représenté par une 20 matrice binaire de taille p x p. Un code non binaire à Al contraintes et N variables peut alors être décrit par une matrice binaire étendue He E MMpj(F2), de dimension MpxNp. 25 Nous envisagerons une représentation binaire étendue d'un code non binaire C c AN où A est un ensemble de cardinal q=2p et par conséquent isomorphe à F. Le code non binaire est défini par une matrice I le MMN(L) dont les éléments hm n E L sont des 30 endomorphismes sur A :5 C = Ker(H) c AN N (X1,...,XN) EhmnXn =0,Vm=1,...,M n=1 Chacune des Al équations figurant dans (15) correspond à une contrainte (c'est-à-dire à une équation linéaire sur les variables non binaires Xn). La matrice H est la « matrice de parité » du code non binaire C. Soit h E L et mh E MP(F2) son image binaire au sens de l'isomorphisme (6). Pour fixer les idées, si p=3 et si h est l'endomorphisme sur A qui à tout élément X fait correspondre l'élément 3X, l'image binaire de h peut s'écrire, comme vu plus haut, en relation avec les expressions (11) et (12) . (1 0 11 mh= u ~0 1 1J Revenant au cas général, et considérant l'ensemble Zq ={0,1,...,qû1} des entiers modulo q, la matrice mh E Mp(F2) induit un endomorphisme Oh sur Zq Fp h >Fp 111 Z ~Z 9 9 (15) (16) (17) où il est la bijection qui à tout p-uplet (bo,bl,..,bp_1) associe l'entier z=bo+b,21+b222+...+bp_,2p'. Réciproquement ,0-1 associe à chaque entier de Zq sa décomposition binaire sur p bits. L'opération de XOR bit-à-bit sur Fp munit Zq d'une structure de F2-espace vectoriel. On définit l'opération A sur Zq par : 10 iAj=i(i-'(i)XORi-'(j)) (18) 0 vérifie alors la propriété : Oh(ZAJ)-Oh(i)AOh(J), Vi,J E Ziq (19) 15 On définit une matrice Mh E Mq_I(F2) de taille (q-1)x(q-1) par : M (i 1, if i = h (i) bi, j E Zq h ,J)= 0, sinon 20 où Z* =Z -{0}. Cette représentation ne fait pas intervenir l'élément nul de Zq, car l'on a trivialement Oh(0)=0. La matrice Mh est appelée « matrice binaire 25 étendue » associée à l'endomorphisme hE L. Dans la définition précédente, on notera que l'ensemble Zq est uniquement utilisé afin d'indexer les lignes et les colonnes de la matrice Mh E Mq_1(F2) par des entiers (20) j)E Zqx Zq, plutôt que par des symboles de l'alphabet A. On remarquera que si hE L est un endomorphisme inversible (ou, de manière équivalente si m h E MP(FZ) est une matrice inversible), alors induit une permutation sur Zq et par suite Mh est une matrice de permutation, ne contenant qu'un seul « 1 » par ligne et par colonne. Nous illustrerons la construction de la matrice binaire étendue dans le cadre de l'exemple précédent A=F8, h = 3 E L, dont on rappelle que l'image binaire est : mh Les lignes de mh définissent respectivement 0(1), 0(2) et 0(4). Ainsi 0(1)=5, entier dont la décomposition binaire correspond à la première ligne de mh. De la même manière, on 0(2)=7 et 0(4)=6. On déduit les valeurs sur les autres éléments de Z8 indexant A à l'aide de (19) . $(3)=$(1)A4(2)=2 4(5)=4(1)A4(4)=3 4(6)=4(2)A4(4)=1 $(7)= $(1)^$(2)^$(4)= 4 (21) Finalement, la matrice binaire étendue Mh associée à h est donnée par : r0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 Mh = 0 0 0 0 0 1 0 (22) 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 On procède ainsi pour chacun des M x N coefficients (c'est-à-dire pour chacun des endomorphismes) hmnE L. La matrice obtenue en remplaçant chaque élément hmn de He MM N(L) par la matrice binaire étendue associée Mh E Mq_1(FZ), définie par (20), est une matrice notée Heu, E MM(q_1),N(q_1)(F2), appelée matrice binaire étendue associée à la matrice de parité H du code non binaire C. Le code binaire Cbin=Ker(riein)c Fz (q-1) est appelé code binaire étendu associé au code non-binaire C=Ker(H)cAN. La Fig. 5 donne un exemple de matrice de parité H, de son image binaire Hbzn et de son image binaire étendue Hbin, construite comme décrit précédemment. Par souci de simplification, seules les valeurs non nulles ont été indiquées dans cette dernière. La matrice de parité H est celle d'un code LDPC non binaire défini sur F8, à N=6 variables et M=3 25 contrôles. 23 Son image binaire, Hest une matrice de taille 9x18, construite à partir de matrices élémentaires 3x3, chaque matrice élémentaire correspondant à un coefficient de H, c'est-à-dire un endomorphisme sur F8 et donnant une représentation binaire de ce dernier (selon (6)). Chaque matrice élémentaire est « pondérée » au sens où les numéros de ligne et de colonne correspondent à des poids binaires 20,21,22 L'image binaire étendue Hbin est une matrice de taille 21x42, construite à partir de matrices élémentaires de taille 7x7, chaque matrice élémentaire correspondant là encore à un coefficient de la matrice H, c'est-à-dire un endomorphisme sur F8 et donnant une représentation binaire étendue de ce dernier (selon (20)). Au contraire de l'image binaire, les lignes et colonnes des matrices élémentaires ne sont ici pas « pondérées » mais correspondent chacune à un élément de F8 (hormis l'élément nul). On remarque que la matrice Hbin est peu dense. Dans le cas présent, elle ne contient par ligne que quatre valeurs non nulles (« 1 ») dispersées parmi 42. Le graphe associé à cette matrice présente par conséquent sensiblement moins de cycles que l'image binaire Hbin. Les mots du code non binaire C peuvent s'exprimer à l'aide de la représentation binaire étendue des éléments de A. En effet, soit (X1,...,XN)E C c AN un mot du code non binaire. VnE{1,...,N}, notons (xn,,xn,l,...n,p_1)EFp l'image binaire de Xn et (anl,an,z, ,an,q_1~E FZ-1 son image binaire étendue, obtenue par (14), c'est-à-dire : =(xno,xn1,...,xn,p-1)SP (23) alors (al l,a12,...,alq 1,...,aNl,aNZ,...,aN,9 1) bin Fz (q-1) On notera dans la suite Sp le code binaire dont la matrice génératrice est Sp. Réciproquement, soit la séquence binaire : ( a1,1 , a1,z - .al,q-11...,aN1,aN2,...,aN,q-1 E Cbin îF2N(g 1) (24) telle que VnE {1,...,N} , (an,l,an,z, ..,an,q_1)E Sp c Fr1 , autrement dit, telle que : 3(xno,xnl,...,xn,p-1)E Fp tel que (anl,anz,...,an,q 1)û(xno,xnl,...,xn p 1)s Soit X1,e A, le symbole dont l'image binaire est (xn,o,xn,l, ,xn,p_l)E Fp Alors (Xl,...,XN)E C c AN est un mot de code non-binaire et (an,l,an,z, ,an,q_l)E FZ-1 est l'image binaire étendue de X1,, pour tout nE 11,...,N1. Il en résulte que l'application qui associe à un mot de code non-binaire (Xl,...,XN)E C son image binaire étendue (al,l,al,2~"'gal,q l,...,aN,l,aN,2~"'~aN,g-1)E Cbin est un isomorphisme de C sur Cb;n nSp où Sp =Sp x...xSp c FN (q-1) est l'espace vectoriel produit de N copies de Sp. Nous donnerons ci-après un exemple simple de représentation binaire d'un code non binaire. Soit le code non binaire défini sur A = F8 par l'unique équation de parité (7). On a p=3 et q=8. La matrice S3 est définie par : rl 0 1 0 1 0 11 S3 = 0 1 1 0 0 1 1 (25) ~0 0 0 1 1 1 1J La représentation binaire étendue (a1,a2,...,a,) d'un élément X de A peut être obtenue à partir de sa représentation binaire (xo,xäx2) au moyen de (a1,a2,...,a,)=(xo,x1,x2)S3, soit encore a1=xo, a2=xä a3=xo+xä a4=x2, a,=xo+x2, a6=x1+x2, a,=xo+x,+x2 (26) On comprendra que les variables a1,a2,...,a, représentent les F2-combinaisons linéaires possibles des valeurs binaires xo,xl,x2. La représentation binaire étendue (b1,b2,...,b,) de Y et celle, (c1,c2,...,c,), de Z est obtenue de la même façon, à savoir (b1,b2,...,b,)=(y0,y1,y2)S3 et (c1,c2,...,c,)=(z0,z1,z2)S3 . Le système d'équations (10) peut alors être réécrit sous la forme : (x0+x2)+y1+(Z1+z2)=0 1I(x0+x1+x2)+(y1+y2)+(z0+z1)=0 L(x1+x2)+(.y0+.y2)+(z0+z1+z2)=0 (27) 26 soit, de manière équivalente, en faisant intervenir la représentation binaire étendue : la5+b2+c6=0 a,+b6+c5 =0 (28) la6+b5+c,=0 ce qui donne sous forme matricielle : r0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 Ol I0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 °=° ~o 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1J (29) où u = (al,..,a7,bl,..,b7,cl,..,c7)E Cbin. Cette matrice contient 3 matrices élémentaires correspondant chacune à un endomorphisme sur F8 (les coefficients du code non- linéaire) et 3 lignes correspondant aux 3 équations du système (28). On remarque que la matrice précédente ne définit pas de contrôle de parité pour certains bits de la représentation binaire étendue de X,Y,Z. Afin que chacun des 21 bits a,,..,aäb,,..,bäc7 participe à un contrôle de parité, on rajoute à cette matrice des lignes supplémentaires qui peuvent se déduire par combinaisons linéaires des lignes déjà présentes. Ainsi par exemple, en additionnant les deux premières lignes de la matrice (29), ou de manière équivalente en ajoutant les deux premières équations du système (28), on obtient : (a5 + a7) + (b2 + b6) + (c5 + c6) = 0 (30) ce qui, compte tenu de a5+a7=xo+x2+xo+x1+x2=x1=a2, b2 + b6 = b4 et C5 + co = C3 la matrice : peut se réécrire comme ligne n°3 de a2 +b4 +c3 = 0 (31) De manière similaire, en additionnant les lignes 10 n°1 et n°4, on obtient une ligne n°5 : b,+c1 =0 (32) en additionnant les lignes n°2 et n°4, on obtient une 15 ligne n°6 : a1+b3+c2=0 (33) et enfin, en additionnant les lignes 1,2 et 4, on 20 obtient une ligne 7 : a4+b1+c4 =0 (34) En définitive, la matrice ainsi complétée n'est 25 autre que la matrice binaire étendue Hbin : Hbin r 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 28 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 00000io 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 (35) Le graphe bipartite associé à cette matrice de parité ne contient aucun cycle, chaque bit al, 1 ou ci n'apparaissant que dans un seul contrôle de parité. De manière générale une matrice binaire étendue Hbin ne contient un cycle que dans la mesure où la matrice non binaire H en contient elle-même : les cycles apparaissant dans Hbin sont en fait induits par les cycles déjà présents dans H. Après avoir donné une représentation binaire étendue du code non binaire, nous exposerons ci-après la méthode de décodage selon l'invention mettant en oeuvre cette représentation. La Fig. 6 représente schématiquement sous forme d'organigramme une méthode de décodage d'un code non- binaire selon un mode de réalisation de l'invention. On considère comme précédemment un code correcteur d'erreurs C, non binaire et susceptible d'une représentation par graphe bipartite, G, le code étant défini par un ensemble de N variables X1,...,XN prenant leurs valeurs dans un alphabet non binaire A et un ensemble de Al contraintes dépendant linéairement desdites variables au moyen d'une matrice de contraintes H à coefficients dans L. On note q=Card(A) et p le plus petit entier tel que p >ûlog2(q), autrement dit p est le plus petit nombre de bits permettant une représentation binaire des symboles de A. Les valeurs des variables Xl,...,XN sont prises en compte à l'étape 610. Ces valeurs peuvent être reçues d'un émetteur à travers un canal de transmission ou bien lues d'un support d'enregistrement. Plus précisément chaque variable X, est représentée par p valeurs binaires x,4o,x,4l,...,xyu où x1zo est le LSB et x, p est le MSB. Ces valeurs binaires peuvent être dures ou souples de manière connue en soi. De même chaque contrainte non-binaire Y. correspond à p contrôles de parité ym,o'Ym,v•••'Ym,p qui doivent être vérifiés par les valeurs binaires o,x, »...,x, p . La matrice de contraintes H est par ailleurs connue du décodeur. A l'étape 620, on génère pour chaque variable X, une représentation binaire étendue (anl,...,anp) de X, au moyen d'une pluralité p de combinaisons linéaires distinctes à coefficients dans F2 de ses valeurs binaires x,o,xnl,...,telle que p>p. Les valeurs sont dénommées valeurs binaires de la représentation binaire étendue de X, ou, plus simplement, valeurs binaires étendues de X,. On peut générer ainsi jusqu'à qû1 valeurs binaires étendues. 30 A l'étape 630, on calcule une matrice de parité étendue Hbin permettant d'obtenir les contrôles de parité associés à chaque contrainte (non-binaire) en fonction des valeurs binaires étendues des différentes variables X1,...,XN . Les contrôles ainsi obtenus sont dénommés contrôles de parité étendus. A l'étape 640, on complète avantageusement mais non nécessairement, la matrice de parité Hbin, en ajoutant des lignes supplémentaires, lesdites lignes supplémentaires étant obtenues au moyen de combinaisons linéaires distinctes à coefficients dans F2 des lignes existantes, hormis la combinaison nulle. On peut ainsi ajouter jusqu'à q û p -1 lignes supplémentaires pour obtenir un total de qû1 lignes par contrainte, chaque ligne de la matrice ainsi complétée étant associée à un contrôle de parité étendu, c'est-à-dire portant sur des valeurs binaires étendues des variables. De manière plus générale, on peut obtenir une matrice parité Hbin à partir de p combinaisons linéaires distinctes par contrainte, chacune d'entre elles étant une combinaison à coefficients dans F2 des lignes existantes (hormis la combinaison nulle). Ces combinaisons peuvent ne pas inclure certaines lignes existantes, voire toutes ces dernières. A l'étape 650, on effectue un décodage itératif à passage de messages au moyen d'un graphe bipartite G reliant les valeurs binaires étendues des variables aux valeurs binaires étendues des contrôles. Les messages échangés entre les noeuds de variables et les noeuds de contrôle peuvent être des probabilités, des rapports de vraisemblance logarithmiques (LLRs), ou simplement des 31 valeurs binaires. Les messages peuvent être calculés de manière connue en soi à l'aide d'algorithmes de type « Sum-Product », « Min-Sum », ou encore de leurs variantes corrigées « Normalized Min-Sum », « Self- corrected Min-Sum ». On trouvera par exemple une description des deux premiers dans la thèse de N. Wiberg précitée. Pour la variante « Normalized Min-Sum » on pourra se référer notamment à l'article de J. Chen et al. Intitulé « Near Optimum universal belief propagation based decoding of low density parity check codes, IEEE Trans. on Comm., 50(3), pages 406-414, 2002. Pour la variante « Self-corrected Min-Sum » on pourra se référer à l'article de V. Savin intitulé « Self-Corrected Min-Sum of LDPC codes », IEEE Int. Symp. on Information Theory (ISIT), Toronto, Canada, 2008. Le décodage itératif se poursuit jusqu'à ce qu'un critère d'arrêt soit vérifié (contrôles de parité vérifiés, nombre maximum d'itérations atteint, valeurs absolues des LLRs franchissant une valeur de seuil, etc.) A l'étape 660, on détermine enfin les valeurs binaires de chaque variable à partir de ses valeurs binaires étendues ainsi obtenues. La Fig. 7 représente un exemple de graphe bipartite G associé à une représentation binaire étendue du code non binaire C et permettant un décodage selon la méthode de la Fig. 6. L'exemple illustré est celui du code non binaire défini sur l'alphabet A = F8 par la matrice de parité H donnée en (1). On a ici q=8 et p=3, N=6 et M=3. Les variables sont notées X1,X2,...,X6 et les contraintes sont notés Y,Y2,Y3. Chaque variable est un élément de F8. Chaque variable X, est représentée par son image binaire, à savoir trois valeurs binaires (xn,0,xn,1,xn,2) Chaque contrainte Y. est représentée par son image binaire, à savoir trois contrôles de parité étendus (Y m,0,.Ym,1' Ym,2) Dans l'exemple illustré, la représentation des variables a été étendue au nombre maximal de bits, à savoir qù1=7 bits (autrement dit p=7). De manière similaire, la représentation des contraintes a été étendue au nombre maximal de contrôles étendus. La représentation binaire étendue de la variable X, est ainsi notée (an1, v•••,an7) et celle de Y est notée (bm 1, bm 2, ... bm 7 ) La représentation étendue est obtenue de la manière suivante : • pour les variables X, an1 =xn0 = xnl an3 =xn0+xn1 an4 =xn2 (36) +xn2 (46=xnl+xn2 0+xnl+xn2 On voit ainsi que chaque bit de la représentation binaire étendue d'une variable s'exprime comme une combinaison de ses valeurs binaires. pour les contraintes Y. bm,l = Ym,O bm,2 = Ym,l bm,3 = Ym,O + Ym,l bm,4 ù Ym,2 (37) bm,s = Ym,o + Ym,2 bm,6 = Ym,l + Ym,2 bm,7 ùYm,O +Ym,l +Ym,2 On voit ainsi que chaque contrôle de parité étendu, s'exprime comme une combinaison linéaire de contrôles de parité de l'image binaire de cette contrainte. La matrice Hbin, dont les lignes correspondent aux contrôles de parité étendus bjm est de taille M(qû1)xN(qû1) c'est-à-dire 21x42. Cette matrice est donnée en Fig. 5. Sur le graphe de la Fig. 7, on a représenté les variables par des hexagones, les valeurs binaires étendues des variables par des cercles, et les contrôles de parité étendus par des carrés. Seule la partie du graphe correspondant au contrôle Y a été représentée pour ne pas surcharger la figure. Bien entendu, les contrôles binaires étendus représentant les contraintes Y2 et Y sont également 34 reliées aux valeurs binaires étendues des noeuds de variables, mais les arêtes correspondantes n'ont pas été représentées. On a représenté en grisé les valeurs initiales des variables servant à initialiser le décodage. Plus précisément, les valeurs binaires xn,o,xn,l,xn2 servent à initialiser respectivement les valeurs binaires étendues an,l,an,2,an,4. Les autres valeurs binaires étendues peuvent être considérées comme des effacements, c'est- à-dire comme des inconnues (par exemple valeur de probabilité égale à 0,5 ou valeur de LLR égale à 0). Selon une variante, les autres valeurs binaires étendues sont également initialisées au moyen de l'équation (36) ci-dessus. Après le décodage itératif à passages de messages, on obtient les valeurs binaires décodées des variables X1,X2,...,X6 à partir de : =a (38) autrement dit, on vient simplement récupérer les valeurs binaires à partir des valeurs binaires étendues, de façon symétrique à l'étape d'initialisation. On comprendra que la représentation binaire étendue des variables ne comprend pas nécessairement toutes les F2-combinaisons linéaires des valeurs binaires de ces variables. De même, la représentation binaire étendue des contraintes ne comprend pas 35 nécessairement toutes les F2-combinaisons linéaires des contrôles de parité associés à ces contraintes. Dans tous les cas, le fait d'utiliser une représentation étendue sur p > p valeurs binaires pour les variables et/ou p» p équations de parité permet d'obtenir une matrice de densité moins dense et un graphe bipartite présentant un plus faible nombre de cycles. On notera que, de manière générale, le nombre p' d'équations de parité de la matrice Hbin peut être 10 différent de p. Dans le mode de réalisation décrit précédemment, les noeuds de variables 710 (symboles non-binaires) et 720 (valeurs binaires étendues) n'échangent des messages que lors de la phase d'initialisation et lors 15 de la phase de récupération des valeurs décodées, au terme du décodage itératif. On peut avantageusement exploiter le fait que les valeurs binaires étendues anj,an2,...,anq_1 forment un mot de code de Sp, ou d'un mot de code raccourci lorsque le 20 nombre de valeurs binaires étendues vérifie p La Fig. 8 représente un autre exemple de graphe 10 bipartite du même code non binaire. On a désigné par 810 les noeuds associés aux valeurs binaires de chaque variable. Les références 820 et 840 sont respectivement identiques aux références 720 et 740 de la Fig. 7. 15 On a désigné par 815 le graphe reliant les valeurs binaires et les valeurs binaires étendues des variables. Ce graphe représente les p combinaisons linéaires permettant de passer des premières aux secondes. Le graphe 815 sera dénommé dans la suite 20 graphe auxiliaire du graphe étendu 800. L'étape de décodage itératif comprend au moins une première phase de passage de messages entre les valeurs binaires et les valeurs binaires étendues des variables, à travers le graphe auxiliaire 815, et une 25 seconde phase de passage de messages entre les valeurs binaires étendues des variables et les contrôles étendus, à travers le graphe 800. On a ainsi un cycle de passage de messages à trois niveaux (810 -> 820 -> 840 -> 820 -> 810). 38 D'autres stratégies de passages de messages peuvent être envisagées par l'homme du métier sans sortir du cadre de la présente invention.5 REVENDICATIONS1. Méthode de décodage d'un code non binaire, en particulier d'un code LDPC non binaire, susceptible d'une représentation par graphe bipartite avec N noeuds de variables et Al noeuds de contraintes, les variables prenant leurs valeurs dans un alphabet A non binaire et étant linéairement contraintes au moyen d'une matrice de contraintes (H), chaque variable étant représentée par une pluralité p de valeurs binaires, caractérisée en ce que : - on génère (620) pour chaque variable une pluralité p > p de valeurs binaires, dites valeurs binaires étendues, obtenues par p combinaisons linéaires distinctes à coefficients dans F2 desdites p valeurs binaires, hormis la combinaison nulle ; - on calcule (630) une matrice de parité, dite matrice de parité étendue, représentant des contrôles de parité sur les valeurs binaires étendues des variables, dits contrôles de parité étendus, lesdits contrôles de parité étendus étant induits par les contraintes sur lesdites variables ; - on effectue (650) un décodage itératif à passage de messages à l'aide d'un second graphe bipartite (700,800), dit graphe étendu, représentant la matrice de parité étendue et reliant les contrôles de parité étendus aux valeurs binaires étendues des variables ; - on détermine (660) les valeurs binaires de chaque variable à partir de ses valeurs binaires étendues, obtenues au terme du décodage itératif. 40 2. Méthode de décodage selon la revendication 1, caractérisée en ce que l'alphabet A est constitué de q=2p éléments et que p=qû1. 3. Méthode de décodage selon la revendication 1 ou 2, caractérisee en ce que l'on complète (630) ladite matrice de parité étendue, Hbin, en ajoutant des lignes supplémentaires, lesdites lignes supplémentaires étant obtenues au moyen de combinaisons linéaires distinctes à coefficients dans F2 des lignes existantes, hormis la combinaison nulle, chaque ligne de la matrice ainsi complétée définissant un contrôle de parité étendu, le graphe étendu reliant alors l'ensemble des valeurs binaires étendues des variables à l'ensemble des contrôles de parité étendus de la matrice Hbin ainsi complétée. 4. Méthode de décodage selon les revendications 2 et 3, caractérisée en ce que le nombre de lignes supplémentaires ajoutées est de q û p -1. 5. Méthode de décodage selon l'une des revendications précédentes, caractérisée en ce qu'au moins une partie des valeurs binaires étendues de chaque variable est initialisée à l'aide des valeurs binaires de celle-ci. 6. Méthode de décodage selon l'une des revendications précédentes, caractérisée en ce que, pour au moins une itération du décodage itératif, les valeurs binaires étendues de chaque variable sont 41 soumises à un décodage à maximum de vraisemblance pour obtenir des valeurs binaires étendues estimées vérifiant un ensemble de contraintes induites par lesdites p combinaisons linéaires, et que l'on remplace, pour chaque variable, lesdites valeurs binaires étendues par lesdites valeurs binaires étendues estimées pour poursuivre le décodage itératif. 7. Méthode de décodage selon l'une des revendications 1 à 5, caractérisée en ce que, pour au moins une itération du décodage itératif, les messages transmis par les valeurs binaires étendues de chaque variable sont corrigés au sens du maximum de vraisemblance pour vérifier un ensemble de contraintes induites par lesdites p combinaisons linéaires, et que l'on remplace, pour chaque variable, lesdits messages transmis au moyen des dits messages corrigés pour poursuivre le décodage itératif. 8. Méthode de décodage selon l'une des revendications 1 à 5, caractérisée en ce que, pour au moins une itération du décodage itératif, les messages reçus par les valeurs binaires étendues de chaque variable sont corrigés au sens du maximum de vraisemblance pour vérifier un ensemble de contraintes induites par lesdites p combinaisons linéaires, et que l'on remplace, pour chaque variable, lesdits messages reçus au moyens des dits messages corrigés pour poursuivre le décodage itératif.30 42 9. Méthode de décodage selon les revendications précédentes, caractérisée en ce qu'elle utilise en outre un graphe auxiliaire (815) reliant les valeurs binaires aux valeurs binaires étendues des variables, ledit graphe auxiliaire représentant les combinaisons linéaires permettant de générer les secondes à partir des premières. 10. Méthode de décodage selon la revendication 9, caractérisée en ce que l'étape de décodage itératif comprend au moins une première phase de passage de messages entre les valeurs binaires et les valeurs binaires étendues des variables, à travers ledit graphe auxiliaire (815), et une seconde phase de passage de messages entre les valeurs binaires des variables et les contrôles de parité étendus, à travers ledit graphe étendu (800).