TWI499969B - 重新調序緩衝器 - Google Patents

Description

重新調序緩衝器

本發明係有關一種重新調序緩衝器，尤指一種適用於連續流程快速傅立葉轉換運算之重新調序緩衝器。

目前快速傅利葉轉換(FFT)廣泛應用於有線及無線通訊系統及電子電機工程領域，具有極大之應用價值，但其運算複雜度極高。針對重新調序緩衝器之應用文獻上已有提出幾種能將資料流以自然順序讀出之方式。舉例來說，一種改良式多路徑延遲交換快速(Improved Multipath Delay Commutator)快速傅利葉轉換架構，其係將輸入資料流分為偶數索引(even-indexed)及奇數索引(odd-indexed)的資料流，再透過適當之排程進行每一級之蝶式運算(Butterfly Operation)；為達成自然順序之輸出，於最後一級基底運算單元前，加入一重新調序緩衝器(Reordering buffer)，將偶數索引資料流以位元反向寫入，自然順序讀出，而奇數索引資料流以自然順序寫入，位元反向讀出。惟，此架構只適用於單一資料流輸入及輸出，以致整體系統產出率(throughput)低。

此外，在實際應用上(如OFDM系統)，經常需要執行連續性(continuous-flow)之快速傅利葉轉換運算，以平行管線式快速傅利葉轉換處理器(Parallel Pipelined FFT Processor)為例，因具有高運算產出 (throughput)，所以被許多高速通訊系統所採用，但是一般管線式快速傅利葉轉換處理器之輸出具有位元反向(bit-reverse)特性，如果要使其轉變成自然順序之輸出，則需加上額外之重新調序緩衝器(Reordering buffer)。然而目前卻沒有任何技術能夠將平行管線式快速傅利葉轉換處理器輸出的位元反相輸出轉成自然順序的輸出，不是具有延遲問題，就是只能單一路徑輸入及輸出之技術窘境。再者，為了維持無延遲之快速傅利葉轉換計算輸出，必須要有足夠之暫存記憶體空間及高效能之資料存取機制，然而所需記憶體面積必須相當龐大，實無法讓整體系統架構縮小化；因此，如何設計一種新穎的重新調序緩衝器能夠在支援連續流程快速傅利葉轉換運算時，利用最小記憶體面積作為資料存取機制，並將平行管線式快速傅利葉轉換處理器輸出的位元反相輸出轉成自然順序的輸出是亟待解決的問題。

有鑑於此，本發明遂針對上述先前技術的缺失，提出一種重新調序緩衝器，以有效克服上述的該等問題。

本發明的主要目的在於提供一種重新調序緩衝器，其以最具面積效益之方式，使平行管線式快速傅利葉轉換處理器之位元反向輸出轉變成自然順序、連續、無延遲之輸出。

為達以上的目的，本發明提供一種重新調序緩衝器，包括一第一記憶體模組、一第二記憶體模組、一寫入交換器、一讀寫控制器及一讀取交換器。第一記憶體模組具有m個第一單埠記憶體單元，每一第一單埠記憶體單元儲存N/2m筆位元資料，N為傅立葉轉換之位元長度，m係為2的冪次方之整數；第二記憶體模組具有m個第二單埠記憶體單元，每一第二單 埠記憶體單元儲存N/2m筆位元資料。寫入交換器電性連接第一記憶體模組及第二記憶體模組，寫入交換器係接收m個傅立葉轉換之反向位元資料，並將反向位元資料交換為一預設排列方式之寫入位元資料，並交替寫入第一記憶體模組及該第二記憶體模組中。讀寫控制器電性連接寫入交換器、第一記憶體模組及第二記憶體模組，讀寫控制器係控制寫入位元資料寫入第一記憶體模組或第二記憶體模組中，或者是自第一記憶體模組或第二記憶體模組中讀出位元資料。讀取交換器電性連接第一記憶體模組、第二記憶體模組及讀寫控制器，讀取交換器係交替將第一記憶體模組及第二記憶體模組內的位元資料分別交換為自然順序之輸出位元資料，並以m個輸出路徑將輸出位元資料輸出。本發明所設計新穎的重新調序緩衝器架構，不僅可支援m倍平行快速傅利葉轉換輸入輸出，又能適用於連續流程快速傅利葉轉換運算(continuous-flow FFT operation)，能使所有需要用到快速傅利葉轉換運算的通訊產品具有更高運算產出之應用價值。

底下藉由具體實施例詳加說明，當更容易瞭解本發明的目的、技術內容、特點及其所達成的功效。

10‧‧‧第一記憶體模組

12‧‧‧第二記憶體模組

14‧‧‧寫入交換器

16‧‧‧讀寫控制器

18‧‧‧讀取交換器

20‧‧‧平行管線式快速傅立葉轉換處理器

22‧‧‧多工器

第1圖為本發明的電路方塊圖。

