于　東，李　麗，韓　峰，王　堃，豐　帆，潘紅兵

(南京大學(xué) 電子科學(xué)與工程學(xué)院,　南京 210046)

?

·信號(hào)處理·

一種高精度的大點(diǎn)數(shù)二維FFT處理器設(shè)計(jì)

于東，李麗，韓峰，王堃，豐帆，潘紅兵

(南京大學(xué) 電子科學(xué)與工程學(xué)院,南京 210046)

摘要：基于傳統(tǒng)的頻域抽取快速傅里葉變換(FFT)算法以及二維FFT算法，設(shè)計(jì)了一種高精度的大點(diǎn)數(shù)FFT處理器。該處理單元采用一個(gè)狀態(tài)機(jī)控制整個(gè)運(yùn)算流程，針對(duì)小點(diǎn)數(shù)情況的一維FFT算法和大點(diǎn)數(shù)情況的二維FFT算法，該處理器都可以智能地選擇合適的處理流程和緩存管理，自動(dòng)地完成整個(gè)FFT運(yùn)算而無(wú)需軟件介入。在支持大點(diǎn)數(shù)的二維FFT算法的基礎(chǔ)上，該設(shè)計(jì)還通過(guò)對(duì)旋轉(zhuǎn)因子計(jì)算過(guò)程的優(yōu)化，以提高在大點(diǎn)數(shù)情況下的精度表現(xiàn)，在4M長(zhǎng)度的輸入序列時(shí)可以獲得130 dB以上的信噪比。

關(guān)鍵詞：快速傅里葉變換；二維快速傅里葉算法；高精度；大點(diǎn)數(shù)；旋轉(zhuǎn)因子優(yōu)化

0引言

快速傅里葉變換(FFT)是信號(hào)處理領(lǐng)域一種重要的快速變換方法，自幾十年前Cooley和Tukey[1]提出FFT至今，這一算法日趨成熟，并衍生出多種新的形式，但主要可以歸納為兩個(gè)發(fā)展方向，一是針對(duì)2的整數(shù)次冪的算法，如：基2算法、基4算法[2]和分裂基算法[3]等;另一個(gè)是N不等于2 的整數(shù)次冪的算法，如：素因子算法和Winograd算法。隨著計(jì)算機(jī)軟件技術(shù)和超大規(guī)模集成電路(VLSI)的發(fā)展，如今我們可以非常方便地使用軟件實(shí)現(xiàn)FFT，在速度要求更高的領(lǐng)域，需要通過(guò)電路來(lái)實(shí)現(xiàn)這一算法[4]。

鑒于FFT本身的特點(diǎn)，通過(guò)電路實(shí)現(xiàn)存在一些難點(diǎn)，譬如如何用同一套電路實(shí)現(xiàn)不同長(zhǎng)度輸入序列的FFT，運(yùn)算速度和精度如何保證等等。事實(shí)上，通過(guò)ASIC來(lái)實(shí)現(xiàn)某種特定的算法，雖然可以達(dá)到較高的性能，但通常會(huì)存在諸如緩存容量方面的限制[5]，如何權(quán)衡性能和硬件資源，這是一個(gè)電路設(shè)計(jì)者必須深入思考的問(wèn)題。綜上所述，本文所設(shè)計(jì)的FFT處理器具有如下特點(diǎn)：

(1)支持16 M～4 M任意長(zhǎng)度輸入序列；

(2)支持二維FFT算法，對(duì)于緩存無(wú)法一次容納的輸入數(shù)據(jù)量，通過(guò)二維FFT算法完成運(yùn)算；

(3)對(duì)緩存的管理非常靈活，小點(diǎn)數(shù)情況下，輸入數(shù)據(jù)可以存放在緩存的任意位置，并且可以通過(guò)乒乓操作同時(shí)進(jìn)行多個(gè)輸入序列的計(jì)算，大點(diǎn)數(shù)情況下，可以通過(guò)乒乓操作將運(yùn)算時(shí)間隱藏入數(shù)據(jù)傳輸時(shí)間中；

(4)運(yùn)算精度高，通過(guò)對(duì)旋轉(zhuǎn)因子計(jì)算過(guò)程的優(yōu)化，信噪比可以達(dá)到130 dB以上。

