Transformée de Fourier Discrète - premiers pas¶
L'objectif est d'aborder la transformée de Fourier discrète par le point de vue géométrique: un changement de base dans l'espace vectoriel des données.
Un signal discret à support fini (de taille finie) peut être vue comme un vecteur dans l'espace de valeur de dimension le nombre d'échantillons. Par exemple, un signal échantilloné et quantifié de telle sorte que nous ayons 64 points peut être vue comme un vecteur de $C^{64}$. Un second signal complètement différent qui aura aussi 64 échantillons ne sera qu'un autre vecteur du même espace. Il sera ainsi possible de définir et utiliser des notions géométriques pour manipuler ces signaux (distance, égalité, orthogonalité).
Questions¶
Définir les vecteurs de la nouvelle base $w_k(n)=e^{2i \pi k n /N}$ sur $C^{64}$
%pylab inline
def w_k(k, n, N=64.0):
return exp(2j*pi*k*n/N)
Afficher les parties réelles et imaginaires des vecteurs $w_k(n)$ pour $n$ sur l'intervalle [0,63] (faire une fonction) pour les valeurs de k suivantes: 0, 1, 2, 3, 4, 16, 20, 30, 31, 32 et 64 moins ces valeurs en les groupant par 4 (partie réelle de $w_1$, partie imaginaire de $w_1$, partie réelle de $w_{63}$, partie imaginaire de $w_{63}$)
Que remarquez-vous ?
def affiche_w_k(k):
# fixe la taille de la figure englobante
figure(figsize=(12,12))
# définit une grille de sous figures de 2 lignes, 2 colones
# la prochaine sous-figure sera à l'emplacement 1 (1,1)
subplot(2, 2, 1)
stem(range(0,64), [w_k(k, n).real for n in range(0,64)])
ylim(-1.1, 1.1)
xlim(0, 63)
title('partie reelle de w_' + str(k))
# emplacement de la deuxième sous figure (ligne 1, colone 2)
subplot(2, 2, 2)
stem(range(0,64), [w_k(k, n).imag for n in range(0,64)])
ylim(-1.1, 1.1)
xlim(0, 63)
title('partie imaginaire de w_'+str(k))
# affichage pour 64-k
k = 64 - k
# emplacement de la deuxième sous figure (ligne 2, colone 1)
subplot(2, 2, 3)
stem(range(0,64), [w_k(k, n).real for n in range(0,64)])
ylim(-1.1, 1.1)
xlim(0, 63)
title('partie reelle de w_'+str(k))
# emplacement de la deuxième sous figure (ligne 2, colone 2)
subplot(2, 2, 4)
stem(range(0,64), [w_k(k, n).imag for n in range(0,64)])
ylim(-1.1, 1.1)
xlim(0, 63)
title('partie imaginaire de w_'+str(k))
[_ for _ in map(affiche_w_k, [0,1,2,3,4,16,20,30,31,32])]
# applique la fonction d'affichage avec les valeurs de parametre donnés dans la liste
Décomposer sur toute la base formée de ces vecteurs $w_k$ le vecteur associé à la fonction $cos(\frac{2\pi}{15}\times n)$ et afficher le module des éléments de ce vecteur. Rappel: projection orthogonale du vecteur x sur le vecteur y est donné par $ (x,y) = \sum_{n=0}^{N-1} \bar{x}[n]\times y[n]$ , $\bar{x}$ étant le conjugué complexe. Dans notre cas, il faut calculé $(w_k, x)$.
from cmath import phase
X = array([sum([cos(2*pi*n/15.0)*w_k(-k, n) for n in range(0,64)]) for k in range(0,64)])
figure(figsize=(12,12))
subplot(2,2,1)
stem(range(0,64), abs(X))
xlim(0,64)
title('module')
subplot(2,2,2)
stem(range(0,64), [phase(x) for x in X])
xlim(0,64)
title('phase')
subplot(2,2,3)
stem(range(0,64), X.real)
xlim(0,64)
title('partie reelle')
subplot(2,2,4)
stem(range(0,64), X.imag)
xlim(0,64)
title('partie imaginaire')
Faire la même chose pour la fonction $cos(\frac{2\pi}{4}\times n)$
X = array([sum([cos(2*pi*n/4.0)*w_k(-k, n) for n in range(0,64)]) for k in range(0,64)])
figure(figsize=(12,12))
subplot(2,2,1)
stem(range(0,64), abs(X))
xlim(0,64)
title('module')
subplot(2,2,2)
stem(range(0,64), [arctan2(x.imag, x.real) for x in X])
xlim(0,64)
title('phase')
subplot(2,2,3)
stem(range(0,64), X.real)
xlim(0,64)
title('partie reelle')
subplot(2,2,4)
stem(range(0,64), X.imag)
xlim(0,64)
ylim(-35,35)
title('partie imaginaire')
Qu'en concluez-vous ?
Quels sont les indices pour lesquels les contributions sont non nulles ?
nonzero(abs(array(X)) > 10**(-10))
Quelles sont les valeurs à ces indices ?
array(X)[list(nonzero(abs(array(X)) > 10**(-10))[0])]
Faire la même chose pour la fonction $cos(\frac{2\pi}{4}\times n + \pi/4)$
from cmath import phase
X = array([sum([cos(2*pi*n/4.0 + pi/4.0)*w_k(-k, n) for n in range(0,64)]) for k in range(0,64)])
figure(figsize=(12,12))
subplot(2,2,1)
stem(range(0,64), abs(X))
xlim(0,64)
title('module')
subplot(2,2,2)
stem(range(0,64), [phase(x) for x in X])
xlim(0,64)
title('phase')
subplot(2,2,3)
stem(range(0,64), X.real)
xlim(0,64)
ylim(-5,35)
title('partie reelle')
subplot(2,2,4)
stem(range(0,64), X.imag)
xlim(0,64)
title('partie imaginaire')
Résolution du problème de stabilité et approximation numérique: Pour le cas de $cos(2\pi/4\times n)$ la partie imaginaire n'est pas exactement nulle à cause des effets des calculs et approximations de la représentation numérique. La phase dépendant de cette valeur, nous obtenons des valeurs très différentes de la théorie. Afin de corriger cela, vous devez modifier les valeurs des parties réelles et imaginaires pour rectifier cette approximation. Nous allons considérer que les valeurs inférieures à $10^{-10}$ sont nulles. Redessiner les graphiques précédents après cette rectification.
X = array([sum([cos(2*pi*n/4.0)*w_k(-k, n) for n in range(0,64)]) for k in range(0,64)])
ReX = X.real
ImX = X.imag
# correction pour les approximations numériques
NewReX = [x if abs(x) > 10**(-10) else 0 for x in ReX]
NewImX = [x if abs(x) > 10**(-10) else 0 for x in ImX]
NewX = array([a+1j*b for (a,b) in zip(NewReX, NewImX)])
figure(figsize=(12,12))
subplot(2,2,1)
stem(range(0,64), abs(NewX))
xlim(0,64)
title('module')
subplot(2,2,2)
stem(range(0,64), [arctan2(NewImX[i], NewReX[i]) for i in range(0,64)])
xlim(0,64)
title('phase')
subplot(2,2,3)
stem(range(0,64), NewReX)
xlim(0,64)
title('partie reelle')
subplot(2,2,4)
stem(range(0,64), NewImX)
xlim(0,64)
ylim(-35,35)
title('partie imaginaire')
Faire la même chose pour la fonction $cos(\frac{2\pi}{4}\times n)$
X = array([sum([cos(2*pi*n/4.0 + pi/4.0)*w_k(-k, n) for n in range(0,64)]) for k in range(0,64)])
ReX = X.real
ImX = X.imag
# correction pour les approximations numériques
NewReX = [x if abs(x) > 10**(-10) else 0 for x in ReX]
NewImX = [x if abs(x) > 10**(-10) else 0 for x in ImX]
NewX = array([a+1j*b for (a,b) in zip(NewReX, NewImX)])
figure(figsize=(12,12))
subplot(2,2,1)
stem(range(0,64), abs(NewX))
xlim(0,64)
title('module')
subplot(2,2,2)
stem(range(0,64), [arctan2(NewImX[i], NewReX[i]) for i in range(0,64)])
xlim(0,64)
title('phase')
subplot(2,2,3)
stem(range(0,64), NewReX)
xlim(0,64)
title('partie reelle')
subplot(2,2,4)
stem(range(0,64), NewImX)
xlim(0,64)
ylim(-35,35)
title('partie imaginaire')
