Brevet FR2902584A1 — publié le 20071221

L'invention concerne l'utilisation de codes LDPC dans des transmissions, et en particulier le décodage de codes LDPC. Un code LDPC est un code correcteur d'erreur permettant d'approcher de la limite théorique de transmission de Shannon. Les codes LDPC sont des codes linéaires en bloc ayant des matrices de parité creuses de vérification de parité. Soit H(M,N) une matrice de parité, N étant la taille du mot de code. Pour N=8 et M=4, un exemple de matrice H est le suivant : ni n2 n3 n4 n5 n6 n7 n8 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 m2 H= 1 0 1 0 0 1 0 1 m3 0 1 0 1 0 1 1 0 m4 Ce même code peut être représenté de manière équivalente par le graphe de Tanner de la figure 1, qui établit chaque équation de parité par les relations entre les noeuds de vérification ml à m4 et les noeuds correspondant aux bits du mot de code nl à n8. Le décodage d'un code LDPC étant relativement simple et pouvant être effectué par des éléments matériels en parallèle, l'utilisation de codes LDPC est de plus en plus fréquente dans les télécommunications. La norme DVB-S2 de diffusion numérique par satellite utilise notamment un code LDPC irrégulier pour la protection des données descendantes. Lors de la conférence intitulée 2nd International Symposium on Turbo_Codes and Related Topics tenue à Brest en 2000 durant le second symposium international sur les turbo codes, des codes LDPC de la classe IRA pour Irregular Repeat and Accumulate ont été présentés. Ces codes présentent la propriété de pouvoir être générés par un algorithme d'encodage linéaire simple. Ces codes présentent en outre d'excellentes performances. Les procédés de décodage des codes LDPC actuellement utilisés mettent en oeuvre des calculs itératifs sur les symboles reçus, jusqu'à ce que les équations de parité convergent. Ces calculs itératifs requièrent un grand nombre d'opérations, ce qui implique un temps de traitement et un coût du circuit de réception importants. Il existe donc un besoin pour un circuit de décodage résolvant un ou plusieurs de ces inconvénients. L'invention porte ainsi sur un circuit de décodage comprenant : - des première et deuxième zones de mémoire vive, comprenant chacune au moins n lignes de stockage de P métriques, les métriques de chaque ligne définissant un polynôme de degré P-1 ; -une interface de réception de métriques d'un canal, inscrivant ces métriques sous formes de n paquets de P métriques dans la première zone; - une mémoire non volatile mémorisant la structure d'une matrice de parité présentant i lignes et j colonnes et dont chaque élément définit un polynôme de degré P-1 dont les coefficients sont booléens, cette mémoire mémorisant le nombre de coefficients non nuls pour chaque position (i,j), cette mémoire mémorisant en outre un couple comprenant le degré s associé à chaque terme dont le coefficient est non nul de chaque polynôme et une valeur de j associée; -un premier multiplicateur polynomial multipliant modulo XP-1 le polynôme d'une ligne j de la première zone par un monôme de degré s, s pouvant être interprété comme un opérateur réalisant un décalage circulaire ; - un module de contrôle parcourant la mémoire non volatile pour fournir séquentiellement la valeur j et le degré s de chaque couple de valeurs respectivement à la première zone et au premier multiplicateur ; -un module de mise à jour présentant : -une mémoire tampon recevant P métriques dont l'amplitude est égale à la différence entre P métriques de la ligne j de la deuxième zone et les P métriques fournies par le premier multiplicateur pour chaque premier coefficient non nul associé à chaque position dans la matrice de parité, ou recevant P métriques d'amplitude égale aux métriques de la ligne j de la deuxième zone pour les autres coefficients non nuls associés à chaque position dans la matrice de parité ; -un opérateur générant P métriques extrinsèques à partir de la différence entre P métriques de la ligne j de la deuxième zone et les P métriques fournies par le premier multiplicateur et inscrivant ces P métriques extrinsèques à la ligne j de la seconde zone ; -un circuit additionnant algébriquement les P métriques extrinsèques et les P métriques de la mémoire tampon ; -un deuxième multiplicateur polynomial réalisant l'opération inverse de celle réalisée par le premier multiplicateur sur le polynôme correspondant aux métriques fournies par le circuit d'addition; -un module cumulant les polynômes fournis par le deuxième multiplicateur pour une même position (i, j) et inscrivant les métriques correspondant à la ligne j de la première zone de mémoire vive lorsqu'un nombre de cumuls correspondant au nombre de coefficients non nuls mémorisé pour la position (i, j) a été effectué, le cumul des polynômes étant réinitialisé lors de l'inscription des métriques dans la première zone. Selon une variante, le circuit de décodage comprend un circuit de commande réinitialisant la seconde zone lorsque l'interface de réception inscrit les métriques dans la première zone. Selon encore une variante, le module de contrôle parcourt la mémoire non volatile de sorte que les couples fournis ne correspondent pas à des lignes successives de la matrice de parité. Selon une autre variante, le module de contrôle parcourt la mémoire non volatile de sorte que les lignes traitées successivement aient aussi peu que possible de coefficients non nuls en des positions identiques. Selon encore une autre variante, le module de contrôle parcourt la mémoire non volatile de sorte que les couples fournis correspondent successivement à des lignes impaires, puis successivement à des lignes paires. Par ailleurs, l'interface de réception comprend un décodeur souple appliquant les métriques du canal reçues dans la première zone mémoire. D'autres caractéristiques et avantages de l'invention ressortiront clairement de la description qui en est faite ci-après, à titre indicatif et nullement limitatif, en référence aux dessins annexés, dans lesquels : - la figure 1 illustre un graphe de Tanner illustrant des relations entre des bits de mots de code et des noeuds de parité ; - la figure 2 illustre un graphe de Tanner d'un code LDPC selon l'invention ; -la figure 3 illustre schématiquement un chemin de traitement selon l'état de la technique ; - la figure 4 illustre schématiquement un chemin de traitement selon l'invention. On va tout d'abord décrire une méthode de construction originale de codes LDPC de la classe IRA mentionnée précédemment. Cette méthode est destinée à organiser efficacement les données en vue de leur codage ou de leur décodage. Le principe de cette méthode est de lire un vecteur de bits par paquets de P bits consécutifs, puis d'interpréter ces paquets comme des polynômes. Les opérations se limitent alors à des opérations sur les polynômes formés. Le mot codé est destiné à présenter une redondance définie par R=r.P et présentera donc une longueur N=K+R=n.P Soit (uo,u,,...,u,_,) les K=k.P bits du mot à coder. Ces bits à coder sont groupés en k paquets de P bits consécutifs. Le je,,,e paquet de bits est traité comme un polynôme u (x) de degré maximum P-1 : . P-I U. (X)= u. X ,,,=o Une matrice G, de dimension (r,k) et dont les coefficients gij sont des polynômes gij(X) de degré maximum P-1 à coefficients dans {0, 1 }, est appliquée à la famille de polynômes U,(x). On construit alors les polynômes V ;(X) en multipliant le vecteur de polynômes U(X) par la matrice G : kù1 V'; (X) = gij (X)(Ji (X) mod (X -1) 0 i La mise en oeuvre des calculs des V ;(X) est ainsi simplement basée sur des décalages circulaires et (U0,...Uk-1, V'0, ..V'r-1) définit un code quasi-cyclique. De façon générale, l'opération X*A définira le produit de X par le 20 polynôme A dont on a supprimé le terme en XI'''. Un nombre r de polynômes vo(x),...,vr_l(x) de degré maximum P-1 est alors généré à partir des équations suivantes : r;.(x)+v.+,(x)=v';+,(x) o La mise en oeuvre des calculs des V;(X) est ainsi simplement basée sur une accumulation. On note alors W le vecteur suivant : 30 w =(u0(x),u,(x),...,Uk 1(x),V0(x),r,(x),...,v,._,(x)) 10 Comme les calculs des V'i(X) et des V;(X) sont basés respectivement sur des décalages circulaires et sur une accumulation, le codage de W appartient bien à la classe IRA. Le décodage en réception vise à déterminer les bits correspondant aux symboles reçus. Le décodage est généralement mis en oeuvre conformément à l'annexe A des directives de l'utilisateur ETSI TR 102.376 vl.1.1. Pour cela, un algorithme de décodage LDPC effectue de façon itérative des échanges entre des modules effectuant des calculs sur les noeuds de mots de code et les modules effectuant des calculs sur les noeuds de vérification. Un noeud de mot de code interagit avec plusieurs noeuds de vérification. Réciproquement, un noeud de vérification interagit avec plusieurs noeuds de mot de code. Le principe de l'algorithme consiste à déterminer la probabilité qu'un bit donné ait une valeur de 0 ou 1, en se basant sur les valeurs probables des autres bits dans le même mot de code. Les itérations font converger un bit vers sa valeur booléenne. En réception, un vecteur M présentant N métriques (mo,m,,...,mN_,) est fourni par un décodage souple. Ces N métriques sont groupées en n paquets de P métriques consécutives. Chaque paquet de métriques forme une ligne d'un tableau. Le jè'ne paquet de métriques est traité comme un polynôme M1(X) de degré maximum P-1 : PùI Mj(x)= mjP+sXs s==0 Le vecteur B=(Bo, .., Bi_1) où Bi est un polynôme de degré au plus P-1 à coefficients dans {0, 1}, est dans le code si et seulement si la relation H'B = 0 mod (XP -1) est vérifiée, avec la matrice H définie comme suit : 7 1 X* 1 1 0 G 1 1 30 H= H étant une matrice de parité réduite du code, dont la ligne i donne une équation de parité Ci, G étant une matrice ayant été définie précédemment. Lorsque le coefficient hie de H est non nul, ce coefficient est associé à hij(X) qui 10 est une somme de monômes Xs avec s E' U{*}. Alors, XsMM(X) mod(XP-1) participe à l'équation de parité Ci. On manipule ainsi P équations de parité simultanément. Cette organisation est indépendante de l'algorithme de décodage retenu. 15 Les coefficients des polynômes gij(X) peuvent notamment correspondre à une table définie dans l'annexe B du standard DVB-S2, pour un taux de codage donné. La jeII1e ligne d'une table de ce document peut par exemple servir à former la je'ne colonne de la matrice G préalablement remplie de 0. En notant c un entier figurant à une ligne j d'une table de l'annexe B du 20 standard DVB-S2, la division euclidienne de c par P s'écrit sous la forme c=i.P+s avec 0 s La figure 3 illustre schématiquement un circuit de décodage 3 de données décrit dans le document nommé High throughput LDPC decoder , IEEE Trans on VLSI Systems, 2002, écrit par Mrs Mansour et Shanbhag. 10 Ce circuit de décodage 3 présente une mémoire vive 31, initialisée avec les métriques du canal sous forme de n paquets de taille P identifiés par Mj, puis mise à jour durant le décodage. Le chemin de décodage présente en outre une mémoire vive 32 de mémorisation des métriques extrinsèques B, initialisées avec des valeurs nulles, puis mise à jour durant le décodage. Les mémoires 31 et 32 15 fournissent un paquet de taille P de métriques à un opérateur 33. L'opérateur 33 soustrait les métriques extrinsèques fournies par la mémoire 32 des métriques fournies par la mémoire 31. L'opérateur fournit le résultat à un circuit de mise à jour 34. Le résultat est mémorisé dans une mémoire tampon 35. Le circuit de mise à jour 34 comprend un module de mise à jour 36 effectuant une mise à jour des 20 métriques extrinsèques B en effectuant des corrections sur le résultat mémorisé dans la mémoire tampon 35. Les métriques extrinsèques mises à jour sont renvoyées à la mémoire 32. D'autre part, ces métriques mises à jour ainsi que le contenu de la mémoire tampon 35 sont fournis à l'opérateur 37. L'opérateur 37 ajoute les métriques qui lui sont fournies et inscrit le résultat du vecteur Mj mis à 25 jour dans la mémoire 31. La figure 4 représente schématiquement un circuit de décodage 4 modifié selon l'invention. Les éléments intégrés principalement ajoutés par rapport au circuit de la figure 3 sont entourés d'une ligne discontinue. Le circuit de décodage 30 4 comprend une mémoire vive 41, initialisée avec les métriques du canal sous forme de n paquets de taille P identifiés par Mj, puis mise à jour durant le décodage. Le circuit 4 comprend en outre une mémoire vive 42 de mémorisation des métriques extrinsèques B, initialisées avec des valeurs nulles, puis mise à jour durant le décodage. Le circuit 4 comprend en outre une mémoire non volatile 48, mémorisant le nombre pij pour chaque valeur de i et j dans la partie fonctionnelle ROMO, ainsi que des couples de valeurs de j et s dans la partie fonctionnelle ROM1. Lors du décodage, la mémoire 42 et la partie fonctionnelle ROM 1 mémorisant les couples (j,$) sont parcourues simultanément. Le contenu d'un couple (j,$) de la partie fonctionnelle ROM1 indique la ligne j de la mémoire 41 à lire et s indique le décalage circulaire à appliquer au contenu de cette ligne. Le décalage circulaire d'une ligne j de la mémoire 41 est effectué par un premier multiplicateur polynomial 49 multipliant le polynôme correspondant par le monôme Xs obtenu, modulo XP-1. Dans l'opérateur 54, les métriques B lues dans la mémoire 42 à une position correspondante sont transformées en leur opposées. Dans l'opérateur 43, la sortie de l'opérateur 54 est ajoutée au résultat fourni par le dispositif 49. L'opérateur 43 fournit en sortie le vecteur de métriques E(t). Pour le premier décalage circulaire effectué pour une valeur de pif donnée, c'est à dire pour le premier coefficient non nul à une position donnée dans la matrice de parité, l'organe 50 inscrit le vecteur de métriques E(t) dans la mémoire tampon 45 du module de mise à jour 44. Pour les décalages ultérieurs, l'organe 50 inscrit le vecteur de métriques issu de l'opérateur 54 (c'est à dire ùB) dans la mémoire tampon 45. Le vecteur de métriques inscrit dans la mémoire 45 sera noté Tamp(t). L'opérateur 43 fournit la valeur E(t) à un opérateur 46 du module 44. L'opérateur 46 génère des métriques extrinsèques et inscrit le vecteur de métriques B mis à jour dans la zone mémoire 42. La génération d'un vecteur de métriques B dans l'opérateur 46 est effectuée par des calculs connus en soi de l'homme de métier et ne sera donc pas détaillé. Le vecteur de métriques B mis à jour est ajouté algébriquement au vecteur de métriques Tamp(t) correspondant dans l'opérateur 53. Un décalage circulaire inverse est réalisé au niveau du dispositif 51, sur le résultat fourni par l'opérateur 53. Le résultat est ajouté au contenu d'une mémoire 52 par l'opérateur 47. Pour le dernier décalage circulaire effectué pour une valeur de donnée, le vecteur de métrique M mis à jour est inscrit dans la mémoire 41 et la mémoire 52 est remise à zéro. La première mise à jour des mémoires 41 et 42 a lieu après avoir parcouru les poi premières positions de la mémoire 42 et des couples (j,$). Une seconde mise à jour des mémoires 41 et 42 a lieu après avoir parcouru les pli positions suivantes de la mémoire 42 et des couples (j,$). Les mises à jour ultérieures sont effectuées de manière itérative de façon similaire. Une itération d'une ligne de la matrice H regroupe r mises à jour. La logique des opérateurs choisis, notamment les opérateurs 43, 53 et 54 est donnée à titre d'exemple, d'autres logiques pouvant aboutir au même résultat. L'algorithme standard mis en oeuvre dans le circuit de décodage décrit est le suivant : it est une variable entière initialement nulle définissant le nombre d'itérations ; itmax est une constante entière définissant le nombre maximal d'itérations autorisé ; i est un numéro de ligne de la matrice de parité H, c'est-à-dire un indice de l'équation de parité traitée ; j est un numéro de colonne de la matrice de parité H ; d est une variable entière utilisée comme indice de la valeur 5(i) ; t est une variable entière représentant un temps symbole ; u est une variable entière utilisée comme indice de la valeur pii ; e est un vecteur de P bits dont la valeur indique la convergence ou non d'une équation de parité ; E(t) est un vecteur de P métriques issu de l'opérateur 43 ; Tamp(t) est un vecteur de P métriques mémorisé dans la mémoire tampon 45 ; ibc est un booléen renvoyé par une fonction permettant de vérifier si une équation de parité est vérifiée ; B(i,t) est un vecteur de métriques extrinsèques à l'instant t dans la mémoire 42 ; Mj(X) un vecteur de P métriques fourni par la mémoire 41 ; M étant un vecteur de P métriques mémorisé dans la mémoire 52 ; Mettre à 0 les vecteurs B(i,t) ; Faire { ibc=0 ; De i=0 à r-1, faire Si VerifMAJ(i)=1 alors ibc=1 ; it=it+1 ; } Tant que (ibc=1 et it Fonction VerifMAJ(i) { t=0 ; e=0 ; De j=0 à n-1 faire { De u=0 à N-1 faire { Lire sä dans la mémoire 48 ; E(t)=Xs .Mj(X)(modulo(XP-I))-B(i,t) ; Tamp(t)=(E(t) si u=0, -B(i,t) sinon) ; e= e OU-EX signe(E(t)) ; t=t+l ; } } VerifMAJ(i)=0 si e ne contient que des 0 et 1 sinon ; De j=n-1 à 0 faire 30 { M=0 ; De u=pu- l à 0 faire { t=t-1 ; B(i,t)= E(t')] ; Lire sä dans la mémoire 48 ; M=M+X-su.[Tamp(t) + B(i,t)] modulo(XP-i) ; } Mj=M ; } Retourner VerifMAJ(i) ; } Contrairement au chemin de Mansour et Shanbhag, l'algorithme permet de prendre en compte la situation où le vecteur Mj de métriques de la mémoire 41 doit être utilisé plusieurs fois par la mise en oeuvre de la fonction VerifMAJ. L'organisation polynomiale et l'architecture du circuit de décodage 4 sont communes pour toute taille de paquet P. L'architecture du circuit 4 peut donc être partagée pour un même taux de codage entre des blocs de tailles différentes en faisant varier le degré des polynômes P. Une mémoire morte est avantageusement utilisée comme mémoire 48. Toutefois, toute mémoire non volatile adéquate peut être utilisée en remplacement. Avantageusement, on traite les lignes de la matrice H selon un ordre particulier accélérant la convergence. Pour cela, on traite successivement des lignes de la matrice H ayant aussi peu que possible de coefficients non nuls en des positions identiques. On peut par exemple traiter successivement les lignes d'indice pair puis ou d'abord les lignes d'indice impair. En effectuant des calculs sur des équations de parité successives peu corrélées entre elles, on peut ainsi 12 réduire le nombre d'itérations nécessaire pour obtenir une convergence lors du décodage. REVENDICATIONS 1. Circuit de décodage (4), caractérisé en ce qu'il comprend : - des première et deuxième zones de mémoire vive (41, 42), comprenant chacune au moins n lignes de stockage de P métriques, les métriques de chaque ligne définissant un polynôme de degré P-1 ; - une interface de réception de métriques d'un canal, inscrivant ces métriques sous formes de n paquets de P métriques dans la première zone (41); - une mémoire non volatile (ROMO, ROM1) mémorisant la structure d'une matrice de parité présentant i lignes et j colonnes et dont chaque élément définit un polynôme de degré P-1 dont les coefficients sont booléens, cette mémoire mémorisant le nombre de coefficients non nuls (K) pour chaque position (i,j), cette mémoire mémorisant en outre un couple comprenant le degré s associé à chaque terme dont le coefficient est non nul de chaque polynôme et une valeur de j associée; - un premier multiplicateur polynomial (49) multipliant modulo XP-1 le polynôme d'une ligne j de la première zone (41) par un monôme de degré s, s pouvant être interprété comme un opérateur réalisant un décalage circulaire ; -un module de contrôle parcourant la mémoire non volatile (ROMO, ROM1) pour fournir séquentiellement la valeur j et le degré s de chaque couple de valeurs respectivement à la première zone et au premier multiplicateur ; -un module de mise à jour (44) présentant : -une mémoire tampon (45)recevant P métriques dont l'amplitude est égale à la différence entre P métriques de la ligne j de la deuxième zone et les P métriques fournies par le premier multiplicateur pour chaque premier coefficient non nul (pii) associé à chaque position dans la matrice de parité, ou recevant P métriques d'amplitude égale aux métriques de la ligne j de la deuxième zone pour les autres coefficients non nuls associés à chaque position dans la matrice de parité ; -un opérateur (46) générant P métriques extrinsèques à partir de la différence entre P métriques de la ligne j de la deuxième zone et les P métriques fournies par le premier multiplicateur et inscrivant ces P métriques extrinsèques à la ligne j de la seconde zone ;-un circuit additionnant algébriquement les P métriques extrinsèques et les P métriques de la mémoire tampon ; -un deuxième multiplicateur polynomial (51) réalisant l'opération inverse de celle réalisée par le premier multiplicateur (49) sur le polynôme correspondant aux métriques fournies par le circuit d'addition; -un module cumulant les polynômes fournis par le deuxième multiplicateur (51) pour une même position (i, j) et inscrivant les métriques correspondant à la ligne j de la première zone de mémoire vive (41) lorsqu'un nombre de cumuls correspondant au nombre de coefficients non nuls mémorisé pour la position (i, j) a été effectué, le cumul des polynômes étant réinitialisé lors de l'inscription des métriques dans la première zone. 2. Circuit de décodage (4) selon la revendication 1, comprenant un circuit de commande réinitialisant la seconde zone lorsque l'interface de réception inscrit les métriques dans la première zone. 3. Circuit de décodage (4) selon la revendication 1 ou 2, dans lequel le module de contrôle parcourt la mémoire non volatile de sorte que les couples fournis ne correspondent pas à des lignes successives de la matrice de parité. 4. Circuit de décodage (4) selon la revendication 3, dans lequel le module de contrôle parcourt la mémoire non volatile (ROMO, ROM1) de sorte que les lignes traitées successivement aient aussi peu que possible de coefficients non nuls en des positions identiques. 5. Circuit de décodage (4) selon la revendication 3 ou 4, dans lequel le module de contrôle parcourt la mémoire non volatile de sorte que les couples fournis correspondent successivement à des lignes impaires, puis successivement à des lignes paires. 6. Circuit de décodage (4) selon l'une quelconque des revendications précédentes, dans lequel l'interface de réception comprend un décodeur souple appliquant les métriques du canal reçues dans la première zone mémoire. 25 30