第2A~2E圖本發明以128位元長度交換為自然順序輸出之實施例示意圖。

第3圖為本發明之寫入交換器的交換模式示意圖。

第4A~4E圖為本發明以256位元長度交換為自然順序輸出之實施例 示意圖。

請參閱第1圖，為本發明的電路方塊圖。重新調序緩衝器一第一記憶體模組10、一第二記憶體模組12、一寫入交換器14、一讀寫控制器16及一讀取交換器18。寫入交換器14電性連接第一記憶體模組10及第二記憶體模組12；讀寫控制器16電性連接寫入交換器14、第一記憶體模組10及第二記憶體模組12；讀取交換器18電性連接第一記憶體模組10、第二記憶體模組12及讀寫控制器16。第一記憶體模組10具有m個第一單埠記憶體單元，每一第一單埠記憶體單元儲存N/2m筆位元資料，N為傅立葉轉換之位元長度，m係為2的冪次方之整數。第二記憶體模組12具有m個第二單埠記憶體單元，每一第二單埠記憶體單元儲存N/2m筆位元資料。寫入交換器14係每次m個筆傅立葉轉換之反向位元資料，此反向位元資料係由一平行管線式快速傅立葉轉換處理器20輸出，且平行管線式快速傅立葉轉換處理器(parallel pipelined FFT processor)20電性連接寫入交換器14。其中，寫入交換器14係將反向位元資料交換為一預設排列方式之寫入位元資料，並交替寫入第一記憶體模組10及第二記憶體模組12中。讀寫控制器16係控制寫入位元資料寫入第一記憶體模組或第二記憶體模組中，或者是自第一記憶體模組10或第二記憶體模組12中讀出位元資料。讀取交換器18係交替將第一記憶體模組10及第二記憶體模組12內的位元資料分別交換為自然順序之輸出位元資料，並以m個輸出路徑將輸出位元資料輸出。重新調序緩衝器更包括一多工器22，電性連接第一記憶體模組10、第二記憶體模組12及讀取交換器18，第一記憶體模組10及第二記憶體模組12中的位元資料係由多工 器22選擇輸出，讀取交換器18係接收多工器22所輸出之位元資料以交換為自然順序之輸出位元資料。

為能進一步說明如何將平行管線式快速傅立葉轉換處理器輸出的反向位元資料交換為自然順序之輸出位元資料，本發明將交換模式根據快速傅立葉轉換(FFT)長度N分為兩種型式，且適用於任意2的冪次方點數，如後說明。寫入交換器14或讀取交換器18分別根據傅立葉轉換之位元長度N而選擇以交替公式將寫入位元資料寫入第一記憶體模組10或第二記憶體模組12，或自第一記憶體模組10或第二記憶體模組12中讀出位元資料，交替公式(1)如下所示：α =log₂ (N /2m ² ).....(1)

其中，α係為整數，N為傅立葉轉換之位元長度，m係為偶數，亦即為平行管線式快速傅立葉轉換處理器20輸出的平行度數目。

後續將詳細說明α 為偶數及奇數之兩種讀寫排程模式。首先，先以α 為偶數為例說明，請同時參閱第1圖、第2A~2E圖及第3圖，第2A~2E圖為本發明N為128位元長度交換為自然順序輸出之實施例示意圖，第3圖為本發明之寫入交換器的交換模式示意圖。當傅立葉轉換之位元長度N為128，其經過m為8倍平行的平行管線式快速傅立葉轉換處理器20後輸出128點的反向位元資料，α 係為偶數，則實施第一種交換模式；詳言之，寫入交換器14係將反向位元資料以各寫入一次之交替方式處理後，將寫入位元資料寫入第一記憶體模組10及第二記憶體模組12中，讀出交換器18係以各讀出一次之交替方式自第一記憶體模組10及第二記憶體模組12中讀出位元資料。首先，如第2A所示，為本發明之位元長度128點經8倍平行管線式 快速傅立葉轉換處理器20後之輸出示意圖。寫入交換器14係根據一預設排列方式選定之控制訊號進行交換反向位元資料，預設排列方式選定之控制訊號係由時脈計數器(clock cycle counter)來產生每一個記憶體之位址，預設排列方式與傅立葉轉換之位元長度N有關。傅立葉轉換之位元長度N為128，其分為16組八個位元參數，例如16組編號為C0~C15。再如第2B圖所示，為本發明之128點的反向位元資料經寫入交換器交換後之輸出；寫入交換器14係將反向位元資料中每兩組的八個位元參數以八種排列方式，例如八種排列的編號為CROT(0)~CROT(7)，而每一種排列方式係遵循第3圖的CROT(0)~CROT(7)八種寫入交換模式進行交換，將反向位元資料交換為寫入位元資料，並將寫入位元資料交替寫入第一記憶體模組10及第二記憶體模組12中。再如第2C、第2D及2E圖所示，第2C、第2D分別為本發明之讀寫排程示意圖及本發明儲存寫入位元資料於記憶體中之示意圖；其中2D為奇數訊框(frame)時之儲存分怖，2E為偶數訊框時之儲存分怖，此處訊框係一周期為(N/m)之區間，並假設從一計數。第一記憶體模組10具有m個第一單埠記憶體單元，若m為8，則8組第一單埠記憶體單元為Bank_A0~Bank_A7，由於每一第一單埠記憶體單元儲存N/2m筆位元資料，因此每一個第一單埠記憶體單元具有8個儲存位址。同理，第二記憶體模組12具有m個第二單埠記憶體單元，若m為8，則8個第二單埠記憶體單元為Bank_B0~Bank_B7，由於每一第二單埠記憶體單元儲存N/2m筆位元資料，因此每一個第二單埠記憶體單元具有8個儲存位址。

