一提到FFT很多FPGA工程師的習慣性動作是打開Vivado或Quartus里的FFT IP核把點數(shù)一配、流模式一選、點一下Generate完事。但今年我在一個資源預(yù)算比較緊的小項目里只需要做16點FFT輸入是8bit定點數(shù)外部數(shù)據(jù)速率不高而核的Latency、DSP占用和時序行為總覺得有點“黑盒”。折騰了一圈之后我決定干脆用Verilog手寫一個基-2 16點FFT。這個規(guī)模不算大但正好能把FFT硬件化的全部關(guān)鍵問題——蝶形運算結(jié)構(gòu)、旋轉(zhuǎn)因子量化、定點數(shù)位寬控制、數(shù)據(jù)調(diào)度、仿真對比——完整地走一遍。做完之后回頭看這件事的價值遠不止“省了一個IP核”它讓我對FFT的數(shù)據(jù)流和FPGA數(shù)字信號處理的設(shè)計思路都有了更實的掌握。這篇文章就按我實際的實現(xiàn)路徑把算法結(jié)構(gòu)、RTL拆分、定位數(shù)處理、驗證方法和踩過的坑一次講清楚。1. 先算清楚這筆賬16點FFT為什么值得手寫1.1 資源占用與延遲的直觀對比基-2 16點FFT的運算量是固定的4級蝶形每級8個蝶形總共32次復(fù)數(shù)蝶形運算。但同樣的算法映射到FPGA上的架構(gòu)差別非常大。全并行架構(gòu)每一級8個蝶形每個蝶形一個復(fù)數(shù)乘法器總共需要32個復(fù)數(shù)乘法器等價于128個實數(shù)乘法器邏輯規(guī)模和布線壓力都不小。單蝶形復(fù)用架構(gòu)只實現(xiàn)一個蝶形運算單元用狀態(tài)機控制它依次完成32次運算每次運算只用一個復(fù)數(shù)乘法器資源占用極小。IP核以Xilinx FFT IP為例配16點、Radix-2 Burst I/O模式Latency通常在百拍量級資源則取決于你選的實現(xiàn)方式。IP核的好處是通用性強但代價是“黑盒”綜合之后未必是最優(yōu)解。我把三種方案在16點這個規(guī)模下的表現(xiàn)粗略列了一下方案復(fù)數(shù)乘法器數(shù)量大致Latency可控性適用場景全并行/流水線32數(shù)拍到十幾拍高高速流式處理單蝶形復(fù)用1約100拍很高低速、資源受限FFT IP核取決于配置數(shù)十到數(shù)百拍低通用快速集成1.2 什么情況下應(yīng)該放棄IP核用手寫IP核不是不能用而是有些場景下它確實不是最優(yōu)選擇。資源受限的小規(guī)模設(shè)計只做16點FFT用IP核有點“殺雞用牛刀”配置頁翻半天不說生成的邏輯可能比手寫大不少。時序與流水需要精確對齊IP核Latency是固定的但它內(nèi)部到底怎么調(diào)度、能不能和你的上下游邏輯無縫銜接很多時候要靠經(jīng)驗去猜。手寫的話每一拍干什么都是自己控制的。需要自定義數(shù)據(jù)格式與截位策略FFT IP核的輸出位寬、縮放方式是可配的但如果你有特殊的定點數(shù)格式要求或者想在中間級做自定義處理手寫反而更靈活。學習與面試需求現(xiàn)在不少數(shù)字IC和FPGA相關(guān)的筆試面試題里都有“手撕FFT”這種題自己完整寫過一遍理解深度完全不同。16點FFT的手寫邏輯量并不大核心模塊也就幾個蝶形運算單元、旋轉(zhuǎn)因子ROM、地址生成器、狀態(tài)機。在資源利用率上單蝶形方案用一個DSP48就夠邏輯消耗只有幾百個LUT。2. 基-2 16點FFT的蝶形結(jié)構(gòu)與旋轉(zhuǎn)因子表2.1 DIT還是DIF選哪一個更順手FFT的按時間抽取DIT和按頻率抽取DIF本質(zhì)上用同一個蝶形公式區(qū)別在于輸入輸出順序。DIT要求輸入按倒位序排列輸出是自然序DIF則是輸入自然序輸出倒位序。我推薦用DIT原因很直接輸入數(shù)據(jù)寫入RAM時做一次bit-reverse地址映射即可后續(xù)每級蝶形運算都按自然序讀數(shù)據(jù)控制邏輯簡單。DIF雖然輸入不需要倒序但最后輸出要處理倒序如果下游還要做頻譜分析或逆變換反而多一道麻煩。2.2 四級蝶形的排布規(guī)律16點基-2 FFT的蝶形間距和旋轉(zhuǎn)因子指數(shù)是有嚴格規(guī)律的。設(shè)級數(shù)從0開始記第s級的蝶形間距是2^s每級固定8個蝶形第s級第j個蝶形的旋轉(zhuǎn)因子指數(shù)由公式k j × (16 / (2^(s1))) 計算。實際算一遍就是這個表級數(shù)蝶形間距分組數(shù)旋轉(zhuǎn)因子指數(shù)說明第0級18k0每組1個蝶形第1級24k0,4每組2個蝶形第2級42k0,2,4,6每組4個蝶形第3級81k0,1,...,7一組8個蝶形這里有個容易記錯的地方16點FFT第二級旋轉(zhuǎn)因子不是W16^0和W16^2而是W16^0和W16^4。因為第二級里每組兩個蝶形合并的只是4點子序列旋轉(zhuǎn)因子對應(yīng)的是N/4周期上的角度。2.3 輸入倒位序的Verilog處理16點需要4位地址反轉(zhuǎn)。比如輸入序號1二進制0001反轉(zhuǎn)后地址是1000也就是8。在RTL里寫一個反轉(zhuǎn)函數(shù)就行function [3:0] bit_reverse4; input [3:0] addr; begin bit_reverse4 {addr[0], addr[1], addr[2], addr[3]}; end endfunction實際寫入RAM時就把原始輸入數(shù)據(jù)寫到bit_reverse4(地址)的位置。例如第1個采樣點寫到地址8第2個寫到地址4第3個寫到地址12依次類推。這個映射可以在Testbench階段就預(yù)先確認一遍常見的一個低級錯誤就是倒位序只反轉(zhuǎn)了半字節(jié)或者反轉(zhuǎn)方向?qū)懛磳?dǎo)致最終輸出頻譜順序是亂的。3. 定點數(shù)格式與中間位寬最容易翻車的環(huán)節(jié)3.1 Q格式定點數(shù)的基礎(chǔ)FPGA里做不了浮點定點數(shù)格式得一開始就定好。最常用的是Q格式表示法。Q1.71位符號位7位小數(shù)范圍[-1, 1-2^-7]精度約0.0078。適合表示歸一化后的信號。Q1.151位符號位15位小數(shù)范圍[-1, 1-2^-15]精度非常高適合存旋轉(zhuǎn)因子的cos/sin值。在這個設(shè)計里輸入用Q1.7格式的8bit有符號數(shù)即可旋轉(zhuǎn)因子用Q1.15格式的16bit有符號數(shù)。兩個定點數(shù)相乘后結(jié)果的格式是Q(1.7) × Q(1.15) ≈ Q(1.22)需要根據(jù)需求截位。3.2 兩種中間位寬方案逐級右移 vs 全精度增長這塊是整個設(shè)計里最容易被低估的部分。FFT每級蝶形進行一次加法和一次減法數(shù)據(jù)位寬理論上每級增長1bit4級下來最多增長4bit。16點FFT的增益正好是16也就是說一個接近滿幅的8bit輸入經(jīng)過4級運算后中間結(jié)果的理論最大值可以達到輸入的16倍。我試驗過兩種主流方案方案A逐級右移1位每級蝶形計算完成后把結(jié)果右移1位相當于每級做一次1/2縮放。4級之后輸出等于原始FFT結(jié)果的1/16但整個運算過程中的數(shù)據(jù)位寬恒定不變不會溢出。實現(xiàn)簡單資源占用小。代價是每級右移時都會引入量化誤差不過16點FFT的級數(shù)只有4級誤差累積有限實測SNR通常還有50dB以上完全夠用。方案B全精度增長最后統(tǒng)一截位輸入8bit每級把位寬擴到16bit甚至更寬中間不縮放最后輸出時再截位或飽和。精度最高但存儲和運算邏輯變多而且最后截位時如果處理不好照樣會有溢出風險。兩種方案我建議初學者直接用方案A理由很簡單省心、無溢出、邏輯清晰。如果你的應(yīng)用對SNR要求特別高再考慮方案B。3.3 旋轉(zhuǎn)因子的量化與ROM生成旋轉(zhuǎn)因子的計算公式是W16^k cos(2πk/16) ? j·sin(2πk/16)在Verilog里存成兩個16bit有符號數(shù)實部存cos值虛部存?sin值?；?2 16點FFT實際需要用的旋轉(zhuǎn)因子是k0到7另一半可以通過對稱性得到所以ROM只需要存8組。用Python生成ROM初始值最方便import math N 16 tw_r [] tw_i [] for k in range(8): angle 2 * math.pi * k / N wr int(round(math.cos(angle) * 32767)) wi -int(round(math.sin(angle) * 32767)) tw_r.append(wr 0xFFFF) tw_i.append(wi 0xFFFF) with open(twiddle_rom.mem, w) as f: for i in range(8): f.write(f{i:02X} {tw_r[i]:04X} {tw_i[i]:04X}\n)需要注意生成時要用16bit有符號數(shù)的補碼形式存這樣才能在Verilog里直接用signed類型讀取。4. RTL實現(xiàn)的關(guān)鍵模塊蝶形單元、ROM與地址生成4.1 蝶形運算單元的Verilog寫法蝶形運算是FFT的核心設(shè)輸入為x和y旋轉(zhuǎn)因子為W則輸出為x y·W和x ? y·W。復(fù)數(shù)乘法展開后需要4個實數(shù)乘法和幾次加法。寫成Verilogmodule butterfly #( parameter DW 16 )( input wire signed [DW-1:0] xr, xi, input wire signed [DW-1:0] yr, yi, input wire signed [DW-1:0] wr, wi, output wire signed [DW-1:0] sum_r, sum_i, output wire signed [DW-1:0] dif_r, dif_i ); // y * W 的實部yr*wr - yi*wi // y * W 的虛部yr*wi yi*wr wire signed [2*DW-1:0] yr_wr yr * wr; wire signed [2*DW-1:0] yi_wi yi * wi; wire signed [2*DW-1:0] yr_wi yr * wi; wire signed [2*DW-1:0] yi_wr yi * wr; wire signed [DW-1:0] ywr (yr_wr - yi_wi) (DW-1); wire signed [DW-1:0] ywi (yr_wi yi_wr) (DW-1); assign sum_r xr ywr; assign sum_i xi ywi; assign dif_r xr - ywr; assign dif_i xi - ywi; endmodule這里有個細節(jié)乘法結(jié)果是32bit使用算數(shù)右移把它截回16bit。右移時研究一下仿真結(jié)果看看用截斷還是四舍五入對SNR影響大。四舍五入可以在右移前加一個偏移量實現(xiàn)代價是幾個加法器。4.2 旋轉(zhuǎn)因子ROM的初始化ROM可以直接用Verilog數(shù)組加initial塊初始化。我用上面的Python腳本生成twiddle_rom.mem然后在RTL里讀入reg signed [15:0] tw_r [0:7]; reg signed [15:0] tw_i [0:7]; initial begin $readmemh(twiddle_rom.mem, tw_r); $readmemh(twiddle_rom.mem, tw_i); end不過$readmemh一次只能讀一個數(shù)組實踐中我通常把實部和虛部分成兩個文件或者用initial塊里的case語句直接查表。16點規(guī)模很小case語句反而最直觀可讀性也最好。4.3 地址生成與狀態(tài)機控制單蝶形復(fù)用方案需要一個狀態(tài)機來調(diào)度32次蝶形運算。核心控制邏輯是兩級計數(shù)器stage_cnt[1:0]當前級數(shù)0到3。bfly_cnt[2:0]當前級內(nèi)的蝶形序號0到7。根據(jù)這兩個計數(shù)器和2.2節(jié)的規(guī)律就可以算出當前蝶形的兩個輸入數(shù)據(jù)地址和旋轉(zhuǎn)因子地址wire [3:0] spacing 4b0001 stage_cnt; // 蝶形間距 wire [3:0] j bfly_cnt (spacing - 4b0001); // 組內(nèi)蝶形序號 wire [3:0] base (bfly_cnt / spacing) * (spacing 1); // 組基地址 wire [3:0] addr0 base j; wire [3:0] addr1 base j spacing; wire [2:0] tw_addr stage_cnt 2d0 ? 3d0 : (stage_cnt 2d1 ? {j[0], 2b00} : (stage_cnt 2d2 ? {j[1:0], 1b0} : j));三級條件嵌套就能把旋轉(zhuǎn)因子換算出來。狀態(tài)機則負責在每個蝶形運算開始時讀兩個復(fù)數(shù)計算完成后寫回RAM然后切換下一組地址。5. 仿真驗證從激勵生成到誤差分析的全鏈路5.1 用Python生成測試向量純隨機數(shù)測試能驗證功能但看不出精度損失。我習慣用已知頻率的正弦信號做激勵這樣頻譜圖上一眼就能看出峰值位置對不對。import numpy as np N 16 t np.arange(N) signal np.round(100 * np.cos(2 * np.pi * 3 * t / N)).astype(int) with open(input_real.txt, w) as f: for v in signal: f.write(f{v 0xFF:02X}\n) # 虛部全0只測實信號 with open(input_imag.txt, w) as f: for _ in range(N): f.write(00\n)Testbench里用$readmemh把這兩個文件讀入存儲數(shù)組然后啟動FFTreg [7:0] mem_r [0:15]; reg [7:0] mem_i [0:15]; reg start; initial begin $readmemh(input_real.txt, mem_r); $readmemh(input_imag.txt, mem_i); #20 start 1; end5.2 結(jié)果比對與SNR計算仿真結(jié)束后把輸出結(jié)果導(dǎo)出在Python里與numpy.fft.fft的參考結(jié)果比對。這里要特別注意幅度對齊如果中間采用的是逐級右移方案RTL輸出等于真實FFT結(jié)果的1/16比較時要先把參考結(jié)果除以16。rtl_out np.loadtxt(fft_out.txt) # RTL仿真導(dǎo)出的復(fù)數(shù)結(jié)果 ref_out np.fft.fft(signal) # 參考FFT ref_scaled ref_out / 16 # 對齊RTL的縮放 error rtl_out - ref_scaled max_err np.max(np.abs(error)) rms_err np.sqrt(np.mean(np.abs(error)**2)) snr 20 * np.log10(np.linalg.norm(ref_scaled) / np.linalg.norm(error)) print(fmax error: {max_err:.4f}) print(frms error: {rms_err:.4f}) print(fSNR: {snr:.2f} dB)我實際做下來用8bit輸入、逐級右移方案SNR大概能到50dB以上如果把截位改成四舍五入SNR還能再提高幾個dB。如果你發(fā)現(xiàn)SNR只有30dB以下大概率不是位數(shù)不夠而是旋轉(zhuǎn)因子方向反了或者截位邏輯有bug。5.3 常見bug復(fù)現(xiàn)從仿真波形定位說兩個我調(diào)試時真實踩過的坑供各位參考?？?輸出頻譜順序全亂表現(xiàn)是三個信號頻率分量的位置完全對不上。排查時發(fā)現(xiàn)是倒位序地址寫反了我在寫RAM時用了bit_reverse4(addr[3:0])但addr在循環(huán)里已經(jīng)是倒好的序等于反轉(zhuǎn)了兩次等于沒反。修正方式是只保留第一次反轉(zhuǎn)。坑2輸出幅度明顯偏小輸入是100量級的信號輸出結(jié)果卻小了一截。原因在截位邏輯乘法器結(jié)果右移15位后符號位擴展被wire signed默認保留但我在加法器里用了無符號比較導(dǎo)致大負數(shù)被錯誤截斷。解決方法是讓蝶形運算單元的所有信號統(tǒng)一用signed類型并且右移用而不是。6. 實測中的幾個坑與下一步擴展思考6.1 輸入滿擺幅時的溢出問題逐級右移方案理論上不會溢出但前提是每一級的右移都在加法和減法之后進行。如果你的數(shù)據(jù)路徑是加法器和減法器共用然后單獨做右移要注意先把蝶形輸出完整算完再統(tǒng)一右移。否則高位數(shù)據(jù)在截位前就可能溢出。6.2 乘法器位寬與DSP資源配置16bit × 16bit乘法正好落在Xilinx DSP48E1的原生能力范圍內(nèi)一個DSP就能搞定。如果你的FPGA里DSP資源緊張也可以用移位加法和分布式算法替代乘法器但那個實現(xiàn)更復(fù)雜16點FFT規(guī)模不大建議還是直接用乘法器省心。綜合之后查一下報告確認乘法器被正確推斷成了DSP原語而不是被綜合器展開成一堆LUT。6.3 向更大點數(shù)擴展的架構(gòu)思路16點做完之后往32點、64點擴展的思路是現(xiàn)成的。基-2結(jié)構(gòu)下每增加一級級數(shù)加1旋轉(zhuǎn)因子表變大控制邏輯中的級數(shù)計數(shù)器和地址位寬相應(yīng)擴展。從單蝶形復(fù)用切換到多蝶形流水線也只需把多個蝶形單元和對應(yīng)的寄存器堆排成流水控制邏輯從狀態(tài)機變成簡單的地址生成器。如果你之后要處理多路并行FFT比如MIMO系統(tǒng)里每個通道都需要頻譜分析單蝶形復(fù)用方案就力不從心了。那時可以在“空分”上做文章復(fù)制多個蝶形單元每個通道一組RAM控制邏輯共享用基地址偏移區(qū)分通道這樣吞吐率可以成倍提高。我在實際項目中最終采用的是單蝶形復(fù)用逐級右移的組合綜合后LUT消耗不到1000DSP使用1個Latency約100拍。在數(shù)據(jù)速率不高的場景下這個實現(xiàn)的功耗和面積都比同配置的IP核要清爽。每次做FFT相關(guān)設(shè)計時我都會先問自己一句到底需不需要IP核的通用性如果只是固定點數(shù)、固定位寬的單通道場景手寫往往更香。