Algorithmique et Programmation TD n Fast Fourier Transform
7
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
7
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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.
Voir
- questions precedentes
- quantite finie de coefficients des series en entree
- dire
- complexite
- consequence immediate de la premiere question
- convolution
- u2 ·
1
AlgorithmiqueetProgrammation ◦ TD n 9 : Fast Fourier Transform
Petits Rappels
Ecolenormalesup´erieure D´epartementd’informatique td-algo@di.ens.fr
2011-2012
ConvolutionLaconvolutionde deux vecteurs (a0, . . . , am−1) et (b0, . . . , bn−1) est le vecteurc=a∗b de longueurn+mdont lekeenfficcoismtet`ee-: X ck=ai∙bj(0≤i < m,0≤j < 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´briqued’unefonctionboole´ennes’in.Onesset´erfenoa`nuntcoi n boole´ennef(x1, . . . , xn) : (F2)→F2teC.rspaabatdeleerv´e´tie’c(-tstefonctionpeutˆertrepe´rsene´tee n `a-direparlalistedes2valeursqu’elleprendsuccessivement),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,etqu’ona`erdni conside´rerdesmonˆomessanscarr´e.Pluspre´cise´ment,onaffirme(etonvajustifier)quefriect:’´s X a1an f(x1, . . . , xn) =g(a1, . . . , an)∙x . . . x 1n n a∈(F2)
a o`ug(aemoduomnˆeocffieitn)seltcex.ttCeaestlatnenoitperese´rrmalmenoforqieue´rbaegl(ANF) n def. Il s’ensuit queg: (F2)→F2etsell-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(x1, . . . , xn) =f0(x1, . . . , xn−1) +xn∙f1(x1, . . . , xn−1)
Exprimezf0etf1en fonction defd´,equ’mˆemssonellertnameno`l-aptrasetufiniend´etbiese.inuq 3.Onconside`relesANFg0etg1def0etf1respectivement. Exprimezgen fonction deg0etg1. Concluez que l’ANF existe et est unique. 4.D´eduisez-enunalgorithmedecalculdegnnoD.mpcosaeze.t´xile 5.Cetalgorithmepermetenfaitdecalculerla“tabledev´erite´”d’unpolynoˆ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( del’op´erationesttrivial.
1
