Algorithmique et Programmation TD n Fast Fourier Transform

Fourier Transform

Description

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 ·

Sujets

• Transform
• Complexité
• Convolution

Informations

• Publié par: pefav
• Nombre de lectures: 63
• Langue: Français

Extrait

1

AlgorithmiqueetProgrammation ◦ TD n 9 : Fast Fourier Transform

Petits Rappels

Ecolenormalesup´erieure D´epartementd’informatique [e-mail]

2011-2012

ConvolutionLaconvolutionde deux vecteurs (a 0 , . . . , a m−1 ) et (b 0 , . . . , b n−1 ) est le vecteurc=a∗b de longueurn+mdont lekeenfficcoismtet`ee-: X c k =a i ∙b j (0≤i < m,0≤j < n) i+j=k

2

−1 ()),o`ulesvecteursaet Leth´eor`emedeconvolutionditquec=DF T n+m DF T m+n (a)∙DF T n+m (b bttaandeiussj’`quzsedore´se´tcevasnolpe´ctmoeleralatlin+m.

R´einventezlaFFTvous-meˆme

Exercice1:Formenormalealge´briqued’unefonctionboole´ennes’in.Onesset´erfenoa`nuntcoi n boole´ennef(x 1 , . . . , x n ) : (F 2 )→F 2 teC.rspaabatdeleerv´e´tie’c(-tstefonctionpeutˆertrepe´rsene´tee n `a-direparlalistedes2valeursqu’elleprendsuccessivement),oubiencommeunemumtlviplonyoˆari´ede degr´eauplusnsurF 2 [x 1 , . . . , x n peapeqll]nr.Ome´le´xustneecrlsuuede`apsorF 2 , l’addition est leXOR 2 et la multiplication est leAND. Il s’ensuit qu’on a toujoursx=xeptuodcnesertser,etqu’ona`erdni conside´rerdesmonˆomessanscarr´e.Pluspre´cise´ment,onaffirme(etonvajustifier)quefriect:’´s X a 1 a n f(x 1 , . . . , x n ) =g(a 1 , . . . , a n )∙x . . . x 1 n n a∈(F 2 )

a o`ug(aemoduomnˆeocffieitn)seltcex.ttCeaestlatnenoitperese´rrmalmenoforqieue´rbaegl(ANF) n def. Il s’ensuit queg: (F 2 )→F 2 etsell-eˆmmeueenofcntionbool´eenne.Ltube’ledrexeecictdese 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(x 1 , . . . , x n ) =f 0 (x 1 , . . . , x n−1 ) +x n ∙f 1 (x 1 , . . . , x n−1 )

Exprimezf 0 etf 1 en fonction defd´,equ’mˆemssonellertnameno`l-aptrasetufiniend´etbiese.inuq 3.Onconside`relesANFg 0 etg 1 def 0 etf 1 respectivement. Exprimezgen fonction deg 0 etg 1 . Concluez que l’ANF existe et est unique. 4.D´eduisez-enunalgorithmedecalculdegnnoD.mpcosaeze.t´xile 5.Cetalgorithmepermetenfaitdecalculerla“tabledev´erite´”d’unpolynoˆmemultivari´ede F 2 [x 1 , . . . , x n ly-luerlepoa`tiave´sisnareteqıvcouiureda ¨ enor´clcpaaeevix´tmplesacoarezComp.] n nˆome2fois. Solution de l’exercice 1 1. Sinoral1,=rchencsoe´rceha`riefsous la formef(x 1 ) =g(1)∙x 1 +g(0). En fixantx 1 = 0, on trouveg(0) =f(0). Ensuite, en fixantx 1 = 1, on trouveg(1) =f(0) +f)1L.ceraca`treieolnvifut( del’op´erationesttrivial.

1