一、DFT(傅里叶变换)
先说一下自己的编写顺序：
1、先用.m文件编写出DFT
2、再将不同值的x(n)和N代入对比变换
3、将多组相同x(n)的用IDFT和DFT的混合图像表示出来，进行对比分析
编写DFT的流程
解释：N和x(n)是输入，X(k)是输出。其中W中的n和k可以建立两个循环嵌套，输出最后的数列X(k)。
不过目前我有一个疑问，那就是如何在这个循环中使其连续输出X(k)形成一个序列，而不是一个最终的数值？
我选择将每一个 数值X(k)转换成一行N-1列的矩阵X(k),然后将其们相加即可得到最终的X（k）
第一次写的DFT函数的代码出现了问题，从网上看见一个下图代码，觉得自己原先的思维太累赘了，索性抛弃后进行新分析。我觉得下面这个代码写的很精彩，对该算法理解的很不错，而且数学语言用的很灵活，长见识了
DFT代码：
function Xk=dft(xn,N)
n=0:N-1; #x的向量个数
k=0:N-1; #k的向量个数
WN=exp(-j*2*pi/N); #不加添加剂的W
nk=n’*k; #’*的意思是先将n转置，再乘k；所得出的矩阵，行=x(n）级同n，列=同k或者说n值不同k相同
WNnk=WN.^nk;
Xk=xn*WNnk; #行向量x(n)×W的第a列后会得出一个数值（非数组），此数值=同一个k（即X(k)中的那个）在∑x(n)×W（不同n），得出的
end
命令窗口
N=8;
x=[ones(1,5),zeros(1,N-5)];
n=0:N-1;
X=dft_succeeded(x,N);
magX=abs(X); #计算幅值
k=0：N-1；
subplot(2,2,1);stem(n,x);
subplot(2,2,2);stem(k,magX);
此为命令窗口中输入的代码。
1.matlab中默认数组为行向量
图形：
————————————————————————————————————————
二、FFT算法
首先，我需要明确
什么是FFT？
是通过什么方式缩减计算量的？
通过W，那么W又是如何缩减的？
通过等效，那么怎么在代码中实现主动等效缩减？通过W的周期性和对称性实现。
理解以后，写代码很快，但是调试过程会需要一些时间。
如果想要在一个脚本文件定义的函数1里面，调用另一个.m文件中的函数，只需要将这两个.m文件放在同一个目录里：
（目录：就是“路径”的意思）
myfft：
function [Y]=myfft(x,N)
x_odd=x(1:2:end); #取x函数的奇数
x_even=x(2:2:end); #取x函数的偶数
X1=dft_succeeded(x_even,N/2);
X2=dft_succeeded(x_odd,N/2);
k=0;
Z=zeros(1,N); #生成一个一行N列的全0矩阵
for k=1:N/2
Y1=X2(k)*exp(-1i*k*2*pi/N);
Xk=X1(k)+Y1；
Xk2=X1(k)-Y1；
Z(k)=Xk;
Z(k+N/2)=Xk2；#一开始Z(k)括号内表示出错了，错误表示成“2k-1”和“2k”，不过看了蝶形图后就改正过来了。原来对应的是"k""k+N/2"的关系
end
Y=Z；
end
命令窗口代码：
n=0:7;
x=[zeros(1,4),ones(1,4)];
subplot(2,1,1);
stem(n,x);
N=32; #N有32个
y=[x,zeros(1,32-8)];
i=0:N-1;
Y=myfft(y,N);
ax=abs(Y); //取正值
subplot(2,1,2);
stem(i,ax);
图像：
三、比较mydft和myfft的时间
1.当N分别为210，220，225时，根据实验内容1，2所编写的函数计算运行时间mydft与myfft，同时计算两者实际用时之并，并将结果与公式（3）的理论计算结果进行比较；
在matlab中实现计数功能
在程序两端加上tic和toc：记住是加在同一个'》'里面
tic的作用是开始计数，而toc的作用是一个计数结束，所以可以多次计数
1）N=210
mydft: t=0.339745s
myfft: t= 0.169710s
比值：△t=2.00189<理论计算：136.467
有意思的是，同一个程序代码执行后，所显示的时间都不同，原因是：
tic/toc测量到的数值与操作系统本身的时间精度和运行代码时系统的负载有很大关系。如果需要一个更准确的时间估计的话，最好是将那个函数运行多次取平均值。
我发现我的电脑最大能够处理N=2^14的mydft，再大的话就超内存了
2）N=2^12
mydft: t=5.368491 s
myfft: t= 2.602924s
比值：△t=2.0624847<理论计算：455.05556s
3）N=2^13
mydft: t=24.024326s
myfft: t=10.573246s
比值：△t=2.2721807475<理论计算：840.153846s
4）N=2^14
mydft: t= 115.032158 s
myfft: t=45.586973
比值：△t=2.5233559<理论计算：1560.33333s
比较后发现，随着N的增大，t(DFT)/t(FFT)的比值是一直2大，但在2附近。而且计算机实际运算的时间远远小于理论计算得出的时间。
四、myfft 时间 vs. matlab的fft时间
5、Matlab函数库中已有fft函数用于计算快速傅立叶变换，当N分别为210，213,214时，试分别用函数myfft和fft计算的傅立叶变换，并对两者的时间进行比较。
1）N=210
myfft: t= 0.169710s
fft: t=0.065144 s
2）N=213
myfft: t=10.573246s
fft: t=0.051153 s
3）N=215
myfft: t= 240.854369s
fft: t= 0.051036 s
3）N=220&25
fft:
1.对于myfft来说，最大能够到215; 但是fft却可以运算到230。可以观察到matlab自带的fft运算速度远远高于myfft。
2.而且两者的波形也不一样，fft的波形和mydft的波形一致。
五、思考题
1、当x（n）的数据长度不是2的整数幂时，计算FFT该怎么处理？
1）若length(x(n)) < N，则通过x=[x,zeros(1,N-n)]，在x后面补0，补到N即可。假设N是2的整数幂
2）若length(x(n)) > N，则通过x=x（1:N），取x中的整数幂个数值形成满足条件的x。
2、是否还有其他的FFT的快速计算算法？
