Reed-Solomon decoder.
Première partie : incertitudes et calcul de syndrome.
Fonction d'incertitude.
Polynome d'incertitude / Erasure polynomial.
"Reed-Solomon algebraic decoding procedures can correct
errors and
erasures. An erasure occurs when the position of an erred symbol is known. A decoder can correct up to t errors or up to 2t erasures."
Dans un système de communication avancé, un démodulateur peut fournir une information qui précise la présence d'une
incertitude à un endroit spécifique, c'est le cas dans tous systèmes à démodulation numérique (QPSK, QAM) lorsque le point de la constellation est trop éloigné de sa position théorique ;
dans ce cas, il et plus avantageux de déclarer la valeur incertaine afin de minimiser les probabilités d'erreurs. Dans le cas du niveau d'adaptation 1 des cellules ATM (AAL-1 layer) l'entrelacement de 47 colonnes par 124 lignes plus 4 lignes de redondance RS(128,124,t=2) permet de localiser des octets incertains dans le cas ou une cellule complète à été perdue.
Figure 1 : implémentation matérielle du calcul du polynome d'incertitude.
Γ(1) Γ(2) Γ(3)
^ ^ ^
| | |
+---+ | +---+ | +---+ |
+--->|FD |--+ +--->|FD |--+ +--->|FD |--+
| |X | | | |X^2| | | |X^3| |
| +---+ | | +---+ | | +---+ |
| | | | | |
[ + ]---------+---->[ * ]-->[ + ]<--------+--->[ * ]-->[ + ]<--------+--
^ ^ ^
| | |
+-------------------+-----------+--------------+----------------------
|
|
α^i_k
Il est donc possible de retrouver le message d'origine si 2s + r < 2t avec 'r' erreurs et 's' incertitudes La connaissance de la position de symboles incertains permet donc d'augmenter l'efficacité du décodage RS.
Dans un cas ou nous ne disposerions pas de cette information, les coefficients du polynome seront donc considérés comme nulles et nous ne traiterons que des erreurs.
2t
____
Γ(x) = | | (1 + x.αi_k)
| |
k=1
Les α^i_k^ correspondent à la localisation des erreurs suspectées qui arrivent une par une ; le degrè du polynome est donc incrémenté de 1 à la reception de chaque nouvelle position d'incertitude.
Prenons par exemple un code RS(15,9,7) sur GF(2^4^) avec pour polynome primitif p(x) = 1 + x^3^ + x^4^. Supposons qu'après réception d'un mot r(x) deux incertitudes soient décelées aux positions 0 et 5. Le polynome de localisation d'incertitudes est définit par :
Γ(x) = (1 + α^0.x).(1 + α^5.x)
Γ(x) = α^5.x^2 + α^10.x + 1
Remarquons que le coefficient de plus petit degré est toujours 1 et qu'il n'est donc pas indispensable de le calculer. Les symboles situés aux positions incertaines doivent être remplacés par zéro ; les 2t syndromes peuvent ensuite être calculés.
Polynome du syndrome.
Le syndrome consiste à l'évaluation du mot reçu v(x) pour les zéros du polynome générateur. Lorsque tous les symboles du bloc sont reçus, les n-k valeurs de syndrome sont mémorisées et les registres sont remis à zéro.
Dans le cas d'une transmission sans erreur, c(x)=r(x) et donc r(?^i^)=0 Dans les autres cas, les valeurs calculées sont non nulles et ne dépendent que de l'erreur introduite.
s(x) = ∏ de i=0 à 2.t-1 de [Si.x^i] = S0 + S1.x + S2.x^2 + ...
avec Si = r(α^i) et i=b à b+2td-1
Figure 2 : Implémentation matérielle non optimisée du calcul de syndrome
+---+
+----------|FD |---[*]<-- α^i : zéro de g(x)
| | | ^
| +---+ |
+-------------------+
|
v +---+
r(x) ------>[ * ]-----[ * ] ---->|FD |--+---> Si
^ | | |
r0,r1,r2... | +---+ |
| |
+---------------+
Le nombre de coefficient du polynome de syndrome est donc de 2t=n-k pour un code Reed-Solomon ; ces valeurs correspondent en fait aux composantes spectrales de la transformée de Fourier E(x) du polynôme d'erreur e(x).
L'expression de chaque coefficient du polynome de syndrome, 'Si', peut être développé selon la '''règle de Horner.''' Ceci permet de ramener l'expression sous forme de multiplications imbriquées qui traduit la structure à implémenter en VHDL optimisée.
Cette optimisation de un multiplieur et quelques bascules pour chaque coefficient de s(x) nécessite de recevoir les données d'entrée en ordre inverse, i.e. poids faible du mot d'information en premier.
Figure 3 : Implémentation matérielle optimisée du calcul de syndrome
+-------------------------+
| |
| |
| A^i |
| | |
| | |
v v +---+ |
r(x) -------->[ + ]-----[ * ] ---->|FD |--+---> S(k+1)
| |
r_n-2, r_n-1 +---+
t0 : 0 + r_n-1 (r_n-1).A^i 0
t1 :(r_n-1).A^i + r_n-2 (...).A^i (r_n-1).A^i
Syndrome modifier.
Dans le cas de l'utilisation du polynôme d'incertitude, il est nécessaire de calculer un polynôme de syndrome modifer ?(x) (modified Forney Syndrome).
La multiplication des polynômes de syndrome et d'incertitude est effectuée modulo 2t ; il faut donc calculer 2t coefficients pour ?(x).
Le coefficients de poids faible de ?(x) est toujours 1 ce qui permet d'économiser un multiplieur dans la structure qui suit. La même structure pourra être utiliser ultérieurement pour l'implémentation BMA avec une logique de controle associée.
Ξ(x) = [Γ(x).S(x)] mod x^(2t+1)
Figure 4 : Implémentation du calcul de Xi(x) (restreint à l'ordre 3)
+------+ +------++------++------+
| Γ(0) | | Γ(1) || Γ(2) || Γ(3) |
+------+ +------++------++------+
. | | | +---+
[*] [*]----- | ----- | ---------|xor| +---+
. | [*] ---- | ---------| |---| |
. | | | +---+ |xor|---->
. | | [*] ------- |xor|---| |
+----------- | ----- | ----- | -------- | | +---+
| | | | +---+
+------+ +------++------++------+
---------->| |----->| || || |
S3,S2,S1,S0 +------+ +------++------++------+
t1 S0 0 0 0 S0 car G(0)=1
t2 S1 S0 0 0 S1 + S0G1
t3 S2 S1 S2 0 S2 + S1G1 + S0G2
t4 S3 S2 S1 S0 S3 + S2G1 + S1G2 + S0G3
Quelques exemples.
Regardons quelques exemples simples qui serviront de test bench pour le décodeur Reed-Solomon.
Soit un code RS de longueur 15 sur GF(2^4^) avec pour zéro α, α^2^, ... α^6^ et utilisant comme polynôme primitif p(x) = 1 + x + x^4^. Le code émis v(x) sera tout à zéro. [ref2: section7.7 exemple7.8 ECC Costello]
g(x) = produit de i=1 à 6 de (x - A^i)
v(x) = 0
r(x) = 0 0 0 * 0 0 * 0 0 A 0 0 A^4 0 0
Gamma(x) = (1 + A^3).(1 + A^6)
Gamma(x) = 1 + A^2.x + A^9.x^2
S(x) = {A^8 , A^11 , A^9 , 0 , 1 , A^8}
Xi(x) = {A^8 , A^14 , A^4 , A^3 , A^14 , 1}
Considérons le code RS(15,9,7) sur GF(2^4^) avec pour zéros α, α^2, ... α^6 et comme polynôme primitif p(x) = 1 + x^3^ + x^4^. A est élément primitif du corps et de ce fait 1 + α^3 + α^4 = 0 et α^15 = 1 en particulier. v(x) et r(x) correspondent au mot de code émit et au polynôme reçu. [exemple 43, Robert H. Morelos-Zaragoza The art of error correcting coding]
g(x) = produit de i=1 à 6 de (x - α^i)
g(x) = x^6 + A^12.x^5 + x^4 + A^2.x^3 + A^7.x^2 + A^11.x + A^6
v(x) = {A5, A3, A13, A, A7, A4, A, A4, A6, 0, A3, A5, A6, A13, A10}
r(x) = {A7, A3, A13, A14, A7, A, A, A4, A6, 0, A3, A5, A11, A13, A10}
supposons des incertitudes aux positions A0 et A5
Gamma(x) = 1 + A^10.x + A^5.x^2
S(x) = A^14.x^6 + x^5 + A^2.x^4 + A^2.x^3 + A^5.x^2 + A^11.x + 1
Xi(x) = x^6 + A^9.x^5 + A^11.x^4 + A^7.x^3 + A^6.x^2 + A^7.x
Détail du calcul de Xi :
x0 1 0 (ajout de 1)
x1 A10 A11 A7
x2 A5 A6 A5 A6
x3 A 1 A2 A7
x4 A10 A12 A2 A11
x5 A7 A12 1 A9
x6 A7 A10 A14 1
x7 -- -- -- (modulo 2t+1)
Il était une fois ... Les codes correcteurs d'erreurs.
Notations & glossaire
ECC/CCE : Code Correcteur d'erreurs.
FEC : Forward Error Coding.
α/A : Elémént primitif du corps.
Γ(x) : Polynome d'incertitude.
s(x) : Polynome de syndrome.
Ξ(x) : Syndrome modifier / Forney syndrome.
g(x) : Polynome générateur.
v(x) : Forme poynomiale du code émit.
r(x) : Forme polynomiale du code reçu.