CE00998-3 Coding and TransformationsAssignment 3 : Fast Fourier transformsABBAS Thomas - Group1 - EFREI For Thursday 26th November 20091. Write your own code to find the Fast Fourier transform in the case of N= 8 .tabX0:=array[8]:tabX1:=array[8]:tabX2:=array[8]:m:=3:N:=2^m:
W:=exp(-2*I*Pi/N);print('W'=evalf(exp(-2*I*Pi/N)));Results of W^n from 0 to 7for n from 0 to 7 do print('W'(n)=factor(W^n)); od;Results of X0 using f(x)for a1 from 0 to 1 do
for a0 from 0 to 1 do
for b0 from 0 to 1 do
X0[a1,a0,b0]:=sum(f(4*a2+2*a1+a0)*evalf(W^(4*a2*b0)),a2=0..1);
print(sum(f(4*a2+2*a1+a0)*evalf(W^(4*a2*b0)),a2=0..1));tabX0[a1*4+a0*2+b0]:=sum(f(4*a2+2*a1+a0)*evalf(W^(4*a2*b0)),a2=0..1);
od:od:od:Results of X1 using X0a1:='a1':
for a0 from 0 to 1 do
for b0 from 0 to 1 do
for b1 from 0 to 1 do
X1[a0,b0,b1]:=sum(X0[a1,a0,b0]*evalf(W^(2*a1*(2*b1+b0))),a1=0..1);
print(sum(X0[a1,a0,b0]*evalf(W^(2*a1*(2*b1+b0))),a1=0..1));tabX1[a0*4+b0*2+b1]:=sum(X0[a1,a0,b0]*evalf(W^(2*a1*(2*b1+b0))),a1=0..1);
od:od:od:Results of the Fast Fourier Transform : X2 using X1a0:='a0':
for b0 from 0 to 1 do
for b1 from 0 to 1 do
for b2 from 0 to 1 do
X2[b0,b1,b2]:=sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+b1+b0))),a0=0..1);
print(sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+b1+b0))),a0=0..1));tabX2[b0*4+b1*2+b2]:=sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+b1+b0))),a0=0..1);
od:od:od: