一種實現快速傅立葉變換、反變換的硬體裝置及方法

2023-06-07 01:36:11

專利名稱：：一種實現快速傅立葉變換、反變換的硬體裝置及方法
技術領域：
：本發明涉及無線移動通信及信號處理系統領域，尤其涉及一種應用於TD-SCDMA基帶處理系統的實現快速傅立葉變換(FastFourierTransform，簡稱FFT)及其反變換(InverseFastFourierTransform,IFFT)的硬體裝置及方法。
背景技術：
：無線移動通信及信號處理系統中，經常需要對處理信號進行時域、頻域間的數據形式的轉化與切換，以方便做下一步的數據處理和完成算法流程。FFT主要用於數據從時域向頻域的轉換，其反變換IFFT則用於實現數據從頻域向時域的切換和轉化。在TD-SCDMA移動通信基帶處理系統中，普遍採用了聯合檢測的基帶處理算法，其中含有對信號傳輸通道的信道估計處理與計算過程。其算法流程描述及數據處理過程較為複雜，其中不可避免的用到了數據形式從時域向頻域(FFT)、從頻域向時域(IFFT)的切換和轉化運算，如圖l所示，在信道估計運算處理中，完成串行幹擾消除、且在與上層配置下來的基本midamble碼頻域數據點除後，需要將頻域數據轉化為時域數據，才能進行基於能量大小的有效徑判決操作，這就需要進行IFFT運算；對低於噪聲徑的徑係數置零後、幹擾係數重構前，又需要將時域的數據轉化為頻域格式，才能和上層配置下來的基本midamble碼FFT變換結果進行點乘運算，這時就需要進行FFT變換。在移動通信基帶處理系統中，特別是用戶側的移動終端處理系統中，對FFT的硬體實現要求頗為苛刻，有幾個方面一是面積資源問題，不可能將用戶終端系統做的很龐大；二是時鐘資源的耗費問題，實時處理系統對時鐘資源的利用提出很高的要求；三是成本問題，多點FFT的運算過程分級、中間結果的合理存儲與利用、運算本身的複數乘法、複數加減法等等，其設計過程均直接涉及到硬體資源的相應耗費。綜上，移動通信終端基帶處理系統，對FFT/IFFT的硬體實現的面積資源及時鐘資源的利用及提出了較高的要求。FFT/IFFT的硬體實現電路，需要考慮以下幾點設計要素(1)FFT/IFFT功能模塊的輸入及輸出數據流排列順序由FFT/IFFT數學運算具體過程可知，可以選擇不同的拓補結構(蝶形中的兩兩數據交叉配對)完成多點FFT/IFFT的運算，理論上講，輸入數據是自然順序或者倒序、對輸出結果要求是自然順序或者倒序均可以做到。但是，對非FFT/IFFT運算來說，很少用到位反序的數據流輸入或輸出，而自然順序的數據排列相對常見。(2)蝶形運算中使用的旋轉因子在蝶形運算X(K)=&(K)±WNkX2(K)中，稱WNk為旋轉因子。根據多點FFT/IFFT運算的具體輸入數據點數(假設為2的n次冪)，以及設計中的定點化精度，來決定運算中所需要的旋轉因子數值取值。在目前的實際設計中，旋轉因子的取數和生成一般採用以下途徑實時生成當前所需旋轉因子本身或者其倍數數值，通過與某一個基值相乘得到想要的旋轉因子數據。這種方法適合對實時性要求不是很強的場合。[OOW](3)蝶形運算單元6由於蝶形運算X(K)=XJK)±WNkX2(K)需要完成複數乘法、複數加減法的運算，硬體設計中相對應的也需要用複數乘法器(多個實數乘法器組成)等器件完成運算。由於採用不同數量的乘法器資源及加法器資源對成本及面積上的影響較大，所以要考慮到蝶形運算單元的實現策略。(4)中間結果的存儲與調用根據多點FFT/IFFT運算的具體輸入數據點數(假設為2的n次冪)，整個FFT/IFFT運算分為n級來完成，即有n級的中間結果需要緩存及被接下來的一級運算有序地調用。考慮每一級採用的不同拓補結構的設計，以及硬體存儲結構的可實現性，合理安排逐級中間結果的緩存與取數調用，對快速高效完成FFT/IFFT運算很關鍵。(5)每級中間計算結果數據的溢出判斷和溢出處理由於硬體設計中定點化的存在，必須考慮每級FFT/IFFT運算的蝶形運算精度控制及補償問題，這就是運算中的溢出判斷和溢出處理。這個和定點化方案中的數據鏈整體精度控制有關。以上就是FFT/IFFT的硬體電路實現需要考慮的五個重要要素。但是作為終端無線移動通信系統處理系統，不僅僅是要實現FFT/IFFT數學運算，還要考慮無線終端設備的特殊性，如成本、便攜、高速數據處理的實時性及其與其他模塊的交互協作、整體設計等。中國專利CN200710103178.9_01_23，描述了一種FFT/IFFT成對處理系統及裝置，但是其所述第一傅立葉變換處理模塊及第二傅立葉變換模塊，均只能接收一種順序的數據流、輸出另一種順序的數據流，比如接收自然序數據流，輸出位反序數據流；或者接收位反序數據流，輸出自然序數據流。該專利的不足在於只有在類似FFT/IFFT的特定運算中，才可能對數據有位反序的排列要求，亦即位反序的數據流，對其他運算來說，作為輸入或者強制的輸出格式均不方便，所以該專利裝置的通用性不強。中國專利CN02152484_01_11，描述了基4和混合基(4+2)FFT處理器地址映射方法和系統，其使用了4個數據存儲體和3個旋轉因子存儲體。該專利的不足在於存儲單元塊數較多，且使用了過多存儲單元對中間操作數的存儲，雖然可能做到了FFT本身數學運算的較大並行度，但並不適合在終端基帶系統中應用。
發明內容本發明所要解決的技術問題是克服現有的有關FFT(或IFFT)硬體設計中硬體資源及時鐘資源均耗費巨大問題和缺陷，提供一種設計思路清晰、實現簡單且滿足實時系統對硬體資源及時間雙重苛刻要求的實現FFT/IFFT的硬體裝置，以及相應的實現方法。為解決上述技術問題，本發明是通過以下技術方案實現的—種實現快速傅立葉變換的硬體裝置，該裝置包括依次相連的逆序讀取單元、處理結果存儲單元、運算單元；所述處理結果存儲單元，包括第一RAM存儲單元和第二RAM存儲單元；所述逆序讀取單元，用於產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將所讀取的兩數據分別寫入第一RAM存儲單元和第二RAM存儲單元中；所述第一RAM存儲單元和第二RAM存儲單元，均用於存儲所述逆序讀取單元所讀取的輸入數據、運算單元所執行的各級蝶形運算的運算結果；還用於提供對外接口，用以輸出運算結果；所述運算單元，用於按照所述輸入數據的點數N進行n級迭代的蝶形運算，在每級的每次蝶形運算過程中，從所述處理結果存儲單元讀取兩個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；所述N等於2的n次冪。其中，所述運算單元包括依次相連的溢出處理單元、第一交換單元、蝶形運算單元、第二交換單元、溢出判斷單元；還包括與第二交換單元相連的整體補償單元、與蝶形運算單元相連的運算信息預存rom單元、與第一交換單元相連的第一控制單元、與第二交換單元相連的第二控制單元；且所述溢出處理單元、溢出判斷單元、整體補償單元均分別與所述處理結果存儲單元相連；所述溢出處理單元，用於在進行第2至n級蝶形運算時，根據相應的溢出標誌位對當前蝶形運算的待處理數據進行溢出處理操作；所述第一控制單元，用於預存各級運算中所使用的第一交換標識信息，據此控制第一交換單元對當前的待處理數據進行交換或者還原操作；所述第一交換單元，用於對當前兩個待處理數據進行交換或還原操作後分別作為XJK)和&(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；所述運算信息預存rom單元，用於預存各級蝶形運算中所使用的旋轉因子WNk;還用於存儲各級的運算結果在處理結果存儲單元中對應的存儲位置；所述蝶形運算單元，用於獲取對應的旋轉因子W/，按照X(K)=XJK)±WNkX2(K)進行蝶形運算，並輸出運算結果&(K)+w;^(K)禾卩&(K)-w;^(K);所述第二控制單元，用於預存各級運算中所使用的第二交換標識信息和運算結果的具體存儲地址信息，控制第二交換單元對當前的運算結果進行交換或者還原操作，並告知第二交換單元當前運算結果在處理結果存儲單元中預設的具體存儲地址；所述第二交換單元，用於在第1至n-l級蝶形運算過程中，對所述蝶形運算單元當前的兩個運算結果進行交換或者還原操作，之後將其送至溢出判斷單元或者整體補償單元；所述溢出判斷單元，用於在第1至n-l級蝶形運算過程中，判斷蝶形運算單元當前的兩個運算結果是否溢出，根據判斷結果設置相應的溢出標誌位並存儲，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述整體補償單元，用於在第n級蝶形運算過程中，根據之前各級的溢出處理操作時採用的縮小倍數對蝶形運算單元當前的運算結果進行數據放大補償，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址。—種實現快速傅立葉變換的方法，該方法包括以下步驟A、確定當前進行快速傅立葉變換運算的輸入數據的點數N，所述N等於2的n次■^^^;B、產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將讀取的兩數據分別寫入處理結果存儲單元的第一RAM存儲單元和第二RAM存儲單元；C、按照所述輸入數據的點數N進行n級迭代蝶形運算，在每級的每次蝶形運算過程中，從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，以作為下一級蝶形運算的待處理數據。其中，所述步驟C包括Cl、從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；C2、對所讀取的兩個數據進行溢出處理及數據交換操作後分別作為&(K)和X2(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；C3、從運算信息預存rom單元中提取預存的本級運算中所使用的旋轉因子WNk，按照X(K)=&(K)±WNkX2(K)進行蝶形運算，並輸出運算結果&(K)+WNkX2(K)和XjK)-WNkX2(K);C4、對所述兩個運算結果進行數據交換及溢出判斷操作，根據判斷結果設置相應的溢出標誌位；C4、將所述運算結果分別存儲至第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，作為下一級蝶形運算的待處理數據；C5、重複步驟C1至C4，直至運行到第n級蝶形運算結束後，對本級的運算結果進行數據倍數的整體補償。—種實現快速傅立葉反變換的硬體裝置，該裝置包括依次相連的逆序讀取單元、共軛處理單元、處理結果存儲單元、運算單元；所述處理結果存儲單元，包括第一RAM存儲單元和第二RAM存儲單元；所述逆序讀取單元，用於產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並將所讀取的數據經共軛處理單元處理後自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將所讀取的兩數據經共軛處理單元處理後分別寫入第一RAM存儲單元和第二RAM存儲單元中；所述共軛處理單元，用於對逆序讀取單元所讀取的輸入數據進行共軛處理操作，還用於對第n級蝶形運算的運算結果進行共軛處理操作後寫入第一RAM存儲單元和第二RAM存儲單元；所述第一RAM存儲單元和第二RAM存儲單元，均用於存儲所述逆序讀取單元所讀取的經共軛處理的輸入數據、運算單元所執行的各級蝶形運算的運算結果；還用於提供對外接口，用以輸出運算結果；所述運算單元，用於按照所述輸入數據的點數N進行n級的蝶形運算，在每級的每次蝶形運算過程中，從所述處理結果存儲單元讀取兩個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；且在進行第n級蝶形運算時，將本級的運算結果經共軛處理單元處理後再分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述N等於2的n次冪。其中，所述運算單元包括依次相連的溢出處理單元、第一交換單元、蝶形運算單元、第二交換單元、溢出判斷單元；還包括與第二交換單元相連的整體補償單元、與蝶形運算單元相連的運算信息預存rom單元、與第一交換單元相連的第一控制單元、與第二交換單元相連的第二控制單元；且所述溢出處理單元、溢出判斷單元均分別與所述處理結果存儲單元相連，所述整體補償單元還與共軛處理單元相連；所述溢出處理單元，用於在進行第2至n級蝶形運算時，根據上一級蝶形運算後設置的相應的溢出標誌位對當前蝶形運算的待處理數據進行溢出處理操作；所述第一控制單元，用於預存各級運算中所使用的第一交換標識信息，據此控制第一交換單元對當前的待處理數據進行交換或者還原操作；所述第一交換單元，用於對當前兩個待處理數據進行交換或還原操作後分別作為XJK)和X2(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；所述運算信息預存rom單元，用於預存各級蝶形運算中所使用的旋轉因子WNk;還用於存儲每級的運算結果在處理結果存儲單元中對應的存儲位置；所述蝶形運算單元，用於按照X(K)二&(K)士W;^(K)進行蝶形運算，並輸出運算結果X！(K)+WNkX2(K)和X！(K)-WNkX2(K);所述第二控制單元，用於預存各級運算中所使用的第二交換標識信息和運算結果的具體存儲地址信息，控制第二交換單元對當前的運算結果進行交換或者還原操作，並告知第二交換單元當前運算結果在處理結果存儲單元中預設的具體存儲地址；所述第二交換單元，用於在第1至n-l級蝶形運算過程中，對所述蝶形運算單元當前的兩個運算結果進行交換操作，之後將其送至溢出判斷單元或者整體補償單元；所述溢出判斷單元，用於在第1至n-l級蝶形運算過程中，判斷蝶形運算單元當前的兩個運算結果是否溢出，根據判斷結果設置相應的溢出標誌位並存儲，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述整體補償單元，用於在第n級蝶形運算過程中，根據之前各級的溢出處理操作時採用的縮小倍數對蝶形運算單元當前的運算結果進行數據放大補償，之後將運算結果送至所述共軛處理單元。—種實現快速傅立葉反變換的方法，該方法包括以下步驟a、確定當前進行快速傅立葉反變換運算的輸入數據的點數N，所述N等於2的n次■^^^;b、產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據，對所讀取的輸入數據進行共軛處理後自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將其分別寫入處理結果存儲單元的第一RAM存儲單元和第二RAM存儲單元；c、按照所述輸入數據的點數N進行n級迭代蝶形運算，在每級的每次蝶形運算過程中，從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；且在進行第n級蝶形運算時，對本級的運算結果進行共軛處理後再分別寫入第一RAM存儲單元和第二RAM存儲單元。其中，所述步驟c包括cl、從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；c2、對所讀取的兩個數據進行溢出處理及數據交換操作後分別作為&(K)和X2(K)10送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；c3、從運算信息預存rom單元中提取預存的本級運算中所使用的旋轉因子WNk，按照X(K)=&(K)±WNkX2(K)進行蝶形運算，並輸出運算結果&(K)+WNkX2(K)和XjK)-WNkX2(K);c4、對所述兩個運算結果進行數據交換及溢出判斷操作，根據判斷結果設置相應的溢出標誌位；c4、將所述運算結果分別存儲至第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，作為下一級蝶形運算的待處理數據；c5、重複步驟cl至c4，直至運行至第n級蝶形運算結束時，對本級的運算結果進行數據倍數的整體補償，並進行共軛處理。本發明具有以下有益效果1)本發明所提供的實現FFT/IFFT的硬體裝置對輸入數據流沒有苛刻的順序要求(如逆序輸入數據的需求，是通過本硬體裝置自身的內部功能設計來滿足的)，輸入、輸出數據流均為自然順序，便於讀取數據和輸出數據；且以ram的形式作為輸出數據接口，適合作時鐘域的切換。2)由於本發明通過將計算中的先驗信息(包括旋轉因子及對中間結運算結果數據的存儲寫控制信息)通過rom存儲起來，不用實時生成該部分信息；而且，由於整個裝置的數據計算採用完全流水的設計結構，n級N個數據的緩存和計算過程同時進行，時序整體協調，處理時間大為優化和縮短，因此，本發明非常適合於實時計算的應用場合。3)本發明採用了對FFT/IFFT中間運算結果優化存儲的策略通過設計rom—wraddr使得n級中間運算結果的存儲共用深度為N(與輸入數據個數相同)存儲單元即可，大大節省了存儲單元的開銷。4)本發明可以根據實際系統中硬體資源及時鐘資源的寬裕度，來選擇使用合適個數的蝶形運算單元同時進行運算；蝶形單元越多，運算的並行度越高，相應的中間結果的存儲策略複雜度增加，但整個模塊的計算耗費時間越少，因此本發明的硬體裝置設計比較靈活。5)本發明的硬體裝置通用性很強，便於實現，具有很強的實用性。圖1是TD-SCDMA系統信道估計計算處理中FFT/IFFT模塊的應用示意圖；圖2是本發明FFT/IFFT硬體裝置的結構示意圖；圖3是本發明的FFT/IFFT變換方法示意圖；圖4是並行度為1的FFT/IFFT裝置中的時鐘資源裕度示意圖；圖5是FFT/IFFT硬體裝置的詳細硬體設計示意圖。具體實施例方式下面結合附圖及具體實施例對本發明作進一步詳細的描述請參閱圖2，該圖所示為本發明FFT/IFFT硬體裝置的結構示意圖。假設當前需要處理的是N點(等於2的n次冪)輸入數據的FFT/IFFT運算，則11逆序讀取單元用於產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並自上而下地寫入處理結果存儲單元(ram—data)中，且每次僅讀取兩個輸入數據並將所讀取的兩數據分別寫入第一RAM存儲單元(ram_datal)和第二RAM存儲單元(r咖—data2)中；處理結果存儲單元ram_data:內部的存儲空間細分為2個大小一致的ram_datal單元和ram_data2單元，均用於存儲逆序讀取單元所讀取的輸入數據、中間運算結果或最終的運算結果；還用於提供對外接口，用以輸出最後一級運算的運算結果；共軛處理單元對IFFT來說，第一級的輸入數據及第n級的輸出數據，均需要進行共軛運算，所以在進行IFFT運算時，對第一級的輸入數據和第n級的輸出數據進行共軛運算，在進行FFT運算時，共軛處理單元不作處理；交換單元主要處理逐級運算中，考慮硬體實現中只能同時向一塊ram寫入一個數據、只能同時從一塊ram讀出一個數據，所以就存在逐級中間結果緩存策略的問題。框圖中的交換單元2用於對計算結果的存儲交換，交換網絡l用於對下一級蝶形運算輸入數據的交換或還原；控制單元框圖中的交換單元1用於預存各級運算中所使用的第一交換標識信息(Data—modify)，據此控制交換單元1對當前的待處理數據進行交換或者還原操作；控制單元2，用於預存各級運算中所使用的第二交換標識信息(Ex_en)和運算結果的具體存儲地址信息(Data—wraddr)，控制交換單元2對當前的運算結果進行交換或者還原操作，並告知交換單元2當前運算結果在處理結果存儲單元中預設的具體存儲地址；蝶形運算單元就是完成對X(K)=XJK)±WNkX2(K)的計算，包括複數乘法和複數加減。為了節省面積資源，採用(A+Bj)*(C+Dj)=[(A+B)*C-(C+D)*B]+j[(A+B)*C-(C-D)*A]—一3乘5加的複數乘法實現策略；運算信息預存rom單元主要用於存儲2部分信息，一是將逐級運算中用到的旋轉因子存儲在rom_w中，使用時候按照存儲地址區分W的數據；二是將1n級的每一級中間運算結果在ram_data存儲中的對應位置分布詳細信息存儲在rom_Wrdata中，以指示每一級、每一個數據應該寫向ram_data的某一個具體存儲單元；溢出判斷和處理單元溢出判斷主要是對每一級蝶形運算後的結果實虛部數值進行判斷，可以知道當前該級FFT/IFFT運算溢出了多少倍(以2的m次方為單位，比如溢出2倍、4倍，等等)，並用專門寄存器記錄下來；在緊接的下一級的計算開始位置，取數完畢、進行蝶形運算之前，進行相反地數據大小縮放，即將當前該級的所有數據均縮小相應倍數(也是2的m次方，比如縮小為1/2、1/4，等等)，以保證完整的n級FFT/IFFT運算，數據不會大幅度溢出失真，這就是溢出處理的子過程。當然，由於在每一級都可能有溢出情況，而在緊接的下一級做了數據的縮小操作，所以整個n級運算結束後，要將專門寄存器中保存的各級(1n級)倍數數值進行累加，進行這n級運算的數據放大補償，這是溢出處理的完整過程。另外由於IFFT運算中，除了2次共軛處理外，還有基於1/N這個係數倍數的數據縮放操作，這個也一併考慮到溢出處理操作中，通過右移n位即可實現。請參閱圖3，該圖所示為上述FFT/IFFT硬體裝置的數據處理過程301、逆序讀取確定當前FFT/IFFT多點運算的點數，比如N(2的n次冪大小)點FFT/IFFT。由逆序讀取單元產生逆序讀取地址，從自然順序的輸入數據流一次兩兩讀取數據，進入之後的共軛處理單元；302、共軛處理。如果當前進行的是IFFT運算，則對讀進來的數據進行共軛運算；否則，數據透明通過；303、存儲待處理數據。由於已經是通過逆序讀取進來的數據，符合FFT/IFFT運算的需要，故該部分數據存儲按照自上而下的順序存儲即可；304、溢出處理及數據交換。檢查上一級(對第一級來說，沒有上一級，自然也沒有溢出處理)運算中的溢出標誌位(overflow)，如果不為O，則需要進行右移操作(即縮小輸入數據為原來大小的1/2、1/4等)；數據交換，則是根據交換標識(Data—modify)對當前ram_data中讀取過來的2個數據做交換操作，即X(K)=&(K)±WNkX2(K)中的&有可能來自存儲前N/2個結果的存儲單元，也可能來自存儲後N/2個結果的存儲單元，同理對X2也是這樣，這個取決於拓補結構的選取和硬體存儲的策略。305、蝶形運算。經過前3步驟的處理後，當前輸入數據即為該級蝶形運算的合適數據，根據數學表達式進行相應的複數乘法、加減即可；306、數據交換及溢出判斷。首先判斷當前運算級別(class—cnt)，如果不是第n級運算，即不是FFT/IFFT運算的最後一級，則需要讓當前運算的中間結果經過交換單元2，根據交換標識Ex—en進行交換處理。這個主要是考慮到硬體設計中單口存儲單元存儲規則_不能同時往一個存儲單元寫入兩個數據、不能同時從一個存儲單元中讀取兩個數據。溢出判斷的同時，對指定專門寄存器進行賦值，以指示當前級FFT/IFFT運算數據有無溢出、溢出了多少倍數。307、在運行到第n級(即最後一級)之前，數據處理在303306這四個步驟中反覆循環；直到運行到最後一級FFT/IFFT，進行數據倍數的整體補償；並通過判斷當前是否進行IFFT運算是則進行共軛處理，否則將輸出數據至ram—data中，作為最終對外接口ram，提供FFT/IFFT運算的結果數據。以上就是本發明的FFT/IFFT硬體裝置對數據處理的詳細過程。經過該FFT/IFFT硬體裝置的計算處理，可以由自然順序的數據流輸入，得到最終還是自然順序的數據流輸出。在TD-SCDMA移動通信基帶處理系統的下行數據接收與碼片級數據解調過程中，首先需要根據接收到天線數據中midamble碼部分的偏移，初步對傳輸信道的信道係數做出估計計算，即基於小區的信道係數估計過程。在信道估計運算裡，首先就是對當前接收midamble碼的FFT變換，將接收到的時域數據轉換為頻域形式，以方便後續算法規定的數據處理流程；稍後的數據處理中，又需要將中間階段結果由頻域轉化為時域(IFFT)，以完成基於噪聲功率門限的小區有效徑判決過程，這裡就需要用到FFT/IFFT的運算處理。另外，由於TD-SCDMA移動通信基帶處理系統是基於時隙單位對數據進行處理的，所以作為下行數據處理的一部分，在以上的應用中，FFT/IFFT模塊的數據處理時間必須嚴格控制在一定的範圍之內，以保證在下一個時隙天線數據到來之前，完整完成當前時隙的所有數據處理。基於以上的實際設計要求，下面對FFT/IFFT裝置的硬體設計進行實際分析。第一、確定N點FFT/IFFT計算的N值，並確定蝶形運算單元的並行度模塊處理均基於接收天線數據midamble碼部分數據，即N=128，需要做7級FFT/IFFT的運算。TD-SCDMA協議中規定，必須在下一個時隙midamb1e碼到來之前完成當前時隙的小區信道估計過程，如圖4所示天線數據中數據域datal為352chips，中間碼midamble的區域為144chips，data2也是352chips，另外還有16chips的保護間隔GP。根據此原則，一個時隙內留給信道估計模塊的最多時鐘資源總數為352+16+352=720chips，，如藍線區域所示。假設採用32倍的時鐘頻率，則最多共有720x32=23040clks時鐘資源來完成所有四個小區的信道估計處理過程。通過分析算法描述可知，共需要做33次FFT/IFFT，而單個蝶形單元帶來的硬體設計耗費時鐘資源大概是(128/2)*7=448clks，448x33=14784<7，b000_0000，7，b000_0001->7，blOOJ)OOO，即為0_>0，1_>64，第1次讀出的數據；7，b000_0010->7，b010_000，7，b000_0011->7，bll0_0000，即為2_>32，3->96，第2次讀出的數據；7，b000_0100->7，b001_0000，7，b000_0101->7，bl01_0000，即為4->16，5->80，第3次讀出的數據......，等等，一直到7'blll_1110->7'b011_llll，7'blll_llll->7，bllljlll，即為126->63，127->127，第64次讀出的數據，從而完成了全部128個midamble數據的讀取過程。3、旋轉因子和對中間結果存儲寫控制信息FFT/IFFT中蝶型運算X(K)=X！(K)±WNkX2(K)，共完成7級(128點)FFT的運算過程。對128點時域數據的FFT變換蝶形運算分析後，可得出在每一級的蝶形運算中，WNk的值其變化規律如下、共64個；一倍數為W^°、W12832，如此反覆，共64個；一倍數為W12832〕、W12816、W12832、W12848，如此反覆，共64個;—倍數為W128160、W19S8、W,—"共64個"128W2"128Wi"128的值分別為-w12的值分別為-w12的值分別為-w12:的值分別為-w12倍數為W，8第五級w/的值分別為-w工第一級W,第二級W,第三級W,第四級W,第六級w/的值分別為-w工第七級w/的值分別為-w^W』4、W徴32、WJUU，如此反覆，.W1284、W1288……W1286°，如此反覆，共64個；一倍數為W1282，W1284……W12862，如此反覆，共64個「倍數為W，1，W1282……WC如此反覆，共64個。一倍數為基於硬體資源的總體考慮，以及相關參與運算信號產生的實時性要求，在硬體設14計上，採取把上述共7級蝶型運算用到的旋轉因子WNk的值，用運算信息預存rom單元(深度64*7=448)存儲起來，然後再在相應的運算周期按順序讀取並參與運算即可。中間結果存儲寫控制信息包括3個方面Datajiiodify，用於圖2框圖中交換單元l，告知每一次下一級蝶型運算的輸入數據是否需要進行相互調換位置；Ex—en，用於圖2框圖中交換單元2，告知每一次蝶型運算的輸出中間結果數據是否需要進行相互調換位置送至ram_data單元存儲；Data_wraddr用於指示逐級運算的中間結果應該寫向ram_data的哪一個具體存儲單元。對完整128點碼片數據的七級(Class_cnt[2:0]=0—6)、每級64(time_cnt)個蝶形運算過程，可用如下控制狀態表來確定Datajiiodify、Ex—en以及Data—wraddr的取值，如下表1:tableseeoriginaldocumentpage15tableseeoriginaldocumentpage16tableseeoriginaldocumentpage17表l上表為第一級FFT/IFFT變換所設計的中間結果存儲寫控制信息舉例，其他級數的FFT變換，其使用到的上述信息按照算法要求的運算過程給出即可，同上表類似。4、溢出判斷及處理單元首先說明數據溢出的判斷。在完成蝶形運算後，OverflowO-3分別對輸出的兩個複數結果數據的實部、虛部均進行是否溢出的判斷，如下(1)如當前被判斷的數據(實部或者虛部的數值)為正數一-即最高位符號位為0時，則對最高位的下一位進行判斷如為l，則表示溢出1位；如為O，則表示沒有溢出；(2)如當前被判斷的數據(實部或者虛部的數值)為負數-一即最高位符號位為1時，則對最高位的下一位進行判斷如為O，則表示溢出1位；如為l，則表示沒有溢出。然後對OverflowO-3各自輸出的2bits的數據進行或運算，即每個蝶形計算輸出的2個複數數據，只要有其中的任何一個實部或者虛部發生了溢出，則通過輸出本組數據對應的溢出操作控制信號Bitjiiodify，在下一次對該組數據讀出後、操作前，進行相應的移位處理。數據溢出的補償處理。在FFT/IFFT運算的第一級，數據初始輸入，沒有溢出處理，數據透明通過溢出處理單元。然後從第二級到最後一級，在每級數據輸入後、蝶型運算前，判斷上一級對運算的溢出操作控制信號Bit—modify進行判斷，如果為l，說明數據溢出1位，則對該級數據進行右移lbit;否則Bit—modify為0，說明上一級運算沒有溢出，輸入數據直接進入蝶型運算單元。以上即為FFT/IFFT內部的四個特定功能單元的設計和實現，其對數據處理的詳細硬體設計電路如圖5所示倒序讀入的兩個數據FFT_data_inl和FFT_data_in2，進入選擇單元，根據rom中固化的控制信息data_modify，來判斷FFT_data_inl和FFT_data_in2是否需要調換進入蝶型運算單元的數據位置；調整完畢後，進入溢出處理單元，根據上一級溢出操作控制信號Bitjiiodify，進行數據倍數大小的縮減控制；然後進入蝶型運算單元，與旋轉因子配合，進行複數乘法、加減的運算；然後順據進入溢出判斷單元，並對應置17位Bit_modify控制位，完成後就把該級計算結果回存到ram—data中，循環進行下一級的FFT/IFFT運算......如此反覆經過硬體電路，完整完成第17級的FFT/IFFT計算過程。整個模塊運算耗費時鐘數為485clks，最後總的模塊耗用時鐘資源19332clks(小於23040clks)，滿足設計需要；硬體電路規模為12.57k門，最高時鐘頻率99.372MHz，綜合報告如下表2:tableseeoriginaldocumentpage18表2本發明提供的技術方案克服了現有技術對硬體裝置要求過高且算法及處理複雜等缺陷，基本上只需按照上述思路，就可做出符合較高實時性要求的FFT/IFFT硬體電路，且節省了硬體資源及提高了系統的可靠性。以上實施例僅用以說明本發明的技術方案而非限制，僅僅參照較佳實施例對本發明進行了詳細說明。本領域的普通技術人員應當理解，可以對本發明的技術方案進行修改或者等同替換，而不脫離本發明技術方案的精神和範圍，均應涵蓋在本發明的權利要求範圍當中。權利要求一種實現快速傅立葉變換的硬體裝置，其特徵在於，該裝置包括依次相連的逆序讀取單元、處理結果存儲單元、運算單元；所述處理結果存儲單元，包括第一RAM存儲單元和第二RAM存儲單元；所述逆序讀取單元，用於產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將所讀取的兩數據分別寫入第一RAM存儲單元和第二RAM存儲單元中；所述第一RAM存儲單元和第二RAM存儲單元，均用於存儲所述逆序讀取單元所讀取的輸入數據、運算單元所執行的各級蝶形運算的運算結果；還用於提供對外接口，用以輸出運算結果；所述運算單元，用於按照所述輸入數據的點數N進行n級迭代的蝶形運算，在每級的每次蝶形運算過程中，從所述處理結果存儲單元讀取兩個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；所述N等於2的n次冪。2.如權利要求1所述的實現快速傅立葉變換的硬體裝置，其特徵在於，所述運算單元包括依次相連的溢出處理單元、第一交換單元、蝶形運算單元、第二交換單元、溢出判斷單元；還包括與第二交換單元相連的整體補償單元、與蝶形運算單元相連的運算信息預存rom單元、與第一交換單元相連的第一控制單元、與第二交換單元相連的第二控制單元；且所述溢出處理單元、溢出判斷單元、整體補償單元均分別與所述處理結果存儲單元相連；所述溢出處理單元，用於在進行第2至n級蝶形運算時，根據相應的溢出標誌位對當前蝶形運算的待處理數據進行溢出處理操作；所述第一控制單元，用於預存各級運算中所使用的第一交換標識信息，據此控制第一交換單元對當前的待處理數據進行交換或者還原操作；所述第一交換單元，用於對當前兩個待處理數據進行交換或還原操作後分別作為XJK)和&(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；所述運算信息預存rom單元，用於預存各級蝶形運算中所使用的旋轉因子WNk;還用於存儲各級的運算結果在處理結果存儲單元中對應的存儲位置；所述蝶形運算單元，用於獲取對應的旋轉因子W/，按照X(K)二^(K)士W/^(K)進行蝶形運算，並輸出運算結果formulaseeoriginaldocumentpage2所述第二控制單元，用於預存各級運算中所使用的第二交換標識信息和運算結果的具體存儲地址信息，控制第二交換單元對當前的運算結果進行交換或者還原操作，並告知第二交換單元當前運算結果在處理結果存儲單元中預設的具體存儲地址；所述第二交換單元，用於在第1至n-l級蝶形運算過程中，對所述蝶形運算單元當前的兩個運算結果進行交換或者還原操作，之後將其送至溢出判斷單元或者整體補償單元；所述溢出判斷單元，用於在第1至n-l級蝶形運算過程中，判斷蝶形運算單元當前的兩個運算結果是否溢出，根據判斷結果設置相應的溢出標誌位並存儲，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述整體補償單元，用於在第n級蝶形運算過程中，根據之前各級的溢出處理操作時採用的縮小倍數對蝶形運算單元當前的運算結果進行數據放大補償，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址。3.—種實現快速傅立葉變換的方法，其特徵在於，該方法包括以下步驟A、確定當前進行快速傅立葉變換運算的輸入數據的點數N，所述N等於2的n次冪；B、產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將讀取的兩數據分別寫入處理結果存儲單元的第一RAM存儲單元和第二RAM存儲單元；C、按照所述輸入數據的點數N進行n級迭代蝶形運算，在每級的每次蝶形運算過程中，從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，以作為下一級蝶形運算的待處理數據。4.如權利要求3所述的實現快速傅立葉變換的方法，其特徵在於，所述步驟C包括Cl、從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；C2、對所讀取的兩個數據進行溢出處理及數據交換操作後分別作為&(K)和X2(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；C3、從運算信息預存rom單元中提取預存的本級運算中所使用的旋轉因子W/，按照X(K)±WNkX2(K)進行蝶形運算，並輸出運算結果&(K)+W/X2(K)禾P&(K)_WNkX2(K);C4、對所述兩個運算結果進行數據交換及溢出判斷操作，根據判斷結果設置相應的溢出標誌位；C4、將所述運算結果分別存儲至第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，作為下一級蝶形運算的待處理數據；C5、重複步驟CI至C4，直至運行到第n級蝶形運算結束後，對本級的運算結果進行數據倍數的整體補償。5.—種實現快速傅立葉反變換的硬體裝置，其特徵在於，該裝置包括依次相連的逆序讀取單元、共軛處理單元、處理結果存儲單元、運算單元；所述處理結果存儲單元，包括第一RAM存儲單元和第二RAM存儲單元；所述逆序讀取單元，用於產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據並將所讀取的數據經共軛處理單元處理後自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將所讀取的兩數據經共軛處理單元處理後分別寫入第一RAM存儲單元和第二RAM存儲單元中；所述共軛處理單元，用於對逆序讀取單元所讀取的輸入數據進行共軛處理操作，還用於對第n級蝶形運算的運算結果進行共軛處理操作後寫入第一RAM存儲單元和第二RAM存儲單元；所述第一RAM存儲單元和第二RAM存儲單元，均用於存儲所述逆序讀取單元所讀取的經共軛處理的輸入數據、運算單元所執行的各級蝶形運算的運算結果；還用於提供對外接口，用以輸出運算結果；所述運算單元，用於按照所述輸入數據的點數N進行n級的蝶形運算，在每級的每次蝶形運算過程中，從所述處理結果存儲單元讀取兩個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；且在進行第n級蝶形運算時，將本級的運算結果經共軛處理單元處理後再分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述N等於2的n次冪。6.如權利要求5所述的實現快速傅立葉變換的硬體裝置，其特徵在於，所述運算單元包括依次相連的溢出處理單元、第一交換單元、蝶形運算單元、第二交換單元、溢出判斷單元；還包括與第二交換單元相連的整體補償單元、與蝶形運算單元相連的運算信息預存rom單元、與第一交換單元相連的第一控制單元、與第二交換單元相連的第二控制單元；且所述溢出處理單元、溢出判斷單元均分別與所述處理結果存儲單元相連，所述整體補償單元還與共軛處理單元相連；所述溢出處理單元，用於在進行第2至n級蝶形運算時，根據上一級蝶形運算後設置的相應的溢出標誌位對當前蝶形運算的待處理數據進行溢出處理操作；所述第一控制單元，用於預存各級運算中所使用的第一交換標識信息，據此控制第一交換單元對當前的待處理數據進行交換或者還原操作；所述第一交換單元，用於對當前兩個待處理數據進行交換或還原操作後分別作為XJK)和X2(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；所述運算信息預存rom單元，用於預存各級蝶形運算中所使用的旋轉因子WNk;還用於存儲每級的運算結果在處理結果存儲單元中對應的存儲位置；所述蝶形運算單元，用於按照X(K)二&(K)士W;^(K)進行蝶形運算，並輸出運算結果X丄(K)+WNkX2(K)和X丄(K)-WNkX2(K);所述第二控制單元，用於預存各級運算中所使用的第二交換標識信息和運算結果的具體存儲地址信息，控制第二交換單元對當前的運算結果進行交換或者還原操作，並告知第二交換單元當前運算結果在處理結果存儲單元中預設的具體存儲地址；所述第二交換單元，用於在第1至n-l級蝶形運算過程中，對所述蝶形運算單元當前的兩個運算結果進行交換操作，之後將其送至溢出判斷單元或者整體補償單元；所述溢出判斷單元，用於在第1至n-l級蝶形運算過程中，判斷蝶形運算單元當前的兩個運算結果是否溢出，根據判斷結果設置相應的溢出標誌位並存儲，之後將運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址；所述整體補償單元，用於在第n級蝶形運算過程中，根據之前各級的溢出處理操作時採用的縮小倍數對蝶形運算單元當前的運算結果進行數據放大補償，之後將運算結果送至所述共軛處理單元。7.—種實現快速傅立葉反變換的方法，其特徵在於，該方法包括以下步驟a、確定當前進行快速傅立葉反變換運算的輸入數據的點數N，所述N等於2的n次冪；b、產生逆序讀取過程的讀地址，按此讀地址逆序讀取自然順序的輸入數據，對所讀取的輸入數據進行共軛處理後自上而下地寫入處理結果存儲單元中，且每次僅讀取兩個輸入數據並將其分別寫入處理結果存儲單元的第一RAM存儲單元和第二RAM存儲單元；c、按照所述輸入數據的點數N進行n級迭代蝶形運算，在每級的每次蝶形運算過程中，從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；並將每級的運算結果分別寫入第一RAM存儲單元和第二RAM存儲單元中，以作為下一級蝶形運算的待處理數據；且在進行第n級蝶形運算時，對本級的運算結果進行共軛處理後再分別寫入第一RAM存儲單元和第二RAM存儲單元。8.如權利要求7所述的實現快速傅立葉反變換的方法，其特徵在於，所述步驟c包括cl、從所述第一RAM存儲單元和第二RAM存儲單元分別讀取一個數據作為當前蝶形運算的待處理數據；c2、對所讀取的兩個數據進行溢出處理及數據交換操作後分別作為&(K)和X2(K)送至蝶形運算單元，所述K表示本級運算中當前蝶形運算的次數；c3、從運算信息預存rom單元中提取預存的本級運算中所使用的旋轉因子WNk，按照X(K)±WNkX2(K)進行蝶形運算，並輸出運算結果&(K)+W/X2(K)禾P&(K)_WNkX2(K);c4、對所述兩個運算結果進行數據交換及溢出判斷操作，根據判斷結果設置相應的溢出標誌位；c4、將所述運算結果分別存儲至第一RAM存儲單元和第二RAM存儲單元中預設的具體存儲地址，作為下一級蝶形運算的待處理數據；c5、重複步驟cl至c4，直至運行至第n級蝶形運算結束時，對本級的運算結果進行數據倍數的整體補償，並進行共軛處理。全文摘要本發明公開了一種實現快速傅立葉變換、反變換的硬體裝置及方法，具體方法為A、確定當前進行FFT運算的輸入數據的點數N(N＝2n)；B、逆序讀取單元產生逆序讀取過程的讀地址，逆序讀取輸入數據並自上而下地寫入處理結果存儲單元中，且每次僅讀兩個輸入數據並將兩數據分別寫入RAM存儲單元1和2；C、運算單元進行n級迭代蝶形運算，在每級的每次蝶形運算過程中，從RAM存儲單元1和2分別讀取一數據作為當前的待處理數據；並將每級的運算結果分別寫入RAM存儲單元1和2預設的具體存儲地址，作為下一級運算的待處理數據。本發明對輸入數據流沒有苛刻的順序要求，適合於實時計算的應用場合，且節省了存儲單元的開銷，具有很強的實用性。文檔編號H04L25/03GK101729463SQ20081021707公開日2010年6月9日申請日期2008年10月24日優先權日2008年10月24日發明者古豔濤,孫映先申請人:中興通訊股份有限公司