Traitement numérique du signal : Théorie et pratique 8e édition

~ =

t)

0; dans ce cas il suffit

1.8 ~chantillonnage de signaux

29

Sl l'on ajoute aux trois signaux sinusoldaux de 1a figure 1.8, Ie signal eontinu de v!i1eur 1 et Ie signal 'it 1a frequenee 112 d'amplitude 1 qui s'eeri! : cos (m). FechantlllQnnage de cette somrne donne des valeurs hulles sauf aux instants- multiple~de 8, ou 1a valeur 8 esl"btenue, conune 1e moalre 1a figure 1.9.a·. Le .spe~tre de eette somme est obtenu direetement en appliquant 1" relation : 1

11 est forme de raies d'amp1itude 1 aux frequenees multiples de 118 (fig. 1.9.b). Ou ce spectre a ete etudle au paragraphe 1.2, et l'on peut constater que 1a relation (1,27') se trouve verifiee. La possibilite d'engendrer une gamme de sighaux s-inuso'L'daux a partir dlun ensemblt; limite de nombres, stockes par exemple dans une me-moire, est utilisee dans les synthetiseurs de frequence numeriques. A

8

------------------------------

2

o

2

5

3

6

7

B

t

.1

:t-rr-r-T-T-T-T-] , o

1

1

8

bl FIG. 1.9.. a)

,o

.'••"•

tchantillonnage du signal s(t)

=

1 +2

f.

/1-=

h)

1

cos (27r

~~ t) + cos (m),

Spectre correspondani

•

],

•o o o

•

1,8.2 Signaux ah~atoires discrets

'
S

] Si 1e signal a1eatoire set) est eehantillonne avec 1a periode supposee Unitaire :; T = l,.il en resu1te un signal a1eatoire disc ret s(n.), qui a par definition I. meme 10i de probabilite de l'amplitude. Les resultats obtenus dans 1e cas. continu se transpo~

sent au cas discret, en particulier pour les signaux aleatoires stationnaires du

second ordre ergocliques [5].

1 • La nUmeration du signal. tchantiJlonnage et codage

30

Ainsi la fonctioJl d'auto-correlation du signai discret s (n ) est la suite r(n) telle que :

r(n) ~ E [sri ) .s(i - n)J

(1.58)

C'est un echantillonnage de la fonction d'auto-correlation r:u (~) du signal aleatoire continu definie par l'expression (1.34) . Sa transfortnee de Fourier donne la densite spectrale energetique if>,(t) du signal discret, qui est liee a la densite spectrale if>u(f) du signal continu par une relation analogue a (1.55), c'est-a-dire :

(1.59) Si la frequence d'6chantillonnage n'a pa~. une vale:l!lr suffisante, au::si Ie spectre

if>" U) s'etend sur un do maine non borne, il y arepliernent. L' hypothese d'ergodicite. pour Ie signal discret s (n) conduit a la relation: .

1

r(n ) ~ hm 2N N---t'D

:N

+

1

L i=- :N

(1.6Q)

sri) s(i- n).

Cette relation pertne.t.d'llppliquer la notion de ionction d'auto-correlation allX signaux deterministes. Ainsi, pour un signal periodique et de perfode. No, la fonction d1auto-correlation est la 'Suite .r (n) definie par: 1

No-1

r (n)~ -N

o

L

(1.61)

s(i)s (i-n)

i =O

C'est une suite periodique et de meme perioqe, E:remp.le .:

sen)

~ Asin (2" ~J

ren) ~

(i) N1o "hi .2... A2 sin 2" N 1=0 0

r(n) ~

A2cos (2" No71 ) ""2

(

sin 2"

i-n)

N' 0

On ,etrouve bien la puissance du sig)1al pour r (0) et la perioclicite No. Un signal aleatoire discret peut allssi eire defini en tant que tel. Par exemple si la suite r(n) s'annule pour n 0, Ie signal s (n) est un bruit blanc discret dont la

*

densite spectrale est constante sur l'intervalle de frequence [-

~, ~

1

Ce signal a

une realite physique, c'est une suite de variables aJeatoires non correlees; pour l'ob"tenir 11 suffit de faire appel a un algorithme qUi fournit des nombres statistique.ment independants. .

1.8 ~chantillonnage de signaux

31

1.8.3 Generation d'un bruit discret La generation de nombres aleatoires figure generalement au catalo.gue des fonc.tions des l.::a1cuJateurs scientifiques. 11 est ainsi possible en 10giciel de former une suite de nombres, utilisable comme signal de test en traitement nume-ri que. Au paragraphe 1.S.1 on a montre qu'il est particulierement simple de produire. nurnerlquement des signaux sinusoi'daux; de tels signaux peuvent aussi servif a sfmuler un bruit, par exemple par addition d~ un grand TIo rnbre de slnusoi'des de frequences differentes, d' amplitude constante et de phase aleatoire au pseudo-aleatorre. Ce.tte approche peut conduire a des realisatio~ particulierernent simples,. comme la m6'thode qui a eli; normalisee pour l'appareillage de mesure utilise dans les transmissions telephoniques numeTiques. Cette methode consiste a engendrer une sequence pseudo-aleatoire, qui est une suite periodique de 2N - 1 bits cornprenant a une unite pres autant de «Zeros» que de ~~ uns>? et qui simule line suite ale-atoire dans. laquelle les bits seraienl .i ndependants el auraien! la probabiJite 1/2 de valolr «zero» ou« un», ou pour centrer les variables, de valoir - 1/2 ou + 1/2. Sf une operation de filtrage, qui en fait consiste. en une sornmation ponderee, est effectuee sur une telle suite, les nornhres obtenus apres filtrage suivent une loi de probabilite qui s'approche de la loi nannale. Les sequences pseudo-alealoires sont eludiees dans la reference [6], elles sont facilernent obtenues a l'aide d' un registre a decal age. a N bits, c.onvenablernent bouch'. La figure 1.10 donne un exemple, utilise en appareillage de mesure, au N ~ 17. Le polyn6me generateur s'ecrit ,

g(x) ~ 1 +x' +X17

(1.62) pIx") 0,5

~---

I I

I

-----

04 ...-r-_

..

0,3

O.Z 0,1

-1

."•••• ],

•c

1

2

1 x

5 FiG. 1.10.

Generateur de sequence pseudo-aliatoire et loi de pro.babilite apresjiltrflge

o c

.~

§ "0

-a.

i •

o ©

la suite comprend 2N - 1 ~ 131071 bits, elle est periodique et de periode 1 T ~ (2'1 - 1). >, si "): ~ T designe la periode de l'horloge du circuit. Le spectre est JH

forme de raies distantes de

i·

Pour fH =.370 kHz, l'espacement entre deux rales

est de 2,8 Hz et l'on !rouve 36 raies dans 100 Hz.

1 • La numeration du signal. tchantillonnage et (adage

32

En 'operant sur cette suite un filtrage a bancle etroite ql,li ne conserve que la bande 450-550 Hz art obtient un ~ignal appro chant les caracteristiques gaussiennes, dont Ie facteur de crete est de 10,5 dB et qui constftue tin excellent signal de lesl

pour les equip,ernents de transmission nurnerique. Si Ie filtrage est fait numeriqtle-

ment la 'suite de nombres obtenue peut elte lltilisee pour tester les equipeinents de trait~ment

1.9

numerique.

L'OPERATION DE QUANTIFICATION

La quantification est l'appro'ximation d" chague valeur duosignal s/t) par un multiple entler d' une qllantite elementaire q, appelee echelon de quantification. Si q est. constant quelle que soit l'arnplitllde du signal, la quantification est dite uniforme. Cette operation revient a faire passer Ie signal dans un organe qui passede une caracteristique en marche dlescalier, co mme ]e montre ]a figure 1..11 pour q ~ 1, et fournit Ie signal sq (t) .

~

---'1

' I- ( , 1. -

~

sIt)

FIG. 1.11.

U operation de qZlantijication

La maniere dont Fapproximalion e-st faite d6finit Ie centTage de cette caracteristique. Par exemple la figure represente Ie cas, appele arrondi, ou toute

valeur du signal comp6se entre en -1/2)q et (n + 1/2)q est ~rrondie a nq. C'est l'approximation par defaut, qui est designee, quand elle porte .sur des. nombres, paT troncation et qui consiste a approcher par nq toute la valeur comprise entre nq et (n + l)q ; la caracteristiquese deplace ~lors de ql2 veLs·la c\roite sur l'axe de s.,a bsclsses.

1.9 L'operation de quantification

33

L'ef{et de cette approximation e$t de superposer au signal d'origine un signai d'erreur e(t) designe par di$toIsion de quantification ou plus communement par bruit de quantification; il vien!:

set)

~s.ct)

+ e(t)

(1.63)

Vne illustration est donnee par la figure 1.12 dans Ie cas de l'arrondi. Les amp litudes multiples impairs de q/2 sont appelees amplitudes de decision. L'amplitude du signal d'erreur est comprise entre - q/2 et q/2. Sa puissance mesure la degradation que subi! Ie signal. Quand les variations du signal sont grandes par rapport a l'echelon de quantification, c'est-a-dire que la quantification est faite avec suffisamment de finesse, Ie signa'! d!erreur est equivalent a'Un ensemble de signaux elementaires, constitues. chacun par un segment de droite (fig. 1.13). La puissance d'Un tel signal e lementaire dy duree 't s'ecrit : .

