低硬件成本256 點FFT 處理器的IP 核設(shè)計

于 建，范浩陽

（河北民族師范學(xué)院物理與電子工程學(xué)院，承德 067000）

引 言

快速傅里葉變換（Fast Fourier transform，F(xiàn)FT）是現(xiàn)代通信領(lǐng)域非常重要的技術(shù)，尤其在正交頻分復(fù)用（Orthogonal frequency division multiplexing，OFDM）并行傳輸技術(shù)中的廣泛應(yīng)用［1］，如IEEE 802.11a/g/n、全球微波互聯(lián)接入（Worldwide interoperability for microwave access，WiMAX）、無線個人局域網(wǎng)（Wireless personal area networks，WPANs）和長期演進（Long term evolution，LTE）等［2］。在不同的OFDM 系統(tǒng)中，載波的數(shù)量正比于FFT 變換長度，例如，WiMAX 系統(tǒng)中FFT 的采樣點數(shù)支持256點FFT 變換長度，因此設(shè)計一種有效的256 點FFT 處理器非常必要。

在OFDM 系統(tǒng)中的物理層，F(xiàn)FT 模塊是最為復(fù)雜的運算模塊，為了減少其硬件成本，已有很多學(xué)者對其進行了研究。李成詩等［3］在設(shè)計FFT 處理器時，利用坐標旋轉(zhuǎn)數(shù)字計算（Coordinate rotation digital computer，CORDIC）算法降低硬件成本消耗；王琳［4］提出通過優(yōu)化基-4 算法結(jié)構(gòu)減少FFT 處理器的硬件資源消耗；Fan 等［5］利用布斯乘法器與CSD（Canonic signal digit）常數(shù)乘法器混合方案減少其所設(shè)計的FFT 處理器的硬件成本；Wang 等［6］為了減少硬件成本，提出了一種2 乘法器和3 加法器流水線型蝶形單元用于處理FFT 處理器的實現(xiàn)；楊琳琳等［7］通過對蝶形單元結(jié)構(gòu)的優(yōu)化，減少乘法器的數(shù)目，從而達到減少FFT 處理器硬件成本的目的；孫曉鋒等［8］提出了基于Turbo 結(jié)構(gòu)的FFT 處理器實現(xiàn)方案來降低硬件開銷。

復(fù)數(shù)乘法器在FFT 處理器的設(shè)計中占用主要的硬件資源，以往的這些研究在處理旋轉(zhuǎn)因子的復(fù)數(shù)乘法時，都只利用常用的布斯乘法器與只讀存儲器ROM 來完成，無法有效地控制其所消耗的硬件資源。基于此，本文設(shè)計了一種基于現(xiàn)場可編程門陣列（Field programmable gate array，F(xiàn)PGA）的低硬件成本256 點FFT 處理器IP 核，為了減少旋轉(zhuǎn)因子的計算復(fù)雜度，采用了基-24算法和SDF 流水線架構(gòu)來完成設(shè)計，提出了一種串接CSD 常數(shù)乘法器，通過簡單的加法單元、移位單元以及選擇單元來完成旋轉(zhuǎn)因子與輸入序列的復(fù)數(shù)乘法運算，同時無須ROM 對旋轉(zhuǎn)因子系數(shù)進行存儲，大幅降低了整個FFT 處理器設(shè)計的硬件成本。

1 設(shè)計思考

若輸入序列為x(n)，那么N點離散傅里葉變換（Discrete Fourier transform，DFT）X(k)定義為

式中旋轉(zhuǎn)因子=e-j2πnk/N。

