無線通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計 課件全套 第1-7章 無線通信系統(tǒng)中FFT與信道譯碼技術(shù)-無人機通信系統(tǒng)VLSI設(shè)計

第1章無線通信系統(tǒng)中FFT

與信道譯碼技術(shù)1.1無線通信的基本數(shù)學(xué)原理1.2FFT在無線通信系統(tǒng)中的應(yīng)用1.3無線通信系統(tǒng)典型的信道編譯碼方法本章小結(jié)

對于無線通信信號，其頻譜分布在中心頻率fc周圍[fc-W/2,fc+W/2]的帶寬為的帶通區(qū)域。但是大多數(shù)的通信信號與信息處理，比如數(shù)據(jù)的編碼與譯碼，信號的調(diào)制與解調(diào)等，都是完全在基帶進行的。在發(fā)送端，最后一步就是將信號上變頻到載頻然后再通過天線傳輸。類似地，接收端在進一步處理之前，第一步就是將射頻信號下變頻到基帶。

1.1無線通信的基本數(shù)學(xué)原理

1.1.1連續(xù)時間基帶模型

考慮實信號s(t)，其傅里葉變換記作S(t)，它帶限于[fc-W/2,fc+W/2]并且W<2fc。定義復(fù)等效基帶信號sb(t)，其傅里葉變換為：

(1.1)

考慮多徑效應(yīng)的無線信道沖激響應(yīng)可以表示為

(1.4)

其中ai(t)和τi(t)分別表示在t時刻從發(fā)送端到接收端的第i條路徑上總的衰減與傳播時延。在時不變模型下，可以忽略(1.4)中的參數(shù)t，得到僅與時延擴展相關(guān)的信道響應(yīng)：

圖1.1從基帶發(fā)送信號xb(t)到基帶接收信號yb(t)的系統(tǒng)框圖

1.1.2離散時間基帶模型

信號采樣是無線通信接收端開展各類數(shù)字信號處理的前置步驟。在前面連續(xù)時間基帶模型基礎(chǔ)上，本節(jié)將考慮采樣對通信信號處理的影響，確定離散時間基帶模型。假設(shè)輸入波形帶限于W，等效基帶信號的帶寬為W/2并可以表示為

(1.9)

圖1.2中給出了完整的離散時間基帶系統(tǒng)框圖。圖1.2從基帶發(fā)送符號x[m]到收信號的基帶采樣y[m]的離散時間基帶系統(tǒng)框圖

1.1.3加性白噪聲

在離散時間基帶模型的基礎(chǔ)上，我們把加性噪聲包含到模型中。我們通常假設(shè)噪聲w(t)是功率譜密度為N0/2的加性高斯白噪聲（AdditiveWhiteGaussianNoise,AWGN），噪聲具有的信號統(tǒng)計特性滿足

?？紤]噪聲后，模型(1.8)修改為

(1.16)

如圖1.3所示，離散時間基帶模型變?yōu)?/p>

(1.17)

圖1.3考慮噪聲的完整離散時間基帶系統(tǒng)框圖

在(1.17)中，是低通噪聲在時刻的采樣值。與信號分量一樣，白噪聲經(jīng)過下變頻、基帶濾波并進行理想采樣，因此可以證明

1.2.1FFT在信號同步中的應(yīng)用

擴頻通信系統(tǒng)的偽碼捕獲是FFT在信號同步領(lǐng)域最典型的應(yīng)用。擴頻通信被認為是衛(wèi)星測控、導(dǎo)航、軍事通信等領(lǐng)域的使能技術(shù)，具有抗干擾能力強、保密性好等諸多優(yōu)勢。偽碼捕獲是擴頻接收機進行信號同步的關(guān)鍵操作，目的在于將接收信號的碼相位差控制在一個碼片之內(nèi)，并信號頻率與本地載波的粗同步。

1.2FFT在無線通信系統(tǒng)中的應(yīng)用

為縮短信號捕獲時間，人們利用信號時域相關(guān)等價于頻域相乘的特性，提出了基于FFT的偽碼頻域并行捕獲方案，并進一步根據(jù)頻移-時移的時頻域?qū)ε夹裕ㄟ^頻域序列的循環(huán)移位，實現(xiàn)對多普勒頻率的并行搜索。在長偽碼碼長或大多普勒頻偏場景下，上述捕獲方法有著廣泛應(yīng)用。圖1.4給出了基于FFT的擴頻接收機的偽碼捕獲流程。

圖1.4擴頻接收機偽碼捕獲流程

其中Y(k)為序列y(n)的N點FFT變換，和S*(k)為s(n)N點DFT變換的共軛。對R(k,fi)進行IFFT，可得r(m,fi)在給定fi下對所有碼相位m的互相關(guān)結(jié)果。具體而言，基于FFT的偽碼捕獲執(zhí)行流程為：

第1步：對接收的復(fù)基帶信號進行N點FFT運算，并設(shè)置p個不同的移位值對計算結(jié)果進行循環(huán)移位，這里每個循環(huán)移位值對應(yīng)于一個多普勒頻率，移位后產(chǎn)生的p個序列全部緩存在存儲器中；

第2步：并行讀取p個序列的數(shù)據(jù)，每個序列分別與本地擴頻碼序列的

點FFT變換結(jié)果共軛相乘，進而進行N點IFFT運算并對結(jié)果取模，這里的N點IFFT結(jié)果對應(yīng)于N個不同碼相位下接收碼序列與本地碼序列的互相關(guān)值，且已經(jīng)覆蓋碼相位的整個搜索范圍；

第3步：比較得到p路IFFT運算結(jié)果的最大模值，并將其與預(yù)設(shè)門限比較，若超過預(yù)設(shè)門限，則最大模值對應(yīng)的碼相位和多普勒頻率即作為偽碼捕獲裝置的最終輸出，否則返回到第1步重新執(zhí)行，并通過調(diào)整循環(huán)移位數(shù)值來搜索新的多普勒頻率范圍。

1.2.2FFT在調(diào)制解調(diào)中的應(yīng)用

利用FFT實現(xiàn)信號調(diào)制解調(diào)是正交頻分復(fù)用（OrthogonalFrequencyDivisionMultiplexing,OFDM）系統(tǒng)最典型的特征。OFDM是多載波調(diào)制技術(shù)的一種，它的基本思想是在頻域內(nèi)將給定信道分成許多正交子信道，在每個子信道上使用一個子載波進行調(diào)制，并且各子載波并行傳輸。雖然無線信道是非平坦的，具有頻率選擇性，但是當子信道數(shù)目很多時，每個子信道則相對平坦，因此在每個子信道上進行的是窄帶傳輸，信號帶寬遠小于信道的相干帶寬，這大大降低了信號波形之間的干擾。