1基8和二維FFT算法簡(jiǎn)述

首先，N點(diǎn)序列x(n)，其FFT定義為

(1)

本設(shè)計(jì)中，緩存為2 MB。對(duì)于長(zhǎng)度小于等于256 k的輸入序列，緩存可以一次容納，因此屬于小點(diǎn)數(shù)的范圍；對(duì)于長(zhǎng)度大于256 k的輸入序列，屬于大點(diǎn)數(shù)范圍，需要引入二維FFT算法進(jìn)行運(yùn)算。

對(duì)于小點(diǎn)數(shù)情況，本設(shè)計(jì)采用傳統(tǒng)的頻域抽取的基8算法，對(duì)于不滿足2n的點(diǎn)數(shù)，需要補(bǔ)零。

對(duì)于頻域抽取的基8算法[6-7]，將頻域X(k)的序號(hào)按除以8的余數(shù)分開(kāi)。按照式(1)，先將x(n)按序號(hào)分為8個(gè)部分，得

(2)

令R8(0)～R8(7)分別表示R8矩陣的第一行至第八行，這樣，上述八個(gè)表達(dá)式可簡(jiǎn)潔地表示為

(3)

根據(jù)式(3)，可以推導(dǎo)出頻域抽取的基8-FFT算法的蝶形運(yùn)算過(guò)程，如圖1所示。

圖1　頻域抽取的基8-FFT算法蝶形單元

對(duì)于大點(diǎn)數(shù)情況，本設(shè)計(jì)采用傳統(tǒng)常見(jiàn)的二維FFT算法[8]。設(shè)長(zhǎng)度為N的輸入序列x(n)，設(shè)置常量N1、N2，使得

(4)

其中

這樣，原始的FFT公式可以按照式(5)形式進(jìn)行變化

X(k)=X(k1+N1k2)=

(5)

根據(jù)對(duì)式(5)的理解，我們可以將初始的較長(zhǎng)的輸入序列劃分為一個(gè)矩陣，其行數(shù)和列數(shù)分別為N1和N2，如式(6)所示

(6)

將式(5)運(yùn)用到式(6)的矩陣上，可以分解為三步：

(1)對(duì)矩陣的每一列做FFT運(yùn)算；

(3)對(duì)矩陣的每一行做FFT運(yùn)算。

2運(yùn)算流程和狀態(tài)機(jī)設(shè)計(jì)

FFT處理器硬件實(shí)現(xiàn)的架構(gòu)如圖2所示。主要功能單元包括控制單元、地址單元、蝶形單元、旋轉(zhuǎn)因子生成單元、乘法單元等[9]?？刂茊卧捎脿顟B(tài)機(jī)實(shí)現(xiàn)，通過(guò)向其他功能模塊發(fā)送相應(yīng)的控制信號(hào)來(lái)控制整個(gè)運(yùn)算的流程。但是對(duì)于小點(diǎn)數(shù)和大點(diǎn)數(shù)兩種不同情形，運(yùn)算的流程也會(huì)有所不同，具體來(lái)講，可以對(duì)應(yīng)到控制單元中狀態(tài)機(jī)不同的狀態(tài)跳轉(zhuǎn)流程。

圖2　FFT處理器實(shí)現(xiàn)架構(gòu)

FFT處理器中，2 MB緩存被劃分成32個(gè)bank。通過(guò)這樣的劃分，控制單元可以通過(guò)與DMA單元的配合實(shí)現(xiàn)對(duì)緩存的靈活調(diào)度，從而完成乒乓操作[10]。對(duì)于小點(diǎn)數(shù)情形，運(yùn)算過(guò)程僅需占用其中的16個(gè)bank，當(dāng)數(shù)據(jù)從外部大容量存儲(chǔ)器搬入緩存單元的16個(gè)bank后，控制單元開(kāi)始啟動(dòng)運(yùn)算單元進(jìn)行運(yùn)算，在運(yùn)算的同時(shí)，控制另一組數(shù)據(jù)從外部大容量存儲(chǔ)器搬入緩存單元的另外16個(gè)bank，前一個(gè)運(yùn)算完成后，控制單元可以調(diào)度運(yùn)算單元直接進(jìn)入運(yùn)算過(guò)程，無(wú)需再等待數(shù)據(jù)的搬入，從而大幅提高了小點(diǎn)數(shù)情形的運(yùn)算速度。

