FR2776115A1 - Dispositif de correction d'erreurs et lecteur de disque optique comportant un tel dispositif - Google Patents

Abstract

Dispositif de correction d'erreur Reed-Solomon, comportant des moyens de correction de type Reed-Solomon (2, 3, 4) apte à réaliser des passes de correction, ce dispositif comportant en outre :- une première mémoire (5) destinée à contenir des données de type DVD, ainsi que des données de type CD (C2) après une première passe de correction, en vue du désentrelacement desdites données de type CD avant une seconde passe de correction;- une seconde mémoire (6) de capacité moindre que ladite première mémoire destinée à contenir des données de type CD (C1) avant correction, ainsi que des données de type CD désentrelacées (C2). L'invention concerne également un lecteur de disques optiques comportant un tel dispositif.

Description

L'invention concerne un dispositif de correction d'erreurs de type

Reed-Solomon et un appareil de lecture optique comportant un tel dispositif.

L'invention s'applique notamment dans le cadre de la correction d'erreur dans

des appareils de lecture de disques optiques ou magnéto-optiques.

Le disque compact, généralement abrégé 'CD', a été introduit sur le marché en 1982. Etant donné le besoin de supports de capacité de plus en i i plus grande et pour tenir compte des évolutions dans les domaines de l'enregistrement, du codage et de la lecture de données, un nouveau standard a récemment vu le jour. Il s'agit du standard dit DVD. Ce dernier repose, pour la lecture, sur des principes similaires à ceux du CD, mais permet une plus

grande densité d'information.

Une compatibilité des disques CD avec les lecteurs DVD est bien évidemment souhaitable pour les utilisateurs. Or, le codage des données dans les deux standards est très différent: paquets de données de longueur différente et entrelaçage des paquets également différent, paramètres de la

correction d'erreur différents.

Typiquement, au niveau de la correction d'erreur de type Reed-

Solomon, pour qu'un appareil de lecture puisse décoder à la fois le format CD et le format DVD, deux circuits, dédiés respectivement à la correction d'erreur type CD et à la correction d'erreur type DVD seraient utilisés au sein d'un

même appareil.

Il est bien évident que cette solution n'est pas satisfaisante, car des éléments redondants sont employés, ce qui grève le coût du dispositif. De plus, étant donné la différence de format des paquets de données de type DVD ou CD à traiter, il est difficile de trouver une configuration qui soit satisfaisante

dans le cas de chaque traitement.

L'invention propose par conséquent un dispositif de correction

pouvant effectuer la correction des deux formats.

L'invention a pour objet un dispositif de correction d'erreur Reed-

Solomon, comportant des moyens de correction de type Reed-Solomon apte à réaliser des passes de correction caractérisé en ce qu'il comprend en outre: - une première mémoire destinée à contenir des données de type DVD, ainsi que des données de type CD après une première passe de correction, en vue du désentrelacement desdites données de type CD avant une seconde passe de correction; - une seconde mémoire de capacité moindre que ladite première mémoire destinée à contenir des données de type CD avant correction, ainsi

que des données de type CD désentrelacées.

On utilise donc deux mémoires, une première de taille relativement grande, permettant de stocker les paquets de type DVD ainsi que les paquets de type CD après la première passe, et une seconde, de taille beaucoup plus

faible, destinée à être utilisée uniquement lors de la correction en mode CD.

Ceci a pour avantage de ne faire appel a la première mémoire lors de la correction en mode CD uniquement pour le désentrelaçage requis. La s fréquence d'accès à cette première mémoire est donc réduite, et permet l'utilisation d'une mémoire moins performante, donc moins chère. Ceci est particulièrement intéressant lorsque la première mémoire est un circuit du commerce. Selon un mode de réalisation particulier, les symboles correspondant aux données de type DVD sont transmis aux moyens de correction de type Reed-Solomon à partir de ladite première mémoire, tandis que les symboles correspondant aux données de type CD sont transmis aux moyens de correction de type Reed- Solomon à partir de ladite seconde

mémoire.

La seconde mémoire est utilisée pour effectuer une correction à la volée pour deux raisons: premièrement, étant de petite taille, on peut utiliser une mémoire à haute performance du point de vue fréquence d'accès; 3o deuxièmement, les mots de code de type CD se prêtent mieux à une telle

correction que les mots de code de type DVD, beaucoup plus volumineux.

L'invention a aussi pour objet un lecteur de disques optiques

comportant le dispositif de correction.

D'autres avantages et caractéristiques de l'invention apparaîtront à

travers la description d'un exemple de réalisation non limitatif décrit à l'aide des

figures parmi lesquelles: la figure 1 est un diagramme illustrant le codage RS d'un bloc de données de type CD, la figure 2 est un diagramme illustrant le codage RS d'un bloc de données de type DVD, la figure 3 est un diagramme bloc du dispositif conforme au présent exemple de réalisation, la figure 4 est un diagramme bloc illustrant les échanges de données en mode dit mode 'DVD', la figure 5 est un diagramme bloc illustrant les échanges de données en mode dit mode 'CD', la figure 6 est un diagramme illustrant le stockage d'un paquet de données de type DVD dans une mémoire du dispositif conforme à l'invention, la figure 7 est un diagramme illustrant l'organisation des données à l'intérieur d'une mémoire du dispositif conforme à l'invention, la figure 8 est un schéma des deux registres de coefficients de polynômes utilisés par le résolveur d'équations des figures 3 à 5, la figure 9 est un diagramme illustrant la connexion de cellules à

registres dans un circuit résolveur d'équations utilisé dans le décodage Reed-

Solomon, la figure 10 est un diagramme bloc d'une cellule de la figure 9, la figure 1 1 est un diagramme bloc de la cellule de la figure 10 dans une première configuration, la figure 12 est un diagramme bloc de la cellule de la figure 10 dans une seconde configuration, la figure 13 est un diagramme bloc de la cellule de la figure 10 dans une troisième configuration, >30 la figure 14 est un diagramme bloc de plusieurs cellules de la figure placées en série selon une première configuration, la figure 15 est un diagramme bloc de plusieurs cellules de la figure placées en série selon une deuxième configuration, la figure 16 est un diagramme bloc d'un lecteur de disque optique

