République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
Université Frères Mentouri Constantine 1
Faculté des Sciences de la Technologie
Département d’Electronique
Exposé en TAS 2 :
L’ALGORITHME LMS
Présenté par:
- Bidi Moussa
- Berkane Mohamed
- Belloum Abd Al Hakim
- Bouaroudj ayhem
1. Introduction
Les techniques de filtre adaptatif ont de nombreuses applications dans le
domaine du traitement du signal telles que les systèmes d'antennes intelligentes,
le RADAR, le SONAR, etc. Si l'on considère l'une de ces applications et qu'on
l'examine, on constaterait que l'antenne émet un faisceau omni-directionnel dont
la puissance est rayonnée dans toutes les directions. Maintenant, tout utilisateur
situé dans une direction particulière par rapport à un point de référence sur
l'antenne reçoit ce rayonnement omni-directionnel et le reste de la puissance
rayonnée est gaspillé, comme dans les endroits A, B et C comme le montre la
figure 1. Afin d'économiser de l'énergie et de concentrer toute l'énergie dans une
direction particulière de sorte que seul l'utilisateur reçoive toute la puissance
indivise, et une puissance optimale, nous avons besoin d'une antenne qui
fournirait un motif d'interférence constructive à l'utilisateur et un motif
d'interférence destructive à l'interférant ou à tout autre utilisateur que l'utilisateur
désiré.
Figure 1 : Antenne rayonnant dans toutes les directions
Ainsi, pour obtenir ce faisceau particulier vers un utilisateur spécifique, nous
avons besoin d'un réseau d'antennes qui fournirait une interférence constructive
à l'utilisateur souhaité et une interférence destructive à l'interférant, de sorte que
toute la puissance soit concentrée vers l'utilisateur, comme le montre la figure 2.
Figure 2 : Faisceau principal dirigé vers l'utilisateur souhaité et nul vers les autres côtés
Cette interférence constructive et destructive dans les directions souhaitées peut
être réalisée en maintenant une combinaison adéquate des poids efficaces du
filtre aux signaux, différents retards temporels, retards de phase et distances
entre les différentes antennes dans le système de réseau d'antennes. Tout cela
étant fait, il reste encore un problème avec l'utilisateur qui n'est pas stationnaire
dans sa position et donc, la direction du faisceau devrait varier continuellement
de manière à ce que le motif d'interférence constructive et destructive constant
des signaux soit généré dans la direction de l'utilisateur. Les poids assignés dans
l'équation du filtre devraient également varier constamment en fonction du
mouvement de l'utilisateur. La position de l'utilisateur peut être déterminée avec
précision en utilisant des informations de ligne de vue directe de l'utilisateur en
tant que signal d'accusé de réception. Une solution pour effectuer une telle
opération est nécessaire et a été développée par le Dr Bernard Widrow de
l'Université Stanford, sous la forme d'un algorithme appelé algorithme du
moindre carré (LMS), qui est célèbre pour les antennes intelligentes.
2. Description de l’algorithme LMS
Cet algorithme LMS peut être décrit dans une procédure étape par étape comme
suit :
Tout d'abord, considérez la séquence aléatoire d'entrées x(n) qui sera donnée à
un filtre FIR dont la sortie est y(n). Supposons que d(n) soit le signal de
référence/cible et qu'il existe toujours une différence entre y(n) et d(n) qui est
considérée comme une erreur e(n). Ce signal d'erreur e(n) est donné à un filtre
adaptatif qui ajuste constamment les poids du filtre de manière à ce que la sortie
du filtre FIR produise des résultats proches de d(n) comme désiré.
Figure 3 : Filtre de Wiener
Définissez votre page au format A4, avec une largeur de 210 et une hauteur de
297, et des marges comme suit [3] :
La séquence d'entrée est x(n) :
xT(n) = [x(0) x(1) x(2) …….. x(N)]
La séquence de sortie est y(n) :
yT(n) = [y(0) y(1) y(2) ……. y(N)]
et
y(n) = w0x0+ w1x1+ w2x2 …. + wpxN = wTx(n)
La séquence cible est d(n) :
dT(n) = [d(0) d(1) d(2) ……...d(N)]
La séquence d'erreur est e(n) :
eT(n) = [e(0) e(1) e(2) ……….e(N)]
x(n),y(n),d(n),e(n) sont des processus aléatoires de moyenne nulle. Ici W0, W1,
W2,…., WN sont les poids/coefficients du filtre.
L'équation suivant le filtre ci-dessus est :
e(n) = d(n) - y(n)
Soit Rxx une matrice de corrélation où :
Rxx = E[x(n) xH(n)]
Rxx : Hermitienne
Choisissez k ≠ 0 :
Où kT = [k0 k1 k2 …. Kn]
Considérez :
kHRxxk = kHE[x(n) xH(n)]k = E[kHx(n). xH(n)k]
Ici kH est un vecteur ligne, x(n) est un vecteur colonne donc le produit d'un
vecteur ligne et d'un vecteur colonne est un scalaire. C'est-à-dire que kHx(n) et
xH(n)k sont des scalaires.
Considérons
E[e^2(n)], qui est l'erreur quadratique moyenne de la sortie.
\E[e^2(n)] = E[(d(n)w^Tx(n))(d(n) - w^Tx(n))^T]
= E[d^2(n)] - 2E[w^Tx(n)d(n)] + E[w^Tx(n)x^T(n)] E[e^2(n)]
= E[d^2(n)] - 2 w^Tp + w^TRw \] ----------- équation(1)
Ici E[d(n)] est un scalaire.
Comme la valeur d'erreur optimale pour un filtre doit être de 0.
La dérivation de l'équation 1 des deux côtés pour une valeur minimale
\[ \frac{d(E[e(n)])}{dw} = \frac{d(E[d(n)])}{dw} - \frac{d(w^Tp)}{dw} + 2\
frac{d(w^TRw)}{dw} \]
\[ 0 = 0 -2p + 2Rw \] (de l'équation (1))
\[ w = Rp \] où
\[ (w = w_{\text{optimum}}) \] ------- équation (2)
Ceci est l'équation de filtre du filtre de Wiener.
Pour obtenir une puissance d'erreur moyenne minimale, les poids du filtre
doivent satisfaire l'équation du filtre de Wiener.
L'équation de l'erreur quadratique moyenne est généralement une équation
quadratique dans ce cas, c'est-à-dire que le graphique serait sous forme
parabolique comme illustré dans la figure 4.
Figure 5 : Graphique de l'équation quadratique de l'erreur quadratique moyenne
Il n'est pas possible de faire converger les poids du filtre vers la valeur optimale
en temps réel, mais nous pouvons obtenir les poids du filtre proches de celle-ci
en utilisant une procédure de descente de gradient. Le filtre adaptatif utilise la
procédure de descente de gradient pour faire converger les poids du filtre vers
les valeurs optimales. Le système subit de nombreuses itérations pour minimiser
l'erreur.
La procédure de descente de gradient peut être décrite comme suit : Considérons
W(i) comme les poids du filtre FIR à la ième itération.
CAS 1: W(i) est à droite de W_optimum.
Figure 6 : Convergence de la valeur des poids du filtre vers la valeur optimale
Si la valeur de w(i) est à droite, elle doit être soustraite d'une valeur de telle sorte
que w(i+1) soit proche de W_optimum par rapport à w(i), et la valeur w(i+2)
doit être encore plus proche de W_optimum par rapport à w(i+1), et la procédure
se poursuit jusqu'à ce qu'elle converge vers W_optimum. Si la tangente passant
par le point sur la parabole a une pente étroite, une petite valeur doit être
sélectionnée soit pour ajouter soit pour soustraire, sinon des grandes valeurs
doivent être prises. Ainsi, la convergence aura lieu en moins d'itérations.
CAS 2 : W(i) est à gauche de W_optimum.
Si la valeur de w(i) est à gauche, elle doit être ajoutée d'une valeur telle que
w(i+1) soit proche de W_optimum par rapport à w(i), et la valeur w(i+2) doit
être encore plus proche de W_optimum par rapport à w(i+1), et la procédure se
poursuit jusqu'à ce qu'elle converge vers W_optimum. Si la tangente passant par
le point sur la parabole a une pente étroite, une petite valeur doit être
sélectionnée soit pour ajouter soit pour soustraire, sinon des grandes valeurs
doivent être prises. Ainsi, la convergence aura lieu en moins d'itérations.
La valeur qui doit être ajoutée ou soustraite peut être choisie par l'expression
suivante :
Considérez µ comme une constante
w(i+1) = w(i) _
w(i+1) = w(i) + µx(n)[d(n)__y(n)])
Voici l'équation pour déterminer la valeur qui doit être ajoutée ou soustraite lors
du processus itératif. Généralement, W(i) se rapproche de W_optimum à partir
de l'équation précédente 3. Mais en temps réel, l'équation 3 est une
approximation. En considérant l'équation 3 comme standard, la convergence
réelle aura lieu par l'expression suivante :
E(w(i)) W_optimum
Figure 8 : E(w(i)) convergeant vers W_optimum grâce au processus itératif
Cela s'appelle l'algorithme LMS. Pour satisfaire l'équation du filtre de Wiener,
les poids du filtre doivent être optimaux. Cela peut être réalisé en utilisant un
filtre adaptatif dans le système. Cette technique LMS est utilisée pour mettre en
œuvre le filtre adaptatif.
Le schéma bloc du système avec le filtre adaptatif ressemblera à ceci :
Figure 9 : Schéma bloc du système avec filtre adaptatif pilotant le système.
La technique LMS est la plus célèbre mise en œuvre pour le filtre adaptatif. La
technique RLS est également utilisée pour mettre en œuvre le filtre adaptatif, qui
présente certains avantages par rapport à la technique adaptative LMS mais
nécessite un matériel complexe en comparaison avec LMS. Ainsi, LMS est une
technique largement mise en œuvre.
3. Exemple appliqué en MATLAB
Script :
%--------------------------------------------------------------------------
% Company: ETMC Exponenta
% Engineer: Kiselnikov Andrei
%
% Revision 0.01 - File Created 21.11.2019
% This example provided strictly for educational purposes!
%
% Brief : LMS equalizer script
%--------------------------------------------------------------------------
clear all
close all
% Parameters --------------------------------------------------------------
%Number of bits
N = 128;
% The data sequence formation
data = round(rand(N,1));
% Raised cosine filter
roll_off_factor = 0.2;
span_in_symbols = 10;
symbols_per_step = 8;
% Equalizer length
eq_len = 21;
%Convergence multiplier
mu = 0.1;
%--------------------------------------------------------------------------
% Rcos fir design ---------------------------------------------------------
nyq_filter = [Link](...
'Shape', 'Normal', ...
'RolloffFactor', roll_off_factor, ...
'FilterSpanInSymbols', span_in_symbols, ...
'OutputSamplesPerSymbol', symbols_per_step);
%--------------------------------------------------------------------------
% Channel symbols design --------------------------------------------------
reference_signal = upfirdn(data, nyq_filter.[Link],
symbols_per_step);
%--------------------------------------------------------------------------
% Channel design ----------------------------------------------------------
channel_grp_delay = 10;
channel_coeffs = [-0.00448802244256685, ...
0.00645719073272638, ...
0.0194125083505277, ...
0.0337393246952826, ...
0.0486610611188258, ...
0.0633171304003086, ...
0.0768253273648968, ...
0.0883475673098707, ...
0.0971535155864083, ...
0.102676757570639, ...
0.104558743492511, ...
0.102676757570639, ...
0.0971535155864083, ...
0.0883475673098707, ...
0.0768253273648968, ...
0.0633171304003086, ...
0.0486610611188258, ...
0.0337393246952826, ...
0.0194125083505277, ...
0.00645719073272638, ...
-0.00448802244256685];
channel_output = filter (channel_coeffs,1,reference_signal);
channel_output = channel_output(channel_grp_delay+1:end);
%--------------------------------------------------------------------------
% LMS equalization performing ---------------------------------------------
%Adaptive filter coefficient initial array
w = zeros (eq_len,1);
%Error behavior
err = zeros (length(reference_signal)-2*eq_len-channel_grp_delay,1);
% Equalized output
equalized_output = zeros(length(reference_signal)-eq_len-
channel_grp_delay,1);
for i = eq_len : (length(reference_signal)- channel_output - eq_len)
u = channel_output(i:-1:i+1-eq_len);
equalized_output(i+1-eq_len)= w' * u;
err(i+1-eq_len) = reference_signal(i) - equalized_output(i+1-eq_len);
w = w + mu * u * err(i+1-eq_len);
end
%--------------------------------------------------------------------------
% Visualization -----------------------------------------------------------
% Channel impulse response vs Equalizer response
subplot (2,2,1);
plot(channel_coeffs, 'ko')
hold on
plot(w, 'r*')
legend('Channel response','Eqlizer response')
grid on
title("Estimated weights by "+N*symbols_per_step+"samples") ;
% Channel signal vs Equalized signal
subplot (2,2,2);
plot(channel_output(eq_len:end));
hold on
plot(equalized_output);
grid on
legend('Channel signal','Eqlized signal')
title("Channel signal vs Equalized signal");
%Error between channel signal and reference signal
subplot (2,2,3);
plot(movmean(abs(err),span_in_symbols));
grid on
title("Average error behavior");
%Error between channel signal and reference signal
subplot (2,2,4);
plot(movmean(abs(reference_signal(1:length(reference_signal)-
channel_grp_delay)-channel_output),span_in_symbols));
grid on
title("Average error on the Equalizer input");
%--------------------------------------------------------------------------