Interprétation et amélioration d’une procédure de démodulation itérative

La géométrie de l’information est la structure géométrique naturelle différentiable que possèdent les familles de distributions de probabilité : chaque distribution de probabilité est considérée comme étant un point dans un espace. Cet espace n’a pas les propriétés d’un espace euclidien, cependant il est possible de définir des pseudo-distances en termes de divergence de Kullback-Leibler. Cette technique s’est avérée assez pertinente pour l’analyse et l’illustration des algorithmes itératifs. Dans cette thèse, la technique géométrique ainsi que celle de l’algorithme itératif du point proximal sont appliquées sur les algorithmes itératifs en général. L’optimum exact d’une fonction est en général impossible à calculer. L’algorithme du point proximal permet de calculer une valeur approchée de cet optimum d’une manière itérative. Depuis son introduction en 1970, divers travaux ont été entrepris concernant l’étude de la convergence de cet algorithme. L’algorithme de Blahut Arimoto est un algorithme itératif permettant le calcul de la capacité des canaux discrets sans mémoire. Notre travail apporte des interprétations géométriques (basée sur la géométrie de l’information) et proximales (basée sur l’algorithme du point proximal) de cet algorithme. Ces interprétations se sont révélées assez intéressantes. Une seconde partie de ce travail est consacré à l’extension de ces techniques sur une classe d’algorithmes itératifs plus compliqués tels l’algorithme de décodage itératif des modulations codées à bits entrelacés dans le but d’apporter certaines améliorations par rapport au cas classique de ces algorithmes tout en essayant de généraliser ici les résultats obtenus dans le cas de l’algorithme de Blahut-Arimoto.

La géométrie de l’information concerne l’application de la géométrie différentielle à des familles de distributions de probabilité et donc à des modèles statistiques. C’est la structure géométrique naturelle différentiable que possèdent les familles de distributions de probabilité [AN00].

Deux types d’information jouent un rôle important dans ce domaine :
– La divergence de Kullback Leibler ou entropie relative
– L’information de Fisher qui prend en compte la courbure

La géométrie de l’information a été appliquée dans l’étude des turbo codes et des codes LDPC [ITA04]. L’idée principale de la géométrie de l’information est que les distributions de probabilité sont considérées comme des points dans un espace. Cet espace n’a pas les propriétés d’un espace euclidien, cependant il est possible de définir des distances, en termes de divergence de Kullback-Leibler (KL). Parmi les concepts de la géométrie de l’information, on peut citer la projection, qui cherche le point le plus proche dans un sous-espace par rapport à un point fixe dans l’espace. Il existe dans la littérature un algorithme itératif simple appelé processus de minimisation alternée [CT84] utilisé pour résoudre ce problème. Nous verrons, dans les chapitres suivants, certaines applications de la géométrie de l’information dans l’analyse de certains algorithmes itératifs.  Des résultats liés à la convergence de cet algorithme de projections alternées figurent dans [LM08] où les auteurs montrent la convergence de cet algorithme vis à vis de l’angle entre les espaces sur lesquels on projette les distributions de probabilité.

Plusieurs études ont été basées sur ces techniques de la géométrie de l’information afin de proposer certaines interprétations de quelques algorithmes itératifs connus dans le but de proposer des améliorations considérables vis à vis de ces algorithmes. Parmi ces études, certaines ont considéré comme application les algorithmes de turbo décodage itératif et essayé grâce à ces techniques géométriques d’améliorer leur fonctionnement classique et trouver des liens intéressants avec d’autres algorithmes de décodage bien connus dans la littérature, notamment le décodage par Maximum a Posteriori et celui par Maximum de Vraisemblance [Ric00, ITA04, WRJ06, MDdC02, Muq01, AND11]. D’autres ont traité d’autres catégories d’algorithmes itératifs notamment l’algorithme de Blahut-Arimoto pour le calcul de la capacité des canaux discrets sans mémoire et ont utilisé ces techniques dans le but de trouver des interprétations géométriques pouvant aider à améliorer le fonctionnement classique de ces algorithmes [MD04, NAD09]. Beaucoup d’autres applications de cette technique ont été étudiées, cependant nous nous sommes concentrés dans cette thèse sur les applications concernant quelques algorithmes itératifs simples utilisés en communications numériques.

Parmi les divers études utilisant l’algorithme de point proximal dans l’analyse des algorithmes itératifs, on peut citer les travaux d’Alfred Hero [CH98, CH08]. Dans ces travaux, les auteurs proposent une version accélérée de l’algorithme EM (Expectation Maximization) suite à une interprétation de type point proximal de cet algorithme utilisant aussi la distance de Kullback dans le terme de pénalité et profitant de la propriété de la convergence super linéaire. D’autres travaux viennent dans la suite compléter ces résultats préliminaires [Tse04].

En 1972, R. Blahut et S. Arimoto [Ari72, Bla72] ont proposé simultanément un algorithme itératif de calcul de la capacité des canaux sans mémoire avec des entrées et des sorties à alphabets finis ainsi que les fonctions de taux de distorsion. Depuis, plusieurs extensions ont été proposées citons notamment [DYW04] qui a étendu l’algorithme de Blahut-Arimoto aux canaux avec mémoire et entrées à alphabets finis et [Dau06] qui a considéré des canaux sans mémoire avec des entrées et/ou des sorties continues.

En parallèle, d’autres travaux se sont concentrés sur l’interprétation géométrique de l’algorithme de Blahut-Arimoto en termes de projections alternées [CT84].