一種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法

2023-05-16 03:28:36

一種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法
【專利摘要】本發明屬於數位訊號處理【技術領域】，尤其涉及在超高速採樣率下利用可編程邏輯器件，對採樣數據進行極低延遲的快速傅立葉變換運算(Fast?Fourier?Transform，FFT)。本發明是一種在可編程邏輯器件上實現快速傅立葉變換的方法，通過一定規則，將高速的採樣數據並行輸入傅立葉變換模塊中，按照規則安排數據後，在並行的基礎上復用硬體資源減小資源的佔用。本發明相對於傳統方法，能滿足數據速率高，處理延遲低的需求。
【專利說明】一種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法

【技術領域】
[0001] 本發明屬於數位訊號處理【技術領域】，尤其涉及在超高速採樣率下利用可編程邏輯 器件，對採樣數據進行極低延遲的快速傅立葉變換運算（Fast Fourier Transform, FFT)。

【背景技術】
[0002] 數位訊號處理系統以其可靠、廉價和精度高等優點在近幾十年得到了迅猛的發 展，被用於幾乎各個工程領域。在數位訊號處理中，一種經常遇到的運算是離散時間傅立葉 變換（Discrete Fourier Transform，DFT)。直接計算DFT會導致很高的運算複雜度，若輸 入信號的點數為N，則直接計算DFT需要N2次複數乘法和N 2-N次複數加法。當點數較大時 這是難以接受的。
[0003] 1965年，Cooley和Tukey提出了一種降低DFT運算量的計算方法即快速傅立葉 變換（Fast Fourier Transform，FFT)。利用FFT計算時，若輸入信號的點數為N，則需要 4-l〇g2(..V)次複數乘法和Ν ·1(^2 (N)次複數加法。隨著N的增加FFT的運算量只比線性增長 快一些。相比於直接結算DFT，FFT的運算量大大降低。所以實際應用中都採用FFT的方法 來實現DFT的計算。
[0004] 在具體實現FFT時，需要綜合考慮各種因素，比如輸入數據的速率、對處理延時的 要求、對資源佔用的要求等。目前，FPGA廠家提供的成熟的FFT的IP核有兩類結構。第 一類是只使用一個蝶形運算單元，通過控制時序達到在時間上復用這個蝶形運算單元的效 果。第二類是流水線技術，使用多個串行排列的蝶形運算，數據也是串行輸入的。分析這個 兩類結構，第一類結構佔用很少的資源，但系統的處理延遲是很高的，而且輸入數據率不會 太高。第二類結構採用流水線技術，能降低處理延遲，但由於蝶形運算是串行的，所以處理 延遲不能降到極低，另外輸入數據速率同樣不會太高。某廠家提供的IP核計算256點FFT， 若採用第一類結構，處理延遲約2000個FPGA工作時鐘周期，採用第二類結構處理延遲約 700個FPGA工作時鐘周期。這能滿足普通的計算FFT的需求。
[0005] 但是，在實際中有另一類計算FFT的需求，這類需求的採樣速率非常高。比如每秒 數吉赫茲個採樣樣本（Gigabit Samples Per Second, GSPS)，同時要求計算FFT的處理延 遲極低。這種需求採用前面所述普通的FFT實現結構不再合適。普通的流水串行結構或者 時分復用結構處理不了這麼高的輸入速率，處理延遲也不能做到極低。


【發明內容】

[0006] 本發明針對現有的普通FFT實現結構的缺陷，提出了一種數吉赫茲採樣率下的極 低延遲快速傅立葉變換方法，該方法能夠滿足數據速率高，處理延遲低這兩個普通FFT無 法滿足的需求。
[0007] -種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法，具體如下：
[0008] S1、採用並行輸入方式輸入採樣數據：記需要進行FFT的點數為N = 21 · 2M，記輸 入的數據速率為Fs，則經過並行輸入後邏輯器件的工作頻率降為F s/2S其中，f表示並行輸 入的通道數目，所述f的值由採樣設備確定，2M表示並行輸入全部數據所需要的時鐘周期；
[0009] S2、確定樣點數據與各個並行通道的映射關係：將並行輸入通道編號為Chx，N點 FFT中的第η個數據被映射到第X個通道Chx上，映射關係式為n = x+m· 2S其中，η表 示Ν點FFT的第η個數據，X表示第X個輸入通道，m表示輸入開始後的第m個時鐘周期， 0 彡 m 彡 2M-1，0 彡 X 彡 2L-1 ;
[0010] S3、經過S1和S2的處理，S1所述FFT按照基2抽取了 Μ次，得出需要2"個2M點 的DFT模塊，每個DFT模塊的輸入數據對應一個S2所述並行輸入通道Chx中的所有數據， 每個DFT模塊的數據按照時鐘串行進入，通過控制時序復用資源；
[0011] S4、當S3所述^個DFT模塊輸出後，根據FFT抽取的次數Μ完成後續Μ次蝶形運 算。
[0012] 進一步地，S3所述f個DFT模塊是並行的，所述f個DFT模塊相互之間硬體獨立。
[0013] 本發明的有益效果是：
[0014] 本發明將FFT結構並行化，提高處理的數據率，同時大大降低了 FFT的處理延遲時 間。

【專利附圖】

【附圖說明】
[0015] 圖1是256點FFT模塊的數據並行輸入示意圖。
[0016] 圖2是256點FFT按基2抽取4次後的運算結構圖。
[0017] 圖3是16點DFT運算關係及實現結構。
[0018] 圖4是256點FFT最終實現結構圖。