comportant un dispositif conforme à l'invention.

Le standard CD ('Compact Disc') préconise l'utilisation d'un code correcteur d'erreur Reed-Solomon à entrelacement croisé ("Cross Interleaved Reed-Solomon error-correction code" ou CIRC). La mise en oeuvre de ce code comporte le partage de chaque échantillon digital de 16 bits à coder en deux symboles de 8 bits. La figure 1 illustre plus particulièrement la structure d'un bloc de

données (trame) conformément au standard CD.

Les échantillons à coder sont stockés dans une mémoire vive et io présentés à l'encodeur sous la forme de blocs de vingt-quatre symboles

(correspondant à six échantillons de 16 bits pour chacun des deux canaux).

Selon une première étape, ces symboles sont entrelacés, en retardant de deux échantillons les échantillons pairs et en intervertissant les connexions vers la première partie de l'encodeur, dit encodeur C2. L'encodeur C2 détermine quatre symboles de parité de 8 bits (dits symboles Q) à partir du mot de code de 24 symboles, et insère les quatre symboles de parité parmi les autres symboles. En résultent 28 symboles. L'encodeur C2 est donc un encodeur

(28,24).

Les symboles sont transmis au second encodeur, appelé encodeur C2, à travers 28 lignes à retard de longueur inégale, multiples de quatre blocs, de façon à répartir les 28 symboles d'un mot sur 28 blocs différents. Ces 28 blocs seront ensuite entrelacés avec d'autres blocs, à raison d'un bloc parmi les 28 blocs pour trois autres blocs. L'encodeur ajoute quatre symboles de parité de 8 bits supplémentaires (symboles P) à chaque bloc, portant le total à 32 symboles. L'encodeur C1 est donc un encodeur (32,28). Ces symboles sont utilisés, après un traitement supplémentaire consistant à inverser les symboles

de parité et à retarder les symboles pairs, pour former un paquet de données.

A ces données s'ajoutent un certain nombre d'informations de contrôle, qui ne seront pas détaillées ici. Pour plus d'informations sur le codage des données, on se reportera entre autres au chapitre 9 de l'ouvrage 'Digital Audio and Compact Disc Technology', troisième édition 1995, Sony Service Centre Europe. ou encore à l'ouvrage 'Reed-Solomon Codes and their

applications', Wicker/Bhagarva, IEEE Press 1994, chapitre 4.

La correction des paquets de type CD nécessite donc deux passes à travers un décodeur Reed-Solomon, la première pour le décodage Cl et la seconde pour le décodage C2, avec un désentrelacement entre les deux passes. Si la capacité de correction de C1 est dépassée (en fonction du nombre d'effacements et d'erreurs à corriger), les 28 symboles (32 moins les quatre symboles de parité P) sont marqués de drapeaux d'effacement ('erasure flags') et ne sont pas corrigés. Lors du désentrelacement, ces 28 symboles seront répartis sur 28 blocs. Si la capacité de correction de C2 est dépassée, les 24 symboles (28 moins les quatre symboles de parité Q) sont marqués d'un drapeau et ne

sont pas corrigés.

La correction d'erreur utilisée dans le cadre du DVD ('Digital VideoNersatile Disc') est différente: un bloc de 192 lignes de 172 symboles (un symbole = 1 octet) est associé verticalement à un code ReedSolomon dit externe ('PO') composé de 16 lignes de 172 octets, puis horizontalement à un code Reed-Solomon dit interne ('PI') composé de 208 lignes de 10 octets. Le code interne est calculé à partir du bloc de données et à partir du code externe. L'ensemble donne un bloc de 208 lignes de 182 octets. Les 16 lignes du code externe sont ensuite insérées de manière entrelacée parmi les 192

lignes restantes.

La structure d'un paquet de données conforme au standard DVD est

2o illustrée par la figure 2.

La figure 3 est un diagramme bloc du dispositif selon le présent

exemple de réalisation.

Un circuit 1 comporte en série, pour les besoins de la correction d'erreur proprement dite, un générateur de syndromes 2, un résolveur

d'équations 3 et un correcteur 4.

Une mémoire vive 5 externe au circuit 1, par exemple du type SRAM, sert à stocker certains paquets de données brutes à corriger et les données corrigées. Une mémoire vive interne 6, utilisée uniquement en mode o CD, est destinée à stocker des résultats de décodage intermédiaire. Ceci évite

avantageusement un accès trop fréquent à la mémoire externe 5.

Le circuit 1 comporte en outre quatre multiplexeurs qui, selon leur état, définissent le mode de fonctionnement CD ou le mode de fonctionnement DVD, ainsi que les diverses étapes dans le cadre de chaque mode. Un premier multiplexeur 7 sélectionne, à l'entrée du générateur de syndromes 2, soit les données en provenance de la SRAM 5, soit les données en provenance de la mémoire 6. Un second multiplexeur 8 sélectionne à l'entrée de la mémoire 6 soit les données en provenance de la SRAM 5, soit les données entrantes en provenance de l'extérieur du circuit (ligne I sur la figure 1). Un troisième multiplexeur 9 sélectionne, à l'entrée du correcteur 4, soit des données en provenance de la SRAM 5, soit des données en provenance de la mémoire 6, soit des données en provenance du résolveur d'équations 3. Un quatrième multiplexeur 10 alimente la SRAM 5, soit par des données corrigées en

provenance du correcteur 4, soit par des données entrantes (I).

La mémoire 5 est utilisée pour stocker les blocs de type DVD, les drapeaux d'erreur ou d'effacements associés à ces blocs avant ou après une io passe de correction, les blocs C2 de type CD dans un but d'entrelacement avant correction, des drapeaux d'erreur qui y sont associés, les blocs C1

corrigés et diverses données de synchronisation.

Chaque passe de correction d'erreur Reed-Solomon effectuée par le

