Algorithmique et Programmation TD n Fast Fourier Transform

De
Publié par

Algorithmique et Programmation TD n? 9 : Fast Fourier Transform Ecole normale superieure Departement d'informatique 2011-2012 1 Petits Rappels Convolution La convolution de deux vecteurs (a0, . . . , am?1) et (b0, . . . , bn?1) est le vecteur c = a ? b de longueur n+m dont le k-eme coefficient est : ck = ∑ i+j=k ai · bj (0 ≤ i < m, 0 ≤ j < n) Le theoreme de convolution dit que c = DFT?1n+m(DFTm+n(a) ·DFTn+m(b)), ou les vecteurs a et b sont completes avec des zeros jusqu'a atteindre la taille n+m. 2 Reinventez la FFT vous-meme Exercice 1 : Forme normale algebrique d'une fonction booleenne. On s'interesse a une fonction booleenne f(x1, . . . , xn) : (F2) n ? F2. Cette fonction peut etre representee par sa table de verite (c'est- a-dire par la liste des 2n valeurs qu'elle prend successivement), ou bien comme un polynome multivarie de degre au plus n sur F2[x1, . . . , xn]. On rappelle que sur le corps a deux elements F2, l'addition est le XOR et la multiplication est le AND.

  • questions precedentes

  • quantite finie de coefficients des series en entree

  • dire

  • complexite

  • consequence immediate de la premiere question

  • convolution

  • u2 ·