暸解上述每一個元件之間的相對關係之後，接下來以實際運作為例詳細說明，寫入交換器14係將反向位元資料中每兩組的八個位元參 數以八種排列方式，其順序為CROT(0)、CROT(4)、CROT(2)、CROT(6)、CROT(1)、CROT(5)、CROT(3)、CROT(7)。詳言之，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C0[0,64,32,96,16,80,48,112]及C1[8,72,40,104,24,88,56,120]以CROT(0)的排列方式進行交換，其交換模式係將第一組的八個位元參數[0,64,32,96,16,80,48,112]平行輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第一個位址A0，第二組的八個位元參數[8,72,40,104,24,88,56,120]平行輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第一個位址B0，且每一第一單埠記憶體單元及每一第二單埠記憶體單元中的第一個單埠記憶體單元係作為位移的初始單埠記憶體單元。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C2[4,68,36,100,20,84,52,116]及C3[12,76,44,108,28,92,60,124]以CROT(4)的排列方式進行交換；其交換模式是將第三組的八個位元參數自初始單埠記憶體單元位移四個單埠記憶體單元後，八個位元參數排列為[20,84,52,116,4,68,36,100]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第二個位址A1；將第四組的八個位元參數自初始單埠記憶體單元位移四個單埠記憶體單元後，八個位元參數排列為[28,92,60,124,12,76,44,108]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第二個位址B1。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C4[2,66,34,98,18,82,50,114]及C5[10,74,42,106,26,90,58,122] 以CROT(2)的排列方式進行交換；其交換模式是將第五組的八個位元參數自初始單埠記憶體單元位移兩個單埠記憶體單元後，八個位元參數排列為[50,114,2,66,34,98,18,82]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第三個位址A2；將第六組的八個位元參數自初始單埠記憶體單元位移兩個單埠記憶體單元後，八個位元參數排列為[58,122,10,74,42,106,26,90]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第三個位址B2。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C6[6,70,38,102,22,86,54,118]及C7[14,78,46,110,30,94,62,126]以CROT(6)的排列方式進行交換；其交換模式是將第七組的八個位元參數自初始單埠記憶體單元位移六個單埠記憶體單元後，八個位元參數排列為[38,102,22,86,54,118,6,70]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第四個位址A3；將第八組的八個位元參數自初始單埠記憶體單元位移六個單埠記憶體單元後，八個位元參數排列為[46,110,30,94,62,126,14,78]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第四個位址B3。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C8[1,65,33,97,17,81,49,113]及C9[9,73,41,105,25,89,57,121]以CROT(1)的排列方式進行交換；其交換模式是將第九組的八個位元參數自初始單埠記憶體單元位移一個單埠記憶體單元後，八個位元參數排列為[113,1,65,33,97,17,81,49]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第五個位址A4；將第十組的八個位元參數自初始單埠記憶體 單元位移一個單埠記憶體單元後，八個位元參數排列為[121,9,73,41,105,25,89,57]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第五個位址B4。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C10[5,69,37,101,21,85,53,117]及C11[13,77,45,109,29,93,61,125]以CROT(5)的排列方式進行交換；其交換模式是將第十一組的八個位元參數自初始單埠記憶體單元位移五個單埠記憶體單元後，八個位元參數排列為[101,21,85,53,117,5,69,37]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第六個位址A5；將第十二組的八個位元參數自初始單埠記憶體單元位移五個單埠記憶體單元後，八個位元參數排列為[109,29,93,61,125,13,77,45]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第六個位址B5。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C12[3,67,35,99,19,83,51,115]及C13[11,75,43,107,27,91,59,123]以CROT(3)的排列方式進行交換；其交換模式是將第十三組的八個位元參數自初始單埠記憶體單元位移三個單埠記憶體單元後，八個位元參數排列為[83,51,115,3,67,35,99,19]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第七個位址A6；將第十四組的八個位元參數自初始單埠記憶體單元位移三個單埠記憶體單元後，八個位元參數排列為[91,59,123,11,75,43,107,27]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第七個位址B6。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20 之反向位元資料C14[7,71,39,103,23,87,55,119]及C16[15,79,47,111,31,95,63,127]以CROT(7)的排列方式進行交換；其交換模式是將第十五組的八個位元參數自初始單埠記憶體單元位移七個單埠記憶體單元後，八個位元參數排列為[71,39,103,23,87,55,119,7]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第八個位址A7；將第十六組的八個位元參數自初始單埠記憶體單元位移七個單埠記憶體單元後，八個位元參數排列為[79,47,111,31,95,63,127,15]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第八個位址B7。

