2 移位寄存器流水線結(jié)構(gòu)的FFT

　　在傳統(tǒng)流水線結(jié)構(gòu)的FFT中，需要將全部數(shù)據(jù)輸入寄存器后，可開(kāi)始蝶形運(yùn)算。在基-2 DIF算法中可以發(fā)現(xiàn)，當(dāng)前N／2個(gè)數(shù)據(jù)進(jìn)入寄存器后，運(yùn)算便可以開(kāi)始，此后進(jìn)入的第N／2+1個(gè)數(shù)據(jù)與寄存器第一個(gè)數(shù)據(jù)進(jìn)行蝶形運(yùn)算，以此類推。

　　由于采用頻域抽取法，不需要對(duì)輸入的數(shù)據(jù)進(jìn)行倒序處理，簡(jiǎn)化了地址控制，這樣，可以采用移位寄存器的方式，依次將前N／2個(gè)數(shù)據(jù)移入移位寄存器，在N／2+l時(shí)刻，第一個(gè)數(shù)據(jù)移出移位寄存器，參與運(yùn)算。相對(duì)于傳統(tǒng)的RAM讀寫(xiě)方式，采用移位寄存器存儲(chǔ)結(jié)構(gòu)綜合后的最大工作頻率為500 MHz，遠(yuǎn)大于RAM方式的166 MHz。

　　當(dāng)移位寄存器相繼有數(shù)據(jù)移出時(shí)，在移位寄存器中會(huì)出現(xiàn)空白位。此時(shí)，引入第二路數(shù)據(jù)，在第一路數(shù)據(jù)依次移出進(jìn)行蝶算時(shí)，第二路數(shù)據(jù)依次補(bǔ)充到移位寄存器的空白位中，為運(yùn)算做準(zhǔn)備。通過(guò)這樣一種類似“乒乓操作”的結(jié)構(gòu)，可以使蝶形運(yùn)算模塊中的數(shù)據(jù)不間斷地輸入，運(yùn)算效率達(dá)到100％。不同于傳統(tǒng)的“乒乓操作”結(jié)構(gòu)，由于使用移位寄存器，不需要兩塊RAM，可以省掉一半的寄存器。圖2為256點(diǎn)FFT處理器的第一級(jí)結(jié)構(gòu)。

　　基于上述基本原理，將這種移位寄存器結(jié)構(gòu)擴(kuò)展到整個(gè)FFT系統(tǒng)的各級(jí)，可以發(fā)現(xiàn)各級(jí)使用的移位寄存器數(shù)量是遞減的?，F(xiàn)使用一個(gè)8點(diǎn)結(jié)構(gòu)來(lái)進(jìn)行說(shuō)明。

　　如圖3所示，數(shù)據(jù)由輸入l和輸入2進(jìn)入第一級(jí)。通過(guò)開(kāi)關(guān)進(jìn)行選通控制。由于是N=8的運(yùn)算，所以各級(jí)分別加入4級(jí)、2級(jí)和1級(jí)的移位寄存器。

　　分兩路來(lái)說(shuō)明運(yùn)算過(guò)程：

　　將K1打到位置①，第一路數(shù)據(jù)進(jìn)入移位寄存器，待第一路的前4個(gè)數(shù)據(jù)存入4級(jí)移位寄存器后，第一路進(jìn)入的第5個(gè)數(shù)據(jù)與移位寄存器移出的第1個(gè)數(shù)據(jù)進(jìn)行蝶形運(yùn)算。

　　由于輸出結(jié)果有上下兩路，第二級(jí)是一個(gè)四點(diǎn)的DFT，所以對(duì)于上路的輸出結(jié)果x0(0)+x0(4)類似于第一級(jí)，直接存入下一級(jí)寄存器，為四點(diǎn)運(yùn)算做準(zhǔn)備，下路的輸出，先存入本級(jí)2級(jí)移位寄存器中，等到上路的四點(diǎn)運(yùn)算開(kāi)始，第二級(jí)的移位寄存器有空白位時(shí)，移入第二級(jí)，為下路的四點(diǎn)運(yùn)算做準(zhǔn)備。所以第一級(jí)蝶形運(yùn)算上路輸出前N／4=2個(gè)進(jìn)入下一級(jí)寄存器，下路輸出的數(shù)據(jù)依次存入本級(jí)移位寄存器中。

　　當(dāng)?shù)谝患?jí)的輸出前N／4=2個(gè)數(shù)據(jù)x0(0)+x0(4)和x0(1)+x0(5)存入第二級(jí)移位寄存器時(shí)，運(yùn)算便可以開(kāi)始，這時(shí)開(kāi)關(guān)K2打到位置②，此時(shí)第一級(jí)上路輸出的數(shù)據(jù)x0(2)+x0(6)，即第一級(jí)上路輸出的第三個(gè)數(shù)據(jù)與第二級(jí)移位寄存器移出的第一個(gè)數(shù)據(jù)，即x0(O)+x0(4)進(jìn)行蝶形運(yùn)算，輸出的第四個(gè)數(shù)據(jù)x0(3)+x0(7)與x0(1)+x0(5)進(jìn)行蝶算。在這個(gè)運(yùn)算過(guò)程中，第一級(jí)的2級(jí)移位寄存器移出數(shù)據(jù)依次移位存入到第二級(jí)的移位寄存器產(chǎn)生的空白位中。

　　兩個(gè)時(shí)鐘后，第一級(jí)上路輸出的四個(gè)數(shù)據(jù)完成了蝶形運(yùn)算，K2打到位置①，在接下來(lái)的兩個(gè)時(shí)鐘里，第一級(jí)中2級(jí)移位寄存器的輸出依次與此時(shí)第二級(jí)中2級(jí)移位寄存器的輸出數(shù)據(jù)進(jìn)行蝶形運(yùn)算，即與，與完成第一級(jí)下路輸出的四個(gè)數(shù)據(jù)的蝶形運(yùn)算。

　　此時(shí)，第一路在第一級(jí)運(yùn)算后的輸出數(shù)據(jù)，在第二級(jí)完成了全部的蝶形運(yùn)算。第二級(jí)的輸出結(jié)果同第一級(jí)一樣，蝶形運(yùn)算的上路輸出前N／8=1個(gè)進(jìn)入下一級(jí)寄存器，后一個(gè)數(shù)據(jù)直接進(jìn)入后一級(jí)進(jìn)行碟算，下路輸出的數(shù)據(jù)存入本級(jí)移位寄存器中。