Publié le : mardi 19 juin 2012
Lecture(s) : 60
Source : di.ens.fr
Nombre de pages : 7
Voir plus Voir moins
1
AlgorithmiqueetProgrammation TD n 9 : Fast Fourier Transform
Petits Rappels
Ecolenormalesup´erieure D´epartementdinformatique td-algo@di.ens.fr
2011-2012
ConvolutionLaconvolutionde deux vecteurs (a0, . . . , am1) et (b0, . . . , bn1) est le vecteurc=ab de longueurn+mdont lekeenccoismtet`ee-: X ck=aibj(0i < m,0j < n) i+j=k
2
1 ()),o`ulesvecteursaet Leth´eor`emedeconvolutionditquec=DF Tn+mDF Tm+n(a)DF Tn+m(b bttaandeiussj`quzsedore´se´tcevasnolpe´ctmoeleralatlin+m.
R´einventezlaFFTvous-meˆme
Exercice1:Formenormalealge´briquedunefonctionboole´ennesin.Onesset´erfenoa`nuntcoi n boole´ennef(x1, . . . , xn) : (F2)F2teC.rspaabatdeleerv´e´tiec(-tstefonctionpeutˆertrepe´rsene´tee n `a-direparlalistedes2valeursquelleprendsuccessivement),oubiencommeunemumtlviplonyoˆari´ede degr´eauplusnsurF2[x1, . . . , xnpeapeqll]nr.Ome´le´xustneecrlsuuede`apsorF2, l’addition est leXOR 2 et la multiplication est leAND. Il s’ensuit qu’on a toujoursx=xeptuodcnesertser,etquona`erdni conside´rerdesmonˆomessanscarr´e.Pluspre´cise´ment,onarme(etonvajustier)quefriect:´s X a1an f(x1, . . . , xn) =g(a1, . . . , an)x . . . x 1n n a(F2)
a o`ug(aemoduomnˆeoceitn)seltcex.ttCeaestlatnenoitperese´rrmalmenoforqieue´rbaegl(ANF) n def. Il s’ensuit queg: (F2)F2etsell-eˆmmeueenofcntionbool´eenne.Ltubeledrexeecictdese construire un algorithmeinvolutif(auto-inverse) qui calculegerdtiarpa`f,ruBit.sˆeniqpuercoern´eemt il sera “rapide”. 1. Exprimezgicel`oulscesaafdannclaciuqerude´corapelqueztron.M=1ulegest involutive. 2.Oncherche`a´ecrirefsous la forme :
f(x1, . . . , xn) =f0(x1, . . . , xn1) +xnf1(x1, . . . , xn1)
Exprimezf0etf1en fonction defd´,equmˆemssonellertnameno`l-aptrasetuniend´etbiese.inuq 3.Onconside`relesANFg0etg1def0etf1respectivement. Exprimezgen fonction deg0etg1. Concluez que l’ANF existe et est unique. 4.D´eduisez-enunalgorithmedecalculdegnnoD.mpcosaeze.t´xile 5.Cetalgorithmepermetenfaitdecalculerlatabledev´erite´dunpolynoˆmemultivari´ede F2[x1, . . . , xnly-luerlepoa`tiave´sisnareteqıvcouiureda¨enor´clcpaaeevix´tmplesacoarezComp.] n nˆome2fois. Solution de l’exercice 1 1. Sinoral1,=rchencsoe´rceha`riefsous la formef(x1) =g(1)x1+g(0). En fixantx1= 0, on trouveg(0) =f(0). Ensuite, en fixantx1= 1, on trouveg(1) =f(0) +f)1L.ceraca`treieolnvifut( delop´erationesttrivial.
1
3
2.
3.
4.
Delamˆememanie`requepr´ece´demment,ona:
Supposons que :
f0(x1, . . . , xn1) =f(x1, . . . , xn1,0), f1(x1, . . . , xn1) =f(x1, . . . , xn1,0) +f(x1, . . . , xn1,1).
X a1an1 g0(a1, . . . , an1)x . . . x f0(x1, . . . , xn1) =1n1 n1 a(F2) X a an1 1 f1(x1, . . . , xn1) =g1(a1, . . . , an1). . xx . 1n1 n1 a(F2)
Vulad´enitiondef0etf1, on trouve
f(x1, . . . , xn) =f0(x1, . . . , xn1) +xnf1(x1, . . . , xn1) X a a a1n1a1n1 f(x , . . . , x) =g(. . . , aa , ). . xx . +g(. . . x . . . , a a , x 1n0 1n1 1n1 1 1n1)x1n1n n1 a(F2)
Etilre´sulteque:
g(x1, . . . , xn1,0) =g0(x1, . . . , xn1) g(x1, . . . , xn1,1) =g1(x1, . . . , xn1)
Onadoncquasimentabouti`aunalgorithmer´ecursifpourcalculergirrtpa`adef´d-eseEn. brouillant bien, on peut s’en tireren placec,-tse-d`aeaircveOepscasepulpe´emntaire.Pour)d(1 N accomplir ceci, la fonction dont le pseudo-code suit suppose qu’il existe un tableauAde 2 boo-l´eendonn´eenargument,etquelatabledeve´rit´edelafonctionbool´eennefennvariable est n donne´eparA[start], A[start+ 1], . . . , A[start]. Si+ 2 Arede´eiterv´debaelletaestnrpe´f, il suffit de poserstart= 0. On utilise la notationrd´esignerladdingreelOX,Rtep+uoprdousi´enoit surZ. 1:procedureANF(A, n, start) 2:s0start n1 3:s1start+ 2 n1 4:fori= 0 to 2do 5:A[s1+i]A[s0+i]A[s1+i] n1 6: f0est dansA[start . . . start+ 21] n1n 7: f1dansA[start+ 2. . . start+ 21] 8:ANF(A, n1, s0) 9:ANF(A, n1, s1) 10:end procedure n Lacomplexite´duprocessusobe´ita`lar´ecurrencehabituelleTN= 2TN/2+N(o`uN), et= 2 n donclacomplexit´etotaleestns.tion´era2op
Applications
(presque) directes de la FFT
Exercice 2 : filtrageutse)...e´silitispositi.Undqeeuclnopfyhisuqopcrnehoe(qumiuncsol,epoonu,lics pouracqu´erirunsignal,quiconstitueunesuiteder´eelsx0, . . . , xnassez longue. Seulement, le dispositif nestpasdetr`esbonnequalit´eetlese´chantillonscontiennentdubruit.Unemesurerudimentairepour retirercebruitconsistea`appliquerunlissageGaussien,cest-`a-direa`remplacerchaque´echantillonpar unemoyennepond´ere´edesesvoisins:
k X 1 2 j yi=xi+je Z j=k
o`ukerte`marapnutseo`et,urgearldeuZest un facteur de normalisation choisi convenablement. Evidemment,ilyaunprobl`emesurlesbords(x1etxn+1tponesnnied´asosiam,)sritnesnnee disant qu’on jette leskmirere`epesltsekdesvaleursreine`erdy. 1. Montrez comment on peut calculeryen tempsO(nlogn).
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.