Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmique et Programmation TD n Fast Fourier Transform

De
7 pages
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 ·


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin