Description
Date depot: 1 janvier 1900
Titre: Reconnaissance de codes LDPC
Directeur de thèse:
Jean-Pierre TILLICH (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
section*{Contexte}
Un code LDPC est un code linéaire de longueur $n$ et dimension $k$
défini par une matrice de parité composée de lignes de poids
$w$ fixé. Ces lignes correspondent à des équations de parité et sont
utilisées pour corriger les erreurs à l'aide d'un algorithme de
décodage itératif. Cet algorithme est particulièrement efficace et
permet d'obtenir, pour un coût algorithmique faible, des performances
s'approchant des limites théoriques de la théorie de l'information.
section*{Le problème}
La séquence binaire observée est constituée d'une concaténation de
mots d'un code LDPC binaire auquel un bruit a été ajouté. Différents
modèles de bruit sont envisageables, mais dans un premier temps nous
considérerons le modèle du canal binaire symétrique dans lequel chaque
bit reçu a une faible probabilité $p$ d'être erroné.
Il s'agit de retrouver à partir de l'observable le code LDPC utilisé.
C'est-à-dire de retrouver la plus grande partie des $r$ équations de
parité de poids faible. Typiquement la longueur $n$ vaudra quelques
milliers, la dimension $kge n/2$ et le poids des équations sera
généralement de quelques unités (6 à 10) mais pourra atteindre
quelques dizaines.
La difficulté du problème provient de sa taille. Le problème de la
reconnaissance de code est intrinsèquement difficile (NP-dur
cite{Val00c,Val01}) et la meilleure technique connue, l'algorithme de
Valembois, résiste mal au bruit lorsque la taille de bloc augmente.
section*{Approches possibles}
Contrairement à d'autres familles, comme par exemple les codes
convolutifs cite{CS09}, il n'existe pas, en général, de structure
algébrique permettant de faciliter le calcul.
L'unique particularité des codes LDPC est l'existence de mots de poids
faible dans leur code dual (les équations de parité). La recherche de
ces mots est difficile y compris en l'absence d'erreur. Lorsque le
poids des équations $w$ est petit, différentes techniques
algorithmiques pourront être étudiées et utilisées pour permettre la
résolution
egin{itemize}
item l'algorithme de Valembois de reconnaissance de codes en blocs
cite{Val01}
item les algorithmes de décodage génériques (qui permettent de
rechercher des mots de petit poids dans un code)
egin{itemize}
item « Information Set Decoding » et ses variantes cite{Ste89}
item « Generalized Birthday Algorithm » cite{Wag02}
end{itemize}
item les algorithmes de fusion de listes cite{CJM02}
end{itemize}
Nous envisagerons également les liens avec les turbo-codes. Les
travaux connus sur la reconstruction des entrelaceurs
cite{CS10,CFT10} ne peuvent pas aider à la reconstruction d'un code
LDPC. En revanche les techniques envisagées ci-dessus pour la
recherche d'équations de parité de poids faible peuvent également être
mise en oe{}uvre pour les turbo-codes cite{SRV01} avec une
amélioration possible des algorithmes existants, en particulier en
présence de poinçonnage.
egin{thebibliography}{1}
ibitem{CJM02}
P.~Chose, A.~Joux, and M.~Mitton.
ewblock Fast correlation attacks: An algorithmic point of view.
ewblock In L.R. Knudsen, editor, {em Advances in Cryptology - EUROCRYPT
2002}, volume 2332 of {em LNCS}, pages 209--221. Springer, 2002.
ibitem{CFT10}
M.~Cluzeau, M.~Finiasz, and J.-P. Tillich.
ewblock Methods for the reconstruction of parallel turbo codes.
ewblock In {em IEEE Conference, ISIT 2010}, pages 2008--2012, Austin, Texas,
USA, 2010.
ibitem{CS09}
M.~{C^ote} and N.~Sendrier.
ewblock Reconstruction of convolutional codes from noisy observation.
ewblock In {em IEEE Conference, ISIT 2009}, pages 546--550, Seoul, Korea,
2009.
ibitem{CS10}
M.~{C^ote} and N.~Sendrier.
ewblock Reconstruction of a turbo-code interleaver from noisy observation.
ewblock In {em IEEE Conference, ISIT 2010}, pages 2003--2007, Austin, Texas,
USA, 2010.
ibitem{Ste89}
J.~Stern.
ewblock A method for finding codewords of small weight.
ewblock In G.~Cohen and J.~Wolfmann, editors, {em Coding theory and
applications}, volume 388 of {em LNCS}, pages 106--113. Springer, 1989.
ibitem{SRV01}
Hong Sun, Didier~Le Ruyet, and Han~Vu Thien.
ewblock Turbo-like codes based on {RSC} code decomposition.
ewblock In {em IEEE Conference, ISIT 2001}, page 297, Washington D.C., USA,
June 2001.
ibitem{Val00c}
A.~Valembois.
ewblock {em D'etection D'ecodage et Reconnaissance des Codes Lin'eaires
Binaires}.
ewblock Th`ese de doctorat, Universit'e de Limoges, October 2000.
ibitem{Val01}
A.~Valembois.
ewblock Detection and recognition of a binary linear code.
ewblock {em Discrete Applied Mathematics}, 111(1-2):199--218, July 2001.
ibitem{Wag02}
D.~Wagner.
ewblock A generalized birthday problem.
ewblock In M.~Yung, editor, {em Advances in Cryptology - CRYPTO 2002},
volume 2442 of {em LNCS}, pages 288--303. Springer, 2002.
end{thebibliography}
Doctorant.e: Tixier Audrey