楊 超 陳海燕 劉 勝

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073)(yc.nudt@gmail.com)

一種支持變形基24FFT的4路并行訪(fǎng)存方法

楊 超 陳海燕 劉 勝

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073)(yc.nudt@gmail.com)

IEEE 802.15.3c是高速無(wú)線(xiàn)個(gè)人局域網(wǎng)(high-rate wireless personal area networks, WPANs)的國(guó)際統(tǒng)一標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)要求采樣頻率為2.592 GHz的情況下在222.2 ns內(nèi)完成512點(diǎn)FFT運(yùn)算，這對(duì)FFT處理器提出了極高的標(biāo)準(zhǔn).為了滿(mǎn)足這一要求，部分FFT處理器采用了變形的基24FFT算法以及多運(yùn)算單元(processing element, PE)并行的方法.在多PE并行的情況下，只有支持其無(wú)沖突并行訪(fǎng)問(wèn)操作數(shù)以及并行按序輸入輸出數(shù)據(jù)的存儲(chǔ)系統(tǒng)設(shè)計(jì)，才能完全發(fā)揮出多個(gè)PE單元并行的優(yōu)勢(shì).根據(jù)4路并行變形的基24FFT運(yùn)算單元訪(fǎng)問(wèn)操作數(shù)的規(guī)律，設(shè)計(jì)了一種支持4路PE并行訪(fǎng)問(wèn)操作數(shù)的地址轉(zhuǎn)換方法；并且該方法支持并行按序輸入輸出數(shù)據(jù)，這解決了由于數(shù)據(jù)輸入或者輸出需要進(jìn)行位反序操作給并行按序輸入輸出帶來(lái)的困難.最后基于同一綜合約束條件進(jìn)行邏輯綜合，結(jié)果表明：該方法比之前的方法節(jié)約面積46%，功耗節(jié)約了28%，并且該方法支持連續(xù)數(shù)據(jù)流(continuous-flow)操作以及即位運(yùn)算(in-place).

IEEE 802.15.3c標(biāo)準(zhǔn)；基24；FFT算法；地址轉(zhuǎn)換；并行；即位運(yùn)算；連續(xù)數(shù)據(jù)流

快速傅里葉變換(fast Fourier transform, FFT)算法在數(shù)字信號(hào)處理中得到了越來(lái)越廣泛的應(yīng)用，比如圖像處理、媒體信號(hào)處理、光譜分析、電力系統(tǒng)、醫(yī)學(xué)分析中等.近些年來(lái)，正交頻譜分解技術(shù) (orth-ogonal frequency-division multiplexing, OFDM)在無(wú)線(xiàn)通信領(lǐng)域中得到了越來(lái)越廣泛的應(yīng)用，而OFDM技術(shù)的基礎(chǔ)是FFT算法；因此，隨著無(wú)線(xiàn)通信系統(tǒng)需求的發(fā)展，F(xiàn)FT處理器的硬件加速性能變得越來(lái)越重要.

為滿(mǎn)足無(wú)線(xiàn)通信應(yīng)用需求的發(fā)展，IEEE訂立了多種標(biāo)準(zhǔn)[1]，比如IEEE 802.11agn，IEEE 802.16e(OFDMA)，IEEE 802.16e(OFDM)標(biāo)準(zhǔn)等.FFT算法作為這些標(biāo)準(zhǔn)的核心和基礎(chǔ)算法，其運(yùn)算的實(shí)時(shí)性和處理速度要求越來(lái)越高.而802.15.3c標(biāo)準(zhǔn)，就是針對(duì)高速無(wú)線(xiàn)個(gè)人局域網(wǎng)(high-rate wireless personal area networks, WPANs)設(shè)計(jì)的標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)針對(duì)采樣頻率為2.592 GHz的512點(diǎn)數(shù)據(jù)進(jìn)行FFT運(yùn)算，F(xiàn)FT處理器完成512點(diǎn)數(shù)據(jù)的處理時(shí)間小于222.2 ns，這對(duì)處理器的設(shè)計(jì)實(shí)現(xiàn)帶來(lái)了極大的困難.

