|
Funció amb `4` valors, `{f(0), f(1)}, f(2), f(3)}` Perň recordem: `F(n)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pi2kn)/4)+e^((-i2pin)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pi2kn)/4)]` `F(n)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pikn)/2)+e^((-i2pin)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pikn)/2)]`
`F(1)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik1)/2)+e^((-i2pi1)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik1)/2)]` `F(2)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik2)/2)+e^((-i2pi2)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik2)/2)]` `F(3)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik3)/2)+e^((-i2pi3)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik3)/2)]`
`F(1)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik1)/2)+e^((-i2pi1)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik1)/2)]` `F(2)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik0)/2)+e^((-i2pi2)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik0)/2)]` `F(3)=1/4[\sum_{k=0}^1 f(2k)e^((-i2pik1)/2)+e^((-i2pi3)/4)\sum_{k=0}^1 f(2k+1)e^((-i2pik1)/2)]`
`F(1)=1/4{f(0)e^((-i2pi0ˇ1)/2)+f(2)e^((-i2pi1ˇ1)/2)+e^((-i2pi1)/4)[f(1)e^((-i2pi0.1)/2)+f(3)e^((-i2pi1.1)/2)]}` `F(2)=1/4{f(0)e^((-i2pi0.0)/2)+f(2)e^((-i2pi1.0)/2)+e^((-i2pi2)/4)[f(1)e^((-i2pi0.0)/2)+f(3)e^((-i2pi1.0)/2)]}` `F(3)=1/4{f(0)e^((-i2pi0ˇ1)/2)+f(2)e^((-i2pi1ˇ1)/2)+e^((-i2pi3)/4)[f(1)e^((-i2pi0.1)/2)+f(3)e^((-i2pi1.1)/2)]}` Que si ens hi fixem veiem que tenim dues FT de dues parelles de valors, les parells `{f(0), f(2)`} i les imparells `{f(1), f(3)}`. O sigui, per calcular, `F(0), F(1)` cal calcular l'FT de dues dades `f(0), f(2)` i l'FT de `f(1), f(3)`, també dues dades, multiplicades per `e^((-i2pin)/4)` i per calcular, `F(2), F(3)`, el mateix.
`F(1)=1/4{[f(0)-f(2)]+ e^((-i2pi1)/4)[f(1)-f(3)]}` `F(2)=1/4{[f(0)+f(2)]+ e^((-i2pi2)/4)[f(1)+f(3)]}` `F(3)=1/4{[f(0)-f(2)]+ e^((-i2pi3)/4)[f(1)-f(3)]}` Recordem: `e^((-i2pi1)/4)= e^((-ipi)/2)= cos(pi/2)-isin(pi/2)=-i`
`F(1)=1/4{[f(0)-f(2)]-i[f(1)-f(3)]}` `F(2)=1/4{[f(0)+f(2)]-1[f(1)+f(3)]}` `F(3)=1/4{[f(0)-f(2)]+i[f(1)-f(3)]}` |