為了說明OFDM利用FFT實現(xiàn)信號調(diào)制與解調(diào)的原理，我們用信號分析中的正交分解理論進行分析。假設(shè)信號集

是某一信號空間的正交基，它們滿足

(1.20)

典型的OFDM系統(tǒng)收發(fā)模型如圖1.5所示。圖1.5典型OFDM系統(tǒng)收發(fā)模型

以O(shè)FDM為基礎(chǔ)，結(jié)合多輸入多輸出（MultipleInputMultipleOutput,MIMO）技術(shù)可以進一步提升系統(tǒng)的頻帶利用率，實現(xiàn)高速率數(shù)據(jù)傳輸。圖1.6給出了空間復(fù)用結(jié)構(gòu)的MIMO-OFDM系統(tǒng)收發(fā)模型，可以看到在發(fā)送端，高速數(shù)據(jù)流經(jīng)過串并轉(zhuǎn)換后變?yōu)槎嗦窋?shù)據(jù)，然后各路數(shù)據(jù)流獨立地生成OFDM信號并通過各自的發(fā)送天線發(fā)送；在接收端，待幀檢測與同步操作完成后，各路接收信號首先利用FFT單元進行解調(diào)；對于得到的頻域數(shù)據(jù)，檢測器執(zhí)行MIMO檢測算法逐個子載波地進行符號檢測，并將結(jié)果傳送至碼信道譯碼模塊完成數(shù)據(jù)糾錯。

圖1.6空間復(fù)用結(jié)構(gòu)MIMO-OFDM系統(tǒng)收發(fā)模型

1.2.3FFT在信道均衡中的應(yīng)用

在無線信道上進行通信信號傳輸時，由于信道多徑效應(yīng)帶來的信號時延擴展，會造成碼間干擾，致使星座圖發(fā)散和接收誤碼率升高。信道均衡旨在克服無線信道給信號帶來的不良影響，通過信道參數(shù)的估計與接收信號的補償，來緩解信號的碼間干擾，保證鏈路通信質(zhì)量。對于單載波頻域均衡系統(tǒng)而言，F(xiàn)FT是信道均衡的關(guān)鍵操作。單載波頻域均衡技術(shù)是IEEE802.16a、IEEE802.15.3以及IEEE802.11ad等主流通信標準規(guī)定的傳輸方案之一，它融合了單載波調(diào)制信號低峰均比優(yōu)勢和OFDM多載波系統(tǒng)低復(fù)雜度信道均衡的特點，在行業(yè)內(nèi)得到了廣泛的應(yīng)用。

在單載波頻域均衡系統(tǒng)中，假設(shè)發(fā)送端發(fā)出的信號為

，其平均功率為1，信道沖激響應(yīng)為

，其中L為FFT窗口的長度，加性高斯白噪聲為w(n)，那么經(jīng)過無線信道的接收信號r(n)可以表示為

(1.28)

與OFDM系統(tǒng)類似，單載波頻域均衡系統(tǒng)會在不同幀的發(fā)送數(shù)據(jù)之前插入具有循環(huán)前綴功能的獨特字（UniqueWord,UW）序列，其作用不僅能夠消除前一幀數(shù)據(jù)對本幀數(shù)據(jù)的干擾，還可以用作信道估計和信號同步。由于UW序列的存在，每個發(fā)送數(shù)據(jù)幀與信道的線性卷積可以等效為循環(huán)卷積，利用循環(huán)卷積的時頻域特性，將(2.5)變換到頻域可以得到

(1.29)

基于上面的數(shù)學(xué)描述，圖1.7給出了典型的單載波頻域均衡系統(tǒng)收發(fā)模型。圖1.7典型單載波頻域均衡系統(tǒng)收發(fā)模型

1.3無線通信系統(tǒng)典型的信道編譯碼方法

信道編碼是為了保證通信系統(tǒng)的傳輸可靠性，克服信道中的噪聲和干擾而專門設(shè)計的一類抗干擾技術(shù)和方法。一般而言，物理層以傳輸信道的方式向上層提供數(shù)據(jù)傳輸?shù)姆?wù)，同時物理層傳輸自身使用的控制信息以支持物理層操作。

本書將重點對turbo碼和卷積碼開展研究，設(shè)計高效的譯碼器VLSI實現(xiàn)方案。如表1.1和表1.2所示，這兩種信道編碼方式承擔了LTE系統(tǒng)的傳輸信道和控制信道的主要數(shù)據(jù)糾錯任務(wù)，其中turbo編碼以其良好的性能，被采用為大部分傳輸信道中數(shù)據(jù)信息的信道編碼方法；卷積碼具有較低的譯碼復(fù)雜度，因此作為廣播信道以及物理層上下行控制信息進行信道編碼的主要方式。在其他非標無線通信設(shè)備中，turbo碼和卷積碼由于具有極高的技術(shù)成熟度，也得到了廣泛的應(yīng)用。

1.3.1卷積碼編碼及譯碼

卷積碼是一種經(jīng)典的信道編碼方案。根據(jù)編碼器中寄存器初始化方式的不同，卷積碼可以分為非咬尾卷積碼和咬尾卷積碼兩類。這里以LTE標準中的卷積碼碼型對編碼過程進行說明。在LTE系統(tǒng)中，控制信道的編碼由卷積編碼來完成。LTE控制信道的傳輸塊經(jīng)過CRC校驗后，直接進入卷積編碼器，采用的卷積編碼器是約束長度為7、母碼碼率為

的截尾卷積編碼器，分量碼采用的編碼多項式為G0=133，G1=171，G2=165，編碼器結(jié)構(gòu)如圖1.8所示。

圖1.8編碼速率為1/3的卷積碼編碼器

圖1.9描述了采用列表譯碼方案的通信系統(tǒng)收發(fā)端原理框圖。圖1.9采用卷積碼編碼與列表譯碼方案的通信系統(tǒng)收發(fā)端框圖

1.3.2Turbo碼編碼及譯碼

Turbo碼以其優(yōu)異的糾錯性能而被主流通信標準采納為長碼編碼方案。如圖1.10所示，發(fā)送端的turbo碼編碼器可以看作是由兩個相同子編碼器構(gòu)成的并行級聯(lián)卷積碼編碼系統(tǒng)。相應(yīng)地在接收端，turbo碼譯碼器配置有兩個軟輸入軟輸出（SoftInputSoftOutput，SISO）最大后驗概率（MaximumAPosteriori，MAP）分量譯碼單元，并采用迭代方式進行譯碼。

圖1.10采用turbo碼編譯碼方案的通信系統(tǒng)收發(fā)端框圖

圖1.11給出了LTE系統(tǒng)的turbo編碼框圖。圖1.11LTE系統(tǒng)turbo編碼框圖