目前，各種各樣的FFT處理器已經(jīng)被設(shè)計(jì)出來(lái)，但是總體歸納起來(lái)主要分為2類(lèi)：基于流水結(jié)構(gòu)的FFT處理器[2-5]和基于存儲(chǔ)結(jié)構(gòu)的FFT處理器[6-7].基于流水線(xiàn)的處理器吞吐率和實(shí)時(shí)性比較高，但是這類(lèi)處理器需要占用更多的面積和功耗；由于基于存儲(chǔ)的FFT處理器具有占用面積和功耗小的優(yōu)點(diǎn)，目前在嵌入式應(yīng)用領(lǐng)域引起了越來(lái)越多的重視.

為了滿(mǎn)足應(yīng)用需求的不斷增長(zhǎng)，文獻(xiàn)[8-9]中提出了針對(duì)特定領(lǐng)域更高效的FFT算法，文獻(xiàn)[10]中的數(shù)字信號(hào)處理器為FFT算法設(shè)計(jì)了專(zhuān)用的指令集和體系結(jié)構(gòu)，文獻(xiàn)[4,9]中采用了多個(gè)運(yùn)算單元(processing element, PE)并行的結(jié)構(gòu)以提高運(yùn)算性能.

在采用多個(gè)PE單元并行運(yùn)算的結(jié)構(gòu)下，存儲(chǔ)接口是連接存儲(chǔ)器與輸入和輸出(IO)設(shè)備以及運(yùn)算單元之間的橋梁，只有存儲(chǔ)系統(tǒng)支持多個(gè)操作數(shù)并行訪(fǎng)問(wèn)，避免訪(fǎng)存沖突引起FFT處理數(shù)據(jù)停頓，才能發(fā)揮出FFT處理器并行運(yùn)算單元最大的數(shù)據(jù)運(yùn)算能力.并且在高速的FFT處理器中IO單元和并行運(yùn)算單元的數(shù)據(jù)帶寬應(yīng)當(dāng)匹配，這就要求數(shù)據(jù)IO單元能實(shí)現(xiàn)并行存取.然而由于在FFT運(yùn)算的開(kāi)始或者結(jié)束需要進(jìn)行位反序操作，這就給輸入或者輸出的并行帶來(lái)了困難.因此，一個(gè)支持運(yùn)算過(guò)程中操作數(shù)并行訪(fǎng)問(wèn)，以及支持?jǐn)?shù)據(jù)并行按序輸入或輸出的存儲(chǔ)系統(tǒng)至關(guān)重要，這直接影響著處理器性能的發(fā)揮.然而文獻(xiàn)[1,11-14]采用的按位相加、個(gè)別地址位異或等地址轉(zhuǎn)換方法僅僅針對(duì)基24或者固定基r有效，并不支持多路變形的基24FFT PE單元并行訪(fǎng)問(wèn)操作數(shù)以及數(shù)據(jù)并行按序輸入或者輸出.

1 算法原理

1.1 傳統(tǒng)基24算法

N個(gè)樣本點(diǎn)的DFT為

(1)

k=0,1,…,N-1,

(2)

n1,k1=[0:15];n2,k2=[0:31].

將式(2)帶入式(1)中:

X(16k2+k1)=

(3)

接下來(lái)可以繼續(xù)對(duì)式(3)進(jìn)行1級(jí)基24FFT運(yùn)算，之后進(jìn)行1級(jí)基2運(yùn)算，即可完成運(yùn)算.

通過(guò)式(3)我們可以發(fā)現(xiàn)，采用傳統(tǒng)的基24FFT運(yùn)算，一共需要24個(gè)存儲(chǔ)體、1個(gè)基24與基2 FFT運(yùn)算單元，然而基24運(yùn)算單元復(fù)雜度比較高，并且采用這種傳統(tǒng)的算法必須進(jìn)行3級(jí)FFT運(yùn)算.

指除職業(yè)暴露外其他個(gè)人行為發(fā)生的HIV暴露。暴露評(píng)估及處理原則尤其是阻斷用藥與職業(yè)暴露相似。尤其注意評(píng)估后阻斷用藥是自愿的原則及規(guī)范隨訪(fǎng)，以盡早發(fā)現(xiàn)感染者。

1.2 變形的基24算法

