Objectif

L'objectif de ce TP est d'aborder la transformée de Fourier discrète en gardant en tête le point de vue géométrique : une décomposition sur une base finie d'un espace vectoriel particulier.

Préambule

Pour effectuer les quelques exercices de ce TP, vous allez travailler dans l'environnement notebook d'IPython/Jupyter. Pour cela, créez un répertoire pour cette matière, déplacez-vous dans celui-ci et exécutez les commandes suivantes :

$> module load python/3.6.5
$> jupyter-notebook

Ceci va ouvrir votre navigateur sur un explorateur de fichier du répertoire dans lequel vous avez lancé la commande.

Si vous obtenez un message d'erreur comme quoi la commande module n'existe pas, exécutez la commande suivante :

$> source /usr/local/Modules/init/profile.sh

Créez un nouveau projet Python3, que vous nommerez tp2.

Au début, dans la première cellule, pour activer le remplissage de l'espace de nommage avec les modules Numpy et Matplotlib (et math), écrivez la commande suivante et exécutez la cellule avec la séquence de touche Ctrl-Enter ou Shift-Enter

%pylab inline

Les fonctions de base

Un signal discret à support fini (de taille fini) peut être vu comme un vecteur dans l'espace de dimension le nombre d'échantillons. Par exemple, un signal échantillonné et quantifié de telle sorte que nous ayons 64 points peut être vu comme un vecteur de \(\mathbb{C}^{64}\). Un second signal complètement différent qui aura 64 échantillons ne sera qu'un autre vecteur de cet espace. Il sera ainsi possible de définir et utiliser des notions de géométrie pour manipuler ces signaux (distance, égalité, orthogonalité).

1. Définissez la fonction w_k qui aux paramètres k et N retourne le k-ième vecteur \(w_k = [e^{2i\pi kn/N}]_{n\in[0,64[}\) de la base \(\mathbb{C}^N\). La valeur par défaut de N sera de 64.
2. Définissez la fonction affiche_w_k, qui pour un k donné affiche dans une sous-figure les parties réelles du vecteur \(w_k\) et dans une autre sous-figure les parties imaginaires du vecteur \(w_k\). Les signaux étant discrets, utilisez la fonction stem à la place de la fonction plot.
3. Afficher en utilisant la fonction précédente les vecteurs \(w_k\) et \(w_{N-k}\) sur la base \(\mathbb{C}^{64}\) pour les valeurs suivantes de \(k\) : 0, 1, 2, 3, 4, 16, 20, 30, 31 et 32. Utilisez la fonction map pour faire ces affichages d'un coup. (Remarque: map retour un générateur, il faut donc parcourir ce générateur. Pour cela, convertissez le simplement en liste : list(map(...))).
4. Que remarquez-vous ?

Manipulation et changement de base dans l'espace vectoriel

Sachant que la projection orthogonale du vecteur \(\mathbf{x}=x[n]\) sur le vecteur \(\mathbf{y}=y[n]\) dans cet espace vectoriel est défini par

1. Définissez la fonction scalaire(x, k) qui retourne pour un \(k\) fixé le produit scalaire entre un vecteur \(\mathbf{x}=x[n]\) et le vecteur \(w_k\). Le résultat attendu est un nombre, réel ou complexe, mais pas un vecteur.
2. Définissez la fonction decompose(x) qui retourne un vecteur formé des produits scalaires du signal \(\mathbf{x}=x[n]\) sur toute la base des \(w_k\). Le premier élément sera \(<\mathbf{x}|\mathbf{w_0}>\), le deuxième sera \(<\mathbf{x}|\mathbf{w_1}>\) etc.
3. Affichez dans quatre sous-figures le module, la phase, la partie réelle et la partie imaginaire du vecteur égale à la décomposition du vecteur \(\cos(\frac{2\pi}{4}n)\) sur cette base \(\mathbb{C}^{64}\).
4. Quels sont les indices pour lesquels les contributions en module sont non-nulles ? (donnez le code permettant de répondre à cette question).
5. Quelles sont les valeurs à ces indices ? (idem)
6. Que constatez-vous par rapport à la théorie ?
7. Corrigez votre code et ré-affichez la décomposition du vecteur précédent.
8. Faîtes la même chose pour le vecteur défini par \(cos(\frac{2\pi}{4}n + \pi/4)\).
9. Faîtes le même calcul cette fois pour le vecteur \(cos(\frac{2\pi}{15}n)\). Que constatez-vous ?

Cette décomposition n'est autre que la transformée de Fourier discrète (DFT) d'un signal de longueur 64.