16. LES TRANSFORMÉES DE E'~URIER
a - Le tri direct - Dans l’ordre séquentiel on considère la donnée d’indicc k, ccttc donnée sera
placée a l’indice j : nous allons donner la correspondance entre k et j CII faisant l’hypothèse que
le premier indice est zéro ct le dernier N ~ 1. Désignons par 4 l’exposant de deux qui permet
d’encadrer le nombre k dc tcllc sorte que :
alors nous obt,iendrons
la valeur de j au moyen de la rela.tion de récurrence suivante :
j = RN(k) = &(AI - 2(j) + &
et l’on prendra au dkpart : RN(O) = 0.
Ccttc méthode s’applique pour k = 0, 1,2; 3.. . , N ~ 1. La manière dc l’exploiter sur un
cnscrrlblc de huit donntes numérotées de un à huit est presentee dans le tableau 16.2.
Indices initiaux
0
1
2
3
4
5
6
7
Tableau 16.2.
-..
- ~
~~~
Indices finals
q = 0
I&(O) = 0
0
q=o
Rs(1) = R,(O) + 8/2
4
q=l
Rg(2) = I&(O) + 8/4
2
q=l
h(3) = Rs(1) + 8/4
6
q=2
h(4) = l&(O) + 8/8
1
q=2
h(5) = R*(l) + 8/8
5
q=2
&(6) = I&(2) + 8/8
3
q=2
Rx(7) = I&(3) + 8/8
7
b - Tri par inversion de bit - Pour des raisons de simplicitk, on considère encore que les
indices commencent a la valeur zero et se tJermincnt donc a la valeur N - 1. Il faut donc
rn = log, (N) bits p our exprimer tous les indices de la fonction échantillonnitc dans le système
binaire. Pour obtenir l’indice j, il suffit d’intervertir l’ordre des chiffres binaires representant le
nombre k avec m bits et l’on obtient ainsi la représentation binaire du nombre j.
9.5. Exemple
Nous avons huit données numérotées de zkro à sept et nous obt,enons UIE représentation binaire
sur trois bits. La façon d’opérer est schématisée sur lc tableau 16.3, page suivante.
9.6. Remarques générales
1. Certaines donnees conservent le même indice.
2. Il est simple de passer d’une numérotation à l’autre selon que la première dom& à la valeur
xero ou la valeur un, et il suffira de retrancher ou d’ajouter une unité pour exploiter à notre
convenance l’un des deux algorithmes que nous venons de présenter.
265
a - Le tri direct - Dans l’ordre séquentiel on considère la donnée d’indicc k, ccttc donnée sera
placée a l’indice j : nous allons donner la correspondance entre k et j CII faisant l’hypothèse que
le premier indice est zéro ct le dernier N ~ 1. Désignons par 4 l’exposant de deux qui permet
d’encadrer le nombre k dc tcllc sorte que :
alors nous obt,iendrons
la valeur de j au moyen de la rela.tion de récurrence suivante :
j = RN(k) = &(AI - 2(j) + &
et l’on prendra au dkpart : RN(O) = 0.
Ccttc méthode s’applique pour k = 0, 1,2; 3.. . , N ~ 1. La manière dc l’exploiter sur un
cnscrrlblc de huit donntes numérotées de un à huit est presentee dans le tableau 16.2.
Indices initiaux
0
1
2
3
4
5
6
7
Tableau 16.2.
-..
- ~
~~~
Indices finals
q = 0
I&(O) = 0
0
q=o
Rs(1) = R,(O) + 8/2
4
q=l
Rg(2) = I&(O) + 8/4
2
q=l
h(3) = Rs(1) + 8/4
6
q=2
h(4) = l&(O) + 8/8
1
q=2
h(5) = R*(l) + 8/8
5
q=2
&(6) = I&(2) + 8/8
3
q=2
Rx(7) = I&(3) + 8/8
7
b - Tri par inversion de bit - Pour des raisons de simplicitk, on considère encore que les
indices commencent a la valeur zero et se tJermincnt donc a la valeur N - 1. Il faut donc
rn = log, (N) bits p our exprimer tous les indices de la fonction échantillonnitc dans le système
binaire. Pour obtenir l’indice j, il suffit d’intervertir l’ordre des chiffres binaires representant le
nombre k avec m bits et l’on obtient ainsi la représentation binaire du nombre j.
9.5. Exemple
Nous avons huit données numérotées de zkro à sept et nous obt,enons UIE représentation binaire
sur trois bits. La façon d’opérer est schématisée sur lc tableau 16.3, page suivante.
9.6. Remarques générales
1. Certaines donnees conservent le même indice.
2. Il est simple de passer d’une numérotation à l’autre selon que la première dom& à la valeur
xero ou la valeur un, et il suffira de retrancher ou d’ajouter une unité pour exploiter à notre
convenance l’un des deux algorithmes que nous venons de présenter.
265