in circuit 1 peut être résumée comme suite, que ce soit en mode CD ou DVD.

Etape 1. Calcul des syndromes Sj, du polynôme d'effacement E(z) et du syndrome modifié T(z): r - 1 S(z)= v- S z o r est le nombre de symboles de parité dans un mot de code, et o Sj v ricl1J (1) i-0 o n est le nombre de symboles d'un mot de code, o les n -1.zn- 2_ coefficients r, sont tels que r(x) =: r n _ r rn - -..-r0 o r(x) est un mot de code reçu, et o a' est une racine de g(z), polynôme générateur, e A E(z) (1- z-Jk) (2) k= O O AJk est la position d'un effacement k et o e est le nombre d'effacements, T(z)=S(z)E(z) mod z2t (3)

o t est un paramètre du code RS.

Remarque: le paramètre r dépend de la correction en cours. C'est le nombre de syndromes à calculer pour chaque mot de code. Il est égal au nombre de symboles de parité dans le mot de code à corriger: 4 et 4 pour les deux codages C1 et C2 du disque compact, 10 et 16 pour les codages interne

et externe du DVD.

Etape 2. Mettre en oeuvre l'algorithme d'Euclide étendu pour calculer le polynôme de localisation d'erreur A(z) et le polynôme d'évaluation d'erreur Q(z), et calculer le nouveau polynôme de localisation d'erreur I(z), o tF(z) =A(z)E(z) mod zt (4) Etape 3. Mettre en oeuvre l'algorithme de Chien pour déterminer les racines du polynôme de localisation d'erreur. Les racines de ce polynôme indiquent les positions des erreurs et des effacements dans les symboles 2o reçus. Mettre en oeuvre l'algorithme de Forney pour déterminer les valeurs des erreurs et des effacements a partir des racines du polynôme de localisation d'erreur, de la dérivée du polynôme de localisation d'erreur et du polynôme

d'évaluation d'erreur.

Etape 4. Vérifier le processus de décodage et corriger les symboles reçus. Les algorithmes mentionnés sont, en soi, connus par ailleurs. On se référera notamment à l'ouvrage 'Reed-Solomon Codes and their Applications', édité par S.B. Wicker et V.K. Bhagarva, IEEE Press 1994, en ce qui concerne des implémentations de l'algorithme d'Euclide et les algorithmes de Chien et de

Forney, et de manière générale, la théorie mathématique des codes Reed-

Solomon. Il existe d'ailleurs dans la littérature d'autres algorithmes pour

réaliser chacune des étapes.

Dans ce qui suit, on décrira dans un premier temps le fonctionnement du dispositif dans chaque mode, DVD ou CD, puis dans un deuxième temps, on s'attachera à décrire plus en détail l'implémentation matérielle de certains aspects du décodeur Reed-Solomon, en particulier le

résolveur d'équations 3.

- Décodaqe DVD Le fonctionnement en mode DVD est illustré par la figure 4. Par rapport au schéma général de la figure 3, les parties du circuit 1 non

concernées par le fonctionnement en mode DVD ont été effacées.

(a) Code interne (PI) - Première passe Les données entrantes sont stockées dans un premier temps dans la SRAM 5, en transitant par le multiplexeur 10. La figure 6 montre la façon dont les blocs sont stockés dans la SRAM 5. Ces données sont composées de deux blocs de 208*182 octets. Chaque bloc est accompagné de 208*23 octets d'effacement. Chaque bit d'effacement indique pour un symbole d'un bloc si ce symbole est à considérer comme sûr ou non. Cette information est utilisée ensuite au cours de la correction d'erreur Reed-Solomon. Ces bits d'effacement sont déterminés de façon connue en soi par un ensemble extérieur au circuit 1. Selon le présent exemple de réalisation, cet ensemble extérieur vérifie la présence de la donnée dans une table de démodulation numérique. Dans un premier temps, le circuit procède au décodage du code RS interne PI. Le bloc de données ou symboles, ainsi que les bits d'effacement sont lus ligne par ligne dans la SRAM 5 et transférés au générateur de syndromes 2. Celui-ci détermine pour chaque ligne (chaque mot de code) le polynôme S(z) et le polynôme d'effacement E(z), tels que définis

Wo précédemment.

Pratiquement, les syndromes Sj sont calculés de la façon suivante: n-I Sj= riTJ iO o T est la matrice associée au polynôme générateur G(z). Selon le présent exemple, G(z) = z8 + z4 + z3 + z + 1. Dans ce cas, la matrice T est:

0 0 0 0 0 0 1]

0 0 0 0 0 0

0 I 0 0 0 0 0 I

0 0 1 0 0 0 0 1

0 0 0 1 0 0 0 1

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

O 0 0 0 0 0 I 0

Les calculs des Sj syndromes sont effectués par le générateur 2, à l'aide de j registres rebouclés chacun sur leur entrée respective à travers un multiplicateur par T net un additionneur. Les syndromes Sj constituent les

coefficients du polynôme S(z).

Dans le cas du décodage DVD, chaque ligne transférée comporte donc 182 octets de données, chaque octet représentant un symbole, ainsi que 182 bits d'effacement. un pour chaque symbole. Le code interne Pl étant constitué de 10 symboles de correction, 10 syndromes sont calculées. Le lm générateur 2 détermine également à partir de s b its d'effacement les coefficients Ej du polynôme d'effacement E(z) et les stocke dans un registre approprié. S'il y a plus de dix effacements dans une ligne, la correction n'est pas possible et le mot de code est marqué comme erroné. L'état erronée d'un 2o mot de code est inscrit dans la mémoire SRAM (Figure 6), sous la forme d'un

bit ( 'Inner 1 Error Flag').

Les coefficients de S(z), et le cas échéant de E(z), sont transmis au

résolveur d'équations 3.

coefi Si un polynôme d'effacement E(z) existe (au moins un effacement), alors lu e circuit 3 calcule le polynôme T(z), produit de E(z) par S(z), puis met en oeuvre l'algorithme étendu d'Euclide pour déterminer en même temps le polynôme de localisation d'erreur A(z) et le polynôme d'évaluation d'erreur (5) S u Si aucun effacement n'existe, alors la détermination de Q(z) et de A(z) est effectuée directement à partir de S(z) (en ce qui concerne les calculs, on prendra dans ce cas E(z)=1),

