基于FPGA的移位寄存器流水線結構FFT處理器

　　2 移位寄存器流水線結構的FFT

　　在傳統流水線結構的FFT中，需要將全部數據輸入寄存器后，可開始蝶形運算。在基-2 DIF算法中可以發現，當前N／2個數據進入寄存器后，運算便可以開始，此后進入的第N／2+1個數據與寄存器第一個數據進行蝶形運算，以此類推。

　　由于采用頻域抽取法，不需要對輸入的數據進行倒序處理，簡化了地址控制，這樣，可以采用移位寄存器的方式，依次將前N／2個數據移入移位寄存器，在N／2+l時刻，第一個數據移出移位寄存器，參與運算。相對于傳統的RAM讀寫方式，采用移位寄存器存儲結構綜合后的最大工作頻率為500 MHz，遠大于RAM方式的166 MHz。

　　當移位寄存器相繼有數據移出時，在移位寄存器中會出現空白位。此時，引入第二路數據，在第一路數據依次移出進行蝶算時，第二路數據依次補充到移位寄存器的空白位中，為運算做準備。通過這樣一種類似“乒乓操作”的結構，可以使蝶形運算模塊中的數據不間斷地輸入，運算效率達到100％。不同于傳統的“乒乓操作”結構，由于使用移位寄存器，不需要兩塊RAM，可以省掉一半的寄存器。圖2為256點FFT處理器的第一級結構。

　　基于上述基本原理，將這種移位寄存器結構擴展到整個FFT系統的各級，可以發現各級使用的移位寄存器數量是遞減的。現使用一個8點結構來進行說明。

　　如圖3所示，數據由輸入l和輸入2進入第一級。通過開關進行選通控制。由于是N=8的運算，所以各級分別加入4級、2級和1級的移位寄存器。

　　分兩路來說明運算過程：

　　將K1打到位置①，第一路數據進入移位寄存器，待第一路的前4個數據存入4級移位寄存器后，第一路進入的第5個數據與移位寄存器移出的第1個數據進行蝶形運算。

　　由于輸出結果有上下兩路，第二級是一個四點的DFT，所以對于上路的輸出結果x0(0)+x0(4)類似于第一級，直接存入下一級寄存器，為四點運算做準備，下路的輸出，先存入本級2級移位寄存器中，等到上路的四點運算開始，第二級的移位寄存器有空白位時，移入第二級，為下路的四點運算做準備。所以第一級蝶形運算上路輸出前N／4=2個進入下一級寄存器，下路輸出的數據依次存入本級移位寄存器中。

　　當第一級的輸出前N／4=2個數據x0(0)+x0(4)和x0(1)+x0(5)存入第二級移位寄存器時，運算便可以開始，這時開關K2打到位置②，此時第一級上路輸出的數據x0(2)+x0(6)，即第一級上路輸出的第三個數據與第二級移位寄存器移出的第一個數據，即x0(O)+x0(4)進行蝶形運算，輸出的第四個數據x0(3)+x0(7)與x0(1)+x0(5)進行蝶算。在這個運算過程中，第一級的2級移位寄存器移出數據依次移位存入到第二級的移位寄存器產生的空白位中。

　　兩個時鐘后，第一級上路輸出的四個數據完成了蝶形運算，K2打到位置①，在接下來的兩個時鐘里，第一級中2級移位寄存器的輸出依次與此時第二級中2級移位寄存器的輸出數據進行蝶形運算，即與，與完成第一級下路輸出的四個數據的蝶形運算。

　　此時，第一路在第一級運算后的輸出數據，在第二級完成了全部的蝶形運算。第二級的輸出結果同第一級一樣，蝶形運算的上路輸出前N／8=1個進入下一級寄存器，后一個數據直接進入后一級進行碟算，下路輸出的數據存入本級移位寄存器中。