具體地，LTE標準采用的8狀態(tài)分量編碼器的傳輸函數(shù)為

其中

分別為正向多項式和反饋多項式。在編碼開始前，所有的以為繼續(xù)存器初始狀態(tài)全部設(shè)為‘0’，令K表示要進行編碼的比特數(shù)目，輸出的規(guī)則如下：

尾比特的生成過程如下：

STEP1：第二個子編碼器禁用，第一個子編碼器中的開關(guān)打到低端和虛線相連，在編碼器的輸入端依次3個比特，這時按照編碼器中的反饋及相關(guān)的運算可以依次得到6比特的輸出；

STEP2：第一個子編碼器禁用，第二個子編碼器中的開關(guān)打到低端和虛線相連，在編碼器的輸入端依次3個比特，這時按照編碼器中的反饋及相關(guān)的運算可以依次得到6比特的輸出

STEP3：將得到的12個比特的輸出按照下面給定的順序排列，獲得最終的尾比特輸出。

從上面的討論可以看出，turbo編碼的編碼速率為

，同時受到尾比特的影響，每個分量碼的長度為

。

在接收端，從典型的MAP譯碼算法出發(fā)，研究者們提出的log-MAP算法將MAP算法映射到對數(shù)域內(nèi)以降低運算復(fù)雜度，同時這一變換使譯碼操作能夠在卷積碼網(wǎng)格中以逐級遞推的方式執(zhí)行；進一步忽略log-MAP算法中的非線性修正項，可以得到復(fù)雜度更低的max-log-MAP算法。盡管max-log-MAP算法的近似帶來了一定的糾錯性能損失，卻極大地簡化了譯碼過程中的算術(shù)運算操作，因而在turbo碼的硬件實現(xiàn)中扮演著重要角色。

隨著無線通信系統(tǒng)所承載的信息傳輸速率的不斷提升，turbo碼譯碼器的吞吐量也從初期的幾兆至數(shù)十兆比特每秒逐步增加至目前的成百上千兆比特每秒。為了突破迭代譯碼對turbo碼譯碼器吞吐量的限制，在譯碼算法層面，基于多進制符號的radix-MAP算法及其簡化方案開始得到廣泛應(yīng)用，該方案相比基于二進制比特的傳統(tǒng)譯碼方法，可以使吞吐量獲得

倍的提升。在譯碼器結(jié)構(gòu)層面，子塊并行譯碼方法已成為高吞吐量turbo碼譯碼器設(shè)計的主流解決方案，它將接收的turbo碼碼塊劃分為

個子塊并對每個子塊配置獨立的運算單元進行譯碼操作，這樣可以使譯碼器的吞吐量近似提升

倍。

在保證吞吐量性能的前提下，為了降低的turbo譯碼器的硬件復(fù)雜度，滑動窗MAP（Sliding-windowMAP，SMAP）算法得到了設(shè)計者們的重視，盡管該方案會損失部分糾錯性能，卻可以顯著降低譯碼器的數(shù)據(jù)存儲開銷。在此基礎(chǔ)上，人們從窗口長度以及窗口邊界狀態(tài)初始化策略等方面對SMAP方案進行改進，以實現(xiàn)糾錯性能與硬件復(fù)雜度的合理折衷。除SMAP算法及其改進方案外，交叉MAP（CrossMAP，XMAP）算法也被證明在降低存儲單元消耗和譯碼器功耗方面具有突出表現(xiàn)，并被應(yīng)用于高吞吐量turbo碼譯碼器實現(xiàn)。

本章小結(jié)

從早期的電報傳信到現(xiàn)在的萬物互聯(lián)，無線通信技術(shù)的每一次發(fā)展都給人類的生產(chǎn)生活帶來深刻的變革。目前，無線通信技術(shù)正在向更高速、更快速、更綠色三個維度不斷演進。更高速是指無線通信的傳輸速率更高，承載信息能力更強；更快速是指無線通信系統(tǒng)的延遲更低，信息交互實時性更強；更綠色是指無線通信設(shè)備更加低功耗、高能效。在新的通信技術(shù)誕生之前，實現(xiàn)上述演進更多地需要依靠底層硬件的不斷優(yōu)化，為各類算法提供高效的VLSI解決方案。

本章首先介紹了無線通信的基本數(shù)學(xué)原理，對基于離散時間信號的基帶信號處理進行了系統(tǒng)性的數(shù)學(xué)描述。接著結(jié)合具體的通信系統(tǒng)，介紹了FFT、卷積碼與turbo碼在實際通信系統(tǒng)中的應(yīng)用方式。在后續(xù)的章節(jié)中，我們將詳細討論FFT與信道譯碼的VLSI實現(xiàn)方案。第2章基于并行流水線的FFT計算方法及VLSI結(jié)構(gòu)2.1面向硬件實現(xiàn)的radix-2k

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

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

對于輸入序列xn

，其

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

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

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

利用混合基算法可以將

進一步分解為：

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

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

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

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

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

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

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

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

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

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

移位寄存器與蝶形運算單元之間存在數(shù)據(jù)反饋，即移位寄存器的輸出數(shù)據(jù)作為蝶形運算單元的輸入，并且蝶形運算單元的輸出數(shù)據(jù)作為因為寄存器的輸入。

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

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

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

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

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

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

；

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

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

在MDC結(jié)構(gòu)中，蝶形運算單元僅需對輸入并行數(shù)據(jù)進行求和與相減運算，然后并行輸出計算結(jié)果即可，對數(shù)據(jù)流的調(diào)整通過蝶形運算單元輸入端的延遲換向器來實現(xiàn)。具體而言，第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ù)送至下一級蝶形運算單元；

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

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

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

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

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

