DFT exponencial complexa - 8 valors - towards FFT Funció amb `8` valors, `{f(0), f(1)}, f(2), f(3)}, f(4), f(5), f(6), f(7)` `F(n)=1/8\sum_{k=0}^7 f(k)e^((-i2pikn)/8)` Perň recordem: `F(n)=1/8[\sum_{k=0}^3 f(2k)e^((-i2pi2kn)/8)+e^((-i2pin)/8)\sum_{k=0}^3 f(2k+1)e^((-i2pi2kn)/8)]` `F(n)=1/8[\sum_{k=0}^3 f(2k)e^((-i2pikn)/4)+e^((-i2pin)/8)\sum_{k=0}^3 f(2k+1)e^((-i2pikn)/4)]` Que si ens hi fixem veiem que tenim dues FT de `4` valors, les parells `{f(0), f(2), f(4), f(6)`} i les imparells `{f(1), f(3)}, f(5), f(7)`. O sigui, per calcular, `F(0), F(1), F(2), F(3)` cal calcular l'FT de quatre dades, `f(0), f(2), f(4), f(6)` i l'FT de `f(1), f(3), f(5), f(7)`, també, quatre dades, multiplicades per `e^((-i2pin)/8)` i per calcular, `F(4), F(5), F(6), F(7)`, el mateix. `F(0)=1/8[{[f(0)+f(4)]+ 1[f(2)+f(6)]}+e^((-i2pi0)/8){[f(1)+f(5)]+ 1[f(3)+f(7)]}]` `F(1)=1/8[{[f(0)-f(4)]-i[f(2)-f(6)]}+e^((-i2pi1)/8){[f(1)-f(5)]-i[f(3)-f(7)]}]` `F(2)=1/8[{[f(0)+f(4)]-1[f(2)+f(6)]}+e^((-i2pi2)/8){[f(1)+f(5)]-1[f(3)+f(7)]}]` `F(3)=1/8[{[f(0)-f(4)]+i[f(2)-f(6)]}+e^((-i2pi3)/8){[f(1)-f(5)]+i[f(3)-f(7)]}]` `F(4)=1/8[{[f(0)+f(4)]+ 1[f(2)+f(6)]}+e^((-i2pi4)/8){[f(1)+f(5)]+ 1[f(3)+f(7)]}]` `F(5)=1/8[{[f(0)-f(4)]-i[f(2)-f(6)]}+e^((-i2pi5)/8){[f(1)-f(5)]-i[f(3)-f(7)]}]` `F(6)=1/8[{[f(0)+f(4)]-1[f(2)+f(6)]}+e^((-i2pi6)/8){[f(1)+f(5)]-1[f(3)+f(7)]}]` `F(7)=1/8[{[f(0)-f(4)]+i[f(2)-f(6)]}+e^((-i2pi7)/8){[f(1)-f(5)]+i[f(3)-f(7)]}]` Recordem: `e^((-i2pi1)/8)= e^((-ipi)/4)= cos(pi/4)-isin(pi/4)=\sqrt{2}/2-i\sqrt{2}/2`, ... `F(0)=1/8[{[f(0)+f(4)]+ 1[f(2)+f(6)]}+1{[f(1)+f(5)]+ 1[f(3)+f(7)]}]` `F(1)=1/8[{[f(0)-f(4)]-i[f(2)-f(6)]}+(\sqrt{2}/2-i\sqrt{2}/2){[f(1)-f(5)]-i[f(3)-f(7)]}]` `F(2)=1/8[{[f(0)+f(4)]-1[f(2)+f(6)]}-i{[f(1)+f(5)]-1[f(3)+f(7)]}]` `F(3)=1/8[{[f(0)-f(4)]+i[f(2)-f(6)]}+(-\sqrt{2}/2-i\sqrt{2}/2){[f(1)-f(5)]+i[f(3)-f(7)]}]` `F(4)=1/8[{[f(0)+f(4)]+ 1[f(2)+f(6)]}-1{[f(1)+f(5)]+ 1[f(3)+f(7)]}]` `F(5)=1/8[{[f(0)-f(4)]-i[f(2)-f(6)]}+(-\sqrt{2}/2+i\sqrt{2}/2){[f(1)-f(5)]-i[f(3)-f(7)]}]` `F(6)=1/8[{[f(0)+f(4)]-1[f(2)+f(6)]}+i{[f(1)+f(5)]-1[f(3)+f(7)]}]` `F(7)=1/8[{[f(0)-f(4)]+i[f(2)-f(6)]}+(\sqrt{2}/2+i\sqrt{2}/2){[f(1)-f(5)]+i[f(3)-f(7)]}]`