目錄
夯實基礎--FFT算法
定點運算--verilog實現(xiàn)小數(shù)運算
Verilog代碼實現(xiàn)
?FFT系數(shù) W 的準備
?輸入數(shù)值的初始化
蝶形運算端點處的值
仿真結(jié)果展示
總結(jié)
夯實基礎--FFT算法
? ? ? ?FFT是DFT的一種快速算法而不是一種新的變換，他可以在數(shù)量級的意義上提高運算速度。它主要有兩種實現(xiàn)方法：一種是按時間抽?。―IT）,另一種是按頻域抽取（DIF）。為了方便起見，我們選用基于時間抽取的FFT的算法。
? ? ? ? 算法原理：先設序列x(n)的點數(shù)為N = 2^L(L為正整數(shù)
將N=2^L的偶數(shù)序列x(n)按n的奇偶將序列分成兩組，對兩組新的序列。在對N點的序列進行DFT運算的時候按奇偶將序列分開，我們便可根據(jù)系數(shù)W的可約性得到前N/2的DFT的點的值，根據(jù)W的周期性有可以得到后面N/2點的DFT的值。詳細請參考數(shù)字信號處理，在此就不過多的解釋。我們以16點FFT為例，在此粘貼處他的蝶形圖
? ? ? ?
?
?還有一點，F(xiàn)FT的運算為輸入倒位序，輸出自然順序或者是輸入自然順序，輸出倒位序。這里我們采取輸入倒位序，輸出自然順序
（倒位序：將n的值轉(zhuǎn)換成二進制，倒過來重新排序所組成的值）
定點運算--verilog實現(xiàn)小數(shù)運算
? ? ? ? 定點運算，顧名思義，我們在運算的過程中需要確定小數(shù)點的位置，讓小數(shù)點的位置保持不變
? ? ? ? 實現(xiàn)原理：對于一個數(shù)，我們可以把他分成三個部分：符號位，整數(shù)部分和小數(shù)部分。
? ?????????若 x 表示一個實際的浮點數(shù)，q表示他的Qn 型的定點小數(shù)（一個整數(shù)）。n表示小數(shù)點固定的位置
???????? ? 則 q = x * 2^n ,x = q / 2^n?
? ? ? ? ?舉例： 計算 2.1 * 2.2? ?（此處我們選擇Q12定點小數(shù)）
? ? ? ? ? ? ? ? 2.1 *? 2^12 = 8601.6 = 8602
? ? ? ? ? ? ? ? 2.2 * 2^12 = 9011.2? = 9011
? ? ? ? ? ? ? ? (8602*9011)/2^12 = 18923 (除以12的原因：兩數(shù)相乘使得小數(shù)點后有24位，所以我們需要除以2^12,固定小數(shù)點)
? ? ? ? ? ? ? ? 最終結(jié)果 = 18923/ 2^12? = 4.619873 而2.1*2.2 = 4.62??
? ? ? ? ? ? ? ? 我們可以知道結(jié)果相差不大，故我們可以用這種方法實現(xiàn)小數(shù)運算
注：當我們用verilog實現(xiàn)的時候我們需要注意格式，在進行負數(shù)運算的時候我們是以二進制補碼的形式儲存的，而? 數(shù)值大小的運算我們用原碼進行運算，在計算過程中注意符號
Verilog代碼實現(xiàn)
? ? ? ? 根據(jù)上面的fft16的蝶形圖，我們可以選擇使用四級流水線進行實現(xiàn)
? ? ? ? FFT系數(shù) W 的準備
? ? ? ? ? ? ? ? ? W的值的運算我們可以用過matlab運算得到，此處我直接把需要用到的W的值給出? W（下標，上標）
? ? ? ? ? ? ? ? W(4,1)=W(8,2)=W(16,4)=-j ;W(8,1)=W(16,2)=0.7071-0.7071j??
? ? ? ? ? ? ? ? W(8,3)=W(16,6)=-0.7071-0.7071j? ; W(16,3)=0.3827-0.9239;W(16,5)=-0.3827-0.9239 ;
? ? ? ? ? ? ? ? W(16,7)=-0.9239-0.3827 ; W(16,1)=0.9239-0.3827
? ? ? ? ? ? ? ? 我們可以看出主要小數(shù)就是0.9239? ；0.3837 ； 0.7071這三個數(shù)，此處我們采取Q12的定點方法進行verilog定義
wire [WIDTH-1:0] coe_dly1_p ;
wire [WIDTH-1:0] coe_dly1_n ;
wire [WIDTH-1:0] coe_dly2_p ;
wire [WIDTH-1:0] coe_dly2_n ;
wire [WIDTH-1:0] coe_dly3_p ;
wire [WIDTH-1:0] coe_dly3_n ;
//0.7071
assign coe_dly1_p = 2896;
assign coe_dly1_n = 2896 ;
//0.3827
assign coe_dly2_p = 1568;
assign coe_dly2_n = 1568 ;
//0.9239
assign coe_dly3_p = 3874;
assign coe_dly3_n = 3874 ; 此處后綴 _p 和 _n 來區(qū)別正負，我們需要用原碼來進行運算，所以不可以直接給符號（否則以補碼形式儲存得到錯誤的結(jié)果）
?輸入數(shù)值的初始化
? ? ? ? 由于我們選定的是Q12定點運算，故我們需要對輸入的數(shù)據(jù)進行擴大，方便后續(xù)的運算（再次提醒：數(shù)據(jù)的操作用原碼?。。?/p>
????????
assign fft0_re_inst=(fft0_re[WIDTH-1]==1'b1)?({1'b1,~((~fft0_re[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft0_re[WIDTH-2:0]<<12});
assign fft0_im_inst=(fft0_im[WIDTH-1]==1'b1)?({1'b1,~((~fft0_im[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft0_im[WIDTH-2:0]<<12});
assign fft1_re_inst=(fft0_re[WIDTH-1]==1'b1)?({1'b1,~((~fft1_re[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft1_re[WIDTH-2:0]<<12});
assign fft1_im_inst=(fft0_im[WIDTH-1]==1'b1)?({1'b1,~((~fft1_im[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft1_im[WIDTH-2:0]<<12});
assign fft2_re_inst=(fft0_re[WIDTH-1]==1'b1)?({1'b1,~((~fft2_re[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft2_re[WIDTH-2:0]<<12});
assign fft2_im_inst=(fft0_im[WIDTH-1]==1'b1)?({1'b1,~((~fft2_im[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft2_im[WIDTH-2:0]<<12});
assign fft3_re_inst=(fft0_re[WIDTH-1]==1'b1)?({1'b1,~((~fft3_re[WIDTH-2:0]+1'b1)<<12)+1'b1}):({1'b0,fft3_re[WIDTH-2:0]<<12});蝶形運算端點處的值
? ? ? ? 為了緩解運算的復雜度，避免時序的問題，通過打拍的方式將每個端點需要進行處理的值在打拍過程中實現(xiàn)，這樣就緩解了組合電路的壓力。第一級和第二級端點處的處理比較簡單，在這里不做過多的解釋，我們重點講解下第三級和第四級的端點處的處理
我們先用相關的原碼計算得到結(jié)果值（主要是兩數(shù)相乘，注意小數(shù)點的處理），然后根據(jù)‘同號得正，異號得負’的原理來處理得到最終的結(jié)果（因為我們是以補碼形式儲存的），在這里粘貼部分代碼供參考：
????????
//得到原碼
assign fft5_re_dly2_temp = (fft5_re_dly2[WIDTH-1]==1'b1)?(~fft5_re_dly2+1'b1):fft5_re_dly2;
assign fft5_im_dly2_temp = (fft5_im_dly2[WIDTH-1]==1'b1)?(~fft5_im_dly2+1'b1):fft5_im_dly2;
assign fft7_re_dly2_temp = (fft7_re_dly2[WIDTH-1]==1'b1)?(~fft7_re_dly2+1'b1):fft7_re_dly2;
assign fft7_im_dly2_temp = (fft7_im_dly2[WIDTH-1]==1'b1)?(~fft7_im_dly2+1'b1):fft7_im_dly2;
//得到端點處的相關系數(shù)的原碼的值
always@(posedge sys_clk or negedge sys_rst_n)
begin
if(~sys_rst_n)
begin
fft5_fft1_re_dly1 <=0;
fft5_fft1_re_dly2 <=0;
fft5_fft1_im_dly1 <=0;
fft5_fft1_im_dly2 <=0;
fft3_fft7_re_dly1 <=0;
fft3_fft7_re_dly2 <=0;
fft3_fft7_im_dly1 <=0;
fft3_fft7_im_dly2 <=0;
end
else
begin
fft5_fft1_re_dly1 <=(fft5_re_dly2_temp*coe_dly1_p )>>12;
fft5_fft1_re_dly2 <=(fft5_im_dly2_temp*coe_dly1_n )>>12;
fft5_fft1_im_dly1 <=(fft5_re_dly2_temp*coe_dly1_n )>>12;
fft5_fft1_im_dly2 <=(fft5_im_dly2_temp*coe_dly1_p )>>12;
fft3_fft7_re_dly1 <=(fft7_re_dly2_temp*coe_dly1_n )>>12;
fft3_fft7_re_dly2 <=(fft7_im_dly2_temp*coe_dly1_n )>>12;
fft3_fft7_im_dly1 <=(fft7_im_dly2_temp*coe_dly1_n )>>12;
fft3_fft7_im_dly2 <=(fft7_re_dly2_temp*coe_dly1_n )>>12;
end
end
end
//轉(zhuǎn)換成補碼形式儲存下來并進行后續(xù)的運算
//最高位為1表示負數(shù)
assign fft5_fft1_re_dly1_wn = (fft5_re_dly2_dly[WIDTH-1]==1'b1)?(~fft5_fft1_re_dly1+1'b1):fft5_fft1_re_dly1;
assign fft5_fft1_re_dly2_wn = (fft5_im_dly2_dly[WIDTH-1]==1'b1)?fft5_fft1_re_dly2:(~fft5_fft1_re_dly2+1'b1);
assign fft5_fft1_im_dly1_wn = (fft5_re_dly2_dly[WIDTH-1]==1'b0)?(~fft5_fft1_re_dly1+1'b1):fft5_fft1_re_dly1;
assign fft5_fft1_im_dly2_wn = (fft5_im_dly2_dly[WIDTH-1]==1'b0)?fft5_fft1_re_dly2:(~fft5_fft1_re_dly2+1'b1);
assign fft3_fft7_re_dly1_wn = (fft7_re_dly2_dly[WIDTH-1]==1'b1)?fft3_fft7_re_dly1:(~fft3_fft7_re_dly1+1'b1);
assign fft3_fft7_re_dly2_wn = (fft7_im_dly2_dly[WIDTH-1]==1'b1)?fft3_fft7_re_dly2:(~fft3_fft7_re_dly2+1'b1);
assign fft3_fft7_im_dly1_wn = (fft7_im_dly2_dly[WIDTH-1]==1'b1)?fft3_fft7_im_dly1:(~fft3_fft7_im_dly1+1'b1);
assign fft3_fft7_im_dly2_wn = (fft7_re_dly2_dly[WIDTH-1]==1'b1)?fft3_fft7_im_dly2:(~fft3_fft7_im_dly2+1'b1);第三級和第四級處理方法類似，理解了一個另一個也很容易理解
仿真結(jié)果展示
? ? ? ? tb代碼
????????
initial
begin
clk = 1'b0 ;
rst = 1'b0 ;
#20
rst = 1'b1 ;
end
always #10 clk = ~clk ;
fft16
#(
.WIDTH ('d32)
)
fft16_inst
(
.sys_clk(clk),
.sys_rst_n(rst),
.fft0_re('d1),
.fft1_re('d2),
.fft2_re('d2),
.fft3_re('d1),
.fft4_re('d2),
.fft5_re('d1),
.fft6_re('d1),
.fft7_re('d2),
.fft8_re('d2),
.fft9_re('d1),
.fft10_re('d1),
.fft11_re('d2),
.fft12_re('d1),
.fft13_re('d1),
.fft14_re('d1),
.fft15_re('d2),
.fft0_im('d0),
.fft1_im('d0),
.fft2_im('d0),
.fft3_im('d0),
.fft4_im('d0),
.fft5_im('d0),
.fft6_im('d0),
.fft7_im('d0),
.fft8_im('d0),
.fft9_im('d0),
.fft10_im('d0),
.fft11_im('d0),
.fft12_im('d0),
.fft13_im('d0),
.fft14_im('d0),
.fft15_im('d0),
//output
.fft0_re_out(fft0_re_out),
.fft1_re_out(fft1_re_out),
.fft2_re_out(fft2_re_out),
.fft3_re_out(fft3_re_out),
.fft4_re_out(fft4_re_out),
.fft5_re_out(fft5_re_out),
.fft6_re_out(fft6_re_out),
.fft7_re_out(fft7_re_out),
.fft8_re_out(fft8_re_out),
.fft9_re_out(fft9_re_out),
.fft10_re_out(fft10_re_out),
.fft11_re_out(fft11_re_out),
.fft12_re_out(fft12_re_out),
.fft13_re_out(fft13_re_out),
.fft14_re_out(fft14_re_out),
.fft15_re_out(fft15_re_out),
.fft0_im_out(fft0_im_out),
.fft1_im_out(fft1_im_out),
.fft2_im_out(fft2_im_out),
.fft3_im_out(fft3_im_out),
.fft4_im_out(fft4_im_out),
.fft5_im_out(fft5_im_out),
.fft6_im_out(fft6_im_out),
.fft7_im_out(fft7_im_out),
.fft8_im_out(fft8_im_out),
.fft9_im_out(fft9_im_out),
.fft10_im_out(fft10_im_out),
.fft11_im_out(fft11_im_out),
.fft12_im_out(fft12_im_out),
.fft13_im_out(fft13_im_out),
.fft14_im_out(fft14_im_out),
.fft15_im_out(fft15_im_out)
);
? ? ? ? 結(jié)果這里通過我手算的結(jié)果和仿真的結(jié)果進行比較驗算
????????
?
?
?
（?由于個人原因我只算了前8個點的值，不過由于前8個點和后8個點的只有+ 和 - 的區(qū)別，所用的數(shù)值的一樣的，所以前8個對了，后面的也就沒什么問題。）
通過比較，我們可以發(fā)現(xiàn)他們的誤差還是比較小的，這是由于modelsim仿真的時候他遇到小數(shù)采取的方式不是四舍五入，而是直接舍掉。
還有最重要的一點：現(xiàn)在仿真得到的結(jié)果不是最終的值，他存儲的結(jié)果是Q12型小數(shù)補碼的形式，如果要得到最終的結(jié)果，我們需要手動對結(jié)果進行處理。切記?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-744365.html
總結(jié)
? ? ? ? 本人第一次寫csdn,其中如果有寫的不正確或者不恰當?shù)牡胤竭€請多多批評指正，在下不勝感激。文章來源地址http://www.zghlxwxcb.cn/news/detail-744365.html
到了這里，關于基于verilog的四級流水線實現(xiàn)并行fft16(可計算小數(shù)和負數(shù))的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
