Maîtrise d'informatique - Module 18 Traitement du signal - Travaux pratiques Séance 1 : 1. Introduction. 2. Programmation. 3. Tests de vérification.

1. Introduction : rappels de cours et structures de données.

Le but de ce premier TP de traitement du signal est de mettre en oeuvre la programmation, en langage C, de l'algorithme de la transformation de Fourier rapide unidimensionnelle (TFR ou FFT) présenté en cours. Les notations du cours sont brièvement rappelées ci-dessous, ainsi que les structures de données nécessaires à l'écriture de votre programme. Le paragraphe 2 décrit les principales fonctions du programme à réaliser. Le signal discret est composé de 8 valeurs réelles. Le spectre discret sera donc composé de 8 valeurs complexes. Il vous est conseillé de créer un sous-répertoire TS. La commande de compilation est la suivante :

> gcc -ansi -pedantic -Wall tfr.c -o tfr -lm

Les bibliothèques nécessaires à l'écriture de votre programme sont <math.h> et <stdio.h>. On définit les deux constantes N=8 et P=3 (N = 2^P). Les complexes utilisés seront tous représentés par des tableaux à deux dimensions. Le signal discret  (f_n)_[0,N-1], à valeurs réelles, est stocké dans un tableau de réels de nom signal_discret[N], initialisé aux valeurs :

Le spectre discret  (F_m)_[0,N-1], à valeurs complexes, est stocké dans un tableau de réels à deux dimensions, de nom spectre[N][2]. Les puissances successives W₈⁰, W₈¹, W₈² et W₈³ du facteur de rotation complexe :

sont stockées dans un tableau de réels à deux dimensions, de nom w[N/2][2].

2. Programmation.

2.1. Opérations sur les complexes.

Ecrire les fonctions permettant de réaliser les opérations suivantes sur des complexes :

• Addition de deux complexes :

void addi_comp(float res[2],float c1[2],float c2[2])

• Soustraction de deux complexes :

void sous_comp(float res[2],float c1[2],float c2[2])

• Multiplication de deux complexes :

void mult_comp(float res[2],float c1[2],float c2[2])

• Module d'un complexe :

float modu_comp(float c[2])

Pour calculer la racine carrée d'un réel, on utilisera la fonction sqrt qui retourne un réel.

2.2. Initialisation du tableau  w[N/2][2].

Ecrire la fonction permettant d'initialiser le tableau w[N/2][2] aux valeurs complexes des puissances successives de W₈ : 

void init_w(float w[N/2][2])

La valeur de    pourra être évaluée en définissant la constante symbolique PI égale à la valeur suivante :

#define PI 3.14159265358979323846

2.3. Initialisation du tableau  spectre[N][2].

Ecrire la fonction permettant de réaliser l'initialisation du tableau spectre[N][2] aux valeurs vues en cours :

void init_spectre(float signal_discret[N],float spectre[N][2])

Cette initialisation correspond à des affectations du type :

F_i  <-  (f_j , 0.)

La difficulté consiste à trouver les indices j correspondant aux indices i. Lorsque N = 8 (exemple traité en cours), on rappelle que ces correspondances peuvent être réalisées par la succession des trois étapes suivantes :

L'étape 1 est une conversion décimal-binaire sur P = 3 bits. L'étape 2 est une inversion des bits. L'étape 3 est une conversion binaire-décimal. Dans l'exemple précédent, la fonction init_spectre devra donc réaliser les 8 affectations suivantes :

Les opérations binaires utiles pour l'écriture de cette fonction sont :

• Le décalage à gauche de n bits (<<n).

• Le décalage à droite de n bits (>>n).

• Le ET logique (&).

• Le OU logique (|).

L'écriture de cette fonction peut présenter quelques difficultés. Si vous êtes bloqué, cliquez sur l'icône d'aide ci-dessous, et vous accéderez à l'algorithme détaillé :

2.4. Calcul de la TFR.

Ecrire la fonction réalisant le calcul "en place" de la TFR, à partir des valeurs retournées par la fonction d'initialisation écrite précédemment :

void tfr(float spectre[N][2],float w[N/2][2])

A chaque étage (si P = 3, il y a 3 étages, correspondant aux valeurs 0, 1 et 2 de la variable locale i), le calcul consiste en une phase d'additions/soustractions, suivie d'une phase de multiplications. Voici l'écriture de la deuxième phase, qui est assez difficile :

nombre_blocs=pow(2,P-i-2);
deca=pow(2,i+1);
for(j=1;j<=nombre_blocs;j++)
{

indice=(2*j-1)*deca;
for(k=0;k<N/2;k+=nombre_blocs)
{

mult_comp(spectre[indice],spectre[indice],w[k]);
indice++;

}

}

L'appel pow(2,P-i-2) retourne la valeur de 2 à la puissance (P-i-2). Il est demandé d'écrire la phase d'additions/soustractions. La principale difficulté consiste à déterminer, à chaque étage, les 4 couples d'indices. Il est conseillé d'introduire, en variable locale, un tableau de booléens, de nom non_apparie[N], initialisés à chaque étage à 1, qui permet de savoir si un des 8 indices a déjà été apparié ou non. Lorsqu'un indice ind1 non encore apparié a été détecté, il forme un couple avec l'indice ind2 tel que :

ind2=ind1+2ⁱ

2.5. Programme principal.

Ecrire le programme principal, qui permet d'afficher les valeurs du signal discret, de calculer sa TFR, puis d'afficher les modules des valeurs de son spectre discret.

3. Tests de vérification.

Avec les valeurs du signal discret données précédemment, vérifiez que vous trouvez bien les 8 valeurs suivantes pour le module du spectre discret :

En modifiant les valeurs des constantes par N=16 et P=4, et avec les valeurs suivantes du signal discret :

vérifiez également que vous trouvez les 16 valeurs suivantes pour le module du spectre discret :

Lorsque ces vérifications auront été faites avec succès, votre programme sera prêt pour la deuxième séance de travaux pratiques.