Le circuit 3 détermine également, le cas échéant, T-(z).

La structure et le fonctionnement du circuit 3 seront vus en détail

plus loin.

Le correcteur 4 exécute de façon connue les algorithmes de Chien

io et Forney.

Ce correcteur disposera donc finalement des données suivantes: - les positions des erreurs dans le mot de code traité, - les valeurs de ces erreurs,

- le nombre d'effacements.

Les erreurs dans le mot de code sont corrigés en conséquence.

Pour ce faire, le circuit correcteur 4 (figure 4) lit le mot de code à corriger dans

la mémoire SRAM 5 et les positions et valeurs des erreurs à partir du circuit 3.

Le correcteur 4 inscrit le mot de code corrigé dans la SRAM 5, à l'emplacement du mot de code initial. Les multiplexeurs 9 et 10 sont commandés en conséquence. Si la capacité du code RS est dépassée, le correcteur inscrit un

drapeau d'indication d'erreur (Référence 'Inner 1 Error Flags' de la figure 6).

(b) Code externe (PO) Le dispositif réalise ensuite une seconde correction sur la base du code PC. En fonction du résultat pour chaque mot de code vertical, un drapeau d'erreur est mis à une valeur appropriée (Référence 'Outer Error Flag' de la

figure 6).

(c) Code interne (PI) - Seconde passe Une fois la correction PC réalisée, une seconde correction horizontale est effectuée sur la base du code interne PI. Certains mots qui n'étaient pas corrigibles lors de la première passe peuvent l'être devenus suite à la correction de certains symboles de ces mots lors de la correction à base du code PO. Le cas échéant, des drapeaux d'erreur (Référence 'Inner 2 Error

Flag' de la figure 6) sont mis à la valeur appropriée.

Cette dernière passe peut être optionnelle.

-Décodaqe CD Le fonctionnement en mode CD est illustré par la figure 5. Par rapport au schéma général de la figure 3, les parties du circuit 1 non

concernées par le fonctionnement en mode CD ont été effacées.

Dans un premier temps, les données à corriger (blocs C1 de 32 symboles) sont inscrites dans la mémoire vive interne 6 à travers l'entrée E. La

figure 7 illustre la façon dont les données sont inscrites dans cette mémoire 6.

La mémoire 6 comporte de l'espace pour trois blocs de 32 symboles chacun.

Les blocs C1 sont entrelacés lorsqu'ils sont stockés dans la mémoire 6. Etant donné la nature de l'entrelacement, deux blocs sont nécessaires pour obtenir un mot de code C1. L'emplacement du troisième bloc est utilisé pour l'écriture du bloc C1 suivant, cette écriture ayant lieu pendant la correction d'un bloc précédent. 28 emplacements de la mémoire 6 sont réservés à un mot de code de 28 symboles (code C2). Quatre emplacements sont réservés à d'autres informations, ce qui donne à la mémoire une longueur de 128 mots. La mémoire possède une largeur de 9 bits, 8 bits étant destinés à stocker des symboles, le neuvième indiquant les effacements. Initialement, les bits

d'effacement indiquent si les symboles stockés sont valides ou non valides.

Le générateur de syndromes 2 lit un premier mot de code désentrelacé dans la mémoire 6, ainsi que les bits d'effacement correspondants. Les traitements effectués par le circuit 2, ainsi qu'ensuite par le résolveur 3, sont similaires à ceux du mode DVD, étant entendu que les paramètres du code Reed-Solomon ne sont pas les mêmes. Le principe de la

3o correction est cependant identique.

Lemplacement des erreurs et leur valeur est communiquée par le résolveur 3 au correcteur 4. Ce dernier reçoit de la RAM 6 tous les symboles du mot de code, en dehors des symboles de parité Cl. Si une correction est nécessaire, alors le symbole erroné est remplacé par le symbole corrigé. Les symboles sont ensuite stockés dans la mémoire 5. Il est à noter que dans cette correction à la volée', tous les symboles transitent de la mémoire RAM 6 par le correcteur 4 vers la mémoire 5, tandis que dans le mode DVD, seuls les symboles à corriger transitent de la mémoire 5 à travers le correcteur et de

nouveau vers la mémoire 5.

Cette architecture est basée sur la reconnaissance du fait que les mots de code en mode CD (28 ou 32 symboles) sont bien plus courts qu'en mode DVD (182 ou 208 symboles). Une correction à la volée est réalisée seulement sur les mots de code 'courts', et cela à partir de la mémoire rapide 6, car tous les symboles d'un mot de code doivent alors transiter par le correcteur. Une telle correction à la volée sur de longs mots de code exigerait plus de cycles de la part du correcteur 4, ainsi que la mise en oeuvre d'une io mémoire 5 beaucoup plus rapide et par conséquent plus coûteuse si les mots

de code à corriger de cette façon y étaient stockés.

Cette architecture permet par conséquent d'utiliser une mémoire 5 du commerce, celle-ci étant disposée hors du composant comportant le dispositif décrit ici, et de prévoir sur le composant lui-même une mémoire interne, de taille faible donc peu coûteuse. Ceci vaut pour le cas o la mémoire est implémentée sur un composant autre que la mémoire 6. Il est clair que l'évocation de mémoires 'externe' ou 'interne' n'exclut pas l'application de ce qui est décrit à un circuit intégré comportant à la fois la mémoire 5 et la mémoire 6. La mémoire 5 doit être vue comme une mémoire de

masse, tandis que la mémoire 6 comme une mémoire cache.