【具體實施方式】
[0019] 下面結合實施例和附圖，詳細說明本發明的技術方案。
[0020] -種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法，具體如下：
[0021] S1、採用並行輸入方式輸入採樣數據：記需要進行FFT的點數為Ν = ^ · 2M。在 FFT中N-定是2的冪次，有N = 2lX2M，其中，表示並行輸入的通道數目，的值由採樣 設備確定，2M表示並行輸入全部數據所需要的時鐘周期。記輸入的數據速率為匕，則經過並 行輸入後邏輯器件的工作頻率降為F s/2l。這樣的並行輸入使得整個FFT模塊能處理超高 速的採樣數據。
[0022] S2、確定樣點數據與各個並行通道的映射關係：將並行輸入通道編號為Chx，其 中，0彡X彡2 1-1。N點FFT中的第η個數據被映射到第X個通道Chx上，映射關係式如下 n = x+m · ，其中η表示N點FFT的第η個數據，X表示第X個輸入通道，m表示輸入開始 後的第m個時鐘周期，0 < m < 2m-1。
[0023] S3、經過S1和S2的處理FFT按照基2抽取了 Μ次，得出需要個2M點的DFT模 塊，每個DFT模塊的輸入數據對應一個S2所述並行輸入通道Chx中的所有數據。每個DFT 模塊的數據按照時鐘串行進入，通過控制時序復用資源，所述ffDFT模塊是並行的，相互 之間硬體獨立。由於一個通道中的所有數據是串行輸入的，所以在計算2 M點的DFT時，復 用所需要的蝶形單元。
[0024] S4、當S3所述f個DFT模塊輸出後，根據FFT抽取的次數Μ完成後續Μ次蝶形運 算。通過控制各個DFT模塊的輸出時序，可以復用後續Μ次的蝶形運算單元，使得各個點數 的蝶形運算單元只需要1個，大大節省資源，同時不會造成時延過大。
[0025] 在Xilinx公司的xc7vx485t-lffgll57上實現256點的FFT。採樣數據的速率是 2. 4GSPS，FFT計算模塊的工作時鐘是150Mhz，採樣數據以16路並行輸入到FFT模塊，256個 採樣點完全輸入需要16個時鐘周期。數據並行輸入結構如圖1所示。
[0026] 由於FFT的256點數據是通過並行16路經過16個時鐘周期輸入的，所以FFT按 照基2抽取4次，這樣就會有16個DFT。為了更加詳細看到這一點，圖2展示了 256點FFT 按基2抽取4次後的運算結構圖。觀察這16個DFT可以看到，每一個16點DFT的輸入數 據剛好對應1個輸入通道中的數據。比如第一個16點DFT的輸入數據是ChO輸入通道的 數據。
[0027] 16點的DFT也是由蝶形運算實現。但是由於16點DFT的輸入數據是按照時鐘串 行輸入的，因此可復用蝶形運算單元。一個16點DFT模塊包含1個2點蝶形運算、1個4點 蝶形運算、1個8點蝶形運算、1個16點蝶形運算。這種實現方式利用數據的串行輸入特點 復用蝶形運算單元，大大減小資源的佔用。16點DFT模塊實現的結構參見圖3。
[0028] 由於16點DFT的輸出是獨立的，所以通過控制時序，使得後續的32點、64點、128 點和256點蝶形運算單元可以復用，節省資源的同時不會造成時延增大的太多。最終的實 現結構如圖4所示。
[0029] 本實施例佔用的05?48小於30%，邏輯小於20%。輸入的數據速率為2.465卩5。 從第一個數據進入開始到256點FFT計算結果全部輸出總共不到50個FPGA工作時鐘周期。
【權利要求】
1. 一種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法，其特徵在於，包括如下步 驟： 51、 採用並行輸入方式輸入採樣數據：記需要進行FFT的點數為N = ^ · 2M，記輸入的 數據速率為Fs，則經過並行輸入後邏輯器件的工作頻率降為F s/2S其中，f表示並行輸入的 通道數目，所述f的值由採樣設備確定，2M表示並行輸入全部數據所需要的時鐘周期； 52、 確定樣點數據與各個並行通道的映射關係：將並行輸入通道編號為Chx，N點FFT中 的第η個數據被映射到第X個通道Chx上，映射關係式為n = x+m ·2、其中，η表示N點FFT 的第η個數據，X表示第X個輸入通道，m表示輸入開始後的第m個時鐘周期，0 < m < 2Μ-1， 0 彡 χ 彡 2L-1 ; 53、 經過S1和S2的處理，S1所述FFT按照基2抽取了 Μ次，得出需要2"個2M點的DFT 模塊，每個DFT模塊的輸入數據對應一個S2所述並行輸入通道Chx中的所有數據，每個DFT 模塊的數據按照時鐘串行進入，通過控制時序復用資源； 54、 當S3所述f個DFT模塊輸出後，根據FFT抽取的次數Μ完成後續Μ次蝶形運算。
2. 根據權利要求1所述的一種數吉赫茲採樣率下的極低延遲快速傅立葉變換方法，其 特徵在於：S3所述f個DFT模塊是並行的，所述f個DFT模塊相互之間硬體獨立。
【文檔編號】G06F17/14GK104123266SQ201410350688
【公開日】2014年10月29日 申請日期:2014年7月23日 優先權日:2014年7月23日
【發明者】劉皓, 何元波, 候號前 申請人:電子科技大學