無線通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計(jì) 課件第2 章基于并行流水線的FFT計(jì)算方法及VLSI結(jié)構(gòu)

第2章基于并行流水線的FFT計(jì)算方法及VLSI結(jié)構(gòu)2.1面向硬件實(shí)現(xiàn)的radix-2k

FFT算法原理2.2FFT串行流水線計(jì)算結(jié)構(gòu)2.3FFT并行流水線計(jì)算方法2.4FFT混合抽取多路延遲反饋VLSI結(jié)構(gòu)2.5理論分析與硬件測試本章小結(jié)

2.1面向硬件實(shí)現(xiàn)的radix-2kFFT算法原理

對于輸入序列xn

，其

點(diǎn)FFT運(yùn)算表示為：其中n和k分別表示時間與頻率次序。系數(shù)

被稱為旋轉(zhuǎn)因子，其表達(dá)式為

傳統(tǒng)的Cooley-Turkey按頻率抽取的radix-2FFT算法將(2.1)按照奇偶頻率劃分為兩部分，即

利用混合基算法可以將

進(jìn)一步分解為：

圖2.1以16點(diǎn)FFT計(jì)算為例，分別給出了radix-22算法和radix-2算法下的信號流圖，其中非平凡旋轉(zhuǎn)因子的數(shù)量與分布很好地印證了結(jié)論。

2.2FFT串行流水線計(jì)算結(jié)構(gòu)

串行流水線結(jié)構(gòu)是中低速率FFT計(jì)算單元的常用VLSI實(shí)現(xiàn)方式，例如在Xilinx公司提供的FFTIP核中，串行流水線就是一類典型的硬件結(jié)構(gòu)。串行流水線結(jié)構(gòu)易于根據(jù)FFT計(jì)算長度的不同進(jìn)行裁剪或擴(kuò)展，計(jì)算吞吐量與工作時鐘相同，其頂層如圖2.2所示，可以分為FFT計(jì)算電路、旋轉(zhuǎn)因子存儲電路和數(shù)據(jù)排序電路三部分。

圖2.2FFT串行流水線計(jì)算結(jié)構(gòu)頂層方案

流水線計(jì)算單元具有兩種典型的電路結(jié)構(gòu)：延遲反饋結(jié)構(gòu)和延遲換向結(jié)構(gòu)。利用這些結(jié)構(gòu)，將數(shù)據(jù)按正確次序兩兩送入蝶形運(yùn)算單元進(jìn)行計(jì)算。另一方面，旋轉(zhuǎn)因子存儲及數(shù)據(jù)排序單元的設(shè)計(jì)方案，直接影響著串行流水線計(jì)算結(jié)構(gòu)的存儲開銷。下面首先說明流水線計(jì)算單元VLSI結(jié)構(gòu)和工作方式，然后給出數(shù)據(jù)排序單元和旋轉(zhuǎn)因子存儲單元的優(yōu)化設(shè)計(jì)方案。

2.2.1延遲反饋VLSI結(jié)構(gòu)

1984年，Wold首次提出了延遲反饋（Single-pathDelayFeedback，SDF）的串行流水線FFT計(jì)算結(jié)構(gòu)。SDF結(jié)構(gòu)中的反饋連接使得每一級運(yùn)算單元的輸入和輸出數(shù)據(jù)能夠共用同一存儲器，這保證了整個FFT計(jì)算模塊對存儲資源的最小消耗。延遲反饋VLSI結(jié)構(gòu)示意圖如圖2.3所示。

圖2.3延遲反饋VLSI結(jié)構(gòu)示意圖（以16點(diǎn)FFT計(jì)算為例）

一般地對于N點(diǎn)FFT運(yùn)算，延遲反饋結(jié)構(gòu)的典型電路特征為：

從信號輸入端開始，在第n級（n=1,2,...,log2N）蝶形運(yùn)算單元配置長度為N/2n的移位寄存器，因此延遲反饋結(jié)構(gòu)的寄存器開銷總計(jì)N-1；

移位寄存器與蝶形運(yùn)算單元之間存在數(shù)據(jù)反饋，即移位寄存器的輸出數(shù)據(jù)作為蝶形運(yùn)算單元的輸入，并且蝶形運(yùn)算單元的輸出數(shù)據(jù)作為因?yàn)榧拇嫫鞯妮斎搿?/p>

在SDF結(jié)構(gòu)中，通過控制數(shù)據(jù)選擇器調(diào)整數(shù)據(jù)流向，第n級蝶形運(yùn)算單元以N/2n-1個輸入數(shù)據(jù)為執(zhí)行周期，循環(huán)執(zhí)行以下步驟：

