快速傅里叶变换FFT的FPGA设计与实现学生姓名郭衡班级电科1704学号17419002064指导教师谭会生成绩2020年5 月20 日快速傅里叶变换FFT 的设计与实现一、研究项目概述非周期性连续时间信号x(t)的傅里叶变换可以表示为：=)(ϖX dt tj et x ⎰∞∞--1)(ϖ，式中计算出来的是信号x(t)的连续频谱。
但是，在实际的控制系统中能够式中计算出来的是信号x(t)的连续频谱。
但是，在实际的控制系统中能够算信号x(t)的频谱。
有限长离散信号x(n)，n=0，1，…，N-1的DFT 定义为：∑-=-=-==102,1.....10)()(N n Nj N knNeW N k W n x K X π、、。
可以看出，DFT 需要计算大约N2次乘法和N2次加法。
当N 较大时，这个计算量是很大的。
利用WN 的对称性和周期性，将N 点DFT 分解为两个N ／2点的DFT ，这样两个N ／2点DFT 总的计算量只是原来的一半，即(N ／2)2+(N ／2)2=N2／2，这样可以继续分解下去，将N ／2再分解为N ／4点DFT 等。
对于N=2m 点的DFT 都可以分解为2点的DFT ，这样其计算量可以减少为(N ／2)log2N 次乘法和Nlog2N 次加法。
图1为FFT 与DFT-所需运算量与计算点数的关系曲线。
由图可以明显看出FFT 算法的优越性。
图1 FFT 与DFT 所需乘法次数比较X[1]将x(n)分解为偶数与奇数的两个序列之和，即x(n)=x1(n)+x2(n)。
x1(n)和x2(n)的长度都是N ／2，x1(n)是偶数序列，x2(n)是奇数序列，则∑∑=--=-=+2)12(1202)1.....,0()(2)(1)(N n kn N N n km N N k W n x W n x K X所以)1...,0()(2)(1)(1222120-=+=∑∑-=-=N k W n x W W n x K X N n km N k N km N Nn由于kmN N jkm Njkm NW eeW2/2/2222===--ππ，则)1.....,0)((2)(1)(2)(1)(122/1202/-=+=+=∑∑-=-=N k k X W k X W n x W W n x K X kN N n km N k N Nn kn N其中X1(k)和X2(k)分别为x1(n)和x2(n)的N ／2点DFT 。
由于X1(k)和X2(k)均以N ／2为周期，且WNk+N/2=-WNk ，所以X(k)又可表示为：)12/....,1,0)((2)(1)(-=+=N k k X W k X K X k N)12/....,1,0)((2)(1)2/(-=-=+N k k X W k X N K X k NFFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。
FFT不是DFT的近似运算，它们完全是等效的。
二、研究项目设计方案比较FFT处理器的理论基础，比较了各种算法实现的运算量及复杂度，结合硬件实现结构与可配置单元。
选择了改良后的基4蝶形算法实现处理器的设计。
设计采用四路并行数据传输，在蝶形单元内部采用四级流水，提高了系统处理速度，根据基带项目数据流的特点，输入输出均采用了兵乓RAM的处理，有效地实现了对连续数据流的处理；通过对系统要求的三种不同点数64点、256点、1024点的运算规律分析，设计了可变点的配置方案，该方案通过控制选择各级蝶形运算及复用蝶形单元，大大地缩减了硬件开销。
三、研究项目系统结构设计ram、旋转ram输四、系统主要VHDL源程序设计fft顶层文件的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity fft_top isport(clock_main:in std_logic;init:in std_logic;ip , op ,fft_en ,enbw , enbor ,rom_en,romgen_en:out std_logic;butterfly_data: out std_logic_vector(10 downto 0);y1,y2:out std_logic;c1_c1,c2_c2,c3_c3,c0_c1,c0_c2,c1_c3,c2_c3: out std_logic);end fft_top;architecture rtl of fft_top issignal incr,staged:std_logic;signal clear:std_logic;signal butterfly_iod:std_logic_vector(10 downto 0);signal stage :std_logic_vector(3 downto 0);signal iod ,iod0,io_mode,fftd:std_logic;signal preset,disable,c0_en,reset_count: std_logic ;signal clk_count : std_logic_vector(2 downto 0) ;signal waves: std_logic_vector(3 downto 0);signal rom_add : std_logic_vector(9 downto 0) ;signal data_rom: std_logic_vector(11 downto 0) ;signal out_data: std_logic_vector(11 downto 0) := (others => '0') ; type state_values is (st0 , st1 , st2 , st3) ;signal pres_state1 , next_state1 : state_values ;signal c0_c0: std_logic;component butterflyport(clk: in std_logic;c0,c1,c2,c3,c01,c02,c13,c23: in std_logic;clear: in std_logic;X,rom_data: in std_logic_vector(11 downto 0);Y:out std_logic_vector(11 downto 0));end component;component cont_genport (con_staged , con_iod , con_fftd , con_init : in std_logic ;con_ip , con_op , con_iomode , con_fft : out std_logic ;con_enbw , con_enbor , c0_enable , con_preset : out std_logic ; con_clear , disable : out std_logic ;c0 , clock_main : in std_logic ;en_rom , en_romgen , reset_counter : out std_logic ; con_clkcount : in std_logic_vector(2 downto 0) ) ; end component;component romadd_gen isport (io_rom,c0,c1,c2,c3 : in std_logic ;stage_rom : in std_logic_vector(3 downto 0) ;butterfly_rom : in std_logic_vector(10 downto 0) ;romadd : out std_logic_vector(9 downto 0) ;romgen_en : in std_logic );end component ;component rommPORT(address : IN STD_LOGIC_VECTOR (9 DOWNTO 0);clken : IN STD_LOGIC ;clock : IN STD_LOGIC ;q : OUT STD_LOGIC_VECTOR (11 DOWNTO 0) );end component;component reg_dpramport (data_fft , data_io : in std_logic_vector (11 downto 0); q_out : out std_logic_vector (11 downto 0);clock_main , io_mode : in std_logic;wr_en,re_en: in std_logic;waddress: in std_logic_vector(10 downto 0);raddress: in std_logic_vector(10 downto 0));end component ;component but_genport (add_incr , add_clear , stagedone : in std_logic ;but_butterfly : out std_logic_vector(10 downto 0) ) ; end component ;component stage_genport (add_staged , add_clear : in std_logic ;st_stage : out std_logic_vector(3 downto 0) ) ;end component ;component iod_stagedport(but_fly : in std_logic_vector(10 downto 0) ;stage_no : in std_logic_vector(3 downto 0) ;add_incr , io_mode : in std_logic ;add_iod , add_staged , add_fftd : out std_logic ;butterfly_iod : out std_logic_vector(10 downto 0) ) ; end component ;component baseindexport(ind_butterfly: in std_logic_vector(10 downto 0);ind_stage: in std_logic_vector(3 downto 0);add_fft: in std_logic;fftadd_rd: out std_logic_vector(10 downto 0);c0,c1,c2,c3: in std_logic);end component ;component ioadd_genport (io_butterfly : in std_logic_vector(10 downto 0) ;add_iomode , add_ip , add_op : in std_logic ;base_ioadd : out std_logic_vector(10 downto 0) ) ; end component ;component mux_addport (a ,b : in std_logic_vector(10 downto 0) ;sel : in std_logic ;q : out std_logic_vector(10 downto 0) ) ;end component ;component ram_shiftport (data_in : in std_logic_vector(10 downto 0) ;clock_main : in std_logic ;data_out : out std_logic_vector(10 downto 0) ) ;end component ;component cyclesport (clock_main , preset , c0_en , cycles_clear : in std_logic ; waves : out std_logic_vector(3 downto 0) ) ;end component;component and_gatesport (waves_and : in std_logic_vector(3 downto 0) ;preset,clock_main , c0_en : in std_logic ;c0,c1,c2,c3,c0_c1,c2_c3,c0_c2,c1_c3 : out std_logic );end component ;component counterport (c : out std_logic_vector(2 downto 0) ;disable , clock_main , reset : in std_logic) ;end component ;component mult_clockport (clock_main , mult1_c0 , mult1_iomode , mult_clear : in std_logic ; mult1_addincr : out std_logic ) ;end component ;component level0port (data_edge : in std_logic;trigger_edge : in std_logic;edge_out : out std_logic);end component;beginfft_but : but_gen port map (incr , clear , staged ,butterfly_iod(10 downto 0));fft_stage : stage_gen port map (staged , clear , stage(3 downto 0)) ; iod_stgd : iod_staged port map(butterfly_iod(10 downto 0),stage(3 downto 0),incr,io_mode,iod,staged,fftd,butterfly_data(10 downto 0)) ;y1<=iod;y2<= clear;control : cont_gen port map (staged , iod , fftd , init , ip , op , io_mode ,fft_en ,enbw , enbor , c0_en , preset , clear , disable , c0_c0 ,clock_main ,rom_en,romgen_en,reset_count,clk_count);cyc: cycles port map(clock_main,preset,c0_en,clear,waves(3 downto 0)); wave: and_gates port map(waves(3 downto 0),preset,clock_main,c0_en,c0_c0,c1_c1,c2_c2,c3_c3,c0_c1,c2_c3,c0_c2,c1_c3);cnt : counter port map (clk_count , disable , clock_main , reset_count) ; mux_clock : mult_clock port map (clock_main , c0_c0 , io_mode , clear , incr) ;end rtl;乘法器的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity multiply isport(num_mux , num_rom : in std_logic_vector(31 downto 0) ;clock : in std_logic ;mult_out : out std_logic_vector(31 downto 0) ) ;end multiply ;architecture rtl of multiply isbeginprocess(num_mux , num_rom , clock)variable sign_mult , t : std_logic := '0' ;variable temp1 , temp2 : std_logic_vector(22 downto 0) ;variable exp_mux , exp_rom : std_logic_vector(7 downto 0) ;variable mant_temp : std_logic_vector(45 downto 0) ;variable exp_mult , mux_temp , rom_temp : std_logic_vector(8 downto 0) ; variable res_temp : std_logic_vector(31 downto 0) ;begintemp1 := '1' & num_mux(22 downto 1) ;temp2 := '1' & num_rom(22 downto 1) ;if (num_mux(31) = '1' and num_rom(31) = '1' and clock = '1') then sign_mult := '0' ;elsif (num_mux(31) = '0' and num_rom(31) = '0' and clock = '1') then sign_mult := '0' ;elsif(clock = '1') thensign_mult := '1' ;end if ;if (num_mux = 0 and clock = '1') thent := '1' ;elsif (num_rom = 0 and clock = '1') thent := '1' ;elsif (clock = '1') thent := '0' ;if (t = '0' and clock = '1') thenexp_mux := num_mux (30 downto 23) ;exp_rom := num_rom (30 downto 23) ;mux_temp := '0' & exp_mux(7 downto 0) ;rom_temp := '0' & exp_rom(7 downto 0) ;exp_mult := mux_temp + rom_temp ;exp_mult := exp_mult - 127 ;mant_temp := temp1 * temp2 ;if(mant_temp(45) = '1') thenexp_mult := exp_mult + 1 ;res_temp := sign_mult & exp_mult(7 downto 0) & mant_temp(44 downto 22) ; mult_out <= res_temp(31 downto 0) ;elsif(mant_temp(45) = '0') thenres_temp := sign_mult & exp_mult(7 downto 0) & mant_temp(43 downto 21) ; mult_out <= res_temp(31 downto 0) ;end if ;elsif (t = '1' and clock = '1') thenmult_out <= "00000000000000000000000000000000" ;t := '0' ;end if ;end process ;蝶形变换的VHDL源程序：library ieee;use ieee.std_logic_1164.all;use ieee.std_logic_arith.all;use ieee.std_logic_unsigned.all;entity butterfly isport( clk :in std_logic;in1_r: in STD_LOGIC_VECTOR (3 downto 0); in1_i: in STD_LOGIC_VECTOR (3 downto 0); in2_r: in STD_LOGIC_VECTOR (3 downto 0); in2_i: in STD_LOGIC_VECTOR (3 downto 0); out1_r: out STD_LOGIC_VECTOR (7 downto 0); out1_i: out STD_LOGIC_VECTOR (7 downto 0); out2_r: out STD_LOGIC_VECTOR (7 downto 0); out2_i: out STD_LOGIC_VECTOR (7 downto 0); w_r:in STD_LOGIC_VECTOR (3 downto 0);w_i:in STD_LOGIC_VECTOR (3 downto 0));end butterfly;architecture butter of butterfly issignal a1 : STD_LOGIC_VECTOR (3 downto 0);signal b1 : STD_LOGIC_VECTOR (3 downto 0); signal a : STD_LOGIC_VECTOR (7 downto 0); signal b : STD_LOGIC_VECTOR (7 downto 0); signal c : STD_LOGIC_VECTOR (3 downto 0); signal ax : STD_LOGIC_VECTOR (7 downto 0); signal bx : STD_LOGIC_VECTOR (7 downto 0); signal cx : STD_LOGIC_VECTOR (7 downto 0); signal dx : STD_LOGIC_VECTOR (7 downto 0); beginprocess(clk)beginif(clk'event and clk='1')thena1<=in1_r;b1<=in1_i;a<=c&a1;b<=c&b1;ax<=w_r*in2_r;bx<=w_i*in2_i;cx<=w_r*in2_i;dx<=w_i*in2_r;out1_r<=a+ax-bx;out1_i<=b+cx+dx;out2_r<=a-ax+bx;out2_i<=b-cx-dx;end if;end process;end butter;交换器的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity swap isport (a : in std_logic_vector (31 downto 0) ;b : in std_logic_vector (31 downto 0) ;clock : in std_logic ;rst_swap , en_swap : in std_logic ;finish_swap : out std_logic ;d : out std_logic_vector (31 downto 0) ;large_exp : out std_logic_vector (7 downto 0) ;c : out std_logic_vector (32 downto 0 ) ) ; end swap ;architecture rtl of swap isbeginprocess (a , b , clock , rst_swap , en_swap) variable x , y : std_logic_vector (7 downto 0) ; variable p , q : std_logic_vector (22 downto 0) ; beginif(rst_swap = '1' ) thenc <= '0' & a(22 downto 0) & "000000000" ;finish_swap <= '0' ;elsif(rst_swap = '0') thenif(en_swap = '1') thenx := a (30 downto 23) ;y := b (30 downto 23) ;p := a (22 downto 0) ;q := b (22 downto 0) ;if (clock = '1') thenif (x < y) thenc <= '1' & a (22 downto 0) & "000000000" ;d <= '1' & b (22 downto 0) & "00000000" ;large_exp <= b (30 downto 23) ;finish_swap <= '1' ;elsif (y < x) thenc <= '1' & b (22 downto 0) & "000000000" ;d <= '1' & a (22 downto 0) & "00000000" ; large_exp <= a (30 downto 23) ;finish_swap <= '1' ;elsif ( (x=y) and (p < q)) thenc <= '1' & a (22 downto 0) & "000000000" ;d <= '1' & b (22 downto 0) & "00000000" ; large_exp <= b (30 downto 23) ;finish_swap <= '1' ;elsec <= '1' & b (22 downto 0) & "000000000" ;d <= '1' & a (22 downto 0) & "00000000" ; large_exp <= a (30 downto 23) ;finish_swap <= '1' ;end if ;end if ;end if ;end if ;end process;end rtl;输入输出的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity divide isport (data_in : in std_logic_vector(31 downto 0) ;data_out : out std_logic_vector(31 downto 0) ) ; end divide ;architecture rtl of divide isbeginprocess(data_in)variable divide_exp : std_logic_vector(7 downto 0) ; variable divide_mant : std_logic_vector(31 downto 0) ; beginif (data_in = "00000000000000000000000000000000") then data_out <= "00000000000000000000000000000000" ;elsif (data_in = "10000000000000000000000000000000") then data_out <= "00000000000000000000000000000000" ;elsedivide_exp := data_in(30 downto 23) ;divide_mant := data_in (31 downto 0) ;divide_exp := divide_exp - "00000001" ;data_out <= data_in(31 downto 0) ;end if ;end process ;end rtl ;调节器的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity cont_gen isport (con_staged , con_iod , con_fftd , con_init : in std_logic ;con_ip , con_op , con_iomode , con_fft : out std_logic ;con_enbw , con_enbor , c0_enable , con_preset : out std_logic ; con_clear , disable : out std_logic ;c0 , clock_main : in std_logic ;en_rom , en_romgen , reset_counter : out std_logic ;con_clkcount : in std_logic_vector(2 downto 0) ) ;end cont_gen ;architecture rtl of cont_gen istype state is (rst1,rst2,rst3,rst4,rst5,rst6,rst7) ;signal current_state , next_state : state ;shared variable counter , temp2 : std_logic_vector(1 downto 0) := "00" ;beginprocess (current_state ,con_staged , con_iod , con_fftd , con_clkcount , c0)begincase current_state iswhen rst1 =>con_iomode <= '1' ;con_ip <= '1' ;con_clear <= '1' ;con_enbw <= '1' ;con_enbor <= '0' ;c0_enable <= '0' ;disable <= '1' ;next_state <= rst2 ;when rst2 =>con_clear <= '0' ;next_state <=rst3 ;when rst3 =>if(con_iod = '1') thencon_preset <= '1' ;reset_counter <= '1' ;c0_enable <= '1' ;con_iomode <= '0' ;con_fft <= '1' ;en_rom <= '1' ;en_romgen <= '1' ;con_clear <= '1' ;con_enbw <= '0' ;con_enbor <= '1' ;disable <= '0' ;next_state <= rst4 ;elsenext_state <= rst3 ;end if ;when rst4 =>con_preset <= '0' ;reset_counter <= '0' ;con_clear <= '0' ;if (con_clkcount = 5) then con_enbw <= '1' ;disable <= '1' ;reset_counter <= '1' ;next_state <= rst5 ;elsenext_state <= rst4 ;end if ;when rst5 =>if (con_fftd = '1') then disable <= '0' ;reset_counter <= '0' ;con_clear <= '1' ;con_fft <= '0' ;if (con_clkcount = 4) then disable <= '1';con_enbw <= '0' ;con_iomode <= '1' ;con_op <= '1' ;con_ip <= '0' ;next_state <= rst6 ;elsenext_state <= rst5 ;end if ;elsenext_state <= rst5 ;end if ;when rst6 =>con_clear <= '0' ;next_state <= rst7 ;when rst7 =>if(con_iod = '1') thencon_clear <= '1' ;con_preset <= '1' ;con_enbor <= '0';elsenext_state <= rst7 ;end if ;when others =>next_state <= rst1 ;end case ;end process ;process(clock_main , con_init)beginif(con_init = '1') thencurrent_state <= rst1 ;elsif (clock_main'event and clock_main = '0') then current_state <= next_state ;end if ;end process ;end rtl ;只读存储器的VHDL源程序：library ieee ;use ieee.std_logic_1164.all ;use ieee.std_logic_arith.all ;use ieee.std_logic_unsigned.all ;entity rom isport (clock , en_rom : in std_logic ;romadd : in std_logic_vector(2 downto 0) ;rom_data : out std_logic_vector(31 downto 0) ) ; end rom ;architecture rtl of rom isbeginprocess(clock,en_rom)beginif(en_rom = '1') thenif(clock = '1') thencase romadd iswhen "000" =>rom_data <= "00111111100000000000000000000000" ;when "001" =>rom_data <= "00000000000000000000000000000000" ;when "010" =>rom_data <= "00111111001101010000010010000001" ; when "011" =>rom_data <= "00111111001101010000010010000001" ; when "100" =>rom_data <= "00000000000000000000000000000000" ; when "101" =>rom_data <= "00111111100000000000000000000000" ; when "110" =>rom_data <= "10111111001101010000010010000001" ; when "111" =>rom_data <= "00111111001101010000010010000001" ; when others =>rom_data <= "01000000000000000000000000000000" ; end case ;end if ;end if ;end process ;end rtl ;随机存储器的VHDL源程序：library ieee;use ieee.std_logic_1164.all;use IEEE.std_logic_arith.all;use IEEE.std_logic_unsigned.all;entity reg_dpram isport (data_fft , data_io : in std_logic_vector (31 downto 0); q : out std_logic_vector (31 downto 0);clock , io_mode : in std_logic;we , re : in std_logic;waddress: in std_logic_vector (3 downto 0);raddress: in std_logic_vector (3 downto 0));end reg_dpram;architecture behav of reg_dpram istype MEM is array (0 to 15) of std_logic_vector(31 downto 0); signal ramTmp : MEM;beginprocess (clock,waddress,we)beginif (clock='0') thenif (we = '1') thenif (io_mode = '0') thenramTmp (conv_integer (waddress)) <= data_fft ;elsif (io_mode = '1') thenramTmp (conv_integer (waddress)) <= data_io ; end if ;end if ;end if ;end process ;process (clock,raddress,re)beginif (clock='1') thenif (re = '1') thenq <= ramTmp(conv_integer (raddress)) ;end if;end if;end process;end behav;五、主要VHDL源程序仿真结果FFT总体结构的RTL视图fft总体结构的仿真乘法器的RTL视图乘法器的仿真蝶形运算的RTL视图蝶形运算的仿真交换器的RTL视图交换器的仿真输入输出的RTL视图输入输出的仿真调节器的RTL视图调节器的仿真只读存储器的RTL视图只读存储器的仿真随机存储器的RTL视图随机存储器的仿真六、硬件验证方案及验证结果本次实验由于是在家进行的，不能去实验室用实验箱进行实验，所以我估计芯片EP3C55F484C7的硬件结果应该是正确的。