其中，寫入交換器14將128點的反向位元資料全部交換為寫入位元資料，並交替寫入第一記憶體模組10及第二記憶體模組12中之後，由多工器選擇輸出第一記憶體模組10及第二記憶體模組12中的位元資料，例如，選擇將Bank_A0~Bank_A7中的位元資料0~7輸出(如第2D圖的虛框所示)，再由讀取交換器18將0~7位元資料交換為自然順序由0至7排列之輸出位元資料；接著交替選擇將Bank_B0~Bank_B7中的位元資料8~15輸出(如第2D圖的虛框所示)，再由讀取交換器18將8~15位元資料交換為自然順序由8至15排列之輸出位元資料。再如第2E圖，為讀取交換器18將128位元資料交換為自然順序輸出的輸出位元資料，並呈現於另兩組記憶體模組GroupA、GroupB中，例如GroupA中的Bank_A0~Bank_A7的第一個位址會依序排列為0~7的位元，而GroupB中的Bank_B0~Bank_B7的第一個位址會依序排列為8~15的位元；Bank_A0~Bank_A7第二個位址會依序16~23的位元，而GroupB中的Bank_B0~Bank_B7的第二個位址會依序排列為24~31的位元，以此類推依序將128點位元資料全部以自然順序讀出。此時，當將 GroupA中的0~7位元輸出至下一級的功能端，空出的位址即能由寫入交換器14繼續寫入下一筆128點的反向位元資料。由於只要空出位址即能寫入下一筆位元資料，因此第一記憶體模組10寫入時，第二記憶體模組12則讀出，以交替讀/寫方式就能夠使平行管線式快速傅利葉轉換處理器之位元反向輸出轉變成自然順序、連續、無延遲之輸出，進而提高輸出效率。

接著，以α 為奇數為例說明，請同時參閱第1圖、第3圖及4A~4E圖，第4A~4E圖為本發明以256位元長度交換為自然順序輸出之實施例示意圖。當傅立葉轉換之位元長度N為256，其經過m為8倍平行的平行管線式快速傅立葉轉換處理器20後輸出256點的反向位元資料，由於α 係為奇數，故實施第二種交換模式；詳言之，寫入交換器14首次先將寫入位元資料寫入於第一記憶體模組10一次，接著以各寫入兩次之交替方式將寫入位元資料寫入第二記憶體模組12及第一記憶體模組10中，讀出交換器18係以各讀出一次之交替方式自第一記憶體模組10及第二記憶體模組12中讀出位元資料。如第4A所示，為本發明之位元長度256點經8倍平行管線式快速傅立葉轉換處理器20後之輸出示意圖。寫入交換器14係根據預設排列方式選定之控制訊號進行交換該反向位元資料，傅立葉轉換之位元長度為256，其分為32組八個位元參數，例如32組編號為C0~C31。再如第4B圖所示，為本發明之256點的反向位元資料經寫入交換器交換後之輸出；寫入交換器14係將反向位元資料中每四組的八個位元參數以八種排列方式，例如八種排列的編號為CROT(0)~CROT(7)，而每一種排列方式係遵循第3圖的CROT(0)~CROT(7)八種寫入交換模式進行交換，由寫入交換器14將反向位元資料交換為預設排列方式之寫入位元資料，並將寫入位元資料交替寫入 第一記憶體模組10及第二記憶體模組12中。再如第4C、第4D及4E圖所示，第4C、第4D分別為本發明之讀寫排程示意圖及本發明儲存寫入位元資料於至記憶體中之示意圖；第一記憶體模組10具有m個第一單埠記憶體單元，若m為8，則8組第一單埠記憶體單元為Bank_A0~Bank_A7，由於每一第一單埠記憶體單元儲存N/2m筆位元資料，因此每一個第一單埠記憶體單元具有16個儲存位址。同理，第二記憶體模組12具有m個第二單埠記憶體單元，若m為8，則8個第二單埠記憶體單元為Bank_B0~Bank_B7，由於每一第二單埠記憶體單元儲存N/2m筆位元資料，因此每一個第二單埠記憶體單元具有16個儲存位址。

暸解上述每一個元件之間的相對關係之後，接下來以實際運作為例詳細說明，寫入交換器14係將反向位元資料以八種排列方式，其順序為CROT(0)、CROT(4)、CROT(2)、CROT(6)、CROT(1)、CROT(5)、CROT(3)、CROT(7)，如後說明。