步驟1：當(dāng)?shù)?至第N/2n個有效數(shù)據(jù)輸入時，將其依次送入移位寄存器，同時移位寄存器中緩存的有效數(shù)據(jù)依次移出，乘以相應(yīng)的旋轉(zhuǎn)因子后送至下一級蝶形運(yùn)算單元；

步驟2：當(dāng)?shù)贜/2n+1至第N/2n-1個有效數(shù)據(jù)輸入時，與移位寄存器移出數(shù)據(jù)共同進(jìn)行radix-2蝶形運(yùn)算，其中相加結(jié)果乘以相應(yīng)的旋轉(zhuǎn)因子后送至下一級蝶形運(yùn)算單元，相減結(jié)果反饋至移位寄存器緩存。

2.2.2延遲換向VLSI結(jié)構(gòu)

將SDF流水線結(jié)構(gòu)的反饋環(huán)打開，并把運(yùn)算單元的輸入和輸出數(shù)據(jù)緩存在不同存儲器中，這樣就得到了延遲換向（Multi-pathDelayCommutator，MDC）的FFT流水線結(jié)構(gòu)。延遲換向VLSI結(jié)構(gòu)示意圖如圖2.4所示，對于N點(diǎn)FFT運(yùn)算，其典型電路特征為：

在第1級蝶形運(yùn)算單元的輸入端，利用長度為N/2的移位寄存器緩存第1至第N/2個輸入數(shù)據(jù)，緩存數(shù)據(jù)與第N/2+1至第N個輸入數(shù)據(jù)組成2路并行數(shù)據(jù)流送入第1級蝶形運(yùn)算單元；在第2級至第log2N級蝶形運(yùn)算單元的輸入端配置雙路延遲換向器，用于對前一級蝶形運(yùn)算單元的并行輸出數(shù)據(jù)進(jìn)行次序調(diào)整，其中第n級（n=1,2,...,log2N）蝶形運(yùn)算單元輸入端采用的延遲換向器集成了2組長度為N/2n的移位寄存器；因此延遲換向結(jié)構(gòu)的寄存器開銷總計(jì)3N/2-2

；

從第1級蝶形運(yùn)算單元的輸入開始，數(shù)據(jù)流以兩路并行的方式在流水線內(nèi)單向流動，不存在反饋環(huán)路。

圖2.4延遲換向VLSI結(jié)構(gòu)及數(shù)據(jù)次序變換示意圖（以16點(diǎn)FFT計(jì)算為例）

在MDC結(jié)構(gòu)中，蝶形運(yùn)算單元僅需對輸入并行數(shù)據(jù)進(jìn)行求和與相減運(yùn)算，然后并行輸出計(jì)算結(jié)果即可，對數(shù)據(jù)流的調(diào)整通過蝶形運(yùn)算單元輸入端的延遲換向器來實(shí)現(xiàn)。具體而言，第n級蝶形運(yùn)算單元輸入端配置的延遲換向器，以N/2n-1個上支路或下支路輸入數(shù)據(jù)為執(zhí)行周期，循環(huán)執(zhí)行以下步驟：

步驟1：配置延遲換向器中的數(shù)據(jù)選擇器，將上支路第1至第N/2n個有效數(shù)據(jù)寫入上支路移位寄存器，將下支路第1至第N/2n個有效數(shù)據(jù)寫入下支路移位寄存器；與此同時，將兩個移位寄存器移出的數(shù)據(jù)送至下一級蝶形運(yùn)算單元；

步驟2：調(diào)整數(shù)據(jù)選擇器，將上支路第N/2n+1至第N/2n-1個有效數(shù)據(jù)通過下支路輸出端口送至下一級蝶形運(yùn)算單元；將下支路第N/2n+1至第N/2n-1個有效數(shù)據(jù)寫入下支路移位寄存器，同時其移出數(shù)據(jù)作為上支路移位寄存器輸入；上支路移位寄存器移出數(shù)據(jù)送至下一級蝶形運(yùn)算單元；

2.2.3數(shù)據(jù)排序單元VLSI結(jié)構(gòu)

在FFT計(jì)算模塊內(nèi)，數(shù)據(jù)排序單元用于實(shí)現(xiàn)數(shù)據(jù)在自然序和倒位序之間的轉(zhuǎn)換。為了對長度為

的數(shù)據(jù)序列進(jìn)行次序調(diào)整，傳統(tǒng)方案首先利用存儲深度為M的RAM對全部數(shù)據(jù)進(jìn)行緩存，然后再生成讀地址將數(shù)據(jù)以新次序從RAM中讀出。為了能夠處理連續(xù)數(shù)據(jù)流，用于數(shù)據(jù)緩存的RAM需要構(gòu)建成乒乓操作結(jié)構(gòu)，此時的數(shù)據(jù)存儲開銷將達(dá)到2M

