《無(wú)線(xiàn)通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計(jì)》全套教學(xué)課件

目錄MENU第1章無(wú)線(xiàn)通信系統(tǒng)中FFT與信道譯碼技術(shù)第2章基于并行流水線(xiàn)的FFT計(jì)算方法及VLSI結(jié)構(gòu)第3章基于單端口存儲(chǔ)器的FFT處理器及VLSI結(jié)構(gòu)第4章Radix-2k

FFT量化誤差分析與VLSI結(jié)構(gòu)優(yōu)化第5章Turbo碼并行譯碼器VLSI結(jié)構(gòu)設(shè)計(jì)第6章卷積碼并行列表譯碼算法與硬件結(jié)構(gòu)設(shè)計(jì)第7章無(wú)人機(jī)通信系統(tǒng)VLSI設(shè)計(jì)本課件是可編輯的正常PPT課件第1章無(wú)線(xiàn)通信系統(tǒng)中FFT

與信道譯碼技術(shù)1.1無(wú)線(xiàn)通信的基本數(shù)學(xué)原理1.2FFT在無(wú)線(xiàn)通信系統(tǒng)中的應(yīng)用1.3無(wú)線(xiàn)通信系統(tǒng)典型的信道編譯碼方法本章小結(jié)本課件是可編輯的正常PPT課件

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

1.1無(wú)線(xiàn)通信的基本數(shù)學(xué)原理本課件是可編輯的正常PPT課件

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

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

(1.1)本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

(1.4)

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

本課件是可編輯的正常PPT課件

圖1.1從基帶發(fā)送信號(hào)xb(t)到基帶接收信號(hào)yb(t)的系統(tǒng)框圖本課件是可編輯的正常PPT課件

1.1.2離散時(shí)間基帶模型

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

(1.9)本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖1.2中給出了完整的離散時(shí)間基帶系統(tǒng)框圖。圖1.2從基帶發(fā)送符號(hào)x[m]到收信號(hào)的基帶采樣y[m]的離散時(shí)間基帶系統(tǒng)框圖本課件是可編輯的正常PPT課件

1.1.3加性白噪聲

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

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

(1.16)

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

(1.17)本課件是可編輯的正常PPT課件

圖1.3考慮噪聲的完整離散時(shí)間基帶系統(tǒng)框圖本課件是可編輯的正常PPT課件

在(1.17)中，是低通噪聲在時(shí)刻的采樣值。與信號(hào)分量一樣，白噪聲經(jīng)過(guò)下變頻、基帶濾波并進(jìn)行理想采樣，因此可以證明本課件是可編輯的正常PPT課件

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

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

1.2FFT在無(wú)線(xiàn)通信系統(tǒng)中的應(yīng)用本課件是可編輯的正常PPT課件

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

圖1.4擴(kuò)頻接收機(jī)偽碼捕獲流程本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

第2步：并行讀取p個(gè)序列的數(shù)據(jù)，每個(gè)序列分別與本地?cái)U(kuò)頻碼序列的

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

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

本課件是可編輯的正常PPT課件

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

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

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

是某一信號(hào)空間的正交基，它們滿(mǎn)足

(1.20)

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

典型的OFDM系統(tǒng)收發(fā)模型如圖1.5所示。圖1.5典型OFDM系統(tǒng)收發(fā)模型本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

圖1.6空間復(fù)用結(jié)構(gòu)MIMO-OFDM系統(tǒng)收發(fā)模型本課件是可編輯的正常PPT課件

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

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

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

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

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

(1.28)本課件是可編輯的正常PPT課件

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

(1.29)本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

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

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

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

1.3.1卷積碼編碼及譯碼

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

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

本課件是可編輯的正常PPT課件

圖1.8編碼速率為1/3的卷積碼編碼器本課件是可編輯的正常PPT課件

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

1.3.2Turbo碼編碼及譯碼

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

本課件是可編輯的正常PPT課件

圖1.10采用turbo碼編譯碼方案的通信系統(tǒng)收發(fā)端框圖本課件是可編輯的正常PPT課件

圖1.11給出了LTE系統(tǒng)的turbo編碼框圖。圖1.11LTE系統(tǒng)turbo編碼框圖本課件是可編輯的正常PPT課件

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

其中

分別為正向多項(xiàng)式和反饋多項(xiàng)式。在編碼開(kāi)始前，所有的以為繼續(xù)存器初始狀態(tài)全部設(shè)為‘0’，令K表示要進(jìn)行編碼的比特?cái)?shù)目，輸出的規(guī)則如下：本課件是可編輯的正常PPT課件

