Brevet FR2817418A1 — publié le 20020531

PROCEDE DE DECODAGE D'UN BLOC DE SYMBOLES ET DISPOSITIF METTANT EN CEUVRE UN TEL PROCEDE La présente invention concerne les techniques de décodage des codes à redondance utilisés pour protéger des informations numériques contre les erreurs susceptibles d'apparaître pendant leur transmission ou leur stockage. La présente invention s'applique en particulier aux codes de type Reed- Solomon couramment utilisés à cette fin. On considère par exemple un code de Reed-Solomon RS(N, N-2t, t) défini sur un corps fini, ou corps de Galois, CG(2m) de cardinal 2m. Un code de Reed-Solomon est un code cyclique en blocs dont le polynôme générateur g(x) de degré 2t, à coefficients dans CG(2m), a pour racines 2t puissances consécutives d'un élément primitif ao du corps CG(2m) 2t g(x) = [ (x - ai) (1) i=1 Chaque mot de code se compose de N symboles (N du code g(x) est un facteur de ce polynôme R(x). Les méthodes de décodage font généralement intervenir des calculs de syndromes d'erreur. Un syndrome est une valeur du polynôme R(x) pour un élément donné du corps de Galois. Le plus souvent, on se limite au calcul des syndromes pour les 2t racines du polynôme générateur du code: Si = R(ai) pour 1 o eh(v) désigne l'amplitude de l'erreur sur le symbole rh(V). Une manière classique de calculer un syndrome Si est d'utiliser une procédure récursive ou un circuit consistant essentiellement en un multiplieur, un additionneur et un registre pour mettre en oeuvre la relation de récurrence Sn) = S(n-1).ai + rN_1ln (4) Avec la condition d'initialisation S?)= rN_1, le syndrome Si peut être calculé au fur et à mesure de l'arrivée des symboles rNln (dans l'ordre des poids décroissants), et obtenu dès l'arrivée du dernier symbole r0 du bloc: Si = S(N-1) i- i Les 2t relations (3) ont 2V inconnues, à savoir les positions h(v) et les amplitudes eh(V) des erreurs. Pour résoudre ces équations, la plupart des algorithmes de décodage impliquent le calcul d'un polynôme localisateur d'erreurs o(x) de degré V dont les racines sont les éléments du corps de Galois de la forme ox-h(v). L'expression du polynôme localisateur d'erreurs est: v a(x) = K.f (1 - x.ah(v))= ot.xt + t_1.Xt-1 +... + c1.X + o0 (5) v=0 O K = G0 est un élément arbitraire du corps CG(2m) et u = 0 pour u > V. Les coefficients ou de ce polynôme vérifient le système linéaire: Sl S2 '" Sv v S3V+1 S2 S3 Sv+i.v1 =v-+2 L-Ki. kv + 2 (6) Sv Sv+ 1 S2v-1 ai S2v Différents algorithmes existent pour résoudre le système linéaire (6), notamment l'algorithme d'Euclide et les algorithmes de type BerlekampMassey. L'algorithme d'Euclide est conceptuellement simple, mais sa mise en oeuvre requiert une complexité plus grande que les algorithmes de type Berlekamp- Massey. Les algorithmes de type Berlekamp-Massey résolvent le système (6) par itérations successives qui s'interprètent classiquement comme une construction récursive d'un registre à décalage à opérateurs linéaires modélisant le système (voir "Theory and Practice of Error Control Codes" de R.E. Blahut, Addison- -3- Wesley, Reading, MA, 1993). A chaque itération, un écart de prédiction ("discrepancy") Ak à valeurs dans le corps CG(2m) est calculé pour mettre à jour le polynôme localisateur. Si cet écart Ak est encore non nul à l'issue de la (2t)-ième itération, I'algorithme indique un échec de décodage, le bloc reçu comportant plus de t symboles erronés. Diverses variantes de l'algorithme de Berlekamp-Massey ont été proposées dans le but de simplifier son implémentation. L'article "VLSI Design of Inverse-Free Berlekamp-Massey Algorithm", de I.S. Reed et al, IEEE Proceedings-E, Vol. 138, N 5, Septembre 1991, pages 295-298, propose une variante intéressante dans la mesure o elle permet de se dispenser d'inverser les écarts de prédiction Ak. Cette variante revient à considérer une valeur a priori quelconque dans CG(2m) pour le coefficient K = co, au lieu de K = 1 dans la version traditionnelle. Une fois que le polynôme localisateur d'erreurs a été calculé, ses racines sont déterminées pour obtenir les positions h(v) des erreurs. Une procédure fréquemment utilisée pour cela, dite "recherche de Chien", consiste à calculer les valeurs du polynôme o(x) pour chacun des éléments du corps CG(2m), une erreur étant identifiée chaque fois que a(x) = 0 (voir "Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes" par R.T. Chien, IEEE Trans. on Information Theory, Vol.10, 1964, pages 357-363). Cette procédure consiste en un calcul récursif des valeurs (o1-N+n) pour n = 0, 1,..., N-1 selon t 1(c-N+n): (n) (7) u=O en exploitant les relations de récurrence (un+1) =(un).ou pour 0 de récurrence. Lorsque le décodeur utilise un algorithme de type Berlekamp-Massey, les coefficients du polynôme évaluateur co(x) peuvent être calculés en même temps que ceux du polynôme localisateur lors des 2t itérations de cet algorithme. Ils i5 peuvent aussi être calculés ultérieurement selon (8). Certains algorithmes de décodage ont été aménagés pour pouvoir prendre en compte des effacements dans les données d'entrée. Un symbole effacé est marqué dans le bloc d'entrée pour indiquer que ce symbole n'a pas été reçu, ou qu'il a été reçu dans des conditions tellement mauvaises que sa valeur est a priori fausse. La prise en compte de ces effacements permet de réduire le nombre d'inconnues des relations (3) puisque certaines des positions h(v) sont connues. Lorsque le polynôme localisateur d'erreurs est calculé de manière itérative selon l'algorithme de Berlekamp-Massey, la prise en compte des effacements conduit à initialiser différemment les coefficients du polynôme localisateur a(x) avant la première itération. Dans un codage sans effacements, ce polynôme localisateur est habituellement initialisé par 60(x) = 1, alors que la prise en compte des effacements conduit à l'initialiser par un polynôme de degré s dont les racines (-h(O),..., uh(s-1) sont déterminées par les positions h(0),..., h(s-1) des s effacements considérés. L'algorithme de Berlekamp- -5- Massey adapté pour prendre en compte les effacements est également décrit dans l'ouvrage précité de R.E. Blahut. Une version adaptée pour se dispenser des calculs d'inverse dans le corps de Galois est décrite dans l'article " On Decoding of Both Errors and Erasures of a Reed-Solomon Code Using an Inverse-Free Berlekamp-Massey Algorithm ">, de J.H. JENG et al., IEEE Transactions on Communications, Vol. 47, No. 10, octobre 1999, pages 1488- 1494. Si s est le nombre de symboles effacés du bloc d'entrée et V le nombre de symboles erronés, I'algorithme de décodage avec gestion des effacements permet de corriger les erreurs et les effacements du bloc si 2s + V soit parfaitement fiable. En pratique, cette condition n'est pas toujours remplie. En particulier, il y a une probabilité d'effacer des symboles qui se trouvaient avoir été bien reçus. Dans un tel cas, si le nombre de symboles erronés était à l'origine inférieur ou égal à t, on peut dépasser les capacités de correction de I'algorithme à effacements alors que l'algorithme sans effacement aurait fourni le bon résultat. Un but de la présente invention est d'optimiser les capacités de décodage de codes correcteurs d'erreurs tels que les codes de type Reed- Solomon ou BCH (Bose-Chaudhuri-Hocquenghem). L'invention propose ainsi un procédé de décodage d'un bloc de symboles d'entrée, dans lequel on calcule des syndromes à partir du bloc, en relation avec un code correcteur d'erreurs, et on applique une première méthode de correction d'erreurs, ayant les syndromes calculés pour paramètres d'entrée, afin d'estimer des symboles d'information. En réponse à une indication d'incapacité de correction par la première méthode, on applique une seconde méthode de correction d'erreurs et d'effacements, ayant les syndromes calculés et au moins une position d'effacement dans le bloc pour paramètres d'entrée, afin d'estimer les symboles d'information. -6- Ce procédé pallie la limitation évoquée ci-dessus des algorithmes à gestion des effacements, en garantissant que le décodage s'opère toujours dans de bonnes conditions lorsque le bloc d'entrée ne comporte pas plus de t symboles erronés. Dans certains cas o il y a plus de t symboles erronés, le second décodage à effacement permettra la bonne correction. Le décodage proposé prend donc en considération une probabilité de se tromper dans le positionnement des effacements. Le schéma est donc bien adapté à des procédés de réception de signaux à faible rapport signal/bruit. Il est à noter qu'on a pas besoin de calculer deux fois les syndromes lorsque les deux méthodes de corrections doivent être appliquées sur le même bloc. Comme le calcul des syndromes représente une proportion importante de la complexité de l'ensemble du décodage (environ 50%), le gain procuré par le procédé est obtenu au prix d'une augmentation raisonnable de la complexité. Un autre aspect de la présente invention se rapporte à un dispositif de i5 traitement de signal, comprenant des moyens de réception du signal pour estimer des blocs de symboles d'entrée et des moyens de décodage desdits blocs au moyen d'un code correcteur d'erreurs. Les moyens de réception du signal sont agencés pour fournir une information sur la fiabilité des symboles d'entrée du bloc. Les moyens de décodage comprennent des moyens de calcul de syndromes à partir d'un bloc de signal, des premiers moyens de traitement des syndromes pour estimer des symboles d'information, des moyens pour déterminer au moins une position d'effacement dans le bloc sur la base de ladite information sur la fiabilité, et des seconds moyens de traitement des syndromes et de ladite au moins une position d'effacement, activés en réponse à une indication d'incapacité de correction par les premiers moyens de traitement, pour estimer les symboles d'information. D'autres particularités et avantages de la présente invention apparaîtront dans la description ci-après d'exemples de réalisation non limitatifs, en référence aux dessins annexés, dans lesquels: - la figure 1 est un schéma synoptique d'un exemple de dispositif selon l'invention; et - la figure 2 est un organigramme illustrant un procédé de décodage selon l'invention. 7 - Le dispositif représenté sur la figure 1 traite un signal numérique d'entrée R qui a pu par exemple être transmis sur une interface radio. Ce signal R est fourni à un démodulateur 1 qui procède à une estimation de symboles numériques transmis. Ces symboles numériques ont été générés au niveau d'un émetteur non représenté en appliquant un codage à redondance, afin de protéger les symboles d'information contre des erreurs de transmission. Le code à redondance est de préférence un code non binaire de Reed- Solomon tel que présenté en introduction. Par commodité de réalisation, on utilise généralement des codes systématiques, c'est-à-dire que les N-2t symboles d'information se trouvent explicitement dans les N symboles transmis. Ce sont par exemple les N-2t premiers symboles. Le démodulateur 1 fournit les symboles estimés rN_1, rN_2,... r1, r0 par blocs de N symboles à un décodeur 2. Chaque symbole est constitué de m bits lorsque le code de Reed-Solomon est défini sur le corps CG(2m). Le décodeur 2 comporte un module 3 de calcul de syndromes, qui calcule de façon classique les 2t syndromes d'erreur S1, S2,..., S2t, par exemple selon la relation (4). Le décodeur 2 comporte en outre un module 4 de décodage d'erreurs sans prise en compte d'effacements. Celui-ci peut fonctionner de façon classique selon les algorithmes de Berlekamp-Massey, de Chien et de Forney pour corriger d'éventuelles erreurs, en nombre inférieur ou égal à t, dans les symboles estimés du bloc d'entrée. Les N-2t premiers symboles sont extraits après correction pour être fournis aux circuits d'exploitation situés en aval. Un autre module de décodage 5 du décodeur 2 prend en compte à la fois des erreurs et des effacements lorsque le premier module 4 indique qu'il a été incapable de corriger le bloc en raison de la détection d'un nombre d'erreurs supérieur à t. Le module 5 fonctionne en utilisant les mêmes syndromes S1,., S2t qui ont été calculés par le module 3, et en initialisant le polynôme localisateur d'erreurs selon un polynôme d'initialisation c (x) fourni par un module 6 de sélection d'effacements. Si le module de décodage 5 est également mis en défaut, il délivre un signal d'alarme X pour indiquer la perte d'un bloc aux circuits situés en aval. -8- Le module 6 de sélection des effacements fonctionne de façon connue sur la base de mesures de vraisemblance XN-1, 'N-27 '" k1, X0 fournies par le démodulateur 1 parallèlement aux symboles estimés rNl, rN_2,..., r1, ro. Ces mesures de vraisemblance ont par exemple été produites à partir de la métrique d'un égaliseur de canal à sorties souples du démodulateur 1 (voir par exemple EP-A-0 946 014). A partir des positions des symboles effacés, le module 6 calcule le polynôme d'initialisation G (x) pour l'algorithme de Berlekamp-Massey mis en oeuvre par le module de décodage 5. La figure 1 donne une représentation synoptique du dispositif selon l'invention. En pratique, le décodeur 2 sera souvent réalisé en programmant un processeur de signal numérique de manière appropriée, par exemple selon l'organigramme de la figure 2. La première étape du traitement d'un bloc rN_1, rN_2,..., r1, r0 est le calcul 11 des syndromes S1, S2,...., S2t selon les relations (4). Si tous les syndromes sont nuls (test 12), le traitement du bloc est terminé, et il suffit d'extraire les symboles d'information du bloc (étape 13). Si l'un au moins des syndromes n'est pas nul, le polynôme localisateur d'erreurs 6(x) est calculé à l'étape 14, par exemple selon l'algorithme de Berlekamp-Massey initialisé par G (x)= 1. Cet algorithme indique de façon classique les blocs pour lesquels il estime que le degré du polynôme localisateur d'erreurs est supérieur au degré 2t du polynôme générateur du code. Cette condition est testée à l'étape 15. Si le degré ne dépasse pas 2t, I'étape suivante est la recherche des racines du polynôme localisateur d'erreur G(x) à l'étape 16, par exemple selon l'algorithme de Chien. Si le nombre de racines trouvé est égal au degré du polynôme G(x) (test 17), I'étape suivante 18 consiste en le calcul du polynôme évaluateur co(x), selon la relation (8). A l'étape suivante 19, I'algorithme de Forney est utilisé pour évaluer les amplitudes des erreurs, et ces amplitudes sont soustraites des symboles correspondants pour les corriger. Les symboles d'information peuvent alors être extraits du bloc à l'étape 13. Quand l'algorithme de décodage sans effacements est mis en défaut, c'està-dire quand le degré du polynôme C (x) dépasse 2t (test 15), ou lorsque la -9- recherche de Chien ne fournit pas le bon nombre de racines (test 17), le décodeur applique la méthode de décodage avec gestion des effacements. Il commence par calculer le polynôme localisateur d'erreurs et d'effacements (également noté 6(x) sur la figure 2) à partir des mêmes syndromes calculés à I'étape 1l 1 et du polynôme d'initialisation a (x) (étape 20). Ce calcul est effectué selon un algorithme de BerlekampMassey modifié pour prendre en compte les effacements. Le décodeur est mis en échec si le degré du polynôme localisateur a(x) obtenu dépasse encore 2t lors du test 21. Sinon, le décodeur passe à la recherche 22 des racines du polynômes 6(x) selon l'algorithme de Chien. Le décodeur est encore mis en échec si le nombre de racines trouvées ne correspond pas au degré au polynôme 6(x). Sinon, il procède à l'étape 18 précitée pour déterminer le polynôme évaluateur d'erreurs et d'effacements. En variante, le polynôme évaluateur co(x) peut être calculé au cours de l'exécution de l'algorithme de Berlekamp-Massey, à l'étape 14 ou 20. Dans une autre réalisation du décodeur, lorsque le décodage avec effacements est mis en défaut, le module 5 le signale au module 6 de sélection des effacements. Celui-ci sélectionne alors davantage d'effacements dans le bloc, et il détermine un polynôme d'initialisation a (x) de degré supérieur. L'algorithme de décodage à effacements est exécuté de nouveau à partir de ce polynôme a (x), toujours avec les mêmes syndromes S1,..., S2t, pour essayer encore de corriger le bloc. - 10- REVENDICATIONS 1. Procédé de décodage d'un bloc de symboles d'entrée (rN_1, rN_2,..., r1, r0), dans lequel on calcule des syndromes (S1, S2,.... S2t) à partir du bloc, en relation avec un code correcteur d'erreurs, et on applique une première méthode de correction d'erreurs, ayant les syndromes calculés pour paramètres d'entrée, afin d'estimer des symboles d'information, caractérisé en ce qu'en réponse à une indication d'incapacité de correction par la première méthode, on applique une seconde méthode de correction d'erreurs et d'effacements, ayant les syndromes calculés et au moins une position I0 d'effacement dans le bloc pour paramètres d'entrée, afin d'estimer les symboles d'information. 2. Procédé selon la revendication 1, dans lequel le code correcteur d'erreurs est un code de Reed-Solomon. 3. Procédé selon la revendication 1 ou 2, dans lequel la première méthode de correction d'erreurs comporte le calcul d'un polynôme localisateur d'erreurs sur la base des syndromes (S1, S2,..., S2t), et dans lequel lorsque le degré du polynôme localisateur d'erreurs dépasse le degré du polynôme générateur du code, on génère une indication d'incapacité de correction par la première méthode. 4. Procédé selon la revendication 3, dans lequel la première méthode de correction d'erreurs comporte une recherche de racines du polynôme localisateur d'erreurs, et dans lequel lorsque le nombre de racines trouvées n'est pas égal au degré du polynôme localisateur d'erreurs, on génère une indication d'incapacité de correction par la première méthode. 5. Procédé selon l'une quelconque des revendications précédentes, dans lequel, en réponse à une indication d'incapacité de correction par la seconde méthode, on applique à nouveau la seconde méthode de correction d'erreurs et d'effacements en augmentant le nombre de positions d'effacement - 11 - dans le bloc prises en compte dans les paramètres d'entrée, afin d'estimer les symboles d'information. 6. Dispositif de traitement de signal, comprenant des moyens (1) de réception du signal pour estimer des blocs de symboles d'entrée (rN_1, rN_2,..., r1, r0) et des moyens (2) de décodage desdits blocs au moyen d'un code correcteur d'erreurs, dans lequel les moyens de décodage comprennent des moyens (3) de calcul de syndromes (S1, S2,..., S2t) à partir d'un bloc de signal et des premiers moyens (4) de traitement des syndromes pour estimer des symboles d'information, caractérisé en ce que les moyens de réception du signal (1) sont agencés pour fournir une information sur la fiabilité des symboles d'entrée du bloc, et en ce que les moyens de décodage (2) comprennent en outre des moyens (6) pour déterminer au moins une position d'effacement dans le bloc sur la base de ladite information sur la fiabilité, et des seconds moyens (5) de traitement des syndromes et de ladite au moins une position d'effacement, activés en réponse à une indication d'incapacité de correction par les premiers moyens de traitement (4), pour estimer les symboles d'information. 7. Dispositif selon la revendication 6, dans lequel le code correcteur d'erreurs est un code de Reed-Solomon. 8. Dispositif selon la revendication 6 ou 7, dans lequel les premiers moyens de traitement (4) comprennent des moyens de calcul d'un polynôme localisateur d'erreurs sur la base des syndromes (S1, S2,..., S2t), incluant des moyens pour générer une indication d'incapacité de correction lorsque le degré du polynôme localisateur d'erreurs dépasse le degré du polynôme générateur du code. 9. Dispositif selon la revendication 8, dans lequel les premiers moyens de traitement (4) comprennent des moyens de recherche de racines du polynôme localisateur d'erreurs, incluant des moyens pour générer une indication d'incapacité de correction lorsque le nombre de racines trouvées n'est pas égal au degré du polynôme localisateur d'erreurs. - 12- 10. Dispositif selon l'une quelconque des revendications 6 à 9, dans lequel les moyens de réception comprennent un démodulateur (1).