；如果RAM單元能夠以雙端口的方式同時支持讀寫操作，存儲器消耗可以減小至M，而控制復(fù)雜度會相應(yīng)提升。為了確定出數(shù)據(jù)排序單元的最小存儲開銷，首先需要對其中的數(shù)據(jù)進(jìn)行壽命分析。

圖2.5以M=16為例給出了倒位序排序的數(shù)據(jù)壽命分析圖，其中左側(cè)是時鐘周期標(biāo)號；數(shù)據(jù)的壽命周期在圖中用粗實(shí)線表示，它起始于數(shù)據(jù)產(chǎn)生或者輸入的時刻，到數(shù)據(jù)執(zhí)行完全部相關(guān)運(yùn)算或輸出時刻結(jié)束；特別地當(dāng)數(shù)據(jù)產(chǎn)生和終止于同一時刻時，數(shù)據(jù)的壽命周期為0，在圖中標(biāo)記為“”；圖右側(cè)統(tǒng)計(jì)了在同一時刻的有效數(shù)據(jù)個數(shù)，需要注意每個數(shù)據(jù)在其產(chǎn)生時刻被看作是無效數(shù)據(jù)；有效數(shù)據(jù)個數(shù)在全部時刻的最大值即為最小存儲開銷。從分析結(jié)果不難發(fā)現(xiàn)M=16的倒位序數(shù)據(jù)排序所對應(yīng)的最小存儲開銷為9，這低于傳統(tǒng)方案中16或32個數(shù)據(jù)的緩存需求。

圖2.4延遲換向VLSI結(jié)構(gòu)及數(shù)據(jù)次序變換示意圖（以16點(diǎn)FFT計(jì)算為例）

圖2.6數(shù)據(jù)排序單元最小存儲器消耗Lmin的物理意義

圖2.7達(dá)到最小存儲器消耗的流水線結(jié)構(gòu)數(shù)據(jù)排序單元

將M=2q代入(2.6)不難驗(yàn)證L=Lmin，這保證了所提出的次序變換方法能夠最高效地利用存儲資源。在硬件結(jié)構(gòu)方面，整個數(shù)據(jù)排序單元可以用一個nR級流水線來實(shí)現(xiàn)，其中流水線的第i級執(zhí)行第i輪排序操作。如圖2.8所示，流水線的第

級由一個長度為Lmin(i)的移位寄存器和共用同一信號ci的兩個數(shù)據(jù)選擇器構(gòu)成。

圖2.8倒位序次序變換方案的硬件實(shí)現(xiàn)結(jié)構(gòu)

當(dāng)ci=1時，第i級當(dāng)前輸入數(shù)據(jù)被直接送至第i+1級；反之若ci=0，當(dāng)前輸入數(shù)據(jù)被送至移位寄存器進(jìn)行緩存，同時移位寄存器的輸出被送至下一級。為了產(chǎn)生流水線每一級數(shù)據(jù)選擇器的控制信號，需要在流水線輸入端設(shè)置一個與輸入數(shù)據(jù)同步的q比特的計(jì)數(shù)器bq-1,...,b1b0，那么ci可以按照如下方式產(chǎn)生：

2.2.4旋轉(zhuǎn)因子優(yōu)化存儲結(jié)構(gòu)

在FFT計(jì)算過程中，中間結(jié)果需要乘以相應(yīng)的旋轉(zhuǎn)因子以實(shí)現(xiàn)數(shù)據(jù)旋轉(zhuǎn)。旋轉(zhuǎn)因子的非線性使其實(shí)時求解具有較高的計(jì)算復(fù)雜度，相比之下采用查找表的方式預(yù)先將離線計(jì)算出的旋轉(zhuǎn)因子存儲在FFT計(jì)算模塊內(nèi)是一種更常用的做法，不過這也帶來了額外的存儲資源消耗。利用正余弦函數(shù)的對稱特性，旋轉(zhuǎn)因子

所對應(yīng)的查找表只要涵蓋

相位范圍內(nèi)的取值即可，位于其他相位范圍的旋轉(zhuǎn)因子可以在此基礎(chǔ)上通過改變實(shí)虛部符號以及交換實(shí)虛部數(shù)值來產(chǎn)生，這一變換規(guī)則在表2.1中進(jìn)行了具體描述。

