DFT exponencial complexa - 2 - 4 - 8 valors - Recurrència a 16 valors - towards FFT Funció amb `2` valors, `{f(0), f(1)}` `F(0)=1/2[f(0)+f(1)]` `F(1)=1/2[f(0)-f(1)]` Funció amb `4` valors, `{f(0), f(1)}, f(2), f(3)}` `F(0)=1/4{[f(0)+f(2)]+ 1[f(1)+f(3)]}` `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)]}` Funció amb `8` valors, `{f(0), f(1)}, f(2), f(3)}, f(4), f(5), f(6), f(7)` `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)]}]` Amb tot això podréim fer una recurrència per trobar la fórmula d'una funció amb `16` valors, `{f(0), f(1)}, f(2), f(3)}, f(4), f(5), f(6), f(7), f(8), f(9), f(10), f(11), f(12), f(13), f(14), f(15)` L'ordre de les `f` és: (se separen parell i imparells i es va fent fins que s'acaba. `{f(0), f(2)}, f(4), f(6)}, f(8), f(10), f(12), f(14) - f(1), f(3), f(5), f(7), f(9), f(11), f(13), f(15)` `{f(0), f(4)}, f(8), f(12)} - f(2), f(6), f(10), f(14) - f(1), f(5), f(9), f(13) - f(3), f(7), f(11), f(15)` `{f(0), f(8)}, f(4), f(12)}, f(2), f(10), f(6), f(14), f(1), f(9), f(5), f(13), f(3), f(11), f(7), f(15)}` `F(0)=1/16{[{[f(0)+f(8)]+ 1[f(4)+f(12)]}+1{[f(2)+f(10)]+ 1[f(6)+f(14)]}]+e^((-i2pi0)/16)[{[f(1)+f(9)]+ 1[f(5)+f(13)]}+1{[f(3)+f(11)]+ 1[f(7)+f(15)]}]}` `F(1)=1/16{[{[f(0)-f(8)]-i[f(4)-f(12)]}+(\sqrt{2}/2-i\sqrt{2}/2){[f(2)-f(10)]-i[f(6)-f(14)]}]+e^((-i2pi1)/16)[{[f(1)-f(9)]-i[f(5)-f(13)]}+(\sqrt{2}/2-i\sqrt{2}/2){[f(3)-f(11)]-i[f(7)-f(15)]}]}` `F(2)=1/16{[{[f(0)+f(8)]-1[f(4)+f(12)]}-i{[f(2)+f(10)]-1[f(6)+f(14)]}]+e^((-i2pi2)/16)[{[f(1)+f(9)]-1[f(5)+f(13)]}-i{[f(3)+f(11)]-1[f(7)+f(15)]}]}` `F(3)=1/16{[{[f(0)-f(8)]+i[f(4)-f(12)]}+(-\sqrt{2}/2-i\sqrt{2}/2){[f(2)-f(10)]+i[f(6)-f(14)]}]+e^((-i2pi3)/16)[{[f(1)-f(9)]+i[f(5)-f(13)]}+(-\sqrt{2}/2-i\sqrt{2}/2){[f(3)-f(11)]+i[f(7)-f(15)]}]}` `F(4)=1/16{[{[f(0)+f(8)]+ 1[f(4)+f(12)]}-1{[f(2)+f(10)]+ 1[f(6)+f(14)]}]+e^((-i2pi4)/16)[{[f(1)+f(9)]+ 1[f(5)+f(13)]}-1{[f(3)+f(11)]+ 1[f(7)+f(15)]}]}` `F(5)=1/16{[{[f(0)-f(8)]-i[f(4)-f(12)]}+(-\sqrt{2}/2+i\sqrt{2}/2){[f(2)-f(10)]-i[f(6)-f(14)]}]+e^((-i2pi5)/16)[{[f(1)-f(9)]-i[f(5)-f(13)]}+(-\sqrt{2}/2+i\sqrt{2}/2){[f(3)-f(11)]-i[f(7)-f(15)]}]}` `F(6)=1/16{[{[f(0)+f(8)]-1[f(4)+f(12)]}+i{[f(2)+f(10)]-1[f(6)+f(14)]}]+e^((-i2pi6)/16)[{[f(1)+f(9)]-1[f(5)+f(13)]}+i{[f(3)+f(11)]-1[f(7)+f(15)]}]}` `F(7)=1/16{[{[f(0)-f(8)]+i[f(4)-f(12)]}+(\sqrt{2}/2+i\sqrt{2}/2){[f(2)-f(10)]+i[f(6)-f(14)]}]+e^((-i2pi7)/16)[{[f(1)-f(9)]+i[f(5)-f(13)]}+(\sqrt{2}/2+i\sqrt{2}/2){[f(3)-f(11)]+i[f(7)-f(15)]}]}` `F(8)=1/16{[{[f(0)+f(8)]+ 1[f(4)+f(12)]}+1{[f(2)+f(10)]+ 1[f(6)+f(14)]}]+e^((-i2pi8)/16)[{[f(1)+f(9)]+ 1[f(5)+f(13)]}+1{[f(3)+f(11)]+ 1[f(7)+f(15)]}]}` `F(9)=1/16{[{[f(0)-f(8)]-i[f(4)-f(12)]}+(\sqrt{2}/2-i\sqrt{2}/2){[f(2)-f(10)]-i[f(6)-f(14)]}]+e^((-i2pi9)/16)[{[f(1)-f(9)]-i[f(5)-f(13)]}+(\sqrt{2}/2-i\sqrt{2}/2){[f(3)-f(11)]-i[f(7)-f(15)]}]}` `F(10)=1/16{[{[f(0)+f(8)]-1[f(4)+f(12)]}-i{[f(2)+f(10)]-1[f(6)+f(14)]}]+e^((-i2pi10)/16)[{[f(1)+f(9)]-1[f(5)+f(13)]}-i{[f(3)+f(11)]-1[f(7)+f(15)]}]}` `F(11)=1/16{[{[f(0)-f(8)]+i[f(4)-f(12)]}+(-\sqrt{2}/2-i\sqrt{2}/2){[f(2)-f(10)]+i[f(6)-f(14)]}]+e^((-i2pi11)/16)[{[f(1)-f(9)]+i[f(5)-f(13)]}+(-\sqrt{2}/2-i\sqrt{2}/2){[f(3)-f(11)]+i[f(7)-f(15)]}]}` `F(12)=1/16{[{[f(0)+f(8)]+ 1[f(4)+f(12)]}-1{[f(2)+f(10)]+ 1[f(6)+f(14)]}]+e^((-i2pi12)/16)[{[f(1)+f(9)]+ 1[f(5)+f(13)]}-1{[f(3)+f(11)]+ 1[f(7)+f(15)]}]}` `F(13)=1/16{[{[f(0)-f(8)]-i[f(4)-f(12)]}+(-\sqrt{2}/2+i\sqrt{2}/2){[f(2)-f(10)]-i[f(6)-f(14)]}]+e^((-i2pi3)/16)[{[f(1)-f(9)]-i[f(5)-f(13)]}+(-\sqrt{2}/2+i\sqrt{2}/2){[f(3)-f(11)]-i[f(7)-f(15)]}]}` `F(14)=1/16{[{[f(0)+f(8)]-1[f(4)+f(12)]}+i{[f(2)+f(10)]-1[f(6)+f(14)]}]+e^((-i2pi14)/16)[{[f(1)+f(9)]-1[f(5)+f(13)]}+i{[f(3)+f(11)]-1[f(7)+f(15)]}]}` `F(15)=1/16{[{[f(0)-f(8)]+i[f(4)-f(12)]}+(\sqrt{2}/2+i\sqrt{2}/2){[f(2)-f(10)]+i[f(6)-f(14)]}]+e^((-i2pi15)/16)[{[f(1)-f(9)]+i[f(5)-f(13)]}+(\sqrt{2}/2+i\sqrt{2}/2){[f(3)-f(11)]+i[f(7)-f(15)]}]}` Un cop descoberta la recurrència caldria trobar un programa que ho implementés.