文獻(xiàn)[9]提出了一種變形的基24FFT算法，可以將16個(gè)操作數(shù)繼續(xù)分割成4個(gè)1組，采用4次基4 FFT算法以及簡(jiǎn)單的乘加單元即可完成.

n1=4m1+m2,

(4)

m1,m2,t1,t2=[0:3],

(5)

2 無(wú)沖突設(shè)計(jì)

2.1 需求分析

針對(duì)IEEE 802.15.3c設(shè)計(jì)標(biāo)準(zhǔn)，采樣時(shí)鐘頻率是2.592 GHz，假設(shè)FFT處理器的時(shí)鐘頻率是采樣頻率的18，即2.592 GHz×18=0.324 GHz.在IEEE 802.15.3c標(biāo)準(zhǔn)里，在連續(xù)數(shù)據(jù)流的情況下，整個(gè)運(yùn)算的時(shí)間只有222.2 ns，則在處理器運(yùn)算和IO并行的情況下，處理器運(yùn)算時(shí)間和IO時(shí)間只有72個(gè)時(shí)鐘周期.為了達(dá)到這一要求，表1列出了采用各種不同的基所需要的運(yùn)算級(jí)數(shù)、蝶形操作數(shù)總個(gè)數(shù)以及最大基的PE的并行度.

Table1 The Demand of FFT Processor of IEEE 802.15.3c

可以從表1中看出，基4 FFT算法為主的情況下一共需要4級(jí)基4和1級(jí)基2 FFT運(yùn)算，最低需要16個(gè)基4 PE并行；基8 FFT算法為主下一共需要3級(jí)基8 FFT運(yùn)算，最低需要4個(gè)基8 PE并行；基16 FFT算法為主的情況下，一共需要2級(jí)基16 和1級(jí)基2 FFT運(yùn)算，基16 PE并行數(shù)最低為2.采用這些傳統(tǒng)的FFT算法，在滿(mǎn)足時(shí)間要求的前提下，由于并行度過(guò)高，需要消耗大量的面積.而采用上述變形的基24FFT算法，并且結(jié)合存儲(chǔ)無(wú)沖突設(shè)計(jì)以及IO全并行的方法可以解決該問(wèn)題.

Fig. 1 The architecture of FFT processor圖1 FFT處理器結(jié)構(gòu)圖

為了滿(mǎn)足上述應(yīng)用需求，采用16個(gè)存儲(chǔ)體，并行進(jìn)行4路變形的基24FFT算法，第1級(jí)操作順序不做要求，第2級(jí)要求相鄰的2路取數(shù)在運(yùn)算完成后直接進(jìn)行基2 FFT運(yùn)算[9,15].雖然文獻(xiàn)[16]里的設(shè)計(jì)也可以在第2級(jí)基16 FFT運(yùn)算完成后，結(jié)果不用存回存儲(chǔ)器而直接進(jìn)行基2 FFT運(yùn)算，但是文獻(xiàn)[16]所采用的變形基16 FFT算法流水線(xiàn)過(guò)長(zhǎng)，PE單元占用面積比較大.為了完成上述設(shè)計(jì)，支持4路運(yùn)算單元同時(shí)運(yùn)算，并且支持在第2級(jí)運(yùn)算完成后可以不用存回而直接進(jìn)行基2 FFT運(yùn)算，存儲(chǔ)器的并行訪(fǎng)問(wèn)設(shè)計(jì)是關(guān)鍵.該處理器結(jié)構(gòu)如圖1所示，圖1中2個(gè)存儲(chǔ)器均包含有16個(gè)雙端口的存儲(chǔ)體；該FFT處理器通過(guò)控制開(kāi)關(guān)Switch0以及Switch1完成連續(xù)數(shù)據(jù)流操作；PE單元主要包括4個(gè)變形基16 PE和8個(gè)基2 PE.

2.2 操作數(shù)并行訪(fǎng)問(wèn)設(shè)計(jì)

本文主要針對(duì)操作數(shù)的并行訪(fǎng)問(wèn)進(jìn)行優(yōu)化，旋轉(zhuǎn)因子可以采用文獻(xiàn)[9,17]中提出的計(jì)算方法.在采用上述算法設(shè)計(jì)時(shí)，第1級(jí)變形的基24FFT算法4路運(yùn)算單元同時(shí)取數(shù)的地址如表2所示:

