CE00998-3 Coding and Transformations Assignment 3 : Fast Fourier transforms ABBAS Thomas - Group1 - EFREI For Thursday 26th November 2009 2. Illustrate the output of the algorithm in the cases where (a) f[j] = j + 1, i = 0...7 tabX0:=array[8]:tabX1:=array[8]:tabF:=array[8]: m:=3:N:=2^m: f:=j->j+1;

Zio2I0kiakc2IkYlNiRJKW9wZXJhdG9yR0YlSSZhcnJvd0dGJUYlLCY5JCIiIkYrRitGJUYlRiU=

W:=exp(-2*I*Pi/N);print('W'=evalf(exp(-2*I*Pi/N)));

LCYqJCIiIyMiIiJGJEYlKiZeIyMhIiJGJEYmRiRGJUYm

L0kiV0c2Il4kJCIrNXkxcnEhIzUkISs1eTFycUYo

Results of W^n from 0 to 7 for a from 0 to 7 do print('W'^a=factor(W^a)); od;

LyIiIkYj

L0kiV0c2IiwmKiQiIiMjIiIiRidGKComXiMjISIiRidGKUYnRihGKQ==

LyokSSJXRzYiIiIjXiMhIiI=

LyokSSJXRzYiIiIkLCYqJl4jIyEiIiIiIyIiIkYsI0YtRixGLSokRixGLkYq

LyokSSJXRzYiIiIlISIi

LyokSSJXRzYiIiImLCYqJCIiIyMiIiJGKSMhIiJGKSomXiNGKkYrRilGKkYr

LyokSSJXRzYiIiInXiMiIiI=

LyokSSJXRzYiIiIoLCYqJl4jIyIiIiIiI0YrRixGKkYrKiRGLEYqRio=

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('X0'[a1*4+a0*2+b0]=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:

LyZJI1gwRzYiNiMiIiEkIiInRic=

LyZJI1gwRzYiNiMiIiIkISsmKioqKioqKlIhIio=

LyZJI1gwRzYiNiMiIiMkIiIpIiIh

LyZJI1gwRzYiNiMiIiQkISslKioqKioqKlIhIio=

LyZJI1gwRzYiNiMiIiUkIiM1IiIh

LyZJI1gwRzYiNiMiIiYkISskKioqKioqKlIhIio=

LyZJI1gwRzYiNiMiIickIiM3IiIh

LyZJI1gwRzYiNiMiIigkISsjKioqKioqKlIhIio=

Results of X1 using X0 a1:='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('X1'[a0*4+b0*2+b1]=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:

LyZJI1gxRzYiNiMiIiEkIiM7Ric=

LyZJI1gxRzYiNiMiIiIkISsqKSoqKioqKlIhIio=

LyZJI1gxRzYiNiMiIiNeJCQhKyYqKioqKioqUiEiKiQiKyIqKioqKioqUkYr

LyZJI1gxRzYiNiMiIiReJCQhKyYqKioqKioqUiEiKiQhKygpKioqKioqUkYr

LyZJI1gxRzYiNiMiIiUkIiM/IiIh

LyZJI1gxRzYiNiMiIiYkISoqKioqKioqUiEiKQ==

LyZJI1gxRzYiNiMiIideJCQhKyUqKioqKioqUiEiKiQiKyEqKioqKioqUkYr

LyZJI1gxRzYiNiMiIiheJCQhKyUqKioqKioqUiEiKiQhKycpKioqKioqUkYr

Results of the Fourier Transform : F using X1 a0:='a0': for b0 from 0 to 1 do for b1 from 0 to 1 do for b2 from 0 to 1 do F[b0,b1,b2]:=sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+2*b1+b0))),a0=0..1); print('F'[b2*4+b1*2+b0]=sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+2*b1+b0))),a0=0..1));tabF[b2*4+b1*2+b0]:=sum(X1[a0,b0,b1]*evalf(W^(a0*(4*b2+2*b1+b0))),a0=0..1); od:od:od:

LyZJIkZHNiI2IyIiISQiI09GJw==

LyZJIkZHNiI2IyIiJSQhKikqKioqKipSISIp

LyZJIkZHNiI2IyIiI14kJCErKikqKioqKipSISIqJCIrKSkqKioqKipSRis=

LyZJIkZHNiI2IyIiJ14kJCErKikqKioqKipSISIqJCErJSkqKioqKipSRis=

LyZJIkZHNiI2IyIiIl4kJCErKSoqKioqKipSISIqJCIrR1Umb2wqRis=

LyZJIkZHNiI2IyIiJl4kJCErIyoqKioqKipSISIqJCErU1Umb2wiRis=

LyZJIkZHNiI2IyIiJF4kJCErKikqKioqKipSISIqJCIrV1Umb2wiRis=

LyZJIkZHNiI2IyIiKF4kJCErLCsrK1MhIiokISs3VSZvbCpGKw==

Plot of the Fourier Transform : FastFT:=[seq ([x,abs(tabF[x])],x=0..7)]: plot(FastFT,style=point);

LSUlUExPVEc2Ji0lJ0NVUlZFU0c2JDcqNyQkIiIhISIiJCIkZyQhIiI3JCQiIzUhIiIkIipQXV8vIiEiKDckJCIjPyEiIiQiK0xVJm9sJiEiKjckJCIjSSEiIiQiKyp5byZIViEiKjckJCIjUyEiIiQiKikqKioqKipSISIpNyQkIiNdISIiJCIqem8mSFYhIik3JCQiI2chIiIkIipCYW9sJiEiKTckJCIjcSEiIiQiK28uRFg1ISIpLSUmQ09MT1JHNiYlJFJHQkckIiM1ISIiJCIiISEiIiQiIiEhIiItJStBWEVTTEFCRUxTRzYkUSE2IlEhNiItJSZTVFlMRUc2IyUmUE9JTlRHLSUlUk9PVEc2Jy0lKUJPVU5EU19YRzYjJCIkKyUhIiItJSlCT1VORFNfWUc2IyQiJCsiISIiLSUtQk9VTkRTX1dJRFRIRzYjJCIlK04hIiItJS5CT1VORFNfSEVJR0hURzYjJCIlIVskISIiLSUpQ0hJTERSRU5HNiI=