Examen de filtrage adaptatif

J.-F. BERCHER

  Sans documents,
sauf dictionnaires de langues.
Durée : une heure.

Les réponses aux questions seront concises, mais précises. Les justifications sont aussi importantes que le résultat brut. Le correcteur appréciera la clarté de la rédaction et de la présentation. L'exercice n'est pas un exercice à tiroirs insurmontable : les résultats utiles sont donnés dans le texte (montrez que...) ; en cas de difficulté sur une question, vous pouvez admettre le résultat, le signaler, et poursuivre.

Pensez à gérer votre temps. Le texte est long, mais il y a peu de questions, qui sont indiquées par un trait dans la marge. Il est conseillé de lire attentivement l'énoncé.

Questions de cours [4 questions au choix, 5 points]

  1. Que veut dire LMS ?
  2. Un algorithme récursif est il adaptatif ? Un algorithme adaptatif est il récursif ?
  3. Donnez les équations normales (ou de YULE-WALKER, ou de WIENER-HOPF) pour l'identification des coefficients d'un filtre à réponse impulsionnelle finie de longueur p (on ne vous demande pas nécessairement de les démontrer).
  4. Quelles sont les conditions de convergence du LMS ?
  5. Quel est le lien entre l'algorithme du gradient (déterministe) et le LMS ?
  6. Quel est l'intérêt de l'utilisation du lemme d'inversion matricielle dans la présentation de l'algorithme des moindres carrés récursifs ?

Exercice : Algorithmes de Bussbang

On considère le système suivant :

Des données x(n) (un message) sont appliquées à l'entrée d'un canal, de réponse impulsionnelle h(n), la sortie de ce canal est perturbée par un bruit blanc additif b(n), pour fournir une observation u(n). Le problème de l'égalisation autodidacte est alors de concevoir un égaliseur permettant de restaurer l'entrée x(n) alors que le canal h(n) est inconnu et l'entrée non observable. On désigne par w(n) la réponse impulsionnelle du << filtre inverse idéal >>. Pour simplifier, on supposera dans la suite que la sortie du canal est observée sans bruit, i.e. b(n) = 0. Enfin, on notera y(n) la sortie du filtre inverse.

La réponse impulsionnelle du canal n'est pas nécessairement finie, ni à phase minimale1. La réponse impulsionnelle du filtre inverse, w(n) n'est alors ni nécessairement causale, ni finie.

Montrez que le filtre inverse idéal doit vérifier

+¥
å
 i = -¥ 
 h(i)w(k-i) = d(k),
où d(k) est le symbole de Kronecker, d(k) = 1 si k = 0 et 0 sinon, en partant par exemple de la relation

+¥
å
 i = -¥ 
 w(i)u(n-i) = x(n).

En pratique, la relation précédente est inexploitable, et l'on doit concevoir une procédure itérative permettant d'approcher le filtre inverse idéal par un filtre de réponse impulsionnelle finie, [^(w)](n)(i), i Î [-L,L], où [^(w)](n)(i) désigne la ie composante de la réponse impulsionnelle estimée avec les données jusqu'à l'instant n.

En décomposant la réponse impulsionnelle [^(w)](n)(i) en

^
w
 
 (n)
 
 (i) = w(i) + æ
è 		^
w
 
 (n)
 
 (i) - w(i) ö
ø 		,
montrez que l'on peut écrire la sortie y(n) sous la forme

y(n) = x(n) + v(n),
où v(n) est un bruit dont on donnera l'expression.

La sortie du filtre inverse estimé, y(n), est maintenant appliquée en entrée d'un dispositif non linéaire, produisant une estimée [^(x)](n) des données d'entrée du canal x(n). Si g(·) est la fonction non linéaire utilisée, on a alors

^
x
 
 (n) = g( y(n) ).
On utilise l'erreur e(n) = [^(x)](n) - y(n) pour mettre à jour les coefficients du filtre w, en utilisant un algorithme adaptatif standard.


Picture Omitted

Picture Omitted
En utilisant le critère d'erreur quadratique,

J(n) = E ì
í
î 		| ^
x
 
 (n) - y(n)|2 ü
