無線通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計(jì) 課件 第4章Radix-2k FFT量化誤差分析與VLSI結(jié)構(gòu)優(yōu)化

第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仿真分析與實(shí)驗(yàn)測(cè)試本章小結(jié)

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

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

一般地，N點(diǎn)DFT運(yùn)算可以表示為(4.1)

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

在(4.2)中，

是一個(gè)用于完成

點(diǎn)倒位序次序變換的置換矩陣。為了給出

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

可以得到

這樣一來

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

(4.3)

另一方面，(3-2)中的M個(gè)連乘項(xiàng)對(duì)應(yīng)于級(jí)聯(lián)的M個(gè)運(yùn)算單元，這里

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

(4.4)

顯然m=M將使得

。對(duì)于給定的cm，

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

（1）當(dāng)km為奇數(shù)且km>1時(shí)

，

可以表示為

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

4.1.2混合radix-

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

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

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

是酉矩陣。實(shí)際上，(4.15)中的各分量矩陣都具有類似的性質(zhì)。證明這一點(diǎn)需要用到跨步置換矩陣的一些數(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算法進(jìn)行分解后得到了L個(gè)蝶形運(yùn)算矩陣

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

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

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

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

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

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

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

4.2.2量化誤差的功率估計(jì)

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

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

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

包含的N個(gè)元素被認(rèn)為是一組獨(dú)立同分布的隨機(jī)變量。在統(tǒng)計(jì)意義上，

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

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

中各元素的方差為

，我們可以得到

對(duì)應(yīng)的功率為

對(duì)于(4.19)中的誤差分量

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

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

不同的是，

中的元素并非都是誤差源，這是因?yàn)槔?/p>

或

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

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

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

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

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

入手。

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

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

倍；其次radix-計(jì)算單元在定點(diǎn)運(yùn)算過程中還會(huì)引入功率為

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

圖4.3混合

算法在定點(diǎn)運(yùn)算方式下信號(hào)與量化誤差功率傳播模型

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

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

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

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

）

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

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

(4.43)

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

）

根據(jù)(4.13)，M3(u,v)中的參數(shù)v=1對(duì)應(yīng)于算法階數(shù)km=1，而令M2(u,v)中的參數(shù)v=3將使得

中的參數(shù)i=2且

，而這進(jìn)一步要求算法階數(shù)km是奇數(shù)且

。結(jié)合(4.41)，我們可以將MDC結(jié)構(gòu)中旋轉(zhuǎn)因子的存儲(chǔ)開銷表示為

4.3.2流水線VLSI結(jié)構(gòu)計(jì)算資源開銷分析

流水線FFT結(jié)構(gòu)對(duì)計(jì)算資源的消耗主要來自于蝶形運(yùn)算單元包含的復(fù)數(shù)加法器以及數(shù)據(jù)旋轉(zhuǎn)單元包含的復(fù)數(shù)乘法器或CORDIC運(yùn)算模塊。在優(yōu)化硬件參數(shù)來對(duì)計(jì)算準(zhǔn)確度和硬件資源消耗進(jìn)行折衷之前，有必要對(duì)基于混合radix-2k算法的流水線結(jié)構(gòu)所消耗的計(jì)算資源進(jìn)行估計(jì)。前面提到對(duì)于任意的算法階數(shù)向量k，SDF和MDC流水線結(jié)構(gòu)均包含L=log2N個(gè)蝶形運(yùn)算單元，因此電路中復(fù)數(shù)加法的數(shù)目可以表示為

(4.45)

在復(fù)數(shù)乘法器的消耗方面，表4.1統(tǒng)計(jì)了混合radix-2k算法中位于第m級(jí)的radix-

計(jì)算單元

在SDF和MDC流水線結(jié)構(gòu)中所占用的復(fù)數(shù)乘法器數(shù)目

。每個(gè)向量中包含的3個(gè)元素分別對(duì)應(yīng)于radix-