尾比特的生成過(guò)程如下：

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

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

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

本課件是可編輯的正常PPT課件

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

，同時(shí)受到尾比特的影響，每個(gè)分量碼的長(zhǎng)度為

。

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

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

個(gè)子塊并對(duì)每個(gè)子塊配置獨(dú)立的運(yùn)算單元進(jìn)行譯碼操作，這樣可以使譯碼器的吞吐量近似提升

倍。本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

本章小結(jié)

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

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

FFT算法原理2.2FFT串行流水線(xiàn)計(jì)算結(jié)構(gòu)2.3FFT并行流水線(xiàn)計(jì)算方法2.4FFT混合抽取多路延遲反饋VLSI結(jié)構(gòu)2.5理論分析與硬件測(cè)試本章小結(jié)本課件是可編輯的正常PPT課件

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

對(duì)于輸入序列xn

，其

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

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

本課件是可編輯的正常PPT課件

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

利用混合基算法可以將

進(jìn)一步分解為：本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

圖2.2FFT串行流水線(xiàn)計(jì)算結(jié)構(gòu)頂層方案本課件是可編輯的正常PPT課件

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

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

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

圖2.3延遲反饋VLSI結(jié)構(gòu)示意圖（以16點(diǎn)FFT計(jì)算為例）本課件是可編輯的正常PPT課件

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

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

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

本課件是可編輯的正常PPT課件

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

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

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

本課件是可編輯的正常PPT課件

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

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

本課件是可編輯的正常PPT課件

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

；

從第1級(jí)蝶形運(yùn)算單元的輸入開(kāi)始，數(shù)據(jù)流以?xún)陕凡⑿械姆绞皆诹魉€(xiàn)內(nèi)單向流動(dòng)，不存在反饋環(huán)路。

本課件是可編輯的正常PPT課件

圖2.4延遲換向VLSI結(jié)構(gòu)及數(shù)據(jù)次序變換示意圖（以16點(diǎn)FFT計(jì)算為例）本課件是可編輯的正常PPT課件

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

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

本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

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

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

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

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

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

圖2.4延遲換向VLSI結(jié)構(gòu)及數(shù)據(jù)次序變換示意圖（以16點(diǎn)FFT計(jì)算為例）本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖2.6數(shù)據(jù)排序單元最小存儲(chǔ)器消耗Lmin的物理意義本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖2.7達(dá)到最小存儲(chǔ)器消耗的流水線(xiàn)結(jié)構(gòu)數(shù)據(jù)排序單元本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

級(jí)由一個(gè)長(zhǎng)度為L(zhǎng)min(i)的移位寄存器和共用同一信號(hào)ci的兩個(gè)數(shù)據(jù)選擇器構(gòu)成。本課件是可編輯的正常PPT課件

