于 建，范浩陽

（河北民族師范學(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）、無線個(gè)人局域網(wǎng)（Wireless personal area networks，WPANs）和長期演進(jìn)（Long term evolution，LTE）等［2］。在不同的OFDM 系統(tǒng)中，載波的數(shù)量正比于FFT 變換長度，例如，WiMAX 系統(tǒng)中FFT 的采樣點(diǎn)數(shù)支持256點(diǎn)FFT 變換長度，因此設(shè)計(jì)一種有效的256 點(diǎn)FFT 處理器非常必要。

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

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

1 設(shè)計(jì)思考

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

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

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

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

2 256 點(diǎn)FFT 處理器IP 核設(shè)計(jì)

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

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

2.1 蝶形單元

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

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

2.2 CSD 常數(shù)乘法器

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

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

在利用MATLAB 對本文所設(shè)計(jì)的256 點(diǎn)IP 核進(jìn)行建模時(shí)，表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è)計(jì)CSD 常數(shù)乘法單元時(shí)所需的旋轉(zhuǎn)因子為：。其中：，因此只需考慮3 個(gè)旋轉(zhuǎn)因子：即可。又因?yàn)椋?0.923 9-j0.382 7，=0.707 1-j0.707 1，=0.382 7-j0.923 9，所以只需對3 個(gè)常數(shù)值（0.923 9，0.382 6，0.707 1）進(jìn)行CSD 化。表2 所示為3 個(gè)常數(shù)值的CSD 表示，為了保證量化噪聲比（Signal-to-quantization-noise ratio，SQNR），這里選擇字長為12 位，如果繼續(xù)增加字長SQNR并無明顯的變化。圖3 所示為不同k值的基-2k算法在不同旋轉(zhuǎn)因子字長的條件下所得到的SQNR 值。由圖3 可知，當(dāng)旋轉(zhuǎn)因子字長為12 位時(shí)，SQNR 值達(dá)到了飽和。

圖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

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

圖4 所示為適配于旋轉(zhuǎn)因子的CSD 常數(shù)乘法器架構(gòu)，其中“d”為輸入的復(fù)數(shù)序列，輸出端的2 個(gè)4 選1 數(shù)據(jù)選擇器完成輸入的復(fù)數(shù)序列與旋轉(zhuǎn)因子進(jì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ù)值的個(gè)數(shù)，隨著旋轉(zhuǎn)因子常數(shù)值個(gè)數(shù)的增多，CSD常數(shù)乘法器的優(yōu)勢越來越不明顯，當(dāng)旋轉(zhuǎn)因子的N值超過64 時(shí)，普通的CSD 常數(shù)乘法器在設(shè)計(jì)上會(huì)相當(dāng)復(fù)雜，與常用的布斯乘法器相比，在硬件成本控制上已無優(yōu)勢可言。為了處理旋轉(zhuǎn)因子的復(fù)數(shù)乘法運(yùn)算，本文提出了一種串接CSD 常數(shù)乘法器，通過對旋轉(zhuǎn)因子的i值進(jìn)行合理的分解，達(dá)到減少旋轉(zhuǎn)因子常數(shù)值的目的。根據(jù)旋轉(zhuǎn)因子的對稱性，將旋轉(zhuǎn)因子的i值平均劃分到8 個(gè)區(qū)域（A～H），設(shè)A區(qū)域旋轉(zhuǎn)因子的表達(dá)式為=xp+jyp(p=0～32)，那么其他區(qū)域旋轉(zhuǎn)因子的表達(dá)式可通過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)，進(jìn)一步縮小參變量指數(shù)的范圍。最后，將分解后的常數(shù)值進(jìn)行CSD 化，并找出相應(yīng)的可被重復(fù)利用的CSE 完成設(shè)計(jì)。串接CSD 常數(shù)乘法器需要進(jìn)行2 個(gè)階段的復(fù)數(shù)乘法運(yùn)算來完成一個(gè)完整的復(fù)數(shù)乘法運(yùn)算，其具體的數(shù)學(xué)表達(dá)如式（2）所示。例如，如果要實(shí)現(xiàn)d×，令p1=3，p2=1 即可。

表4 所示為適配于旋轉(zhuǎn)因子12 組常數(shù)值的CSD 表示，CSE1為紅色橢圓圈起的“101”（或），CSE2為藍(lán)色橢圓圈起的“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 模塊由加法單元右移模塊完成，矩形方塊即為右移模塊，利用簡單的硬件連接被放置在適當(dāng)?shù)奈恢?，通過4 選1 選擇單元與8 選1 選擇單元用于得到最終的計(jì)算結(jié)果。

