[發明專利]基于3D存儲器的地址生成器

有效

• 申請號: 201310469997.0
• 申請日: 2013-10-10
• 公開（公告）號: CN103777896B
• 公開（公告）日: 2019-04-16
• 發明（設計）人: L·徐
• 申請（專利權）人: 阿爾特拉公司
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F17/14
• 代理公司: 北京紀凱知識產權代理有限公司 11245
• 代理人: 趙蓉民

本發明涉及基于3D存儲器的地址生成器。公開了用于在可變大小的快速傅里葉變換（FFT）架構中減少存儲器使用并增加吞吐量的系統和方法。特別地，公開了3D對稱虛擬存儲器，從而利用可變大小FFT計算的內在結構。可以按照利用可變大小FFT計算中的內在結構的具體的坐標序列向3D對稱虛擬存儲器寫入數據樣本或從中讀取數據樣本。可以利用地址生成電路將3D對稱虛擬存儲器中的存儲位置映射到1D緩沖區中的存儲地址。

技術領域

本發明涉及用于在可變大小快速傅里葉變換（FFT）架構中降低存儲器使用并增加吞吐量的系統和方法。

背景技術

3GPP長期演進（LTE）是支持高速無線通信的無線通信標準。LTE是基于單載波頻分復用（SC-FDM）和正交頻分復用（OFDM）兩種算法的通信標準，這兩種算法大量使用FFT，例如可變大小的離散傅里葉變換（DFT）或離散傅里葉逆變換（IDFT）。

FFT計算包括讀取帶有數據樣本x[n],n=0,…,N-1（其中N是輸入數據序列的長度）的輸入數據序列，并輸出帶有數據樣本X[k],k=0,…,N-1的頻域FFT數據序列。通常將這樣的計算稱為N點FFT。FFT算法使用分治法來降低計算FFT的計算復雜度。例如，庫利-圖基（Cooley-Tukey）算法在每個中間級（pass）將計算FFT的問題遞歸地分解為一半大小（即，N/2）的子問題。FFT分解的大小被稱為基數。在以上示例中，基數為2。假如N是k的冪，則這種分解方法通常對任意基數k適用。因此，計算FFT一般包括在輸入數據序列上形成數個級（也稱為階段）并形成中間結果。通常，每一級可以與不同的基數相關聯。

LTE標準一般使用基數R=2、3、4或5的FFT算法。作為示例，考慮使用基數R=4的64點FFT的計算。為計算FFT，FFT處理器通常按順序處理輸入數據序列，其中與數據樣本對應的索引按照如下順序排列：

00,16,32,48,01,17,33,49,02,18,34,50,03,19,35,51,04,20,36,52,...,15,31,47,63。

數據樣本的這個順序被稱為反基數順序（radix-reversed order）。在FFT計算的第一級，利用對應于索引00,16,32和48的數據樣本來計算第一個基數-4蝶形；利用對應于索引01,17,33和49的數據樣本來計算下一個基數-4蝶形，以此類推。FFT蝶形是FFT計算的一部分，其將較大的FFT計算分解成較小的子變換計算。

已經注意到，可變大小的DFT/IDFT實現通常需要很高的存儲器使用并且會遭遇吞吐量低的問題。因此，擁有能夠有效執行DFT/IDFT計算的架構是有益的。如果沒有用于執行這樣的計算的有效架構，則DFT/IDFT計算可能會成為阻礙基于LTE的通信方案最優運行的瓶頸。

一些當前的可變大小的DFT/IDFT實現使用雙處理內核，以便滿足LTE的吞吐量需求。此外，一些當前的可變大小的DFT/IDFT實現使用雙重雙端口存儲器來滿足存儲器使用需求。例如，一些可變大小的DFT/IDFT實現使用包含兩個單獨的存儲陣列的乒乓緩沖區（ping-pong buffer），這兩個單獨的存儲陣列按照允許并行進行數據的讀取和寫入的配置布置。具體地，每個存儲陣列可以具有獨立的數據總線，在第一時間段內，該數據總線可以使數據能夠寫入第一存儲陣列中，同時從第二存儲陣列中讀取數據。在第二時間段內，可以從第一存儲陣列中讀取數據，同時將數據寫入第二存儲陣列中。在后續的時間段內，可以按照上述方式對每個存儲陣列交替進行數據的讀取和寫入。

然而，利用乒乓緩沖區以增加存儲器需求為代價，即，需要比使用單個存儲陣列更多的存儲器。因此，期望的是擁有一種在不增加存儲器需求的情況下有效執行可變大小的FFT的方法和系統。

發明內容

為解決本技術領域內的以上不足和其它不足，本發明提供用于在可變大小的快速傅里葉變換（FFT）架構中減少存儲器使用并增加吞吐量的方法和系統。