1.算法仿真效果
VIVADO2019.2仿真结果如下：
输入信号实部和虚部
FFT变换实部和虚部
IFFT变换实部和虚部恢复原始输入数据
2.算法涉及理论知识概要
快速傅里叶变换(fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
FFT的基本思想是把原始的N点序列，依次分解成一系列的短序列。充分利用DFT计算式中指数因子 所具有的对称性质和周期性质，进而求出这些短序列相应的DFT并进行适当组合，达到删除重复计算，减少乘法运算和简化结构的目的。此后，在这思想基础上又开发了高基和分裂基等快速算法，随着数字技术的高速发展，1976年出现建立在数论和多项式理论基础上的维诺格勒傅里叶变换算法(WFTA）和素因子傅里叶变换算法。它们的共同特点是，当N是素数时，可以将DFT算转化为求循环卷积，从而更进一步减少乘法次数，提高速度。
FFT算法很多，根据实现运算过程是否有指数因子WN可分为有、无指数因子的两类算法。
有指数因子的算法
经典库利-图基算法 当输入序列的长度N不是素数(素数只能被1而它本身整除）而是可以高度分解的复合数，即N=N1N2N3…Nr时，若N1=N2=…=Nr=2，N=2则N点DFT的计算可分解为N=2×N/2，即两个N/2点DFT计算的组合，而N/2点DFT的计算又可分解为N/2=2×N/4，即两个N/4点DFT计算的组合。依此类推，使DFT的计算形成有规则的模式，故称之为以2为基底的FFT算法。同理，当N=4时，则称之为以4为基底的FFT算法。当N=N1·N2时，称为以N1和N2为基底的混合基算法。
在这些算法中，基2算法用得最普遍。通常按序列在时域或在频域分解过程的不同，又可分为两种：一种是时间抽取FFT算法（DIT），将N点DFT输入序列x(n)、在时域分解成2个N/2点序列而x1(n)和x2(n)。前者是从原序列中按偶数序号抽取而成，而后者则按奇数序号抽取而成。DIT就是这样有规律地按奇、偶次序逐次进行分解所构成的一种快速算法。
分裂基算法(RSFFT) 1984年由P．杜哈美尔和H．赫尔曼等导出的一种比库利图基算法更加有效的改进算法，其基本思想是在变换式的偶部采用基2算法，在变换式的奇部采用基4算法。优点是具有相对简单的结构，非常适用于实对称数据，对长度N=2能获得最少的运算量(乘法和加法），所以是选用固定基算法中的一种最佳折衷算法。
3.Verilog核心程序
reg [15:0]cnts;
always @(posedge i_clk or posedge i_rst)
begin
if(i_rst)
begin
cnts <= 16'd0;
i_real_dat <= 16'b1111110000000000;
i_imag_dat <= 16'b0000000000111111;
end
else begin
if(i_enable == 1'b1)
begin
cnts <= cnts+16'd1;
if(cnts>=16'd17 & cnts<=16'd512-16)
begin
i_real_dat <= ~i_real_dat;
if (cnts[2]==1'b1)
i_imag_dat <= ~i_imag_dat;
else
i_imag_dat <= i_imag_dat;
end
end
else begin
cnts <= 16'd0;
i_real_dat <= 16'b1111110000000000;
i_imag_dat <= 16'b0000001111111111;
end
end
end
...........................................................................
FFT_tops FFT_tops_u(
.i_clk (i_clk),
.i_rst (i_rst),
.i_before_fft(i_before_fft),
.i_last_fft (i_last_fft),
.i_enable (i_enable),
.i_real_dat (i_real_dat),
.i_imag_dat (i_imag_dat),
.o_start (o_start),
.o_ends (o_ends),
.o_enable (o_enable),
.o_real_ifft (o_real_ifft),
.o_imag_ifft (o_imag_ifft)
);
initial
begin
i_before_fft2=1'b0;
#53540
i_before_fft2=1'b1;
#40
i_before_fft2=1'b0;
end
IFFT_tops IFFT_tops_u(
.i_clk (i_clk),
.i_rst (i_rst),
.i_before_fft(o_start),
.i_last_fft (o_ends),
.i_enable (o_enable),
.i_real_dat (o_real_ifft[31-9:7]),
.i_imag_dat (o_imag_ifft[31-9:7]),
.o_start (o_start2),
.o_ends (o_ends2),
.o_enable (o_enable2),
.o_real_ifft (o_real_ifft2),
.o_imag_ifft (o_imag_ifft2)
);
initial
begin
i_clk = 1'b1;
i_rst = 1'b1;
#10000
i_rst = 1'b0;
end
always #10 i_clk=~i_clk;
endmodule
A794