L'entrelacement des symboles des mots de code C2 est tel que les 28 symboles d'un même mot de code sont répartis parmi 112 blocs de 32 symboles. A chaque correction de code C1 correspond une correction de code C2. Ainsi, le système ne sera correctement initialisé qu'après 112 trames. De plus, pour pouvoir effectuer le désentrelacement du code C2, après la correction de code C1, les symboles sont stockés dans la mémoire 5, de plus grande capacité que la mémoire 6 et sont relus pour être, d'une part, inscrits dans la mémoire 6 et, d'autre part, fourni directement au générateur de

o syndromes 2.

L'inscription dans la mémoire 6 est nécessaire pour la correction du mot de code par le correcteur 4 'à la volée', car comme mentionné à propos de la correction Cl, dans le mode CD, le correcteur lit les mots de code à corriger

non pas dans la mémoire SRAM 5, mais dans la mémoire vive 6.

Le processus de correction C2 est similaire à ce qui a déjà été exposé pour la correction Cl. Suite à la correction à la volée, les symboles corrigés sont stockés dans la mémoire 5, sans toutefois les symboles de parité

du code C2.

-Résolveur d'équations - Détermination de Q(z) et de A(z)

La suite de la description concerne l'implémentation du résolveur

d'équations. La tâche principale du résolveur d'équations (dénommé aussi 'Key 0o Equation Solver' en langue anglaise) est de déterminer les polynômes de

localisation et d'évaluation d'erreur, respectivement A(z) et (z).

La détermination de Q(z) et de A(z) est effectuée en mettant en oeuvre l'algorithme étendu d'Euclide. On met en oeuvre pour cela deux i registres de polynômes, respectivement RTOP et RBOT, illustrés par la figure 8. L'algorithme d'Euclide étendu est le suivant: Les polynômes Q(z) et A(z) satisfont l'équation A(z) S(z) = Q(z) mod zr deg reé(z) < deg reA(z) (La variable 'r' est égale au nombre de symboles de parité d'un mot de code (capacité de correction du code), c'est à dire àa 2t), On prend comme valeurs initiales An-l (z)= 0 A0(z) = I Q-l(z) = Z Q0 (z)= T(z) 0o (On prendra Q0(z) = S(z)dans le cas o aucun effacement n'est connu). On réalise les itérations suivantes jusqu'à ce que degréQn (z) < degréAn (z) Qn (z) = Qn-2 (z)mod Qn-l(z) (A) An(z) =Anl(Z)*Qn(z)+ An-2(z) (B) Qn(z) = n-2(z)divQn-l(z) (C) Les registres polynomiaux RTOP et RBOT comportent chacun r+1

registres (RTOP(k) et RBOT(k)) de 8 bits, appelés registres de symboles.

Chacun de ces registres de symboles stocke un coefficient d'un des polynômes A(z) ou n(z). Chaque registre RTOP et RBOT est séparé en une partie dite

partie A et une partie dite Q, de droite à gauche.

lo Initialement, le degré de Q(z) est maximal et le degré de A(z) est minimal. Dans les registres RTOP et RBOT, les degrés de Q(z) augmentent vers la gauche, tandis que les degrés de A(z) augmentent vers la droite, à

partir du point de séparation entre les parties A et .

Le tableau 1 illustre le contenu des registres en phase initiale de I'itération. Rang de r+1 r... 2 1 O registre I cellule I ' a_

RBOT 1 0 0 0 0 1:

Pbot 0 0 0 0 O 1 RTOP IF r: -. TX 0 0 Ptop 0 0 1... O 1

Tableau 1

Les drapeaux Ptop et Pbot indiquent pour chaque registre de symbole si ce registre comporte un coefficient de Q(z) (Ptop/bot=O) ou de A(z) (Ptop/bot=l). On définit par ailleurs 'DegTop' et 'DegBot' comme étant les degrés des parties Q de RTOP et RBOT respectivement, ainsi que la variable 'ratio',

qui désigne la rapport RTOP(r+1)/RBOT(r+1I).

L'algorithme étendu d'Euclide se traduit dans ce contexte par: DegBot=r, DegTop=r-1 TANT QUE (DegTop≥t) FAIRE SI ratio <> 0 ET (DegTop<DegBot)

ECHANGER RTOP, RBOT

ECHANGER DegTop, DegBot F ECHANGER Ptop, Pbot

FIN SI

POUR k=r JUSQU'A O SI (Pbot(k)=Ptop(k)=1l) ALORS RBOT(k)=RBOT(k)+ ratio*RTOP(k) l0 RTOP(k+1)=RTOP(k) SINON SI (Pbot(k)=Ptop(k)=0) ALORS RTOP(k+1)=RTOP(k)+ratio*RBOT(k) SINON RTOP(k+1)=RTOP(k)

1:, FIN SI

Ptop(k+1)=Ptop(k)

FIN POUR

DegTop=DegTop-1

FIN TANT QUE

Lorsqu'il faut prendre en compte des effacements, la condition du

TANT QUE devient DegTop≥m, o m=t+(degréE(z)/2).

L'indice k désigne une cellule d'ordre k et les registres qui y sont

contenus.

On définit r+1 cellules, chaque cellule comprenant les deux registres de symboles de RTOP et RBOT ayant le même rang. Chaque cellule doit

également effectuer les opérations définies ci-dessus.

La figure 9 est un schéma illustrant la connexion des r+1 cellules pourformer les registres RTOP et RBOT. Le rectangle en tirets identifie une cellule de base, qui comprend les différents registres, multiplexeurs,

additionneurs et le multiplieur nécessaire pour l'implémentation de l'algorithme.

La figure 10 est un diagramme fonctionnel d'une cellule.

La cellule comporte un registre a 1 bit 101 destiné à stocker le drapeau Ptop, ainsi qu'un registre à 1 bit 102, destiné à stocker le drapeau Pbot. Ces registres sont constitués chacun d'une bascule D commandée de façon appropriée. Un circuit d'inversion 103 possède deux entrées, connectées respectivement aux sorties non inversées Q des registres 101 et 102 (signaux Ptop et Pbot). Ce circuit d'inversion comporte deux sorties, dont la première, référencée Ptop_NEXT, est connectée à l'entrée du registre équivalent au registre 101 de la cellule suivante, et dont la seconde sortie reboucle sur l'entrée D du registre 102. Selon la valeur d'un signal de commande SWAP,