首先，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C0[0,128,64,192,32,160,96,224]、C1[16,144,80,208,48,176,112,240]、C2[8,136,72,200,40,168,104,232]及C3[24,152,88,216,56,184,120,248]以CROT(0)的排列方式進行交換，其交換模式係將第一組的八個位元參數[0,128,64,192,32,160,96,224]及第四組的八個位元參數[24,152,88,216,56,184,120,248]分別平行輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第一個位址A0及第四個位址A1，第二組的八個位元參數[8,136,72,200,40,168,104,232]及第三組的八個位元參數[24,152,88,216,56,184,120,248]分別平行輸入至八組第二單埠記憶體單元 Bank_B0~Bank_B7中的第一個位址B0及第二個位址B1，且每一第一單埠記憶體單元及每一第二單埠記憶體單元中的第一個單埠記憶體單元係作為位移的初始單埠記憶體單元。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C4[4,132,68,196,36,164,100,228]、C5[20,148,84,212,52,180,116,244]、C6[12,140,76,204,44,172,108,236]及C7[28,156,92,220,60,188,124,252]以CROT(4)的排列方式進行交換；其交換模式是將第五組及第八組的八個位元參數自初始單埠記憶體單元位移四個單埠記憶體單元後，第五組的八個位元參數排列為[36,164,100,228,4,132,68,196]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第三個位址A2；第八組的八個位元參數排列為[60,188,124,252,28,156,92,220]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第四個位址A3。將第六組及第七組的八個位元參數自初始單埠記憶體單元位移四個單埠記憶體單元後，第六組的八個位元參數排列為[52,180,116,244,20,148,84,212]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第三個位址B2；第七組的八個位元參數排列為[44,172,108,236,12,140,76,204]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第四個位址B3。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C8[2,130,66,194,34,162,98,226]、C9[18,146,82,210,50,178,114,242]、C10[10,138,74,202,42,170,106,234]及C11[26,154,90,218,58,186,122,250]以CROT(2)的排列方式進行交換；其交 換模式是將第九組及第十二組的八個位元參數自初始單埠記憶體單元位移兩個單埠記憶體單元後，第九組的八個位元參數排列為[98,226,2,130,66,194,34,162]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第五個位址A4；第十二組的八個位元參數排列為[122,250,26,154,90,218,58,186]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第六個位址A5。將第十組及第十一組的八個位元參數自初始單埠記憶體單元位移兩個單埠記憶體單元後，第十組的八個位元參數排列為[114,242,18,146,82,210,50,178]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第五個位址B4；第十一組的八個位元參數排列為[106,234,10,138,74,202,42,170]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第六個位址B5。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C12[6,134,70,198,38,166,102,230]、C13[22,150,86,214,54,182,118,246]、C14[14,142,78,206,46,174,110,238]及C15[30,158,94,222,62,190,126,254]以CROT(6)的排列方式進行交換；其交換模式是將第十三組及第十六組的八個位元參數自初始單埠記憶體單元位移六個單埠記憶體單元後，第十三組的八個位元參數排列為[70,198,38,166,102,230,6,134]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第七個位址A6；第十六組的八個位元參數排列為[94,222,62,190,126,254,30,158]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第八個位址A7。將第十四組及第十五組的八個位元參數自初始單埠記憶體單元位移六個單埠記憶體單元後，第十四組的八個 位元參數排列為[86,214,54,182,118,246,22,150]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第七個位址B6；第十五組的八個位元參數排列為[78,206,46,174,110,238,14,142]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第八個位址B7。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C16[1,129,65,193,33,161,97,225]、C17[17,145,81,209,49,177,113,241]、C18[9,137,73,201,41,169,105,233]及C19[25,153,89,217,57,185,121,249]以CROT(1)的排列方式進行交換；其交換模式是將第十七組及第二十組的八個位元參數自初始單埠記憶體單元位移一個單埠記憶體單元後，第十七組的八個位元參數排列為[225,1,129,65,193,33,161,97]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第九個位址A8；第二十組的八個位元參數排列為[249,25,153,89,217,57,185,121]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十個位址A9。將第十八組及第十九組的八個位元參數自初始單埠記憶體單元位移一個單埠記憶體單元後，第十八組的八個位元參數排列為[241,17,145,81,209,49,177,113]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第九個位址B8；第十九組的八個位元參數排列為[233,9,137,73,201,41,169,105]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十個位址B9。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C20[5,133,69,197,37,165,101,229]、C21[21,149,85,213,53,181,117,245]、C22[13,141,77,205,45,173,109,237]及 C23[29,157,93,221,61,189,125,253]以CROT(5)的排列方式進行交換；其交換模式是將第二十一組及第二十四組的八個位元參數自初始單埠記憶體單元位移五個單埠記憶體單元後，第二十一組的八個位元參數排列為[197,37,165,101,229,5,133,69]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十一個位址A10；第二十四組的八個位元參數排列為[221,61,189,125,253,29,157,93]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十二個位址A11。將第二十二組及第二十三組的八個位元參數自初始單埠記憶體單元位移五個單埠記憶體單元後，第二十二組的八個位元參數排列為[213,53,181,117,245,21,149,85]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十一個位址B10；第二十三組的八個位元參數排列為[205,45,173,109,237,13,141,77]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十二個位址B11。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C24[3,131,67,195,35,163,99,227]、C25[19,147,83,211,51,179,115,243]、C26[11,139,75,203,43,171,107,235]及C27[27,155,91,219,59,187,123,251]以CROT(3)的排列方式進行交換；其交換模式是將第二十五組及第二十八組的八個位元參數自初始單埠記憶體單元位移三個單埠記憶體單元後，第二十五組的八個位元參數排列為[163,99,227,3,131,67,195,35]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十三個位址A12；第二十八組的八個位元參數排列為[187,123,251,27,155,91,219,59]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十四個位址A13。將第二十六組及第二十七組的 八個位元參數自初始單埠記憶體單元位移三個單埠記憶體單元後，第二十六組的八個位元參數排列為[179,115,243,19,147,83,211,51]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十三個位址B12；第二十七組的八個位元參數排列為[171,107,235,11,139,75,203,43]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十四個位址B13。