計(jì)算單元內(nèi)用于實(shí)現(xiàn)

相位旋轉(zhuǎn)的復(fù)數(shù)乘法器以及通用復(fù)數(shù)乘法器的數(shù)目，這里對(duì)不同類型的復(fù)數(shù)乘法器分開進(jìn)行統(tǒng)計(jì)是考慮到它們具有不同的硬件復(fù)雜度。

當(dāng)算法階數(shù)向量k給定時(shí)，我們可以將流水線結(jié)構(gòu)中占用的復(fù)數(shù)乘法器數(shù)目fmu1記作

以各種類型的復(fù)數(shù)乘法器可以全部替換為CORDIC模塊，這樣流水線結(jié)構(gòu)中需要配置的CORDIC模塊的個(gè)數(shù)為

4.3.3FFT流水線VLSI結(jié)構(gòu)硬件參數(shù)優(yōu)化方法

在基于混合radix-2k算法的流水線結(jié)構(gòu)中，選取合適的數(shù)據(jù)位寬向量w和算法階數(shù)向量k可以實(shí)現(xiàn)計(jì)算準(zhǔn)確度和硬件復(fù)雜度的有效折衷。從前面的分析中我們得出，w和k的選擇將會(huì)在較大程度上影響FFT計(jì)算單元對(duì)存儲(chǔ)器的消耗，同時(shí)k也決定了流水線FFT結(jié)構(gòu)所占用的復(fù)數(shù)乘法器或CORDIC單元的數(shù)目。一般地，基于量化誤差來優(yōu)化FFT計(jì)算單元的硬件參數(shù)大致可歸結(jié)為以下兩類問題：

（1）硬件資源優(yōu)先型，即在SQNR不低于給定基準(zhǔn)TSQNR的前提下最小化FFT計(jì)算單元的硬件資源開銷。以最小化系統(tǒng)對(duì)存儲(chǔ)資源的消耗為例，可以得到以下優(yōu)化問題：

(4.48)

2）計(jì)算準(zhǔn)確度優(yōu)先型，即在存儲(chǔ)開銷不高于給定約束Rc的條件下最大化FFT計(jì)算結(jié)果的SQNR，這可以描述為以下的優(yōu)化問題：

(4.49)

實(shí)際上FFT計(jì)算單元對(duì)復(fù)數(shù)乘法器或CORDIC模塊的消耗也可以作為約束條件或優(yōu)化目標(biāo)體現(xiàn)在(4.48)和(4.49)中，我們?cè)谶@里僅將存儲(chǔ)開銷納入上面的優(yōu)化問題，這是因?yàn)榇鎯?chǔ)資源的消耗與SQNR存在較強(qiáng)關(guān)聯(lián)性并且直接決定了流水線FFT結(jié)構(gòu)所占用的電路面積大小。確定最優(yōu)的w,k

需要到對(duì)上面的非線性整數(shù)優(yōu)化問題進(jìn)行求解，而在經(jīng)典優(yōu)化理論框架下尚無有效的數(shù)學(xué)工具來解決這一NP難問題。我們注意到(4.48)和(4.49)的后兩個(gè)約束條件給變量w,k

劃定了可行域

，其中(w,k)

內(nèi)包含的

參數(shù)對(duì)的個(gè)數(shù)為

當(dāng)算法4.2的外循環(huán)達(dá)到最大次數(shù)或者歷史最優(yōu)解不進(jìn)行更新時(shí)搜索過程終止，由于模擬退火算法是一種啟發(fā)式算法，此時(shí)得到的w,k無法保證一定是全局最優(yōu)解。然而注意到

能夠保證每次產(chǎn)生的鄰域解均落在可行域

內(nèi)，這有助于提升模擬退火算法的搜索效率以及獲得全局最優(yōu)解的可能性。

4.4仿真分析與實(shí)驗(yàn)測(cè)試

4.4.1流水線結(jié)構(gòu)SQNR與存儲(chǔ)開銷的仿真分析