Table2 Operating Access Order in the First Stage

在FFT運(yùn)算的第1級(jí)，同一個(gè)時(shí)鐘周期需要取出的操作數(shù)可以表示為：k,k+128,k+256,k+384,k+1,k+129,k+257,k+385,k+2,k+130,k+258,k+386,k+3,k+131,k+259,k+387; 在每次基24運(yùn)算的子基4運(yùn)算時(shí)，k值加32；在每次基24運(yùn)算結(jié)束時(shí)，下一個(gè)基24運(yùn)算的k值相對(duì)于上一次基24運(yùn)算的初始k值加上4.

第2級(jí)4路并行基24FFT運(yùn)算，必須在相鄰2路基24FFT運(yùn)算完成后可以直接進(jìn)行基2 FFT運(yùn)算，數(shù)據(jù)的訪(fǎng)問(wèn)如表3所示.

在FFT運(yùn)算的第2級(jí)，同一個(gè)時(shí)鐘周期需要取出的操作數(shù)可以表示為：k,k+8,k+16,k+24,k+1,k+9,k+17,k+25,k+32,k+40,k+48,k+56,k+33,k+41,k+49,k+57.在每次基24運(yùn)算的子基4運(yùn)算時(shí)，k值加2；在每次基24運(yùn)算完成時(shí)，下一個(gè)基24運(yùn)算的初始k值相對(duì)于上一次基24運(yùn)算的初始k值加64.

通過(guò)該運(yùn)算訪(fǎng)問(wèn)操作數(shù)的順序我們可以發(fā)現(xiàn)，在采用16體低位交叉的存儲(chǔ)方式時(shí)，第1,2級(jí)每次需要取出的16個(gè)操作數(shù)分別存在于2個(gè)存儲(chǔ)體里，需要8個(gè)節(jié)拍才能取出，而這8個(gè)節(jié)拍期間PE會(huì)處于閑置狀態(tài)，故一般的低位交叉存儲(chǔ)方式并不適合該種變形算法.只有4路基24FFT運(yùn)算需要訪(fǎng)問(wèn)的16個(gè)操作數(shù)可以無(wú)沖突并行取出，才可以充分發(fā)揮運(yùn)算單元的并行性，才能在第2級(jí)基24FFT運(yùn)算完成后直接進(jìn)行基2 FFT運(yùn)算，以達(dá)到節(jié)約時(shí)鐘周期的目的.

在上述2級(jí)運(yùn)算中，每一個(gè)訪(fǎng)存節(jié)拍只有對(duì)存儲(chǔ)器準(zhǔn)確高效地讀寫(xiě)4路PE并行運(yùn)算結(jié)構(gòu)才能完全發(fā)揮出性能.而地址位b[8:7],b[2:0]可以區(qū)分出第1級(jí)的數(shù)據(jù)地址，地址位b[6:3],b[0]可以區(qū)分出第2級(jí)的數(shù)據(jù)地址.這里我們令addr表示地址所在的行，bank代表地址所在的存儲(chǔ)體，本文中，bank和addr分別表示如式(6)所示：

(6)

在采用式(6)中地址轉(zhuǎn)換方法轉(zhuǎn)換后，地址排列如表4所示.從表4可看出，在地址訪(fǎng)問(wèn)的第1級(jí)和第2級(jí)，1次16個(gè)操作數(shù)可以并行無(wú)沖突取出，這就說(shuō)明該地址轉(zhuǎn)換可以有效支持變形的基24FFT算法4路同時(shí)操作，在第2級(jí)運(yùn)算完成后可以直接進(jìn)行基2 運(yùn)算，節(jié)省了時(shí)鐘數(shù).

Table 3 Operating Order in the Second Stage

Table 4 Address Scheme After Transformation

2.3 結(jié)果并行順序輸出