圖2.8倒位序次序變換方案的硬件實(shí)現(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

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

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

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

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

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

以旋轉(zhuǎn)因子實(shí)部的壓縮存儲(chǔ)為例，圖2.9對(duì)上面介紹的數(shù)據(jù)壓縮過(guò)程進(jìn)行了描述。圖2.9旋轉(zhuǎn)因子的壓縮存儲(chǔ)（以數(shù)據(jù)實(shí)部壓縮為示意）本課件是可編輯的正常PPT課件

在上述方案中，參數(shù)λ1的最優(yōu)值λ1*需要最小化查找表的存儲(chǔ)資源消耗，即本課件是可編輯的正常PPT課件

圖2.10不同參數(shù)配置下旋轉(zhuǎn)因子壓縮存儲(chǔ)的最優(yōu)分組長(zhǎng)度本課件是可編輯的正常PPT課件

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

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

一般地，N=2u點(diǎn)的FFT和IFFT運(yùn)算可以分別定義為下面的形式：本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖2.12FFT并行計(jì)算的頂層結(jié)構(gòu)框圖本課件是可編輯的正常PPT課件

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

2.4.1基于折疊變換的延遲反饋結(jié)構(gòu)分析本課件是可編輯的正常PPT課件

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

圖2.13利用折疊變換將DIFFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

圖2.14利用折疊變換將DITFFT數(shù)據(jù)流圖轉(zhuǎn)化為SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

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

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

圖2.15能同時(shí)執(zhí)行DITFFT和DIFFFT的SDF流水線(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

圖2.16用于同時(shí)執(zhí)行DITFFT和DIFFFT的SDF計(jì)算單元結(jié)構(gòu)本課件是可編輯的正常PPT課件

圖2.16用于同時(shí)執(zhí)行DITFFT和DIFFFT的SDF計(jì)算單元結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

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

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

的radix-2M2DF結(jié)構(gòu)（簡(jiǎn)記為R2M2DF結(jié)構(gòu)）為例來(lái)對(duì)硬件設(shè)計(jì)方案進(jìn)行說(shuō)明。如圖2.17所示。本課件是可編輯的正常PPT課件

圖2.17R2M2DF并行流水線(xiàn)結(jié)構(gòu)（N=32,P=2）本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

2.5理論分析與硬件測(cè)試

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

或其他給定的旋轉(zhuǎn)因子。本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

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

和

的形式，計(jì)算時(shí)延被定義為FFT計(jì)算模塊的首組輸入數(shù)據(jù)和首組輸出數(shù)據(jù)之間的時(shí)鐘周期個(gè)數(shù)。本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

在不同配置方式下各流水線(xiàn)FFT計(jì)算結(jié)構(gòu)的硬件資源開(kāi)銷(xiāo)和計(jì)算時(shí)延、吞吐量等性能記錄在了表2.3中本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

以radix-和radix-FFT算法對(duì)應(yīng)的應(yīng)用場(chǎng)景為例，圖2.20統(tǒng)計(jì)了不同流水線(xiàn)FFT計(jì)算結(jié)構(gòu)的算術(shù)運(yùn)算與邏輯操作對(duì)sliceLUTs的消耗情況。整體來(lái)看，構(gòu)建M2DF結(jié)構(gòu)所需的sliceLUTs最少，MDC結(jié)構(gòu)次之，而MDF結(jié)構(gòu)消耗的sliceLUTs最多。此外可以發(fā)現(xiàn)三種流水線(xiàn)結(jié)構(gòu)均在蝶形運(yùn)算單元的實(shí)現(xiàn)上消耗了大量的sliceLUTs資源，由于MDF結(jié)構(gòu)和其他兩種方案相比需要更多的加法器來(lái)完成運(yùn)算，因而其對(duì)sliceLUTs的需求量也更大。M2DF結(jié)構(gòu)的計(jì)算單元需要同時(shí)對(duì)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最多。本課件是可編輯的正常PPT課件

圖2.20FFT計(jì)算模塊內(nèi)的不同操作對(duì)sliceLUTs消耗情況統(tǒng)計(jì)本課件是可編輯的正常PPT課件

圖2.20FFT計(jì)算模塊內(nèi)的不同操作對(duì)sliceLUTs消耗情況統(tǒng)計(jì)本課件是可編輯的正常PPT課件

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

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

本章小結(jié)

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

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

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

一般地，radix-2kFFT算法通過(guò)

級(jí)的radix-2k蝶形計(jì)算來(lái)完成N=2n點(diǎn)的FFT運(yùn)算，其中

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

分別為：

(3.1)

本課件是可編輯的正常PPT課件

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

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

個(gè)radix-蝶形，第t+1個(gè)蝶形（

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

(3.2)本課件是可編輯的正常PPT課件

其中

，

表示為

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

其中

表示在

范圍內(nèi)以

為增量的整數(shù)序列。本課件是可編輯的正常PPT課件

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

(3.4)本課件是可編輯的正常PPT課件

其中

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

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

(3.5)

類(lèi)似地，

的第一行和第二行表示上支路和下支路的輸出數(shù)據(jù)次序。本課件是可編輯的正常PPT課件

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

圖3.1基于存儲(chǔ)器的radix-2kFFT處理器頂層架構(gòu)本課件是可編輯的正常PPT課件

圖3.2以

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

圖3.2基于MDC計(jì)算電路的處理單元結(jié)構(gòu)本課件是可編輯的正常PPT課件

FFT處理器的數(shù)據(jù)調(diào)度流程如圖3.3所示。圖3.3FFT處理器數(shù)據(jù)調(diào)度流程本課件是可編輯的正常PPT課件

3.2FFT處理器數(shù)據(jù)訪(fǎng)問(wèn)方案設(shè)計(jì)

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

圖3.4并行度為4的32點(diǎn)radix-22FFT在不同數(shù)據(jù)訪(fǎng)問(wèn)方案下的計(jì)算流程本課件是可編輯的正常PPT課件

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

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

(3.6)

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

對(duì)于第m級(jí)（

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

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

(3.9)

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

(3.15)

值得注意的是，這里第2級(jí)至第M-1級(jí)蝶形運(yùn)算操作數(shù)的緩存方式，實(shí)際也是第1級(jí)至第M-2級(jí)蝶形運(yùn)算計(jì)算結(jié)果的緩存方式。本課件是可編輯的正常PPT課件

基于(3.15)的數(shù)據(jù)存儲(chǔ)方式，可以滿(mǎn)足第1級(jí)至第M-2級(jí)計(jì)算過(guò)程中的數(shù)據(jù)無(wú)沖突訪(fǎng)問(wèn)，具體總結(jié)如下：

定理3.1：若第m級(jí)（

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

，那么

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

2）第u級(jí)（

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

個(gè)時(shí)鐘周期。

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

與前M-1級(jí)不同，第M-1級(jí)蝶形運(yùn)算結(jié)果按照如下方式存儲(chǔ)在數(shù)據(jù)緩存單元中：本課件是可編輯的正常PPT課件

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

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

個(gè)時(shí)鐘周期。本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

，那么其無(wú)沖突數(shù)據(jù)訪(fǎng)問(wèn)要求數(shù)據(jù)讀取基于(3.16)執(zhí)行，數(shù)據(jù)寫(xiě)入基于(3.23)執(zhí)行，并且對(duì)于前N/2個(gè)數(shù)據(jù)，數(shù)據(jù)寫(xiě)入與數(shù)據(jù)讀取操作之間的延遲為

個(gè)時(shí)鐘周期，對(duì)于后N/2個(gè)數(shù)據(jù)，數(shù)據(jù)寫(xiě)入與數(shù)據(jù)讀取操作之間的延遲為2k+1個(gè)時(shí)鐘周期。本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

因此的具體表達(dá)式為本課件是可編輯的正常PPT課件

進(jìn)而基于(3.23)，可以確定數(shù)據(jù)緩存單元寫(xiě)入?yún)?shù)的表達(dá)式為本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