圖2.5以M=16為例給出了倒位序排序的數(shù)據(jù)壽命分析圖，其中左側(cè)是時鐘周期標號；數(shù)據(jù)的壽命周期在圖中用粗實線表示，它起始于數(shù)據(jù)產(chǎn)生或者輸入的時刻，到數(shù)據(jù)執(zhí)行完全部相關(guān)運算或輸出時刻結(jié)束；特別地當數(shù)據(jù)產(chǎn)生和終止于同一時刻時，數(shù)據(jù)的壽命周期為0，在圖中標記為“”；圖右側(cè)統(tǒng)計了在同一時刻的有效數(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點FFT計算為例）

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

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

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

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

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

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

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

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

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

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

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

在上述方案中，參數(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并行流水線計算方法

一般地，N=2u點的FFT和IFFT運算可以分別定義為下面的形式：

圖2.12FFT并行計算的頂層結(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)計算調(diào)度優(yōu)化

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

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

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

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

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

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

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

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

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

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

2.5理論分析與硬件測試

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

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

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

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

和

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

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

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

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

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

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

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

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

最后對表2.3中FFT計算模塊的時延和吞吐量性能進行討論。由于FPGA內(nèi)的復(fù)數(shù)乘法器在進行數(shù)據(jù)旋轉(zhuǎn)時存在若干個時鐘周期的計算延遲，且流水線結(jié)構(gòu)在實現(xiàn)過程中要用寄存器隔離不同操作以縮短電路的關(guān)鍵路徑，這些因素使得FFT模塊實測的計算時延略高于表2.2中的理論值。另一方面，并行流水線結(jié)構(gòu)的可達吞吐量可以用并行度與最大時鐘頻率的乘積來確定，三種設(shè)計方案在這一指標上具有相近的表現(xiàn)。

本章小結(jié)

并行流水線結(jié)構(gòu)是實現(xiàn)高吞吐量FFT計算模塊的主要方式。作為具有代表性的并行流水線FFT計算方案，MDF和MDC結(jié)構(gòu)在實際系統(tǒng)中得到了廣泛應(yīng)用，然而這些設(shè)計并未實現(xiàn)對硬件資源的最優(yōu)化利用。具體來講，由串行流水線結(jié)構(gòu)衍生而來的MDF結(jié)構(gòu)對計算資源的使用效率不高，而MDC結(jié)構(gòu)需要配置大量的存儲器來完成復(fù)雜的數(shù)據(jù)排序工作。

為了解決這些問題，本章首先回顧了面向硬件實現(xiàn)的radix-2kFFT算法，以及基于串行流水線結(jié)構(gòu)的FFT硬件實現(xiàn)結(jié)構(gòu)，同時拓展研究了倒位序排序的最小存儲資源需求并給出了相應(yīng)的硬件設(shè)計方案，此外還提出了新的旋轉(zhuǎn)因子壓縮存儲策略來降低其存儲資源開銷。在這些工作的基礎(chǔ)上，推導(dǎo)了FFT并行計算結(jié)構(gòu)的頂層設(shè)計方案；遵循該方案并利用折疊變換的基本原理，設(shè)計了新的并行流水線FFT計算結(jié)構(gòu)，即M2DF結(jié)構(gòu)。理論分析和基于FPGA硬件測試結(jié)果表明，M2DF結(jié)構(gòu)作為對現(xiàn)有設(shè)計方案的有效補充，它能夠比MDC結(jié)構(gòu)消耗更少的存儲資源并具有更短的計算時延，同時在對計算資源的使用效率方面也比MDF結(jié)構(gòu)有了顯著提升。第3章基于單端口存儲器的FFT處理器及VLSI結(jié)構(gòu)3.1FFT處理器頂層架構(gòu)設(shè)計3.2FFT處理器數(shù)據(jù)訪問方案設(shè)計3.3FFT處理器VLSI結(jié)構(gòu)設(shè)計3.4理論分析與硬件測試本章小結(jié)

3.1FFT處理器頂層架構(gòu)設(shè)計

一般地，radix-2kFFT算法通過

級的radix-2k蝶形計算來完成N=2n點的FFT運算，其中

表示向上取整運算符。各級采用的蝶形運算階數(shù)

分別為：

(3.1)

為便于討論，這里還定義k0=0。令表

示數(shù)據(jù)索引，相應(yīng)地在radix-2k信號流圖中，F(xiàn)FT輸入數(shù)據(jù)、計算結(jié)果以及每一級的操作數(shù)均按從上至下的方式利用數(shù)據(jù)索引依次編號。第m級運算的操作數(shù)構(gòu)成了

個radix-蝶形，第t+1個蝶形（

）包含的數(shù)據(jù)索引構(gòu)成向量

(3.2)

其中

，

表示為

同時，公式(3.2)中的數(shù)組Im定義為：

其中

表示在

范圍內(nèi)以

為增量的整數(shù)序列。

Radix-2k蝶形運算的實現(xiàn)方式有多種，除了直接根據(jù)信號流圖布設(shè)加法器、乘法器并進行電路互聯(lián)外，還可以基于多路延遲換向（multipathdelaycommutator,MDC）結(jié)構(gòu)來實現(xiàn)，此時每個MDC結(jié)構(gòu)獨立執(zhí)行radix-2k蝶形運算。MDC結(jié)構(gòu)的輸入與輸出數(shù)據(jù)均為2路并行方式，當計算與bm.t相關(guān)的蝶形時，MDC結(jié)構(gòu)輸入數(shù)據(jù)對應(yīng)的數(shù)據(jù)索引為

(3.4)

其中

利用向量x的元素依次填充u×v維矩陣的每一列，產(chǎn)生一個u×v維的矩陣。

的第一行和第二行分別描述了MDC結(jié)構(gòu)上支路和下支路的輸入數(shù)據(jù)順序。MDC結(jié)構(gòu)輸出數(shù)據(jù)對應(yīng)的數(shù)據(jù)索引為：

(3.5)

類似地，

的第一行和第二行表示上支路和下支路的輸出數(shù)據(jù)次序。

基于存儲器的radix-2kFFT處理器頂層設(shè)計方案如圖3.1所示，主要由處理單元、數(shù)據(jù)訪問單元、數(shù)據(jù)緩存單元、數(shù)據(jù)次序變換單元以及輸入輸出轉(zhuǎn)換單元五部分構(gòu)成，其中數(shù)據(jù)訪問單元和數(shù)據(jù)次序變換單元作為橋梁控制數(shù)據(jù)讀寫，用于連通FFT處理器的處理單元與數(shù)據(jù)緩存單元。

圖3.1基于存儲器的radix-2kFFT處理器頂層架構(gòu)

圖3.2以

為例給出了處理單元的底層詳細硬件結(jié)構(gòu)，除了執(zhí)行蝶形運算的MDC結(jié)構(gòu)外，在處理單元數(shù)據(jù)輸出側(cè)還排列了一組復(fù)數(shù)乘法器，用于對蝶形運算結(jié)果進行旋轉(zhuǎn)因子加權(quán)。

圖3.2基于MDC計算電路的處理單元結(jié)構(gòu)

FFT處理器的數(shù)據(jù)調(diào)度流程如圖3.3所示。圖3.3FFT處理器數(shù)據(jù)調(diào)度流程

3.2FFT處理器數(shù)據(jù)訪問方案設(shè)計

與CPU中算術(shù)邏輯單元與數(shù)據(jù)緩存的關(guān)系類似，在基于存儲器的FFT處理器中，對處理單元于數(shù)據(jù)緩存單元之間的數(shù)據(jù)存取操作進行沖突消解，是保證FFT處理器高吞吐量運行的關(guān)鍵。圖3.4以并行度為4的32點radix-22FFT計算為例，展示了不同數(shù)據(jù)訪問方案下的計算流程，其中灰色格點表示數(shù)據(jù)訪問存在沖突。

圖3.4并行度為4的32點radix-22FFT在不同數(shù)據(jù)訪問方案下的計算流程

3.2.1輸入數(shù)據(jù)緩存方案

輸入數(shù)據(jù)首先通過輸入輸出轉(zhuǎn)換單元將q路并行轉(zhuǎn)換為pc路并行，然后以pc路并行的方式寫入數(shù)據(jù)緩存單元，其數(shù)據(jù)次序可以表示為

(3.6)

3.2.2中間計算結(jié)果存取方案

對于第m級（

）的蝶形運算，處理單元每次會從數(shù)據(jù)緩存單元讀取pc個數(shù)據(jù)，這些數(shù)據(jù)分屬于pc/2個radix-蝶形，并依托處理單元內(nèi)的pc/2個MDC運算結(jié)構(gòu)分別進行處理。用

分別表示同時處理的pc/2個radix-蝶形對應(yīng)的數(shù)據(jù)索引向量，其中t屬于數(shù)組

(3.9)

公式(3.7)既描述了輸入數(shù)據(jù)的緩存方法，同時也是FFT第1級操作數(shù)的緩存方法。對于第m級（

）的蝶形計算，其操作數(shù)緩存方式為

(3.15)

值得注意的是，這里第2級至第M-1級蝶形運算操作數(shù)的緩存方式，實際也是第1級至第M-2級蝶形運算計算結(jié)果的緩存方式。

基于(3.15)的數(shù)據(jù)存儲方式，可以滿足第1級至第M-2級計算過程中的數(shù)據(jù)無沖突訪問，具體總結(jié)如下：

定理3.1：若第m級（

）的數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么

1）第1級的數(shù)據(jù)無沖突訪問要求數(shù)據(jù)讀取基于(3.7)執(zhí)行，蝶形運算結(jié)果寫入基于m=2情況下的(3.15)執(zhí)行；

2）第u級（

）的無沖突數(shù)據(jù)訪問要求數(shù)據(jù)讀取基于m=u情況下的(3.15)執(zhí)行，蝶形運算結(jié)果寫入基于m=u+1情況下的(3.15)執(zhí)行，并且數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個時鐘周期。

與前M-1級不同，第M-1級蝶形運算結(jié)果按照如下方式存儲在數(shù)據(jù)緩存單元中：

定理3.2：若第M-1級數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么其無沖突數(shù)據(jù)訪問要求數(shù)據(jù)讀取基于m=M-1情況下的(3.15)執(zhí)行，數(shù)據(jù)寫入基于(3.16)執(zhí)行，并且數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個時鐘周期。

定理3.3：若第M級數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么其無沖突數(shù)據(jù)訪問要求數(shù)據(jù)讀取基于(3.16)執(zhí)行，數(shù)據(jù)寫入基于(3.23)執(zhí)行，并且對于前N/2個數(shù)據(jù)，數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個時鐘周期，對于后N/2個數(shù)據(jù)，數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為2k+1個時鐘周期。

因此的具體表達式為

進而基于(3.23)，可以確定數(shù)據(jù)緩存單元寫入?yún)?shù)的表達式為

