1 實序列IFFT并行運算原理
　　進行N點實數(shù)X(k)的IFFT 運算時,一般的方法是把實數(shù)數(shù)據(jù)當作虛部為0的復數(shù)數(shù)據(jù)來處理。由于這種函數(shù)的時域呈現(xiàn)如式1所示的復數(shù)共軛對稱的性質(zhì)，所以運算所需的2N個存儲單元中有一半是多余的，并且所耗的運算量與復數(shù)IFFT相同，沒有達到優(yōu)化設(shè)計的目的。為了節(jié)約DSP 片內(nèi)資源并且加快運算速度，可以將兩行實序列組合為復序列進行處理。設(shè)有兩個N點的實序列X(k)與Y(k)，整合為復序列Z(k)=X(k)+Y(k)j 。根據(jù)IDFT的線性和對稱性可得X(k)與Y(k)處理結(jié)果x(n)、y(n)與Z(k)的結(jié)果z(n)的關(guān)系式，如式(2)、(3)所示。
　
　　這樣就將x(n)、y(n)從z(n)中分離出來。該方法將運算速度提高了近一倍，并且運算需要的存儲量減少了一半。
2 算法在Blackfin DSP上的實現(xiàn)
　　Blackfin系列DSP是ADI公司和Intel 公司合作推出的基于微信號體系結(jié)構(gòu)(Micro Signal Architecture)技術(shù)的定點DSP，整合了傳統(tǒng)體系結(jié)構(gòu)DSP和RISC控制器的優(yōu)點。該系列器件具有多級流水線結(jié)構(gòu)，含有2個乘加運算(MAC)單元，并集成了大量的外圍設(shè)備和存儲器接口，每秒最高可執(zhí)行1.2億次乘加運算，適用于實時圖像處理。由于在圖像處理過程中經(jīng)常會遇到對實序列進行離散傅里葉逆變換的問題，所以需要設(shè)計一種優(yōu)化的實序列IFFT程序。下面選用Blackfin系列中的BF561進行實序列并行基-2 IFFT程序設(shè)計，該程序適用于Blackfin系列所有的DSP。算法程序采用匯編語言編寫，可以通過C語言調(diào)用，具有良好的接口性能和可擴展性能。
2.1 實序列IFFT并行算法流程
　　在BF561上進行N點實序列基-2 IFFT運算流程如圖2所示（N=2^m,m≥3），具體功能塊描述如下：
　　(1)程序初始化。由于BF561為定點DSP，如果進行浮點運算（如“塊浮點”運算^[7]）將會影響計算的實時性。所以對輸入輸出數(shù)據(jù)及旋轉(zhuǎn)因子都做了定點處理，規(guī)定數(shù)據(jù)都為如圖3所示的16位有符號小數(shù)格式(即Q15格式)。IFFT運算的旋轉(zhuǎn)因子可由Matlab產(chǎn)生并以cos(2πk/N)、sin(2πk/N)（k=0,1,2……,2^m-1)的格式進行實部、虛部交替排列成表，通過“#include”語句填充到BF561上的L1數(shù)據(jù)SRAM中，需要N字節(jié)容量存儲空間。L1數(shù)據(jù)SRAM以內(nèi)核速度訪問，使得查表的速度達到最快。在L1數(shù)據(jù)SRAM中開辟了4N字節(jié)容量的存儲區(qū)進行中間結(jié)果的存放。

　　(2)將兩行N點實數(shù)數(shù)據(jù)X(k)、Y(k)合并成為N點復數(shù)數(shù)據(jù)Z(k)，并完成復數(shù)數(shù)據(jù)的位反轉(zhuǎn)操作。Blackfin DSP有專為IFFT算法設(shè)計的反序間接尋址，可實現(xiàn)增/減1或增/減一個變量的間接尋址方式，可以直接實現(xiàn)各種方式的位反轉(zhuǎn)操作。
　　(3)計算N點復數(shù)數(shù)據(jù)基-2 IFFT運算的蝶形運算結(jié)構(gòu)如圖4所示。IFFT運算過程中需要大量的循環(huán)運算，而BF561支持“零開銷的硬件循環(huán)控制”及“硬件循環(huán)緩存”功能，即利用硬件尋址功能實現(xiàn)循環(huán)構(gòu)造，并且循環(huán)體的指令在每次執(zhí)行后暫時存放在循環(huán)緩存中以備下次使用，極大地加快了循環(huán)運算速度。

?

　　(4)分離還原。根據(jù)式(2)、(3)將兩行N點實數(shù)數(shù)據(jù)IFFT運算結(jié)果x(n)、y(n)從z(n)中分離出來。
2.2 利用并行指令進行程序設(shè)計
　　Blackfin系列DSP的多級流水線結(jié)構(gòu)可以實現(xiàn)多個乘加及算術(shù)邏輯運算，并且可以實現(xiàn)運算與存儲器讀寫的并行執(zhí)行。充分利用指令的并行性可以加快IFFT的運算速度。
2.2.1 32位數(shù)據(jù)寄存器的并行操作
　　Blacfin DSP的數(shù)據(jù)寄存器可以作為一個32位字(Rn)或是2個16位半字(Rn.H與Rn.L)。并且由于Blackfin DSP具有2個MAC，所以在一個指令周期內(nèi)可以進行4個16位半字的操作。利用該并行指令進行如圖4的碟形運算的程序如式(4)、式(5)、式(6)所示，其中寄存器R1與R2的低位、高位分別存放Z₁(k)與Z₂(k)的實部、虛部，R3的低位、高位分別存放w_N^-k的實部、虛部。完成一次碟形運算只需要3個指令周期。

　　R1=R1+|+R2, R2=R1-|-R2(ASR);
??　??? /*16位加減并行運算，結(jié)果右移一位*/???????? (4)
?　 A1=R2.L*R3.H, A0=R2.L*R3.L;
??????? /*16位乘法并行運算*/?????????????????????? (5)
??? R3.H=(A1+=R2.H*R3.L),R3.L=(A0-=R2.H*R3.H);
??????? /*16位乘法并行運算*/?????????????????????? (6)
2.2.2 運算與存儲器讀寫的并行指令
??? Blackfin DSP支持下列3種并行指令語句：
　　(1) A 32-bit ALU/MAC instruction || A 16-bit instruction ||A 16-bit instruction;//
　　(2) A 32-bit ALU/MAC instruction || A 16-bit instruction; //
　　(3) MNOP || A 16-bit instruction || A 16-bit instruction; //

　　其中：(1)表示1個指令周期內(nèi)可以同時執(zhí)行一條32位邏輯/乘加運算及2條16位指令；(2)表示1個指令周期內(nèi)可以同時執(zhí)行1條32位邏輯/乘加運算及1條16位指令；(3)表示1個指令周期內(nèi)可以同時執(zhí)行2條16位指令。其中16位指令包括對數(shù)據(jù)的讀取和存儲指令。
　　結(jié)合上述兩種并行指令的蝶形運算程序如式(7)、(8)、(9)所示。由程序可以看出：3個指令周期內(nèi)不僅可以完成一次碟形運算，還可以實現(xiàn)旋轉(zhuǎn)因子的查表讀入、數(shù)據(jù)的讀入和運算結(jié)果的儲存等操作，大大減少了運算周期數(shù)。