一、引言

快速傅里葉變換（FFT）作為計算和分析工具，在信號處理、圖像處理、生物信息學、計算物理、應用數學等眾多學科領域有著廣泛的應用。在高速數字信號處理領域，如雷達信號處理，FFT的處理速度往往是整個系統設計性能的關鍵所在。針對高速實時信號處理的要求，傳統的軟件實現方法顯然無法滿足需求。近年來，現場可編程門陣列（FPGA）以其高性能、高靈活性、友好的開發環境、在線可編程等特點，使得基于FPGA的設計可以滿足實時數字信號處理的要求，在市場競爭中具有很大的優勢。

二、FFT算法原理

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

對于N=4γ，基-4 DIT具有log4N=γ次迭代運算，每次迭代包含N/4個蝶形單元。蝶形單元的運算表達式為：

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

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

三、FPGA選型與元器件功能

在基于FPGA的高速定點FFT算法設計中，選擇合適的FPGA器件至關重要。本文將詳細介紹FPGA選型過程，并闡述所選元器件的型號、作用、選擇原因及功能。

3.1 FPGA選型

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

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

3.2 元器件功能與電路框圖

3.2.1 FPGA（EP1S25）

型號：EP1S25

作用：作為整個FFT處理器的核心器件，負責實現FFT算法中的各種運算和控制邏輯。

選擇原因：

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

• 大容量存儲資源：該器件包含大量的存儲單元，可用于存儲旋轉因子和中間結果，提高FFT運算的效率。

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

• 開發環境友好：Altera公司提供了完善的開發環境和工具鏈，方便用戶進行FPGA設計和仿真。

功能：

• 實現FFT算法中的蝶形運算、旋轉因子乘法等運算。

• 協調控制各個模塊之間的數據傳輸和時序關系。

• 提供與外部設備的接口，實現數據的輸入和輸出。

電路框圖：

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

|      FPGA       |

|  (EP1S25)       |

|                 |

|  蝶形運算單元   |

|  旋轉因子單元   |

|  控制單元       |

|  數據控制單元   |

|  存儲器接口     |

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

3.2.2 存儲器（RAM和ROM）

型號：根據設計需求定制

作用：用于存儲輸入數據、中間結果和旋轉因子等。

選擇原因：

• 大容量：需要足夠大的存儲容量來存儲64點FFT運算所需的輸入數據、中間結果和旋轉因子。

• 高速訪問：存儲器需要具有高速訪問能力，以滿足FFT運算對數據處理速度的要求。

• 雙端口設計：為了方便數據的讀寫操作，存儲器采用雙端口設計，允許同時進行讀和寫操作。

功能：

• 輸入RAM：用于存儲外部輸入的64點復數數據。

• 中間結果RAM：用于存儲FFT運算過程中產生的中間結果。

• 旋轉因子ROM：用于存儲FFT運算所需的旋轉因子。旋轉因子是預先計算好的固定值，存儲在ROM中可以節省FPGA的邏輯資源。

電路框圖：

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

|  輸入RAM    |-------| 中間結果RAM |-------| 旋轉因子ROM |

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

3.2.3 蝶形運算單元

型號：自定義設計

作用：實現FFT算法中的蝶形運算。

選擇原因：

• 高效性：蝶形運算單元是FFT處理器的核心部件，其設計需要高效性，以減少運算時間和資源消耗。

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

功能：

• 實現基-4蝶形運算公式中的復乘和復加運算。

• 支持并行輸入和輸出數據，提高運算速度。

電路框圖：

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

|  蝶形運算單元   |

|                 |

|  復乘器1        |

|  復乘器2        |

|  復加器1        |

|  復加器2        |

|  復加器3        |

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

3.2.4 旋轉因子單元

型號：自定義設計（基于ROM實現）

作用：提供FFT運算所需的旋轉因子。

選擇原因：

• 節省資源：旋轉因子是預先計算好的固定值，存儲在ROM中可以節省FPGA的邏輯資源。

• 高速訪問：ROM具有高速訪問能力，可以滿足FFT運算對旋轉因子的快速訪問需求。

功能：

• 存儲FFT運算所需的旋轉因子。

• 根據控制單元提供的地址信號，輸出相應的旋轉因子給蝶形運算單元。

電路框圖：

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

|  旋轉因子單元   |

|                 |

|  ROM            |

|  地址譯碼器     |

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

3.2.5 控制單元

型號：自定義設計（基于有限狀態機實現）

作用：協調控制各個模塊之間的數據傳輸和時序關系。

選擇原因：

• 靈活性：有限狀態機具有高度的靈活性，可以根據FFT運算的需求動態調整控制邏輯。

• 可靠性：有限狀態機設計簡單、易于調試，能夠提高FFT處理器的可靠性。

功能：

• 產生控制信號，協調各個模塊之間的工作。

• 控制數據的輸入、輸出和存儲過程。

• 監控FFT運算的狀態，確保運算的正確性。

電路框圖：

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

|   控制單元      |

|                 |

|  有限狀態機     |

|  計數器         |

|  比較器         |

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

3.2.6 數據控制單元

型號：自定義設計

作用：負責數據的輸入輸出控制，以及數據格式的轉換和處理。

選擇原因：

• 靈活性：數據控制單元需要根據FFT運算的需求靈活調整數據輸入輸出方式。

• 高效性：數據控制單元需要高效處理數據，以減少FFT運算的延遲。

功能：

• 控制數據的輸入輸出時序。

• 對輸入數據進行預處理，如格式轉換、定點化等。

• 對輸出數據進行后處理，如格式轉換、溢出判斷等。

電路框圖：

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

|  數據控制單元   |

|                 |

|  數據輸入接口   |

|  數據輸出接口   |

|  數據格式轉換器 |

|  溢出判斷器     |

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

四、設計方案詳述

4.1 流水線方式FFT算法的實現

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

4.2 存儲單元設計

為了實現算法的流水線設計，存儲器RAM設計為雙端口RAM，即在時鐘信號和寫控制信號同時為低電平時，從輸入總線寫入RAM；在時鐘信號和讀控制信號同時為高電平時，從RAM輸出數據。ROM用于儲存經過量化后的旋轉因子，旋轉因子為正弦函數和余弦函數的組合。根據旋轉因子的對稱性和周期性，在利用ROM存儲旋轉因子時，可以只存儲旋轉因子的一部分，通過地址的改變查詢出每級蝶形運算所需的旋轉因子。

4.3 運算結構設計

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

4.4 塊浮點結構設計

數字信號處理系統可分為定點制、浮點制和塊浮點制。定點制算法簡單、速度快，但動態范圍有限；浮點表示法動態范圍大，可避免溢出，但系統實現復雜、硬件需求量大、速度慢。為了提高精度并減少復雜度和存儲量，采用塊浮點結構。塊浮點算法是定點制和浮點制的結合，一組數共用同一個階碼，這個階碼是這組數中最大數的階碼。在調整時僅保留一位符號位，因而能夠充分利用有限位長。這樣處理比定點方法擴大了動態范圍，并且提高了精度，比浮點運算在速度上有了提高。

五、綜合仿真與驗證

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

六、結論與展望

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

未來工作可以進一步優化FPGA資源的使用效率，提高FFT處理器的性能。同時，還可以探索將FFT算法應用于更多領域，如實時圖像處理、無線通信等，以發揮FPGA在高速數字信號處理領域的優勢。