Brevet FR2714555A1 — publié le 19950630

La présente invention se rapporte à un procédé et à un dispositif pour corriger des erreurs présentes dans des données stockées ou transmises; et, plus particulièrement, à un procédé et à un dispositif pour déterminer les coefficients d'un polynôme localisateur d'erreurs à utiliser pour corriger des erreurs dans les données codées en utilisant un code de Reed-Solomon. Les bruits se présentant pendant un processus de transmission, stockage ou récupération de données peuvent à leur tour provoquer des erreurs dans les données transmises, stockées ou récupérées. En conséquence, diverses techniques de codage, ayant la capacité de rectifier de telles erreurs, pour coder les données à transmettre ou à stocker, ont été développées. Dans de telles techniques de codage, un groupe de bits de vérification est ajouté à un groupe de bits de message ou d'information pour former un mot de code. Les bits de vérification, qui sont déterminés par un codeur, sont utilisés pour détecter et corriger les erreurs. De ce point de vue, le codeur traite essentiellement les bits comprenant les bits de message en tant que coefficients d'un polynôme d'un message binaire et dérive les bits de vérification en faisant opérer un polynôme générateur G(X) sur le polynôme de message par multiplication ou division. Ce polynôme générateur est sélectionné pour impartir des propriétés souhaitées à un mot de code sur lequel il opère de manière que le mot de code appartienne à une classe particulière de codes d'un groupe binaire de correction d'erreurs (voir, e.g., S. Lin et autre, "Error Control Coding: Fundamentals and Applications", Prentice-Hall, 1983). Une classe de codes de correction d'erreurs est formée des codes bien connus de BCH (Bose-Chaudhuri-Hocquenghen), qui comprend les codes de Reed-Solomon. La base mathématique des codes de Reed-Solomon est expliquée e.g., dans la référence ci-dessus par Lin et autre et également chez Berlekamp, "Algebraic Coding Theory", McGraw-Hill, 1968, 2 2714555 auquel on se réfère de plus dans le brevet U.S. N 4 162 480 publié au nom de Berlekamp. Un code de Reed-Solomon a un polynôme générateur G(X) défini comme suit: d-1 G(X) = X (X-a') Eq. (1) i=l o a est un élément primitif dans le Champ de Galois (GF(2m), et d est la distance désignée du code. Dans le procédé de réception ou de récupération d'un mot de code transmis ou stocké, certains bruits peuvent avoir été convertis en un motif d'erreur dans le mode de code. Afin de traiter ce motif d'erreur imposé sur les codes de Reed- Solomon, on utilise généralement un processus en quatre étapes. Dans la description du processus de correction d'erreurs, on se référera à un code de Reed-Solomon consistant en mots de code contenant n symboles à m bits (dont k symboles sont des symboles d'information et n-k symboles sont des symboles de vérification). En tant que première étape de correction d'erreurs, on calcule les valeurs de syndrome SO, S1,... Snk_1. En tant que seconde étape, en utilisant les valeurs de syndrome, on calcule les coefficients d'un polynôme localisateur d'erreurs a(X). Dans une troisième étape, le polynôme localisateur d'erreurs a(X) est résolu pour obtenir ses racines Xi, qui représentent les emplacements d'erreurs dans les mots de codes reçus. En quatrième étape, en utilisant les emplacements d'erreurs Xi et les valeurs de syndrome, on calcule les valeurs d'erreurs. Les expressions mathématiques pour les valeurs de syndrome et les coefficients du polynôme localisateur d'erreurs sont données dans le brevet U.S. N 4 162 480 référencé ci-dessus, publié au nom de Berlekamp. La deuxième étape dans le processus généralisé de correction d'erreurs décrit ci-dessus, i.e., l'étape de calcul des coefficients du polynôme localisateur d'erreurs, nécessite une tâche de calcul qui est assez laborieuse. Un 3 2714555 algorithme populaire pour obtenir les coefficients du polynôme localisateur d'erreurs est l'algorithme de Berlekamp-Massey qui est décrit dans les références ci-dessus mentionnées. Dans l'algorithme de Berlekamp-Massey, le polynôme localisateur d'erreurs est obtenu par une méthode itérative. Plus particulièrement, le polynôme localisateur d'erreurs est remis au point en se basant sur les valeurs de syndrome à chaque itération. Afin de calculer les coefficients du polynôme localisateur d'erreurs, diverses variables e.g. les termes de correction, l'écart etc., sont introduites. Les multiplicateurs sont utilisés pour remettre les variables et le polynôme localisateur d'erreurs au point à chaque itération. Pour un code de Reed-Solomon corrigeant t erreurs, il faut 6t multiplicateurs pour calculer le polynôme localisateur d'erreurs en utilisant l'algorithme de Berlekamp-Massey, o t représente la capacité de correction d'erreurs du code. Les valeurs de syndrome sont introduites tous les deux cycles d'horloge de symboles à utiliser pour calculer le polynôme localisateur d'erreurs. En d'autres termes, il faut deux cycles d'horloge pour effectuer chaque itération. L'algorithme de Berlekamp a été modifié par Liu, o le nombre des multiplicateurs est réduit à 4t+1, tandis que les valeurs de syndrome sont introduites tous les trois cycles d'horloge de symboles (voir e.g., K. Y. Liu, "Architecture for VLSI Design of ReedSolomon Decoders", IEEE Transactions on Computers, volume c-33, N 2, pp. 178-189, Février 1984). Dans l'algorithme de Liu, certaines des variables sont modifiées par rapport à celles de l'algorithme de Berlekamp- Massey pour un traitement plus efficace. Cependant, de nombreuses variables sont impliquées dans le calcul du polynôme localisateur d'erreurs dans ces algorithmes. Par ailleurs, dans chaque itération, certaines des variables sont calculées avant certaines autres variables parce que les premières sont utilisées pour calculer les 4 2714555 dernières. En conséquence, tous les multiplicateurs ne sont pas utilisés en même temps dans chaque cycle d'horloge. La présente invention a, par conséquent, pour objectif principal de procurer un procédé et un dispositif perfectionnés permettant de calculer un polynôme localisateur d'erreurs en employant un nombre réduit de multiplicateurs, pour ainsi obtenir une réduction du temps de traitement ainsi que du prix de fabrication du dispositif. Selon la présente invention, on prévoit un procédé de production d'un polynôme localisateur d'erreurs d'une énième itération à utiliser dans un système de décodage pour décoder un signal transmis codé en utilisant un code de Reed-Solomon, en se basant sur un nombre prédéterminé de valeurs de syndrome, un groupe de variables d'une (n-l)ième itération comprenant un écart et son polynôme localisateur d'erreurs et un polynôme localisateur d'erreurs d'une (n-2)ième itération, ledit procédé comprenant les étapes de: (a) déterminer un terme temporel en se basant sur l'écart de la (n-l)ième itération et du polynôme localisateur d'erreurs de la (n-2)ième itération; (b) calculer un écart de la énième itération en se basant sur les valeurs de syndrome et le polynôme localisateur d'erreurs de la (n-1)ième itération; (c) décider d'un terme de correction en se basant sur ledit terme temporel et l'écart de la énième itération; et (d) calculer le polynôme localisateur d'erreurs de la énième itération en se basant sur le terme de correction et le polynôme localisateur d'erreur de la (n-1)ième itération. L'invention sera mieux comprise et d'autres buts, caractéristiques, détails et avantages de celle-ci apparaîtront plus clairement au cours de la description explicative qui va suivre faite en référence aux dessins schématiques annexés donnés uniquement à titre d'exemple illustrant un mode de réalisation de l'invention et dans lesquels: 2714555 - la figure 1A montre un organigramme permettant de calculer un polynôme localisateur d'erreurs dans l'algorithme de Berlekamp-Massey; - la figure lB représente un organigramme permettant de calculer un polynôme localisateur d'erreurs dans l'algorithme de Liu; - la figure 1C offre un organigramme permettant de calculer un polynôme localisateur d'erreurs selon la présente invention; - les figures 2A à 2C illustrent un diagramme des temps pour calculer le polynôme localisateur d'erreurs selon l'invention; et - la figure 3 donne un schéma bloc d'un dispositif pour calculer le polynôme localisateur d'erreurs selon la présente invention. En se référant aux figures 1A à 1C, elles montrent des organigrammes simplifiés pour calculer un polynôme localisateur d'erreurs dans l'algorithme de Berlekamp-Massey, l'algorithme de Liu et la présente invention, respectivement. Le processus complet pour obtenir un polynôme localisateur d'erreurs comprend un nombre multiple, e.g., de 2t, itérations, o t représente la capacité de correction d'erreurs du code; et, à chaque itération, le polynôme localisateur d'erreurs est remis une fois au point (voir Berlekamp, Algebraic Codinq Theory, McGraww-Hill, 1968). Le polynôme localisateur d'erreurs est déterminé en se basant sur 2t valeurs de syndrome, o les valeurs de syndrome sont obtenues de mots de code reçus, codés en utilisant un code de Reed-Solomon. Les racines du polynôme localisateur d'erreurs indiquent les emplacements des erreurs. Dans les organigrammes montrés aux figures 1A à 1C, une partie du processus accompli sur une, e.g. la énième, itération est donnée à titre d'exemple, comprenant une opération qui impose une grande charge de calcul, e.g. une opération de multiplication sur un Champ de Galois. Plus particulièrement, dans le processus représenté aux figures 1A 6 2714555 à 1C, le polynôme localisateur d'erreurs est remis au point comme suit: an(x) = (un-1(X) - dnX d-1.Un_ - 2(x) Eq. (2) n-1 o n désigne la énième itération; dn désigne un écart qui est calculé en utilisant les valeurs de syndrome et le polynôme localisateur d'erreurs de l'itération qui précède; et an(X) et a1(X) sont respectivement 1 et 1-d1X. Comme le montre la figure 1A, le calcul de l'équation (2) est divisé en trois parties, dans l'algorithme de Berlekamp-Massey. Plus particulièrement, à l'étape Sll, l'écart dn est calculé en se basant sur les valeurs de syndrome et le polynôme localisateur d'erreurs de l'itération précédente anl(X). A l'étape S12, le polynôme localisateur d'erreurs est mis au point en se basant sur l'écart dn obtenu à l'étape Sll et un terme de correction. Le terme de correction bn(X) est introduit pour séparer l'équation (2) et il est défini comme suit: bn(x) = d. n-l (x) Eq. (3) n Le terme de correction de l'itération précédente, i.e., bnl(X), est utilisé pour obtenir le polynôme localisateur d'erreur an(X). Le terme de correction est également remis au point à l'étape S12 et est utilisé pour la remise au point du polynôme localisateur d'erreur à une itération suivante. Sur la figure 1A, les valeurs remises au point à chaque étape sont présentées. Les deux valeurs spécifiées entre les parenthèses correspondantes sont multipliées pour remettre au point l'écart dn, le terme de correction bn(X), et le polynôme localisateur d'erreurs an(X). Chacune des valeurs représentées sous la forme d'un polynôme, e.g., bn(X) comprend un groupe de valeurs dont le nombre n'est pas plus grand que 2t. Par conséquent, le calcul de chaque valeur comprend une multiplication de vecteurs, o il faut jusqu'à 7 2714555 2t multiplicateurs pour remettre chaque valeur au point, chaque multiplicateur accomplissant une opération de multiplication dans le Champ de Galois. Ces étapes de processus entreprises dans l'organigramme de la figure 1A sont résumées au Tableau 1: TABLEAU 1 l_ _ 1er cycle d'horloge 2ème cycle d'horloge Mil dn M12 an(x)=an-l(X)-dnx.bn-l(X) M13 - M13 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ n - o Mll, M12 et M13 désignent un groupe de 2t multiplicateurs dans le Champ de Galois, respectivement. Le calcul du polynôme localisateur d'erreurs on(X) et du terme de correction bn(X) peut être accompli dans un même cycle d'horloge parce que l'un n'a pas besoin du résultat de l'autre. On peut facilement apprécier qu'il faut 6t multiplicateurs dans l'ensemble et que chaque itération est terminée en deux cycles d'horloge dans l'algorithme de Berlekamp- Massey. Dans l'algorithme de Liu qui est une modification de l'algorithme de Berlekamp-Massey, le calcul de l'équation (2) est également divisé en trois parties. Cependant, au lieu du terme de correction utilisé dans l'algorithme de Berlekamp- Massey, un terme intermédiaire dn* est utilisé. Le terme intermédiaire est défini par: dn = dndn-1 Eq. (4) o dn et dnl représentent l'écart entre l'itération courante et la précédente, respectivement. La figure lB montre le processus accompli dans l'algorithme de Liu dans chaque itération. Plus particulièrement, l'opération à accomplir à l'étape S21 est 8 2714555 la même que celle de l'étape S11 de la figure 1A, o l'écart dn est calculé. A l'étape S22, le terme intermédiaire dn* est calculé en se basant sur l'écart entre dn de l'itération courante et dn_1 de l'itération précédente. A l'étape S23, le polynôme localisateur d'erreurs est remis au point en se basant sur le terme intermédiaire dn* obtenu à l'étape S22 et le polynôme localisateur d'erreurs de la (n- 2)ième itération an-2(X). Le résultat de l'opération que l'on peut voir à la figure lB est le même que celui de la figure 1A. Sur la figure lB, les valeurs à remettre au point à chaque étape sont représentées. Le calcul de l'écart dn et du polynôme localisateur d'erreurs on(X) comprend une multiplication de vecteurs, tandis que le calcul du terme intermédiaire dn* nécessite une multiplication scalaire uniquement. Les opérations accomplies dans l'organigramme de la figure lB sont résumées au Tableau 2: TABLEAU 2 1er cycle 2ème cycle 3ème cycle I______ d'horloge d'horloge d'horloge M21 dn m22 dn*=dndn_1-1 M23 an(X)=an-l(x) -dn*X. an-2 (X) o M21, M23, désignent un groupe de 2t multiplicateurs, respectivement et m22 désigne un multiplicateur scalaire. Le calcul des trois termes spécifiés au Tableau 2 est accompli dans des cycles différents d'horloge parce que dn* et an(X) peuvent être calculés après que dn et dn* ont été obtenus, respectivement. On peut facilement voir qu'il faut (4t+1) multiplicateurs et que chaque itération est terminée en trois cycles d'horloge dans l'algorithme de Liu. En se référant à la figure 1C, elle montre un processus accompli dans chaque itération selon la présente invention. Dans la présente invention, un terme temporel et un terme 9 2714555 modifié de correction sont introduits; et, le calcul de l'équation (2) est divisé en quatre parties, seules trois d'entre elles nécessitant une multiplication de vecteurs. Le terme temporel Tn(x) est défini par: Tn(x)=dn-1 1. an-2(X) Eq. (5) o dn_1 est l'écart de l'itération précédente, i.e., la (n-l)ième et On_2(X) est le polynôme localisateur d'erreurs de la (n- 2)ième itération. Le terme de correction modifié Cn(X) est défini par: Cn(X)-dn.Tn(X) Eq. (6) Plus particulièrement, à l'étape S31, on calcule l'écart dn et le terme temporel Tn(x). A l'étape S32, le terme de correction modifiée Cn(X) est déterminé en se basant sur le terme temporel Tn(x) et l'écart dn obtenu à l'étape S31. A l'étape S33, le polynôme localisateur d'erreurs on(X) est remis au point en utilisant le terme de correction modifié Cn(X). Le résultat de l'opération représentée à la figure 1C est le même que celui des figures lA et lB. Sur la figure 1C, les valeurs à remettre au point à chaque étape sont représentées. Le calcul de l'écart dn, du terme temporel Tn(x) et du terme de correction modifié Cn(X) comprend un multiplication de vecteurs, tandis que la remise au point du polynôme localisateur d'erreurs an(X) nécessite simplement une addition de vecteurs. On peut facilement remarquer que l'écart dn et le terme temporel Tn(X) peuvent être calculés pendant le même cycle d'horloge en utilisant des groupes différents de multiplicateurs parce ce qu'ils ne nécessitent pas le résultat l'un de l'autre. Par ailleurs, les étapes S32 et S33 peuvent être accomplies pendant un cycle d'horloge parce que ces dernières ne nécessitent pas d'opération de multiplication. Les opérations accomplies dans l'organigramme de la figure 1C sont résumées au Tableau 3: 2714555 TABLEAU 3 1er cycle d'horloge 2ème cycle d'horloge M31 dn M32 Tn(x)=dn_-1.an2(x) Cn(x)=dn.Tn(x) A33 an(x)=Gnl(x) ___ __ _ __ __ ___ __ __ __ _ L -x.Cn(x) o M31, M32 désignent un groupe de 2t multiplicateurs et A33 désigne un groupe d'additionneurs. On peut facilement voir qu'il faut 4t multiplicateurs dans le Champ de Galois et que chaque itération est accomplie en deux cycles d'horloge dans le cas du présent algorithme. Les opérations expliquées ci-dessus sont résumées et comparées aux figures 2A à 2C. Dans les algorithmes de Berlekamp-Massey et Liu, on utilise différents multiplicateurs pour calculer différentes valeurs comme le montrent les figures 2A et 2B. Cependant, dans la présente invention, on emploie un multiplicateur, i.e. M32, pour calculer deux variables différentes, alternativement, dans chaque cycle d'horloge comme cela est représenté à la figure 2C, pour ainsi réduire le nombre de multiplicateurs et le cycle d'horloge pour chaque itération. En référant à la figure 3, elle montre un schéma bloc d'un dispositif 1 pour la remise au point du polynôme localisateur d'erreurs selon la présente invention. Le dispositif 1 comporte deux blocs de multiplication 10 et 30, et un bloc d'addition 60, qui correspondent à M31, M32 et A33 que l'on peut voir au Tableau 3. Le premier bloc de multiplication 10 calcule l'écart dn, en se basant sur les valeurs de syndrome S et le polynôme localisateur d'erreurs de l'itération qui précède Onl(X). Le second bloc de multiplication 30 calcule le terme temporel Tn(x) et le terme de correction modifié Cn(X), alternativement, en réponse à un groupe de dn_1-1 et on-2(X), et un groupe de Tn(x) et dn, respectivement. Le bloc 11 2714555 d'addition 60 remet le polynôme localisateur d'erreur on(X) au point en réponse au terme de correction modifié Cn(X). Chacun des blocs de multiplication 10 et 30 peut comprend 2t multiplicateurs dans le Champ de Galois pour la multiplication de vecteurs. Le bloc d'addition 60 peut comprend 2t additionneurs pour l'addition de vecteurs. Plus particulièrement, les valeurs de syndrome S et le polynôme localisateur d'erreurs de l'itération précédente anl(X) sont couplés au premier bloc de multiplication 10, pour ainsi produire l'écart dn. L'écart dn est couplé à un bloc de retard et d'inversion 20, pour ainsi produire dn_1-1, i.e., l'inverse de l'écart de l'itération qui précède, au second bloc de multiplication 30 via un multiplexeur 25. L'écart dn de l'itération courante est également couplé au bloc de multiplication 30 via le multiplexeur 25. Au multiplexeur 25, l'une des valeurs introduites, i.e., dn ou dn_1-l, est sélectionnée et est appliquée au second bloc de multiplication 30. Plus particulièrement, au premier cycle d'horloge de chaque itération, on sélectionne dn_1-1, tandis que l'on sélectionne dn au second cycle d'horloge. on_2(X) et Tn(X) sont également introduits alternativement dans le second bloc de multiplication 30 pour ainsi appliquer le terme temporel Tn(X) et le terme de correction modifié Cn(X) à un démultiplexeur 40, alternativement. Le terme temporel Tn(X) est appliqué par le démultiplexeur 40 à un multiplexeur , pour être appliqué au second bloc de multiplication 30 lors du second cycle d'horloge. Le terme de correction modifié Cn(X) est appliqué par le démultiplexeur 40 au bloc d'addition 60. Au bloc d'addition 60, le polynôme localisateur d'erreurs est remis au point en se basant sur le terme de correction modifié Cn(X) et est appliqué par le démultiplexeur 40 et le polynôme localisateur d'erreurs de l'itération précédente anl(X) qui est produit par un bloc de retard 80. Le polynôme localisateur d'erreurs de l'itération précédente Onl(X) est également appliqué au multiplexeur 50 par un bloc de retard 70, pour être appliqué au second bloc 12 2714555 de multiplication 30 pour le calcul du terme temporel lors d'une itération suivante. En utilisant le dispositif présenté ci- dessus, on peut remettre au point, en deux cycles d'horloge, le polynôme localisateur d'erreurs. 13 2714555 REVENDICATIONS 1. Procédé de production d'un polynôme localisateur d'erreurs d'une énième itération à utiliser dans un système de décodage pour décoder un signal transmis, codé par l'utilisation d'un code de Reed-Solomon en se basant sur un nombre prédéterminé de valeurs de syndrome, un groupe de variables d'une (n-l)ième itération comprenant un écart et son polynôme localisateur d'erreurs, et un polynôme localisateur d'erreurs d'une (n-2)ième itération, caractérisé en ce qu'il comprend les étapes de: (a) déterminer un terme temporel basé sur l'écart de la (n- 1)ième itération et le polynôme localisateur d'erreurs de la (n-2)ième itération; (b) calculer un écart de la énième itération en se basant sur les valeurs de syndrome et le polynôme localisateur d'erreurs de la (n-1)ième itération; (c) décider d'un terme de correction en se basant sur ledit terme temporel et l'écart de la énième itération; et (d) calculer le polynôme localisateur d'erreurs de la énième itération en se basant sur le terme de correction et le polynôme localisateur d'erreurs de la (n-l)ième itération. 2. Procédé selon la revendication 1, caractérisé en ce que les étapes (a) et (b), en tant qu'une unité d'opération et les étapes (c) et (d), en tant qu'une autre unité d'opération, sont accomplies alternativement, o chacune desdites étapes de chaque unité d'opération est accomplie dans un même cycle d'horloge. 3. Procédé selon la revendication 1, caractérisé en ce que le terme temporel T(x) est représenté par: - T(x) =dn-1 On-2(X), dn_1 et an_2(x) étant l'écart de la (n-1)ième itération et du polynôme localisateur d'erreurs de la (n-2)ième itération.; le terme de correction c(x) est représenté par: 14 2714555 c(x) =dn.T(x) dn étant l'écart de la énième itération; et le polynôme localisateur d'erreurs de la énième itération on(x) est représenté par: an(X) = an-l(X)-x/c(x), Gn_1(X) étant le polynôme localisateur d'erreurs de la (n-l)ième itération. 4. Dispositif pour produire un polynôme localisateur d'erreur d'une énième itération à utiliser dans un système de décodage pour décoder un signal transmis, codé par l'utilisation de Reed-Solomon, en se basant sur un nombre prédéterminé de valeurs de syndrome, un groupe de variables d'une (n-1)ième itération comprenant un écart et son polynôme localisateur d'erreurs, et un polynôme localisateur d'erreurs d'une (n-2)ième itération, ledit dispositif comprenant: un premier bloc de multiplication (10) pour calculer un écart de la énième itération en se basant sur les valeurs de syndrome et le polynôme localisateur d'erreur de la (n-l)ième itération; un second bloc de multiplication (30) pour déterminer alternativement un terme temporel en se basant sur l'inverse de l'écart de la (n-1)ième itération et le polynôme localisateur d'erreurs de la (n-2)ième itération; et un terme de correction basé sur ledit terme temporel et ledit écart de la nième itération; et un bloc d'addition (60) pour calculer le polynôme localisateur d'erreurs de la énième itération en se basant sur ledit terme de correction et ledit polynôme localisateur d'erreurs de la (n-l)ième itération. 5. Dispositif selon la revendication 4, caractérisé en ce que le polynôme localisateur d'erreurs de la nième itération est produit dans un groupe de deux cycles d'horloge comprenant un premier et un second cycles d'horloge; l'écart de la nième itération et le terme temporel sont calculés aux 2714555 premier et second blocs de multiplication (10, 30), respectivement, pendant le premier cycle d'horloge; le terme de correction est calculé au second bloc de multiplication (30) pendant le second cycle d'horloge; et le polynôme localisateur d'erreurs de la énième itération est calculé au bloc d'addition (60) pendant le second cycle d'horloge. 6. Dispositif selon la revendication 4, caractérisé en ce que le terme T(x) est représenté par: T(x)=dn_-l.an-2(X), dnl et an_2(x) étant l'écart de la (n-1)ième itération et du polynôme localisateur d'erreurs de la (n-2)ième itération; le terme de correction c(x) est représenté par: c(x)=dn.T(x) dn étant l'écart de la énième itération; et le polynôme localisateur d'erreurs de la énième itération on(x) est représenté par: an(X) = an-l(X) - x.c(x), anl(x) étant le polynôme localisateur d'erreurs de la (n-l)ième itération.