Télécharger le fichier pdf d’un mémoire de fin d’études
Divergence de Kullback-Leibler
La divergence de Kullback-Leibler ou entropie relative mesure « la distance » entre deux distributions de probabilité définies sur le même domaine. C’est un outil fonda-mental utilisé notamment en statistique et en apprentissage.
Considérons deux distributions de probabilité p = fp(x); x 2 Xg et q = fq(x); x 2 Xg d’une variable aléatoire X prenant ses valeurs x dans un ensemble discret X. La divergence de Kullback-Leibler entre ces deux distributions de probabilité p et q peut être définie comme suit : [CT91, Gal68]
D(pjjq) = X p(x) log p(x) (2.1)
Propriétés
La divergence de Kullback, appelée aussi entropie relative possède quelques proprié-tés d’une métrique :
– D(pjjq) est toujours non négative : D(pjjq) 0
– D(pjjq) = 0 si et seulement si p q
Cependant, cette divergence n’est pas une vraie distance entre distributions car elle ne possède pas la propriété de symétrie. En effet D(pjjq) 6= D(qjjp) et ne satisfait pas en général l’inégalité triangulaire.
Par abus de langage, l’entropie relative est nommée distance de Kullback-Leibler entre distributions de probabilité.
Familles de distribution de probabilité
Une famille de probabilité est un espace dans lequel une distribution de probabilité spécifique est un point caractérisé par ses coordonnées dans cet espace. On distingue plusieurs types de familles dont les plus utiles dans la suite sont :
– Famille linéaire de probabilité
– Famille exponentielle de probabilité
Famille linéaire de probabilité
– Définition :
Une famille linéaire de probabilité est définie comme [CT84] : 8f1; f2; : : : ; fK 2 X et 8 1; 2; : : : ; K
L = fp : Ep(fi(x)) = i; 1 i Kg (2.2)
La valeur de l’espérance Ep(fi(x)) de la variable aléatoire x par rapport à la dis-tribution p(x) est restreinte à i.
Une famille linéaire de probabilité est complètement définie par ffi(x)g1 i K et f ig1 i K .
Familles de distribution de probabilité
Le vecteur = [ 1; : : : ; k] sert de système de coordonnées dans l’espace de la famille linéaire, ces coordonnées sont appelées « coordonnées mixtes ».
– Propriétés : Etant donné p1(x),p2(x) 2 L, et 0 t 1, p(x; t) = (1 t)p1(x) + tp2(x) 2 L (2.3)
– p1(x) 2 L, il en suit que Ep1 (f(x)) =
– p2(x) 2 L, il en suit que Ep2 (f(x)) =
– Ep(f(x)) = (1 t)Ep1 (f(x)) + tEp2 (f(x)) = (1 t) + t = . D’où p(x; t) 2 L. D’autres propriétés liées à la projection sur ces familles linéaires seront mises en évidence dans la suite.
– Exemples :
– Une famille linéaire importante dans le contexte du décodage souple est la famille de distributions compatibles avec le code : LC = fp : Ep((f(x))) = 0g.
Etude de convergence
Convergence super-linéaire
Considérons une suite numérique xn qui converge vers une valeur x , on a donc :
lim xn = xn!1(3.5)
lim jxn+1 x j =x j n!1 jxn (3.6)
Algorithme du point proximal
– S’il existe telle que : 0 < < 1, la convergence est linéaire. étant la vitesse de convergence.
– Si = 0, dans ce cas la convergence est dite super-linéaire.
– On dit que la suite de limite x est convergente d’ordre q (q > 1), s’il existe > 0 telle que : limjxn+1x j=(3.7)
– q = 2: convergence quadratique
– q = 3: convergence cubique
– q = 4: convergence quartique
En se basant sur ces définitions générales, Rockafellar [Roc76] a établi les conditions que doit vérifier la fonction f ainsi que l’opérateur T afin d’avoir une convergence super linéaire de l’algorithme du point proximal. En effet, à partir de l’équation (3.2), on pourra écrire que zk+1 = Pk(zk) (3.8)
où Pk = (I + ckT ) 1 et T étant l’opérateur de différentiel de la fonction f dans ce cas. T et Pk doivent vérifier les deux conditions suivantes :
– T est fortement monotone avec comme module > 0 : < z z0; w w0 > k z z0 k2 8w 2 T (z); w0 2 T (z0) (3.9)
– Pk doit être un opérateur pseudo-contractant : k P (z) P (z0) k k z z0 k (3.10)
A partir de ces deux propriétés, Rockafellar a pu montrer que l’opérateur Pk0(z) = (1 + ck)Pk(z) est aussi pseudo-contractant et on aura donc k P (z) P (z0) k (1 + ck) 1 k z z0 k 8z; z0 (3.11)
Cas où le terme de pénalité est une divergence de Kullback-Leibler
En particulier, cela implique que Pk a un point fixe unique qui devra être le point unique z1 telle que 0 2 T (z1), cela se traduit par k zk+1 z1 k=k Pk(zk) Pk(z1) k (1 + ck) 1 k zk z1 k (3.12)
D’où, si ck c > 0, la séquence zk converge vers la solution z1 d’une manière linéaire avec un coefficient (1 + c) 1 < 1.
Algorithme classique de Blahut-Arimoto et ses interprétations géométriques
Algorithme classique de Blahut-Arimoto
Considérons un canal discret sans mémoire avec pour entrée X prenant ses va-leurs dans l’ensemble fx0; : : : ; xM g et en sortie Y prenant ses valeurs dans l’ensemble fy0; : : : ; yN g. Ce canal est défini par sa matrice de transition Q telle que [Q]ij = Qijj = P r(Y = yijX = xj). Les distributions des symboles d’entrée et de sortie sont caractérisées respectivement par les vecteurs p = [p0 pM ]T et q = [q0 qN ]T = Qp avec pj = Pr(X = xj) et qi = Pr(Y = yi) = PM Qijj pj.
Algorithme classique de Blahut-Arimoto et ses interprétations géométriques
L’information mutuelle H(Y ) H(Y jX) de X et Y est égale à [Gal68, CT91] : MN Xj X Qijj (4.1) I(Q; p) =pj Qij log: jqi =0 i=0
Avec Qj = [Q0jj : : : QNjj]T représente la jème colonne de Q. La capacité de canal est : C(Q) = max I(Q; p): (4.2)
En résolvant ce problème de maximisation et en prenant en compte la condition de normalisation, nous obtenons le processus itératif : PM j=0 pjk exp(Djk)pjk+1 = pjk exp(Djk) : (4.3)
où Djk , D(Qjkqk) avec qk = Qpk. C’est la Divergence de Kullback-Leibler entre la distribution courante de sortie qk et la jème colonne de Q.
Algorithme de gradient naturel
Dans cette section, nous proposons un nouvel algorithme pour le calcul de la capacité basé sur le gradient naturel [AD98]. Nous allons exploiter le fait que les vecteurs de probabilité d’entrée p constituent un ensemble de Riemann de dimension M avec comme métrique associée la matrice d’information de Fisher. L’avantage de l’approche gradient naturel réside dans le fait que la courbure de cet ensemble est bien prise en considération [AD98].
Cet algorithme de gradient naturel pour le calcul de la capacité pourra être représenté (voir annexe A), de la manière itérative suivante : k+1 k k k ) : pj= pj1 + k(DjI(4.16) avec Ik , I(pk) est l’estimée courante de la capacité. Notons que, comme dans le cas de BA, (4.16) correspond à une mise à jour multiplicative. Cependant, la complexité de calcul dans cet algorithme de gradient naturel a diminué par rapport au cas BA car il n’y a pas d’exponentielle dans l’équation itérative de mise à jour.
Ayant M M
j=0 pj Djk = Ik, (4.16) garantit que j=0 pjk+1 = 1. Cependant, il faut choisir kj0. Cette contrainte est en conflit avec un pasPP notre but d’accélérer la vitesse de la convergence de ce processus itératif (choisir un k+11 pas assez grand). En effet, la non négativité de pj est assurée pour k . minj Djk Ik
Des simulations numériques indiquent qu’un choix de k proche de 1 mène minj Djk Ik à un comportement instable dans les itérations de l’approche gradient naturel. Une convergence stable est cependant observée avec k = . Avec cette valeur Ikminj Djk Ik du pas, ainsi qu’avec des valeurs fixes de pas k = > 1, l’algorithme de gradient naturel converge plus vite que BA.
Algorithme de Blahut-Arimoto accéléré
Une comparaison numérique entre BA et NG montre que, pour des pas fixes k = , l’algorithme NG converge fois plus vite : les propriétés de convergence sont presque les même pour = 1.
Pour démontrer cela, nous divisons le numérateur et le dénominateur de (4.3) par exp(Ik) et utilisons ensuite le développement limité en série de Taylor de premier ordre des exponentielles : pjk+1 = pjk exp(Djk Ik) pjk 1 + (Djk Ik) : PMIk) j=0 pjk exp(Djk(4.17)
Le terme de droite n’est autre que l’équation de mise à jour de NG pour k = 1. Cette approximation en série de Taylor est valable pour Djk Ik 0. Cela est vérifiée au voisinage de la solution optimale. Nous pouvons ainsi conclure que BA et NG sont asymptotiquement équivalents pour k = 1. Cette relation entre ces deux algorithmes nous conduit à considérer un algorithme BA plus général : pjk+1 = pjk exp( kDjk) : Pj=0 pjk exp( kDjk)(4.18)
En se servant des même arguments, nous pouvons montrer que cet algorithme est asymp-totiquement équivalent à celui de gradient naturel. En effet, en utilisant le même pas k = , les deux algorithmes possèdent la même vitesse de convergence qui est fois plus rapide que celle de l’algorithme BA classique. Nous appelerons l’algorithme (4.18) algorithme de BA accéléré.
Décodage itératif des BICM : approche point proximal
Les modulations codées à Treillis (« Trellis Coded Modulations ») [Ung82][Ung87] ont été longtemps considérées comme étant le meilleur choix pour une bonne performance de transmission. En effet, la modulation et le codage sont considérés simultanément. Ce-pendant, les TCM souffrent de deux inconvénients majeurs empêchant leur utilisation dans les communications sans fil : i) les systèmes de base de ces modulations codées sont compatibles uniquement avec l’entrelacement symbole menant à une mauvaise per-formance dans le cas des canaux à Rayleigh par comparaison aux systèmes utilisant l’entrelacement bit ; ii) les TCMs sont conçues pour des codages à taux fixes mais peu flexibles.
Il en suit, dans la plupart des systèmes sans fil récents, que l’entrelacement bit est plus utilisé que l’entrelacement symbole. Par conséquent, le codage canal, l’entrelacement bit et le mapping bit-symbole sont séparément réalisés en suivant l’idée originalement introduite dans [VWZP89]. Cela est connu dans la littérature comme modulation codée à bits entrelacés (Bit-Interleaved Coded Modulation) [CGB98] où l’entrelacement est effectué avant la modulation bit-symboles complexes. La modulation codée à bits entrelacés est une approche pragmatique de la modu-lation codée. Elle a été tout d’abord proposée par Zehavi [Zeh92] pour améliorer les performances des modulations codées à Treillis dans le cas des canaux de Rayleigh à évanouissement. Une analyse des taux atteints et de la probabilité d’erreur est don-née par Caire [CGB98]. Les BICMs ont été récemment utilisées dans quelques standards comme DVB-S2, wireless LANs, DSL et WiMax grâce à leur flexibilité et leur simplicité. Les BICMs combinent les codes correcteurs d’erreur avec des schémas de modulation d’ordre élevé. Bien qu’elles aient étées à l’origine développées pour des canaux à éva-nouissement (SISO) [Zeh92][CGB98], les modulations codées à bits entrelacés ont été rapidement étendues pour les systèmes multi-Antennes (MIMO systems) [BBL00].
C’est maintenant un sérieux concurrent par rapport aux codes espace-temps (Space-time (ST) codes), qui exploitent la diversité spatiale dans les environnements MIMO contre des faibles taux de transmission. D’autre part, les BICM peuvent assurer des taux élevés de transmission tout en maintenant une grande diversité [FG98]. Dans les BICM, l’ordre de diversité est augmenté par l’utilisation d’entrelaceurs bits au lieu d’en-trelaceurs symboles. Cela est réalisé en dépit d’une réduction de la distance Euclidienne minimale menant à une dégradation de performance sur les canaux Gaussiens sans éva-nouissement [Zeh92]. Cela peut être résolu par l’usage d’un décodage itératif (BICM-ID) au niveau du récepteur qui consiste à échanger des informations extrinsèques entre le décodeur canal et le démodulateur selon un processus de type turbo jusqu’à arriver à la convergence [LCR02].
Les BICM-ID donnent d’excellentes performances pour les canaux Gaussiens et à évanouissement. Le schéma de décodage itératif utilisé dans les BICM-ID est très simi- laire aux turbo décodeurs série. Dans les BICM-ID, le décodeur interne est remplacé par un démodulateur qui nécessite moins de complexité que l’étape de décodage. C’est pour cela nous avons considéré dans cette thèse l’étude du décodage itératif des BICM.
Pour une constellation, un entrelaceur et un code correcteur d’erreur fixés, le mapping signal joue un rôle important dans la détermination de la performance d’erreur d’un système de BICM-ID. Bien que ce chapitre étudie le décodage itératif des BICM, les résultats peuvent être appliqués sur la large classe des décodeurs itératifs incluant les turbo décodeurs série ou parallèle ainsi que les décodeurs « Low-Density Parity-Check » (LDPC).
Aucun de ces décodeurs turbo n’a été à l’origine introduit comme solution d’un pro-blème d’optimisation ce qui rend leur structure précise adhoc (l’échange des informations extrinsèques entre les constituants d’un récepteur itératif à la place des probabilités a posteriori était initialement intuitif) et l’analyse de leur convergence et stabilité très difficile.
Parmi les différentes approches pour l’analyse du décodage itératif, les analyses par EXIT chart et évolution de densité ont permis de faire un progrès important [GH01][tB01] mais les résultats développés selon ces approches peuvent être appli-qués uniquement dans le cas de blocs de grande taille. Un autre outil d’analyse est la connexion du décodage itératif à la théorie des graphes [KFL01] et à la propagation des croyances (Belief propagation) [Pea88]. Des résultats de convergence pour la pro-pagation des croyances existent mais sont limités au cas où le graphe correspondant est un arbre ce qui exclue les turbo codes et les codes LDPC. Un lien entre le déco-dage itératif et les algorithmes classiques d’optimisation a été récemment établi dans [WRJ06] où le décodage turbo est interprété comme étant la solution d’un problème d’optimisation avec contraintes. Vu que l’ensemble des contraintes n’est pas fixe, les outils classiques ne sont pas efficaces pour analyser le comportement d’une procédure itérative à la convergence.
Une approche géométrique a été considérée dans [WJR05], elle fournit une interpré-tation intéressante en termes de projections. Le cas particulier des BICM-ID a été étudié dans [MDdC02] menant à une bonne caractérisation du démodulateur et de décodeur.
Dans ce chapitre, nous reformulons le décodage itératif des BICM comme étant une minimisation d’une distance de Kullback dans le but d’essayer de trouver une inter-prétation géométrique et une autre de type point proximal caractérisant le processus itératif en entier. Ces deux approches ont été introduites dans les chapitres précédents.
Il en suit, dans la plupart des systèmes sans fil récents, que l’entrelacement bit est plus utilisé que l’entrelacement symbole. Par conséquent, le codage canal, l’entrelacement bit et le mapping bit-symbole sont séparément réalisés en suivant l’idée originalement introduite dans [VWZP89]. Cela est connu dans la littérature comme modulation codée à bits entrelacés (Bit-Interleaved Coded Modulation) [CGB98] où l’entrelacement est effectué avant la modulation bit-symboles complexes. La modulation codée à bits entrelacés est une approche pragmatique de la modu-lation codée. Elle a été tout d’abord proposée par Zehavi [Zeh92] pour améliorer les performances des modulations codées à Treillis dans le cas des canaux de Rayleigh à évanouissement. Une analyse des taux atteints et de la probabilité d’erreur est don-née par Caire [CGB98]. Les BICMs ont été récemment utilisées dans quelques standards comme DVB-S2, wireless LANs, DSL et WiMax grâce à leur flexibilité et leur simplicité. Les BICMs combinent les codes correcteurs d’erreur avec des schémas de modulation d’ordre élevé. Bien qu’elles aient étées à l’origine développées pour des canaux à éva-nouissement (SISO) [Zeh92][CGB98], les modulations codées à bits entrelacés ont été rapidement étendues pour les systèmes multi-Antennes (MIMO systems) [BBL00].
C’est maintenant un sérieux concurrent par rapport aux codes espace-temps (Space-time (ST) codes), qui exploitent la diversité spatiale dans les environnements MIMO contre des faibles taux de transmission. D’autre part, les BICM peuvent assurer des taux élevés de transmission tout en maintenant une grande diversité [FG98]. Dans les BICM, l’ordre de diversité est augmenté par l’utilisation d’entrelaceurs bits au lieu d’en-trelaceurs symboles. Cela est réalisé en dépit d’une réduction de la distance Euclidienne minimale menant à une dégradation de performance sur les canaux Gaussiens sans éva-nouissement [Zeh92]. Cela peut être résolu par l’usage d’un décodage itératif (BICM-ID) au niveau du récepteur qui consiste à échanger des informations extrinsèques entre le décodeur canal et le démodulateur selon un processus de type turbo jusqu’à arriver à la convergence [LCR02].
Les BICM-ID donnent d’excellentes performances pour les canaux Gaussiens et à évanouissement. Le schéma de décodage itératif utilisé dans les BICM-ID est très simi- laire aux turbo décodeurs série. Dans les BICM-ID, le décodeur interne est remplacé par un démodulateur qui nécessite moins de complexité que l’étape de décodage. C’est pour cela nous avons considéré dans cette thèse l’étude du décodage itératif des BICM.
Pour une constellation, un entrelaceur et un code correcteur d’erreur fixés, le mapping signal joue un rôle important dans la détermination de la performance d’erreur d’un système de BICM-ID. Bien que ce chapitre étudie le décodage itératif des BICM, les résultats peuvent être appliqués sur la large classe des décodeurs itératifs incluant les turbo décodeurs série ou parallèle ainsi que les décodeurs « Low-Density Parity-Check » (LDPC).
Aucun de ces décodeurs turbo n’a été à l’origine introduit comme solution d’un pro-blème d’optimisation ce qui rend leur structure précise adhoc (l’échange des informations extrinsèques entre les constituants d’un récepteur itératif à la place des probabilités a posteriori était initialement intuitif) et l’analyse de leur convergence et stabilité très difficile.
Parmi les différentes approches pour l’analyse du décodage itératif, les analyses par EXIT chart et évolution de densité ont permis de faire un progrès important [GH01][tB01] mais les résultats développés selon ces approches peuvent être appli-qués uniquement dans le cas de blocs de grande taille. Un autre outil d’analyse est la connexion du décodage itératif à la théorie des graphes [KFL01] et à la propagation des croyances (Belief propagation) [Pea88]. Des résultats de convergence pour la pro-pagation des croyances existent mais sont limités au cas où le graphe correspondant est un arbre ce qui exclue les turbo codes et les codes LDPC. Un lien entre le déco-dage itératif et les algorithmes classiques d’optimisation a été récemment établi dans [WRJ06] où le décodage turbo est interprété comme étant la solution d’un problème d’optimisation avec contraintes. Vu que l’ensemble des contraintes n’est pas fixe, les outils classiques ne sont pas efficaces pour analyser le comportement d’une procédure itérative à la convergence.
Une approche géométrique a été considérée dans [WJR05], elle fournit une interpré-tation intéressante en termes de projections. Le cas particulier des BICM-ID a été étudié dans [MDdC02] menant à une bonne caractérisation du démodulateur et de décodeur.
Dans ce chapitre, nous reformulons le décodage itératif des BICM comme étant une minimisation d’une distance de Kullback dans le but d’essayer de trouver une inter-prétation géométrique et une autre de type point proximal caractérisant le processus itératif en entier. Ces deux approches ont été introduites dans les chapitres précédents.
Interprétation géométrique du bloc de décodeur
Nous avons déjà vu que l’APP d’un bit codé évaluée par le décodeur peut être obtenue par (5.6). D’une manière itérative, nous pourrons ainsi écrire : p(n) X Y (cl = b) = KcI (c) p(n)(cj; I) AP PclCj (5.9)
Soit qdem(n)(c) = Qj p(n)(cj; I), alors et en résolvant le problème de minimisation suivant : qdem(n)(c) = argminq2LC D(qjjqdem(n)(c)) (5.10) où LC est la famille des distributions compatibles avec le code, nous obtenons la solution suivante : qdem(n)(c) = KIC (c)qdem(n)(c) (5.11)
En se basant sur les définitions des projections rapportées dans le chapitre 2, nous pouvons conclure que qdem(c) est la I-projection de qdem(c) sur la famille LC .
Notons que le résultat du bloc de décodeur n’est autre que la marginalisation de qdem(c) qui pourra être interprétée comme la projection de qdem(c) sur la famille EF des densités séparables : pAP(n) P (cl = b) = argminq2EF D(qjjqdem(n)(c)) (5.12)
Nous pouvons ainsi conclure que l’APP d’un bit codé évaluée par le bloc de décodeur n’est autre que le résultat de deux blocs de projection, le premier étant la projection de l’extrinsèque fourni par le bloc de démodulateur sur la famille linéaire des distributions compatibles avec le code LC , et le deuxième étant la projection du résultat de la première projection sur la famille exponentielle des densités séparables EF (Voir chapitre 2 pour plus de détails).
|
Table des matières
1 Introduction générale
2 Géométrie de l’information
2.1 Définition et historique
2.1.1 Définition
2.1.2 Intérêts
2.2 Outils de base
2.2.1 Divergence de Kullback-Leibler
2.2.2 Familles de distribution de probabilité
3 Algorithme du point proximal
3.1 Algorithme du point proximal
3.1.1 Etude de convergence
3.1.2 Cas où le terme de pénalité est une divergence de Kullback-Leibler
4 Algorithme de Blahut-Arimoto : interprétations géométriques et analyse point proximale
4.1 Introduction
4.2 Algorithme classique de Blahut-Arimoto et ses interprétations géométriques
4.2.1 Algorithme classique de Blahut-Arimoto
4.2.2 Interprétations géométriques de l’algorithme de Blahut-Arimoto
4.3 Algorithme de gradient naturel
4.4 Algorithme de Blahut-Arimoto accéléré
4.5 Interprétations point proximal
4.6 Exemple numérique
4.7 Conclusions
5 Décodage itératif des BICM : approche point proximal
5.1 Introduction
5.2 BICM-ID
5.3 BICM et lien avec la géométrie de l’information
5.3.1 Interprétation géométrique du bloc de décodeur
5.3.2 Interprétation géométrique du bloc de démodulateur
5.4 Formulation du critère
5.4.1 Justification de la forme factorisée : la structure de décodeur
5.5 approche proximale : critère modifié
5.6 Approche point proximal : blocs traités séparément
5.7 conclusion
5.8 Annexe
5.8.1 Annexe 5.1 : Notation compacte pour l’algorithme de BCJR
5.8.2 Annexe 5.2 : Conditions de convergence du décodage itératif des BICM
5.8.3 Annexe 5.3 : Résolution du problème d’optimisation
6 Lien entre Maximum de Vraisemblance et décodage itératif
6.1 Introduction
6.2 Critère maximum de vraisemblance et critère approché
6.3 Maximisation du critère approché
6.3.1 Maximum global
6.3.2 Maximisation itérative
6.4 Simulation
6.5 conclusion
7 Conclusion générale et perspectives
Références
Télécharger le rapport complet
