Complexité de l’algorithme LMS

Modulation en bande de base

La modulation en bande de base permet d’améliorer l’efficacité spectrale du signal à transmettre. L’objectif est de regrouper plusieurs bits ensemble pour créer ce qu’on appelle un symbole. Dans la littérature, on distingue plusieurs techniques de modulation. Chaque méthode possède des avantages et des inconvénients. On choisit le type de modulation en fonction des besoins du lien de communication à implémenter. Parmi les critères de sélections, on note: le débit de transmission requis, le taux d’erreur binaire requis, la largeur de bande disponible.
Dans un contexte de radio configurable, la modulation M-QAM représente un choix efficace. Effectivement, en fonction de l’environnement de communication, on peut aisément configurer un niveau de constellation M simplement qu’en modifiant une table de référence qui peut être logée dans un bloc de mémoire vive. Ceci en conservant sensiblement la même architecture matérielle, (Joshi, R. B., 1992).

Translation en fréquence

Au transmetteur, la première étape de translation en bande passante se fait généralement entièrement numériquement. Les symboles I et Q sont multipliés par un oscillateur numérique générant deux signaux orthogonaux, sinus et cosinus, afin de conserver la distinction entre la partie  réelle et imaginaire du signal M-QAM. La somme est convertie en analogique à l’aide d’un convertisseur numérique à analogique puis est acheminée à travers toute la chaîne de translation RF, (Stremler, 1992). L’étape inverse est effectuée au récepteur. La démodulation est accomplie à l’étage IF et le traitement se fait généralement de manière numérique.

Complexité de l’algorithme LMS

On s’intéresse à l’algorithme LMS en raison de sa simplicité mais aussi à cause de sa faible complexité de calcul. Pour décrire la complexité de calcul d’un algorithme, on examine le nombre de multiplications réelles requises mais aussi d’autres facteurs tels que le nombre d’additions et l’espace mémoire.

Il existe une multitude de stratégies d’implémentations. Certaines implémentations sont optimisées pour la vitesse, d’autres pour l’espace matérielle en utilisant des techniques de réutilisations de ressources. Il y a aussi des réalisations qui combinent l’optimisation des deux derniers critères. Ainsi, il est difficile voire même impossible de comparer justement deux implémentations. Cependant, le nombre d’opérations requises pour accomplir l’adaptation LMS des coefficients est le même pour chaque égaliseur basé sur cet algorithme. De plus, dans toutes les réalisations matérielles, le nombre de multiplicateurs disponibles est un critère primordial. Ainsi, nous allons effectuer l’analyse de complexité de calcul des algorithmes à l’étude en énonçant seulement que le nombre de multiplications réelles requises par itérations.

Les algorithmes CMA et MMA

La plupart du temps, pour que l’algorithme LMS converge, on doit inclure une séquence connue dans le protocole de communication. Cette séquence d’entraînement s’accompagne de deux inconvénients notables. Dans un premier temps, l’ajout d’une séquence d’entraînement amoindrit l’efficacité spectrale du lien de communication. De plus, afin de retracer la séquence d’entraînement, on doit mettre en œuvre un circuit non trivial de recouvrement de la trame qui consiste essentiellement en une corrélation glissante semblable à ce qu’on fait avec le CDMA, (Proakis, 2001).

Pour éviter les embarras engendrés par l’ajout de la séquence d’entraînement, on a recourt à des algorithmes dits autodidactes. Ces types d’algorithmes sont basés sur des propriétés statistiques d’ordre supérieur dont sont agrémentées les constellations QAM et PSK. Dans ce travail, nous aborderons l’algorithme CMA (constant modulus algorithm) de (Godard, 1980) ainsi que le CMA modifié connue sous l’acronyme MMA (multilmodulus algorithm), (Yang, Werner & Dumont, 2002)

Effet de la longueur de l’égaliseur sur la convergence de l’EQM