由于串接CSD 乘法器需要兩個(gè)階段的乘法運(yùn)算，會(huì)導(dǎo)致整體FFT 處理器的運(yùn)算速度降低，為了減少關(guān)鍵路徑，在兩階段復(fù)數(shù)乘法接口處插入流水線型寄存器，如圖5（b）左圖所示。圖5（b）右圖所示為具體的控制邏輯，只需利用旋轉(zhuǎn)因子的指數(shù)i，通過簡單的二進(jìn)制補(bǔ)碼與選擇操作便可獲得對應(yīng)于p1和p2的控制邏輯，綜合后的結(jié)果顯示其所消耗的硬件資源只占整體串接乘法器總硬件成本的0.96%。與常用的布斯乘法器相比，本文所提出的適配于旋轉(zhuǎn)因子的串接CSD 常數(shù)乘法器能夠節(jié)約34% LEs 的使用量，同時(shí)能夠移除存儲(chǔ)旋轉(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è)計(jì)的FFT 處理器IP 核進(jìn)行建模，并利用Intel的QUARTUS PRIME平臺(tái)和Cyclone 10LP FPGA 進(jìn)行綜合和性能評估。另外，與定點(diǎn)數(shù)運(yùn)算相比，雖然浮點(diǎn)運(yùn)算能夠在一定程度上提高數(shù)據(jù)精度，但其所需的硬件電路復(fù)雜，硬件資源消耗大，而且運(yùn)算速度慢，因此，本文的設(shè)計(jì)采用定點(diǎn)字長方案，同時(shí)采取了逐級運(yùn)算增加字長的方案，有效防止了數(shù)據(jù)溢出的問題。驗(yàn)證結(jié)果表明，對于256點(diǎn)24位符號(hào)數(shù)FFT 運(yùn)算，本文方案所設(shè)計(jì)的FFT 處理器最大時(shí)鐘頻率可以達(dá)到100 MHz，延遲為255個(gè)時(shí)鐘周期，只需消耗3 978 LEs和6 456 MBs的硬件資源。表5所示為本文方案與國內(nèi)外其他設(shè)計(jì)方案在設(shè)計(jì)256點(diǎn)FFT 處理器的比較結(jié)果。為了更加直觀地進(jìn)行比較，參考文獻(xiàn)的設(shè)計(jì)方案同樣是利用Verilog HDL進(jìn)行建模，在基于Intel的QUARTUS PRIME 平臺(tái)和Cyclone 10LP FPGA 進(jìn)行綜合和性能評估。由表5可知，文獻(xiàn)［2］采用了基-16算法來減少旋轉(zhuǎn)因子的復(fù)雜度，但其蝶形單元復(fù)雜不易于硬件實(shí)現(xiàn)，而且在處理256點(diǎn)FFT 復(fù)數(shù)乘法運(yùn)算時(shí)采用了常規(guī)的復(fù)數(shù)乘法器，硬件資源消耗高；文獻(xiàn)［7］采用了基-4 MBA 架構(gòu)，雖然在一定程度上減少了實(shí)現(xiàn)時(shí)所需的硬件資源，但其延時(shí)大并在處理旋轉(zhuǎn)因子復(fù)數(shù)乘法時(shí)采用了普通復(fù)數(shù)乘法器，相較于本文提出的全CSD 常數(shù)乘法器方案，本文方案所占用的硬件資源更少、延時(shí)更??；文獻(xiàn)［13］采用了多路徑混合基MDC 架構(gòu)，在一定程度上提升了硬件使用效率與工作頻率，但其硬件實(shí)現(xiàn)架構(gòu)與控制邏輯復(fù)雜，而且同樣利用普通復(fù)數(shù)乘法器完成256點(diǎn)FFT 計(jì)算，硬件資源消耗高；文獻(xiàn)［14］由于其所選擇的算法在處理256點(diǎn)FFT 計(jì)算時(shí)旋轉(zhuǎn)因子更復(fù)雜、復(fù)數(shù)乘法的運(yùn)算量更高（表1），因此在硬件成本控制方面并不理想。綜上所述，本文方案在設(shè)計(jì)低硬件成本256點(diǎn)FFT 處理器時(shí)更具優(yōu)勢。

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

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

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

4 結(jié)束語

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