為了在規(guī)定的時(shí)鐘周期內(nèi)完成運(yùn)算，數(shù)據(jù)的并行輸入和輸出至關(guān)重要.假設(shè)采用頻域分解DIF方法，數(shù)據(jù)的輸入可以并行順序輸入，然而結(jié)果輸出時(shí)，由于需要進(jìn)行位反序(bit reversal)操作，這給結(jié)果的并行按序輸出帶來(lái)了難度.所以衡量一個(gè)地址轉(zhuǎn)換方法的好壞，除了是否支持操作數(shù)可以并行訪(fǎng)問(wèn)，運(yùn)算結(jié)果可以并行順序輸出也是關(guān)鍵.而本文中的地址轉(zhuǎn)換方法可以支持運(yùn)算結(jié)果并行順序輸出.

在運(yùn)算結(jié)果輸出時(shí)，運(yùn)算結(jié)果是X(k)，地址k=k[8:0].數(shù)據(jù)輸入為x(n)，n可以表示為b[8:0].則k用n表示為k=k[8:0]={b[0],b[4:1],b[8:5]}.每個(gè)時(shí)鐘周期，并行輸出X(16m)～X(16m+15),m=[0:31].m初始值為0，每過(guò)一個(gè)時(shí)鐘周期，m值增加1，即運(yùn)算結(jié)果地址位k[8:4]每次增加1，一直增加到m值為31，即完成一次完整的運(yùn)算結(jié)果輸出.表5給出了運(yùn)算結(jié)果順序輸出分別對(duì)應(yīng)的bank地址和addr地址.

Table 5 Parallel and Normal Order Output of Result

從表5可以看出，在每一個(gè)時(shí)鐘周期并行輸出的16個(gè)連續(xù)的運(yùn)算結(jié)果，均存放在不同的bank體內(nèi)，也即本文中提出的地址轉(zhuǎn)換方法支持運(yùn)算結(jié)果并行按序輸出.

3 實(shí)現(xiàn)與對(duì)比

在文獻(xiàn)[1,11-14]中提出的FFT處理器無(wú)沖突并行地址排列方法，要么不支持多路變形的基24PE并行訪(fǎng)問(wèn)操作數(shù)，要么不支持?jǐn)?shù)據(jù)并行按序輸入或者輸出.在文獻(xiàn)[9,15]中，為了支持4路變形的基24FFT運(yùn)算單元并行訪(fǎng)問(wèn)操作數(shù)且數(shù)據(jù)并行按序輸入或者輸出的地址轉(zhuǎn)換式為

(7)

對(duì)比式(6)(7)，可以看出式(7)中采用的地址轉(zhuǎn)換方法，除了需要進(jìn)行異或操作外，還要對(duì)2個(gè)2位二進(jìn)制地址進(jìn)行乘法操作以及對(duì)2進(jìn)制地址進(jìn)行1次模4和模16操作.而本文中的地址轉(zhuǎn)換方法，可以?xún)H僅通過(guò)3個(gè)2輸入異或門(mén)和1個(gè)3輸入異或門(mén)進(jìn)行實(shí)現(xiàn)，地址轉(zhuǎn)換電路實(shí)現(xiàn)非常簡(jiǎn)單.將式(6)中的地址轉(zhuǎn)換方法，用電路進(jìn)行實(shí)現(xiàn)，b[8:0]代表初始地址，a[8:0]代表轉(zhuǎn)換后的完整地址，如圖2所示：

Fig. 2 Circuit of address transformation圖2 地址轉(zhuǎn)換電路

圖1中地址生成單元主要包括操作數(shù)地址生成單元[9]和輸出結(jié)果地址生成單元(DIF情況下，原始數(shù)據(jù)并行按序輸入很簡(jiǎn)單，所以不做介紹)，分別如圖3、圖4所示.圖3和圖4中的Address Trans-formation Unit就是地址轉(zhuǎn)換單元.圖3中，計(jì)數(shù)器從0開(kāi)始，每個(gè)周期加1，一直到31即完成1級(jí)FFT運(yùn)算，2級(jí)運(yùn)算都完成后，整個(gè)512點(diǎn)FFT運(yùn)算結(jié)束.圖4中，計(jì)數(shù)器從0每次加1到31，即可完成512點(diǎn)數(shù)據(jù)并行按序輸出，圖4中顯示地址為k值位反序后的n值，結(jié)果輸出順序和表5一樣.

