DFT (Discret Fourier Transform) La sèrie de Fourier o desenvolupament de Fourier d'una funció f(x) és defineix: `a_o + \sum_{n=1}^\infty[a_n cos((npix)/l)] + b_n sin((npix)/l)]` On els coeficients de Fourier `a_n` i `b_n` es calculan: `a_n = 1/l\int_-l^l cos((npix)/l) · f(x) dx` i `b_n = 1/l\int_-l^l sin((npix)/l) · f(x) dx` On `2l` és el període de la funció 0-Si la funció és discreta i suposem que cada període té `n` valors, `{f(0), f(1), ..., f(n-1)}` L'anterior expressió queda: `a_n=1/(n/2)\sum_{k=0}^(n-1) cos((npi k)/2)f(k)` i `b_n=1/(n/2)\sum_{k=0}^(n-1) sin((npi k)/2)f(k)` 1-Exemple: cada període té `4` valors, `{f(0), f(1), f(2), f(3)}` L'anterior expressió queda: `a_n=1/2\sum_{k=0}^3 cos((npi k)/2)f(k)` i `b_n=1/2\sum_{k=0}^3 sin((npi k)/2)f(k)` Si ho posem en notació matricial pel càlcul dels `a_n`. $$ \begin{pmatrix} a_0\\\ a_1\\\ a_3\\\ a_4 \end{pmatrix}= \frac{1}{2} \begin{pmatrix} cos(\frac{1\pi 1}{2})&&cos(\frac{1\pi 2}{2})&&cos(\frac{1\pi 3}{2})&&cos(\frac{1\pi 4}{2})\\\ cos(\frac{2\pi 1}{2})&&cos(\frac{2\pi 2}{2})&&cos(\frac{2\pi 3}{2})&&cos(\frac{2\pi 4}{2})\\\ cos(\frac{3\pi 1}{2})&&cos(\frac{3\pi 2}{2})&&cos(\frac{3\pi 3}{2})&&cos(\frac{3\pi 4}{2})\\\ cos(\frac{4\pi 1}{2})&&cos(\frac{4\pi 2}{2})&&cos(\frac{4\pi 3}{2})&&cos(\frac{4\pi 4}{2}) \end{pmatrix}· \begin{pmatrix} f(0)\\\ f(1)\\\ f(2)\\\ f(3) \end{pmatrix} $$ Si ho simplifiquem un xic: $$ \begin{pmatrix} a_0\\\ a_1\\\ a_3\\\ a_2 \end{pmatrix}= \frac{1}{2} \begin{pmatrix} cos(\frac{\pi}{2})&&cos(\pi)&&cos(\frac{3\pi}{2})&&cos(2\pi)\\\ cos(\pi)&&cos(2\pi)&&cos(3\pi)&&cos(4\pi)\\\ cos(\frac{3\pi}{2})&&cos(3\pi)&&cos(\frac{9\pi}{2})&&cos(6\pi)\\\ cos(2\pi)&&cos(4\pi)&&cos(6\pi)&&cos(8\pi) \end{pmatrix}· \begin{pmatrix} f(0)\\\ f(1)\\\ f(2)\\\ f(3) \end{pmatrix} $$ Que de fet és: $$ \begin{pmatrix} a_0\\\ a_1\\\ a_2\\\ a_3 \end{pmatrix}= \frac{1}{2} \begin{pmatrix} cos(\frac{\pi}{2})·f(0)+cos(\pi)·f(1)+cos(\frac{3\pi}{2})·f(2)+cos(2\pi)·f(3)\\\ cos(\pi)·f(0)+cos(2\pi)·f(1)+cos(3\pi)·f(2)+cos(4\pi)·f(3)\\\ cos(\frac{3\pi}{2})·f(0)+cos(3\pi)·f(1)+cos(\frac{9\pi}{2})·f(2)+cos(6\pi)·f(3)\\\ cos(2\pi)·f(0)+cos(4\pi)·f(1)+cos(6\pi)·f(2)+cos(8\pi)·f(3) \end{pmatrix} $$ Són en total `4` vegades `4` multiplicacions i `3` sumes. `4·4=16` multiplicacions i `4·3=12` sumes. Cal recordar que també cal calcular els coeficients `b_n` $$ \begin{pmatrix} b_0\\\ b_1\\\ b_2\\\ b_3 \end{pmatrix}= \frac{1}{2} \begin{pmatrix} sin(\frac{\pi}{2})·f(0)+sin(\pi)·f(1)+sin(\frac{3\pi}{2})·f(2)+sin(2\pi)·f(3)\\\ sin(\pi)·f(0)+sin(2\pi)·f(1)+sin(3\pi)·f(2)+sin(4\pi)·f(3)\\\ sin(\frac{3\pi}{2})·f(0)+sin(3\pi)·f(1)+sin(\frac{9\pi}{2})·f(2)+sin(6\pi)·f(3)\\\ sin(2\pi)·f(0)+sin(4\pi)·f(1)+sin(6\pi)·f(2)+sin(8\pi)·f(3)\end{pmatrix} $$ O sigui cal comptar el doble d'operacions. De l'ordre de `n^2` multiplicacions (dobles) i `n(n-1)` sumes (dobles). Si un mira el resultat veu que hi ha moltes coses redundants, per exemple les últimes columnes `cos(2pin).f(3)=f(3)` i `sin(2pin).f(3)=0` I una altra qüestió, el, "divideix i venceràs" que aquí no es evident, però si canviem la forma de calcular l'FFT s'aconsegueix veure-ho. Aquesta nova forma és, la Transformada de Fourier fent servir la notació exponencial complexa. DFT - Forma exponencial complexa