以旋轉(zhuǎn)因子實(shí)部的壓縮存儲為例，圖2.9對上面介紹的數(shù)據(jù)壓縮過程進(jìn)行了描述。圖2.9旋轉(zhuǎn)因子的壓縮存儲（以數(shù)據(jù)實(shí)部壓縮為示意）

在上述方案中，參數(shù)λ1的最優(yōu)值λ1*需要最小化查找表的存儲資源消耗，即

圖2.10不同參數(shù)配置下旋轉(zhuǎn)因子壓縮存儲的最優(yōu)分組長度

利用壓縮的數(shù)據(jù)正確恢復(fù)旋轉(zhuǎn)因子的步驟和硬件結(jié)構(gòu)如圖2.11所示。圖2.11利用壓縮存儲的數(shù)據(jù)恢復(fù)旋轉(zhuǎn)因子

2.3FFT并行流水線計(jì)算方法

一般地，N=2u點(diǎn)的FFT和IFFT運(yùn)算可以分別定義為下面的形式：

圖2.12FFT并行計(jì)算的頂層結(jié)構(gòu)框圖

2.4FFT混合抽取多路延遲反饋VLSI結(jié)構(gòu)

2.4.1基于折疊變換的延遲反饋結(jié)構(gòu)分析

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線結(jié)構(gòu)

2.4.2延遲反饋結(jié)構(gòu)計(jì)算調(diào)度優(yōu)化

(2.26)和(2.29)表明，無論采用DIF算法或DIT算法構(gòu)建SDF流水線，折疊矩陣中包含的空操作都將使得計(jì)算單元在某些時隙處于空閑狀態(tài)，這導(dǎo)致整個FFT計(jì)算模塊對計(jì)算資源的利用率只能達(dá)到50%左右。為解決這一問題，需要用有效運(yùn)算將折疊矩陣中的空操作進(jìn)行填充，這就涉及到了對折疊矩陣進(jìn)行變換。從本質(zhì)上講，折疊矩陣的變換實(shí)際上是對相應(yīng)數(shù)據(jù)流圖中的運(yùn)算操作進(jìn)行重新調(diào)度的過程，又因?yàn)檎郫B矩陣形式與具體電路結(jié)構(gòu)相對應(yīng)，在變換過程中能夠?qū)崿F(xiàn)對電路結(jié)構(gòu)的相應(yīng)調(diào)整以使之適應(yīng)新的運(yùn)算操作調(diào)度方式。具體而言，我們通過如下方式對SDF流水線的折疊矩陣進(jìn)行變換以提升計(jì)算資源的使用效率：

圖2.15能同時執(zhí)行DITFFT和DIFFFT的SDF流水線結(jié)構(gòu)

圖2.15中DIFSDF流水線與DITSDF流水線的結(jié)合將改變計(jì)算單元的底層結(jié)構(gòu)。根據(jù)原計(jì)算單元對復(fù)數(shù)乘法器利用率的不同，新計(jì)算單元將具有兩種硬件實(shí)現(xiàn)方式，如圖2.16所示。

圖2.16用于同時執(zhí)行DITFFT和DIFFFT的SDF計(jì)算單元結(jié)構(gòu)

圖2.16用于同時執(zhí)行DITFFT和DIFFFT的SDF計(jì)算單元結(jié)構(gòu)

2.4.3混合抽取多路延遲反饋VLSI結(jié)構(gòu)設(shè)計(jì)

對于圖2.12給出的FFT并行計(jì)算頂層結(jié)構(gòu)，用于執(zhí)行橫向DFT運(yùn)算的

條SDF流水線可以利用前面描述的運(yùn)算操作調(diào)度方法進(jìn)行優(yōu)化設(shè)計(jì)，這便引出了M2DF并行流水線結(jié)構(gòu)。我們首先以

的radix-2M2DF結(jié)構(gòu)（簡記為R2M2DF結(jié)構(gòu)）為例來對硬件設(shè)計(jì)方案進(jìn)行說明。如圖2.17所示。

圖2.17R2M2DF并行流水線結(jié)構(gòu)（N=32,P=2）

2.5理論分析與硬件測試

2.5.1并行流水線FFT結(jié)構(gòu)的資源消耗估計(jì)與比較在流水線FFT計(jì)算結(jié)構(gòu)中，蝶形運(yùn)算單元的構(gòu)建需要用到復(fù)數(shù)加法器，而數(shù)據(jù)旋轉(zhuǎn)則依靠復(fù)數(shù)乘法器來完成。復(fù)數(shù)乘法器可以進(jìn)一步分為通用復(fù)數(shù)乘法器和常數(shù)復(fù)數(shù)乘法器，前者可以基于任意旋轉(zhuǎn)因子來旋轉(zhuǎn)數(shù)據(jù)，而后者只適用于某些特定的旋轉(zhuǎn)因子，如實(shí)部與虛部模值相同的旋轉(zhuǎn)因子