直接實現(xiàn)式（1）中的離散傅里葉變換需要消耗大量的硬件成本和計算時間。因此Tukey 與Cooley提出了基-2 快速傅里葉變換算法用于減少離散傅里葉變換的計算時間與硬件資源消耗。為了減少旋轉(zhuǎn)因子計算復(fù)雜度，基-4 算法應(yīng)運而生，雖然能夠降低旋轉(zhuǎn)因子的復(fù)雜度，但是蝶形單元結(jié)構(gòu)復(fù)雜，不易于硬件實現(xiàn)。后來基-2k算法［9］出現(xiàn)，較于基-2 算法，不但具有與其同樣簡單的蝶形單元結(jié)構(gòu)，還能夠像基-4 算法一樣簡化旋轉(zhuǎn)因子的復(fù)雜度?；诨?2k算法的256 點FFT 處理器的計算包括7 個階段。不管k值如何，基-2k算法在每個階段都保留了與基-2 算法相同的蝶形單元架構(gòu)，但是k值的不同會導(dǎo)致不同階段旋轉(zhuǎn)因子的不同。表1 所示為不同k值下，256 點FFT 在每個階段旋轉(zhuǎn)因子的詳細分布，其中的“-j”為普通運算，只需對輸入序列實部和虛部的位置進行交換，再對虛部求反即可。由表1 可知，由于具有更低的復(fù)數(shù)乘法運算量與更低復(fù)雜度的旋轉(zhuǎn)因子，基-24算法在處理256 點FFT 計算方面更具優(yōu)勢，因此本文的設(shè)計采用基-24算法。

表1 256 點基-2k算法旋轉(zhuǎn)因子序列分布Table 1 Sequence distribution of 256-point FFT twiddle factor for radix-2k algorithm

通常來說，F(xiàn)FT 處理器架構(gòu)一般可分為兩種不同的類型：基于記憶體架構(gòu)（Memory-based architec-ture，MBA）和流水線架構(gòu)［10］。前者一般由主處理單元，即蝶形單元，存儲單元與控制邏輯所組成，這種架構(gòu)雖然能夠減少所需的硬件資源和功耗，但是其數(shù)據(jù)吞吐量低、延遲高，無法滿足數(shù)據(jù)的實時處理需求。而后者雖然相對來說消耗更多的硬件資源，但其具有更高的數(shù)據(jù)吞吐量。流水線架構(gòu)的FFT 處理器的設(shè)計又可以分為兩種風格：前向反饋（Feedforward）和后向反饋（Feedback）。前向反饋又可分為單路延遲轉(zhuǎn)換（Single-path delay commutator，SDC）和多路延遲轉(zhuǎn)換（Multi-path delay commutator，MDC）［11］；負向反饋又可分為單路延遲負反饋（Single-path delay feedback，SDF）和多路延遲負反饋（Multi-path delay feedback，MDF）［12］。與前向反饋風格相比，負向反饋風格具有更簡單的控制邏輯，負向反饋風格中的MDF 架構(gòu)較SDF 架構(gòu)需要消耗更多的硬件資源。由于SDF 架構(gòu)具有硬件資源消耗低、易于實現(xiàn)等特點，因此本文的設(shè)計采用SDF 流水線架構(gòu)。

2 256 點FFT 處理器IP 核設(shè)計

圖1 所示為基-24算法256 點FFT 的SDF 流水線架構(gòu)圖。由圖1 可知，本文設(shè)計的FFT 處理器架構(gòu)由兩種類型的蝶形單元（BFⅠ型和BFⅡ型）、不同容量的延遲緩沖單元（用于給蝶形單元的輸入提供恰當?shù)臄?shù)據(jù)以及數(shù)據(jù)整理）以及?代表的復(fù)數(shù)乘法單元所組成?？刂菩盘栍糜谇袚Q蝶形單元的類型并為旋轉(zhuǎn)因子的復(fù)數(shù)乘法運算提供合適的控制邏輯。為了獲得更少的硬件成本收益，復(fù)數(shù)乘法運算全部由CSD 常數(shù)乘法器來完成。

圖1 基-24算法256 點SDF FFT 結(jié)構(gòu)圖Fig.1 Block diagram of 256-point SDF FFT with radix-24 algorithm

2.1 蝶形單元

圖2 所示為本文所提出的256 點FFT 處理器IP 核所需蝶形單元的具體結(jié)構(gòu)，圖2（a）為BFⅠ型，圖2（b）為BFⅡ型。蝶形單元主要伴隨緩沖單元的輸入執(zhí)行復(fù)數(shù)加法與復(fù)數(shù)減法運算［13］，其中BFⅡ型蝶形單元除了進行基本的加減法運算，還要進行額外的“-j”運算，因此多出了額外的控制邏輯，如圖2（b）所示。xr(n)和xr(n+N/2)代表輸入序列的實部，xi(n)和xi(n+N/2)代表輸入序列的虛部，zr(n)和zr(n+N/2)代表輸出數(shù)據(jù)的實部，zi(n)和zi(n+N/2)代表輸出數(shù)據(jù)的虛部?！皌”和“c”是蝶形單元運算時所需的控制信號。蝶形單元運算過程如下，輸入數(shù)據(jù)序列的按照順序儲存到先進先出寄存器中，直到第N/2 個數(shù)據(jù)（N為FFT 點數(shù)），接下來的輸入數(shù)據(jù)與先前存放在寄存器中的數(shù)據(jù)依次進行復(fù)數(shù)加減法運算。蝶形單元所進行的復(fù)數(shù)加法運算直接作為下一個階段的輸入數(shù)據(jù)，而減法運算結(jié)果存入下一階段的先進先出延遲緩沖單元中。