Nous avons observé que la déconvolution (ou l’inversion) du canal résulte en une infinité de coefficients. Par le biais d’un exemple, on remarque que la puissance des résidus de la déconvolution diminue suivant N. Ainsi, à un certain seuil donné, il devient inutile d’augmenter la longueur N de l’égaliseur car la réduction de l’interférence entre symbole n’est plus perceptible. De ce fait, il est inutile de poser plus de 128 coefficients temporels pour le canal SUI-3 que nous avons présenté plus haut. Un égaliseur plus long ne réduirait pas l’EQM et serait plus susceptible à l’instabilité. En effet, n’oublions pas que la convergence d’un égaliseur linéaire dépend de la variation de la puissance des symboles reçus et de la longueur de l’égaliseur .

Nous avons aussi démontré que la longueur utile d’un égaliseur linéaire dépend des conditions de canal et également de la vitesse de transmission des symboles. Par l’équation 1.18 on remarque que la longueur relative des échos est linéairement dépendante du taux de symboles. Ainsi, si on quintuple le nombre de symboles transmis par secondes, il faudra aussi quintupler la longueur de l’égaliseur. Donc, pour un canal SUI-3 tel que présenté plus haut, il faudrait maintenant au moins 200 coefficients d’égaliseur pour couvrir tous les échos.  où l’on aperçoit que l’EQM est remarquablement réduite avec un égaliseur de 256 coefficients temporels.

Stratégie de quantification de l’égaliseur FBMMA3M

Les signaux circulant dans l’algorithme FBMMA3M sont de nature complexes, aléatoires et bipolaires. Pour cette raison, nous avons choisi une représentation en complément à deux avec point fixe pour les quantifier. La variation d’amplitude des signaux qui se propagent dans l’égaliseur dépend des distorsions engendrées par le canal de transmission. En effet, le niveau de bruit blanc ainsi que le taux de variation des coefficients du canal agissent directement sur le comportement de l’égaliseur. En conséquence, on ne peut pas déterminer la quantification exacte pour tous les contextes de communications.

Dans notre démarche, nous avons choisi de quantifier l’égaliseur de manière à ce qu’il puisse être utilisé dans un contexte de télécommunication avec un trajet en vue non directe tel que le modèle SUI. Le rapport signal sur bruit est limité à un environnement où l’on peut transmettre à un taux d’erreur de 10-4 .Ainsi, les essais en simulation tiennent compte des cas où le bruit est élevé par rapport au niveau de modulation.

Table des matières