接續，寫入交換器14將平行管線式快速傅立葉轉換處理器20之反向位元資料C28[7,135,71,199,39,167,103,231]、C29[23,151,87,215,55,183,119,247]、C30[15,143,79,207,47,175,111,239]及C31[31,159,95,223,63,191,127,255]以CROT(7)的排列方式進行交換；其交換模式是將第二十九組及第三十二組的八個位元參數自初始單埠記憶體單元位移七個單埠記憶體單元後，第二十九組的八個位元參數排列為[135,71,199,39,167,103,231,7]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十五個位址A14；第三十二組的八個位元參數排列為[159,95,223,63,191,127,255,31]，並輸入至八組第一單埠記憶體單元Bank_A0~Bank_A7中的第十六個位址A15。將第三十組及第三十一組的八個位元參數自初始單埠記憶體單元位移七個單埠記憶體單元後，第三十組的八個位元參數排列為[151,87,215,55,183,119,247,23]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十五個位址B14；第三十一組的八個位元參數排列為[143,79,207,47,175,111,239,15]，並輸入至八組第二單埠記憶體單元Bank_B0~Bank_B7中的第十六個位址B15。

其中，寫入交換器14將256點的反向位元資料全部交換為寫入位元資料，由時脈計數器(clock cycle counter)將每4個clock cycle變換一 次交換模式，並交替寫入第一記憶體模組10及第二記憶體模組12中；因此，平行管線式快速傅立葉轉換處理器20輸出的256點反向位元資料與128點反向位元資料的讀寫排程不同，主要是根據快速傅立葉轉換的長度與平行度來決定。之後，由多工器選擇輸出第一記憶體模組10及第二記憶體模組12中的位元資料，例如於反向位元資料C30時，則選擇第一記憶體模組10中的Bank_A0~Bank_A7開始將第一筆資料輸出(如第4D圖的虛框所示)，再由讀取交換器18將0~7位元資料交換為自然順序由0至7排列之輸出位元資料；接著選擇將Bank_B0~Bank_B7中的位元資料8~15及16~23輸出(如第4D圖的虛框所示)，再由讀取交換器18將8~15及16~23位元資料交換為自然順序由8至15排列及16至23排列之輸出位元資料；再連續自Bank_A0~Bank_A7中輸出兩筆位元資料24~31及32~39，由讀取交換器18將24~31及32~39位元資料交換為自然順序由24至31排列及32至39排列之輸出位元資料，依此規律持續進行，直到將256點的位元資料全部輸出為止。其中，寫入的交換模式與讀取的交換模式是類似的。再如第2E圖，為讀取交換器18將256位元資料交換為自然順序輸出的輸出位元資料，並呈現於另兩組記憶體模組GroupA、GroupB中，例如GroupA中的Bank_A0~Bank_A7的第一個位址會依序排列為0~7的位元，而GroupB中的Bank_B0~Bank_B7的第一個位址會依序排列為8~15的位元，第二個位址會依序排列為16~23的位元；Bank_A0~Bank_A7第二個位址會依序24~31的位元及第三個位址會依序32~39的位元，以此類推依序將256點位元資料全部以自然順序讀出。此時，當將GroupA中的0~7位元輸出至下一級的功能端，空出的位址即能由寫入交換器14繼續寫入下一筆256點的反向位元資料。由於只要空出位址即 能寫入下一筆位元資料，因此第一記憶體模組10寫入時，第二記憶體模組12則讀出，以交替讀/寫方式就能夠使平行管線式快速傅利葉轉換處理器之位元反向輸出轉變成自然順序、連續、無延遲之輸出，進而提高輸出效率。