圖2 蝶形單元架構(gòu)Fig.2 Block diagram of butterfly unit

2.2 CSD 常數(shù)乘法器

一般來說，在特定階段蝶形單元的輸出數(shù)據(jù)都要與相應(yīng)的旋轉(zhuǎn)因子進行復(fù)數(shù)乘法運算來得到正確的輸出。由圖1 可知，本文所設(shè)計的256 點FFT 處理器需要兩種CSD 常數(shù)乘法器用于旋轉(zhuǎn)因子與的復(fù)數(shù)乘法運算。

2.2.1 適配于旋轉(zhuǎn)因子的CSD 常數(shù)乘法器

在利用MATLAB 對本文所設(shè)計的256 點IP 核進行建模時，表1 中第2 階段與第6 階段的旋轉(zhuǎn)因子W i16的i值分別由如下代碼生成。

（1）第2 階段：tw=[zeros(1，16)，ones(1，16)，2*ones(1，16)，3*ones(16)] i_stg2=[0.*tw，2.*tw，3.*tw ]

（2）第6 階段：tw=repmat([0 0 0 0 0 2 4 6 0 1 2 3 0 3 6 9]，16)；i_stg6=tw(1，：)

由此可知，在設(shè)計CSD 常數(shù)乘法單元時所需的旋轉(zhuǎn)因子為：。其中：，因此只需考慮3 個旋轉(zhuǎn)因子：即可。又因為：=0.923 9-j0.382 7，=0.707 1-j0.707 1，=0.382 7-j0.923 9，所以只需對3 個常數(shù)值（0.923 9，0.382 6，0.707 1）進行CSD 化。表2 所示為3 個常數(shù)值的CSD 表示，為了保證量化噪聲比（Signal-to-quantization-noise ratio，SQNR），這里選擇字長為12 位，如果繼續(xù)增加字長SQNR并無明顯的變化。圖3 所示為不同k值的基-2k算法在不同旋轉(zhuǎn)因子字長的條件下所得到的SQNR 值。由圖3 可知，當旋轉(zhuǎn)因子字長為12 位時，SQNR 值達到了飽和。

圖3 不同旋轉(zhuǎn)因子字長基-2k算法SQNR 比較Fig.3 SNQR comparison of different twiddle factor word lengths for radix-2k algorithm

表2 12 位字長3 常數(shù)值的CSD 表示Table 2 CSD representation of three constant values with 12-bit word-length

為進一步節(jié)約硬件成本，找出能夠在硬件實現(xiàn)上被重復(fù)利用的最優(yōu)公共子表達式共享模塊（Common sub-expression sharing block，CSE），表2中紅色橢圓圈起的“101”或即為最優(yōu)的CSE，其中代表-1。

圖4 所示為適配于旋轉(zhuǎn)因子的CSD 常數(shù)乘法器架構(gòu)，其中“d”為輸入的復(fù)數(shù)序列，輸出端的2 個4 選1 數(shù)據(jù)選擇器完成輸入的復(fù)數(shù)序列與旋轉(zhuǎn)因子進行復(fù)數(shù)乘法后的輸出結(jié)果。綜合后的結(jié)果顯示，對比常用的布斯乘法器可節(jié)約72% LEs 的使用量。

圖4 適配于旋轉(zhuǎn)因子 的CSD 常數(shù)乘法器架構(gòu)Fig.4 Structure of CSD constant multiplier for twiddle factor

2.2.2 適配旋轉(zhuǎn)因子的串接CSD 常數(shù)乘法器

