Projet de recherche doctoral numero :3666

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