對(duì)于大點(diǎn)數(shù)情形，由于緩存無(wú)法一次容納所有的數(shù)據(jù)，必須分段地進(jìn)行計(jì)算，這就產(chǎn)生了多次緩存與外部存儲(chǔ)器之間的數(shù)據(jù)交換過(guò)程，通過(guò)乒乓操作，同樣可以大幅提高大點(diǎn)數(shù)FFT的運(yùn)算性能。

為了實(shí)現(xiàn)完整的FFT運(yùn)算過(guò)程，并支持大點(diǎn)數(shù)情況下的二維FFT算法，控制單元的狀態(tài)設(shè)計(jì)機(jī)如圖3所示。

圖3　FFT處理器控制單元狀態(tài)轉(zhuǎn)移圖

對(duì)于小點(diǎn)數(shù)情形(以4 k點(diǎn)為例)，運(yùn)算流程和狀態(tài)跳轉(zhuǎn)如下：

(1)狀態(tài)機(jī)初始處于IDLE狀態(tài)，數(shù)據(jù)從外部大容量存儲(chǔ)器傳輸?shù)骄彺鎲卧?/p>

(2)運(yùn)算開(kāi)始，狀態(tài)跳轉(zhuǎn)至START(路徑1)；

(3)開(kāi)始第一級(jí)運(yùn)算，狀態(tài)跳轉(zhuǎn)至CAL(路徑2)，源數(shù)據(jù)從緩存單元流入蝶形單元進(jìn)行基8運(yùn)算，旋轉(zhuǎn)因子生成單元通過(guò)計(jì)算生成旋轉(zhuǎn)因子，蝶形單元計(jì)算結(jié)果與旋轉(zhuǎn)因子匯入乘法單元進(jìn)行相乘運(yùn)算，結(jié)果數(shù)據(jù)返回緩存單元；

(4)第一級(jí)運(yùn)算完成，狀態(tài)跳轉(zhuǎn)至BREAK(路徑4)；當(dāng)?shù)谝患?jí)的結(jié)果數(shù)據(jù)返回緩存單元后，進(jìn)入第二級(jí)運(yùn)算，狀態(tài)重新跳轉(zhuǎn)至CAL(路徑3)；

(5)相似地進(jìn)行第二、三、四級(jí)運(yùn)算(因?yàn)? k=84，共需要4級(jí)運(yùn)算)，狀態(tài)跳轉(zhuǎn)至BREAK(路徑4)，此時(shí)所有運(yùn)算結(jié)束，狀態(tài)跳轉(zhuǎn)至END(路徑7)；

(6)給出運(yùn)算完成的結(jié)束信號(hào)，狀態(tài)重新跳轉(zhuǎn)至IDLE(路徑8)，最終的運(yùn)算結(jié)果數(shù)據(jù)從緩存單元傳輸?shù)酵獠看笕萘看鎯?chǔ)器。

對(duì)于大點(diǎn)數(shù)情形(以4 M點(diǎn)為例)，運(yùn)算流程和狀態(tài)跳轉(zhuǎn)更為復(fù)雜[11]，如下：

(1)4M數(shù)據(jù)存在于外部大容量存儲(chǔ)器中，我們可將其視為一個(gè)1 k×4 k的源數(shù)據(jù)矩陣S；

(2)將矩陣S每一行的第0～127個(gè)數(shù)據(jù)搬入緩存單元，并在搬運(yùn)過(guò)程中，通過(guò)DMA單元使數(shù)據(jù)在緩存中排布成128個(gè)長(zhǎng)度為1 k的序列形式，在此過(guò)程中，共傳輸128 k數(shù)據(jù)量，剛好占滿緩存單元的第0～15個(gè)bank；

(4)類似于步驟(3)，完成剩余的127個(gè)長(zhǎng)度為1 k的序列的運(yùn)算，在運(yùn)算的同時(shí)，按照類似于步驟(2)的過(guò)程，將矩陣S每一行的第128～255個(gè)數(shù)據(jù)搬入緩存單元的第16～31個(gè)bank；