CSD 常數(shù)乘法器的復(fù)雜度依賴于旋轉(zhuǎn)因子常數(shù)值的個數(shù)，隨著旋轉(zhuǎn)因子常數(shù)值個數(shù)的增多，CSD常數(shù)乘法器的優(yōu)勢越來越不明顯，當旋轉(zhuǎn)因子的N值超過64 時，普通的CSD 常數(shù)乘法器在設(shè)計上會相當復(fù)雜，與常用的布斯乘法器相比，在硬件成本控制上已無優(yōu)勢可言。為了處理旋轉(zhuǎn)因子的復(fù)數(shù)乘法運算，本文提出了一種串接CSD 常數(shù)乘法器，通過對旋轉(zhuǎn)因子的i值進行合理的分解，達到減少旋轉(zhuǎn)因子常數(shù)值的目的。根據(jù)旋轉(zhuǎn)因子的對稱性，將旋轉(zhuǎn)因子的i值平均劃分到8 個區(qū)域（A～H），設(shè)A區(qū)域旋轉(zhuǎn)因子的表達式為=xp+jyp(p=0～32)，那么其他區(qū)域旋轉(zhuǎn)因子的表達式可通過A區(qū)域的映射獲得，詳情如表3 所示。

表3 8 區(qū)域中旋轉(zhuǎn)因子對應(yīng)的映射Table 3 Mapping of twiddle factor in eight symmetric regions

通過這樣的方式，旋轉(zhuǎn)因子指數(shù)范圍由i=0～255 減少到p=0～31，再將參變量p分解為p=4p1+p2(p1=1～8，p2=0～3)，進一步縮小參變量指數(shù)的范圍。最后，將分解后的常數(shù)值進行CSD 化，并找出相應(yīng)的可被重復(fù)利用的CSE 完成設(shè)計。串接CSD 常數(shù)乘法器需要進行2 個階段的復(fù)數(shù)乘法運算來完成一個完整的復(fù)數(shù)乘法運算，其具體的數(shù)學(xué)表達如式（2）所示。例如，如果要實現(xiàn)d×，令p1=3，p2=1 即可。

表4 所示為適配于旋轉(zhuǎn)因子12 組常數(shù)值的CSD 表示，CSE1為紅色橢圓圈起的“101”（或），CSE2為藍色橢圓圈起的“10”（或01），CSE3為紫色橢圓圈起的“1000”（或0001）。

表4 12 位字長12 組常數(shù)值CSD 表示Table 4 CSD representation of twelve constant values with 12-bit word-length

圖5 所示為適配于旋轉(zhuǎn)因子串接CSD 常數(shù)乘法器的整體架構(gòu)圖。圖5（a）所示為適配于旋轉(zhuǎn)因子的串接CSD 常數(shù)乘法器的邏輯模塊，其中最優(yōu)CSE 模塊由加法單元右移模塊完成，矩形方塊即為右移模塊，利用簡單的硬件連接被放置在適當?shù)奈恢茫ㄟ^4 選1 選擇單元與8 選1 選擇單元用于得到最終的計算結(jié)果。

由于串接CSD 乘法器需要兩個階段的乘法運算，會導(dǎo)致整體FFT 處理器的運算速度降低，為了減少關(guān)鍵路徑，在兩階段復(fù)數(shù)乘法接口處插入流水線型寄存器，如圖5（b）左圖所示。圖5（b）右圖所示為具體的控制邏輯，只需利用旋轉(zhuǎn)因子的指數(shù)i，通過簡單的二進制補碼與選擇操作便可獲得對應(yīng)于p1和p2的控制邏輯，綜合后的結(jié)果顯示其所消耗的硬件資源只占整體串接乘法器總硬件成本的0.96%。與常用的布斯乘法器相比，本文所提出的適配于旋轉(zhuǎn)因子的串接CSD 常數(shù)乘法器能夠節(jié)約34% LEs 的使用量，同時能夠移除存儲旋轉(zhuǎn)因子系數(shù)的ROM。

圖5 適配于旋轉(zhuǎn)因子 串接CSD 常數(shù)乘法器整體架構(gòu)詳解Fig.5 Overall detailed cascade CSD multiplier for twiddle factor

3 結(jié)果與比較

