The basic step of the Cooley–Tukey FFT for general factorizations can be viewed as re-
interpreting a 1d DFT as something like a 2d DFT. The 1d input array of length"N"="N
1
N
2
"is
reinterpreted as a 2d"N
1
×N
2
"matrix stored in"column-major order. One performs smaller 1d DFTs
along the"N
2
"direction (the non-contiguous direction), then multiplies by phase factors (twiddle
factors), and finally performs 1d DFTs along the"N
1
"direction. The transposition step can be
performed in the middle, as shown here, or at the beginning or end. This is done recursively for the
smaller transforms.
上面的算法很有意思主要是可以通过计算 M*N 点的 FFT
这个算法有个极大的好处就是除了核心的 M 个 N 点 FFT 和 N 个 M 点的 FFT 可以用高效单元
实现
其他的数据搬移可以用 D MA 很好的优化,
而且计算的 FFT 核心点数很小，适合计算大规模 FFT 时候高速的 cache 优化
我用 matlab 做了实现供参考可以设置 M，N 就可以计算 M*N 点的 FFT
M=8;
N=4;
len=M*N;
w=exp(-2*pi*j/len);
inputaa=1:len;
for index1=1:N
for index2=1:M
W(index1,index2)=w^((index1-1)*(index2-1));
end
评论0
最新资源