0o Pbot est transmis à la première sortie et Ptop à la seconde, ou inversement.

La cellule comporte également deux registres à 8 bits, référencés 104 et 105, faisant partie respectivement du registre RBOT et RTOP. Ces registres sur 8 bits sont formés par exemple de 8 registres à 1 bit connectés en parallèle. Les sorties respectives des registres 104 et 105 sont connectées chacune à une entrée d'un circuit inverseur 106, commandé par un signal

SELECT.

Le circuit inverseur 106, à l'image du circuit inverseur 103, connecte chaque entrée soit à l'une, soit à l'autre de ses sorties, selon l'état du signal SELECT. La première sortie 107 du circuit inverseur 106 est reliée à une entrée d'un additionneur 108. La seconde sortie 109 du circuit inverseur 106 est reliée à un multiplieur 110, qui multiplie la valeur présente à la sortie 109 par la variable 'ratio'. La sortie du multiplieur 110 est reliée à une entrée de

l'additionneur 108.

Le registre 105 reçoit sur son entrée D un signal RTOP_IN, qui

correspond à la sortie du registre à 8 bits de RTOP de la cellule précédente.

Le signal de sortie de la cellule vers la prochaine cellule est référencé RTOP_NEXT. Cette sortie est constituée par la sortie d'un multiplexeur 11, qui sélectionne, selon la valeur d'un signal de commande référencé OMEGA_C, soit la sortie de l'additionneur 108, soit la seconde sortie

109 du circuit inverseur 106.

En dernier lieu, I'entrée du registre RBOT 104 est reliée par l'intermédiaire d'un second multiplexeur 112, selon la valeur d'un signal de commande référencé LAMBDAC, soit à la sortie du l'additionneur 108, soit à la sortie d'un troisième multiplexeur 113. Ce troisième multiplexeur sélectionne, selon la valeur du signal de commande SWAP, soit la contenu du registre 104

(RBOT), soit celui du registre 105 (RTOP).

Les signaux de commande sont élaborés de la facçon suivante: LAMBDA_C = Pbot AND Ptop OMEGA_C = NOT (Pbot OR Ptop)

SELECT = NOT (SWAP XOR OMEGAC)

EN_MUL = (LAMBDA_C OR OMEGA_C)

La figure 11 représente une cellule dans le cas o Ptop et Pbot sont égaux à 0. Les deux registres 104 et 105 de la cellule contiennent alors des coefficients de Q(z). Cette configuration de la cellule est par consequent dite

io configuration Omega.

De manière similaire, les figures 12 et 13 représentent une cellule dans les cas respectifs o Ptop=Pbot=1 et Ptop est différent de Pbot, et sont

appelées configurations Lambda et Mixte.

Typede SWAP = 0 SWAP=1 cellule Cellule Pbott.+(k)=Ptbot(k) Pbot,+,(k)=Pttop(k) Lambda PtopNEXTt. 1(k)=Ptopl(k) Ptop_NEXTt+1(k)=Pbott(k) RBOT,i(k)=RBOTt(k)+ RTOPt(k)* RBOTt+,(k)=RTOPt(k)+RBOTt(k)* ratio ratio RTOPNEXTt, (k)=RTOPt(k) |RTOPNEXTt+, (k)=RBOTt(k) Cellule Pbott+ ,(k)=Ptbot(k) Pbot+,(k)=Pttop(k) Omega Ptop_N EXTt.+ (k)=Ptopt(k) Ptop_N EXTt+1 (k)=Pbott(k) RBOTt.,(k)=RBOTt(k) RBOTt+,(k)=RTOP,(k) RTOP_NEXTt, (k)=RTOPt(k) RTOP_NEXTt, (k)=RBOTt(k) +RBOTt(k)*ratio +RTOPt(k)*ratio Cellule Pbott,+1 (k)=Pbot(k) Pbott, (k)=Pttop(k) Mixte PtopNEXTt,(k)=Ptopt(k) Ptop_NEXTt.1(k)=Pbot,(k) RBOTt+, (k) = RBOTt(k) RBOT,+1 (k)=RTOPt(k) I RTOP_NEXTt,(k)=RTOP,(k) RTOP_NEXT+,+(k)=RBOTt(k) t5 Tableau 2 Les parties Lambda réalisent la multiplication de l'équation (B),

tandis que les parties Omega réalisent la division de l'équation (C).

Si l'on prend comme exemple le polynôme S(z) tel que: S(1)4z5 a10z4 + 3z3 7z2 +9 +12 S(z) =a z -a z +a z ïa z +a z+a alors les conditions initiales sont: An-l(z) = 0 AO(z) = 1 -I (z) = Z6 no(z) = S(z)

Les tableaux 3 à 10 illustrent le contenu des cellules a la fin de chaque itération de l'algorithme.