3.2.3輸出數(shù)據(jù)讀取方案

用

來表示以pc路并行的方式來從數(shù)據(jù)緩存單元中讀取計算結(jié)果的數(shù)據(jù)次序，其形式與(3.6)中

的形式相同。通過輸入輸出轉(zhuǎn)換單元的數(shù)據(jù)速率變換，F(xiàn)FT計算結(jié)果的輸出并行度變?yōu)閝，與輸入數(shù)據(jù)的并行度保持一致。由于處理單元輸出的計算結(jié)果以倒位序方式排序，并且基于映射規(guī)則(3.23)存儲在數(shù)據(jù)緩存單元中，通過將(3.23)中的數(shù)據(jù)索引d替換為

，并利用

，從數(shù)據(jù)緩存單元中讀取自然序排列的FFT計算結(jié)果，應(yīng)當遵循的映射規(guī)則為

此外，這里所設(shè)計的映射規(guī)則能夠允許FFT計算結(jié)果讀取與新數(shù)據(jù)寫入在數(shù)據(jù)緩存單元內(nèi)并發(fā)執(zhí)行，這使得FFT處理器不必為輸入數(shù)據(jù)和待輸出數(shù)據(jù)配置獨立的存儲資源，將輸入緩沖區(qū)與輸出緩沖區(qū)混合，從而顯著降低無沖突數(shù)據(jù)存取所對應(yīng)的存儲開銷。具體而言，當數(shù)據(jù)緩存單元中的兩塊RAM在數(shù)據(jù)讀取模式下輸出FFT計算結(jié)果時，另外兩塊RAM可以工作在輸入寫入模式下，利用已經(jīng)釋放的RAM存儲空間來接收新數(shù)據(jù)。FFT計算結(jié)果讀取與新數(shù)據(jù)寫入的并發(fā)操作需要輸入數(shù)據(jù)在緩存時使用與FFT計算結(jié)果讀取相同的映射規(guī)則。

通過比較(3.8)和(3.25)，這兩個映射規(guī)則以相同的方式生成i和j，而物理地址a的生成僅在N=22k或N=22k-1時相同。而當N>22k時，通過移除(3.25)中的

操作，物理地址a可以轉(zhuǎn)換為

舉例：假設(shè)FFT處理器采用radix-22算法執(zhí)行4路并行的64點FFT運算，即N=64

，Pc=4

。整個計算分為三級，算法階數(shù)設(shè)置為

。圖3.5詳細描述了FFT并行計算過程中輸入數(shù)據(jù)次序、處理單元輸入與輸出數(shù)據(jù)流的數(shù)據(jù)次序，以及數(shù)據(jù)緩存單元的4塊單端口RAM內(nèi)數(shù)據(jù)的排列方式，。通過圖3.5可以直觀反映出(3.9)、(3.18)規(guī)定的蝶形處理次序，以及(3.17)和(3.22)中的數(shù)據(jù)重排操作給數(shù)據(jù)次序帶來的影響。

圖3.5FFT處理器無沖突數(shù)據(jù)訪問流程示意圖（以64點的4路并行FFT計算為例）

3.3FFT處理器VLSI結(jié)構(gòu)設(shè)計

以上三種運算覆蓋了數(shù)據(jù)映射規(guī)則中的基本運算類型，這表明數(shù)據(jù)訪問參數(shù)i，j和a的可以通過數(shù)據(jù)位的調(diào)整來生成。為了說明這一點，我們首先對前M-2級計算中的數(shù)據(jù)訪問次序進行討論。如圖3.6所示。