本文采用Verilog HDL 對所設(shè)計的FFT 處理器IP 核進行建模，并利用Intel的QUARTUS PRIME平臺和Cyclone 10LP FPGA 進行綜合和性能評估。另外，與定點數(shù)運算相比，雖然浮點運算能夠在一定程度上提高數(shù)據(jù)精度，但其所需的硬件電路復(fù)雜，硬件資源消耗大，而且運算速度慢，因此，本文的設(shè)計采用定點字長方案，同時采取了逐級運算增加字長的方案，有效防止了數(shù)據(jù)溢出的問題。驗證結(jié)果表明，對于256點24位符號數(shù)FFT 運算，本文方案所設(shè)計的FFT 處理器最大時鐘頻率可以達到100 MHz，延遲為255個時鐘周期，只需消耗3 978 LEs和6 456 MBs的硬件資源。表5所示為本文方案與國內(nèi)外其他設(shè)計方案在設(shè)計256點FFT 處理器的比較結(jié)果。為了更加直觀地進行比較，參考文獻的設(shè)計方案同樣是利用Verilog HDL進行建模，在基于Intel的QUARTUS PRIME 平臺和Cyclone 10LP FPGA 進行綜合和性能評估。由表5可知，文獻［2］采用了基-16算法來減少旋轉(zhuǎn)因子的復(fù)雜度，但其蝶形單元復(fù)雜不易于硬件實現(xiàn)，而且在處理256點FFT 復(fù)數(shù)乘法運算時采用了常規(guī)的復(fù)數(shù)乘法器，硬件資源消耗高；文獻［7］采用了基-4 MBA 架構(gòu)，雖然在一定程度上減少了實現(xiàn)時所需的硬件資源，但其延時大并在處理旋轉(zhuǎn)因子復(fù)數(shù)乘法時采用了普通復(fù)數(shù)乘法器，相較于本文提出的全CSD 常數(shù)乘法器方案，本文方案所占用的硬件資源更少、延時更小；文獻［13］采用了多路徑混合基MDC 架構(gòu)，在一定程度上提升了硬件使用效率與工作頻率，但其硬件實現(xiàn)架構(gòu)與控制邏輯復(fù)雜，而且同樣利用普通復(fù)數(shù)乘法器完成256點FFT 計算，硬件資源消耗高；文獻［14］由于其所選擇的算法在處理256點FFT 計算時旋轉(zhuǎn)因子更復(fù)雜、復(fù)數(shù)乘法的運算量更高（表1），因此在硬件成本控制方面并不理想。綜上所述，本文方案在設(shè)計低硬件成本256點FFT 處理器時更具優(yōu)勢。

表5 不同設(shè)計方案綜合結(jié)果比較Table 5 Performance comparison of the proposed scheme compared with previous implementations

圖6所示為MODELSIM 輸出仿真結(jié)果的幅度值與MATLAB計算結(jié)果幅度值的比較（設(shè)輸入序列的實部和虛部為1～256，即xr(n)=[1∶256]，xi(n)=[1∶256]），其中“*”代表MATLAB 計算結(jié)果，“Δ”代表MODELSIM輸出仿真結(jié)果。由圖6可知，兩者的結(jié)果完全吻合，證明了設(shè)計的有效性。

圖6 MODELSIM 仿真結(jié)果與MATLAB 計算結(jié)果比較Fig.6 Comparison between MODELSIM simulation result and MATLAB calculation result

4 結(jié)束語

本文設(shè)計了一種低硬件成本256 點FFT 處理器IP 核，設(shè)計上采用了基-24算法與SDF 流水線架構(gòu)。為了最小化硬件資源的消耗，提出了一種適配于旋轉(zhuǎn)因子的串接CSD 常數(shù)乘法器，利用旋轉(zhuǎn)因子的對稱性以及對旋轉(zhuǎn)因子指數(shù)合理的分解，減少了旋轉(zhuǎn)因子進行復(fù)數(shù)乘法運算所需的常數(shù)值個數(shù)，令其所占用的硬件資源比常用的布斯乘法器減少了34%的LEs 使用量，而且無須ROM 對旋轉(zhuǎn)因子系數(shù)進行存儲。此外，為了保證處理器的工作頻率，在串接CSD 常數(shù)乘法器的設(shè)計中引入了流水線型寄存器，減少了關(guān)鍵路徑，F(xiàn)FT 處理器的最高工作頻率達到了100 MHz，且延時只需255 個時鐘周期。基于QUARTUS PRIME 平臺的綜合結(jié)果表明，對比已有的方案，本文方案在設(shè)計256 點FFT處理器方面能夠更加有效控制硬件成本。