ý
þ 		,
donnez l'algorithme LMS correspondant. Vous pouvez bien-entendu utiliser une formulation vectorielle, mais dans ce cas, vous définirez les vecteurs que vous employez.

Notez que le critère J(n) est une fonction non convexe de w, à cause de la non linéarité g(·), et peut être une fonction multimodale. L'algorithme LMS pourra alors converger, - s'il converge, vers un minimum local. L'algorithme LMS converge en moyenne si


lim
n ® +¥ 
 E ì
í
î 		^
w
 
 (n+1)
 
 (i) - ^
w
 
 (n)
 
 (i) ü
ý
þ 		® 0.

Montrez que cette condition implique que

E{ u(n-i)y(n) } = E{ u(n-i)g(y(n)) },    i = -L..L.
En multipliant chacun des membres par [^(w)](n)(i-k) et en sommant sur i, et en supposant que L est assez grand pour ne pas avoir à se préoccuper de l'effet d'un changement de variable sur les bornes d'intégration, montrez que cette condition est équivalente à :

E{ y(n)y(n-k) } = E{ g(y(n))y(n-k) }.

Ceci signifie que l'autocorrélation de y est identique à l'intercorrélation entre y et g(y). Les processus qui vérifient cette relation, à un coefficient multiplicatif près, sont les processus de Bussbang (on peut toujours << normaliser >> la non linéarité pour ramener le coefficient multiplicatif à l'unité). Les processus de Bussbang, parmi lesquels les gaussiennes corrélées, et tous les processus à corrélation exponentiellement décroissante, permettent donc la convergence de l'algorithme. Reste cependant le problème de la convergence éventuelle vers un minimum local. Un théorème de Benveniste- Goursat- Ruget donne une condition de convergence vers le minimum global : si

alors l'algorithme converge.

Algorithme de Godard

Dans le cas des modulations M-PSK, on obtient après démodulation un signal complexe, u(n). Le canal introduit à la fois une interférence intersymboles et un déphasage. L'entrée du canal est également un signal complexe, mais dont le module est constant. L'algorithme de Godard réalisent l'égalisation en pénalisant les sorties de l'égaliseur qui ne sont pas de module constant. L'intérêt de ne travailler que sur le module est d'éviter d'avoir à effectuer une récupération de la phase de la porteuse. L'algorithme de Godard minimise une fonction non convexe de la forme

J(n) = E{ (|y(n)|p - Rp)2 },
où

Rp = E{ |x(n)|2p }
E{ |x(n)|p }
L'algorithme LMS complexe correspondant est2

w(n+1) = w(n) + mu(n) e*(n).

À partir du critère à minimiser, donnez l'expression de l'erreur, e(n), en fonction de y(n), p, et Rp. Donnez l'expression de la fonction non-linéaire g(·) correspondant au critère3.

En prenant p = 1, et en se souvenant que

Signe(y) = y
|y|
 = |y|
y
 ,
identifiez la fonction non linéaire g mise en jeu et donnez l'expression du critère correspondant4. L'algorithme associé est l'algorithme de Sato.

Pour p = 2, donnez l'expression du critère J(n), et la fonction g.

L'algorithme associé est connu sous le nom d'algorithme CMA, pour Constant Modulus Algorithm, et est largement utilisé en pratique, pour effectuer une égalisation autodidacte, c'est-à-dire sans séquence d'apprentissage, pour des signaux de type PSK. Notez qu'il faut tout de même disposer d'une estimation, ou d'un a priori sur la valeur de Rp.

Footnotes:

1 ce qui signifie que son inverse causal n'est pas stable.

2 w(n) est le vecteur constitué avec les échantillons de la réponse impulsionnelle conjuguée, u(n) est le vecteur de données, e(n) est l'erreur, m le pas d'adaptation.

3 il suffit d'écrire l'égalité entre le critère général Bussbang et le critère précédent. Ne cherchez pas plus loin

4 On ne vous demande évidement pas de calculer Rp, qui dépend de la densité de probabilité de l'entrée...

File translated from TEX by TTH, version 1.46.