Décodage pondéré des codes longs linéaires en blocs, basé sur des statistiques dordre Andrzej Kabat Directeur de thèse : Ramesh Pyndiah Encadrant : Frédéric

Décodage pondéré des codes longs linéaires en blocs, basé sur des statistiques d’ordre

Andrzej KabatDirecteur de thèse : Ramesh Pyndiah

Encadrant : Frédéric Guilloud

Institut TELECOM / TELECOM Bretagne / Dpt SC

Séminaire des doctorants de TELECOM BretagnePage 2 Andrzej Kabat

Sommaire

Les codes de Reed-Solomon ;

Décodage souple et vecteurs de test ;

Proposition d’un algorithme de génération des vecteurs de test.


Perturbation

Codage correcteur d’erreurs, codes en blocs

messagebits de redondance

infod' symboles ksymboles kn ),( code kn


Codes de Reed-Solomon (RS)

Minimum de redondance pour un pouvoir de correction fixé ;

Très répondus : • stockage ;• transmission ;• diffusion ;• (255,251) , (255,239), (255, 223) ;

Décodage algébrique (ferme).


Algorithmes de décodage souple

Deux types d’algorithmes de décodage souple :

1. Décodage avec le décodeur algébrique :• GMD [Forney-66], Chase [Chase-72], GS [Gur-Sud-99],

KV [Koet-Var-03] ;• dépend de la structure algébrique du code ;

2. Décodage par le test et le re-encodage d’un ensemble de bits d’information :

• RBCS [Gaz-Snyd-97], VF [Val-Foss-01], [KGP-07].


Décodage par le test et le re-encodage d’un ensemble de bits d’information

fiabilité

bits reçus

bits de redondance bits d’information

bits reçusarrangés

re-encodage


Décodage par le test et le re-encodage d’un ensemble de bits d’information

.............. ..............

[Dorsch-74]

test 1

test 2

test 3

test ...

bits de redondance bits d’information


Méthodes de génération des vecteurs de test

• Prédéfini [Gaz-Snyd-97]

• Heuristique [Val-Foss-01]

performance

complexité

• Proposé [KGP-07]


Propriétés de l’ALMLT :

ALMLT – Arranged List of the Most a priori Likely Tests :

Fiabilités des bits – estimées hors transmission ; Adapté au décodage des codes longs ; Vecteurs de test – arrangés suivant leurs fiabilités

décroissantes ; Nombre de vecteurs de tests – flexible ; Pendant le décodage – des vecteurs de test sont

lus à partir d’une liste (ils ne sont pas générés au vol).


Performances


Performances en fonction du nombre de vecteurs de test


Complexités


Conclusion Codes RS – une bonne solution pour corriger des

erreurs de transmission ; Algorithme efficace pour le décodage souple des

codes longs linéaires en blocs – effectué par le test et le re-encodage ;

Bonne façon de générer des vecteurs de test – algorithme ALMLT :• Flexibilité - la liste des vecteurs de test peut avoir une

taille quelconque ;• Robustesse - comparé avec des algorithmes compétitifs

ayant le même nombre de vecteurs de test, l’ALMLT minimise également la complexité de décodage et le taux d’erreurs.


Bibliographie

[Forney-66] G. D. Forney Jr., “Generalized minimum distance decoding”, IEEE Trans. Inf. Theory, vol. 12, pp. 125-131, Apr. 1966.

[Chase-72] D. Chase, “A class of algorithm for decoding block codes with channel measurement information”, IEEE Trans. Info. Theory, vol. IT-18, pp. 170-179, Jan. 1972.

[Gur-Sud-99] V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and Algebraic-Geometric codes”, IEEE Trans. Inf. Theory, vol. 45, pp. 1757-1767, Sept. 1999.

[Koet-Var-03] R. Koetter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes”, IEEE Trans. Inf. Theory, vol. 49, no. 5, pp. 2809-2825, Nov. 2003.

[Dorsch-74] B. Dorsch, “A Decoding for Binary Block Codes and J-ary Output Channels”, IEEE Trans. Inf. Theory, May 1974.

[Gaz-Snyd-97] D. Gazelle and J. Snyders, “Reliability-Based Code-Search Algorithms for Maximum-Likelihood Decoding of Block Codes”, IEEE Trans. Inf. Theory, vol. 43, no. 1, Jan. 1997.

[Val-Foss-01] A. Valembois, M. Fossorier, “An Improved Method to Compute Lists of Binary Vectors That Optimize a Given Weight Function With Application to Soft-Decision Decoding”, IEEE Comm. Letters, vol. 5, no. 11, Nov. 2001.

[KGP-07] A. Kabat, F. Guilloud and R. Pyndiah, “New approach to order statistics decoding of long linear block codes”, IEEE Globecom ’07, Nov. 2007.

[Bel-Kav-Ping-07] J. Bellorado, A. Kavcic and L. Ping, “Soft-Input, Iterative, Reed-Solomon Decoding using Redundant Parity-Check Equations”, ITW ‘07, Sept. 2007.


Fiabilités des bits reçus

Fonction de répartition des fiabilitésde bits reçus :

Fonction de répartition des fiabilitésde bits reçus et erronés :

21

21

21 erferf)( xxxF

21

21

erfc

erfc1)(

x

e xF

xdB 3SNR


ordre du bit normaliséni

niF 1

ordre du bit i

1][ 1

n

iFE i

ordre du bit

i

ordre du bit i

Statistiques d’ordre

numéro du bit

rangement n

normalisation

normalisationinverse

Documents

Décodage pondéré des codes longs linéaires en blocs, basé sur des statistiques dordre Andrzej Kabat Directeur de thèse : Ramesh Pyndiah Encadrant : Frédéric