Rang 7 6 5 4 3 2 I 0 RBOT 1 O O 0 0 1 0 0 0 0 0 0 1 Pbot; O O 0 1 04 0 0 3 7 a, a1 RTOP a al a3 a7 a9 a12 0 0 Ptop 0 10 10 0 0 0 '1 1 Tableau 3 (Conditions initiales) (DegBot=6 - DegTop=5 - ratio=ca4 - SWAP=1) Rang 7 6 5 4!3 2 1 0 14i 3 7 a1I RBOT a4 ai a' a7 a al 1O Pbot 0 O O 0 0 01 1 RTOP 1 0 0 0 0 0 0 1 Ptop 0 10 0 0 0 10 i 1 Tableau 4 (Itération 1) (DegBot=5 - DegTop=6 - ratio=ct - SWAP=O) Rang 7 6 5 4 3 2 I i0 RBOT 4 cz a a C a Pbot 0 0 0 0 0 0 1 1 RTOP, t4 l S I1l,(f-130 1 0 Ptop 0 0;0) ,0O 0 1 O 1 i Tableau 5 (Itération 2) (DegBot=5 - DegTop=5 - ratio=&'2 - SWAP=O) Rang 7 6 5 4 3 2 1 0 RBOT d a' a3 a7 a9 a'2 a'2 a Pbot 0 0 0 0 00 1 u i O RTOP a2 a2 a 1a 10 0 Ptop 0 0 0 O 1 1 i Tableau 6 (Itération 3) (DegBot=5 - DegTop=4 - ratio=c3 - SWAP=1) RBOT 3 a2 a2 1 0 1 Pbot 0 0 60 0 0 1 1 1 RTOP Pam4alO a3 a a9 al2 a1 a Ptop 0 0 0 0 0 0 1 1 1 Tableau 7 (Itération 4) (DegBot=4 - DegTop=5 - ratio=a" - SWAP=0) Rang 7 16 15 14 3!2 i1 10 RBOT a2 a' 1 a9 1 a Pbot 0 0 0 10 1 1 1l RTOP a9 8 a8 a6 al12 a a 0 ,,.a ___ O O i i '1i Ptop 0 0 i 000 1 1 1 i 1 Tableau 8 (Itération 5) (DegBot=4 - DegTop=4 - ratio=x6 - SWAP=O) Rang 7 16 "5 14 13 i2 11 iO RBOT 2 a a, a,9 a14 a z:2

L. . . . I

Pbot 0 0 ' 10 1 i1 1 RTOP 0 0 0 ai ac1: a o o Ptop O O 0 1i 1 1 Tableau 9 (Iteration 6) (DegBot=4 - DegTop=3 - ratio=0 - SWAP=0) Rang 7 _ 6 5 4 3 2 1 0O (x 2, o9 1- 1 t12 RBOT a aa 1 a a a12 Pbot 0 0 0 0 0 1 1 1 RTOP 0 0 all:1 0 :1' i 0 i0 i Ptop 0 0, o 1 1 1 1 1 Tableau 10 (Itération 7) (DegBot=4 - DegTop=2 - ratio=0 - SWAP=O) On obtient donc finalement A(z)= a 12z2 _a 1lz _ a 14 Q(z)= a Les coefficients de A(z) sont stockés dans la partie Lambda de RBOT, tandis que les coefficients de Q(z) sont stockés dans la partie Omega

de RTOP.

Après le calcul de A(z) et de Q(z), il faut ajuster les coefficients de Q(z) en rebouclant RTOP(r+1) sur RTOP(2) et en effectuant m=t+ (degréE(z)/2) rotations. Détermination de T(z) - syndrome modifié Avantageusement, le résolveur d'équations est également utilisé pour multiplier les polynômes E(z) et S(z) pour le calcul du syndrome modifié T(z). Le résolveur d'équations dispose déjà des multiplieurs nécessaires, car la détermination du polynôme A(z) requiert une multiplication de polynômes. On met à profit ces ressources pour ce qui est de la multiplication E(z)*S(z), ce qui

simplifie la constitution du générateur 2.

Le degré maximal de S(z) est 2t-1=r-1, tandis que celui de E(z) est 2t=r par construction (si le degré de E(z) est supérieur à 2t, le mot de code est marqué comme non corrigible). Le degré maximal de T(z) est donc r+l, ce qui

o20 correspond exactement au nombre de cellules du résolveur d'équations.

La figure 14 illustre la configuration d'une cellule pour la mise en oeuvre d'une multiplication. Les registres Ptop et Pbot servent à déterminer le contenu des registres RTOP(k) et RBOT(k). La configuration des cellules est assez proche de celle illustrée par le diagramme de la figure 12 (Ptop=Pbot=1), c'est à dire la configuration Lambda. Chaque registre RBOT reboucle sur son entrée à travers l'additionneur 108 associé, tandis que l'entrée de chaque registre RTOP est connecté à la sortie du registre RTOP de la cellule précédente. En dernier lieu, I'ensemble des multiplieurs des cellules sont connectés à une même entrée E, en vue de l'introduction des coefficients en série d'un des deux polynômes à multiplier. Dans le cadre du présent exemple, ce sont les coefficients de E(z) qui sont introduits par ce biais, mais on pourrait également introduire les coefficients de S(z). L'entrée E servait dans la configuration utilisee pour la détermination de A(z) et de Q(z) pour fournir la

valeur de 'ratio' à chaque cellule.

Une autre différence avec la configuration Lambda de la figure 12 est que l'état du circuit inverseur 106 demeure identique tout au long de la multiplication. Le principe de fonctionnement est le suivant: Dans un premier temps, les coefficients de S(z) sont stockés dans

les registres RTOP. Un '0' est présenté à l'entrée du premier registre RTOP(0).

Dans un second temps, les coefficients Ei de E(z) sont présentés par ordre d'indice croissant à l'entrée E, à raison d'un coefficient par cycle

d'horloge.

Le nombre de cycles d'horloge nécessaires pour effectuer la

multiplication est égal au degré de E(z).

A titre d'exemple, le tableau 11 donne le contenu de chacun des registres dans le cas d'une multiplication de S(z) et de E(z) o S(z) est de

degré 3 et E(z) de degré 3.

Cycle Cellule 4 3 2 d'Horlo.e ReQistre i

1 RBOT 0 S0 SE0 S0E0

RTOP S2 S2 S0 So

I2 RBOT S3E0+S2E1 S2E0+S1E S1E0+S0E1 S0E0

RTOP S2 S0 So 0 32 RBOT S3E0+S2E1+S1E2 S2E0+S1E1, S1Eo+SoE1 SoEo RTOP Si So 0 0 3 RBOT S3Eo+S2E, +SiE2 S2Eo+SlEl+SoE2 'S1Eo+SoE,;SoEo - t RTOP S, 0 0o '0

4 RBOT S3E0+S2E,+S1E2.S0E3 S2E0+S1E1+S0E2 S1E0+S0E1 S0E0

- RTOP 0 10!O 10

Tableau 1 1

On voit que les registres RTOP(k) forment un registre à décalage servant uniquement à stocker les coefficients de S(z). Le registre à décalage est réalisé en choisissant correctement l'état des inverseurs 106. Les registres RBOT(k) servent d'accumulateurs respectifs pour chaque coefficient du

polynôme T(z).

Chaque registre RBOT(k) contient donc finalement le coefficient Tk, r o T(z)= ETkzk k= 1 Détermination du nouveau polynôme de localisation d'erreur YP(z) Avantageusement, le résolveur d'équations est également utilisé pour multiplier les polynômes E(z) et A(z) pour le calcul de 'F(z). Ce dernier polynôme est calculé une fois A(z) déterminé par le résolveur d'équations. Une fois que l'algorithme étendu d'Euclide a été mis en oeuvre, les coefficients de A(z) sont stockés dans la partie Lambda de RBOT. Les autres registres

RTOP(k) et RBOT(k) sont mis à zéro.

o10 La configuration des cellules pour réaliser la multiplication est

illustrée par le diagramme de la figure 15.

Les registres RTOP(k) sont connectés en série à travers les additionneurs des cellules. La valeur 'O' est présentée à l'entrée du premier registre RTOP(0). La sortie de chaque registre RBOT(k) est connectée au multiplieur de sa cellule k. Les valeurs stockées dans les registres RBOT(k) ne changent pas pendant la présente multiplication. Comme dans la configuration de la figure 14, les entrées des multiplieurs autres que celles connectées à la

sortie des registres RBOT(k) sont interconnectées (référence E).

Le degré de A(z) est égal au nombre d'erreurs. Le degré de E(z) est

égal au nombre d'effacements.

Le tableau 12 donne le contenu des cellules après chaque cycle d'horloge. Cl Cellule -7 6 5 4 3 12 0 O CycleCell!i, i : Reqistre RBOT 0 O',O O Ao A1 A2

RTOP 0 0 O O O 0 0 0

i1 jRBOT 0 0 0 O O A0 Ai A2 : RTOP 0 0 0 0 0 A\oE0.\1E0 A2Eo 0 2 RBOT 0 0 O 10 O 0 Ao A1 A2 1 RTOP 0 0 0 O AoEo A1Eo+ A2Eo+ A2E1 0O RBOITo o o O: I\AoE1 A1E1, 3 RBOT 1 0 0 0 0 0 A1 iA2 RTOP 0O 0 0 AoEo A.Eo+ A2Eo 'A2E+ A2E2 0 AoE1 I AiEI+ A1E2 I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ A oE 2 I i. i 4 RBOT O 0 0 1 0 Ao A1 A2 RTOP 0 0 Ao AiE-o+I A2Eo+ 1A\2E1+ A2E2+ A2E3 0 EO AoE1 A1E1+ A1E2+ A1E3 l_______ _ _ tAoE2 AoE3 I

Tableau 12

Pendant le calcul de u?(z), les multiplieurs restant actifs sont ceux

des cellules pour lesquelles Pbot(k)=1.

Bien que le présent exemple de réalisation concerne la correction ReedSolomon, la configuration de deux mémoires décrite peut être appliquée dans tous les cas o des paquets de données de longueur sensiblement

différente doivent être corrigés.

En dernier lieu, la figure 16 représente un lecteur 200 de disque optique 201 comportent le dispositif conforme à l'invention. Ce lecteur comporte un bloc optique 202 comportant de manière connue un laser, des moyens de focalisation, des détecteurs photoélectriques. Le lecteur comporte également un moteur 203 commandé par une unité d'asservissement 204. Les données lues par le bloc optique sont transmises à un démultiplexeur 205. Les données de contrôle sont transmises à un microprocesseur 206 commandant un affichage 207, I'asservissement de la focalisation 208 et le suivi de piste

209. Un clavier 210 permet à l'utilisateur de commander le lecteur.

Les paquets de données CD/DVD proprement dits sont transmis par le démultiplexeur 205 au dispositif de décodage 1 relié a la mémoire 5 et à une unité d'interpolation 211 qui fait office d'interface avec des convertisseurs

numérique/analogique non illustrés.

Claims (7)

Revendications

1. Dispositif de correction d'erreur Reed-Solomon, comportant des moyens de correction de type Reed-Solomon (2, 3, 4) apte a réaliser des passes de correction caractérisé en ce qu'il comprend en outre: - une première mémoire (5) destinée à contenir des données de type DVD, ainsi que des données de type CD (C2) après une première passe de correction, en vue du désentrelacement desdites données de type CD avant o10 une seconde passe de correction; - une seconde mémoire (6) de capacité moindre que ladite première mémoire destinée à contenir des données de type CD (Cl) avant correction,

ainsi que des données de type CD désentrelacées (C2).

2. Dispositif selon la revendication 1, caractérisé en ce que les symboles correspondant aux données de type DVD sont transmis aux moyens de correction de type Reed-Solomon à partir de ladite première mémoire (5), tandis que les symboles correspondant aux données de type CD sont transmis aux moyens de correction de type Reed-Solomon à partir de ladite seconde

mémoire (6).

3. Dispositif selon l'une des revendications précédentes, caractérisé

en ce que ladite seconde mémoire est destinée à mémoriser au moins deux paquets de données entrelacés (C1l) de type CD avant une première passe de

correction, de façon à effectuer un désentrelacement desdits paquets.

4. Dispositif selon l'une des revendications précédentes, caractérisé

en ce que les moyens de correction, de type Reed-Solomon comportent un correcteur (4) qui réalise une correction à la volée des symboles correspondant

aux données de type CD à partir de la seconde mémoire (6).

5. Dispositif selon la revendication 4, caractérisé en ce que, dans le cadre d'une correction des données de type DVD, le correcteur (4) lit dans la première mémoire (5) uniquement les symboles à corriger et y inscrit les

symboles corrigés.

6. Dispositif selon l'une des revendications précédentes, caractérisé

en ce que la première et la seconde mémoire comportent des emplacements pour la mémorisation de drapeaux d'erreur pour les données stockés dans ces mémoires.

7. Lecteur (200) de disques optiques (201) caractérisé en ce qu'il

comporte un dispositif selon l'une des revendications précédentes.