Project topics and materials
Get Complete Project Material File(s) Now! »
Méthode du maximum de vraisemblance
Pour l’estimation des paramètres inconnus , on emploie le principe du maximum de vraisemblance, c’est-à-dire on considère la valeur des paramètres qui maximise la fonction de vraisemblance des observations comme la meilleure description du modèle, étant donnée la séquence d’observations. L’estimateur du maximum de vraisemblance du paramètre est donc le maximum de la fonction ! l(Y ; ), où l(Y ; ) est la vraisemblance de la suite d’observations Y .
Puisque le maximum de vraisemblance ne peut pas être calculé de façon explicite dans ce modèle, on est obligé de mettre en oeuvre un algorithme itératif. L’algorithme EM est la méthode de référence pour calculer cet estimateur. Cet algorithme prend en paramètre une valeur initiale, qui est ensuite mise a jour de manière itérative jusqu’à la convergence. L’algorithme est globalement convergent, mais il ne converge pas nécessairement vers un maximum absolu de la fonction de vraisemblance (il peut converger dans certaines conditions vers un attracteur local). Pour éviter la convergence vers un maximum local, l’algorithme est initialisé plusieurs fois avec des valeurs différentes. Chaque itération de l’algorithme EM consiste en deux étapes : l’étape E(xpectation) et l’étape M(aximisation). La quantité centrale, qui est calculée au cours de l’étape E, est la probabilité de lissage pk(jY ; ) = P (sk = j Y ; ) de l’état sk, étant données les observations Y et la valeur courante des paramètres . Dans des modèles de dimension faible, elle peut être calculée de façon exacte en utilisant l’algorithme de Baum-Welch. Par contre, dans des modulations plus grandes (à partir de MAQ-16 ou MAQ-32), la complexité des calculs de cet algorithme devient rapidement trop grande. Suivant les résultats numériques des rapports précédents, on a décidé d’approcher les lois de lissage à l’aide d’un système de particules en interractions pour réduire la complexité de calcul. Par souci de concision, nous notons pk(sjy1:k; ) = P (sk = sjy1:k; ).
Simulations numériques
Nous considérons dans ces simulations les taux d’erreurs pour des données engendrées par le simulateur développé dans le cadre du projet. Les alphabets des modèles MAQ (MAQ-4, MAQ- 16, MAQ-32, MAQ-64, MAQ-128, MAQ-256) sont normalisés pour que la puissance moyenne des symboles soit égale à 1. Les canaux considéré sont RAx, TUx, BUx et HTx. Nous fixons le rapport signal sur bruit (RSB) de chaque constellation pour que le taux d’erreur théorique soit égal à 1e 3. L’excès de bande est fixé à = 0:5.
Nous commençons par présenter les résultats d’estimation des taux d’erreurs des symboles pour des canaux à temps fixe. Nous comparons nos algorithmes à l’algorithme CMA par blocs, qui est considéré comme l’état de l’art dans le contexte de la déconvolution autodidacte. Afin de pouvoir employer le CMA, il est nécessaire que le nombre d’états de la modulation soit connu. Par contre, l’ordre du canal n’a pas besoin d’être connu a priori et il est estimé parmi les ordres potentiels L = 3; 5; 8. Afin de réduire la complexité des simulations, nous réduisons la liste des ordres potentiels. Notons que l’algorithme CMA ajuste directement un filtre de déconvolution et ne procède donc pas à proprement parler à une estimation du canal.
Les résultats dépendent de façon très significative des choix de paramètres comme le nombre de particules, le nombre d’itérations et le nombre maximal d’itérations de l’algorithme EM approché. Les taux d’erreurs s’améliorent si on augmente le nombre de particules et le nombre d’itérations de l’algorithme EM. Mais l’augmentation de ces quantités augmente la complexité, de sorte que le choix des paramètres est un compromis entre le temps de calcul et la performance des méthodes d’estimation, mesurée au moyen du taux d’erreurs. Par exemple, il est préférable d’utiliser des ordres faibles du canal (par exemple L = 3), car l’estimation dans un tel modèle est plus simple et on peut donc diminuer à la fois le nombre de particules et le nombre d’itérations de l’algorithme EM. Les taux d’erreurs doivent donc être comparés en prenant en considération le choix correspondant des paramètres utilisés pour la simulation.
Estimation au sens du maximum de vraisemblance d’une modulation linéaire basée sur un modèle de proportion
Lehmann and Romano [2005] Nous nous sommes intéressés à la question de trouver un estimateur de l’ordre de la modulation ayant une distribution asymptotique plus explicite que la distribution de l’estimateur d’ordre que l’on avait décrit dans les rapports précédents. Nous avons aussi travailler sur les estimateurs de canaux non-stationnaires structurés, permettant de prendre en compte la présence de Doppler ou de résidu de porteuse. Nous sommes en train de finaliser cet aspect du travail et nous allons donc consacrer ce rapport au premier point, qui est aujourd’hui quasiment achevé [il reste à écrire précisément les résultats].
Si on restreint d’estimation de l’ordre du modèle (autrement dit la classification de modèle) à deux modèles potentiels, le problème peut être considéré comme un test d’hypothèses multiples avec des paramètres de nuisance (ici, la variance du bruit et les coefficients des canaux de propagation). L’approche naturelle pour résoudre ce type de problèmes est de mettre en oeuvre un test de rapport de vraisemblance généralisé (GLRT = ’generalized likelihood ratio test’). Nous allons présenter différents tests basés sur cette idée dont on peut (à l’exception du premier) déterminer la distribution asymptotique sous l’hypothèse nulle. L’intérêt de pouvoir calculer cette distribution est de calculer, au moins de façon théorique, une probabilité asymptotique de fausse alarme, et dans certains cas, de construire la courbe COR.
Nous considérons une méthode de maximum de vraisemblance pour la classification aveugle des modulations MAQ transmises sur un canal sélectif en fréquence et perturbées par du bruit additif Gaussien. Des tests de rapport de vraisemblance pour la classification aveugle ont déjà été considérés dans Panagiotou et al. [2000], Dobre and Hameed [2006], Hong and Ho [2000] et d’autres. Les test ont toujours été présenté en tant que problème d’estimation du nombre de paramètres d’un modèle: chaque alphabet de modulation potentiel est associé dans ce contexte à un modèle. En pratique, ces algorithmes reviennent à tester le nombre de composantes dans un modèle de mélanges Gaussiens. En général, les estimateurs de ce type ne sont pas consistants, parce que l’estimation de l’ordre d’un mélange est un problème singulier (les méthodes proposées ne sont d’ailleurs pas consistantes). Nous avons développé et mis en oeuvre une approche différente. Plutôt que de décrire chaque alphabet de modulation par un modèle spécifique, nous considérons ici un seul modèle statistique englobant, qui décrit l’ensemble des modulations. Par rapport aux modèles définis pour chaque modulation individuelle, ce modèle possède un paramètre auxiliaire qui permet de discriminer les différentes modulations. Il est défini de telle sorte que le test de rapport de vraisemblance généralisé testera plutôt les valeurs de paramètre (plutôt que d’évaluer la vraisemblance pour des modèles différents). De plus, nous allons utiliser la structure particulière du modèle afin d’établir l’identifiabilité de ce modèle et développer les propriétés asymptotiques des test proposés.
Pour simplifier la présentation, nous traitons ici le problème de discrimination entre deux modulations potentielles. Nous supposons que l’alphabet X0 de la modulation du modèle 1 est un sous-ensemble de l’alphabet de modulation X = X0 [ X1. Cette approche s’étend naturellement à des situations où le nombre de simulations à discriminer est plus important [en faisant des tests d’hypothèses multiples par paires: il faudra simplement faire attention à la façon de combiner les résultats de tests pour éviter les erreurs]. Dans notre méthode, nous considérons deux modulations MAQ correspondant à deux alphabets de modulation différents et nous introduisons comme paramètre permettant de discriminer les différentes modulations la proportion des symboles (éventuellement, comme nous le discutons dans la suite, il est possible de rajouter une information a priori sur la structure de ces proportions). Si le vrai modèle correspond à l’alphabet global X, les paramètres de tous les symboles sont égaux. Par contre, dans le cas contraire, une partie de ces probabilités doit être égale à 0. Basées sur ces proportions, nous discutons trois statistiques possibles de test.
La première statistique est seulement la reformulation du test que nous avions développé précédemment, mais en utilisant ce nouveau cadre statistique. Pour la deuxième statistiques, l’hypothèse nulle est que le vrai modèle corresponde à la MAQ d’alphabet X0 [ X1, ce qui implique notamment que toutes les proportions soient égale. L’hypothèse est testée contre l’hypothèse alternative que les proportions ne soient pas égales. Cette statistique a l’avantage que la distribution asymptotique sous l’hypothèse nulle est connue et est libre (une distribution chi-2 centrée dont la distribution ne dépend d’aucun paramètre). Au contraire du premier test, la fausse alarme de la deuxième statistique de test est donc facile à calibrer. La troisième statistique considère l’hypothèse nulle que le vrai modèle correspond à la MAQ d’alphabet X0, ce qui implique notamment qu’une partie des proportions est égale à 0. L’hypothèse alternative est donc que toutes les proportions sont différentes de 0. La distribution asymptotique sous l’hypothèse nulle n’est pas aussi facile à établir que dans les deux cas précédents, car les paramètres sous l’hypothèse nulle appartiennent à la frontière de l’espace de paramètres. Nous avons pu montrer qu’elle est une mélange de deux distribution chi-2 en utilisant les résultats de Andrews [2001] sur la distribution des tests de rapport de maximum de vraisemblance généralisés quand les paramètres appartiennent à la frontière de l’espace des paramètres.
Afin de simplifier les notations nous présentons les méthodes pour tester une modulation MAQ-4 contre une MAQ-16. Il est néanmoins facile de généraliser ces méthodes pour d’autres modèles MAQ. De plus, comme nous l’avons déjà mentionné précédemment, les méthodes que nous avons introduites peuvent aussi être généralisées pour le cas de plus que deux modèles potentiels. Nous avons pour l’instant établi les distributions de ces statistiques de tests pour un canal à évanouissement plat; il n’y a guère de doute que les mêmes distributions restent valables pour un canal sélectif en fréquences, mais la technique de preuve sera, dans ce cas, beaucoup plus complexe (et dépasse le cadre de ce projet).
Table of contents :
1 Résumé (en français)
1.1 Introduction
1.1.1 Algorithmes de lissage particulaire
1.1.2 Algorithmes de déconvolution autodidacte
1.1.3 Reconnaissance de modulation
1.1.4 Identification autodidacte sous contrainte de parcimonie
1.2 Classification et identification aveugle
1.2.1 Déscription du modèle
1.2.2 Estimation de l’ordre
1.2.3 Méthode du maximum de vraisemblance
1.2.4 Lissage à horizon fixe
1.2.5 Un nouvel algorithme de lissage de deux filtres
1.2.6 Simulations numériques
1.3 Estimation d’une modulation linéaire basée sur un modèle de proportion
1.3.1 Description de modèle
1.3.2 Tests de rapport de vraisemblance
1.3.3 Simulations numériques pour la performance de classification
1.4 Expectation Sparse Maximization Algorithm
1.4.1 Description du modèle
1.4.2 Estimation de maximum de vraisemblance (ML)
2 Introduction
2.1 An Overview of the ML Classification Concept
2.2 A Survey of the Main Contributions
2.3 A Survey of the Lack of Theoretical Results for Approximate ML Classification .
3 Model
3.1 The General Model
3.2 The Sparse General Model
3.3 Probability Distributions
3.4 The Standard Model: Frequency-Selective Multi-Path Channel
3.5 The Doubly-Selective Channel Model
3.6 The OFDM Transmission Model
3.7 Linear Modulation Schemes
3.8 Unknown Quantities for Each Level of the Blind Classification Problem
3.9 Comparison Criteria for the Monte-Carlo Experiments
4 Filtering and Smoothing
4.1 State of the Art
4.2 Exact Smoothing and Maximum A Posteriori Estimate
4.2.1 Baum-Welch Algorithm
4.2.2 Viterbi Algorithm
4.3 Particle Filtering
4.3.1 Marginal Filtering
4.3.2 Joint Filtering
4.3.3 Approximate Viterbi Algorithms
4.4 Particle Selection
4.4.1 Proof of Theorem
4.5 A General Framework for Approximate Viterbi Algorithms and Particle Filtering
4.6 Approximate Smoothing – Particle Smoothing
4.6.1 Fixed-Interval Smoothing
4.6.2 Fixed-Lag Smoothing
4.6.3 Two-Filter Smoothing
4.6.4 Joined Two-Filter Smoothing
4.7 Computational Results
4.7.1 Comparison of Smoothing Algorithms and Selection Schemes
4.7.2 General Framework and Improving the EMVA
5 Blind Identification
5.1 State of the Art
5.2 ML Estimation and the Expectation-Maximization Algorithm
5.2.1 Expectation-Maximization Viterbi Algorithm and Viterbi Decoding Techniques
5.3 The Expectation Sparse Maximization Algorithm
5.3.1 Discussion on the Sparse ML Estimation
5.3.2 Convergence Properties of the ESpaM Algorithm
5.3.3 Semiblind ESpaM algorithm
5.4 Simulations
5.4.1 Sparse Time-Invariant Multipath Channel
5.4.2 Doubly-Selective Multipath Channel
5.4.3 OFDM Transmission with Doubly-Selective Multipath Channel
6 Blind Classification
6.1 State of the Art
6.2 Standard Maximum Likelihood Estimator for Blind Classification in Frequency- Selective Channels
6.2.1 Model Description
6.2.2 Model Estimation
6.2.3 Approximate ML-Estimation of Unknown Parameters
6.2.4 Reversed HMM Model
6.2.5 Macro-States Model
6.2.6 Simulations Results
6.3 Generalized Likelihood Ratio Tests Based on Proportions Parameter
6.3.1 Model Description
6.3.2 Likelihood Ratio Tests
6.3.3 ML Estimation with the EM Algorithm
6.3.4 Computational Results on Classification Performances
6.3.5 Conclusion
7 Conclusion
7.1 Classification and Identification in Frequency-Selective Channels
7.2 Expectation Sparse Maximization Algorithm
A Simulations numériques
A.1 Taux d’erreurs pour le modèle MAQ-16
A.2 Taux d’erreurs pour le modèle MAQ-32
A.3 Taux d’erreurs pour le modèle MAQ-4
A.4 Taux d’erreurs pour le modèles MAQ-64 et MAQ-128
A.5 Influence d’erreur de l’estimation de la période symbole et de la fréquence de la porteuse
A.6 Choix de modèle
A.7 Canaux à temps variables
Bibliographie
