一、引言

快速傅里葉變換（FFT）作為計(jì)算和分析工具，在信號(hào)處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等眾多學(xué)科領(lǐng)域有著廣泛的應(yīng)用。在高速數(shù)字信號(hào)處理領(lǐng)域，如雷達(dá)信號(hào)處理，F(xiàn)FT的處理速度往往是整個(gè)系統(tǒng)設(shè)計(jì)性能的關(guān)鍵所在。針對(duì)高速實(shí)時(shí)信號(hào)處理的要求，傳統(tǒng)的軟件實(shí)現(xiàn)方法顯然無(wú)法滿足需求。近年來(lái)，現(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）以其高性能、高靈活性、友好的開(kāi)發(fā)環(huán)境、在線可編程等特點(diǎn)，使得基于FPGA的設(shè)計(jì)可以滿足實(shí)時(shí)數(shù)字信號(hào)處理的要求，在市場(chǎng)競(jìng)爭(zhēng)中具有很大的優(yōu)勢(shì)。

二、FFT算法原理

FFT算法的基本思想是利用權(quán)函數(shù)的周期性、對(duì)稱性、特殊性及周期N的可互換性，將較長(zhǎng)序列的DFT（離散傅里葉變換）運(yùn)算逐次分解為較短序列的DFT運(yùn)算。針對(duì)N=2的整數(shù)次冪，F(xiàn)FT算法有基-2算法、基-4算法、實(shí)因子算法和分裂基算法等。從處理速度和占用資源的角度考慮，本文選用基-4按時(shí)間抽取FFT算法（DIT）。

對(duì)于N=4γ，基-4 DIT具有l(wèi)og4N=γ次迭代運(yùn)算，每次迭代包含N/4個(gè)蝶形單元。蝶形單元的運(yùn)算表達(dá)式為：

A′ = A + B × W
B′ = A - B × W
C′ = C + D × W
D′ = C - D × W

其中，A, B, C, D和A′, B′, C′, D′均為復(fù)數(shù)據(jù)；W=e-j2π/N。進(jìn)行1次蝶形運(yùn)算共需3次復(fù)乘和8次復(fù)加運(yùn)算。以64點(diǎn)數(shù)據(jù)為例，只需進(jìn)行3次迭代運(yùn)算，每次迭代運(yùn)算含有N/4=16個(gè)蝶形單元。

三、FPGA選型與元器件功能

在基于FPGA的高速定點(diǎn)FFT算法設(shè)計(jì)中，選擇合適的FPGA器件至關(guān)重要。本文將詳細(xì)介紹FPGA選型過(guò)程，并闡述所選元器件的型號(hào)、作用、選擇原因及功能。

3.1 FPGA選型

在FPGA選型時(shí)，需要綜合考慮多個(gè)因素，包括邏輯資源、I/O資源、布線資源、DSP資源、存儲(chǔ)器資源、鎖相環(huán)資源、串行收發(fā)器資源和硬核微處理器資源等。同時(shí)，還需要考慮器件的功耗、性能、成本、供貨穩(wěn)定性以及開(kāi)發(fā)工具的兼容性等。

針對(duì)高速定點(diǎn)FFT算法的設(shè)計(jì)需求，本文選擇Altera公司的Stratix系列EP1S25型FPGA作為核心器件。該器件具有高性能體系、大容量存儲(chǔ)資源、高帶寬DSP模塊等特點(diǎn)，能夠滿足高速定點(diǎn)FFT算法對(duì)處理速度和資源的需求。

3.2 元器件功能與電路框圖

3.2.1 FPGA（EP1S25）

型號(hào)：EP1S25

作用：作為整個(gè)FFT處理器的核心器件，負(fù)責(zé)實(shí)現(xiàn)FFT算法中的各種運(yùn)算和控制邏輯。

選擇原因：

• 高性能：EP1S25具有高性能體系，能夠滿足高速定點(diǎn)FFT算法對(duì)處理速度的要求。

• 大容量存儲(chǔ)資源：該器件包含大量的存儲(chǔ)單元，可用于存儲(chǔ)旋轉(zhuǎn)因子和中間結(jié)果，提高FFT運(yùn)算的效率。

• 高帶寬DSP模塊：EP1S25內(nèi)置了高帶寬DSP模塊，能夠完成較為耗費(fèi)資源的乘法器單元功能，提高FFT運(yùn)算的精度和速度。

• 開(kāi)發(fā)環(huán)境友好：Altera公司提供了完善的開(kāi)發(fā)環(huán)境和工具鏈，方便用戶進(jìn)行FPGA設(shè)計(jì)和仿真。

功能：

• 實(shí)現(xiàn)FFT算法中的蝶形運(yùn)算、旋轉(zhuǎn)因子乘法等運(yùn)算。

• 協(xié)調(diào)控制各個(gè)模塊之間的數(shù)據(jù)傳輸和時(shí)序關(guān)系。

• 提供與外部設(shè)備的接口，實(shí)現(xiàn)數(shù)據(jù)的輸入和輸出。

電路框圖：

+-----------------+

|      FPGA       |

|  (EP1S25)       |

|                 |

|  蝶形運(yùn)算單元   |

|  旋轉(zhuǎn)因子單元   |

|  控制單元       |

|  數(shù)據(jù)控制單元   |

|  存儲(chǔ)器接口     |

+-----------------+

3.2.2 存儲(chǔ)器（RAM和ROM）

型號(hào)：根據(jù)設(shè)計(jì)需求定制

作用：用于存儲(chǔ)輸入數(shù)據(jù)、中間結(jié)果和旋轉(zhuǎn)因子等。

選擇原因：

• 大容量：需要足夠大的存儲(chǔ)容量來(lái)存儲(chǔ)64點(diǎn)FFT運(yùn)算所需的輸入數(shù)據(jù)、中間結(jié)果和旋轉(zhuǎn)因子。

• 高速訪問(wèn)：存儲(chǔ)器需要具有高速訪問(wèn)能力，以滿足FFT運(yùn)算對(duì)數(shù)據(jù)處理速度的要求。

• 雙端口設(shè)計(jì)：為了方便數(shù)據(jù)的讀寫(xiě)操作，存儲(chǔ)器采用雙端口設(shè)計(jì)，允許同時(shí)進(jìn)行讀和寫(xiě)操作。

功能：

• 輸入RAM：用于存儲(chǔ)外部輸入的64點(diǎn)復(fù)數(shù)數(shù)據(jù)。

• 中間結(jié)果RAM：用于存儲(chǔ)FFT運(yùn)算過(guò)程中產(chǎn)生的中間結(jié)果。

• 旋轉(zhuǎn)因子ROM：用于存儲(chǔ)FFT運(yùn)算所需的旋轉(zhuǎn)因子。旋轉(zhuǎn)因子是預(yù)先計(jì)算好的固定值，存儲(chǔ)在ROM中可以節(jié)省FPGA的邏輯資源。

電路框圖：

+-------------+       +-------------+       +-------------+

|  輸入RAM    |-------| 中間結(jié)果RAM |-------| 旋轉(zhuǎn)因子ROM |

+-------------+       +-------------+       +-------------+

3.2.3 蝶形運(yùn)算單元

型號(hào)：自定義設(shè)計(jì)

作用：實(shí)現(xiàn)FFT算法中的蝶形運(yùn)算。

選擇原因：

• 高效性：蝶形運(yùn)算單元是FFT處理器的核心部件，其設(shè)計(jì)需要高效性，以減少運(yùn)算時(shí)間和資源消耗。

• 并行性：為了提高FFT運(yùn)算的速度，蝶形運(yùn)算單元需要支持并行運(yùn)算。

功能：

• 實(shí)現(xiàn)基-4蝶形運(yùn)算公式中的復(fù)乘和復(fù)加運(yùn)算。

• 支持并行輸入和輸出數(shù)據(jù)，提高運(yùn)算速度。

電路框圖：

+-----------------+

|  蝶形運(yùn)算單元   |

|                 |

|  復(fù)乘器1        |

|  復(fù)乘器2        |

|  復(fù)加器1        |

|  復(fù)加器2        |

|  復(fù)加器3        |

+-----------------+

3.2.4 旋轉(zhuǎn)因子單元

型號(hào)：自定義設(shè)計(jì)（基于ROM實(shí)現(xiàn)）

作用：提供FFT運(yùn)算所需的旋轉(zhuǎn)因子。

選擇原因：

• 節(jié)省資源：旋轉(zhuǎn)因子是預(yù)先計(jì)算好的固定值，存儲(chǔ)在ROM中可以節(jié)省FPGA的邏輯資源。

• 高速訪問(wèn)：ROM具有高速訪問(wèn)能力，可以滿足FFT運(yùn)算對(duì)旋轉(zhuǎn)因子的快速訪問(wèn)需求。

功能：

• 存儲(chǔ)FFT運(yùn)算所需的旋轉(zhuǎn)因子。

• 根據(jù)控制單元提供的地址信號(hào)，輸出相應(yīng)的旋轉(zhuǎn)因子給蝶形運(yùn)算單元。

電路框圖：

+-----------------+

|  旋轉(zhuǎn)因子單元   |

|                 |

|  ROM            |

|  地址譯碼器     |

+-----------------+

3.2.5 控制單元

型號(hào)：自定義設(shè)計(jì)（基于有限狀態(tài)機(jī)實(shí)現(xiàn)）

作用：協(xié)調(diào)控制各個(gè)模塊之間的數(shù)據(jù)傳輸和時(shí)序關(guān)系。

選擇原因：

• 靈活性：有限狀態(tài)機(jī)具有高度的靈活性，可以根據(jù)FFT運(yùn)算的需求動(dòng)態(tài)調(diào)整控制邏輯。

• 可靠性：有限狀態(tài)機(jī)設(shè)計(jì)簡(jiǎn)單、易于調(diào)試，能夠提高FFT處理器的可靠性。

功能：

• 產(chǎn)生控制信號(hào)，協(xié)調(diào)各個(gè)模塊之間的工作。

• 控制數(shù)據(jù)的輸入、輸出和存儲(chǔ)過(guò)程。

• 監(jiān)控FFT運(yùn)算的狀態(tài)，確保運(yùn)算的正確性。

電路框圖：

+-----------------+

|   控制單元      |

|                 |

|  有限狀態(tài)機(jī)     |

|  計(jì)數(shù)器         |

|  比較器         |

+-----------------+

3.2.6 數(shù)據(jù)控制單元

型號(hào)：自定義設(shè)計(jì)

作用：負(fù)責(zé)數(shù)據(jù)的輸入輸出控制，以及數(shù)據(jù)格式的轉(zhuǎn)換和處理。

選擇原因：

• 靈活性：數(shù)據(jù)控制單元需要根據(jù)FFT運(yùn)算的需求靈活調(diào)整數(shù)據(jù)輸入輸出方式。

• 高效性：數(shù)據(jù)控制單元需要高效處理數(shù)據(jù)，以減少FFT運(yùn)算的延遲。

功能：

• 控制數(shù)據(jù)的輸入輸出時(shí)序。

• 對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，如格式轉(zhuǎn)換、定點(diǎn)化等。

• 對(duì)輸出數(shù)據(jù)進(jìn)行后處理，如格式轉(zhuǎn)換、溢出判斷等。

電路框圖：

+-----------------+

|  數(shù)據(jù)控制單元   |

|                 |

|  數(shù)據(jù)輸入接口   |

|  數(shù)據(jù)輸出接口   |

|  數(shù)據(jù)格式轉(zhuǎn)換器 |

|  溢出判斷器     |

+-----------------+

四、設(shè)計(jì)方案詳述

4.1 流水線方式FFT算法的實(shí)現(xiàn)

為了提高FFT工作頻率和節(jié)省FPGA資源，采用流水線結(jié)構(gòu)實(shí)現(xiàn)64點(diǎn)的FFT運(yùn)算。流水線處理器的結(jié)構(gòu)由多級(jí)組成，每級(jí)均由延時(shí)單元、轉(zhuǎn)接器（SW）、蝶形運(yùn)算和旋轉(zhuǎn)因子乘法4個(gè)模塊組成。延時(shí)節(jié)拍由方框中的數(shù)字表示。各級(jí)轉(zhuǎn)接器和延時(shí)單元起到對(duì)序列進(jìn)行碼位抽取并將數(shù)據(jù)拉齊的作用。每級(jí)延時(shí)在FPGA內(nèi)部用FIFO實(shí)現(xiàn)，不需要對(duì)序列進(jìn)行尋址即可實(shí)現(xiàn)延時(shí)功能。數(shù)據(jù)串行輸入，經(jīng)過(guò)多級(jí)流水處理后，串行輸出。

4.2 存儲(chǔ)單元設(shè)計(jì)

為了實(shí)現(xiàn)算法的流水線設(shè)計(jì)，存儲(chǔ)器RAM設(shè)計(jì)為雙端口RAM，即在時(shí)鐘信號(hào)和寫(xiě)控制信號(hào)同時(shí)為低電平時(shí)，從輸入總線寫(xiě)入RAM；在時(shí)鐘信號(hào)和讀控制信號(hào)同時(shí)為高電平時(shí)，從RAM輸出數(shù)據(jù)。ROM用于儲(chǔ)存經(jīng)過(guò)量化后的旋轉(zhuǎn)因子，旋轉(zhuǎn)因子為正弦函數(shù)和余弦函數(shù)的組合。根據(jù)旋轉(zhuǎn)因子的對(duì)稱性和周期性，在利用ROM存儲(chǔ)旋轉(zhuǎn)因子時(shí)，可以只存儲(chǔ)旋轉(zhuǎn)因子的一部分，通過(guò)地址的改變查詢出每級(jí)蝶形運(yùn)算所需的旋轉(zhuǎn)因子。

4.3 運(yùn)算結(jié)構(gòu)設(shè)計(jì)

Radix-4蝶形運(yùn)算單元是整個(gè)FFT處理器中的核心部件。在用Radix-4運(yùn)算器計(jì)算時(shí)需要并行輸入數(shù)據(jù)，如果能以并發(fā)數(shù)據(jù)輸入的話，則同步性和控制度較好。存儲(chǔ)RAM按單節(jié)拍輸出數(shù)據(jù)，選擇器不停旋轉(zhuǎn)送入到確定的位置，每4點(diǎn)全部到位后R-4使能有效；然后4個(gè)時(shí)鐘節(jié)拍得到有效結(jié)果數(shù)據(jù)，再通過(guò)選擇器旋轉(zhuǎn)送入到對(duì)應(yīng)存儲(chǔ)RAM中。復(fù)數(shù)運(yùn)算中，對(duì)應(yīng)復(fù)數(shù)的實(shí)部和虛部RAM用同一個(gè)地址發(fā)生器。地址發(fā)生器在進(jìn)行RAM地址發(fā)生時(shí)采用兩套地址，第一套是計(jì)數(shù)器按時(shí)鐘節(jié)拍順序產(chǎn)生的，用于輸入數(shù)據(jù)的存儲(chǔ)；第二套是由數(shù)據(jù)寬度為16b的ROM產(chǎn)生的，ROM中存放的數(shù)據(jù)為下級(jí)運(yùn)算所需倒序的序列地址，發(fā)生地址給RAM，然后RAM按倒序地址輸出下級(jí)需要進(jìn)行運(yùn)算的數(shù)據(jù)。

4.4 塊浮點(diǎn)結(jié)構(gòu)設(shè)計(jì)

數(shù)字信號(hào)處理系統(tǒng)可分為定點(diǎn)制、浮點(diǎn)制和塊浮點(diǎn)制。定點(diǎn)制算法簡(jiǎn)單、速度快，但動(dòng)態(tài)范圍有限；浮點(diǎn)表示法動(dòng)態(tài)范圍大，可避免溢出，但系統(tǒng)實(shí)現(xiàn)復(fù)雜、硬件需求量大、速度慢。為了提高精度并減少?gòu)?fù)雜度和存儲(chǔ)量，采用塊浮點(diǎn)結(jié)構(gòu)。塊浮點(diǎn)算法是定點(diǎn)制和浮點(diǎn)制的結(jié)合，一組數(shù)共用同一個(gè)階碼，這個(gè)階碼是這組數(shù)中最大數(shù)的階碼。在調(diào)整時(shí)僅保留一位符號(hào)位，因而能夠充分利用有限位長(zhǎng)。這樣處理比定點(diǎn)方法擴(kuò)大了動(dòng)態(tài)范圍，并且提高了精度，比浮點(diǎn)運(yùn)算在速度上有了提高。