1["Z

B~ -

"t

1(q)2[" 'I

e'2(1) dl~ -

_:

"t"t

2

--'=

q2

t ? dt ~ -

12

(1.64 )

2

- - - - - - - - - - - - - - - - - ......="""'-

sltl .,(tl

."••••

- - - - - - - - --

FIG, 1.12.

Erreurde quantification

],

• (t)

•c

~

o c

•

2

'D-

S o

"0

~

~

• -g ~

,.

o

@

------

FIG. 1.13. Signal d'erreur etementaiIe

o

t

1 • La numeration du signal. tchantillonnag'e et cadage

34

2

La '{aleur ainsi oblenue, B ~ i2' est une eslimatiom de la puissaruoe du bruit de quantification suffisante dans la plupart des Gas reels. La distribution spectrale du signal d'erreuFest plus difficile a cemer. Le spectre du signal d'erreur e1ementaire de 1'a figure 1.13, E,(f), peut etre caleule a partir de celui de sa derivee. Ains! en utilisant les relations (1.22) puis (1.12), oh abtient : . .

1

E,(f) ~ j2rrf· q ·

[Sinrrf" (rrf~) ] - cos (rrf")

(1.65)

11 apparall que 1a plus gnmde partie de l'energie se trouve au voisinage de la 1 frequence Dans ces condilions la repartilion spectrale du signal d 'erreur depend

:r.

ci'une part de la pente dl1 signal elementaire, e'est-a-dire en fait de la distribution statistique de la derivee du signal .'(t), et d' autre part de la grandeur de l'echelon de quantification q par TappDTt au signaL La reference [7] donne Ie calcul de ce spectre pour un signal de bruit et fait 'appaYaltre un etalement en fonction de la frequence, quand Ie pas de quantification est suffisamment petit, sur un domaine qui couvre plusieurs centaines de fois la largeur de bande du signal. Si Ie signal it quantiner n'est pas un signal aleatoire, Ie spectre du signal d'erreur peut se concentter sur certaines frequences par exemple les harilloniques d'un signal sinusdidal. Dans la conversion d'un signal analogique SOllS forme numerique, la quantification jntervient conjointement avec l'echantillbnnag.e, ces deu.x operations etartt realisees successiverrient. Bien que l'echantillonnage soit en general fait en premier, il est equivalent de faire la quantification d1abord et l'echantillpnnage ensuite, a une frequence Ie habituellement un peu superieure au double de 1a largeur de bande du sjgnal. Dans ces conditions Ie signal d 1eTreur a sQuvenl un spectre qui s'etend biem au-dela de la frequence d'echantillonnage, et comme c1est en realite la somme du signal et du signal d'erreur qui est echantillonnee, Ie phenpmime de repliement du spectre intervient et 13 totalite de l'energie du signal d'erreur se relrouve dans la bande de frequences [- [,12. f,/2]. La plupart du temps les condltions' sont remplie& pour que la densite spectrale 6nergetique du brl1it de quantification soit constante et Fon refiendra Ie re-sultat suivant : Le bruit produit da:ns I'operation de quantification onifonne avec un echelon q~i s'exprime en general par B = q 2/U et presente one repartilion spectrale constante dans la ban de de frequ.ences [-/,12,/,12].

q a one puissance

n faut remarquer que .1a quantification des petits signaux, ceux dont I'amplitude est de I'ordre de grandeur de i'echelon q, depend beaucoup du centrage de 1\1 caracteristique. Par exemple avec. Ie centrage de la figure 1.11 un signal sinusoldal d'amplitude inferieure a '112 est totalement supprime. II est possible cependant de coder convenablement Ges petit& signaux en leur superposartt un signal auxiliaire de grande amplitude qui est elimine par la suite. Le cod age d'un signal introduit ainsi une limitation pour les faibles amplitudes mais il impose egalement une borne aux fortes amplitudes.

1.10 La dynamique de codage

35

1.10 LA DYNAMIQUE DE (ODAGE Le signal echantillonne et quantifie eN amplitude est fepre-senie par une suite de nombres presque toujours so us forme binaire. -8i chaque nombre compte N bits, Ie nombre maximum d' amplitudes quantifiees qu·it est possible de distinguer s' eliwe a 2N. Alars la gamme des amplitudes qu'i1 est possible de coder est soumise a une double limitation: veTS les faibles valeurs eile se trouve limit6e par I'echelon de quantificaHon q et vers les fottes valeurs par 2 N. q. Toute amplitude qui depasse celte valeur ne peut etre 'representee et it y a ecretage du ·signal. 11 s~en suit une ciegradatjon, par exemple par distorsion harmonique 8i Ie signal est sinusoi'dal . Si.la gammet des amplitudes a coder couvre Ie do maine [-Am' + AmJ , iI vient : Am~2Nq/2

(1.66)

et a'autre part, 'avec l'arrondi, Ie signal d~erreur e(t) est tel que:

On appelle puissance de crete d'un codeur la puissance du signal sinusoidal ayant I'amplitude maximale admissible sans ecretage, Am' Elle s:exprime par ~

p, ~~. [2N2·qr~22N- 3 .q2 La figure 1.14 represente ce signal avec Ie pas de quantification et les amplitudes de decision. z

- - - - - - - +Am

-r--------~------_+--O

.'•••"• ],

•c o c

•

___ _ Am

'1C

8o

'0

~

~

• 1i ~

8 "

FIG. 1.14.

Puissance. de crete 'du. .codeur

On definit la dynamique du cod age comme Ie rapport de cette puissance de crete a la puissance du bruit de quantification; c'est en fait Ie rapport signal a bruit

1 • La numeration du signal. tchantillonnage et codage

36

maximal pour un signal sinusoIdal avec codage unl£orme.• Cette dynamique s'exprime par la formule suivante ;,

ou plus commode-ment en decibeLs : (1.67) Cetle formule, d'une grande utilite pratique, relie Ie nombre de bits du codage

a la plage des amplitudes qui peuvent etre codees. Tn3s souvent cependant Ie signal a coder n'est pas un signal sinusoIdal. 11 est possible toutefo.is qe se ramener a ce cas si, pour Ie signal a coder, est d6finie une

puissance equivalente de crete, qui est alors prise comme puissance de crete du codeur. Le cas des signaux ah~atoires gaussiens, est particulierement important car ils repre~entent Gonvenablement beaucoup de signaux rencontres en pratique. II faut alors positionner cortectement Famplitude maximale du codeur par rapport a l' amplitude du signal, de [a,on ii ce que I. disforsion introduite par ecretage reste dans 'les limites imposees. En examinant Ie tableau donne en ann eKe 2, on peut remarquer que 1a probabilite pour que l'amplitude d'un signal de moyenne nulie et de puissance 0 2 de-passe 3,4 0 est inferieure a 10- 3 La fi~ur" 1.15 donne un exemple de codage avec 0 ~ q . II appaTal! que la prQbabilite d' ~cretage est inferieure a 5.10- 4 avec les vaieurs de parametres choisie.s.

x 4. ./.

3 0.004 2

o -1 -2 -3

-4 'F.!4, 1.,15,

Cbdage d'un signpl gaussien

1.11 Codage non linealre suivant une loi segmentee

37

Finalement, pour obtenir Ie rapport signal abruit maximai associe donne, il faut consiqerer Ie rapport signal a bruit ae crete ;

(SIB), ~

a un signal

A2 q2

12

= 3 , 2N

et soustraire Ie facteur de crete Fc' L'expression generale du -rapport ·s~gnal maximal pour un signal 'l.uelconque est done la suivante : (S/B)m~ ~ 6,02 N t 4,77 -F, dB

abruit

(1.670is)

Ce resultat est utilise hon seulenient dans la specification des codeurs de signaux analogiques mais aussi dans ie traitement numerique pour la determination des memoires de donnees et'le ca,drage des hombres. La dynamique de codage, pour un nombre de bits donne, peut etre considerablement augmentee si Ie codage est fait avec un echelon de quantification qui varie avec 1'amplitude du -signal; c'est Ie codage non linea,ire. De nombreuses 'lois de variation peuvent etre envisagees. Cependant il en est une qui est particulierement importante puisqu'elle a ete' normalisee P1IT l'Union Internationale des Telecommunications (UIT) pour Ie cod age de signaux telephonique dans les [eSeaUX de telecommunications, c'est 1a loi segmentee a13 segments [8].

1.11

(aDAGE NON LlNEAIRE SUIVANT UNE LOI SEGMENTEE

Dans l'operation de codage non lineaire suivant la Ipi segmentee a13 segments, les amplitudes positives et negatives coder sont divisees en 7 plages, chacune desqueUes est associe un echelon de quantific'ation dont 1a grandeur resuIte de la multiplication d'un echelon elementaire q par: une puissance de 2. Cette operation peut etre consideree comme resultant d 1un cod age lineaire precede d~une compression selon laquelle Ie signal x eSt transforme en signal y conformement aux relatipns suivantes :

a

a

, 1+ 1nAlxl y~slgne(x)" 1 +lnA

,o

"••

,

'.

Alxl

Y~Slgne(x), 1+1nA

],"

•5

pour

pour

-1 ,,;; Ixl ";; l A

(168)

O ~ lxl ~ ~ A

Le parametre A determine I'augmentation de la dynamique du eodeur; la valeur: retenue est A = 87,6. Finalement la caracteristique de compression suivant '1C 8 la loi A a 1~ segments est donnee par l(l.figure 1.16 et deerite camme suit: ~

o

"0

~

~

~

]. §

o

"

si

1

o~ Ixl - "' -64 ' 1

1

-64 "" Ix I'" 32 -

alors , y

~

16k

1 • La numeration du signal. tchantiJlonnage et codage

38

1 32

"'·Ix I '"

1 16

1 16

"'·Ix I '" 8"

)! ~ 4x

+ 1/4

1

1

8 '" Ix I '" 114 1

4 '" Ix I '" 1/2 1

2: '" Ix I '" 1 y

--- - ---- - ------ - - - -11 1 11

a

1 a1

100 ----1/2 01 1 010

-- - -1/' 001 000 1 64

o ~~~-4------~1~------------~.1~~. 111 1 • 32168 4" 2" FIG. 1.16. Caracteristique de compression a13 st gments

Celte caracteristique fait apparaitre 7 segments de droite dans Ie quadrant positif et dans Ie quadrant negatif ; les 2 segments qui entourent I'origin" etant colineaires, au totalla caracteristique compte bien 13 segments. La quantification des amplitudes y etant faile avec l'echelon q, celie .des amplitudes x voisines de Porigine est faite avec l~ echeion q/16, clest-a-dire que la dynamique du codeur se trouve augmentee de 24 dB. Les amplitudes voisines de l'unite sont mains bien quantifiees puisque l'echelon se trouve multiplie par 4. La

1.11 (adage nan linealre suivant une lai segmentee

39

puissance du bruit de quantification est fonction de I'amplitude du signal: pour chaq1)e valeur il faut c"lculer un ec'helon moyen faisant intervenir la statistique du signal. La figure 1.17 donne Ie rapport signal a bruit en fonction du niveau du signal apn3s codage, pour Ie cod age a8 bits lineai"re et non lineaire d 1un signal gaussien. Le niveau de reference pour Ie signal (0 dB) est la puissance de crete du codeur. On remarque Pextension de la dynamique due au codage non lineaire. Pour les amplitudes faibles Ia quantification correspond en fait 12 bits. En realite Ie signal code suivant la loi non lineaire peut 'etre obtenu a partir d~une quantification a 12- bits, suivie d'un tra"itement numerique qui est tres proche de la conversion d 1urr nombre entier en un no.mbre avirgule fiottante :

a

Par exemple au nombre a 12 bits : +00010110110 +100 0110 correspond Ie nombre a 8.bits : par application de la loi de compression.

~

(dB)

40

30

10 -80 FIG , 1.17.

-70 -60

- 50 -40 -30 -20 -1 0

o

5 l dB)

Co dage ii 8 bits iineaire et non lineajre d'un signal.gaussien

Les trois bits qui suivent Ie siBne donnent Ie code du segment, ou exposant; les quatre bits suivants indiquent la pDsition sur Ie segment, ou nlantisse. La dif."!:::i ference avec la conversion entier-virgule t10ttante apparait au voisinage de Porigme. , 1ii Ce traitement necessite pour sa mise en ceuvre"soit un reseau de portes c'est la • .31 realisation parallele, sDit un registre adecalage associe a un compteur a$ bits dan~ ~ la realisation serie. 'On peut egalement utiliser line memoire OU est stockee la table i de conversion. g Une autre 10i de c-odage non lineaire est egaiement utilis6e en telecommunica.~ tions, dite loi 11 a 15 segments. Elle correspond a la relation de compression s-ui§ vante:

" ~

I::

"0

~

~

•

~

-g.

.

In (1 + J.1lx I)

y ~ slgne(x) . In(l+J.1)

pour

- 1 '" x ,,; 1

§

o

"

La vaieur retenue pour Ie parametre de c9mpr~ssion e~t J.1 ~ 255.

(1.69)

1 • La numeration du signal. tchantiJlonnage et codage

40

1.12 OPTIMISATION DU (ODAGE En poursuivant dans la voie du perfectionnement du cod age, si la densite de pro-

babilite p (x) de l"amplitude du signal est connue, on peut determiuer la caracteristique de quantification qui, poUr un rrombre de bits N donne, m1nimise la pUlssance

de la distorsion totale. Dans I'operation de quantification, 1a plage des amplitudes du signal est divisee en M ~ 2'1 pi ages elementaires (x; -1' x;) avec -

M M '2 + 1 ,0; i ,0; '2' e.\ chaque plage

elementaire est representee par une valeur Yi' comme Ie montre la figure I.iS. L'optimisation 'consj;.;te a determiner l~ensemble des valeurs Xj et Yi qui minimi~e la puiss'a nce du signal d'en'eur E2 donnee par: M 2

L M i=-y+l

J"

(x - y;)2p (x) dx

-J Hl

y YMn~------------------~----~

- - - - - - - ---- -,------1

!,,

j

Y2

----r---i

y,W:

x

XM/2-' FIG. 1.18.

Caracteristique-de- quantification optimale

En prenont la derlvee par rapport aux variables x ; et y;, on montre que j;optimum 'est obtenu si 'les relations suivantes sont verifi6es : x; ~

r

Xi_l

1

2:

(Yi + y; + ,)

pour

(x- Yi)p(x)dx ~ O

-

M

2 +1 ~ i ~

pour -

M '2 +1

M -1

2

~'i,o;

M '2

(1.70)

1.12 Optimisation du codage

41

Ces relations permettent de determiner la caracteristique de quantification. Si p

(:x:) est \!ne fonction paire, On prend .1'0 ~ 0 et l'on procede par iterations en choiM

sissant a priori une valeur de h Si la relation (1.70) n 'est pas satisfaite pour 2 ' o n re prend les ealeuls pour une autre valeur de Y, et ainsi de suite [9]. Le table'au ~ .l donne la puissance du signal d1erreur E 2 obtenue avec un signa,l ga:ussien de puissance unite, pour qifferentes valeurs du nombre de bits N, d1une part avec Ie codage optimal t d'autre part avec un codage a e.-chelan constant pour Ie meilleur cadrage de la earacteristique de quantification [9]. Le tablea\! t 2., tire de la reference [10], donne, dans les memes conilitions, les valeurs correspond ant a un s-ignal 'a denslte d'e probabiHte exponentiel1e selan la relation (1.48). Tablequ. 1.1 . -

~ Codage optimal

CODAGE D'lJN SIGNAL GAUSSIEN uNITAlRE.

1

2

3

4

5

0,3634

0 ,1175

0,03454

0,0095

0,0025

0,3634

0,1188

0,03744

Q,01 15.4

0,00349

1

1,911

2,825

,,765

4,730

Codage

a echelon constant

Elltropie H

Tableau 1.2. -

.~

',"

CoDAGED'UN SIGNALLAPLAC.mNUNrrAllHi-

~

I

2

3

4

5

CodageDptimal

0,5

0;1765

0·,0548

0,0154

0,00414

0,5

0,1963

0,0717

0,0254

0,0087

~

o

.•• "••

Codage

aechelon constant

],

•

g

.~

8

ii

~

•

~.§

o

"

Lloptimisation du codage peut aussi e tre abo rdee sous Faspect du contenu informationnel en introduisant la fonction entropie H definie par [2, Tom" 3] :

H~-

L

p; 10g;2 (P;)

(1.71)

i

avec - M + 1 -'S: i ~ M et Oll p; designe la probabilite pour que l'amplitude du 2 2 signal se trouye dans la plage repre sentee par la valeun /,;.

1 • La nUmeration du signal. tchantillonnage et codage

42

Compte tenll de la relation :

Fentrapie est nulle lorsque l'amplitude du signal se concentre sur une seule pI age et elle est maximale lorsque cette amplitude est rep artie uniformement _i d'ans cecas elle prend la valeur Hm~ egale au nombre de bits N dll cadage : Hm~ ~

log 2.(M) ~ N

(1:72)

au log 2 (M) represente Ie logarithme en bas.e2, au binal, du nombre M. En fait I'entrapie mesure I'ecart d'une distribution de pwbabilite avec la distribution uniforme. La caracteristique de- quantification qui maximise Fentrop1e est donc' celle qui

conduit a des plages elementaires correspondant a une distribution de probabilite uniforme. La derhiere ligne du tableau 1.1 montre que pour un signal gaussien, Ie codage qui minimise 1a puissance du signal cl'erreuT conduit a des valeurs de Pentropie proohes Q.u maximum N .

1.1;3

QUANTITE O'INFORMATION ET CAPACITE O'UN CANAL

Les resultats obtenus sur l'echantillonnage et la quantification peuvent etre utili-

allinverse, pour evaluer 1a quantite d'informatioTI portee par uTI-signal ou pour determiner 1a capacite d~un canal dB transmissiop. Un canal reel de largeur de bande 1m peut trans pOTter 21m 6dhantillons ind€pendants par sec.a nde, ca mme Ie montre la figure 1.3, en rempla,ant ,; paT 21m' Quant i\ la quantite d'infmmation par echantillon, elle depend des puissances respectives du signal utile et du bruit, et de lellrs distributions d'~mplitude. U n cas particulier important est celui du canal gaussien [11 J. Soit a transmettre un ensemble de M symboles de N bits chacul.l dans un canal ses,

en presence d~un bruit blanc gaussien de puissance db = B . Dans un hyperespace a M dimensions 1 les M symboles occupent Ie volume. d' une hypersphere V M' defini par

(173) En supposant une repartition uniforn'le des symboles dans l'hypersphere de rayon R ~ Ie signal correspondant a pour energie:

1J~r 2 rM- 1 dr J

E,~V M

0

i :d

...

f

M-I

1(8;)d8;~R2MM:

+

2

(1.74)

1.13 Quantite d;information et capacite d'un canal

43

La quantite d'information transmise eSt de MN bits. A chaque ensemble de bits possible, on peut associer dans I'hypersphere 'un volume· V, egal il :

V I (R) M

V,~ 2MN ~ M F(S) 2N

(1.75)

M

A. chl,ique ensemble de bits est associe un bruit aM composantes dont fenergie s'ecrit : Eb ~ Mal. Quand M tend veTS l'infihi, Ie point representatif du bruit dans I'hypersphere 'se rapproche .d'une sphere de rayon b et centree sur Ie point representatif de l'ensemble des bits. En effet, pour M variables aleatoires gaussiennes,

\!Ma

b (n), la variable r ~ et sa variance pour volu)lle :

~

-

M

L

n~l

.

b 2 (n) a pour moment d'ordre 1 : m, ~

mi tend veTS zero quand M

tend veTS

a~infinJ.

1M2

ab \j ~-­ M+I

Cette sphere a

(1.76) Pour que 1a transmission se fasse sans, erreur, il faut que cette sphere so it ineluse dans Ie volume V, attribue a chaque ensemble de bits, c'est-a-dire :

\,/Mab <

R 2N

(1:75)

Or, qunndM tend vers I'infini, d'apr"s la relation (1.74), R~ represente I'cenef" gie de I'ensemble du signal, de puissance S et du bruit, soit

R2 ~ M(S + a;;)

(1.76)

La condition de transmision sans errel,lr s'ecrit alors

.2

2N

Star < --2ab

(1.77)

d'ou :

12 (. aS)

N <. -log 2 1 + 2

(1.78)

b

."•••• ],

•c

Si Ie canal est reel et a une laTgeur de bande W et s'i1. est sans distorsion, les symboles peuvent iHre emis a la cadence 2W et la capacite asymptongue du canal s'ecrit, en bits par seoonde:

o c

• '''-

(1.79)

8o

"0

~

~

• -g ~

,.

o

@

I1 (aut bien noter gu'une telle capacite suppose : -'"'- un canal sans distorsion, - un bruit blanc. gaussien, - un retard a1a transmission infilli.

1 • La numeration du signal. tchantillonnag'e et (adage

44

En pratique, l'egalisation des canaux et 1e codage correcteur d'erreurs permettent de-se rapprooher de c~tte limite avec un retard de transmission fini.

1.1 4

LES REPRE SENTATIONS BI NA IRES

II existe diverses [a,ons d'etablir la correspondance entre l'ensemble des amplitudes quantifiees et 1.'ensemble des nOlllores "binaires qui doivent les repre-senter. Les signaux it cOQer ayant des amplitudes en general positives et negatives, les representations pre-fe-rees sont celles qUi cohser'Vent l'information de signe. Les plus courantes pour les codages a echelon constant sont les suivantes : - signe et valeur absolue - hina.ire de-centre - complement a i - complement a 2. Les definitions et particularites de ces. representations 5.0nt donnees dans la rMerence [12], Ie. tableau 1.3 les definit pour 3 bits. Les representations en signe et valeur absolue et en binaire ciecent:re !?cmt les plus commodes pour la conversion Analogique/Numeriql.le ; les deux 3utres sont surtout utilisees dans les circuits de calcul nume-rique; elles spnt presentees en detail par la suite. Comme indique au paragraphe 1.11, qui (leorit une representation particuliere importante du domaine des telecommunications, Ie. codage non lineaire perinet d'augmenter considerablem~nt 1a clynamique. Les machines de traiternent, et en particulier celles qui s.ont )1sage gen.eral, ut,illsent s.ouyent ,Jes. repr~s.'mtations dites a virgule ftottante au chaque nombre corhporte trois parties: Ie bit de signe, b;l.lTIantisse et rexposant. La mantisse repre~ente une partie fractionnaire et l'exposant la puissance d'un nombre de base; par exemple, en base 10 : + 0,719 X 10 5

a

Tableau 1.3. -

REPREsENTATIONS BJNAIRES POUR CQDAGE LINEA-mE.

Nombre

Signe et valeur 'a bsolue

Binaire decentre

Complement ill

Complement il2

+3

0'11

111

all

+1

OiO

1io

oto

+1 +0'

101 100

-1

0'01 000 1 00 lC11 110

- 3'

11 1

001 000 111 11D 1 0.1 10.0

all 010 001 000

-0 -1

-

all 0'1 0 001 (0 a 0)

-

111 110 101 (100)

Annexe 1

45

L'extension de la dynamique provient de I'effet multiplicatif introcluit par I'exposant. Ainsi en base 2, pour un Iiombre a 6 bits d'exposant et 16 bits de mantisse, la dynamique correspond a 2 64 x 2 '6 ~ 2"" = 10 24 , soit 24 chiffres decimaux. Un graIn supplementaire est obtenu en prenant une base -qui est elle' meme une puissance de de~, comme 8 au 16, Gorrespondant au~ numerations octale au hexadec.imale respectivement. La presentation a virgule fiottante ent;ra'ine cepenclant une complication des operations arithmetiques et des circuits, Les nombres issus du codage se presentent, swvant la technique utilise-e, soit S!Jus forme parallele, c'est-a-dire que les N bits sont disponibles sur N point:>; de connexion en meme temps, soit sous. forme. serie, c'est-a-dire que les. N bits apparaissent successivement sur Ie me-me point de connexion, le signe d'·"abord et ensuite les bits de poids decroissants. La reference C13] decrit les principales techniques de. conversion AnalogiquelN umeriql)e.

ANNEXE 1 : La fonction I (x) . ( n\ sm "20)

Suite des valeurs : I (n)

~

n

pOUT 0 '" n '" 159 avec n ~ k + 20 N .

" 20 k 0 1

.:ijj ~

,o

." "••

],

•o o

c

•

lo

"0

~

~

• 1i ~

"

o

@

N~1

N~2,

N~3

N~4

N= ~

1'1 ~ 6

0 - 0,04742 - 0,08942 - 0,12566 - 0,15591 - 0,18006 - 0,19809 - 0,21009 -0,21624 - 0,21682

0 0,02429 0,04684 0,06721 0,08504 0,10004 0,11196 0,12069 0,12614 0,12832 0,12732 0,12329 0,11643 0,10702 0,09538 0,08185 0,06682 0,05071 0,03392 0,01688

0 -0,01633 -0,03173 -0,04588 -0,05847 -0,06926 - 0,07804 -0,08466 -0,08904 -0,09113 - 0,09095' -0,08856 -0,08409 -0,07770 - 0,06960 -0,06002 -0,04924 -0,03753 -0,02522 -0,01261

0 0,01229 0,02399 0,03482 0,04455 0,05296 0,05989 0,06520 0,06880 0,07065 0,07074 0,06910 0,06581 0,06099

0 - 0,00986 -0,01929 - 0,02806 - 0,03598 -0,04287 - 0,04850 -0,05301 - 0,05606 - 0,05769 - 0,05787 - 0,05965 - 0,05406 -0,05020 - 0,04518 - 0,03914 -0,03298 - 0,02470 - 0,01667 -0,00837

0 0,00823

N~O

1 0,99589 Z 0,98363 3 0,96340 4 0,93549 5 0,90032 6 0,85839 7 0,81033 8 0,75683 9 0,69865 10 0,63662 11 0,57162 12 0,50455 13 0,43633 14 0;36788 15 0,30011 16 0,23387 17 0,17001 18 0,10929 19 0,05242

-0,21241 -

0,20283 0,18921 0,17189 0,15148 0,12862 0,10394 0,07811 0,05177 0,02554

0,0547~

0,04739 0,03898 0,02980 0,02007 0,01006

O,OHi13 0,02350 0,03018 0,03601 0,04088 0,04466

0,04730 0,04874 0,04897 0,04800 0,04587 0,04265 0,03844 0,03335 0,02751 0,02110 0,01426 0,00716

N~'7

0 -0,00706 -0,01385 - 0,02021 - 0,02599 -0,03105 - 0,03528 - 0,03859 -0,04091 -0,04220 - 0,04244 -0,04164 -0,03983 - 0,037.07 - 0,03344 - 0,02904 -0,02399 - 0,01841 - 0,01245 -0,00626

46

1 • La numeration du signal. .tchantillonnage et codage

ANNEXE

i : La 1

~l

/(x) ~-e

v'2rr

x 0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1i 8 2 2,2 2,4 2,6 2,8 3 3,2 3,4 3,6 3 ,8 4 4,2 4,4

4,6

loi Normale. Reduite

-

7:

10' .f(x) 39894 39104 36827

33322 28969 24197 19419 14973 11 092 7895 5399 3547 2239 1358 792 443 238 123 61

29 13 5,9 2,5

1

P '=

v'2rr r-:'.' 2

~ e'

lOOP 100 95 90 85 80 75 70 65 (i)()

55 50 45 40 35 3.0 25 20 15 10 5 1

0,1 0,01 0,001 0,0001 0,00001

2

2

dx

3 4

1

~ v'2rr

L

Xl

e --,; dx

A.

A.

lOOP

0 0,0627 0,1257 0,,891 -0,2533 0,3186 0,3853 0,4538 0,5244 0,5978 0,6745 0,7554 0,8416 0,9346 1,0364 1,1503 1,2816 1,4395 1,6449 1,9600 2,5758 3 ,:1,905 3,8901j ,4;4172 4,8916 5,3267

0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2 2,2 2,4 2,6 2,8 3 3,2 3,4 3,6

100 84,148 68,916 54,851 42,371 31,] 31 23,014 16,151 10,960 7,186 4,550 2,781 1,640 0,932 0,511 0,270 0,137 0,067 0,032 0,014 0,006 0,00068 0,000057 0,000004

Agproximation pour les grandes valeurs du paral)1etre A.:

p= -

P

a>

).

-'A. e- ·

3,8 4 4,5 5 5,5

Bibliographie

47

20 log ,\

p

·-5 1

o

5

"'10-1

10

15

'\. \

1O~2

10- 3

10.-4~

\

10-5 FIG. 1.19.

Loi Nor!fl(ll~ R,iduite. Courbe donna.nt P enfonctioiI d,c 20 log}.

BIBLIOGRAPHIE [1] L

SOHWARTZ -

Methodes mi1thCmi1tiq~es pOllr les Sciences Physiques. Ed. Hennann,

1961,

[2] E.

RO UBll'fB -

Introduction

a la theorie de la €.ommunication. Ed. Masson, 2e- €dLtion,

1979.

.."••"

[3] B. P WINBClNG - Signaux aIeatoires. Tomes 1 et 2, Ed', Duned, 1994.

•c

[5] B. PICINBONd - Elements de Theori!) du Sisnal.

],

o c

•

'<e

8o

"0

[4] J. R. RICE - The Approximation offunctions. Reading Mass. Addison-Wesley, 1964.

[6] W.

PIITERSON -Error

Ed. Dunad, 1977.

Correcting Codes. MIT Press, 1972.

[7] W. B . BENNET - Spectra of quantized signals. - The Bell System Technkal Journal (BSTI),Juillet 1948.

~

~

• 1ic , ~

o

©

[8J .CCITT - Reseaux numeriques. Systemes de transmission et equipements de multiplexage, Vol. III-3, Genove, 'Suisse, 1981. [9] J. MAx - Quantiz"ing for Minimum Distortion. IRE Transactions on Information Theory, Vol. IT.6, pp. 7-12, March 1960.

1 •

48

La nUmeration du signal. tchantillonnage et codage

[10] M. D. PAEZ and T. H. G r.rssoN - Minimum merzn-Squared erto; -quantization in Speech PCM and DPCM systems. IEEE Trans. on Communications, Vol. COM-20, pp. 225-230, April 1972.

[11] C.

SHANNON - Commqnica1ion in the presence o/noise, Proceedings of LR.E., Vol. 37, pp. 10-21, Janv. 1949 (reimprime dans: Proceedin&, df the I1lEE, Sept. 1984 et Feb. 1998).

[1,,] P. DEBRAlNB- Mar:;hine$ de tra/tement de rin/Ol:mation. Tome I, Ed. Masson, 1972.

[13) R.

VAN DE PLASSCHE <
EXERCICES 1 Soit Ie developpement

en

.erie de Fourier de la Fonction i (t) periodique et tie T

periode T, nulle sur toute la petiode, sauf dans l'intervalle - -

2

la valeur 1. Donner la valeur qes coefficients pour t =

T

'2

et 'f =

~ t

'[ $; :-

2

011 elle prend la

T 3"-'

Verifier que Ie. developpement conduit bien it : i (0) ti6veloppement est limite a 5 tennes.

=

1 et tracer la fonction quand Ie

2 Analyse! l'echantillonnage ilIa frequence I e du signal set)

~sin (nl,t +

'1') quand 'I'

° 2' 1t

vane de Ii

Exaniiner la reconstitution de ce signal apartir' des echantillbns. 3 Calculer 1a distorsioo d'amplitude apportee it un signal restitue par des impulsions dont la largeurest egale la moiti6 de la periode d'echantillonnage.

a

4 EChantillonnage passe-bande d'un signal occupant la bande de frequence [/1 - IJ. QueUes soot les conditions aim poser ala frequence fJpour que ce signal puisse etre echantillonne directement a une frequence comprise entre Aet 2/2" 5 Analyser l'e.chantillonnage du signal suivant :

±

Sl (t) ~ n=l sin(zn"8 T'-) et Ie comparer acelu! du signal :

s, (t) ~

f

n =1

cos(2n".T ~) 8

Montrer parune ,etude des spectres que l!ensemble des deux suites d"ec'hantillons oon'stitue. l'echantillonnage d'un ~ignal complexe.

6 Soit s (t) Ie signal defini par Fegalite c s (I) ~ i

+2

(kt

3 Leos 2n hi

8

+ (jlk

)+ cos (nt +

(jl4)

Exercices

49

Ce signal est eehantillonne avec 1a penode T = 1. Quelle est la valeuL maximale que peut prendre s (n) avec n entier? Motilter qu'il exisle 'Un ensemble de valeul:s 'l'k (k ~ 1, 2,3,4) qui minimisent la valeur maximale des s (n) . Peut-on generaliser cette propriete ?

a

7 -Un synth6tiseur de frequence numerique est oonstruit partir a~une memoire morte de 16kbits ayant un temps d'acces de 500 ns. Sach~nt que les nombtes qui representent les 6chantillons de signaux sinusoi'daux comptent 8 bits, quelles sont les caracteristiques du synthetiseur~ gamme et pas de frequence, qui peuvent etre obtenues 7 8 QueUe est la loi de probabilite. des amplitudes du signal sinusoi'dal suivant : set) ~ A cos (2IT~) Calc:ulerla fonction d'autoc:orrelation correspondante. Donner la fonction d'autocorrelation d'un signal aleatoire .gaussien stationnaiFe dont Ie. spectre a une repartition uhifonne dans la ban,de de ftequence [f 1, Al.

9 Calculer Ie spectre d'une suite d'impulsions de largel1r TI2, separees de. T, chaque. impulSion ayant lil probabilite p d'apparaitre. Examiner en particulier- Ie CilS ou p ::::: 112. Que devient ce spectre si ces impulsions constituent IDle sequence pseudo-aleatoire de. longueur 24 -1 = 15 engendrk par un registre a4 bits, sulvantle polynome g(x) = X4 -t. X + i ?

a

a

.a

10 Un $ignal sinllsoidal la frequence 1050 H:z est echantillonne 8 kHz et t:ode 10 bits. QueUe. est la valeur du rapport sigmil a bruit maximal 'J Quel est Ie nlveau par rapport au signal du bruit de quantification mes'ure dans 1a: bande de frequence 300-500 Hz ? Meme question si la frequence d'echantillonnage est portee a 16 kHz. 11 Le signal sin

(2n ~ ~ 'l') avec. 0 '" 'l' ,,; ~ est echanlillonne "vee la periode T ~ 1 el

a

code:: 5'bits. Dans le cas ou q:> = 0 calculeF la puissance eJl le.:spectre. du bruit de quantificati'an. C.olilment evolue ce spectre en fonction de la phase ~?

,o

"••

'., •

]

•5 ~

l

.§

12 So~t une echelle de Godage ou Peehelon a La valeur q. Etudier la quantification du sign,aLsI (t) = (X • q. sin (cor' t) pour - 1 ~ (t ~ 1 ~ en .foncticn du centrage de.la caract6ristique. de quantification. Donner Fenveloppe gu signal restitue apres decodage et filtrage etroit aut~ur ae la frequence cu1 . Au signal '1 (t) on superpose Ie signal s,(O ~ 10,q.sin ill 2t. Eludier l"enveioppe du signal restitue dans ces conditions. 13 Soit a coder un signal gaussien. Combien de. bits faut-il pour que Ie rapport signal a btuit de quantification soit meilleur que 50 dB? Peut-on nfduire ce nombre si l'on admet un ectetage pertd~t 1 % du temps.

(2IT

14 Le signal set) ~ A sin ,S10.t) est code. il 8 bits, L"echelon de quantification ayant la ·v aleur q, tracer la co:urbe donnant Ie rapport signal i bruit de quantification en forrctiorl del'amplitude A Lorsque cette amplitude varie de q a 27 _q. Meme question 10rque Ie codage est du type non lineaire suivant la loi it 13 segments.

~

~

•

~

1io , o

©

15 CalcuJer les limit'es' des' plages dramplitude. elementaires pOUT Ie. codage Gptimal 2bits d'un signal gaussien de puissance unite ~

a

Chapltre 2

La tra ..sformation de Fourier discrete La transformation de Fourier Discrete s'introduit quand ,j1 s'agit de calculer la transformee de Fourier d'une fanction a l'aide d'un. calculateur numerique. En effet un tel operateur ne peut traiter <)ue des nombres et de plus en quantite limitee par la taille de sa mernoire.. II s:eh suit que 1a transformee de Fottrier ~ S (I) ~

r:

(t) e-i 2"fl dt

doit etre adaptee, d'une part en remplac,;ant 1e signal set) par des nombres senT) qui representent un echantillonnage de ce signal et tfautre part en limitant fensemble des nombres sur lesquels portent les calculs a tme valeur lime N . Le caleul faurnit alors des nombres S* (I) delinis par: N-1

S· (I)

~

~

s (nT) e ~j2"fnT

n=O

Corume le calculateur est limite dans sa puissance de caleul, i·l n" peut ["urnir ces resultats que pour unnombre limite de valeurs· de la frequencej, qu'l1 est naturel de choisir mUltiples d' un certain pas de fre'luence At Alars : N-1

S* (kl1f)

~

~ S (liT) e-i2mJkAfT n=Q

Les conditions dans lesqu,eiies les valeurs c_leul"es constituent une bonne approximatton des va leurs recherchees SO)1t etudiees par la suite. Un chaix simplificateur interessant consiste

a prendre' : At :S. ~.

On peut alors verifier qu'il existe seuleNT ment N v~1eurs differentes dans 1_ suite des S* (kINTj, qui est une suite periodique et de peri ode N pl!isque

S' [(k + N)/NT]

~ S* (kINT)

2.1

51

Definition et proprl"t"s de la TFD

D "l)ut;re part 1a transformee ainsi caiculee S8 presente sous 1a forme de valeurs discriotes et d' apr"s Ie paragraphe 1.6 sur l'e
2.,1 DEFINITION ET PROPRIETES DE LA TFD Soit deux suites de nombr.es complexes x(n) et X (k), periodiques et de periode N . La tninsformee de Fourier Discrete et la transformee inverse 6tablis:$ent entre ces deux su
1

N-l

.

nlv

X(k) ~ N n~o x (n)e -12'N" x(n) ~

N-'1

(2.1)

kn

L X(k)e i2'N"

(2.2)

k~O

La position du facteur d'echelle lIN est choisie pour que les X(k) soient les coefficients du developpement en serie de Fourier de la suite x (n). Cette transformation poss_e de les proprietes suivantes : - Linearit';: si.x(n ) et y (n) sont deux suites de meme periode, dont les transfor" mees sont X(k) et Y(k) respectivement, la suite de meme perioc!e v(n) ~ ,,(n) + AY (n) ou A est un scalaire a pour transforme"e : V(k)~X (k) +),. . Y(k)

~

••

'., •

]

•

g

- Une translation des x(n) entraine nne rotation de phase des X (k) ; En effet calculous la transformee Xno(kl de la suite x(n - no)'

XnoCk) ~

N -1

nk

L ..t(n - no) e -i2n N" = X (k)e-i2nnok!N

n =0.

Une translation de x(n) de no entplme sur X(k) une rotation de 1a phase d'un angle

.~ , '1 a: ' 2IT N n"k . § ega "0

~

~

j

1i

o5' @

- s.ymetrie: si la suite x(n) est reelle les nombres X(k) et X(N - k ) sont complexes conjugues : X (N-k) ~

N

L n=Q

. . n(N-k)

x (n) eI2n-N-~X(k)

2 • La transformation de Fourier discre.te

52

Si la suite x (n) est noelle et paire il en est de meme de la suite X (k). En effet, si x(N - n) ~ x(n), il vient par exemple pour N ~ 2P + 1 : P x(n) cos (nk) X(N-k)~x(O)+2n~' 21tN ~X(k)

Si la suite x (n) est [
X(k)~-2j n=l i

x(n h in(21t nk)=_X(N_k) N

On peut remarquer que X (0) ~ X (N) ~ o. Tout signal reel pouvant toujours se decomposer en une paTtie paire et une partie impalre, ces deux clernieres proprietes de symetrie sont importantes.

- CODyolution circulaire : la transformee d'un produit de convolution est egale au produit des transformees.

Si x(n) et hen) sont deux suites de periode N, la convolution circulaire yen) peut etre definie par I'equation : N-l

y(n)=

L

(2.3)

x(l)h (n-l)

1=0

C'est une suite qui possede la meme petiode N. Sa t'ransforrtlee s'ecrit: N-l[N-l

]

nk

N-l

J

[N-l

Ik

Y (k)~ n~o I~O x(l)h(n - l ) e-;2nN~ I~ox(l) n~o h(n_l) e-12n(n -lj kIN .e-;2nN N-l

Y(k)~n~o h (n _lje (

. (n-l)k)(N-l Ik) i2n - NI~O x(z)e-i2nN ~H(k) . X(k)

(2.4)

C'est 'line propriete majeure de la transformation de Fourier Discrete. Une application directe en sera donnee ulterieurement. - Egalile de Parseval : elle exprime que la puissance du signal est egale sornme des puissances de ses harmoniques. En effet : .

1 N

N- l

n~o x (n)x(n) =

1 N

N-l

N-l

.

kn

n~O x(nJ. k~O X(k) , -!2n N

(2:5)

a la

2.2

53

La transformation de Fourier rapide

~ Relation avec la serie de Fourier: avec la position du facteur d'echelle liN choisie dans la definition (2.1) de la TFD, les valeurs X(k) representent, aUX repliements de spectre pres, les coefficients du developpement en serle de "Fourier du signal periodique, quand ce sign'al ne 'presente pas de disctmtinuite. Si ce n'est pas. '1e cas, des differences importantes 'apparaissent. En effet, on montre qU'a Un point de discontinuite to de la fonction periDdique x (t), Ie develQPpeinent en serie de Fourier de x (t) prend une valeur egale it la moyenne des limites a gauche et a droite de xCt) quand t tend velS to. Par contre, la TFD inverse restitue exactement les echantiHons du signal d' origine et par suite les valeurs X (k) comptennent la TFD de la distribution des discontinuites avec Ie signe inverse et Ie facteur 1/2.

E>:;emple : soit Ie signal triangulaire :

x (t)

~t;O$t < l

x(td)~x(t) Coeffic.ien~

du developpement enserie de Fourier:

Co ~ 1/2 Cn ~ j/2rrn; n entier; n '" 0 La discontinuite a I'origine a une amplitude egale Fourier discrete d'ordre N donne les valeurs suiv,antes : X(k)~ ~

1 2N +X'(k)

a r ella transformee de ,

avecX'(k)~Ck

Celte particularite de la TFD par rapport a .1a serie de Fourier est un effet indesirable quand on cherche. un developpement avec des coefficients ayant les valeurs les plus faibles possibles, cnmme dans-Ia compression des signaux, Cependant la propriete la plus importante de la Transformation de Fourier Discrete reside probablement dans Ie fait qu'elle se prete a des techniques de calcuI efficaces, qui lui ont donne une place preponderante en traitement numerique du signal.

.."•••

2.2

LA TRANSFORMATION DE FOURIER RAPIDE

],

Les equations de definition de la TFD fournissent une relation entre deux ensenlbles de N nombr.es complexes, qui s'ecrit d'une maniere commode SOliS une .~ forme mat;ricieile, en posant ~

•

g 8o

"0

~

~

•

(2.6)

~

1i

8' @

Les affixes des nombres Wn, appeles coeffic'ients de la T.F.D. se trouvent sur I" eerGle 'Unite comme Ie monire la figure 2.1. Ce sont les racines de l'equation ZN -1 = 0 ou racihes Niemes.de l'unite,

2 • La transformation de Fourier discrete

54

FlO, 2.1.

A fjUes des coefficienrs de]a TFD

L!equation matricielle est la suivante pour la transformee direc W.

Xu X,

Xz

1 N

X N- 1

1 1 1

1

1

W

W2

W2

W "

W ' W 6

1

W (N-l)

W 2(N-i)

1

1 WN ~l

W Z(N-l )

W (N _l )(N: -l)

Xo Xl

-'2

'¥N-l

Pour la transforrn,,,e inverse, ilsuffit de retirer Ie scalaire 11:N et de· changer Wn W-n. La matrice carn~e d'ordre N designee par TN presente des particularites evidentes, les !ignes et les colonnes de meme indice ont les memes elements et ces 61ements sont des puissances d'un nombre de base W tel que WN ~ 1, Des simplificaen

tions importantes peuvent etre envisagees dans ces conditions, co.nduisant

a des

algorithmes de calcul rapide. Quand la TFD est caleul"e a ['aide de tels algorithmes on dit que l'on effectue une Transformation de Fourier Raplc\e (TFR). Un cas tres interessant est celui

a des

au Nest une puissance de deux car il conduit

algorithmes peu complexes qui sont particuJierement efficaces. Ces algo-

a

rithmes sont bases Sllf une decomposition de la suite transformer en -solis-suites entrelacees. Le cas de l'entrelacement dans Ie temps va etre considere d1abord.

2.2.1 TFR avec entrelacement temporel La suite d'elements x(n) peut etre decomposee en de-uX suites- entrelacees, celle des elements d'indice pair et celle des elements d'tndice impair. Calculons, en faisant apparaitre cette deco.mposition, 'les NI2 premiers elements de Fensemble des

X (k ) : 1

1

W Z

W 2(NI2-1)

Xz

1 1 i

W'

W4(Nlr ~l)

X N1Z - 1

1

W Z(NI2-1 )

W 2(NI2-1)(NI2 " )

Xo

X,

Xo

x, x.

·">\N12 - i )

2.2

55

La transformation de Fourier rapide

i

1

W W2

W' W6

W Nfl-l )

W3(NIl -l)

+

x,

1 WN- I)

x,

W'(N-l)

-'5

W(NIl -I)(N -1)

~N -l

-,-

E,n designant par TNfl la matrice qui vient en facteur du veeteur eolonne des elements d' indice pair et en decomposant la lnatrice [acleur du vecteur des elements d'jl'ldict; impair en un produit d'une matriee diagonale par la matrice T N!4' on obtient :

Xo

X, X2

a o

X2

~TNIl

XN",-_i

X.

a

1

'>:0

+

Q

W Q 0 W'

O. 0

X2(NIl' _I)

o o a W N/lr1

XN_I

Et pour les N I2 derniers elements de l'ensemb le desX (k), compte tenu du fait que WN~l : X N fl

Xo

1

0

0

0

Xl

XN12+ 1

X2

Q

W

0

Q

X,

0

0

W2

X3

X2(NIl- l )

0

0

0

X N!2 +2

~TNIl

XN - I

0 .. . WNIl- I

T Nt2

-'5 'XN_l

n appaIait que Ie calcul de X ( k ) et X (k + N /2) pour- 0 '" k '" N /2-

1 met en ceuvre les memes ealculs avee seulement un changement de signe dans. la somme finale'. D 'oa Ie diagramine suivant : ligne k

Xi

o ,;;

k ~ Ni l

~

X 2(NIl -I j

1 Jigne fr.

"••

'.

W'

],"

•c

g

l•

ii -a.

• 1ic , ~

o

©

Ce diagramme montte que le caieul d'une Transformee de Fourier d'ordr:e N revient au caicui de deux transformees d'ordre NI2 auquei s' ajoutent N/2 multiplications complexes, Par iteration en un nombre d' 6tapes egal a log 2 (N) - 1 ~ log 2 (N/2), on aboutit aux transformees d'ordre 2, dont lit matriee s'eerit :

T~ [1 1J

1 - 1 et qui ne demandent pas de multiplications, 2

2 • La transformation de Fourier discrete

S6

Comme chaque etape comporte N /2 multiplications complexes, l'ensemble de la transformation del1'1ande un nombre de mqltiplications: complexes: Me qUI sleerit:

M, ~ N /210g 2 (N /2)

(2.7)

et un nombre d' additio ns complexes A c tel que:

(2.8)

A t ~ N log 2 (N)

En re-alit6- Ie nombre de multiplications complexes peut encore etre fe-duit paree que certaines puissances de W presentent des particularites ; WO= 1 et W N /4 = - j ne demandent p.as de muLtiplicati,OnS c,Omp!eX<4i ; et TIe demandent qu'une dt(mi-multiplication complexe chacune. Dans la

premiere

etape on peut ainsi economiser 3 multiplications, dans Pavant clerniere etape 3. N /8 et dans 1a derniere 2 . N /4. Le gain dans I'ensemble des etapeS' ,'"Ieve Ii 5N /4 - 3 et Ie nombre minimum de multiplications complexes est donne par :-

n fa ut

toutefois noter que toute.s ces reductions de cal'cu! J;le so1),1 pas toujours faciles a exploiter, aussl bien en logioiel qu'en materie l. La transformee d' ordre 4 a pour matrice :

+~ 1

11 1 1 - j -1 T4 ~ 1-1 1 -1 [ 1 +f - 1 - j

(2.10)

.son diagramme est donne par la figure 2 .2.

= Xo + " > + x, +x, = Xo - x, -ilXl- l1 ,i Xo

X,

X'j

=XO-+:':2 -

X, = X,a

Xl

- x,

-X2+j{ Xl - x 3)

(xo +x,) :><,:xo . (xo -x,) x, w·o

w'

ix,+x,i -x.,)

(X,

::x-:x, X,

FIG . 2.2. Transformee d' ordre 4 avec entrelacement temporel

Par convention 1es fleches representent les multiplications, les points it gauche des croisi11o~ 6Iementaires representent, Ie point superieur une addition, Ie point inferieur une soustraction. La transformee d'ordre 8 est representee sur Ia figure 2.3.

2.2

La transformation de Fourier rapide

57

Xo

·X.

X' I

x.

X,

w·

X,

X, X,

x.

XI

Xs

:1:(.5

X,

Xl

)(,

w'

FIG. 2.3.

w'

"

Transfonnee-d' ordre 8 avec entreiacement temporei

On peut remarquer que dam; ce traitement les X (k) apparaissent dans Yardre naturel des indices alars que les x en) se presen\ent dans un ordre permute. Gett", permutation est due aux entrelacements successifs et se traduit par un retournement ou inversion de 1a repres~ntation binaire des indices. Par exemple pour N = 8 .:

it . :

(0 00) correspond' : Xo (0 0 0) (00 1) x 4 (1 00) x 2 (0' 1 0) x 2 (0 10) .<3 (011) X 6 (11 0) Xo

xi

x4

(100)

Xs (1 0 1) .1'6(110) x7(111)

(0'01) x, (1 01) x3(Oil) Xl

x7 (111)

La quantite de memoires de donnees necessaire pour calculer une transformee d'ordre N est de N positions complexes. En effet les calcuIs sont faits sur des couples de variables qui subisseht Foperation representee paL' un crolsillon et cOTI,servent leur position dans l'ensemble des variables a la fin de cette operation, ~ comme l~intliq.uent clairement les djagranunes. D ~ autre part, 1a transformee ~, inverse est obtenue en change ant simplement Ie. signe- des exposants de- W. On ]I introduit Ie factem l iN , par exemple en l11ultipliant pat 112 les resuItats des addi• tions et soustractions effectuees dans ies croisillons ce qui permet de Conserver' ie ]," oadrage des rrornbres dans les memolres. On peut aussi faire les c.alculs sans inversion binaire, il faut alors 2N memoir.es •c g de donm\es, car les couples de nombres chaugent de position a chaque etage, • "6... Le- type d'entrelacement qui vient d'etre etudie peut aussi etre opere sur les ii8 X(k) ·; un algorithme simiJaire est alars obtenu .

.. ~

~

• 2,2,2 TFR avec entrelacement frequentiel 1i 8 La suite des elements X (k) peut etre decomposee en 2 suites ~

@

elements

d~indice

entrelacee·~, celie des pair et ceUe des elements d'indice impair. Pour les elements

2 • La transformation .de Fourier discrete

58

d'indice pair, en tenant compte eu fait que WN teur e1ernentaire :

= 1~

il vient apres ujle 'm ise en fac-

1

1

1

r

i

W2

W2(NI2-I)

X4

1

W4

W' W8

Xc,(NI2-1)

1

WU,NI2-1l

Xo ~

Xo + xN I2 Xl

W4(N"'_1)

WUNI2-I )(NI2- I)

+ X.NJ2. + 1

X 2 + X NI2 + 2

XNl2 - 1 +XN_l

Et pour leselements d'indice impair, apres mise en facteur: X,

1

W

X3

1 1

W3 W'

X,

W2

WNI2 - 1

Xo -= XN/2

we

W3(NI2-1)

Xl -X,N12+1

W'O

W'(NI2 -I)

X:2 -XNi'2 + 2

W(N-I)(NI2.-1j

Dans ce cas la matrice carn~e abtenue est egale au produit de la matriee carn~e TN!2 abtenue pour les elements d' indic.e pair par la matriee diagonale dont les elements sont les puissances Wk avec 0 oS k '" N /2 - 1. D' oil :

X, X3

X,

= TN'"

1 0 0 a 0 WOO 0 '0 W2 0

o

0

XO-XNI2

X, -~NIZ+1

X 2 -XNl2+ 2

0

Le ",llcul des elements X (k) d' indicepair et d 'indice impair se fait avec la matrice oarree T NI,2 de 1a transformee d !ordreN/2 et Ie diagramme suivant est abtenu :

Xo X2 X 4

TNI2

ligne k

"'.

X Z(N!2 -1)

.0':;; k .:;; N /2 - 1 X, X3 X,

ligne k TNI2

X N/ 2 +k

W· X N -1

En adoptant la meme notation pour les croisillons qu'au paragraphe precedent on etablit des diagrammessemblables. La figure 2.4 montre Ie diagramme obtenu pour N ~ 8. Dans l'entre1acement frequentiel, Ie nombre de calculs est Ie meme que daNS l~entrelacement tempore! ; les hombres- a transformer x (n) apparafssent dans I'ordre nature! alors que !es nombres transformes X (k) sont permutes.

2.2

59

La transformation de Fourier rapide

Les algorithmes qui ont ete obtenus jusqu'a maintenant sont bases sur une pecompbsition de la transform6e p"ordre N en transformees elementaires d'ordre 2 qui ne necessitent pas de mullipncatians. Ces algorithmes sont dits en base 2. Cep'e ndant d1autres transformees 6lementaires peuvent e-ire utilisees; la plus in,teressante est 1a transformee en. bas'e 4 quJ s'appuie sur la matrice e16mentaire. T 4 et conduit aux algorithmes en base 4. x , ~~--~----~~----~----~----~

x,

~~--~~--~~~~~--~~~-f~

"

x,

",

)(,

., x,

",

x. ~----~~----~~~-?~~~~-*~~

.,

X,

X,

wO

)(7

"7

w3 FIG. 2.4. Transformie d'ordre Saveo entrelacement jrequentiel

2.2.3 Algorithme de TFR en base 4 eet algorithme peut etre utilise lotsque Nest upe puissance de 4. La sHite des nambres x(n) est decomposee en 4 suites entrelacees . Calculons Ie. ; premiers

X(k) en mettant en evidence cette decemposition ; l'expression matricielle est alors la suivante, si T N/4 designe la matrice carree cle la transformee d"ordre N /4 et DI(i ~ 1,2,3) la matrice diagonale dont les elements sont les puissancesWI.k avec. 0 ", k '" N/4 -1 :

Xo

X, X, XN14~1

x, x,

Xo x4

:::::TN /4

Xs

x 4 (N/4 _.1)

+ D,TN/4

Xg

XN_3

X3

X2

+ D2TN14

x6

x,

xlO

xll

+ J!)STN/4

60

2 • La transformation de Fo urier discretE;

Les N/4 termes X(k) suivants sont donnis par:

XNI4]

~N;4+1

[X

N/2 - J

Cette equation fait intervenir les me"m es calculs matriciels que la precedente avec en plus des multiplications par les elements de la seconde ligne d", la matrice 1'4. On peut alors mantrer que Ie ~alcul de la transformee aboutit au diagramme 4e la figure 2.5.

Une telIe transformee s'effeclue en 10g4 (1'1) -1

~ log" (~) et.apes.

2.2

61

La transformation de Fourier rapide

Chaque etape demande 3

~

mUltiplications complexes ce qui conduit au total au

nombre de multiplications Mc4 donne par :

M"

~ ~ Nlo& (~)

Le nombre d'additions complexes Ac4 s ~eleve

(2.11)

a:

A'4 ~ 2N lo&(N)

(2.12)

II apparait que Ie nombre d'additions est Ie meme en base 2 et en base 4, pai; contre PQur les multiplications iComplexes, Ie caleul en base 4 apporte un· gain superieur a25 %. La figure 2.6. donne Ie diagramme complet pour N ~ <6. Xq ~--------~~~--1X4

~----------~~~-w.e

"

'" )(1

~

X,

w2

)(9

'11 3

Xl)

WO

X2

'-------W"'2O""--.2l--.::--- '" '-------w·,;-+--~}---I~-

w6

)(14

WO

XJ

'-~--~W~"~--~-{~-.

FIG. 2.6.

."••" ],

x 10

"

w6

X"

w9

X15

TFansfomlie d'ordre 16 en base 4

D 'autres. bases peUvent encore etre envisagees, par exemple la base 8; dans ce ca's, il y a' des multiplications dans la matrice 6lementaire et' les' gains pat rapport a la base 4 sont minime§. Des bases differentes peuvent 6galement eire combinees [5].

•c o c

.~

8o

'0

~

~

2.2.4 Algorithme de TFR en base double Dans une transformee d'ordre N , la -suite des va'leurs iransformees d'indices

• impairs peut etre decomposee en deux suites, exprimees par Tes relations :

~

,.

-g o

"

1

N-l

N

.~O

X ( 4k+l ) ~-

L

x(n)wnW4kn

2 • La transformation de Fourier discrete

62

at: 1

N~ l

N

n=O

Lx

X (4k + 3)~ -

(n)W"'W4kn

Compte tenu de la definition (2-6) de W les sommations.peuvent aussi ~'ecrire :

1L

X (4k+1 ) ~-

N

( N )] 2

N/4 - 1 [ [

n~O

x (n) -xil+-

et:

1 X(4k+3)~ N

.'fo

N)]

x(n)-Ji n + 2"

NI4 -1 [[

.

(

t

j

[x(n+ ~) -x(n

t

3~)]] w'nW4kn

(2,14)

La suite des valeurs:trapsformees d'll1dices Ra irs. s'eorit :

(2.15) Ces equations montrent que la premiere etape d1une transformee d'ordre N avec entrelacement tempore! peut etre remplacee par Ie calcui d'une transformee d'ordre NI2 et de deux transformees d'ordreN/4. L' algorithme en base double est obtenu par applications successives de cette decomposition. Pour l'entrelacement frequentieJ l'algorithme en base double est obtenu par la de.composition suivante : N(2- 1

X(k)~

L

n=O

N/4-1

x (2n)W2nk+Wk

L

x(4n+l ) W4nk

n =O

Nr4 - 1

+ W 31e

L

x (4n + 3) W4nk

(2.16)

11=0

Rour une transformee d'ordre N, Ie nombre de multiplications complexes M,2J4(N) est fouIni' par une fe.currence d6duite des relattons ci-dessus :

(2.17) ave.c. comme valeurs initiales M (2) ~ M (4) ~ O. La valeur ainsi 0 btenue est legerement inferieure acelle donne-e' par la base 4. A titre de reference, il est interes:$ant de noter que Ie nombre minimal de multiplicatIons complexes non tr1viales pour une transformee d'ordre N , avec.N = 2m,. est ega!" : 2 m + 1 - 2m 2 + 4m - 8 [5].

2.3

63

Degradations dues aux limitations dans Ie cafcul

Les algorithmes qui ont ete presentes, entre\acement temporel et frequentiel, en base dell)< e\ quatre, sont des elements' d 'un ensemble d'algorithmes, Vne presentation unifiee des algorithmes de TFR est donnee dans Ie chapitre sUivant, elle 'permet de determiner l'algorithme Ie plus approprie dans chaque application, Dans les calculs, les operatiofis sont faites avec une preGision limitee, ce qlli amene certaines degradations du signal.

2.3

DEGRADATIONS DUES AUX LIMITATIONS DANS LE CALCUL

Les machines reelles apportent des limitations dans Ie calcul, qui sont dues aux operateurs arithme-tiques et aux me-moires. D1abord les coefficients sont souvent stockes dans- une mem6ire morte, avec 'un nombre de- chiffres limite ; e-n fait Ie contenu de la memoire represente une approximation des coefficients, en general obtenue par arrondi. Ensuite tout au long du calcul des arrondis sont operes pour limiter Ie no mbre de chiffres des nombres traites a 1a capacite des positions de memoire ou des operateurs arithmetiques . .Ces deux types de limitations entralnent des degradations qu' il est important d'analyser pour pouvoir determiner avec precision Ie materiel strictement necessaire a 1a mise en ceuvre d'une Transformee ayant des performances .specifiees.

2.3.1

Effets de I'arrondi des coefficients

Les coefficients reellement utilises par la machine re presentent une approximation des c,oefficients tMorigues, dont Ja valeur des parties reelle et imaginaire est comprise dans l'intervalle [- 1, + 1J. ' n Une quantification 'abe bits, sigrre compris, entrame sur ie coefficient e-J·271"'~i une erIe\jr d'arrondi I)(n) ~ odn ) + j o] (n) telle que l'on ait:

IIlr«n) i "' 2- b ,

.:ijj ~

,o

'.,

1

:5o

•

S o

"0

L

N

]

a partir

n ~O

des donnees

nk

N -1

X (k ) +t'1 (k) o= -

•

'
10](n)I <; 2- b ,

Le caleul de chaque nombre transforme X(k) avec une erreur t'1 (k) telle q\le :

"•• •

et

x (n) [,,-i"" 'iJ +o (nk)]

so it :

i

N-1

t'1(k) ~ N n~O x(n) 8(nk)

~

~

• -g ~

"

o

@

Comme il existe entre les x(n) e\ X(k) la relation (2,2) : N- l

x (n)=

L

n~O

X (k )e

i 2n

nk

N

x (n) est fait

2 • La transformation de Fourier discrete

64

i1 vient; N-l

/1(k) ~L

j =O

X(i) e (i, k)

(2,18)

(2.18) Par suite l'arrondi des coefficients de la transformee entralne pour Ie nombre transform" X(k) une perturbation /1(k) obtenue en faisant une somme· de perturbations- 61ementaires doht chacune est egale au prQduit d' un nombre- transforme par 'Un facteur representant sa contribution. Les nombres transfoJ1mes reagiss:ent les uns sur les autres et ne sont plus strictement inciependants. Pour toute transformee il est possible de calculer les eli, k). Il est en general interessant de connaltre la valeur maximale Em que peuvent prendre les 1,E(i, k)1 pour un ordre de transfoT!nee et un nombre de bits de quan,tification be donnes., D'apr"s l'inegalite : lo(n)1 oS y'2. 2- b , un maximum pour em est fourni par:

em """ y'2.2- b , En fait les valeurs trollvees en pratique pour Em §dnt nettement infe.rieures a ce maximum. Par exemple pour N = 64, on trouve Em ::::::: 0;6 .2 -b,, ; eette valeur se conserve e nsuite pour les valeurs de N sup6rieures [6].

2.3.:2 Bruit de calcul dans la lFR Les donnees se presentent a Fentree d~un cakulateur de TFD avec un nombre de bits limite. A chaque operation, addition et multiplication, ce nombre de bits augmen1e. En ge'neralle nombre de bits affeate chaque donnee reste fixe dans tout Ie calculateur i iI en resu'lte Ia necessite d.l.operer des limitations du nombre de bits des nombres au cours du ca1cul. Ces limitations ·sont presque toujours faites par une elimination des bits de plus faible paids avec arrondi. En effet, un depassement vers les forts poids n'esl pas acceptable en general et Ie cadrage des nornbres dans les memoires doit etre etudie en con~equence. Deux cas importants et simples vont etre exanlines pour une transformee en

a

base 2. D'abord la transformee directe : avec Ie facteur d'echeiie

J~

il suffit de divi-

ser par 2 les resultats des additions et soustraction~, dans chaque crbisillQn pour maintenlr un cadrage convenable. EnsuIte sera etudie Ie cas ou Ie cadrage au debut de la transformee est tel qu'il permet la totalite des calculs sans risque de depassement. Ce cas pellt etre celui de la transformee inverse. Pour e,valuer la puissance du bruit de calcul, on considere que la machine stocke les nombres dans des memoires ayant la capacite de hi bits pour chaque nombre [Joel et l'an prend comn'le unite la plus grande amplitude representable ;

2.3

65

Degradations dues aux limitations dans Ie cafcul

c~est-a-dire ql,le les nombres internes prennent des valeurs comprises dans t~inter­ valle-[-l , + 1] et ql!e l'echelon de qualification q a pow valeur ;

q

~ 2.2-b.~

2 1- b,

La figure. 2.7 donne Ie schema d' un craisillon avec multiplication.

Crbisillon de TFR en base 2

FIG. 2.7.

A l'entree du croisillon 'les donnees comp.lexes sont representees par une partie reelle et une partie. imaginaire comprenant b j bits- chacune. Apres multiplication les nombres subissent une'lirnitation a b j bits avec arrondi. Cette operation sur un nombre reel apparte

~me

puissance de bruit estimee

a

i2' '2

La multiplication

complexe Se realisant generalement par 4 multiplications reelles, 11 d'une puissance de bruit egale

a

4i2 '

y a introducti0n

2

Le coefficient Wk ayant un module qui ne

depasse pas Punite, aucun recadrage des donnees dans ies memoires n'est necessaire. Bruit de calcul avec recadrage Le. recadr.age. des donnees. est suppose. e tre realise avant le.s operations. d:additiQn et soustraction du croisillon, ce qui est un cas defavorable mais 'facilite la realisatio n. Les parties reelle et iml;lgjnaire sont divisees par deuX' par un decal age au couts duquel un bit est elimine; ce bit 'ayant la valeur 0

QU

1 avec la probabilite

~,

on adrnet que sur chaque nombre reel il en resulte. une puissance de bruit egale 2

,o

."••• ],

•

~ et sur Ie nombre complexe nne puissance de bruit egale

2

a q4

a

. Par contre les

bruits presents anterieurement sont divises par 4. A I'entree de chaque croisillon Ie signal est affecte du bruit Be, it I. sortie du bruit Es. Avec Ie recadrage il existe entre Bs et Be la relation suivante :

o o c

•

'0..

8o

]

~

~

Le premieretage de la transformee ne comprenant pas de multiplication ; si Ie bruit a l'entree du calculateur de TFR n'est pas pris en consideration, il vient en sortie du premier croisillpn : BS,~

q2

"2

2 • La transformation de Fourier discrete

66

Le seco nd etage, dans l'entrelacement temporel par exemple, a des multiplications par j qui n'entrainent pas d'arrondi, Le bruit en sortie

s\~crit dans

ces conditions: q1 1 ) q2 q2 BS;, = 2 ( 4 + 4 Bs, = 2 + 4

dememe : 1

q2

BS3 = 2 (

)

.q 2

q'2

q2 .q2 q2 <4 + 8. + 12

4 + 4 g", + 12 = 2 +

Au demier 6tage de rang IQg 2 (N) : q2

ib(~) 2

L

B ST = - + 2

[ =0

1

~

21

lb(~)

q2

S

L

+ -

12

f =O

1

2i

Finalement en sortie de transformee on peut ecrire :

Bs-r "" q 2 D 'ou le resu lt-at : dans- une transformee avec recadrage par division par '2 etage, 1a pu.issance de bruit sur chaque sortie peut etre estimee a: BST ~

2 2 (1-b. 1)

achaque-

(2.19)

Bruit de calcul sans· recadrage Les puissances de bruit relation :

a l~entree et ala sortie d'un cJ'oisillon sont ijees par la 2

Bs = 2Be+4~ 12

En considerant qu'il n'y a pas production de bruit dans les 2 premiers etages, Ie bruit to tal sUr chaque sortie est dtmne par: q2 N

B sr =4 12

Ib(~)

8 {~O

1

2'

d'ou :

Dans !.me tr-a:hsformee sans recadrage, la puissance de bruit 'sur chaque ·sortie peut etre estimee a: 22('~b,)

BST

"'"

N . ----:1'"'2;--

(2.20)

Ce :resultat peut s~nterpreter en disant que la precision des donnees se trouve

redulle de ~ bils apres Ie calcul d'une transformee d' ordre N =2M Le meme raisonnement peut etre applique au Galcul suivant d'autres bases, en par-

ticulier la base 4. Les resultats obtenus sont comptlIab1es_

2.4

67

Calcul de spectre par TFD

En pratique les puissances de bruit dOlvent eire associees aux puiss-ances du signal et Ie parametIe Ie plus interessant est Ie rapport signal it bruit. Pour determiner comment evolu,e ce parametre dans line Transformee, la relation qui lie la puissance du signal a·la puis$ance de $on spectre est: utilisee :

~ :~; fx(n)12 ~ :~; IX (k) 1

2

Le rapport ~ignal a bruit en sortie de la Transforme.e depend de la repartition de la puissance entre les X(k). Far exemple dans Ie calcul avec recadrage de la Transformee directe, avec t'hypothese d'une repartition uniforme de la puissance entre les X (k), la puissance de chaque sortie se trouve divisee par N. Dans

c.es conditions si S designe la puissance du signal. en entree, si Ie bruit a a bruit en sortie de traru;formee (S/B)s-r. s'ecrit:

I'entree est neglige, Ie rapport signal

S (SIB)ST ~ N2"(Lb'1

(2.21)

Dans les memes conditions, mais- sans recadrage la puissance du signal est multipliee par N et Ie rapport (SIB)ST devient :

(SIB lST ~ Les calculs qui ont

ete'

S 22(1

"'J/12

(2.22)

faits dans ce paragraphe qoivent eire consideres comme

approximatifs. lis ont "Ie menes dans I'hypothese d'une absence de correlation entre les erreurs. Vne telle hypothese n'est pas toujours verifiee, en particulier pow les transformees d'ordre N faible. L'analyse simplifiee qui a ete presentee est suffisante dans la plupaTt des applications; \Ine analyse approfondie est donnee dans la reference [7]. L'application la plUS directe ae la TFD est I'analyse spectrale.

2.4 .:ijj

CALCUL DE SPECTRE PAR TFD

~

Le calcul d'un spectre par la Transformation de Fourier Discrete oblige it faire cer-

~

taines apprQximations et necessite un choix convenable des pa'rametres pour atteindre les perlormances imposees. Avant de considerer les applications. il est utile cependant de bien voir la fanction remplie par la Transformation de Fowrier Discrete.

.~ ~

,

•c o

~

2.4.1

Fonction de filtrage remplie par la TFD

'1C

8o

Examinons la relation qu'etablit la Transformation de Fourier Discrete entre les sorties X (k) et les entrees x (n) considerees comme Ie resultat de reohantillonnage • (I'un signal x (t) avec la periode T , Pour k ~ 0 celte relation s'ecrit: -g 1 N-l o5' X(O) ~ - L x (n) @ N n=O '0

~

~

~

2 • La transformation de Fourier discrete

68

Le signal X (0) ainsi ciMini resuite de ia convolution du signal x (t) avec la distribution <poet) lelleque : 1 N-l
.

L

-

N

n=O

o(t~nT)

La Transformee .de Fourier de cette ,distribution est d'onnee p"ar :-

1>0 (f)

~

1 N

N-l

L

e- i2
n=O

1 N

1~e-i2M[NT

~

1 ----.. e '-- j21tnfT

Ou encore:

avec

1 sin (It.tNT)

(2.23)

<1> ([)= N sin (lttr)

Or une operation de convolution dans llespace des temps correspond a un produit dans l'espace des' frequenees, c'est-il-dire que X (0) est un signal obtenu par filtrage du signal d'entree par la fanction <1>0 (fl. La figure 2.8 represente la fanction <1> (I) et ia fonction

(1) s'annule

aux points de l'axe des frequences multiples entiers de Elle est periodique et de periode

~

~ sauf 'aux multiples de ~ .

conformeinent aux lois de l'echanttllonnage;

il s'agit simplement du spectre d'une impulsion de largeur NT echantillonnee. v\ la sortie X(k ) correspond la fanction
1 N


N-l

""

L e-i'" " ll (t-nT)

n~O

'f' (\)

I rIf"r·1··] u

1

NT 0

T

.1

2T

t BIG.2.8. Fonction de filtrage

--,,

ddaTFD

\ \

0

1 NT

2 NT

~-

1,-

,

-'

f·

1.1

(./cul du spectre pour TDF

69

SallS forme concise, apres simplification, 11 vient:


(2.23bis)

La sortie X (k) fmlrnit 1e signal fi1tre suivant 1a fonction
!

sur l'axe des frequences.

Finaiement la transformee de Fourier Discrete constitue un ensemble de N tiltres identiques~ ou han(l: d~ filtres~ repattis ufliformement dans Ie domaine des frequences avec Ie pas :T'

Si Ie signal d'entree est une suite periodique. suivant l'hypothese. de definition de la TFD , ce bane de filtres se trouve echantillonne en frequenee avec Ie pas

~,

et l'on peut remarquer qu'il n 'y. pas d'interferences entre les>sorties X (k) . Celte propriete cependant est perdue, en toute rigueur, si les coefficients sont arrondis, cQmrne un paragraphe precedent montre., La mise en evidence de la fonction remplie par la TFD illustre aussi Ie probleme du cadrage des nomhres dans les memoires d'un calculateur de TFR. En effet supposons que les nombres it transformer x (n) resu1tent de !' echantillonnage d'un signal aleatoire dont 1. Ioi de probabilite des amplitudes 'a la variance 0 2. Si ce signal a une distribution spectrale energ6tique uniforme~ sa puissance se repartit

ra

unifonnement entre les X (k) . et chacun a une variance egale

2

a ~ . 'Par contre

si Ie sigmil a une distribution spectn!le qui (,eut se concentrer sur ul1 X(k), cet X(k) ala meme loi de probabilite que les x(n), en paTticulier la variance 0 2 Le r«ca.;irage des nombr~s pac division Par .2 it cl)aque etag!" crun caleul de TFR ~st adapte au traitement de tels signallx. On peu! approfondir l'etude du processus de filtrage en observant que les sorties X (k) de la TFD sont les sommes des entrees x (n) apres dephasage. En effe! la sortie X (O) est la SOmIDe des ",(n) avec Mph as ages nuls, 1a sortie X (k) est la .'!:::i

ow

~,

"~

.•••

somme des x (n) avec dephasages multiples de 2rr

~ , comme 1e montre la figure 2.9 .

A chaque

sortie les composantes des signaux Tesultants qui sont en phase s'ajo utent, Ies autres s'annulent. Par exemple si les X (n) sont des 110mbres complexes ayan! la meme phase et 1e meme module, tous les X(k) s'annulent saufX(O).

],

•

c o c

•

'D-

S o

"0

~

~

•

~

,.

1i o

@

X,

Xo FIG. 2.9.

Filtrage par dephasage dans fa TFD

2 • La transformation de Fourier discrete

70

Cette observation est utile dans I'etude des banes de filtres qui comprennent un calculate·ur de TFD.

2.4.2. Resolution spectrale L'analyse spectrale est utilisee dans de nombreux domaines. Elle ~e fait a partir d'un enregistrement foumi par 'un capteur. Or, par definition la TFD etablit une relation entre deux suites periodiques, les x (n) et X (k) qui comprennent ehacune N elements qifferents. Pow I'utiliser il faut dOfie i)ltroduire cette double periodicite. La periodicite en frequence est introduite par l'operation d'ec hantillpnnage du signa1. Llenregistrement a traiter se pre-sente soit sous forme numerique, alors l'echantillonnage et1e cod age ont He effecttJes par Ie capteur, soit

SOllS

forme "ana-

logique et alors il faut Ie nunreriser. Le choix de I. frequence d'echantillonnage

f, ~ ~ doit .()tre tel q\le les composantes du signal de frequence superieure a fj2 soient negIigeables et eil tout cas inferieures en amplitude a l"erreur tole-ree sur l'amplitude des c.omposantes utiles. On peut s'assurer que cette cpndition est hien remplie en procedant a un prefiltrage du signal. La perioclicite temporelle est introduite artificiellement en supposant que Ie signal se reproduit en dehors de l'intervalle de temps 8 ~ NT qui correspond a renregistrement atraiter. Dans ces conditions la TID fournit un echantillonnage du spectre avec une periode frequerttielle I'1f egale a l' inverse de la dUree d« l'enregistrement et qui constitue 13 resQlution frequentielle de l'analyse. La relation

1'1/ = ~

exprime pour l'analyse spectrale la relation d'incertitude de Heisenberg.

Uno. analyse plus fine peut etre obtenue en augmentant la duree de ['enregistrement, par exemple en la portant aN'T (avec N' > N) avec des echantillons complementaires nuls ; les echantillons frequentiels supplementaires obtenus constituent simplement une interpolation des precedents; ceUe operation se pratique couramment pour avoir un nombre de donnees N' qui soit une puissance de. 2 et pour pou-

vQir utiliser les algOTithmes de calcul rapides. D' autre part Ie fait que Ie signal ne

soit pas compose uniql)ern;ent de raies aux frequences multipies de

~

entraine

une interference entre les' composantes' s,pectrales obtenues; en effet la fanction de-

filtr.age (f! de la TFD, qui a ete don nee au paragraphe 2.4.1, presente des ondulations dans toute la bande de frequenees et sf Ie signal possede Ulle composante speetnile S (fo) ala fr€quence fo, c'est-a-dire si x(t) ~ S (to) ei2~fot, on obtient :

X(k) '"' S(fO) (:T - fo) pour .O ~ k

~

(224)

k < )0 • < kNT + 1 11'1 en resu ' 1te une contn. butlon . non seu1eN -1. S· 1· NT

ment sur les sorties X (k) et X (k + 1) de la TFD, maissur toutes les sorties, comme Ie montre 'la fi.gure 2.10 ~ ainsi appaTaissent les limitations du pouvoir -separateur

2.4

71

Calwl de spectre par TFD

de l' analyseur. eet effet peut etre a!tenue en modifiant la fonction de filtrage de la

TFD par pond6ration des.6chantillons du signal avant transformation. X(k)

,, , ""-...

,

--

2

0

-

~

3

4

5

k

1 FIG. 2.10, Analyse d'un signal de frequem;e "/Jon multiple de NT

Cette operation revient a remplacer 1a fenetre temporelle rectangulaire. i.p(t), par une fanction dont la transformee de Fourier presente des ondula:tiolls plus faib les. De nombreuses fanotions sont utilisees, les plus- simples sont 1a cosinus~ol'de

surele.vee : 1 (.1 + cos ,,11: NT t )

(2.25)

etla fenetre dite de Hamming :


~)

(2.26)

Cette derniere fonction a 99,96 % de son energie dans Ie lobe principal et Ie lobe secondaire Ie plus important se trouve a environ 40 dB au-dessous du lobe principal. La reference [8] presente un ensemble de fonctions ayant des l'roprietes.

pour applioation aFanalyse, spectrale. Si cP (j) designe Ie spectre de la fonction fenetre

varfe~-es

,o

."••••

n)]if> (k -. - -u )du NT

11; m X (k) = Tlc [ S ( u-a T n~-m T

],

J

•o

(2,21)

o o

a l'echan-

]

Pou; mieux ma'itriser les interferences entre les compos antes spectrales calcuil fa1,lt faire appel a un bane de filtres plus ·stHectifs, camme celui Cl,1,li est presente au ch api tre 10. La"TFD peut etre utilisee d' une maniere indirecte ,dans la procednre de Galcul des cOllvolutions.

• .<e

Cette expression fait apparal\re Ie repliement de bande du sigmil dfi 8 tillonnage avec la periode T. ~

j

lees ~

72

2.5

2 • La transformation de Fourier discrete

LA CONVOLUTION RAPIDE

La pui~sance de caleul des _algorithmes de- Transformation de- Fourier Rapide conduit a utiliser la TFD dans des cas autres que I' analyse spectrale et en partieulier pour la realisation d'operatiQns de convolution. Bien que cette approche ne sait pas en generalla plus efficace, elle peut presenter de rinteret dans les applications au un calculaleur de TFR est dispanible, Parmi les proprietes de la TFD figure la propriete slilvante : la transformee d' un, produit de convolution est egale au produit des transforinees. Elant donne deux suites x (n ) et h (n) de. periode N et dont les transformees sont X (k) et H (k), la convo1ution circulaire : N-l

k

y(n ) ~

h(tn) x (n -m )

m=O

est une suite de meme periode dont la transformee ·s'ecrit: ~

Y(k)

H(k). X (k).

La convolution rapiqe consiste a calculer 1'a suite y (n) en effectuant:une tran'sformee de Fourier Discrete inverse ·sur la ·suite Y (k) . Comme en general un des terrnes de 1a convolution est constant l'operation demande une TFD. un produit et une TFD inverse. Celte technique ~: applique aux suites de duree finie; si x(n) et .h(n) sanldeux suites deNl el N2 termes non nuls, lasuite yen) definie par : .n

L

yen) '"'

rn= 0

h(m)x(n-m)

est une suite de duree finie, ayant N 1 + N2 - 1 termes ~. la convolution rap ide s'applique en considerant que les trois suites y (n), x (n) e1 h (n) ant la peri ode N tel que N '" N, + N z - 1 ; iJ suffit de completer par un nombre convenable de termes nuls. nest alors interessant de choisir pour N une puissance de deux. Cependant en pratique Poperation de convolution est une operation de filtrage, au les x (n) :representenl Ie signal et les hen) les coefficients. La suite des x (n) est beaueoup plus longue que la suite des h (n) et il faut [raelia nner Ie caleul. Dans ce but la suite des x(n) est consideree comme une superposition de suites 61emenlaires xk (n) de N, termes. C'est-a-dire que I'on a :

x (n) ~

Lk

xk(n ).

·aveoxk (n) ~ x (n) pour kN3 '" n ,;;; (k + l)N, -1 elx" en) ~ 0 ailleurs. Alors on peut ecrire : n

yen) ~

L m=O

y(n)~L k

h em)

L ok

xk(n -m)

.• h(m)xk(n-m) ~ L Yk(n)

L

m =0

k

2.6

73

Calcul d'une TFD par convolution

Chaque suite Yk(n) compte N, + N z -1 termes non nuls. Les convQlutions arealiser pOTtent sur N, T N z -1 termes. Le <\iagramme de 10 figure 2.11 montre l'enchalnement des operations; Ie. suites Yk(n) el Yk +i (n) ant N z - i termes qui se supeT·posen!. h(n] ... , --,-,N.!..2~ I

I

INJ

Xk (n) ... , --""1I=----f , I

Yk(n) ~k+1{n)

f

Nz+ N3-'

"'I--~~'~~~--r-----<

I

I

I

I

t

I

N,

1

l I

Yk1'1 (n)

,

,~

I

I

: N2 -1 y(·n)

I

I

~HH$$$$1

I

N2-11

~\H<$\\~

N 2 -1 ~$$$$\S\SI

FIG.2.11. Encj1afnement des opb:ations dans fa convolution rapide avec frac tionne!1l'ent

Dans ce processus Ie nombre de caleuls

a effectuer

par element de la suite

y (n) croit comme Logz (Nz + N3 - 1) e( il ne faut pas choisir N, (rop grand; si N3 < N z aucun terme de la suite y (n) nlest obtenu directement. Par suite il existe une valeur optimale pour N 3 . Le nombre de positions de memoires necessaire croft comme N3 + N2 + 1. Un bon compromis consiste a prendre pour N3. 1a premiere valeur superieure aN2 telle que N3 + N2 - l ·soit une puissance de deux.

2.6

CALCUL D'UNE TFD PAR CONVOLUTION

Dans cer.taines applications on ne dispose que d'operateurs cap abIes de faire des convollltions pour caleuler une TFD , C'est Ie cas des ,ircllits utilisant les dispositifs a transfert de charges qui permettent defair e des calculs, sallS forme analogique et sur des signaux echantillonnes, a des vitesses compatibles avec les frequences rencon trees dans. Ie dOlhaine des radars par exernple, La relation de definition de la TFD s' ~crit: 1 N-l nk X(k)~- L x(n)e-i""N N n=O En posant

2 • La transformation de Fourier discrete

74

il "ient : kl N-1

X(k)=W 'i convolution

cITculaire

IT'·

_(n_k) l

L x (n)w T w -zn='O

(2,28)

CeUe expression exprime Ie prpduit <;\~ des suites x(n)WT

n'

et W- T . rI g'en suit que Ie caleu! des X(k) peut etre effectue en trois etapes cornprenant les operations sllivantes : n1 ~

multiplication des donnees x (n) par les coefficients W 1:

- produit de convolution par la suite de coefficients W- 2 k'

- multiplication des resultats par les coefficients W T Le processus est represente sur la figure 2J2. Convoluti on par W- n212

Ca[clJ,l d'une TFD par convolution

FIG. 2.12.

Cette methode s'etend au cas au West un nombre c0IDplexe dont Ie module est different de l'unite [9]. Apres la presentation et l'application des' algprithrries' de TFR, cNtaiRs aspects de la realisation vant etre abordes.

2.7

REALISATION

Pour mettre en reuvre les algorithmes de calcul de la TID il faut disposer d' equipements comprenant les elements suivants : - unite de memoire pour stocker les donnees d'entree-sortie et les resultats intermediaires ; - unite de memoire. pour stocker les coeffi,cients de la transformee ; - unite arithmetique capable d' effectuer des additions· et multiplications portant sur des nombres.c.omplexes; - unite de commande pour enchainer le.s operations. Ces- elements de base se- retrouvent dans tQute machine destlnee au traitement nUl.l.lerique du signal, que ce soit en logique cab lee ou en logique programmee. Les particularites liees a. la mise en <;euvre de la TFR tiennent a deux caracteristiques principales : - 'Un volume- de calculs arithm6tiques important; - les permutations a effectuer sur les donnees qui conduisent d' indiGes Gompliques.

a des

calculs

2.7

Re'alisation

75

Les contraintes sont d'autanl plus grandes que l'ordre de la Transformee est 61eve, Le probleme de realisation qui se pose est celui d'une mise en ceuvre efficacedes a1gorithmes decrits dans 1es paragraphes precedents. V ne mise en reuvre efficace est celle qui conduit ·il un taux eleve d'uti1isatiofi des differentes unites de 1a machine et pattiouJierement l'unit6 arlthmetique, On peut itnaglner differents ageneements de circuits et modes d'organisation des caleu1s [10J et [11]. A titre d'exemp1e, un circuit simple pour realiser l'a1gorithme de 1a figure 2.4 est donne par la figure 2.13. Les donnees- x (n) se presentent en serle, la Transformee est d'orclre N = 8.

E

e,~

, , " " '"

- I X:3

' x, '

~,

, x,

I

'x 7

,

L

r-

.---J

e, eJ

."•• ],"

S,

I Xo

, x, , x, , x, > - -

5,

I ·x,

, x,

Fru."2.13.

' X, I X, > - - -

Realisation serie d'une TFR en base. 2

Le circuit comporte un registre M, de 4 donnees, deux registres M~ de 2 donnees et 2 registres M3 d'une donnee. Les dispositifs de commutation, commandes g p~r les signaux C1, C2 et C3 respectivement ,permettent un enehainement conve• nab1e des calcu1s. Les coefficients WP doivent etre appliques aux mu1tiplieurs ·au .<e 8 .§ moment approprie. La figm:e donne les signaux de commande et les signaux d'en-a tree et sertie. Le mu1tiplieur comp1exe est realise il l'aide d'un ensernb1e de mu1tipliems et additionneurs reels qui pour faire l"operation :

•c

1 o

"

2 • La transformation de Fourier discrete

76

effectuent les caleuls suiyants :

c;, ~ aRb R - aib, Cj

=

aR,.bi + aib R

II faut noter qu1il existe une autre possibilite qui c.onduit pour chaque multiplication complexe a:3 multiplications reelles au lieu de 4 et 5 additions au lieu de 2 :

taR + jai) (b R+ jbJ ~ [taR + aJ bR -

a;(b R + b;)] +j[(aR+ai)bR + aR (bi-bRl]

(2.29)

Et meme, si Ie nombre comple.xe bR + jb i est fixe , Ie nombre d'additions a faire se reduit a 3 pour dhaque multiplication. Si Ie debit de donnees est continu et que les calouls de TFR sont a faire sur des biocs de donnees adjacents, Ie rytbme de base des calculs est celui des donnees et l'on peut remarquer que les n'lulliplieuts sont ihactifs pendant la moilie du temps. 11 est possible de perfectlonner Ie circuit pour que les multiplieurs soient utilises a leur capacite maximale, en traitant des blocs de donnees conse-cutifs avec un rythme c\e base egal a la moitie de la cadence des donnees. L'exemple de realisation deerit cl-dessus appelle deux remarques : - Le circuit comprend trois etages de structure diffe-rente, avec des signaux de commande di'fferents; c'est un inconvenient car on 'recherche plutat le$ circuits modulaires, en particulier pour Fintegration agrande echelle. - Les resultats se presentent dans un orllie permute; it faut un traitement complemen'taire pOllr retrouver l'orel-re naturel des indice$. Quand un certain degre d'optimisation est recherche, plutot qu'adapter les circuits aux algorithmes, il est preferable de rechercher des algorithmes compatibles avec le$ contraintes qu'impose la technologie'aUX" circuits. D'autre paTt, en vue de reduire encore Ie volume des calculs arithmetiques, des algorithmes plus sophistiques que la TFR peuvent etre envisages, De plus si les donnees pre·sentent des:particularites, par exemple si ce sont des nombres reels, si des symetries apparaissent, des simplifications import antes peu:vent intervenir. Ces sujets sont abordes dans Ie chapitre suivant, a partir d~une representation unifiee des ·algorithmes de TFR.

77

Exercices

BIBLIOGRAPHIE FfT 'and

application~,

IEEE Transactions, Vol AU-iS, W 2, June

[1]

Specjal Issue orr 1967,

[2]

A. OPPENHEllJ ;Ind R . SeEiA.FER - Digital Signal Processing chapters 3 and 6, PrenticeHall, New Jersey, 1974,

[3]

L. RABINER and B, GOLD - Theory and Application of Digital Signal Processing, Ch-apten< 6 and 10, Prentice-Hall, New Jersey, 1975,

[4]

J.

LlFERM:AN - Theorie et Application de La Transfonnatlon de Fourle.r Rapide. Masson, Paris, 1977,

Ed-.

[5J P. DUHAMEL - <~ Un algorithme de TransfOlmation de Fourier Rapide a double base ,» , Annales des Telecom" Tome 40, N° 9-10, Sept,-Oct, 1985, pp, 481-494, [6]

D, T0FTI and H. HERSEY - Effects of FFT Coefficient Quantization on Bin Frequency Response, Proceedings'of IEEE, January 19?2,

[7] T RAN-THONQ and

BEDE Lru - Fixed Point FFT Error Analysis, IEEE Trans. ASSP, VoL 24, N° 6, December1976,

[8] J" MAX et Collaborateurs - Methodes et Techniques de Traitement du Signal et Application~ au;rMesure.s PhYsiques, Tome I, Editions Milsson, Paris, 1981. . [9]

'", R. RABINER, R. W, SOHAFER and C. M, RADER - The Chirp Z-Transform AJ gorithm, IEEE Trans" Vol. AU-17, June 1969,

[10]

H . L. GROGINSKY and G . A. WOR'£5! - A Pipeline Past Fourier Tmnsform, IEEE Trans, On Computers, C 19, Nov. 1970,

[11] E, GO LD and T. BIALh Y - Parallelism in Fast Fourier Transform Hardware, IEEE Trans, AU-21,:W 1, Feb, 1973,

EXERCICES ~ u

1 CalcuLer la Transfohliee de Fourier Discrete. de la suit e c'omportant N = 16 termes

5 tels que:

"••

x (0) ~xCI) ~x (2) ~ 'i("4) ~x(15) ~ 1

'. • ],

•c o c

et de Ia suite:

.<e

•

xeD)

8o

x(n)~6

"0

~

~

x (1) ~x(2) ~ x(~) ~ X(4) ~ 1

pour 5 "' n"'15

:;

Comparer les resu1tats obtenus. Bifectuer 1a Ttans.fonne~ inverse -Sl\I ces resultats:

-g 8"

2 E.tablirle diagramme de 'f'algorithme de TFR d'ordre 16 avec entrelacement temporel et entrelacement frequentie1. Quel est Ie nombre minimum de multiplications et additions hecessai'res?

~

@

2 • La transformation .de FoLirier discrete

78

4 Calculer1 ,en 'utilisant Ie programme donne err annex-e, 1a Transfonnee de Fourier Discrete de 1a suite eOrripottant N = 118 teffiles tels que .: x(Q) = ;,;(1) ~ x (2) = x (126) = x (117) = 1

x(n)=O pour 3 "" n ", 125 Comparer les resultats a ceux donnes par }'exerdce 1. 'La suite X (k) obtenue constitue une approximation du d6veioppement en .serie de Fourier d'-une suite d'impulsions. Rapprocher les re-suItats' obtenus avec les chiffres du tableau de l'annexe I du chapitre 1. Expliquer les differences. Comment evolue l'approximalion si N = 514 ?

4 Soit 4.re41iser llne TFD d'OTdTe 64 aVec l~ minimum d'operatiol1Smitlun6tiques. Evaluer le nornbre de multiplications et d'addltions necessaires avec les algorithmes en bas" 2, 4 et 8. 5 Soit a amilyser la puis-sanc;e du bruit de caleul produite dans une Transformee. d' ordre 32. Montrer, en utilisant les resuitats duoparagraphe 2.3, comment varient les n~sul­ tats sur les diffe-rentes sorties. Calculer la djstornon introduite par une limitation a 8 bits des coefficients.

a

6 Montter qlle chaqu~ sortie d'une 1FD ~ X(k), peut &tre obtenlle partir des entrees x (n) par uhe relation de r€currence. Evaluer Ie nombre de multiplication.s necessaire. 7 Soit arealiser une 1FD d'ordre 64 sur des donnees qui sont des nombres de 16 bits. Evahler la degradation du rapport signal abruit q~and on fait en cascade- une Transformee airecte et inverse, avec une maGhine.a 16bits.

a

a

8 La bande supposee occupee par un signal analyser s'etend de 0 10 kHz. La resolution specttaIe recherchee est de 1 Hz. Quelle longueur d'enregi..strement doit-on p telever pour faire 'line te11e analyse? Quelle capacit6 de memoire. faut-il pour stocker'les donnees supposees (3odees a,.-& bits? l)etenniner les earacteristiqhes d'un calculateur capable de realiser une te11e analy.se spectrale : capacite de memoire, cycle memoire, temps· d'addition et multiplication.

9

Cakuler la TFD de la suite x (n) definie par:

X(l1) = sin 2n

n

~5 +

3,

n 0,2 sin 2 n -5 6,

Pour ameIiorer l'an·a1yse on :p.tilise Il;s' fenetres

g (n)=V+-cos

2:J

avec

suivattt~s

0 ", n ""J5.

:

2.rrn

'g(n)=O,54 -0,46cDs 16 'g'(n)

=O,4~ -

(Hamming)

2M 41'1t 0,5 t os 16 + 0,08 CDS 16

(Blaknfim)

Comparerles resultats de cette analyse.

10 Det;lIirl; ge maniere getaillee Ie fonctionnement du circuit de la figure 2.13. Donner en p'arliculier la sUite des nombres qUi se presentent en sortie de chaque additiort.i1eur et

Exerdces

79

soustracte'ur. Montl'er que pour faire f0nctionner les multiplieurs a ieur pleine capacite, il fautinttoduire, Une memoi:(e d'enttee .slippJemei1taire ~ donner le,s .sig:Q:aux de comh1,ande dans ce cas.

11 Generaliser a la base 4 la r6:::ilisation serie donn6e au paragraphe 2.7. Donner It;!diagramme des temps detaille. Si la Transformee est d'ordre N = 64, si les donnees ont 16 bits et se pre's entent ala cadence de 8 kHz ~ si les coeffidents out 16 bits, e~..pr.imer la puissance de calr;::ul necyssaire I;t Ie volUn1e de memoire pour les donnees et 'les coefficients. Rapprocher ces resultats des caracteristiques d'un microprocesseur courant.

chapitre 3

Autres .a lgor,i thmes de ,c alcul rap ide de la TFR

Lesalgorithmes de calcul rapide de la Transformee de Fourier Discrete (TFD) sont bases sur une factorisation de la matrice- de ceUe Transformee. Cette factorisation est deja apparue dans les aigorithmes a entrelacement tempore! et frequentiel introduits dans Ie chapitre prec€dent et qui sortt des elements d'ljn en~emble d'algorithmes tres varies. Pour apprehender l'ensembie des algorithmes de caleul rapide et pouvojr ainsi exploiter au n'lleux les partiGqlarites· des signaux a traiter et les possibilites technologiques, il est neelossaire. de faire appe1 a un olitil mathematique bien adapte, Ie produit de Kronecker des matrices. En combinant ce produit avec le produit au 'sens habituel il est possible de decomposer simplement to ute matriee de TFD .

3.1

LE PRODUIT DE KRONECKER. DES MATRICES

Le produit de Kronecker est une operation du caleul tensariel ql!i constitue une generalisation de la multiplic.ation d'une ma!rice par un scalaire T1]. Etan! donne deux matrices A lot BRyant respeetivement metp lignes etn et q colbnnes, Ie produi! de Kronecker de A par B, note A ® S, est une nouvelle matrice amp lignes etnq eolannes, que lIon obtient en rempla~ant chaque 61ement b;j de 1a matriee B par Ie tabieau b;j A suivant : bjj a ll

bij a12.

···

bija1n

Ce produi! n 'es! generalement pas commutatif :

3.1

Le produit de Kronecker des matrices

'81

Par exemple, si la matrice Best telle que

Le produit de Kronecker de la matrice A par la mattice Best defin'i par :.

(3.1)

A

Ort peut remarquer en particuIier que Ie produit de Kronecker de Ia matrice unite de dimel]Si.on N, IN' paJ; la matrice uni\~ de dimemion M., 1M ~st egal ~)a .IDa tric;~ unite de dimensionMN:

(3.2) De meme Ie produit de Kronecker d'une matrice diagonale par une- autre matrice diagonaIe est encore une matriee diagonale.. Le produit de Kronecker se combine avec Ie praduit de matrices au sens- habituel, avec les proprietes suivantes, qui vont etre uti.lisees dans les prochains para.., graphes, pourvu que les dimensions soie nt compati\Jles : - Le produit de Kronecker d'un produit de, matrices par Ia matrice unite- est egal au produit des produits de Kronecker de chaquematrice par la matrice unite:

(ABC) ® I ~ (A ® I)(B ® [)(C ® I)

(3.3)

Un produit de produits Be Kronecker est egal aU produit de Kronecker des produits :

(A

B

® C)(D ® E

F)

~

(AD) ® (BE) ® (CF)

(3.4)

- L'inverse d 'un produit de Kronecker est eMI au pJ;oduit de Kronecker des lnverses :

(A @ B ® C)-'= A-' ® B-1

C-1

(3.5)

.'!:::i

§" L ~0peration de transposition a Ia meme propriete que Pinversion:

."••"

Br@ C'

(A @ B

(3 .6)

],

La matrice trans po see d'un pr.oduit de Kronecker esl le produit de Kronecker des matrices transposees . .~ Ces proprietes sont aisement mises en evidence sur des exemples simples; § e11es sont lltilisees pour Ia factorisation des matrices a elements redondants. et en particu!ier les matrices de la TFD [2]. L'entrelacement frequentiel est considere en premier lieu.

•

g

i

l

II faut noter que Ie [acle ur d'echelle n'est pas pris en compte dans' I. sui!.e de ce chapitre. N

3 • Autres algorithmes de (alcul rapide de la TFR

82

3.2

FACTORISATION DE LA MATRICE DE L'ALGORITHME D'ENTRELACEMENT FREQUENTIEL

Dans les algorithmes ex amines au chapitre precedent, l'une des suites, en entree ou en sortie, se trouve permutee; ia matrice qui fepresente eet ·algorithme est une matrice qui se deduit de 'la matrice TN par permutation des lignes:Oll des Golonnes

suivant que l'on considere l'entrelacement frequentiel au temporel [3]. Designons par T~ la matrice qui correspcmd a l'entrelacement frequentie1 et est obtenue par permutation des !ignes de la matrice TN definie par la regie suivante : chaque ligne est nurnerotee en binaire; on inverse }'ordre des- chiffres de ce nonlbre binaire; la valeur du nombre binaire ainsi abtenu indique Ie numero de la ligne dans la nouvelle matrice.. Par exemple pour N ~ 8 il v.ient :

Ts: ~

1

1 1 1 1

W wz W' -1 -W _Wz -W'

1

1 1

1

T~=

-1

1 1 1 1 1 1 1 1

-1

wz -W ~

W -W

W' -W'

1 w~

-1 -W~

1 wz -1 _W2

1 W3 _wz

W -1

-W' W2 -W

1 1 -1

1 -1 _wz W2 -1 wz W' W2 -W' _W2 W _W2 -W

1

-1 1 -1 1 -1 1

-1 1 1 1 1 -1 -1 -1 -1

1 -w wz -W'

1 1 -Wl -W' _wz -1 2 -W W

1 -1 wz. -wz -W W -W' W'

o· ~

0

OiO~2

o 11~3

1

lOO~4 -1 W' 101~5 W2 11 O~ 6 111~7 W

1 1 -1

O .oO~O.

-1

W -wz W'

on

001~1

_W2 -1 Wl

1 -1 _wz wz -1 _ w z -W' _W2 W' Wl -W Wl W

100~4

01n~2

11 O~ 6 o 0 1~ 1 101~5 Oll~3 111~7

On peut remarquer que pour N ~ 2, la matrice T~ est egale a Tz,. matrice de la TransfoTmee d'ordre 2. La matrice T~ se factorise en faisant appaT31tte la matrice TN et 1a matrice

diagonale

2:

D N

dont les elements sont les nombres Wk avec 0. .;,; k

2 N

TN=

[T 2

TifDli 2 2

T i1 -LD' 2·

2.

oS

N -1. En effet: 2

3.1

83

Ualgorithme d'entrelacement fnEquentiel

Cette decomposition apparait cl(limmtml pour T~ par exempJe. Si IN designe la matrice uni te d'ordre

~

2

11 vient :

T'

Tf.r=. [

o

~

au enc.ore :

T' 0

TN=

~

[

En utilisant les produits de Kro.necker des matrices, on obtient pour T.~:

(3.7)

TN= (T;" 2

ou

~N est une matrice carn~e d'ordre N

diagonale, dont 1es. N premiers elements 2

valent 1 et Ies suivants:sontles puissances de W, W k avec 0

~ k~

N -1 . 2

Par iteration on obtient la factorisation complete- :

("'·N 0 I:,)(IN ® T; to 12) 2

..

"'N(IN ®T~)

,-

ou encore ; L%N

."••••

T,,=

I j=l

],

("'2 ' ® IN )(12,., 2'

T z ® IN)

(3.8)

2'

Celte expression montre que Ia transformee se caleule en Logz(N) etapes qui cha· •c cune comprennent: o c - line partie d'arra-ngetnent des donnees' cQrrespondant au facteU'r • .0S o (10,·, ® T z ® IN ) et qui ne comprend que des additions et soustractions, '0

~

~

1 o

@

2< - une partie comprenant les multiplications par les coefficients representes dans Ia matrice (4 2' ® IN )· 2'

3 • Autres algorithmes de (alcul rapide de la TFR

84

L 'etape cmrespondant a i ~ 1 ne comprend pas de mUltiplications. On peut vexifier que totttes 1es matrices ont bien la dimension N. Pour voir comment 1a factorisation se generalise a 1a base 4, il est interessant d~ examiner 1a matrice T~6' obtenue a partir de la-matrice T16 par-Ia permutation suivante des lignes : les !ignes_sont nurnerotees en base 4 ; on inverse l'brqre des chiffres dans les numeros de ligne; la valeur obtenue indique Ie numero de la ligne dans 1a nouvelle matrice. Suivant cette permutation on a ~ T4 = T 4Avec les notationSsuivantes :

Dj= I

1 a a W' Q a 0 a

a

a

(I

0

a

W"

a

W 3i

la rn:atrice de la transformee d'ordre 16 ainsi obtenue s\~crit :

T{6=

T{6=

T4-

a

a

0. 0.

T4

0.

0

0. 0.

T. T tDJ

T4 Tt(-j)Dl

T4D~

T4D~

T, 0

0.

a 0

T,

T4 T4 (-l) Dl

T4 Tt (+ j) Dl

T4(-1 ) D ~

T4l)~

T4 (-1)D ~

T4(+J ) D ~

T4 (-l )Dl

T4 (- J )Dl

14 0.

0. 0.

0.

a

a

D~

0.

0

Q

D 24

a

0.

0.

D'4 14-

SOllS

r.

T4

- J I4

It 14-

+ }14-

-T4

14 - 14 ,]4 - 14

14

+i I4 -14 - ) 14

forme de produits de Kronecker cette expression s'ecrit : T;6 ~ (T4. I8l 14)"',6(14

0 T 4)

(3.9)

est une matrice diagollale dont les 4 premiers termes ont pour valeur L les 4 su\vants W k avec 0 os; k os; 3, ies suivants (W 2) k et (W ')k avec 9 '" k os; 3. La factorisation en produits de Kronecker est a la h ase d' algorithmes ayant des propriHes variees, notamment sur l'ordre de presentation et d'extraction des donnees etrenehainement des o perations. E lle s'app lique aussi !tux transformees partielles qui ont une grande importance pratique.

Alp

3.3

LES TRANSFORMEES PARTIELLES

Les transformees qui ont " e te etudiees dans les paragraphes precedents portent sur des ensembles de N nombres q ui peuvent etre complexes. Dans une an alyse

3.3

Les

tran~formees

85

partielles

spectrale fine it se peut que I'ordre de la transformee N devienne tres grand alars que seuls ~ont interessants a connaitre un nombre reduit de points 911 spectre.. La limitation du calcul aux seuls points utiles peut alors permettre- une. ecorromi"e imp,ortante. Soit a calculer la transform€e partielle d6finie par l'equation suivante Ott rest un diviseur de N : WP

W1J>

W(N-l)P

Xp+l

1 1

WP'+i

W 2(P+l)

W (N-l)(P+l)

Xp+ 3

1

W

W2(P+ 2)

W (N ~ I)(P+ 2J

1

W (E +·r - l )

........

W (N-l )

Xp

Xp H

-1

P -f2

A partin de l' ensemble des dO)1nees, on forme

N

~P H -l)

Xo X, ,t 2

(3.10)

X'N -1

sous ensembles de r terrrles

r

chacun: (Xo, xN ,x 2N,

,

X C,-I)NJ

,

x(r _l)N

)

--+1

(XN

,

--1

'X 3N

,

-1

Sbi~ Dj la matrice diagoh·ale de dimension .. et dont les elemenfs de la diagonale sent les puissances de Wi, soit Wik, avec 0 ~ k ::-:; r -1.

La matrice de la transformee partielle peut etre s'eparee en N salis-matrices r qui s'appliquent chacune a l' une des suites definies precedemment et I'equation matricielle de la transformee s'ecrit : ~-1

,o

,

." "••

N

[xlpfLo DiT,(WP) ; D~7 [x] ;, r

(3.11)

,~

]

~

.i 8 o

au [xlp,,, designe l'ensemble de r nambres X k avecc p l'ensemble des donnees

Xk

avec k

=

<s k '" P +

r - 1 et [x1,,,

n. .. N + i et fl = 0, 1, . __ . r - 1. D ' autre part Tr r .

:;

est la transformee d' ordre r. Par suite si r est un diviseur de N une transf.ormee partielle pOI.tant sur ,r

~.

points se caicule

"0

~

5

o

,@"

des,matric~s

a l'ai,de de

N transforrnees tfordre r auxquelles sont associees r diagonales convenables.

3 • Autres algorithmes de (alcul rapide de la TFR

86

si N el r $cmt des puissances de 2, ie nombre de multiplications complexes effectuerMp s'exprime par:

a

(3.12) Par Tapport i\ 1a transformee glob ale, i1 apparait ainsi que 1a transformee partielle est avantageuse pour N > 16r, done pour 1es faib1es nombres de points a ca1culer. Ce resu1tat est egalement val able lorsque c'es! Ie nombre de points a transformer qui est limite, ce qui est aussi un cas frequent en analyse de spectre. Un exemple courant de transformee partielle est celle qui porte sur des donnees reelles.

3.3 ..1 Transformee de nombres reels et TFD impaire

atransformer sont n~e1s, les prQprletes enoncees au ehapitre 2 indiquent que les nomb res transformes X(k) et X(N ~ k) sont complexes conjugues, c'est-a-dire que X (k) ~ X(N ~ k); alors il suffit de ca!culer I'ensemble des X k

Si le;5 nombres

avec 0 ·"" k ""

~ ~ 1 e( Ie resultat precedent s'applique :

[X1o I'l ~ T I'l [x10 I'l + J) I'lT I'l [x1, I'l ~2

2

' 2

2

2

(3.13)

'2

Dans ce cas precis il est ppssible de n'effecluer qul·une seule fois Ie calc.ul de la transformee TN ' en tenant compte de la propriBi6 suivante de la Transformee de 2

Fourier D1screte; si la suite tTanSformee est telle qU,e :

a transformer

xi< est purement i maginaire, la suite

X(k)~~X(N~k)

Dans ces conditions 1a procedure- po ur Ie calcul de· la tran:?formee dlune ~uite reelle est la s-uivante :

~

Former a partir desx(k) unesuite comp.1exe de

Y (k) ~x (2k)

termes

N 2 ~ 1.

~

Calcu1er la transformee Y (k) de la suite y (k) 'avec 0 "" k ""

~

Calculer les nombres cherches Par l't;xpression:

X(k)~

avec

* jx(2k + 1) avec 0 "" " ""

~

1 )] + 21je 2, [Y(k)+ - (N Y . 2'~k

Nee Y (N) a "" k os 2' Z ~ Y (0).

-jz,o "l" [Y

(N)

2 ~k ~ Y(k)

J

~ ~ 1. (3:.14)

3.3

87

Les transformees partielles

En regroupant les facteurs on peut ecrire so us' une autre forme:

X(k) avec A (k) ~

1

2

~ A(k) Y (k) + B (k) Y ( ~ -

(1 - JWk) el B (k) ~

La !ransformeeinverse s:obtien! en calculant:

1

2

(1 + JWk).

a partir des N" 1 termes X(k) <'lVeC 0 '" k '" ~ ,

Y(k)~ A (k) X(k) + B(k)X(~ pour 0 "'- k "'-

~

-k)

-1, puis en ca!culanl la TFD inverse d'o:rdre

enfin en prenant les parties

n~elles

(315)

k)

(3.16)

~

deces valeurs et

de l'ensemble Dbtenu comme donnees d'indices

impairs et les parties imaginaires c,o mmes donnees d? indices~ pa,irs. Si Nest une puissance de 2, Ie nombre de multiplications complexes M e effectuer s!eh~-ve a :

a

(3 .17) Le nomhre de memoires necessaire est de N positions reelles. La reference [4] decrit en detail un algorithme de ca!cul pour donnees reelles. Une autre methQde pour calculer le~ transformees de nombres reels con-siste a faire appel aux transformees impaires [5]. La Transformee de Fourier Discrete impairet6tablit par definition les relations suivantes entre deux ensembles de N nombres complexes x (n) et X (k) : 1

X(k)~-

N

x(n) ~

N-l

L

~ '21T £2k+ l)n 2N

N-l

~

n ~O

x(n )e " .

(3 .18)

(2x+l)n

X(k)eI2~~

k~O

.;ijj

§ ]I

.~

],

•c

Les coefficients de cette transformee ont pour -affixe les points M du cerole unite tels que Ie vecteur C5M fas's e avec Paxe des abscisses un angle multiple impair de

2"

'2N comme Ie montre la figure 3.11m

o c

• '''8o

"0

~

~

• -g ~

,.

o

@

FIG, 3.1.

Coefficients, de fa TFD impaire

3 • Autres algorithmes de (alcul rapide de la TFR

88

IT

En posant W ~ e-i N la matrice de cette transformee s'ecrit :

Tk ~

1 1 1

W

W2

W'

W 6

W3 (N-I)

W5

WIO

W 5 (N-1)

1

W(2N- 1)

.... .. ...

W (2N-Ij (N-1)

Si les x (n) so nt des nombres recis, on peut ecrire : 1 N'- 1 2 (N -

X(N-l-k)~N ~

1 N

I.

n~O

x (n) e-i '"

N-l

'<'

~

-

x (n) e

WN - J

1 - k) +1 2N

(},19)

2k+l

i'he - - n 2N

n""O

D 'ou Ie Tesultat suivanl : X(N-l-k)~X(k)

(3,20)

Pm; suite les X (k) d'indice pair et d' indice impair sont complexes conjugues; il suffit donc de calcUle r les X (k) d' ihdice pair pour faire une transfor mee sur des n,els, Une telle transformee correspond ala matrice,T R t elle que: N

1

W

W2

1

W5

W-:;

1

W2N - 3

WN - l

5N

"' , ',"'"

(2N -3)N W - 2-

W5(N-1)

W(2N -3) (N-I)

Soh D N la matrice diagonale dont les e lements de la diagonale sont les W k avec 2

o ,,;; k oS

~

-1 et T ~ la matrice de la transformee d' ordr.e

~ , Compte tenu du fall

N

que W

2N ~

1, et W:1

~

- j , il vient :

(3,2l) AlDIS la i ransformee impaire sur des nombres reels se calcule en effectuant une tTansformee d'ordre

~

slir la suite des nomb res'complexes

y (n) ~ [x(n) -jx(~ +n)] Wn

avec noSh""

~ -1,

(3,22)

3.3

Les tran~formees partielles

89

Le rlombre de caleuls est Ie meme que dans la methode indiquee au debut du paragraphe, mais la structure est pl!!s simple. Il faut noter cepenc\ant q!!e les nombres transformes donnent nn echantil10nnage du spectre du signal que represente les -"(n), dec ale d'nn demi-pas d'echantillonnage en frequence. Un cas important oil des simplifications notables interviennent est cel!!i des. suites reelles symetriques. Les reductions de ealcul sont mises en e.vidence par utilisation de 1a transformee doublement impaire [6].

3.3.2

La Tr.ansformee doublement impaire

La. Tran,sformee de Fourier Discrete doublement"Imp'a ire etab lit par definition les relations suivantes entre deux ensembles de N nombres complexes .• (n) et X (k) , , -L

N-I. ~

)

X(k ) ~ N nL: x(n e o

L

k
(2k+ 1)(2n +1)


(3 .23)

' 2 (2k+ J)(2n +1)

N -I

x(n )~

-,2Jr

X (k) e' n

4N

(3.24 )

Les coefficients de cette transformee ont pour affixe les points M du cerele unite tels que Ie vecteur OM fasse "£lvec l' axe des abscisses un angle multiple impair de 2/t - comme Ie montre 1a figure 3.2.

4N

FIG. 3.2.

Coefficients de' fa: TFD doublement impain!'

."•••• ~

•c o c

•

Si les X (n) s'o nt des nombres reels o n veri fie la relation , X (N-l -k)~-X(k)

'1C

g

'0

~

~

•

De meme si les X (k) sont reels alors :

x(N -l-n) ~-x (n)

~

]

§

o

@

n

En posant comme preeeciemment W = e -i N la matriee de Ja transformee slecrit:

3 • Autres algorithmes de (alcul rapide de la TFR

9()

1

5

Wz

W I,

3

Wz Tl!

~

W3("-~)

15

9

We

5

Wz

N- ~

W 2

We 25

15

We

W5 (N-})

We

(3.25)

WN-~ W3(N-~) Vne·rene transforme e se factorise comme suit :

1 W eb

1 W'

W'

W8

W2(N-l)

::t:~:; 1 W2(N-1; (N - 1)

Ll C'~st-a.-dire que

: 1

Tl!~W 3 DNTNDN

(3 .26)

Considerons Ie cas ou la suite des donnees ,y-(n) est une suite n~elle et antisym,e trique, c'est-a-dire quex(n) ~ - x(N -1 - n) ; alars il en est de meme de la suite X (k ). La suite des x(n ) pour n pair est egale a la suite des x (n) pour n impair au signe pres ; de meme POljf la suite des X (k ). Pour calculer la transformee il suffit dans ce cas de mener les calcu ls sur les x (2n ) avec 0 "" n ""

i-

1 puisque les X (k) sont des n,ombres reels ; d 'autr.e

suffit de faire ces calculs sur les X (2k) avec Q '" k "" La matrice correspond ante T RR s' ecrit ~

1

TRR ~ Wz

[' 0. 0

0 W2 0

0 0

i-

1.

p ~rt il

Les tran~formees partielles

3.3

91

1

1

1

1

1 1

W2 W'6

1

W8(~-1) W8(~ -1) (~-1)

'0

0

W8(~ -1 )

a o

0

Compte tenu du fait que W2N = 1, il went '

T '"4

1 TRR =

W 2: DN

T"-] 4

DN

(3,27)

[ TN T~2'

2

4 N

Et cOIiulle W 2,.- = - jee c,aleul peut etre conduit en ll'effectuant qu' une seule fois les operations· representees par 1a matrice TN sur Fensemble de nombres 4

(

x(2n) - jx 2n

N)

+:2

avec 0 '" n '"

4N-1,

Les

4Nnombres

obtenus sont des

nombres complexes dont les parties reeHes constituent l'ensemble des X (2k) avec

o ""

k '"

~

- 1 recherch€es', En effectuant l' operation definie par T RR pour

nombres transformes de rang 2k +

~

avec

0 "" k

'"

~

le~

- 1, on peut verifier que

Pon obtient les nonibres precedents multiplies par - j; c1est-a-dire que 1a partie ima-

ginaire des nombres obtenus precedemment, fournit l'ensemble des X(2k +

~ ~

,o

"••

'.

,'en suit que la transformee doublement impaire app'liquee a une suite de N termes, teelle antisymetrique, au a une suite symetrique rendue antisymetrique par un changement de signe convenable, se roouit al'equation :

[X

(2k)

+ jX( 2k + ~)] = W~D" T"D,,:[X(2n) 4

],"

•

o o c

•

S o

N

elements spnt les W·2j avec ,b ~ l ~ -

4

~

~

4

jX( 2n + ~)]

4

(3,28)

'

avec 0 '" k ,'" N - i 0 '" n "" N - 1 et ou D est line mat rice diagonale dontles , 4' 4 ~

'D-

]

~), 11

- L.

Ly nombre tie multipliGations complexes necessa'ire Me Me =

s~eleve

Nlog 2 (N) 8 * 2 4N 8Nlog 2 (2N)

8

=

a: (3,29)

3 • Autres algorithmes de (alcul rapide de la TFR

92

Les comparaisons de volume de calculs entre les differentes transfo rmees conduisent au tableau 3.1 :

Tableau 3.1- Q >JANrrrEs DE ·CAr;CULS DANS-DNERsES TFR. mllltipliq~tions ~6mpl~~ ~s

Md\tiOus

qe..m~mo.ira

N log, 0N)

2N

TID complexe

~ log, (~)

TED impaire.-donnees reelles

Tlog, (N)

N 2 log,

TID doublement impairedonnees d:elles paires

N s log2(2N)

N . (N) T log, 4

N

Pos\ti'6ns

cQrnplex e.!]

C~ 2)

N N 2

-

L'interel des transformees imp aires apparai t olairement. Jl faul c,,;pendant noter que d'autres algorithmes pe rmettent d'obtenir avec les donnees reelles et reelles symetriques des reductions encalcul un peu superieures ['7], mais sans aVoir la facilite de mise en ceuvre, en particulier pOlir les realisations rrrarerlelles·, qu~of­ frent les transformees impaires. Une particularite Be la transform6e do\!blement impaire appliqlJee Ii line sllite reelle antisymetrfque est qu~ elle est identique a la transformee inverse; il n1y a pasde distinction, mis

a part

l'e facteur d'echelle

~,

entre transfo rmees directe et

inverse dans ce cas. La transformee de Fourier d'une s1.:lite reelle symetrique intervient par exemple dans Ie cakul de la deLlsite spectrale i\nerg6tique d'un signal a partir de la fonetion d'autocorrelation.

3.3.3

les Transformees discretes en cosinus et sinus

Les transformees considerees jusqu'a present a nt des coeffidents complexes. Des transformeeS' discretes de la meme famille peuvent etre obtenues partir des parties n~,.e lles et imaginaires des coefficients comp lexes. On peut ainsi d6finir :

a

• Uue transformee de Fourier Discrete en cosinus (TFD-cos) : 1 N

XFd k)~-

) L x (n) cos (2rt!lk --

N-! . ~o

N

(~.30 )

,. Une transformee de Fourier Discrete en sinus (TFD-sin) :

1

X.FS (k) ~ N

n;o x (n) sin (2rt!lk) -N

N-!

(3.'3 1)

3.3

93

Les transformees partielles

• Une transformee en cosinus discrete (TeD) :

XCD(O) ~

Vi

N-I

N 'n~O x (n)

()

(21t(2n+l)k) X CD (k) -- N2 N~' /::'0 x n cos 4N

(3.32)

alaquelle correspond 1a transformee inverse: 1

.

x(n)= ,rXCD(O)+ y2

N-1

L

k~l

XCD(k)cos

(21t(2n + l )k) 4N

• U ne transformee en sinus.discrete (TSD) :

(k) =

X SD

~

i,'

2 N x (n) sin ( 21t (n + 1) (k + 1) ) N + 1 n~O 2N + 2

(3.33)

A l' aide de manipUlations comparables ~ celles des donnees dans les paragraphes precedents, on peut etablir des relations entre la TFD et ces diverses transformees ainsi qu'entre ces transformees elles-memes. Par yxemple, d'apres les definitions, il vient : TFD (N) ~ TFD-cos (N) - j TFD-sin eN) Considerant la transformee en cosinus, il vient : N/2-1

XFd k) ~ n~o x (2n)cos

(21tnk) N/4-1 N/2 + n~o [x (2n+l ) +x (N -2n-l )J cos (

21t(2n +'l)k) 4.N/4

c'est-a-dire que la transformee en c.osinus d'ordre N peut 's e calculer a l'aide d?urte transformee en cosinus d'ordre ;~

TFD-cos (N) ~ TFD-cos (~) + T CD

• XCD(k)~ ~ •

N

Nt' [x (2n ) cos 21t(4n+l)k 4N n=O

'<e

?

8o

+x ('~n.+

"0

~

~

~

(~)

De memela transformee en cosinus discrete (TeD) -~'eGrit :

],

g

et d'une transfonnee discrete d'ordre N /4, soit

sous.forme concise :

]

• ·m

~

c'est-a-dire

qu~ e.n

posant, pour 0 ~ fl.~N/2 -1 :

yen ) ~x(2n) yeN -n-l) ~x(2n + 1)

1)

cos

21t[4(N-n-l)+1]k 4N

3 • Autres algorithmes de (alcul rapide de la TFR

94

il vlent;

·X . (k) _ 2 L CD - N

N~l ( ) 2rr(4n + i )k ~ y n Gas 4" n=O 1,

et en develappant Ie cosinus :

TCD (N) ~ GaS

!~ TFD-GOS (N) - sin ~~ TFD-sin (N)

ce'qui s'ecrit egalement, en fauction des donnees et sous une forme concise :

TCD(x) ~ 2e(k) Re {e- i ,(O)~

-aveC-

;~ ·TFD (y)}

(:>.34 )

1

V2 el9(k)~1pourk~1, ... , N-1.

Atnsi, 1a transformee en COSlnUS discrete d'ordre N peut se calculer a l'aide d'Ll:ne transformee de Fourier discrete de meme Drdre. Compte tenu du fait que seule la: partie n~elle est utilisee dans Fexpression ci-dessus', on peut meme calculer 2TOD, en utilisant egalement la partie imaginaire. La meme methode s'applique a la transformeeinverse et on peut calculer 2TCD inverses avec une TFD inverse, en effeGtuant les operations indiquees it laiigtlre 3.3. Les relations enlre les varia bles :

FIG. 3.3

Calcul de 2 TeD inverses avec u.ne TFD inverse de m({me dimension

it I' entree de la TFD inverse sonl les suiv.nles [8J :

.

So~

Co(xr) + 100 (X2 )

v'2

2 Sk

; SNfl ~

~/2 (Xl ) + j CNfl (X2)

~ {[Ck(X , ) + ~ _ k(x2 lJ GOS ( ;~ ) + [~~ k(Xl) ~ ~~ k(X2)l sin ( ;~ )} + j {[Ck(X1) +

·avee k

~

V2

~-k(Xo)l sin (;~ }r [Ck(x2l - ~-k(Xl)J cos (:)

1, .. " N -1 ; k;., N/2.

De meme en sortie de la TFD inverse,:

-t, (2p) = Re (s(P )) ; X, (2p + 1) = Re [seN - p - 1)); x2(2p) ~ 1m [s(P)); x 2 (2p + 1) = 1m [s(N - p -1 ))

3.3

95

Les transformees partlelles

La methode permet de reduire la quantite de caleuls en compression d'images, par exemple, Parmi les transformees a coefficients reels, on peut aussj mentionner la transformee, dite de Hartley discrete (TOO), definie jOar' : 1

XHD(k) ~ N

n~O x(n)

N-1

[

cos 21t

k

k]

~ + sin 21t ~

(335)

et pour 1a transformee inverse :

x(n )=

N-1

L

k~O

[ nk nk] XHD(k) cos21t-tsin21t-

N

N

La liaison avec la TFD est donnee par [9] : 1 . X (k) = 2: [XHD(k) +XHD (N ~ l-k)~}(XHD(k)-XHD (N -l-k))]

(3.36)

La transformee en cosinltS cliscrete est utilisee en compression de l'informatique, notamment en tr.aitement d1images. En effet, elle fournit pour les ·signaux d'images une approximation de la transformation propre, qui permet de representer un.signal par Ie minimum de cornposantes. Ce pouvoir de compression provient du fait qu'elle elimine les discontinuites de bord de la TFD mentionnees au paragraphe 2.1, car elle correspond a I. TFD d'une suite symetrisee. Pour pouvoir effectuer cette symetrisation avant d'.appliquer la TFD, 'il faut eviter d1avoir une valeur a l'indice zero, c.e qui est obtenu en prenont la suite u (n) telle gue: u(2p)~O

; O<>p<>2N-l

"(2pt1) =u (4N-2p ~ 1 ) =x(P)

; O<>p<>N-l

La TFD d' ordre 4N de la suite u;(n ) conduit, apres simplifications, a'l'expressibn (3.32) .

3.3.4 La transformee en cosinus discrete a 2 dimensions .:ijj ~

,

La tr.ansformee en cosinus discrete a deux dimensions (TCD-2D ) est definie, pour un ensemble de N X N donnees reelles, par les equations:

."••••

2 4e(k~: C~) :~: ~t>(n"n2)

X('s,k )=

],

•c

21t(2n1 + l )k,

o

cos

c

•

4N

cos

21t(m, + 1) k2 4N

(3.37)

'1C

8 -§ ~

~

3

et: N -1

x (n1, n,) = L

kl =0

N -1

~ E('s) e(k,) X (k ~)

k;~O

"

cos

.(21t ('Zn1 +1)k1 ) 4N

cos

(21t(2fl;;+ 1)k,) 4N

3 • Autres algorithmes de (alcul rapide de la TFR'

96 aveC :

1

e(k)~;fi

pour

k~O

e (k) ~ 1

pour

k,* Q,

Cette trans-formee est separable et peut erre calculee de la maruere suivante :

L-)~"I (k) N~' X (' k:l"/}2 N e" 2 kJ

n,~O

COS

21t(2n2+1)1<:, 4N

Ainsi la lransformee a deux dimensions 5e caleule en utilisant 2N fois l'algorithme corresponciant it 1a trahsformee TeD it Une dimenSion et Ie nombre de multiplications [eelles it effectuer est de lCordrede N"log 2 (N) , En 'fait, celte valeur peut etre aheinte, notammen! en faisant appcl a un algorithme base sur la reduction d1llne TCD d'ordre N it deux TCD d'ordre la valeur

!

~

[10]. Il est meme possible d'atteindre

N2 log 2 (N) en h'utilisant pas la propriete. de separatibilite de la TCD-2D

mais. en etendant

a. deux dimensions le p.rincipe d'entr.elacement par

tion de, l'ensemble des N x N donnees en ensembles de Appliguee

a uhe

~x~

decomposi-

donnees [11].

image, la TCD-2D fait apparaitre les frequences spatiales.

Par exemp1e, pour une ligne vertic ale d6finie par: x(n"n,)~

1

N;

n,~Q

x (n"n2) ~ 0; n, '" 0 les valeurs transformees X(k" 1<:,) s'annulent pour k2 ,. O. On verifie egalement qu)une diagonale constante est transformee en une diagonale constante 1 la' matrice unite est un element propre de 1a tran$formation.

3.4 TRANSFORMEE AVEC RECOUVREMENT La fonction de filhage de la TFD peut etre al)1elioree en considerant des tmnsformees effectuees sur des blocs de donnees qui se reoouvrent [12]. Soit un bloc de donnees de longueur 2M, double de l'ordre M de la transformee. Au temps n, Ie bloc de donnees traitees est represente par un ensemble de 2 ve<;teurs a M elements designes par Xln) et X2(n) comme Ie montre la figure 3.4.

3.4

Transformee avec recouvrement

97

temps n + 1

•X

X,(n + I)

Xj(n) ,

2(n

•

+ I)

X 2(n)

.

,

temps n fig. 3.4.

Recouvrentent des blocs d£. donnees

Au temps (n + 1), Ie bloc de donnees com porte la moitie des donnees du bloc precedent, c'est-a-dire que X,(n + 1) ~ X,(n). La ttartsformee avec recouvrement permet de restituer les vedteurs. Xln) et X 2(n). Sa matrice comporte 2M !ignes et M colonnes et elle correspond aux operations suivantes, sur deux blocs consecutifs ~

(3.38)

el

0\1. A 'et B sont deux matrices carrees:de cote M. S'j ron considere main tenant

les operations:

[N]U". [ Yl(n+l) ]~[A' l u (n 1) B'

Yl (n) ] ~ [ Y2(n) B'

Y2

+

(3.39)

2

on obttent: 1

Z:[Y2(n) + Y , (n+ 1)]

~ [B'AX,(n) +B'BX2(n) + A'AX., (n + 1) + NBX2(n + 1)]~ 5

l c

"0

'li

•

Pour retwuver les ,"onnees d'origine

X 2(n)

a la

fin du temps (n

(3.40)

+ I),

G'est~a"dire

~ ~ [Y2 (n) + Ylen + 1)], U faut que les conditions suivantes soient veTifiees: B'A~

NB ~ 0

~

,.

1i o

@

~2 [B'B' + NA] ~ I M

(3.4n

3 • Autres algorithmes de (alcul rapide de la TFR

98

Par exemple, ce-s conditIons sont verifiees si les elements de la matrice' LA, BJ de la transform6e sont tels que:

iT

ani( =h(n)\j 1).1 c6.

[(n + M 1) M1t ] , - 2+ - 1)('k + '2

o ,; n ,; 2M -1 ;

avec

h{n)

0 ,; Ie,; M - 1 et

~- sin (n + ~)--"2 2M

E n fait, on a obtenu un bane de M filtres orthQgonaux et les termes h(n ), sont les coefficients du filtre prototype qui, dans l'exemple est un fillre passe-bas en sinus dont la re-ponse en frequence donnee a,u paragraphe 5.8, est plus selective que celie du filtre de 1a TFD, En compression d'image, les transformees avec reCQuvtement prodl1isent un lissage et permettent de reduire les effets dits de hlocage, l

3.5

AUTRES ALGORITHMES DE CALCUL RAPIDE

Les algorithmes de TFR constituent une technique pour calculer une TFD d'ordre N avec un nombre de multiplications de l'ordre de N log 2(N), Dans les paragraphes precedents, il 'a ete montre que ce.s algorithmes ont une structure relativement simple et offrent suffisamment de souplesse pour qu'une bonne adaptation aux contraintes d'exploitation et aUx caracteTistiques technologiques puisse etre ,a'isement atteinte, \i'pu leur grand interet pratique, Cependant ils ne constituent pas la seule methode de calcul rapide de la TFD et l'o n peut elaborer des algorithmes qui necessitent, tout au moins tialls certains cas, un temps de 'calcul tnoindre ou Un no.mbre de rnultip1ications plus f~ible, au qui sont applicables quel que so it Fordre Net pas obligatoirement une, puissance de deux, ' Une premiere approche cons~te a remplacer les multipIications cotnplexe$', coCiteuses en circuits ou en temps de machine, par un ens,emble d'Qperations plus faciles a mettre en' ceuvre. La reference [13J decrit une technique qui utilise une caracteristique de la TFD mentionnee au paragraphe 2.4.1, Ie fait gue Ies operations de multiplication par les coefficients W k, correspondent a des rotations de phase, La technique dlte CORDIC (caleu! numerique a rotation des coordonnees) permet de realiser ces rotations par un enchalnement d'op6ratiorts simple$ : pour faire tourner un vecteur (x,

y)

d'un angle 8 avec la precision 28n ' on opere une

suite de n rotations 61ementaires d1angles d8 j et -

t~ls

que tg d8 i -= 2- i avec 0 ~ i ~.n

-1

~ ~ 8 ::-:-; ~. Les coo.rdonnees Xi et Yi du vecteur a l iteration i cong.uisent aux

coordonnees

1

a1'iteration i + 1 par les relations :

3.5

99

Autres algorithmes de ca/Cul rapide

Xi + 1

= Xi + signe [8J .yj 2,-i

y, + 1 ~ y, - signe [e,].x,2-'·

(3.42)

fl, + 1 ~ fl, - signe [9,l. de, La fonction signe [8;] est Ie signe de 8, et on prend 80 ~ - 8. Ces operations ne comportent que des additions avec decalages, elles peuvent etre plus avantageuses que la multiplication complexe de meme precision. Le ealeul d'une TFD d'ordre N avee un volume de multiplications qui soit de l'ordre de N, au lieu de N log 2(N), peut etre obtenu par une factorisation de la matrice TN d'un type particulier. En effet la malrice TN peut se decomposer en un pmduit de trois f"cteurs :

au AN est une matrice de dimension J x N, avec J entier, CN est une matri'ce diagonale de dimension J et BN une matrice de dimension N x J. L a paJ'ticularite de cette factorisation reside dans Ie fait que les ele" ments des matrices AN et BN sont 0, 1 au - 1. Dans ces conditions Ie calcul demande J multiplications. Far exemple la multiplication complexe. se. met'sous cette forme :

[~

Q a+b

-1 0.

o

c.e qui permeJ .de Fdfectuer avec- :3 multiplic.ations reelles seulement Com me indique au paragraph" 2:7. Celte decomposition est evidente pour J ~ N '\ par, exemple pour N = 3, il vieJ;lt : 1 1

." T3~ l ~ ,o

"••

],

•o o o

•

1 1 a 0 0 0. 0. 0. 1 r 1 .0 0 0. 0 0. 0 0. 1 1

.Q

n

0 1 1 W

W2

a

1

W2 W

1 0. a1 a 0. 1 0 0. 1 0. 0. 1 0 a1 0. O.

D 0 1 0

0. 1 0. 0 1

'1C

8o

]

~

Avec certaines valeurs de N faibles, il existe des factorisa tions tellts que 1 soit de l'ordre de N, alors il en est de meme du nombre de multiplic.ations. Pour generalio ser cette propriete et rnettre en evidence une f;:tctorisation de TN convenable il £aut operer une permutation des donnee~ avant et apres transformation. Par exemple, pour N ~ 12, en posant :

3 • Autres algorithmes de (alcul rapide de la TFR'

10Q

Xo Xg

Xa X,

X4 X ' ·~

et x'=

Xi XJ O

X 7. Xs

X,

X2

Xu

et en faisant appe1 aux produits de Kronecker de matrices, on verifie que:

., T) 4 ,x De, meme. 81 N s_e

de.compose~ en

L facteurs pre-hliers entre. eux :

On peut monTIer que : (H~)

En utilisant la factorisation definie precedemment pO\lf les matrices prietes a\gebriques des produits de Kronecker, it v ient :

T", et 1es pro-

Ce resultat definit un type d'algorithme, appele algorithme de Winograd, Il apparall c1airement que l' algorithme d'ordre N se deduit des algorithmes d'ordre N; avec 1 '" i '" L; d'ou l'importance des algorithmes a faible nombre de multiplications P,Qur les petites valeurs de N, La reference [14] donne des algorithmes pour N ~ 2,3, 4,5,7,8,9,16, au Ie nombre de multiplications est de l'mQre de N, comme Ie montre 1e tableau 3.2, Dans la colonne des inultiplications, les chiffres entre parentheses dannent 1e nombre de multiplicatio ns par des coefficients differents de 1, De plus ces multiplications sont des multiplications complexes qui correspondent a deux multiplication" noelles, Le nombre d'additions est comparable a celui des algorithmes de TFR Les algorithmes pour les faibles valeurs de N sont obtenus en calcu1ant la Transfo.rmee de Fourier Camme un ensemble de' correlations : N ~l

Xk

~

L

n =1

(xn -x,o)Wnk;

k~ 1, "" N-1

3 .5

Autres algorithmes de calcul rapide

Tableau 3.2. -

101

NOMBRE D~ 0PERATIONS DANS LES ALGORITIIM;ES

DE WINOGRAD D'ORDRE

O.rdre

N SAIELE.,

Multiplicatiens

dl< la TIm 2 3 4 5 7 13·

2 3 4 6

9

16

Additions

(0) (2) (0)

2 6 8

(5)

17

g

(8) (2) (10) 18 (10)

36

8 11

26

44 74

et en utilisant'les propri"les algebriques de l'ensemble des exposantsde W, definis moduloN. Par exemple, pour N ~ 4, l'enchalnement des operations est Ie suivar\t: t1 =Xo + x2!

t2= .\1. +x 3

mo~1.(~

m l = 1. (11 -12)

+,,),

me =1. (XO--"2)' m3= j(X,-X3) X o= ·mo Xl = 1112 + m 3 X2 ~ml X3~~-m3

PourN =1\ : ~=~+~

t4 = X1 -X5'

t1 + t')"

t7 ~

~~~+4

~~~+~.

+ x7 , + tS t

t6=X3-X7'

t5 =X3

t8 = t3

~ 1. (1,

"••

mo ~ 1.(1, + '8),

ml

m2 =1.(11-12).

'/J13 ~

•c

m 4 = cos

"].," o c

cn·

(14

- 18), 1. exo - x 4 ),

-16),

•

.<e

8o

"0

~

:; s1=m3+ m 4' s2= m 3·-m 4, s3=m6+~ Xo=tno ,· Xl = Sl + S3) Xl =m2 + m s ,

~

~=mv

Xj

=S2+ S4_'

X 6 = in 2 = m:s,

s4=m 6 -11'lrX3 = Sz -S4

X7=Sl-S3'

3 • Autres algorithmes de (alcul rapide de la TFR

102

Finalement les algorithmes de Winograd apportent une reduction du volume <,Ie aaleul, qui peut etre importan!e, par rapport aljX algorithmes de TFR. Il en est de meme pour d'autres algorithmes, CDmme ce.ux qUI consistent autiliser les transfOTmees polynomiales [15]. Ces techfiiques peuvent apparaltre interessantes dans certaifle$ applications, mais il fllut bien Doter qu'elles peuvent conduire a une plus grande capacite de memoire et aun enchainement plus complique des operations, se traduisant par un accroissement dl! voll.!me de materiel de I'unite de cbmmande du systeme au de 'la taille des memoires de programme. Vne autre voie· sed\lisante dans la recherche de I'optimisation uu traitement et des,machines, est celle qui fa,it appel aux transformations ·algebriques.

3.6

TRANSFORMEE DE FOURIER BINAIRE - HADAMARD

La transforrnee de Fourier discrele et ~es variantes necessitent une quantite de caiculs qui pelit etre jugee excessive pour certaines applications 1 certains traitements d' images en temp. reel pur exemple. Alors, on peut faire appel a des' transformee. ayaJ,lt des proprietes comparables, mais sam; mult'ipikatlon..s, cQrnme la translormee dite de Fourier binaire ou Hadamard [16]. La transfonnee de Hadamard d'ordre N ~2M est definle lJar la matrice H", qui se deduit de la TFD d' ordre 2, T 2 , par produits de Kr,me-cker:

H, oT' ~l:

"1,n,ot,0T'0[l

1

1

-1

l

1

-1

-1

-1

11 ;

-1 -1 1

HN~T2

(3 .44 )

C'est une transformee reelle, sym€trique et ortliogonale:

I.es algorithmes rapides sont les memes que pour la TFR, avec les croislllons mais sans les multiplications. Sur Ie plan du filtrage, Ie bane de filtres: obtenu est beaucoup moins selectif que celui de la TFD ~ car les fonctions elementaires comportent une frequence et des harmoniques. Par exemple, 1a figure 3.5 represente Ie module de 1a transformee de Fourier de la ligne 31 <,Ie la matrice H 64 .

103

Les transformees a/ge'b riques

3.7

Amplitude

.0,5 0,45

0,4 0,35 o, ~

0,25 0,2

0,15 0,1 0,05

J

°°

I 10

20

30

40

50

60 Indice (0 - 63)

Fig, 3.5.

Sp ectre du wde 31/64 de Hadamard

Les matrices de Hadamard trouvent un domaine d'application inlportant en radiocommunications. mobiles) car les elements sont utilises comme code:$. a'etalement dans les systemes bases sur l'etalement de spectre.

3.7

LES TRANSFORMATIONS ALGEBRIQUES

La transformation de Fourier conduit a faire des operations arithmetiques dans Ie corps des nombres complexes; les machines qui realisent ces operations utilisent generalement des repre§entations bin aires qui sont des approximations des donnees et des coefficients. La precision des ealculs est fonction du nombre de bits disponible dans la machine, • En fait une machine a B bits effectue des operations sur I'ensemble a 2B elements des entlers : 0, 1, ... , 2B - 1. Dans cet enSemble les lois d'addition et multiplication habituelles ne peuvent etre respectees, il faut introduire Ie decalage et la troncation qui g entra1nent des appTO.ldrnatians dans les caleuls, camme inclique au paragraphe 2.3 . .~ La premiere condition a remplir pour que les caleuls soient exacts dans un S ensemble E est que Ie produit ou· la somme de deux elements de l'ensemble E -@ -a appartiennent a cet ensembie.. Cette condition est verifiee dans l!ensemble des c"l entiers 0, 1, ... , M - l .. i les ca1culs sont faits modulo M. En choisissant convenab1e'ri ment Ie module Mil est possible de definir des transformations ayant des proprieo ," les comparables a celies de la TFD et permettant 1e calcu! de convolutions sans "@ erreur avec des algosithmes de oaleul rapide.

"

3 • Autres algorithmes de (alcul rapide de la TFR

104

La definitio n de telles transformations repose sur les propri6tesalgebriques des entiers modulo M, pour certains chaix de M ; on peut les designer par transfo r-

mations algebriques. Le choix du module M est regi par les considerations s uivantes :

a) SimpliGite des caleuls dans une arithmetique modulo . Dans son principe, uno. arithmetique modulo implique une division par Ie module M . Cette division est triviale pour M = 2m; elle est Ires simple pour M = 2 m ± 1, car il suffit pour obtenir Ie resultat d 1aj buter une retenue (arithm6tique en co:mplement a un ) OU de la sOliStraire.

b) Le module doit eire suffisamment grand. Le resultat de 'la convolution doit pouvoir etre represente 'sam. ambigui.16 dans llarithmetique modulo M. Par exemple, une convolution a32 termes avec des don-

nee$ a 12 bits et des coefficients a 8 bits impose M > 2 '5 c) Proprie!es algebriques Gonvenables. L'ensemble des entiers modulo M doH presenter des proprieles algebriques perIPettant de dMinir de~ transformations comparables a la TFD. D'abord il doit exister dans Get ensemble des elements periodiques, pour que ['on puisse elaborer des algorithmes de calcul rapide ; it faut disposer d'un element oo tel que .: On peut alors definir une transformation par l'expression ; N-l

X(k)=

L

n=O

(3. 45)

.v (n)a. nk

Pour que la Transformation inverse, d6finie par l'expre:;;sion ; N-l

x (n ) = N-l

L

X (k)a.- nk

(3.46)

k= O

existe, il faut d'abord que N et les puissances de a possedent des. inverses. On demontre que N a un inverse modulo M si N et M sont premie rs entre eux. Ltelement a doit etre premier avec M et d'ordre N, c'est-a-dire ql)e aN = L L'existence de la transformation inverse implique de plus une condition sur les ai, c.' est-a-dire que: N-l

L

k ~O

a.;k=Ni5 (i ) avec

Il (i ) = 1 si ll(i)=O .si

t' = 0 modulo N i omodulo N

'*

Cette condition se traduit par 1e fait que les elements

n- aI ) deivent posseder

un inverse. On qemontre que l'ensemble des conditions pour l'existence d'une tnl,nsformatiqn et de son inverse se ramene ala condition sulvante: pour tout facteur pre-

mierP deM, il faut que N divise P -1. Ainsi , ~iM est premier, N doit diviser M-l. Des algorithmes de caleul rapide peuvent etre elabores si N est un nombre composjte, en particulier si Nest une puissance de 2 ; ces algorith:mes sont semblables a Geux de la TFR. .

3.7

Les tran~formees a/ge'b riques

105

D'autre part les calculs a faire dans la transformation se trouvent considerablement simplifies dams Ie cas particulier ou ()( ~ 2. Fjnalement un choix du module M tres interessant est Ie suivant:

quand M est premier. Ce. nombres sont les.nombres de Fermat. Une transformation algebrique basee sur les nombres de Fermat est detinie comme ·suit ~ - M odule M ~ 22m + 1 .Ordre de la Transformee : N = 2 In + 1 - Transform~e directe :

~

1>1 . 1 X (k)~

L,. x(n)2nk n ~O

- Transformee inverse: N-l

x(n)~(2()

L

X(k)2' nk

ave,c

t~2nH l-m-l

k=O

CeUe transformation permet de calculer des convolutions de nombLes reels" comme la Transformation de fourier Discrete, mais aVec les avantages suivanls_~ - Le resultat est obtenu sans approximation. - Les operations portent sur desnombres reels. - Le calGul de la transfQrm6e et de son inverse ne neGessite allcune mtiltiplication. Seules restent les multiplications dans l'espace trans forme.

,o

."••"

Cependant cette technique presente des limitations importantes. Les calculs etant eXacts, Ie moduie M doit eire suffisammenl grand, ce qUI cangult ii des nombres de grande longueur. Les·Telations entre les parametres M et N donnees ci-dessus, i-rpposent que les

calcul~ soient faits

avec un nombre de bits B de i'9rdre de

~ ; c'est-ii-dire que ie

~ nOlilbre cle termes de la convolution est approximativement Ie double du hombre

§

de bits des donnees dans- Ie calcuL L'applfcation S,e. trouve par suite- restreinte aux convoiutions (:;omportant peu de termes. '1C 8 Le domaine d'application des transformations algebriques peut etre elaTgi en .§ faisant appel a d'autres nombres que les nombres de Fermat, ou encore en traitant :; les conv.olutions a grands nombres de termes comme des convolutions a deux 1i dimensions [17]. La reference [18] d6Qrit un exemple de realisation. §Les· transformations algebriques sont utilisees en cod age correcteur d'erreur, o
~

~

3 • Autres algorithmes de (alcul rapide de la TFR

106

BIBLIOGRAPHIE PEA,sE~ Methods

olMatrix Algebra. Academic Press, New York, 19(55.

[1]

M. C.

[2)

C. S. B URRUS and York, 1985'.

[3J

H . S WATE - Matrix Representatioils for sorting and the Fast Fourier TransfotID. IEEE Trans. Vol. CAS-21, N ° 1, Janvier 1974.

T. W.

PARKS - DFIIFFT and Convolution Algorithms, Wiley, New

l4] G. B ERGLAND - A fast Fo~rier Transfonn Algorithm for Reil! Valued Series. Communications ofthACM, Vol. 11, N" 10, Octobre1968.

[5] J.6. VERNEr - Real Signals FFT by Means of an Odd Discrete Fourier Transform. Proceedings of IEEE,_Oetobre 1971.

[6] G. BGNNERGT and M. BELLANGER - Odd-Time Odd-Frequency DFT for Symmetri'C Real-Valued Series. Proceedings of IEEE, March 1976. [7]

H. ZrEGL.ER - A fast Transform Algorithm for Symmetric Real Valued Series. IEEE Transactions, Va!. AU-20, N" 5, December 1972.

[8] C;:. DrAB, M. OUE)DAT and R. P RO,T, «A New IDCT-DFT Relationship Reducing the IDCT computational Cost », IEEE 'trans. on Signal Processing, VoL 50, N ° 7, July 2002, pp.1681-84. [9]

J. PRADO - «Transformation de Hartley Discrete Rapide», Annales des Telecom., 40, 9-10, Oct. 1985, PP·. 478-484.

.N ~

H. J. NUSSRA.UMER - -.; :<:Algorithrues de transfonnation de FOllrier et en lD,ono et bi-dimensiortnels», Annales des Telecom." 40, NM 9-10~ Oct. 1985, pp. 466-477.

[lQ] M.

VEIT ERLI,

COMUS

[11]

M. A. HAQUE - ~<- A two-DimensiQnnal Fast Cosine Transfonn », IEEE Trans., vol. ASSP-33, N' 6, Dec. 1985, pp. 1532-1539.

[12] H. S. M ALVAR, Signal Proces$ing wlth L(lpped Trans/o·rms. Artech. House, Norwood MA,1992. [13] A. DESPAIN - Very Fast 'F ourier Transfonn Algorithms Hardware fo); Implementation. IEEE Transactions on Computers, Vol. C . 28, N" 5, May 1979. [14]

H . SILVERMAN - An Introduction to Programming the Winograd Fourier Transfomi Algorithm. IEEE Transactions, Vol. ASSP-25, N' 2, April 1977.

[15]

H. NUSSBAUMER, - NouveauX' Algorithmes de Transfor.mee de Fouriet Rapide. L 'onde Electrique, Vol. 59, N'" 6-7, Juin 1979, pp. 81-&8.

[16-] B. F INO and R. ALoAZI, «Unified Matrix Treatment of Fast Walsh-Hadamard Transform», IEEE Transaction! on Computers, Nov. 19'76, pp. 1142-46. [17]

R. C. A GRAWAL AND C. S. BURRUS - Number Theoretic Transforms to Implement Fast Digita.l Convolution P t oc. IEEE, Vol. 63, 1975.

[18]

J, H . MAe CLElLAN - Hardware Realization of a Fennat Number T ransform. IEEE Trans. Vol. ASSP-24, June 1976.

,Exercices

107

EXERCICES 1 EifectlleF 1" pTgduit de Kronecker A <8l Ig, de 1a matrice A telle que: A~

par la matrice uniteI3 de dimensi~n 3. Effectuer Ie produit I3 ® A et Ie comparer au precedent . .2 En prenant des matrices carrees- de dimension 2, vecifier Ies proprietes dys proguits de ,Kronecker des matrices donnles au patagraphe3.1. 3 Bcrire Ia factorisation de Ia matrice sela TFD d'ordre 64 en base 2, en base 4 et en base 8, st}lon la procedury donnee au paragraphe J .2. 4 En utilisant l'entrelacement temporel t factoriser Ia matrice. de Ia TFD d'ordre 12. Quel est Ie nomBre minimum de multiplications et ad'ditions necessaire.? :Berire. Ie pro~ grainme de calcul. 5 Fa~toriser Ia matrice de.'la TFD d'ordre 16 en base 2, dans les deux <>as suivants : - Ie.s donneys se presentent en entree et s ortie. dans l~ordre naturel, - les-etages de calcul soilt identiques. Donner, dans Ie demier cas, un schema de realisation en utilisant comme memrnres, des registres a decal.age. 6 Soit a _cakuler une Trnnsfonne:e de Fourier Discrete d'ordre 16 port ant sur des donnees reeiles. EciiTe l'algorithme qui utilise une TFD d'ordre 8, pour ce calcu1. Ecrire.I'algoritbme base sur Ia TFD impaire. Comparer ces algorithmes et Ies nombres d'operation s-. 7 Soit a calculer uhe TFD d'ordre 12, en utilisant une factorisation du type donne au paragraphe 3.6 et avec les permutations indiquees pour les donnees. Ev_alller Ie nombre d'operations et Ie compurer aux yaleurs trQuvet}s dans L'eXeItice 4. ·8 Pour effectuer la convolution circulaire des deux suites : x

h = (1, 2, 0, 0), on utilise. une transfonnee algebrique de module M

',. •

]

•c o c

•

'1C

8o

"0

~

~

• -g ~

§

o

"

(2, - 2~ 1, 0) et 17 et de coefficient

=

4, C0ll1111e N ~ 4, verifier que aN = 1. Ecrire la matrice de la transformation et de Ia transfonnation'inverse . V6ifi.er qlle Ie re.sultat chen::h~ e1itla s\.lite ,Y= (2, 2, -J. 2). C<~

"••

=

Chapitre 4

Les systemes lineaires discrets invariants dans Ie temps

Les systemes lineaires discrets invariants dans Ie temps (UT) constituent un domFl-lne tres important du traitement nume-rique du signal~ qui est celui des filtres nl,lmeriques a coeffir;iynts frx~s. Ce.s 1?ystemes se caracterisent par Ie fait que leur fonctionnement est regi par une equation de convolution. L'analyse de leurs-proprietes se fait a l'aide de la Transformation en Z , qui joue pour .les systemes discrets Ie meme r61e que la transformee de Laplace au de Fourier pour les systemes conlin us. Dans Ie present chapitre les elements les plus utiles pour l'i\tude de tels systemes sont introduits brievement. En complement on peut se reporter am references [1 ,2,3,4,5].

4,1

DEFINITION ET PROPRIETES

Un systeme discret est un systeme' qui convertit 'TIne ·suite de donnees d'entree'x en) en une suite de sortie y (n). II est lineaire si la suite xl(n) + ax, (n) est convertie en la suite y,(n) + aY2(n) . II est invariant dans Ie temps si la suite x (n - no) est convertie en la ·suite y (n. -no) quel que soit no entier. SOil uo(n) 1a suite unitaire representee sur la figure 4.1. et definie par:

uo(n) = 1 pour n = 0 uo(n)=O pour n*O

(4,1)

Toute suite x (n) peut se decomposer en llne sDmme de suites uniraires convenabJement decalees : rn

x (n)=

1:

m=-
x (m)uo(n-m)

(4.2)

4.1

Deflnition et proprleies

.,

109

'0

•

..

I

I

o

•

n

n

FIG. 4,1,

Suites unitaires

D ~ autre part soit hen) la suite qui constitue 1a repons~ du systeme a la suite unitaire uo(n). A lasuite Uo(n - m) correspond la reponse h (n - m) en raison de rin-

variance temporelle: La linearite entralne alors la relation suivante :

yen) ~

Lm

Lm hem) x(n -m) ~ h(n) • .t(n) (4.3)

.t ern) hen -m) ~

C'est l'equation de- convolution qui caract€rise Ie systeme lineaire invariant dans Ie

temps (LIT). Un tel systeme est done completement dMini par la dOllllee de la suiteh(n). qui est appelee repanse lmpulsionnelle du systeme. Ce systeme possede 1a propriete de causalit6 5i la sortie a l'indice n = no ne depend que des entrees aux indices n ,;; no' CeUe propriete linplique que h (n) = 0 pour n <. O. et la sOTtie est donnee par : y(n)=

L

h(m)x(n-m)

(4.4)

m=O

Un systeine LIT est stable si

a. toute

entree d'amplltude borhee correspond une

sortie borne-e. Une cONdition necessaire et suffisante de stabilite est donnee par l'in6galit~ :

Ln

Ih(n)1

<00

( 4.5)

o

~

•

.~

Pour memtrer 'que la condition est necessaire il suffit d'appliquer au syste,me la suited'entreex(n) telleque:

],"

x..(n)=+l

SI

o

- 1

51

•o o

•

lo

h'(n) C3 Q h(n) < 0

II vient alors ptmr .n = 0 :

'0

~

~

• 1i ~

8 ©

y (0) =

Lm 1/1 (m)1

Si l'inegalite (4.5) n'e&t pas veriftee, y(O) n'est pas borne et lesysteme n'est pas stable,

,4 • Les systemes linea ires discrets invariants dans Ie temps

110

SI 1a suite d~entree est bornee, c~est-a-dire : fx(n)1 s M

poqr loulli

alors 11 vien! :

ly(n)l,;;

Lm

Ih (m)1 fx(n-m )1~ M

Lm

Ih(mJI

5i I'egalite (4.5) est veTifiee, alors y enJ est borne; la condition est suffisante. En particulier Ie systeme LIT dMini par la reponse suivante :

hem) ~am avec m ",, 0 est stable pour lal < 1. Les camctl~ristiques des systernes LIT sout eturuees tion en Z.

4.2

a Paige de la transforma-

LA TRANSFORMATION EN Z

La transformee en Z, X(Z) de I. suite x (n) est definie par la relation SUlvante : m

X(Z)~

L x(n) Z-n n=-($J

(4.6)

Zest une variable complexe et la fonction X(Z) ppssede un domaine de convergence qui en geneTal est un anneau centre sur l'origine, de rayons Rl et R2. C!esta-dire qqe X(Z) est defini pour Rl < IZI < R2. Les valeurs Rl et R2 dependent de la suite x(n). Si la suite x(n) represente la suite des echantillons d'un signal preleyeS avec 1a periocle T , 1a transforrnee de Fourier de cette suite s'ecJit: w

L

S(t) ~

J; (n )e-i2nJnT

A1nsi, pour Z = e J2J>[f 1a transformee en Z de la suite x (/1) cOl'noide avec sa transformee de Fourier. C'est-a-dire que l'analyse d'un systeme discret peut se (aire. ay~q' 1& transfQ)1l1ee en Z el, pO\lr connall,e 1& repon~e en freq\!eJ)q~ , suffit de remplacer Z paT e i""fr Cette transformee possede une transformee inverse. Snit r 'Un contour ferme eontenant lous les points singuliers, bu poles, de X(Z) ainsi que I'origine; on peut e-.crire:

a

zm-1X(Z)~

L'"

x(n)Zm-l-n~x .(m)Z· '+

L

Zm- ' -nx(n)

ni'm

n=-q;.

et .d'~pres Ie theoreme des

re~id'Us

:

x(m)~~f 2TC} p

zm-1X(Z)dZ

(4.7)

4.2

La transformation en Z

Par exemple si X(Z)

~

111

1

1- pZ

on obtient par applioation directe de l'equation

l '

ci-dessus : ~ pn

:>;(n)

pour

x(n)~O

n

~

0

pour li < O

De me me ii X(Z) definie par:

l-p,Z' correspond la suitex(n) teUe que: N

x(n)~

L a.p" i= 1 I

x(n)~O

I

pour

n""O

pour

n< O

U'ne condition de stabilit6 apparalt tres sirnplement en observant que la suite

x (n) est bornee si, et seulement si Ipil < 1 pour 1 "" i "" N, c'est-a-dire que les poles de X(Z) sont ii ]'interieur du cerele unite.

Dans ces exemples, les termes de [a su1te x(n ) peuvent aussi etre obtenus directement par developpement en serie. Quand X(Z) est une fraction rationneUe une methode tres simp'le pour obtenir 'les pren1ier~~ valeurs de 'la suite x (n) consiste afaire une division de polyn6mes. Par exemple pour:

1+2Z-1+Z-2+Z-3

X(Z) ~ l-Z '-SZ 2+12Z

3

la division directe donne :

X(Z) ~ 1 + 3Z- 1 + 12Z~ 2 + 25 Z.- 3 + . . . d'ou ~

x(0) = 1 ;

x(1)~3 ; x(2)~12; x (3)~25

,o

" La transformation en Z 'possede la propriete de linearite·. D'autre I'art ]'a transfor• .31mee en Z de la suite :retardee x(n -~) s'e.crit:

• ~

•o

g

l•

ii -a. • -g~

8 @

Xno(Z) ~ z~n0X(Z)

(4 .8)

Ces deux proprietes .gont utiliseys pour calculer la transformee en Z, Y (Z), de 1a suite y(n) obtenue en sor~ie d'un systeme iineaire discret, par convolution des suites x (n) et h (n) qui ont pour transformees X(Z) et H(Z). En calculant la transformee en Z des deux membres de l'equation de convolution(4.3) :

Y0)~Lb(m) x(li-m) ~

4 • Les systemes linea ires discrets invariants dans Ie temps

112

il vient ; Y(Z) ~

l: m

h(m)Z-mX(Z)~H (Z) . X(Z)

('4,9)

Par suite la transform6e en Z ~ruIi produit de convo.lution est Ie produit des transformees. La fonction H (Z) est appelee fonction de transfert en Z du systeme LIT c'onsidere. La transformee en Z du produit de deux suites -,,(n) ~ "" (n) .x,,(n) estla fonetion X, (Z) definie par :

L

X3(:Z;)~ 2~j Xl(V)~(~)V-ldV Le contour dlinregration est

( 4.10)

al'int6rleur du domaine de conveI;gence des fon,ctions

~ (V) etX2 (~). L~ application

aux suites causales arne-ne

a introduire

1a transformation en Z

monolaterale.

La transformation en Z monolaterale de la suite x (n) s'ecri! : ~

X(Z)

~

l:

X (n.)

z-n

n=O

(4.11)

Les proprietes sont res memes que celles de la transformation d6finie par 1a relation (4.6), sauf pour les suites retardees. En effet la transformee de la suite x (n = no) s~ ecrit : .no

ro

Xno(Z) ~

l:x(n - no) z-n~z-no.x ( Z)+ n =0

l:x (-n ) Z-("9- h )

(4.12)

n=1

L ~interet de cette transformation est de prendre en compte- les conditions initiales et de fai're apparaltre les regimes transito'ires dans l'etude de la reponse d'un

systeme. D'autre part elle permet de determiner a partir de X(Z) extremes de la suite x (n). La valeur initialex (0) s'ecrit: x (0) ~ Urn X(Z) :z: ~w

le~

valeur.

\4.13)

eLla valeur finale, obtenue encaleulaht la transformee de la suite x(n + 1) - ,~(n) : x (00) ~ lim (Z-l) X(Z) ~ lim (1- Z-l)X(Z-) Z--d

l---+l

(4.14)

Pour .des developpements plus importants sur la transformation en Z et ses applicatlons, on peut se reporter a la reference [6.], Les resultats ei'-dessus s'appllquent au caleu! de la puissance. des signaux discrets,

4.3

4.3

tnergie et puissance des :s;gnaux-discrets

113

ENERGIE ET PUISSANCE DES SIGNAUX DISCRETS

Soit a calculer l'energie E du signal represente pa, la suite- .t(n), dont la Transformee en Z s' ecrit X(Z) . Par definition : 00

lh

L lx (ll )12 n=-w

La sultex3(n) deDnie par:

peut etre consideree comme Ie praduit de deux suites, xl (n) et -'2 (n) telles <;lue :

a

a

La transformee X3