(5)當(dāng)運(yùn)算和數(shù)據(jù)傳輸完成后，控制單元直接開(kāi)始第16～31個(gè)bank中數(shù)據(jù)的運(yùn)算，同時(shí)，將第0～15個(gè)bank中的中間結(jié)果數(shù)據(jù)傳送至外部存儲(chǔ)器，并將矩陣S每一行的第256～383個(gè)數(shù)據(jù)搬入緩存單元的第0～15個(gè)bank；

(7)將矩陣M的前32行存入緩存單元，并在傳輸過(guò)程中，通過(guò)DMA單元使數(shù)據(jù)在緩存中排布成32個(gè)長(zhǎng)度為4 k的序列的形式，在此過(guò)程中，共傳輸128 k的數(shù)據(jù)量，剛好占滿緩存單元的第0～15個(gè)bank；

(8)按照小點(diǎn)數(shù)情形的運(yùn)算流程完成這32個(gè)4 k長(zhǎng)度的FFT運(yùn)算，在運(yùn)算的同時(shí)，按照類似于步驟(7)的過(guò)程，將矩陣M的第32～63行數(shù)據(jù)存入緩存單元的第16～31個(gè)bank；

(9)當(dāng)運(yùn)算和數(shù)據(jù)搬運(yùn)完成后，控制單元直接開(kāi)始第16～31個(gè)bank中數(shù)據(jù)的運(yùn)算，同時(shí)，將第0～15個(gè)bank中的中間結(jié)果數(shù)據(jù)傳送至外部存儲(chǔ)器，并將矩陣M的第64～95行數(shù)據(jù)存入緩存單元的第0～15個(gè)bank；

(10)將上述的步驟(8)至步驟(9)重復(fù)32次，這就完成了對(duì)矩陣M每一行的FFT運(yùn)算，得到了最終的4 M長(zhǎng)度序列的FFT結(jié)果。

通過(guò)上述設(shè)計(jì)，可以使同一個(gè)狀態(tài)機(jī)兼容小點(diǎn)數(shù)和大點(diǎn)數(shù)的運(yùn)算流程。另外，通過(guò)與DMA模塊的配合以及劃分為32 bank的緩存模塊設(shè)計(jì)，可以實(shí)現(xiàn)數(shù)據(jù)搬運(yùn)過(guò)程與計(jì)算過(guò)程的并行，提高了FFT處理器的性能，具體的性能提升分析將在第4節(jié)中詳述。

3旋轉(zhuǎn)因子的實(shí)時(shí)計(jì)算及優(yōu)化

出于節(jié)省運(yùn)算資源的考慮，本設(shè)計(jì)當(dāng)中采用單精度運(yùn)算單元，由此帶來(lái)的問(wèn)題是當(dāng)輸入序列的長(zhǎng)度較長(zhǎng)時(shí)，F(xiàn)FT的運(yùn)算精度就成為了一個(gè)無(wú)法忽視的問(wèn)題。而旋轉(zhuǎn)因子的精度對(duì)最終結(jié)果的精度有著很大的影響，這是由于存儲(chǔ)空間的限制，我們不可能將所有的旋轉(zhuǎn)因子預(yù)先計(jì)算完成并存儲(chǔ)下來(lái)。因此，旋轉(zhuǎn)因子的生成一般考慮預(yù)先存儲(chǔ)少量的常數(shù)，然后通過(guò)實(shí)時(shí)計(jì)算得到[12]。本設(shè)計(jì)對(duì)常數(shù)的選擇和實(shí)時(shí)計(jì)算的方法進(jìn)行了優(yōu)化，在消耗極為有限的存儲(chǔ)空間(16 kB)的情況下，大幅提高了最終結(jié)果的運(yùn)算精度，并同時(shí)兼容了不同輸入序列長(zhǎng)度的旋轉(zhuǎn)因子生成要求。