Fig. 3 Circuit of operating address generation圖3 操作數(shù)地址生成單元

Fig. 4 Circuit of output result address generation圖4 輸出結(jié)果地址生成單元

將本文中提出的方法與文獻(xiàn)[9,15]中采用的方法也即式(7)，在某廠(chǎng)家65 nm工藝下進(jìn)行綜合，結(jié)果顯示式(7)綜合的面積為81 nm2，功耗為110μW；而本文中的面積約為44 nm2，功耗為79μW；而且在連續(xù)數(shù)據(jù)流的2組雙端口存儲(chǔ)器里，如圖3和圖4所示，數(shù)據(jù)輸入輸出以及運(yùn)算取操作數(shù)和存中間運(yùn)算結(jié)果共需要2組地址轉(zhuǎn)換單元，故一共需要16×2=32個(gè)地址轉(zhuǎn)換單元，故本文中的地址轉(zhuǎn)換方法相對(duì)文獻(xiàn)[9,15]中采用的方法一共節(jié)約面積(81-44)×32 nm2=1 184 nm2，功耗節(jié)約了(110-79)×32μW=992 μW.最后經(jīng)過(guò)對(duì)比，本文中的方法比式(7)的方法節(jié)約面積46%，功耗節(jié)約了28%.

4 總 結(jié)

本文提出了一種極其簡(jiǎn)單的支持4路變形基24FFT算法并行訪(fǎng)問(wèn)操作數(shù)的地址轉(zhuǎn)換方法，它支持即位運(yùn)算和連續(xù)數(shù)據(jù)流；更重要的是，這種簡(jiǎn)單的地址轉(zhuǎn)換方法同時(shí)可以支持在位反序的情況下數(shù)據(jù)并行按序輸入或者輸出，這就可以減少后續(xù)其他部件等待FFT運(yùn)算結(jié)果的時(shí)間.本文中的方法相對(duì)之前方法的實(shí)現(xiàn)更為簡(jiǎn)單，最后的面積和功耗的綜合結(jié)果表明了本文中的地址轉(zhuǎn)換方法是最優(yōu)的.

[1]Tsai P Y, Lin C Y. A generalized conflict-free memory addressing scheme for continuous-flow parallel-processing FFT processors with rescheduling[J]. IEEE Trans on Very Large Scale Integration Systems, 2012, 19(12): 2290-2302

[2]Chang Yunnan, Parhi K. An efficient pipelined FFT architecture[J]. IEEE Trans on Circuits and Systems II: Analog and Digital Signal Porcessing, 2003, 50(6): 322-325

[3]Lin Yuwei, Liu Hsuanyu, Lee Chenyi. A 1-GSs FFTIFFT processor for UWB applications[J]. IEEE Journal of Solid-State Circuits, 2005, 40(8): 1726-1735

[4]Shin M, Lee H. A high-speed four-parallel radix-24FFTIFFT processor for UWB applications[C]Proc of IEEE ISCSA’08. Piscataway, NJ: IEEE, 2008: 960-963

[5]Cho T, Lee H, Park J, et al. A high-speed low-complexity modified radix-25 FFT processor for gigabit WPAN applications[C]Proc of IEEE ISCAS’11. Piscataway, NJ: IEEE, 2011: 1259-1262

[6]Ma Y, Wanhammar L. A hardware efficient control of memory addressing for high-performance FFT processors[J]. IEEE Trans on Signal Processing, 2000, 48(3): 917-921

[7]Baas B M. A low-power, high-performance, 1024-point FFT processor[J]. IEEE Journal of Solid-State Circuits, 1999, 34(3): 380-387

[8]Fang Wei, Sun Guangzhong, Wu Chao, et al. A parallel algorithm of three-dimensional fast Fourier transform[J]. Journal of Computer Research and Development, 2011, 48(3): 440-446 (in Chinese)(方維, 孫廣中, 吳超, 等. 一種三維快速傅里葉變換并行算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(3): 440-446)

[9]Huang S J, Chen S G. A high-throughput radix-16 FFT processor with parallel and normal inputoutput ordering for IEEE 802.15.3c systems[J]. IEEE Trans on Circuits and Systems I: Regular Papers, 2012, 59(8): 1752-1765