圖3.6通過對計數(shù)器劃分的數(shù)據(jù)段重排來產(chǎn)生前M-2級數(shù)據(jù)訪問索引

對于第M-1級計算，包含log2N比特的二進制計數(shù)器被劃分為5段，從最高位開始數(shù)據(jù)段長度分別為

比特、1比特、

比特、1比特和k-1比特，如圖3.7所示。注意當M=2時需要略去第一個數(shù)據(jù)段，因為此時其長度為

。依據(jù)定理3.2的推導(dǎo)結(jié)果，可通過對劃分后數(shù)據(jù)段進行次序調(diào)整來產(chǎn)生

對應(yīng)的數(shù)據(jù)索引。

圖3.7通過對計數(shù)器劃分的數(shù)據(jù)段重排來產(chǎn)生第

級數(shù)據(jù)訪問索引

對于第M級FFT計算，計數(shù)器被劃分為6個數(shù)據(jù)段，從最高位開始數(shù)據(jù)段長度分別為1比特、

比特、1比特、k-1比特、1比特和k-1比特，其中包含單一比特位的第1段和第3段通過異或運算進一步產(chǎn)生新的輔助數(shù)據(jù)段。依據(jù)定理3.3的推導(dǎo)結(jié)果，通過對計數(shù)器中的6個數(shù)據(jù)段以及輔助數(shù)據(jù)段進行重新排列，可以產(chǎn)生數(shù)據(jù)索引

，如圖3.8所示。

圖3.8通過對計數(shù)器劃分的數(shù)據(jù)段重排來產(chǎn)生第M級數(shù)據(jù)訪問索引

圖3.8通過對計數(shù)器劃分的數(shù)據(jù)段重排來產(chǎn)生第M級數(shù)據(jù)訪問索引

通過數(shù)據(jù)段調(diào)整來得到數(shù)據(jù)索引后，可以根據(jù)映射規(guī)則確定數(shù)據(jù)訪問所需的RAM標識符

與物理地址

。如圖3.9所示，數(shù)據(jù)訪問參數(shù)的生成只涉及到數(shù)據(jù)截位和邏輯異或操作。

圖3.9基于給定的數(shù)據(jù)訪問索引產(chǎn)生數(shù)據(jù)訪問參數(shù)的方式

圖3.9基于給定的數(shù)據(jù)訪問索引產(chǎn)生數(shù)據(jù)訪問參數(shù)的方式

3.3.2輸入輸出轉(zhuǎn)換單元及數(shù)據(jù)次序變換單元

輸入輸出轉(zhuǎn)換單元的VLSI實現(xiàn)結(jié)構(gòu)如圖3.10所示，其作用是完成

路并行輸入/輸出數(shù)據(jù)與pc路數(shù)據(jù)緩存單元并行讀寫數(shù)據(jù)之間的并行度轉(zhuǎn)換。

圖3.10輸入輸出轉(zhuǎn)換單元VLSI實現(xiàn)結(jié)構(gòu)

數(shù)據(jù)次序變換單元用于對處理單元輸入數(shù)據(jù)次序進行調(diào)節(jié)，并對處理單元輸出數(shù)據(jù)進行重新排序，以保證在第M-1級和第M級計算過程中能夠?qū)?shù)據(jù)緩存單元進行無沖突訪問。數(shù)據(jù)次序變換單元的硬件結(jié)構(gòu)如圖3.11所示，包括數(shù)據(jù)轉(zhuǎn)置模塊和延遲換向模塊兩個部分。

圖3.11數(shù)據(jù)次序變換單元VLSI實現(xiàn)結(jié)構(gòu)

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

從圖3.1的頂層設(shè)計方案可以看出，處理單元在MDC計算結(jié)構(gòu)輸出端部署復(fù)數(shù)乘法器，用于對計算結(jié)果進行旋轉(zhuǎn)因子加權(quán)。旋轉(zhuǎn)因子加權(quán)不改變數(shù)據(jù)索引，即加權(quán)前后的數(shù)據(jù)對應(yīng)的數(shù)據(jù)索引相同。對于第m級運算，用

表示處理單元某個輸出數(shù)據(jù)的數(shù)據(jù)索引，那么用于對該數(shù)據(jù)進行加權(quán)的旋轉(zhuǎn)因子表示為：

由于處理單元在執(zhí)行第M級運算時，MDC計算結(jié)構(gòu)的輸出不必乘以旋轉(zhuǎn)因子，我們重點考慮前M-1級運算過程中的旋轉(zhuǎn)因子的快速生成。具體而言，在第m級（

）可將(3.26)中的數(shù)據(jù)索引d例化為

。參照圖3.6和圖3.7中基于數(shù)據(jù)段分割與重排方法生成的

格式，可以快速生成(3.26)中旋轉(zhuǎn)因子復(fù)指數(shù)項的分子部分作為旋轉(zhuǎn)因子的訪問索引，如圖3.12所示。

圖3.12旋轉(zhuǎn)因子訪問索引生成方式（以第1至第M-1級計算涉及的旋轉(zhuǎn)因子為例）

3.4理論分析與硬件測試

3.4.1FFT處理器性能及資源消耗估計與比較

表3.1總結(jié)了所設(shè)計的FFT處理器在FFT計算長度為N=2n、數(shù)據(jù)輸入與計算結(jié)果輸出并行度為q、計算并行度為pc=2k情況下的硬件開銷，并同時評估了計算延遲與吞吐量。

在處理性能上，F(xiàn)FT處理器的計算延遲被定義為處理器接收第一個有效輸入數(shù)據(jù)到提供第一個有效輸出數(shù)據(jù)之間的時間間隔，其數(shù)值為

根據(jù)圖3.3(a)給出的數(shù)據(jù)調(diào)度流程，當FFT處理器部署一個數(shù)據(jù)緩存單元時，以時鐘速率為單位的吞吐量可表示為

這里假設(shè)FFT在開始輸出計算結(jié)果的同時立刻接收新的數(shù)據(jù)。當FFT處理器部署兩個數(shù)據(jù)緩存單元時，處理單元在執(zhí)行FFT運算時即可接收新的數(shù)據(jù)，此時吞吐量進一步提升至

表3.2將所設(shè)計的FFT處理器與現(xiàn)有設(shè)計方案進行了比較。在計算并行度為2的冪次的各類FFT處理器中，所提方案支持的計算并行度高于一般基于單端口RAM的FFT處理器，與基于雙端口RAM的FFT處理器性能保持一致。

3.4.2FFT處理器硬件實現(xiàn)與測試