INTRODUCTION
CHAPITRE 1 APERÇU D’UN SYSTÈME DE COMMUNICATION NUMÉRIQUE M-QAM
1.1 Introduction
1.2 Codage et décodage de canal
1.3 Modulation en bande de base
1.3.1 Modulation M-QAM
1.4 Mise en forme, interpolation et décimation
1.4.1 Filtre de mise en forme
1.5 Translation en fréquence
1.6 Canal de transmission
1.6.1 Bruit blanc gaussien additif
1.6.2 Propagation multi chemin
1.6.2.1 Effet Doppler
1.6.2.2 Étalement des délais
1.6.2.3 Sélectivité du canal
1.6.2.4 Atténuation et évanouissement du canal
1.6.3 Modèle SUI
1.7 Contrôleur automatique de gain numérique
1.8 Égalisation de canal
1.8.1 Topologies d’égaliseurs basés sur le critère EQMM
1.8.2 Égaliseur à échantillonnage fractionné
1.8.3 Égaliseur à longueur finie
1.9 Conclusion
CHAPITRE 2 ÉGALISATION ADAPTATIVE
2.1 Introduction
2.2 Filtre de Wiener
2.3 L’algorithme LMS
2.3.1 Convergence de l’algorithme LMS
2.3.2 Complexité de l’algorithme LMS
2.4 Les algorithmes CMA et MMA
2.4.1 Convergence des algorithmes CMA et MMA
2.4.2 Complexité de calcul des algorithmes CMA et MMA
2.5 L’algorithme BLMS
2.5.1 Convergence de l’algorithme BLMS
2.5.2 Complexité de calcul de l’algorithme BLMS
2.6 L’algorithme FBLMS
2.6.1 Convolution dans le domaine fréquentiel
2.6.1.1 Méthode overlap-save
2.6.2 Adaptation des coefficients FBLMS
2.6.3 Convergence de l’algorithme FBLMS
2.6.3.1 Convergence de l’algorithme FBLMS non contraint
2.6.4 Complexité de calcul de l’algorithme FBLMS
2.6.4.1 Complexité de calcul d’une FFT/IFFT
2.7 Complexité de l’algorithme FBLMS versus l’algorithme LMS en bloc
2.8 Conclusion
CHAPITRE 3 CONCEPTION ET SIMULATION EN VIRGULE FLOTTANTE D’UN ÉGALISEUR FRÉQUENTIEL
3.1 Introduction
3.2 Environnement de simulation
3.3 Conception de l’architecture en point flottant de l’égaliseur fréquentiel
3.3.1 Réduction de la complexité
3.3.1.1 Effet de la longueur de l’égaliseur sur la convergence de l’EQM
3.3.2 Égalisation fréquentielle autodidacte
3.3.2.1 L’algorithme FBMMA3M
3.3.3 Pas d’adaptation variable
3.4 Conclusion
CHAPITRE 4 QUANTIFICATION ET LATENCE DE L’ÉGALISEUR FBMMA3M
4.1 Introduction
4.2 Stratégie de quantification de l’égaliseur FBMMA3M
4.2.1 Quantification de l’erreur MMA
4.2.2 Quantification de l’erreur LMS
4.2.3 Quantification du seuil d pour la sélection MMA-LMS
4.2.4 Impact de la précision sur la convergence de l’EQM
4.3 Latence de l’algorithme FBMMA3M
4.3.1 Complexité de l’algorithme FBMMA3M sans latence
4.3.2 Effet de la latence sur l’égaliseur FBMMA3M
4.4 Conclusion
CHAPITRE 5 RÉALISATION DE L’ÉGALISEUR FBMMA3M
5.1 Introduction
5.2 Stratégie d’implémentation et de vérification
5.2.1 VHDL
5.2.2 Implémentation
5.2.3 Vérification pré synthèse
5.3 Description des modules implémentés
5.3.1 Module de chevauchement et sauvegarde
5.3.2 Choix du module de FFT
5.3.3 Modules r22pcx
5.3.3.1 Ordonnancement
5.3.3.2 Largeur des bus internes et mise à l’échelle
5.3.3.3 Latence
5.3.3.4 Initialisation du module r22pc
5.3.3.5 Complexité multiplicative du module r22pc
5.3.4 Module de temporisation des données
5.3.4.1 Synchronisation à l’initialisation
5.3.4.2 Configuration du module sfifo
5.3.5 Module de multiplication complexe
5.4 Module de sélection des données
5.4.1 Modules de gestion de l’erreur
5.4.1.1 Module de décision
5.4.1.2 Module de l’erreur MMA
5.4.1.3 Module de sélection de l’erreur (mux_mma_lms)
5.4.2 Module d’insertion de zéros
5.4.3 Module de contrainte du gradient
5.4.4 Module d’adaptation des coefficients
5.4.5 Module de temporisation des coefficients
5.5 Configuration et programmation de l’égaliseur FBMMA3M
5.5.1 Complexité de l’égaliseur
5.5.1.1 FPGA XCV2P40-7
5.5.1.2 Estimation théorique des ressources requises
5.5.1.3 Ressources requises après placement routage
5.6 Quelques résultats de performances de l’égaliseur FBMMA3M
5.7 Conclusion
CONCLUSION

Télécharger le rapport complet