[10]Chen Shuming, Li Zhentao, Wan Jianghua, et al. Research and development of high performance YHFT digital signal processor [J]. Journal of Computer Research and Development, 2006, 43(6): 993-1000 (in Chinese)(陳書(shū)明, 李振濤, 萬(wàn)江華, 等. 銀河飛騰"高性能數(shù)字信號(hào)處理器研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(6): 993-1000)

[11]Sorokin H, Takala J. Conflict-free parallel access scheme for mixed-radix FFT supporting IO permutations[C]Proc of IEEE ICASSP’11. Piscataway, NJ: IEEE, 2011: 1709-1712

[12]Takala J H, Jarvinen T S, Sorokin H T. Conflict-free parallel memory access scheme for FFT processors[C]Proc of IEEE ISCAS’03. Piscataway, NJ: IEEE, 2003: IV-524-IV-527

[13]Reisis D, Vlassopoulos N. Conflict-free parallel memory accessing techniques for FFT architectures[J]. IEEE Trans on Circuits and Systems I: Regular Papers, 2008, 55(11): 3438-3447

[14]Richardson S, Markovic D, Danowitz A, et al. Building conflict-free FFT schedules[J]. IEEE Trans on Circuits and Systems I: Regular Papers, 2015, 62(4): 1146-1155

[15]Liu Weichang, Wei Tingchen, Huang Yashiue, et al. All-digital synchronization for SCOFDM mode of IEEE 802.15.3c and IEEE 802.11ad[J]. IEEE Trans on Circuits and Systems I: Regular Papers, 2015, 62(2): 545-553

[16]Huang Shenjui, Chen Saugee. A green FFT processor with 2.5-GSs for IEEE 802.15.3c (WPANs)[C]Proc of IEEE ICGCS’10. Piscataway, NJ: IEEE, 2010: 9-13

[17]Huang S J, Chen S G. A new memoryless and low-latency FFT rotator architecture[C]Proc of ISIC’14. Piscataway, NJ: IEEE, 2014: 180-183

Yang Chao, born in 1990. Received his MSc degree from the College of Computer, National University of Defense Technology (NUDT), China, in 2015. PhD candidate in the College of Computer, NUDT, China. His main research interests include FFT processor, memory system and SIMD.

Chen Haiyan, born in 1967. Received her BE and master degrees in computer science from NUDT, China. Currently a professor in the College of Computer, NUDT, China. Her main research interests include VLSI designs, microprocessor architecture and the memory system.

Liu Sheng, born in 1984. Currently an associate professor at the College of Computer, NUDT, China. Received his PhD degree in electronic science and technology from NUDT, China. His main research interests include memory systems and VLSI designs.

An Address Parallel Access Method Supporting Four Reformulated Radix-24FFT

Yang Chao, Chen Haiyan, and Liu Sheng

(CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha410073)

IEEE 802.15.3c is international unified standard of high-rate wireless personal area networks (high-rate WPANs) to support high data rate applications such as high-definition streaming content downloads, home theater and etc, which needs to finish 512 FFT sizes operations in only 222.2 ns at the sampling rate of 2.592 GHz. To satisfy this demand, some FFT processors adopt parallel PEs and reformulated radix-24FFT algorithm which can reduce the required number of butterfly stages. When parallel PEs are employed, only memory system supporting these PEs parallel accessing operating data and normal order IO can express the full advantages of parallel PEs. According to the accessing law of four reformulated radix-24FFT PEs, this paper designs an address transformation method supporting four reformulated radix-24. And the method in this paper supports normal order IO, which solves the difficulty caused by bit reversal operation of initial or result data, to get a high-throughput design result. The implementation of the single address transformation unit is simple which requires only three two-input XOR gates and one three-input XOR gate. At the same synthesis condition, this method saves area 47% and power 24% compared with the method before. And this method supports continuous flow and in-place operation.

IEEE 802.15.3c; radix-24; FFT; address schedule; parallel; in-place; continuous-flow

2015-07-20；

2016-04-01

國(guó)家自然科學(xué)基金項(xiàng)目(61472432) This work was supported by the National Natural Science Foundation of China (61472432).

陳海燕(hychen@nudt.edu.cn)

TP332.1