我們首先利用速度等級為-3的XilinxFPGA對FFT處理器進行原型測試。這里FPGA型號為Kintex7XC7K325T，所采用的編譯器為Vivado2015.2，在該測試中文獻[22]和[24]的FFT處理器VLSI實現(xiàn)結(jié)構(gòu)作為對比方案。與本章基于MDC計算結(jié)構(gòu)搭建的處理單元不同，對比方案直接基于radix-r（

r=pc）信號流圖結(jié)構(gòu)來實現(xiàn)并行度為pc的處理單元。三種用于測試的FFT處理器的數(shù)據(jù)緩存開銷均為N個復(fù)數(shù)存儲單元，但對應(yīng)的RAM模塊數(shù)量和存儲深度各不相同。FFT處理器中的通用復(fù)數(shù)乘法器和常數(shù)復(fù)數(shù)乘法器均基于FPGA內(nèi)的DSP48E乘法單元實現(xiàn)，其中每個復(fù)數(shù)乘法器消耗3個DSP48E乘法單元。

此外，盡管兩個對比方案是面向的是數(shù)據(jù)串行輸入與計算結(jié)果串行輸出的場景，而文獻[24]中的FFT處理器內(nèi)支持輸入/輸出并行度擴展到pc，同時文獻[24]中的FFT處理器也可以支持2路并行的數(shù)據(jù)輸入與輸出，這些因素在評估FFT處理器吞吐量時會被一并考慮。不同F(xiàn)FT處理器占用的FPGAslice數(shù)量與可以達到的數(shù)據(jù)吞吐量如圖3.13所示。表3.3以N=16384，pc=16,為例對FFT處理器再FPGA上的實現(xiàn)情況進行了詳細的統(tǒng)計。

圖3.13不同F(xiàn)FT處理器占用的FPGAslice數(shù)量與可以達到的數(shù)據(jù)吞吐量關(guān)系圖

根據(jù)FPGA測試結(jié)果，F(xiàn)FT處理器所占用的slice資源主要用于實現(xiàn)處理單元和數(shù)據(jù)無沖突訪問電路結(jié)構(gòu)，并且從圖3.13可以看出，F(xiàn)FT處理器對slice的消耗與計算并行度pc成正比。

所設(shè)計的FFT處理器基于SMIC-40nmCMOS工藝進行了ASIC實現(xiàn)，所用的邏輯綜合工具為SynopsysDesignComplier，布局布線通過CadenceInnovus完成。FFT處理器的計算并行度pc=16，計算長度在可在2048點至16384點之間變化，其數(shù)字后端版圖如圖3.14所示，所占用的硅片面積為2.358mm2，在150MHz的工作時鐘頻率下功耗為38.76mW。

表3.4對比了不同F(xiàn)FT處理器的AISC實現(xiàn)結(jié)果，為了更為直觀地比較不同設(shè)計方案，我們引入FFT單點歸一化面積和單點歸一化能量來評價硬件效率：

本章小結(jié)

基于存儲器的FFT處理器是對流水線FFT計算結(jié)構(gòu)的有益補充，其中單端口RAM由于占用的電路面積更小，在FFT處理器設(shè)計與實現(xiàn)中日益得到關(guān)注。目前，設(shè)計基于單端口RAM的高并行度FFT處理器，以較低的硬件開銷實現(xiàn)高吞吐量的FFT計算已經(jīng)成為FFT硬件結(jié)構(gòu)研究領(lǐng)域的又一熱點。以radix-2kFFT算法為基礎(chǔ)，本章首先介紹了一種基于單端口存儲器的FFT并行計算方法，并且給出了FFT處理器頂層架構(gòu)。

進而對FFT處理器內(nèi)的無沖突數(shù)據(jù)并行訪問方案進行了設(shè)計，并對有效性給出了嚴格的數(shù)學(xué)證明。遵循上述頂層架構(gòu)和數(shù)據(jù)無沖突訪問方案，進一步設(shè)計了FFT處理器的VLSI實現(xiàn)結(jié)構(gòu)，完成了FPGA原型驗證與ASIC實現(xiàn)評估。概括起來，所設(shè)計的FFT處理器具有以下三個技術(shù)特點：

一是單端口RAM的數(shù)量固定為4個，不受計算并行度的影響；

二是無沖突數(shù)據(jù)訪問控制簡單，不因計算并行度的增加而更為復(fù)雜；

三是支持數(shù)據(jù)并行輸入和計算結(jié)果的并行輸出，輸入與輸出并行度可以與FFT處理器計算并行度保持一致。和現(xiàn)有的各類FFT處理器相比，理論分析和實驗結(jié)果均印證了本章設(shè)計方案在面積，容量，功耗等方面的優(yōu)越性，能夠滿足LTE移動終端、頻譜感知接收機等低功耗、高集成設(shè)備對FFT計算的能力要求。第4章Radix-2kFFT量化誤差分析與VLSI結(jié)構(gòu)優(yōu)化4.1基于矩陣變換的混合radix-2kFFT算法分析4.2混合radix-2k算法量化誤差分析4.3流水線FFT結(jié)構(gòu)硬件參數(shù)的優(yōu)化配置4.4仿真分析與實驗測試本章小結(jié)

Radix-2k算法是FFT硬件設(shè)計中廣泛應(yīng)用的一類計算方案。與經(jīng)典的radix-2k算法或混合基算法相比，利用radix-2k算法來設(shè)計FFT硬件結(jié)構(gòu)，其優(yōu)勢有兩點：一是radix-2k算法的蝶形運算以最簡單的radix-2運算方式進行，降低了蝶形運算單元的VLSI設(shè)計難度和控制復(fù)雜度；二是radix-2k算法可以將非平凡旋轉(zhuǎn)因子的數(shù)據(jù)加權(quán)在信號流圖中進行集中，這樣在流水線實現(xiàn)方式下，無需為每一級蝶形運算單元都配置復(fù)數(shù)乘法器，從而有助于降低FFT計算單元的硬件資源開銷。

4.1基于矩陣變換的混合radix-2kFFT算法分析

一般地，N點DFT運算可以表示為(4.1)

4.1.1混合radix-2k算法的矩陣變換表示

在(4.2)中，

是一個用于完成

點倒位序次序變換的置換矩陣。為了給出

的具體表達式，首先定義S階的跨步置換矩陣GS，將該矩陣作用于S維向量

可以得到

這樣一來

可以分解為一組跨步置換矩陣連乘的形式，即

(4.3)

另一方面，(3-2)中的M個連乘項對應(yīng)于級聯(lián)的M個運算單元，這里

描述了執(zhí)行radix-2k算法的運算單元所涉及的全部操作，其中參數(shù)cm表示前m個計算單元的算法階數(shù)累積量，即

(4.4)

顯然m=M將使得

。對于給定的cm，

對應(yīng)的算術(shù)運算操作由km決定。

