並行分支蝶形單元的fft的地址映射方法及裝置的製作方法
2023-05-01 01:06:51
專利名稱：並行分支蝶形單元的fft的地址映射方法及裝置的製作方法
技術領域：
本發明涉及通信技術領域，更具體的說，是涉及一種並行分支蝶形單元的FFT的地址映射方法及裝置。
背景技術：
當前，寬帶無線系統中隨著要 求傳輸的碼元速率不斷提高，傳輸帶寬也越來越寬的情況下，為消除傳輸過程中的幹擾和衰落等，寬帶無線系統的物理層多採用 OFDM (Orthogonal Frequency Division Multiplexing,正交頻分復用)技術，如WiMAX(Worldwide Interoperability for Microwave Access,全球微波互聯接入)、WiFi (wireless fidelity,無線區域網)、DVB (Digital Video Broadcasting，數字視頻廣播)、DAB (Digital Audio Broadcasting,數位訊號廣播)等，上述系統基帶調製部分的共同特點即均採用FFT (Fast Fourier Transformation,快速傅立葉變換)作為「調製引擎」。由於寬帶系統的不斷升級，人們對帶寬的要求也更加苛刻起來，為提升系統的處理能力，對符合上述要求的可高速、並行、可擴展和低成本的FFT的設計需求也變得迫切起來。在現有技術中，設計並行FFT的實現架構時(在對應的FFT裝置中包括控制架構內部模塊間的協調調度的主控單元和外部存儲器)，為了解決不可避免的高速、並行的數據讀寫問題，一般採用多個存儲體(FFT的基數)的方式來解決上述並行數據讀寫的問題，並且多採用成本較低的單埠或雙埠存儲器。但是，依照FFT的運算規則(即利用旋轉因子的周期性和對稱性進行運算，該旋轉因子存儲於旋轉因子存儲器中)，在進行蝶形單元的FFT地址映射的過程中，將中間數據寫入下一級存儲體組時，會影響緊接著的並行數據的讀取，不能保證FFT運算的連續性和有效性，尤其是當FFT的點數較多、基數較大或有多個基數混合運算時，在進行並行FFT運算時，更不能保證FFT運算的連續性和有效性。
發明內容
有鑑於此，本發明提供了一種並行分支蝶形單元的FFT的地址映射方法及裝置，以克服現有技術在蝶形單元的FFT地址映射過程中，不能保證FFT運算的連續性和有效性的問題。為實現上述目的，本發明提供如下技術方案一種並行分支蝶形單元的快速傅立葉變換FFT的地址映射方法，包括依據快速傅立葉變換FFT的採樣點個數確定FFT的基數，及所述基數對應的FFT級間變換的總級數M ;按順序將所述採樣點存儲至第一存儲體組的存儲體中，所述存儲體的個數為當前確定FFT的基數中的最高基的數值Dmax ；依據當前確定的基數在第一存儲體組與第二存儲體組之間執行FFT級間變換，具體為
噹噹前級數m大於等於I且小於M時，將存儲於當前級的存儲體中的待處理數據或中間數據依據列按邏輯塊移一位、行按存儲體移一位的循環移位方式，並行寫入下一級的A=個不同邏輯塊中，所述m的取值範圍為I M ;循環執行上述FFT級間變換至當前級數m等於M。優選地，所述執行FFT級間變換時，將當前級m中的A=個邏輯塊進行劃分，且一個邏輯塊對應劃分為下一級的D個邏輯塊。優選地，所述循環移位的範圍包括行的循環範圍為存儲體組中的存儲體個數；
列的循環範圍為各級每個邏輯塊中所包含的每個存儲體的地址個數。優選地，所述循環移位寫入數據的方式為先按存儲體進行移位，再按邏輯塊進行移位，後按邏輯塊內列移位後寫入數據。優選地，所述循環移位寫入數據的方式為先按邏輯塊內列移位，再按邏輯塊進行移位，後按存儲體進行移位後寫入數據。優選地，包括當FFT的採樣點數為4或8的整數次冪時，確定FFT的基數為單一基，所述單一基為基2、基4或基8 ;當前確定FFT的基數中的最高基的數據Dmax等於所述單一基的數值；所述單一基數對應的FFT級間變換的總級數M為以單一基為底採樣點數的對數。優選地，包括當FFT的採樣點數不為4或8的整數次冪時，確定FFT的基數為混合基，所述混合基為基2、基4或基8的任意組合；當前確定FFT的基數中的最高基的數據Dmax為混合基數中的最高基的數值；所述混合基對應的FFT級間變換的總級數M具體為將不為4或8的整數次冪的採樣點數分解為混合基中各單一基的整數次冪數值的乘積；計算各所述單一基對應的級數，獲取所述混合基中各單一基對應的級數的總和為總級數M ;當進行FFT級間變換時，先依據基4或基8執行FFT級間變換，最後一級執行基2或基4的運算。一種並行分支蝶形單元的快速傅立葉變換FFT的地址映射裝置，包括主控單元、旋轉因子存儲器和外部存儲器，還包括並行分支蝶形單元組，用於經主控單元控制確定FFT的基數，進行FFT級間運算；第一內部存儲體組和第二內部存儲體組，用於存儲進行FFT級間變換時，列按邏輯塊移一位、行按存儲體移一位的循環移位方式並行寫入或讀出的待處理數據或中間數據；地址產生單元，用於向所述旋轉因子存儲器、所述外部存儲器、所述第一內部存儲體組和第二內部存儲體組提供進行FFT級間變換時讀取的地址。經由上述的技術方案可知，與現有技術相比，本發明公開了一種並行分支蝶形單元的FFT的地址映射方法及裝置，基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，能夠解決並行分支蝶形單元運算時FFT的級間數據讀寫問題，即通過地址間的映射實現多組數據間的並行讀寫相互之間不產生影響，保證FFT運算過程中的連續性和有效性，並且可採用普通常用的低成本單埠或雙埠存儲器實現並行FFT運算，進一步降低了實現成本與複雜度。
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據提供的附圖獲得其他的附圖。圖I為本發明實施例一公開的一種並行分支蝶形單元的FFT的地址映射方法流程圖；圖2為本發明一種並行分支蝶形單元FFT 64點DIF4地址變換的示意流程圖；圖3為本發明一種並行分支蝶形單元FFT 64點DIF8地址變換的示意流程圖；圖4為本發明一種應用並行分支蝶形單元FFT地址映射方法的FFT實現結構示意圖。
具體實施方式
為了引用和清楚起見，下文中使用的技術名詞的說明、簡寫或縮寫總結如下FFT Fast Fourier Transformation,快速傅立葉變換；DIF :頻率抽取，為FFT算法中的一種，另一種為時間抽取DIT ；data:數據。下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。由背景技術可知，在利用現有技術中的構架解決高速、並行的數據讀寫問題時，其中對應的FFT裝置在進行蝶形單元的FFT地址映射的過程中，將處理過程中的中間數據寫入下一級存儲體組時，會影響緊接著的並行數據的讀取，不能保證FFT運算的連續性和有效性，尤其是當FFT的點數較多、基數較大或有多個基數混合運算時，在進行並行FFT運算時，更不能保證FFT運算的連續性和有效性。因此，本發明提供了一種並行分支蝶形單元的FFT的地址映射方法及裝置，通過地址間的映射實現多組數據間的並行讀寫相互之間不產生影響，保證FFT運算過程中的連續性和有效性。具體過程通過以下實施例進行詳細說明。實施例一請參閱附圖1，為本發明公開的一種並行分支蝶形單元的FFT的地址映射方法的流程圖，主要包括以下步驟步驟S101，依據FFT的採樣點個數N確定FFT的基數D，以及所述基數D對應的FFT級間變換的總級數M。在執行步驟SlOl中，基數D的FFT即為執行FFT蝶形單元的基數，D的取值與採樣點的個數N有關。所述基數D對應的FFT級間變換的總級數M則與基數D和採樣點數N有關。在本發明中的基數主要包括基8、基4和基2，一般情況下，基數越大效率越高。其中，採樣點數可按DIF進行抽取，也可以按照DIT進行抽取。步驟S102，按順序將所述採樣點存儲至第一存儲體組的存儲體中，所述存儲體的個數為當前確定FFT的基數中的最高基的數值D_。步驟S103，依據確定的基數在第一存儲體組與第二存儲體組之間執行FFT級間變換。在整個FFT系統中存在兩組存儲體組，所進行的級間變換也是在兩組存儲體組中桌球進行的。在執行步驟S102中，將抽取到的採樣點N存儲至第一存儲體組的存儲體中，需要說明的是，在兩組存儲體組中的存儲體的個數為當前確定的FFT的基數中的最高基的·數值Dmax。一般情況下，每個存儲體組中的每個存儲體中存儲的採樣點的個數是相同的。步驟S104，判斷當前進行FFT級間變換的級數m是否大於等於I且小於M，如果是，則執行步驟S105 ;如果否，則執行步驟S106。步驟S105，將存儲於當前級的存儲體中的待處理數據或中間數據依據列按邏輯塊移一位、行按存儲體移一位的循環移位方式，並行寫入下一級的A=個不同邏輯塊中，所述m的取值範圍為I M。在執行步驟S105進行FFT級間變換時，將當前級m中的A=個邏輯塊進行劃分，且一個邏輯塊對應劃分為下一級的D個邏輯塊。對邏輯塊的劃分詳細進行說明，具體每一級劃分的邏輯塊的個數與其所在級數和FFT的基數有關，具體為山疒其中m的取值範圍為I M，即在總級數之內(包括總級數)。需要注意的是該劃分是在實際運算過程中的邏輯劃分，且上一級中的一個邏輯塊將對應分割為下一級的D個邏輯塊。給出一示例進行說明當FFT的基數為2，採樣點數為64，FFT的總級數M為6，此時計算其各個所在級數m的邏輯塊為當m等於I時，Dnri = D0,第一級具有一塊邏輯塊；當m等於2時，Dnri = D1 = 2，第二級具有兩塊邏輯塊；當m等於3時，Dnri = D2 = 4，第三級具有四塊邏輯塊；依次類推，第四級八塊，第五級十六塊，第六級三十二塊。由此，第一級中的一塊邏輯塊分割成第二級中的兩塊邏輯塊；第二級中的兩塊邏輯塊則依次分割為第三級中的四塊邏輯塊，依次進行分割。需要說明的是，在分割的過程中，被分割的邏輯塊與分割後的邏輯塊是一一對應的，例如第三級中具有四塊邏輯塊，分別將其編號為第三級的第一邏輯塊至第四邏輯塊，而第二級中的兩塊邏輯塊的編號為第二級的第一邏輯塊和第二邏輯塊，其對應分割後的邏輯塊，即對應第三級中的邏輯塊分別為第二級中的第一邏輯塊分割為第三級的第一邏輯塊和第二邏輯塊；第二級中的第二邏輯塊則分割為第三級的第三邏輯塊和第四邏輯塊，即分割上一級中的邏輯塊時，依次分割並與下一級中分割的邏輯塊對應。步驟S106，當前進行FFT運算的級數m等於M，上述循環執行的FFT級間變換已到達最後一級，即總級數M級處，停止FFT級間變換，即停止FFT運算。在執行步驟S104至步驟S106的過程中，在當前級數m小於總級數M時，則依次進行FFT級間的變換，即從第一級開始向第二級進行變換(從第一存儲體組向第二存儲體組進行變換)，然後再從第二級向第三級進行變換(從第二存儲體組向第一存儲體組進行變換)，依次進行。如果總級數為2，則只進行一次級間變換即可。如果總級數較大，則依據步驟S105的方式循環進行上述的級間變換、循環移位等，即利用列(邏輯塊或塊內地址)、行(存儲體)循環移位的方式實現將上一級FFT處理完的中間數據寫入下一級待處理的D個存儲體中，為不影響下一級的FFT處理運算，處理完畢的數據會被並行寫入下一級中的Dm-1On為當前運算所處的級數)個不同邏輯塊中。
需要說明的是，在進行上述循環移位的過程中，行的循環範圍為存儲體組中的存儲體個數；列的循環範圍為各級每個邏輯塊中所包含的每個存儲體的地址個數。此外，上述循環移位寫入數據的方式可以為先按存儲體進行移位，再按邏輯塊進行移位，後按邏輯塊內列移位後寫入數據；也可以為先按邏輯塊內列移位，再按邏輯塊進行移位，後按存儲體進行移位後寫入數據。本發明並不對此進行限定，即移位的順序並不是唯一的。通過上述本發明所提供的方法，基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，能夠解決並行分支蝶形單元運算時FFT的級間數據讀寫問題，並且可採用普通常用的低成本單埠或雙埠存儲器實現並行FFT運算，進一步降低了實現成本與複雜度。需要進行說明的是，關於FFT的採樣點數N的取值對FFT所選取的基數的影響。當FFT的採樣點數N為4或8的整數次冪時，確定FFT的基數為單一基，所述單一基為基2、基4或基8。那麼，當前確定FFT的基數中的最高基的數據Dmax等於所述單一基的數值，即確定當前存儲體組中的存儲體的個數。而對於該單一基數對應的FFT級間變換的總級數M為以單一基為底採樣點數的對數。可以用公式⑴表示M = log^}( I )其中，M即為FFT的總級數，D為FFT的基數，N為確定的採樣點數，為D的整數次冪。當FFT的採樣點數不為4或8的整數次冪時，確定FFT的基數為混合基，所述混合基為基2、基4或基8的任意組合。那麼，當前確定FFT的基數中的最高基的數據Dmax為混合基數中的最高基的數值。如混合基為基2與基8的組合，則Dmax = 8 ;如混合基為基2與基4的組合，則Dmax = 4。而對於該混合基對應的FFT級間變換的總級數M，則將採樣點分解為混合基中各單一基的整數次冪數值的乘積，然後再計算各單一基對應的級數，即依據公式(I)獲取為基2、基4或基8時各自對應的級數，計算其級數的總和為FFT級間變換的總級數M。如N =128，採用基2和基4混合，將其分解為2的I次冪與4的3次冪乘積，依據公式(I)可知，Iog^=SJogf = I, M = 3+1 =4。實際上即為，FFT級間變換的前三級採用基4，最後一級米用基2。對於混合基來說，當進行FFT級間變換時，先依據基4或基8執行FFT級間變換，最後一級執行基2或基4的運算。同樣，通過上述本發明所提供的方法，基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，能夠解決並行分支蝶形單元運算時FFT的級間數據讀寫問題，並且可採用普通常用的低成本單埠或雙埠存儲器實現並行FFT運算，進一步降低了實現成本與複雜度。此外，針對上述本發明所公開的地址映射方法既可用於基4、基8的高效實現，也可用於基2的運算範圍。下面給出具體實施例進行詳細說明。實施例二請參閱附圖2,為本發明示出的一種並行分支蝶形單元FFT 64點DIF4地址變換的示意流程圖，具體的變換流程如下所述如圖2所示，按照DIF即按照頻率抽取的方式，共採樣(抽取)了 64個點，按照 FFT的基4進行運算，即D的取值為4，N的取值為64。由此，可以根據公式⑴得出，FFT的總級數M為3，依次該64點DIF4的FFT變換的中間級數為2級，如圖2中示出的A和B，其中，A表示第一級變換存儲體組，B表示第二級變換存儲體組。如圖2所示，兩級變換中的兩個存儲體組分別為組I 中包括，RAMAl、RAMA2、RAMA3、RAMA4 ；組2 中包括，RAMBI、RAMB2、RAMB3、RAMB4。在已知上述基本條件的基礎上，首先，將待變換數據(即獲取的採樣點)按照如圖2順序依次寫入存儲體組I中。由於是基4的並行運算，因此，按照並行讀出的過程，從組I的4個存儲體中並行讀出4個數據，第一組為0、16、32和48地址中的待處理數據(後續說明中讀取的數據用標識data的方式進行表示,如dataO, datal6, data32, data48等)。經蝶形單元處理後並行寫入存儲體組2中的4個存儲體中，在本發明所要解決的問題中，主要是要在不影響級間的並行運算的基礎上完成待處理數據或中間數據的並行讀取和寫入。因此，在本發明所提供的方法中，為了不影響第二級並行計算，寫入規則如圖2所示，即先將第一級中的一塊邏輯塊分割成對應第二級中的四塊邏輯塊並分別對其編號；然後，依據行、列循環移位的方式進行並行的寫入。具體為將dataO寫入存儲體組2中第一個邏輯塊的第一個存儲體RAMBl中；將datal6寫入第二個邏輯塊對應dataO存儲體行、列移位後的存儲體RAMB2中；將data32寫入第三個邏輯塊對應datal6存儲體行、列移位後的存儲體RAMB3中；將data48寫入第四個邏輯塊對應data32存儲體行、列移位後的存儲體RAMB4中。完成上述第一級中的第一組並行輸出的待處理數據進行第一級變換A後並行寫入至第二級中。同理,針對第二組並行輸出的待處理數據datal、datal7、data33和data49進行第一級變換A後並行寫入的方式如圖2所示，即將datal寫入存儲體組2中第一個邏輯塊對應dataO位置循環行、列移位後的存儲體RAMB2中；datal7寫入存儲體組2中第二個邏輯塊對應datal6位置循環行、列移位後的存儲體RAMB3中；data33寫入存儲體組2中第三個邏輯塊對應data32位置循環行、列移位後的存儲體RAMB4中；data49寫入存儲體組2中第四個邏輯塊對應data48位置循環行、列移位後的存儲體RAMBl中。需要說明的是，對於後續從第一級中並行輸出的數據再寫入時，都依據之前寫入數據的位置進行循環行、列移位。該循環行、列移位的範圍即整個邏輯塊。如圖2所示，針對第二級變換B，按照同樣的方式將上一級中的邏輯塊對應分割成16塊邏輯塊，上一級中的一塊邏輯塊各對應其分割而成的四個邏輯塊。同樣，在進行第二級變換B的過程中，其方向為從存儲體組2中按組並行讀取待處理數據或中間數據寫入至存儲體組I中。寫入規則如圖2所示，其具體過程與進行第一級變換A的過程相同。如從存儲體組2中並行輸出的第一組待處理數據為dataO、data4、data8、datal2，將dataO寫入存儲體組I中第一個邏輯塊的第一個存儲體RAMAl中；將data4寫入第二個邏輯塊對應dataO存儲體行、列移位後的存儲體RAMA2中；將data8寫入第三個邏輯塊對應data4存儲體行、列移位後的存儲體RAMA3中；將datal2寫入第四個邏輯塊對應data8存儲體行、列移位 後的存儲體RAMA4中。同理,針對第二組並行輸出的待處理數據datal3、datal、data5和data9,如圖2所示，將datal3寫入存儲體組I中第一個邏輯塊對應dataO位置循環行、列移位後的存儲體RAMAl中第四邏輯塊中；datal寫入存儲體組I中第二個邏輯塊對應data4位置循環行、列移位後的存儲體RAMA2中的第一邏輯塊中；data5寫入存儲體組I中第二個邏輯塊對應data8位置循環行、列移位後的存儲體RAMA3中的第三個邏輯塊中；data9寫入存儲體組I中第四個邏輯塊對應datal2位置循環行、列移位後的存儲體RAMA4中的第三塊邏輯塊中。需要說明的是，，上一級中的一個邏輯塊對應的存儲體中存儲的待處理數據，每一次進行並行寫入以及循環行、列移位時都針對其分割而成的下一級中對應的邏輯塊進行，即如圖2中進行第二級變換B時的寫入循環方式所示。實施例三在上述本發明實施例公開的基礎上，如圖3所示，本發明還公開了一種並行分支蝶形單元FFT 64點DIF8地址變換的示意流程圖，具體的變換流程如下所述如圖3所示，按照DIF即按照頻率抽取的方式，共採樣(抽取)了 64個點，按照FFT的基8進行運算，即D的取值為8，N的取值為64。由此，可以根據公式⑴得出，FFT的總級數M為2，依次該64點DIF4的FFT變換的中間級數為I級，如圖3中示出的A表示第一級變換。如圖3所示，兩級變換中的兩個存儲體組分別為組I 中包括，RAMAl、RAMA2、RAMA3、RAMA4、RAMA5、RAMA6、RAMA7、RAMA8 ；組2 中包括，RAMBI、RAMB2、RAMB3、RAMB4、RAMB5、RAMB6、RAMB7、RAMB8。在已知上述基本條件的基礎上，首先，將待變換數據(即獲取的採樣點)按照如圖3順序依次寫入存儲體組I中。在並行分支的蝶形單元進行處理的過程中，將存儲體組I中的8個數據並行讀出，處理後再並行寫入存儲體組2中。為了不影響第二級FFT的數據處理，並行讀出的8個數據即0地址、8地址、16地址、24地址、32地址、40地址、48地址和56地址中的數據(n地址的數據後面均採用data的形式加以標示)採用如圖方法寫入存儲體組2中。8個數據被依次寫入不同的邏輯塊中，且在存儲體即列上予以移位。後續的數據的寫入方式也相同，列移位時為循環移位。通過上述本發明所述的具體實施例可知，基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，能夠解決並行分支蝶形單元運算時FFT的級間數據讀寫問題，並且可採用普通常用的低成本單埠或雙埠存儲器實現並行FFT運算，進一步降低了實現成本與複雜度。
需要說明的是，當採樣得到的運算點數，即採樣點數N不為4或8的整數次冪時，在進行並行分支蝶形單元FFT地址映射的過程中，依照上述變換的方法，先進行基4或基8的變換，最後一級則採用基2或基4的運算方式完成即可。此外，針對多級基的處理時，列和行的移位均為循環移位，同樣的，列的循環範圍為存儲體組中存儲體的個數，行的循環範圍是邏輯塊中所包含的每個存儲體的地址個數。上述本發明公開的實施例中詳細描述了一種並行分支蝶形單元FFT地址映射方法，對於本發明的方法可採用多種形式的裝置實現，因此本發明還公開了一種並行分支蝶形單元FFT地址映射裝置，下面給出具體的實施例進行詳細說明。請參閱附圖4，為本發明公開的一種並行分支蝶形單元的快速傅立葉變換FFT的 地址映射裝置，即FFT實現的結構示意圖。主要包括主控單元101、地址產生單元102、旋轉因子存儲器103、第一內部存儲體組104、第二內部存儲體組105、並行分支蝶形單元106和外部存儲器107。並行分支蝶形單元組106為主要單元，用於經主控單元控制確定FFT的基數，進行FFT級間運算。第一內部存儲體組104和第二內部存儲體組105，用於存儲進行FFT級間變換時，行按邏輯塊移一位、列按存儲體移一位的循環移位方式並行寫入的待處理數據或中間數據。地址產生單元102，用於向所述旋轉因子存儲器103、所述外部存儲器107、所述第一內部存儲體組104和第二內部存儲體組105提供進行FFT級間變換時讀取的地址。其具體執行過程為主控單元101負責控制內部模塊間的協調調度，主要包括控制地址產生單元為外部存儲器107、第一內部存儲體組104和第二內部存儲體組105以及旋轉因子存儲器103提供讀取地址，同時還需控制並行分支蝶形單元組106以選擇蝶形單元的基數，其內可包含基2、基4或基8的並行分支蝶形單元，採用哪種分支及何時採用由主控單元加以控制，本發明的主要變換方法即體現在該單元中，是整個FFT的運算核心。旋轉因子存儲器103內存有FFT變換所需的旋轉因子，為配合FFT的並行計算，旋轉因子也可採用多個存儲體存儲的形式。第一內部存儲體組104和第二內部存儲體組105主要用來保存FFT運算的中間數據，均由D個存儲體組成，D對應FFT運算基數的最大值。綜上所述通過上述本發明所提供的方法和裝置，基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，通過地址間的映射實現多組數據間的並行讀寫相互之間不產生影響，保證FFT運算過程中的連續性和有效性，能夠解決並行分支蝶形單元運算時FFT的級間數據讀寫問題，並且可採用普通常用的低成本單埠或雙埠存儲器實現並行FFT運算，進一步降低了實現成本與複雜度。本說明書中各個實施例採用遞進的方式描述，每個實施例重點說明的都是與其他實施例的不同之處，各個實施例之間相同相似部分互相參見即可。對於實施例公開的裝置而言，由於其與實施例公開的方法相對應，所以描述的比較簡單，相關之處參見方法部分說明即可。結合本文中所公開的實施例描述的方法或算法的步驟可以直接用硬體、處理器執行的軟體模塊，或者二者的結合來實施。軟體模塊可以置於隨機存儲器(RAM)、內存、只讀存儲器(ROM)、電可編程ROM、電可擦除可編程ROM、寄存器、硬碟、可移動磁碟、CD-ROM、或技術領域內所公知的任意其它形式的存儲介質中。對所公開的實施例的上述說明，使本領域專業技術人員能夠實現或使用本發明。對這些實施例的多種修改對本領域的專業技術人員來說將是顯而易見的，本文中所定義的一般原理可以在不脫離本發明的精神或範圍的情況下，在其它實施例中實現。因此，本發明將不會被限制於本文所示的這些實施例，而是要符合與本文所公開的 原理和新穎特點相一致的最寬的範圍。
權利要求
1.一種並行分支蝶形單元的快速傅立葉變換FFT的地址映射方法，其特徵在於，包括 依據快速傅立葉變換FFT的採樣點個數確定FFT的基數，及所述基數對應的FFT級間變換的總級數M ； 按順序將所述採樣點存儲至第一存儲體組的存儲體中，所述存儲體的個數為當前確定FFT的基數中的最高基的數值Dmax ； 依據當前確定的基數在第一存儲體組與第二存儲體組之間執行FFT級間變換，具體為 噹噹前級數m大於等於I且小於M時，將存儲於當前級的存儲體中的待處理數據或中間數據依據列按邏輯塊移一位、行按存儲體移一位的循環移位方式，並行寫入下一級的 A=個不同邏輯塊中，所述m的取值範圍為I M ;循環執行上述FFT級間變換至當前級數m等於M。
2.根據權利要求I所述的方法，其特徵在於，所述執行FFT級間變換時，將當前級m中的A=個邏輯塊進行劃分，且一個邏輯塊對應劃分為下一級的D個邏輯塊。
3.根據權利要求I所述的方法，其特徵在於，所述循環移位的範圍包括 行的循環範圍為存儲體組中的存儲體個數； 列的循環範圍為各級每個邏輯塊中所包含的每個存儲體的地址個數。
4.根據權利要求I所述的方法，其特徵在於，所述循環移位寫入數據的方式為先按存儲體進行移位，再按邏輯塊進行移位，後按邏輯塊內列移位後寫入數據。
5.根據權利要求I所述的方法，其特徵在於，所述循環移位寫入數據的方式為先按邏輯塊內列移位，再按邏輯塊進行移位，後按存儲體進行移位後寫入數據。
6.根據權利要求I 5中任意一項所述的方法,其特徵在於,包括 當FFT的採樣點數為4或8的整數次冪時，確定FFT的基數為單一基，所述單一基為基.2、基4或基8 ; 當前確定FFT的基數中的最高基的數據Dmax等於所述單一基的數值； 所述單一基數對應的FFT級間變換的總級數M為以單一基為底採樣點數的對數。
7.根據權利要求I 5中任意一項所述的方法,其特徵在於,包括 當FFT的採樣點數不為4或8的整數次冪時，確定FFT的基數為混合基，所述混合基為基2、基4或基8的任意組合； 當前確定FFT的基數中的最高基的數據Dmax為混合基數中的最高基的數值； 所述混合基對應的FFT級間變換的總級數M具體為將不為4或8的整數次冪的採樣點數分解為混合基中各單一基的整數次冪數值的乘積； 計算各所述單一基對應的級數，獲取所述混合基中各單一基對應的級數的總和為總級數M ; 當進行FFT級間變換時，先依據基4或基8執行FFT級間變換，最後一級執行基2或基4的運算。
8.一種並行分支蝶形單元的快速傅立葉變換FFT的地址映射裝置，包括主控單元、旋轉因子存儲器和外部存儲器，其特徵在於，還包括 並行分支蝶形單元組，用於經主控單元控制確定FFT的基數，進行FFT級間運算； 第一內部存儲體組和第二內部存儲體組，用於存儲進行FFT級間變換時，列按邏輯塊移一位、行按存儲體移一位的循環移位方式並行寫入或讀出的待處理數據或中間數據；地址產生單元，用於向所述旋轉因子存儲器、所述外部存儲器、所述第一內部存儲體組 和第二內部存儲體組提供進行FFT級間變換時讀取的地址。
全文摘要
本發明公開了一種並行分支蝶形單元的FFT的地址映射方法及裝置，其方法包括依據FFT的採樣點個數確定基數及FFT級間變換的總級數；按順序將採樣點存儲至第一存儲體組的存儲體中；執行FFT級間變換，噹噹前級數m大於等於1且小於M時，將存儲於當前級的存儲體中的待處理數據或中間數據依據列按邏輯塊移一位、行按存儲體移一位的循環移位方式，並行寫入下一級的個不同邏輯塊中；直至當前級數m等於M時停止級間變換。通過上述基於FFT級間的變換和依據行、列循環移位的方法，實現並行分支蝶形單元FFT地址映射，即通過地址間的映射實現多組數據間的並行讀寫相互之間不產生影響，保證FFT運算過程中的連續性和有效性。
文檔編號G06F17/14GK102855222SQ20111017552
公開日2013年1月2日 申請日期2011年6月27日 優先權日2011年6月27日
發明者亓中瑞, 陳杰, 曲文澤, 瞿海慧 申請人:中國科學院微電子研究所