用

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

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

，并利用

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

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

操作，物理地址a可以轉(zhuǎn)換為本課件是可編輯的正常PPT課件

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

，Pc=4

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

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

圖3.5FFT處理器無(wú)沖突數(shù)據(jù)訪(fǎng)問(wèn)流程示意圖（以64點(diǎn)的4路并行FFT計(jì)算為例）本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

以上三種運(yùn)算覆蓋了數(shù)據(jù)映射規(guī)則中的基本運(yùn)算類(lèi)型，這表明數(shù)據(jù)訪(fǎng)問(wèn)參數(shù)i，j和a的可以通過(guò)數(shù)據(jù)位的調(diào)整來(lái)生成。為了說(shuō)明這一點(diǎn)，我們首先對(duì)前M-2級(jí)計(jì)算中的數(shù)據(jù)訪(fǎng)問(wèn)次序進(jìn)行討論。如圖3.6所示。本課件是可編輯的正常PPT課件

圖3.6通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生前M-2級(jí)數(shù)據(jù)訪(fǎng)問(wèn)索引本課件是可編輯的正常PPT課件

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

比特、1比特、

比特、1比特和k-1比特，如圖3.7所示。注意當(dāng)M=2時(shí)需要略去第一個(gè)數(shù)據(jù)段，因?yàn)榇藭r(shí)其長(zhǎng)度為

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

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

本課件是可編輯的正常PPT課件

圖3.7通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第

級(jí)數(shù)據(jù)訪(fǎng)問(wèn)索引本課件是可編輯的正常PPT課件

對(duì)于第M級(jí)FFT計(jì)算，計(jì)數(shù)器被劃分為6個(gè)數(shù)據(jù)段，從最高位開(kāi)始數(shù)據(jù)段長(zhǎng)度分別為1比特、

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

，如圖3.8所示。本課件是可編輯的正常PPT課件

圖3.8通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第M級(jí)數(shù)據(jù)訪(fǎng)問(wèn)索引本課件是可編輯的正常PPT課件

圖3.8通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第M級(jí)數(shù)據(jù)訪(fǎng)問(wèn)索引本課件是可編輯的正常PPT課件

通過(guò)數(shù)據(jù)段調(diào)整來(lái)得到數(shù)據(jù)索引后，可以根據(jù)映射規(guī)則確定數(shù)據(jù)訪(fǎng)問(wèn)所需的RAM標(biāo)識(shí)符