圖4是本設(shè)計(jì)所采用的旋轉(zhuǎn)因子生成單元結(jié)構(gòu)圖，其中，WSRAM_1和WSRAM_2用來(lái)存儲(chǔ)常數(shù)，每塊容量為8 kB，分別可以容納1 k個(gè)64 bit位寬的單精度復(fù)數(shù)。w_unit模塊用于實(shí)時(shí)計(jì)算旋轉(zhuǎn)因子，其主體為1個(gè)復(fù)數(shù)乘法器[13-14]，另外還包括一些地址生成邏輯和對(duì)稱性處理邏輯用來(lái)生成取數(shù)地址以及按照對(duì)稱性對(duì)計(jì)算結(jié)果做相應(yīng)的處理。

圖4　旋轉(zhuǎn)因子生成單元結(jié)構(gòu)圖

在此給出旋轉(zhuǎn)因子生成單元的整個(gè)工作流程：首先，w_unit根據(jù)當(dāng)前輸入序列的長(zhǎng)度生成相應(yīng)的取數(shù)地址序列，并按照該地址序列從兩個(gè)常數(shù)存儲(chǔ)器WSRAM_1和WSRAM_2中取出對(duì)應(yīng)的常數(shù)；然后，將這兩個(gè)常數(shù)傳回w_unit模塊并通過(guò)復(fù)數(shù)乘法器相乘，得出的乘積根據(jù)對(duì)稱性的需要進(jìn)行相應(yīng)的處理；最后，經(jīng)由w_unit模塊輸出得到旋轉(zhuǎn)因子序列。

表1　常數(shù)存儲(chǔ)器WSRAM_1和WSRAM_2中的數(shù)據(jù)存儲(chǔ)形式

在取數(shù)過(guò)程中，為了得到地址序列，需要將n參數(shù)和k參數(shù)相乘，在w_unit中可以通過(guò)對(duì)n參數(shù)的移位和加法操作得到結(jié)果。這里稱n參數(shù)和k參數(shù)的乘積為kn參數(shù)(需要22bit位寬表示)。對(duì)于不同的輸入序列長(zhǎng)度N，取數(shù)地址如表2所示。

表2　kn參數(shù)在不同輸入序列長(zhǎng)度N下對(duì)應(yīng)的取數(shù)地址

上述地址的產(chǎn)生依賴于FFT旋轉(zhuǎn)因子的一種屬性：旋轉(zhuǎn)因子具有很大的相關(guān)性，較小的輸入序列長(zhǎng)度所需的旋轉(zhuǎn)因子往往包含在較大輸入序列長(zhǎng)度所需的旋轉(zhuǎn)因子當(dāng)中。

4FFT運(yùn)算性能和精度分析

本設(shè)計(jì)使用Sysnopsis公司的VCS仿真工具，基于UVM驗(yàn)證方法學(xué)進(jìn)行了功能仿真，所有功能均順利通過(guò)。根據(jù)Design Compiler在TSMC_40nm工藝下綜合的結(jié)果，本設(shè)計(jì)可以運(yùn)行在1 GHz的頻率以上。

對(duì)于運(yùn)算性能的分析，本文使用周期數(shù)表示。對(duì)于任意2n點(diǎn)數(shù)，可以將其表示為2a×4b×8c形式，令其中的c盡可能大，則a和b最多有1個(gè)等于1或全為0。因此，該點(diǎn)數(shù)FFT運(yùn)算的級(jí)數(shù)即為a+b+c。每一級(jí)的運(yùn)算時(shí)間依賴于點(diǎn)數(shù)和運(yùn)算單元的數(shù)量，在本設(shè)計(jì)中，運(yùn)算單元的數(shù)量可以達(dá)到每周期2個(gè)數(shù)據(jù)的吞吐率，此時(shí)，每一級(jí)的運(yùn)算時(shí)間為2n-1個(gè)周期。狀態(tài)機(jī)每次BREAK狀態(tài)均會(huì)消耗128個(gè)周期，共消耗(a+b+c-1)×128個(gè)周期。另外，運(yùn)算的開(kāi)始和結(jié)束時(shí)也需消耗一定的周期(137個(gè))。因此，可以得到在2m條管線時(shí)完成2n點(diǎn)數(shù)的FFT所需的周期數(shù)為

T=137+(a+b+c-1)×128+

(a+b+c)×2n-1

(7)