或其他給定的旋轉(zhuǎn)因子。

另一方面，流水線FFT計(jì)算模塊還需要利用存儲器來緩存中間計(jì)算結(jié)果，存儲旋轉(zhuǎn)因子以及調(diào)整數(shù)據(jù)次序。用于緩存中間計(jì)算結(jié)果的存儲器通常以移位寄存器的形式分布在流水線的每一級，它們在數(shù)據(jù)選擇器的控制下將數(shù)據(jù)按正確次序送至運(yùn)算單元完成計(jì)算。存儲旋轉(zhuǎn)因子的存儲器以查找表的形式集成在FFT計(jì)算模塊內(nèi)，它保證了計(jì)算過程中旋轉(zhuǎn)因子的實(shí)時獲取。

表2.2對不同并行度下MDF結(jié)構(gòu)、M2DF結(jié)構(gòu)以及MDC結(jié)構(gòu)的硬件資源消耗與計(jì)算時延進(jìn)行了估計(jì)，其中FFT計(jì)算模塊的輸入和輸出數(shù)據(jù)流分別具有(2.19)中

和

的形式，計(jì)算時延被定義為FFT計(jì)算模塊的首組輸入數(shù)據(jù)和首組輸出數(shù)據(jù)之間的時鐘周期個數(shù)。

2.5.2M2DF結(jié)構(gòu)的硬件實(shí)現(xiàn)與測試

我們在XilinxVirtex6FPGA上對本章設(shè)計(jì)的M2DF結(jié)構(gòu)和其他流水線FFT計(jì)算結(jié)構(gòu)進(jìn)行了硬件實(shí)現(xiàn)，其中FPGA型號為XC6VLX240T-3FF784，所用的編譯器版本為ISE12.4。

在不同配置方式下各流水線FFT計(jì)算結(jié)構(gòu)的硬件資源開銷和計(jì)算時延、吞吐量等性能記錄在了表2.3中

以radix-和radix-FFT算法對應(yīng)的應(yīng)用場景為例，圖2.20統(tǒng)計(jì)了不同流水線FFT計(jì)算結(jié)構(gòu)的算術(shù)運(yùn)算與邏輯操作對sliceLUTs的消耗情況。整體來看，構(gòu)建M2DF結(jié)構(gòu)所需的sliceLUTs最少，MDC結(jié)構(gòu)次之，而MDF結(jié)構(gòu)消耗的sliceLUTs最多。此外可以發(fā)現(xiàn)三種流水線結(jié)構(gòu)均在蝶形運(yùn)算單元的實(shí)現(xiàn)上消耗了大量的sliceLUTs資源，由于MDF結(jié)構(gòu)和其他兩種方案相比需要更多的加法器來完成運(yùn)算，因而其對sliceLUTs的需求量也更大。M2DF結(jié)構(gòu)的計(jì)算單元需要同時對DIT數(shù)據(jù)流的DIF數(shù)據(jù)流進(jìn)行控制，這使其在數(shù)據(jù)流控制方面消耗的sliceLUTs略高于MDC結(jié)構(gòu)和MDF結(jié)構(gòu)。MDC結(jié)構(gòu)的數(shù)據(jù)流排序比其他兩種方案更為復(fù)雜，因此在這一操作上利用到的sliceLUTs最多。

圖2.20FFT計(jì)算模塊內(nèi)的不同操作對sliceLUTs消耗情況統(tǒng)計(jì)

圖2.20FFT計(jì)算模塊內(nèi)的不同操作對sliceLUTs消耗情況統(tǒng)計(jì)

不同流水線FFT計(jì)算結(jié)構(gòu)的存儲資源消耗在表2.3中通過所占用的塊RAM個數(shù)來體現(xiàn)，需要指出的是在實(shí)現(xiàn)過程中所有方案都采用的相同的旋轉(zhuǎn)因子存儲方法，因此塊RAM個數(shù)的區(qū)別主要來自于流水線結(jié)構(gòu)設(shè)計(jì)。前面在對表2.2中的數(shù)據(jù)進(jìn)行分析時指出，MDF結(jié)構(gòu)和M2DF結(jié)構(gòu)能夠比MDC結(jié)構(gòu)更為有效地利用存儲資源，這一結(jié)論從表2.3的實(shí)驗(yàn)結(jié)果中也得到了很好的印證。另一方面，我們發(fā)現(xiàn)