為了研究流水線FFT結(jié)構(gòu)在定點(diǎn)運(yùn)算方式下計(jì)算結(jié)果的SQNR與存儲(chǔ)開銷的關(guān)系，我們用白噪聲源來產(chǎn)生輸入序列x0，其中每個(gè)數(shù)據(jù)的實(shí)部和虛部在[-1,1]的取值范圍內(nèi)均勻分布。因此

，代入(4.34)可以得到

將上面的

代入(4.49)描述的優(yōu)化問題并改變參數(shù)Rc，我們可以得到在存儲(chǔ)資源約束給定的情況下FFT計(jì)算單元的可達(dá)SQNR性能。圖4.6在FFT長(zhǎng)度N=512以及運(yùn)算結(jié)果實(shí)部和虛部數(shù)據(jù)位寬wfin=16的情況下給出了SQNR與存儲(chǔ)資源消耗的關(guān)系曲線。

圖4.6流水線FFT結(jié)構(gòu)輸出數(shù)據(jù)SQNR與存儲(chǔ)資源消耗的關(guān)系曲線

圖4.6流水線FFT結(jié)構(gòu)輸出數(shù)據(jù)SQNR與存儲(chǔ)資源消耗的關(guān)系曲線

圖4.7和圖4.8以基于SDF流水線結(jié)構(gòu)實(shí)現(xiàn)的FFT計(jì)算單元為例，比較了在數(shù)據(jù)位寬向量w和算法階數(shù)向量k的不同配置方式下，F(xiàn)FT計(jì)算結(jié)果準(zhǔn)確度以及FFT計(jì)算單元的存儲(chǔ)資源開銷。

圖4.7基于復(fù)數(shù)乘法器的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

圖4.7基于復(fù)數(shù)乘法器的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

圖4.7基于復(fù)數(shù)乘法器的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

圖4.8基于CORDIC模塊的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

圖4.8基于CORDIC模塊的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

圖4.8基于CORDIC模塊的SDF流水線結(jié)構(gòu)的數(shù)據(jù)位寬配置方案比較（

N=32768）

4.4.2流水線FFT結(jié)構(gòu)SQNR的實(shí)驗(yàn)測(cè)試

圖4.9對(duì)比了在數(shù)據(jù)位寬向量

的不同配置下FFT計(jì)算結(jié)果SQNR的理論估計(jì)值與實(shí)測(cè)值?？梢钥吹綄?duì)于利用復(fù)數(shù)乘法器的SDF流水線結(jié)構(gòu)，SQNR的估計(jì)值通常略高于其實(shí)際數(shù)值，這是因?yàn)槲覀冊(cè)谕茖?dǎo)中為了得到SQNR的閉合表達(dá)式而假設(shè)流水線結(jié)構(gòu)每一級(jí)所產(chǎn)生的量化誤差是不相關(guān)的，而事實(shí)上這些誤差之間存在著一定的相關(guān)性。當(dāng)SDF結(jié)構(gòu)使用CORDIC模塊來實(shí)現(xiàn)數(shù)據(jù)旋轉(zhuǎn)時(shí)，在某些參數(shù)配置方式下SQNR的估計(jì)值也會(huì)低于實(shí)測(cè)值，這主要是由于附錄在分析CORDIC運(yùn)算單元的量化誤差時(shí),采用的是殘余角度誤差方差的上界，相應(yīng)地(4.35)對(duì)CORDIC運(yùn)算單元量化誤差方差的估計(jì)在某些情況下會(huì)大于實(shí)際數(shù)值?？傮w上來看，SQNR估計(jì)值和實(shí)測(cè)結(jié)果的差距不超過1.5dB，因此我們認(rèn)為(4.34)能夠?yàn)镕FT硬件結(jié)構(gòu)的設(shè)計(jì)提供計(jì)算準(zhǔn)確度的有效參考。

圖4.9SQNR理論估計(jì)值與實(shí)測(cè)值比較

圖