但是上面的式(7)僅適用于小點(diǎn)數(shù)情況，對(duì)于大點(diǎn)數(shù)情況，運(yùn)算完成的時(shí)間很大程度上需要依賴于外部存儲(chǔ)器和緩存單元之間的數(shù)據(jù)搬運(yùn)時(shí)間。因?yàn)?，通過(guò)對(duì)存儲(chǔ)器的乒乓操作，計(jì)算時(shí)間可以掩蓋在數(shù)據(jù)搬運(yùn)時(shí)間當(dāng)中。表3根據(jù)理論推導(dǎo)和VCS仿真結(jié)果給出一些典型點(diǎn)數(shù)下的運(yùn)算周期數(shù)，512 k和1 M由于上述大點(diǎn)數(shù)的特殊性并沒(méi)有理論推導(dǎo)時(shí)間。

表3　1 k～1 M點(diǎn)數(shù)運(yùn)算時(shí)間

對(duì)于運(yùn)算精度的分析，本文采用matlab下雙精度運(yùn)算結(jié)果作為參考，較大點(diǎn)數(shù)下得到的信噪比如表4所示。

表4　本設(shè)計(jì)在各點(diǎn)數(shù)情況下的信噪比

5結(jié)束語(yǔ)

FFT是數(shù)字信號(hào)處理中非常重要的算法。本文設(shè)計(jì)了一種高精度并支持大點(diǎn)數(shù)二維算法的FFT處理器，可以自動(dòng)地完成小點(diǎn)數(shù)或大點(diǎn)數(shù)這2種情況下的整個(gè)FFT運(yùn)算流程，并且對(duì)旋轉(zhuǎn)因子的存儲(chǔ)和計(jì)算過(guò)程進(jìn)行了優(yōu)化，使最終結(jié)果獲得了130 dB以上的信噪比。

參 考 文 獻(xiàn)

[1]胡廣書(shū). 數(shù)字信號(hào)處理——理論、算法與實(shí)現(xiàn)[M]. 北京: 清華大學(xué)出版社, 1997.

HU Guangshu. Digital signal processing: theory, algorithm & implementation[M]. Beijing: Tsinghua University Press, 1997.

[2]王曉君, 龍騰, 周希元. 二維級(jí)聯(lián)流水結(jié)構(gòu)大點(diǎn)數(shù)FFT運(yùn)算器實(shí)現(xiàn)研究[J]. 無(wú)線電工程, 2010, 40(11): 19-22.

WANG Xiaojun, LONG Teng, ZHOU Xiyuan. Research on implementation of 2-dimension long FFT processor based on cascade-pipelined structure[J]. Radio Engineering, 2010, 40(11) : 19-22.

[3]林晗, 夏宇聞, 陳杰. 一種改進(jìn)型基-8 FFT算法及其ASIC實(shí)現(xiàn)[J]. 中國(guó)集成電路, 2003(9): 68-71.

LIN Han, XIA Yuwen, CHEN Jie. An improved radix-8 FFT algorithm and ASIC implementation[J]. China Integrated Circuit, 2003(9): 68-71.

[4]陶而芳. 浮點(diǎn)FFT處理器IP設(shè)計(jì)[D]. 成都: 西南交通大學(xué), 2008.

TAO Erfang. Design of float-point FFT processor IP[D]. Chengdu: Southwest Jiaotong University, 2008.

[5]陸波, 許煒陽(yáng), 胡星波, 等. 高吞吐率可配置FFT處理器IP核設(shè)計(jì)與VLSI實(shí)現(xiàn)[J]. 復(fù)旦學(xué)報(bào)(自然科學(xué)版), 2010, 49(2): 151-157.

LU Bo, XU Weiyang, HU Xingbo, et al. Design and VLSI implementation of IP core of high-throughput configurable FFT processor[J]. Journal of Fudan University(Natural Science) , 2010, 49(2): 151-157.

[6]賀衛(wèi)東, 段哲民, 龔誠(chéng). 基于FPGA的大點(diǎn)數(shù)FFT算法研究[J]. 電子測(cè)量技術(shù), 2007, 30(11): 14-16.

HE Weidong, DUAN Zhemin, GONG Cheng. 2D-parallel method for ultra long FFTs in FPGA[J]. Electronic Measurement Technology, 2007, 30(11): 14-16.