其中，本發明是針對平行管線式傅立葉轉換處理器的位元反向輸出，轉成自然順序輸出之重新調序緩衝器架構的新設計，因此以交替公式(1)計算出α 為偶數或奇數，皆能利用上述特殊的讀寫排程來支援快速傅立葉轉換的運算，並搭配兩群單埠第一記憶體模組與第二記液體模組完成自然順序輸出功能。

綜上所述，本發明之重新調序緩衝器的記憶體寫入/讀取位址之產生具有相當規律性，利用一個時脈計數器來產生每一個記憶體之位址，而寫入位址之產生方式是依據當時快速傅立葉轉換的位元長度以交替公式(1)計算出為是奇數或偶數而有所不同，而每一快速傅立葉轉換的位元長度的周期為N/m。假設快速傅立葉轉換的位元長度是從1開始計數，則於奇數符元期間，經由寫入交換器交換後之各路資料便會開始填入第一記憶體模組或是第二記憶體模組，而且從位址0開始依序寫入，每次寫入後，第一記憶體模組或第二記憶體模組之記憶體位址便加1。至於在每一個時脈時是寫入第一記憶體模組或是第二記憶體模組，則須依據快速傅利葉轉換之長度與平行度來決定。而於偶數符元時，此時經由寫入交換器交換後之各路資料會寫入在前一個快速傅立葉轉換的位元長度與其呈現位元反向之資料所在之位置。更進一步而言，本發明設計一種能夠執行連續性的快速傅立葉轉換之運算，且在支援連續流程快速傅立葉轉換運算時，僅需要大小為N的單埠記憶體，對於整體的系統架構設計來說，極具最小面積使用效 益，且將多倍的資料平行輸入與輸出，具有極高的運算產出功效，對於應用於有線及無線通訊系統及電子電機工程領域具有極大的應用價值。

唯以上所述者，僅為本發明的較佳實施例而已，並非用來限定本發明實施的範圍。故凡依本發明申請範圍所述的特徵及精神所為的均等變化或修飾，均應包括於本發明的申請專利範圍內。

10‧‧‧第一記憶體模組

12‧‧‧第二記憶體模組

14‧‧‧寫入交換器

16‧‧‧讀寫控制器

18‧‧‧讀取交換器

20‧‧‧平行管線式快速傅立葉轉換處理器

22‧‧‧多工器

Claims (8)