與物理地址

。如圖3.9所示，數(shù)據(jù)訪(fǎng)問(wèn)參數(shù)的生成只涉及到數(shù)據(jù)截位和邏輯異或操作。本課件是可編輯的正常PPT課件

圖3.9基于給定的數(shù)據(jù)訪(fǎng)問(wèn)索引產(chǎn)生數(shù)據(jù)訪(fǎng)問(wèn)參數(shù)的方式本課件是可編輯的正常PPT課件

圖3.9基于給定的數(shù)據(jù)訪(fǎng)問(wèn)索引產(chǎn)生數(shù)據(jù)訪(fǎng)問(wèn)參數(shù)的方式本課件是可編輯的正常PPT課件

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

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

路并行輸入/輸出數(shù)據(jù)與pc路數(shù)據(jù)緩存單元并行讀寫(xiě)數(shù)據(jù)之間的并行度轉(zhuǎn)換。本課件是可編輯的正常PPT課件

圖3.10輸入輸出轉(zhuǎn)換單元VLSI實(shí)現(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

圖3.11數(shù)據(jù)次序變換單元VLSI實(shí)現(xiàn)結(jié)構(gòu)本課件是可編輯的正常PPT課件

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

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

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

本課件是可編輯的正常PPT課件

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

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

。參照?qǐng)D3.6和圖3.7中基于數(shù)據(jù)段分割與重排方法生成的

格式，可以快速生成(3.26)中旋轉(zhuǎn)因子復(fù)指數(shù)項(xiàng)的分子部分作為旋轉(zhuǎn)因子的訪(fǎng)問(wèn)索引，如圖3.12所示。本課件是可編輯的正常PPT課件

圖3.12旋轉(zhuǎn)因子訪(fǎng)問(wèn)索引生成方式（以第1至第M-1級(jí)計(jì)算涉及的旋轉(zhuǎn)因子為例）本課件是可編輯的正常PPT課件

3.4理論分析與硬件測(cè)試

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

表3.1總結(jié)了所設(shè)計(jì)的FFT處理器在FFT計(jì)算長(zhǎng)度為N=2n、數(shù)據(jù)輸入與計(jì)算結(jié)果輸出并行度為q、計(jì)算并行度為pc=2k情況下的硬件開(kāi)銷(xiāo)，并同時(shí)評(píng)估了計(jì)算延遲與吞吐量。本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

本課件是可編輯的正常PPT課件

這里假設(shè)FFT在開(kāi)始輸出計(jì)算結(jié)果的同時(shí)立刻接收新的數(shù)據(jù)。當(dāng)FFT處理器部署兩個(gè)數(shù)據(jù)緩存單元時(shí)，處理單元在執(zhí)行FFT運(yùn)算時(shí)即可接收新的數(shù)據(jù)，此時(shí)吞吐量進(jìn)一步提升至本課件是可編輯的正常PPT課件

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

本課件是可編輯的正常PPT課件

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

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

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

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

圖3.13不同F(xiàn)FT處理器占用的FPGAslice數(shù)量與可以達(dá)到的數(shù)據(jù)吞吐量關(guān)系圖本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

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

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

表3.4對(duì)比了不同F(xiàn)FT處理器的AISC實(shí)現(xiàn)結(jié)果，為了更為直觀(guān)地比較不同設(shè)計(jì)方案，我們引入FFT單點(diǎn)歸一化面積和單點(diǎn)歸一化能量來(lái)評(píng)價(jià)硬件效率：本課件是可編輯的正常PPT課件

本課件是可編輯的正常PPT課件

本章小結(jié)

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

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

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

二是無(wú)沖突數(shù)據(jù)訪(fǎng)問(wèn)控制簡(jiǎn)單，不因計(jì)算并行度的增加而更為復(fù)雜；本課件是可編輯的正常PPT課件

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

Radix-2k算法是FFT硬件設(shè)計(jì)中廣泛應(yīng)用的一類(lèi)計(jì)算方案。與經(jīng)典的radix-2k算法或混合基算法相比，利用radix-2k算法來(lái)設(shè)計(jì)FFT硬件結(jié)構(gòu)，其優(yōu)勢(shì)有兩點(diǎn)：一是radix-2k算法的蝶形運(yùn)算以最簡(jiǎn)單的radix-2運(yùn)算