[7]蘇濤, 莊德靖.大點(diǎn)數(shù)FFT算法的改進(jìn)及其實(shí)現(xiàn)[J]. 現(xiàn)代雷達(dá), 2005, 27(7): 23-26.

SU Tao, ZHUANG Dejing. Improvement and implementation of FFT algorithm for long sequences[J]. Modern Radar, 2005, 27(7): 23-26.

[8]劉學(xué)梅, 孫志堅(jiān). 按頻率抽取的基4FFT算法在FPGA中實(shí)現(xiàn)[J]. 現(xiàn)代雷達(dá), 2005, 27(1): 50-51.

LIU Xuemei, SUN Zhijian. Algorithmic realization of the radix-4 DIF FFT in FPGA[J]. Modern Radar, 2005, 27(1): 50-51.

[9]COOLEY J W, TURKEY J W. An algorithm for the machine computation of complex Fourier series[J]. Mathematics of Computation, 1965, 19(4): 297-301.

[10]MA Y, WANHAMMAR L. A hardware efficient control of memory addressing for high-performance FFT processors[J]. IEEE Transactions on Signal Processing, 2000,48(3): 342-345.

[11]STEVENSON D. 754-1985-IEEE standard for binary floating-point arithmetic[J]. IEEE Journal, 1987(4): 345-348.

[12]SIDDAMAL S V, BANAKAR R M, JINAGA B C. Design of high-speed floating point multiplier[C]// 4th IEEE International Symposium on Electronic Design, Test & Applications. [S.l.]: IEEE Press, 2008: 285-289.

[13]HORIMA Y, ONOMI T, KOBORI M, et al. Improved design for parallel multiplier based on phase-mode logic[J]. IEEE Transactions on Applied Superconductivity, 2003, 13(2): 527-530.

[14]GEORGE K, CHEN C I. Configurable and expandable FFT processor for wideband communication[C]// IEEE Instrumentation and Measurement Technology Conference. [S.l.]: IEEE Press, 2007: 1-6.

于東男，1990年生，碩士研究生。研究方向?yàn)閂LSI設(shè)計(jì)。

韓峰男，1987年生，博士研究生。研究方向?yàn)閂LSI設(shè)計(jì)和高性能計(jì)算架構(gòu)。

李麗女，1975年生，教授，博士生導(dǎo)師。研究方向?yàn)閂LSI設(shè)計(jì)、數(shù)字信號(hào)處理系統(tǒng)、可重構(gòu)計(jì)算、多核SoC設(shè)計(jì)方法學(xué)。

A High-precision FFT Processor Supporting 2D FFT Algorithm

YU Dong，LI Li，HAN Feng, WANG Kun，F(xiàn)ENG Fan，PAN Hongbing

(College of Electronic Science and Engineering, Nanjing University,Nanjing 210046, China)

Abstract：Based on the traditional DIF FFT and 2D FFT algorithm, a high-precision FFT processor supporting various input data size is designed. In the procedure of FFT calculation, a finite state machine is used as a controller. When the input data size varies in a range, the cache can be smartly managed and 1D/2D FFT algorithm is automatically chosen according to the situation whether the amount of input data is beyond the cache size. Therefore the whole FFT calculation can be completed without any involvement of software but a start signal. Other than the support to 2D FFT algorithm in case the cache is not enough, an optimization in the calculation procedure of twiddle factor is introduced to improve its precision and furtherly to improve the precision of final results when facing a large input data size. In the FPGA verification, a 130 dB or higher SNR(signal-noise ratio) is reached while the SNR is only around 110 dB without this optimization.

Key words：FFT; 2D FFT algorithm; high precision; large data size; optimization about twiddle factor

DOI：10.16592/ j.cnki.1004-7859.2016.05.005

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61176024、61006018)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20120091110029)；江蘇省科技廳科技廳產(chǎn)學(xué)研聯(lián)合創(chuàng)新基金(BY2013072-05);江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目。

通信作者：于東Email：469889089@qq.com

收稿日期：2016-01-22

修訂日期：2016-03-21

中圖分類號(hào)：TN957

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1004-7859(2016)05-0016-06