1. 一種重新調序緩衝器，包括：一第一記憶體模組，具有m個第一單埠記憶體單元，每一該第一單埠記憶體單元儲存N/2m筆位元資料，N為傅立葉轉換之位元長度，m係為2的冪次方；一第二記憶體模組，具有m個第二單埠記憶體單元，每一該第二單埠記憶體單元儲存N/2m筆位元資料；一寫入交換器，電性連接該第一記憶體模組及該第二記憶體模組，該寫入交換器係接收2的冪次方傅立葉轉換之反向位元資料，並將該反向位元資料交換為一預設排列方式之寫入位元資料，並交替寫入該第一記憶體模組及該第二記憶體模組中；一讀寫控制器，電性連接該寫入交換器、該第一記憶體模組及該第二記憶體模組，該讀寫控制器係控制該寫入位元資料寫入該第一記憶體模組或該第二記憶體模組中，或者是自該第一記憶體模組或該第二記憶體模組中讀出該位元資料；及一讀取交換器，電性連接該第一記憶體模組、該第二記憶體模組及該讀寫控制器，該讀取交換器係交替將該第一記憶體模組及該第二記憶體模組內的該位元資料分別交換為自然順序之輸出位元資料，並以m個輸出路徑將該輸出位元資料輸出。
2. 如請求項1所述的重新調序緩衝器，其中該寫入交換器或該讀取交換器分別根據該傅立葉轉換之位元長度N而選擇以交替公式將該寫入位元資料寫入該第一記憶體模組或該第二記憶體模組，或自該第一記憶體模組 或該第二記憶體模組中讀出該位元資料，該交替公式如下所示：α =log₂ (N /2m ² )其中，α 係為整數，N為傅立葉轉換之位元長度，m係為2的冪次方。
3. 如請求項2所述的重新調序緩衝器，其中該α 係為偶數，則該寫入交換器係以各寫入一次之交替方式將該寫入位元資料寫入該第一記憶體模組及該第二記憶體模組中，該讀出交換器係以各讀出一次之交替方式自該第一記憶體模組及該第二記憶體模組中讀出該位元資料。
4. 如請求項3所述的重新調序緩衝器，其中該寫入交換器係根據該預設排列方式選定之控制訊號進行交換該反向位元資料，該傅立葉轉換之位元長度為128時，其分為16組八個位元參數，將該反向位元資料中每兩組的八個位元參數以八種排列方式，交換為該寫入位元資料，並將該寫入位元資料交替寫入該第一記憶體模組及該第二記憶體模組中；其中該八種排列方式的順序為：第一組及第二組的八個位元參數分別平行輸入至八組該第一單埠記憶體單元及該第二單埠記憶體單元中，且每一該第一單埠記憶體單元及每一該第二單埠記憶體單元中的第一個單埠記憶體單元係作為位移的初始單埠記憶體單元；第三組及第四組的八個位元參數分別自該初始單埠記憶體單元位移四個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中；第五組及第六組的八個位元參數分別自該初始單埠記憶體單元位移兩個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記 憶體單元中；第七組及第八組的八個位元參數分別自該初始單埠記憶體單元位移六個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中；第九組及第十組的八個位元參數分別自該初始單埠記憶體單元位移一個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中；第十一組及第十二組的八個位元參數分別自該初始單埠記憶體單元位移五個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中；第十三組及第十四組的八個位元參數分別自該初始單埠記憶體單元位移三個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中；及第十五組及第十六組的八個位元參數分別自該初始單埠記憶體單元位移七個單埠記憶體單元並輸入至該八組第一單埠記憶體單元及該第二單埠記憶體單元中。
5. 如請求項2所述的重新調序緩衝器，其中該α 係為奇數，則該寫入交換器首次先寫入該寫入位元資料於該第一記憶體模組一次，接著以各寫入兩次之交替方式將該寫入位元資料寫入該第二記憶體模組及該第一記憶體模組中，該讀出交換器係以各讀出一次之交替方式自該第一記憶體模組及該第二記憶體模組中讀出該位元資料。
6. 如請求項5所述的重新調序緩衝器，其中該寫入交換器係根據該預設排列 方式選定之控制訊號進行交換該反向位元資料，該傅立葉轉換之位元長度為256時，其分為32組八個位元參數，將該反向位元資料中每四組的八個位元參數以八種排列方式，交換為該預設排列方式之該寫入位元資料，並將該寫入位元資料交替寫入該第一記憶體模組及該第二記憶體模組中；其中該八種排列方式的順序為：第一組及第四組的八個位元參數係平行輸入至八組該第一單埠記憶體單元，第二組及第三組的八個位元參數係平行輸入至八組該第二單埠記憶體單元中，且該八組第一單埠記憶體單元及該八組第二單埠記憶體單元中的每一組第一個單埠記憶體單元係作為位移的初始單埠記憶體單元；第五組及第八組的八個位元參數分別自該初始單埠記憶體單元位移四個單埠記憶體單元並輸入至該八組第一單埠記憶體單元中，第六組及第七組的八個位元參數分別自該初始單埠記憶體單元位移四個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中；第九組及第十二組的八個位元參數分別自該初始單埠記憶體單元位移兩個單埠記憶體單元並輸入至該八組第一單埠記憶體單元，第十組及第十一組的八個位元參數分別自該初始單埠記憶體單元位移兩個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中；第十三組及第十六組的八個位元參數分別自該初始單埠記憶體單元位移六個單埠記憶體單元並輸入至該八組第一單埠記憶體單元，第十四組及第十五組的八個位元參數分別自該初始單埠記憶體單元位移六個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中； 第十七組及第二十組的八個位元參數分別自該初始單埠記憶體單元位移一個單埠記憶體單元並輸入至該八組第一單埠記憶體單元，第十八組及第十九組的八個位元參數分別自該初始單埠記憶體單元位移一個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中；第二十一組及第二十四組的八個位元參數分別自該初始單埠記憶體單元位移五個單埠記憶體單元並輸入至該八組第一單埠記憶體單元，第二十二組及第二十三組的八個位元參數分別自該初始單埠記憶體單元位移五個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中；第二十五組及第二十八組的八個位元參數分別自該初始單埠記憶體單元位移三個單埠記憶體單元並輸入至該八組該第一單埠記憶體單元，第二十四組及第二十七組的八個位元參數分別自該初始單埠記憶體單元位移三個單埠記憶體單元位址並輸入至該八組第二單埠記憶體單元中；及第二十九組及第三十二組的八個位元參數分別自該初始單埠記憶體單元位移七個單埠記憶體單元並輸入至該八組第一單埠記憶體單元，第三十組及第三十一組的八個位元參數分別自該初始單埠記憶體單元位移七個單埠記憶體單元並輸入至該八組第二單埠記憶體單元中。
7. 如請求項1所述的重新調序緩衝器，其中該反向位元資料係由一平行管線式快速傅立葉轉換處理器輸出，該平行管線式快速傅立葉轉換處理器電性連接該寫入交換器。
8. 如請求項1所述的重新調序緩衝器，更包括一多工器，電性連接該第一記憶體模組、該第二記憶體模組及該讀取交換器，該第一記憶體模組及該 第二記憶體模組中的該位元資料係由該多工器選擇輸出，該讀取交換器係接收該多工器所輸出之該位元資料以交換為自然順序之該輸出位元資料。