五、綜合仿真與驗(yàn)證

選用Altera公司的QuartusⅡ軟件作為開(kāi)發(fā)平臺(tái)，以Stratix系列中的EP1S25型FPGA為器件，采用自頂向下的設(shè)計(jì)思路和VHDL語(yǔ)言，實(shí)現(xiàn)對(duì)各個(gè)模塊單元的設(shè)計(jì)、綜合和仿真。為了簡(jiǎn)化設(shè)計(jì)，只在數(shù)據(jù)輸入時(shí)鐘下輸入了一組64個(gè)復(fù)數(shù)，其余輸入設(shè)為0，并且實(shí)部和虛部都限定在一定范圍內(nèi)。為防止溢出先將輸入數(shù)據(jù)乘以一定比例因子，再轉(zhuǎn)化為十六進(jìn)制數(shù)。輸出的結(jié)果需要乘以相應(yīng)的比例因子才是實(shí)際結(jié)果。將仿真結(jié)果與Matlab計(jì)算的結(jié)果相比較，數(shù)據(jù)基本一致，說(shuō)明了設(shè)計(jì)正確。其誤差主要來(lái)源于數(shù)據(jù)的截取和旋轉(zhuǎn)因子的近似。

六、結(jié)論與展望

本文著重討論了基于FPGA的64點(diǎn)高速定點(diǎn)FFT算法的實(shí)現(xiàn)方法。采用高基數(shù)結(jié)構(gòu)和流水線結(jié)構(gòu)，大大提高了FFT處理器的運(yùn)行速度。同時(shí)塊浮點(diǎn)結(jié)構(gòu)的引入也大幅減少了浮點(diǎn)操作占用FPGA器件的資源數(shù)目，兼顧了FPGA高精度、低資源、低功耗的特點(diǎn)。從實(shí)驗(yàn)結(jié)果看，該方法可以滿足高速實(shí)時(shí)處理數(shù)字信號(hào)的要求。

未來(lái)工作可以進(jìn)一步優(yōu)化FPGA資源的使用效率，提高FFT處理器的性能。同時(shí)，還可以探索將FFT算法應(yīng)用于更多領(lǐng)域，如實(shí)時(shí)圖像處理、無(wú)線通信等，以發(fā)揮FPGA在高速數(shù)字信號(hào)處理領(lǐng)域的優(yōu)勢(shì)。