（1）當km為奇數(shù)且km>1時

，

可以表示為

其中N階蝶形運算矩陣BF(u)具有如下形式：

4.1.2混合radix-

2k算法分量矩陣的數(shù)學(xué)性質(zhì)

在(4.15)中，混合radix-2k算法使得DFT變換矩陣TN能夠用數(shù)據(jù)排序矩陣

、蝶形運算矩陣BF(u)以及數(shù)據(jù)加權(quán)矩陣M1(u)，M2(u,v)，M3(u,v)等分量矩陣進行表示。不難驗證TN滿足

是酉矩陣。實際上，(4.15)中的各分量矩陣都具有類似的性質(zhì)。證明這一點需要用到跨步置換矩陣的一些數(shù)學(xué)特性，因此我們首先給出如下的引理：

引理4.1：如果矩陣GS是跨步置換矩陣，那么GS可逆且其逆矩陣GS-1滿足

。

另一方面，矩陣的Kronecker積具有如下性質(zhì)：

4.2混合radix-2k算法量化誤差分析

4.2.1可變數(shù)據(jù)位寬下的量化誤差模型

在(4.15)中，DFT變換矩陣TN按照混合radix-2k算法進行分解后得到了L個蝶形運算矩陣

。對于實際的流水線FFT計算結(jié)構(gòu)，BF(l)中涉及的radix-2蝶形運算和數(shù)據(jù)原位存儲操作將通過流水線第l=1級的蝶形運算單元實現(xiàn)。

由于BF(l)不受參數(shù)

的影響，因而蝶形運算單元在定點計算中引入的量化誤差將只由數(shù)據(jù)位寬決定。令wini和wfin分別表示FFT輸入數(shù)據(jù)和計算結(jié)果實部與虛部的數(shù)據(jù)位寬，同時定義數(shù)據(jù)位寬向量

，其中wl對應(yīng)于流水線第l=1級的蝶形運算單元和旋轉(zhuǎn)因子加權(quán)單元在計算過程中所采用的數(shù)據(jù)位寬。在滿足

的前提下，數(shù)據(jù)位寬向量w可以進行任意設(shè)置，而數(shù)據(jù)位寬非遞減的約束旨在減小由數(shù)據(jù)截位所引入的量化誤差。

在數(shù)據(jù)位寬固定的流水線結(jié)構(gòu)中，參與radix-2蝶形運算的兩個數(shù)據(jù)在計算前通常要進行縮放：數(shù)據(jù)的實部和虛部分別右移一位并根據(jù)數(shù)據(jù)最低位的取值對移位運算結(jié)果進行舍入，該操作在避免蝶形運算發(fā)生溢出的同時也引入了量化誤差。而當流水線結(jié)構(gòu)中的數(shù)據(jù)位寬可變時，在某一級增加數(shù)據(jù)位寬將使得后續(xù)的部分蝶形運算單元在不縮放輸入數(shù)據(jù)的條件下也能夠避免計算溢出。

圖4.2radix-2km計算單元內(nèi)的量化誤差傳播模型

4.2.2量化誤差的功率估計

我們首先考慮(4.19)中舍入誤差向量

，其元素對應(yīng)于輸入數(shù)據(jù)

在縮放過程中引入的誤差。一般地，

包含的N個元素被認為是一組獨立同分布的隨機變量。在統(tǒng)計意義上，

中每一個元素的實部與虛部為非負數(shù)和負數(shù)的概率均為1/2，同時數(shù)據(jù)的最低位以相同概率取0和1，這保證了

中各元素的均值為0。進一步假設(shè)

中各元素的方差為

，我們可以得到

對應(yīng)的功率為

對于(4.19)中的誤差分量

，其元素對應(yīng)于輸入數(shù)據(jù)

在數(shù)據(jù)旋轉(zhuǎn)操作中所引入的誤差。和舍入誤差

不同的是，

中的元素并非都是誤差源，這是因為利用

或

等平凡旋轉(zhuǎn)因子進行數(shù)據(jù)旋轉(zhuǎn)可以通過對輸入數(shù)據(jù)的實部與虛部進行互換和取反來完成，而這些操作并不引入量化誤差。因此為了計算

對應(yīng)的功率，首先需要確定數(shù)據(jù)加權(quán)矩陣

的主對角線上包含的非平凡旋轉(zhuǎn)因子的個數(shù)。進一步考慮到

是由旋轉(zhuǎn)因子矩陣

通過元素次序調(diào)整和維度擴展而產(chǎn)生的，我們的分析將從

入手。

(4.30)和(4.31)從信號功率的角度將radix-計算單元的特性概括為兩個方面：首先輸入信號

在經(jīng)過radix-計算單元后各分量功率將變?yōu)樵瓉淼?/p>

倍；其次radix-計算單元在定點運算過程中還會引入功率為

的新誤差項。將這一結(jié)論應(yīng)用于混合radix-算法所包含的其他M-1個計算單元，可以得到如圖4.3所示的信號功率傳播模型。

圖4.3混合

算法在定點運算方式下信號與量化誤差功率傳播模型

4.3流水線FFT結(jié)構(gòu)硬件參數(shù)的優(yōu)化配置

4.3.1流水線VLSI結(jié)構(gòu)存儲資源開銷分析

本節(jié)以SDF結(jié)構(gòu)和MDC結(jié)構(gòu)為代表，對流水線VLSI結(jié)構(gòu)存儲資源開銷進行分析。作為一種廣泛應(yīng)用的流水線FFT實現(xiàn)方案，SDF結(jié)構(gòu)的主要特征在于每一級蝶形運算單元內(nèi)用于實現(xiàn)數(shù)據(jù)次序調(diào)整的反饋連接。圖4.4以N=16為例對采用radix-2算法的SDF流水線結(jié)構(gòu)進行了描述。

圖4.4采用FFT算法的SDF流水線結(jié)構(gòu)（N=16

）

在MDC流水線結(jié)構(gòu)中，蝶形運算單元利用雙路換向器來調(diào)整參與運算的數(shù)據(jù)次序，圖4.5以N=16為例對采用radix-22

算法的MDC結(jié)構(gòu)進行了描述。與SDF結(jié)構(gòu)類似，算法階數(shù)向量k的調(diào)整只對流水線中數(shù)據(jù)旋轉(zhuǎn)單元的數(shù)目以及分布位置產(chǎn)生影響。要實現(xiàn)N=2L點的FFT運算，MDC結(jié)構(gòu)中蝶形運算單元所對應(yīng)的存儲開銷為

(4.43)

圖4.5采用radix-22FFT算法的MDC流水線結(jié)構(gòu)（N=16

）

根據(jù)(4.13)，M3(u,v)中的參數(shù)