摘 要： 針對DSP上常用的實序列IFFT算法運算速度慢的缺陷，采用兩行實序列合并為一行復序列進行IFFT運算的方法編制了在Blackfin系列DSP上進行實序列基-2 IFFT運算的程序。實驗表明，結合DSP指令的并行性及硬件并行結構的軟件設計提高了運算速度，完成兩行512點實序列的IFFT運算只需要11864個時鐘周期，為原來方法所需時間的一半。該方法應用于基于BF561的并行頻域OCT圖像處理系統中，滿足系統實時處理的要求。
關鍵詞： 實序列IFFT； Blackfin DSP； 并行
?
離散傅里葉逆變換（IDFT）是一種將離散信號從頻域轉變為時域表示的變換手段，其快速算法——快速傅里葉逆變換（IFFT）在數字信號處理過程中得到廣泛使用。
實際應用中經常遇到實序列的IFFT運算[1-2]。如在如圖1所示的并行頻域OCT(Parallel Spectral-Domain Optical Coherence Tomography,PSDOCT）圖像處理系統中,需要對攝像機輸入的像素為180×512的頻域圖像在DSP內進行逐行IFFT運算及幅度譜運算后得到反映樣品深度信息的空域層析圖像[3]并輸出顯示。由于系統需要進行25幀/s視頻速度的實時處理，而常用的把實數數據當作虛部為0的復數數據進行IFFT運算的方式浪費了其中一半的運算量和存儲量，不能滿足實時處理的要求。鑒于此，本文介紹了一種將兩行實序列合并為一行復序列進行IFFT運算的方法[4]，并且結合ADI公司Blackfin系列DSP指令的并行性及硬件的并行結構[5-6]，編制了512點實序列IFFT并行運算程序。實驗表明，該方法對兩行實序列運算所需的周期數約為直接進行復數計算周期數的一半,可以滿足并行頻域OCT圖像處理系統實時處理的要求。
?
1 實序列IFFT并行運算原理
進行N點實數X(k)的IFFT 運算時,一般的方法是把實數數據當作虛部為0的復數數據來處理。由于這種函數的時域呈現如式1所示的復數共軛對稱的性質，所以運算所需的2N個存儲單元中有一半是多余的，并且所耗的運算量與復數IFFT相同，沒有達到優化設計的目的。為了節約DSP 片內資源并且加快運算速度，可以將兩行實序列組合為復序列進行處理。設有兩個N點的實序列X(k)與Y(k)，整合為復序列Z(k)=X(k)+Y(k)j 。根據IDFT的線性和對稱性可得X(k)與Y(k)處理結果x(n)、y(n)與Z(k)的結果z(n)的關系式，如式(2)、(3)所示。
這樣就將x(n)、y(n)從z(n)中分離出來。該方法將運算速度提高了近一倍，并且運算需要的存儲量減少了一半。
2 算法在Blackfin DSP上的實現
Blackfin系列DSP是ADI公司和Intel 公司合作推出的基于微信號體系結構(Micro Signal Architecture)技術的定點DSP，整合了傳統體系結構DSP和RISC控制器的優點。該系列器件具有多級流水線結構，含有2個乘加運算(MAC)單元，并集成了大量的外圍設備和存儲器接口，每秒最高可執行1.2億次乘加運算，適用于實時圖像處理。由于在圖像處理過程中經常會遇到對實序列進行離散傅里葉逆變換的問題，所以需要設計一種優化的實序列IFFT程序。下面選用Blackfin系列中的BF561進行實序列并行基-2 IFFT程序設計，該程序適用于Blackfin系列所有的DSP。算法程序采用匯編語言編寫，可以通過C語言調用，具有良好的接口性能和可擴展性能。
2.1 實序列IFFT并行算法流程
在BF561上進行N點實序列基-2 IFFT運算流程如圖2所示（N=2m,m≥3），具體功能塊描述如下：
(1)程序初始化。由于BF561為定點DSP，如果進行浮點運算（如“塊浮點”運算[7]）將會影響計算的實時性。所以對輸入輸出數據及旋轉因子都做了定點處理，規定數據都為如圖3所示的16位有符號小數格式(即Q15格式)。IFFT運算的旋轉因子可由Matlab產生并以cos(2πk/N)、sin(2πk/N)（k=0,1,2……,2m-1)的格式進行實部、虛部交替排列成表，通過“#include”語句填充到BF561上的L1數據SRAM中，需要N字節容量存儲空間。L1數據SRAM以內核速度訪問，使得查表的速度達到最快。在L1數據SRAM中開辟了4N字節容量的存儲區進行中間結果的存放。
(2)將兩行N點實數數據X(k)、Y(k)合并成為N點復數數據Z(k)，并完成復數數據的位反轉操作。Blackfin DSP有專為IFFT算法設計的反序間接尋址，可實現增/減1或增/減一個變量的間接尋址方式，可以直接實現各種方式的位反轉操作。
(3)計算N點復數數據基-2 IFFT運算的蝶形運算結構如圖4所示。IFFT運算過程中需要大量的循環運算，而BF561支持“零開銷的硬件循環控制”及“硬件循環緩存”功能，即利用硬件尋址功能實現循環構造，并且循環體的指令在每次執行后暫時存放在循環緩存中以備下次使用，極大地加快了循環運算速度。
?
(4)分離還原。根據式(2)、(3)將兩行N點實數數據IFFT運算結果x(n)、y(n)從z(n)中分離出來。
2.2 利用并行指令進行程序設計
Blackfin系列DSP的多級流水線結構可以實現多個乘加及算術邏輯運算，并且可以實現運算與存儲器讀寫的并行執行。充分利用指令的并行性可以加快IFFT的運算速度。
2.2.1 32位數據寄存器的并行操作
Blacfin DSP的數據寄存器可以作為一個32位字(Rn)或是2個16位半字(Rn.H與Rn.L)。并且由于Blackfin DSP具有2個MAC，所以在一個指令周期內可以進行4個16位半字的操作。利用該并行指令進行如圖4的碟形運算的程序如式(4)、式(5)、式(6)所示，其中寄存器R1與R2的低位、高位分別存放Z1(k)與Z2(k)的實部、虛部，R3的低位、高位分別存放wN-k的實部、虛部。完成一次碟形運算只需要3個指令周期。
R1=R1+|+R2, R2=R1-|-R2(ASR);
?? ??? /*16位加減并行運算，結果右移一位*/???????? (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個指令周期內可以同時執行一條32位邏輯/乘加運算及2條16位指令；(2)表示1個指令周期內可以同時執行1條32位邏輯/乘加運算及1條16位指令；(3)表示1個指令周期內可以同時執行2條16位指令。其中16位指令包括對數據的讀取和存儲指令。
結合上述兩種并行指令的蝶形運算程序如式(7)、(8)、(9)所示。由程序可以看出：3個指令周期內不僅可以完成一次碟形運算，還可以實現旋轉因子的查表讀入、數據的讀入和運算結果的儲存等操作，大大減少了運算周期數。
2.3 硬件的并行處理
Blackfin DSP的L1數據SRAM采用分塊設計，如BF561的64 KB容量的L1數據SRAM分為16個獨立的存儲塊（每塊容量為4KB），并且內核與DMA可以同時訪問不同的存儲塊，所以可以通過“乒乓操作”的方式進行數據傳輸和處理的并行執行。這種流水線式算法完成了數據的無縫緩沖與處理，大大加快了IFFT運算速度。
3 實驗結果
在Blackfin集成開發環境Visual DSP++4.5上編制512點實序列基-2 IFFT程序。并用該程序在BF561上對兩行512點正弦數據進行計算，通過集成開發環境中的CYCLES計數器進行周期計數表明兩行數據IFFT運算需要11 864個周期。而直接計算兩行數據需要的周期數為21 098。前者所用的運算時間約為后者的一半。以MATLAB計算的32位精度結果作為基準進行比較，該程序計算結果誤差為0.009%。在如圖1的系統中對一幀頻域圖像(180×512)進行IFFT運算，其中BF561的內核時鐘為600MHz，運算需要的時間僅為1.7ms。
結合實序列IFFT運算、Blackfin系列DSP指令的并行性及硬件的并行結構設計了在BF561定點DSP上對實序列進行基-2 IFFT運算的程序。實驗證明，該程序比以往的方法運算周期減少了約一半，并且誤差小于萬分之一，滿足快速精確計算的要求。運用于并行頻域OCT圖像處理系統中，滿足系統實時處理的要求。該程序同樣適用于Blackfin系列中其他的DSP。
參考文獻
[1] 馬振鶴,王瑞康,張帆,等.快速高分辨率的頻譜光學相干層析成像系統研究[J].納米技術與精密工程,2005,3(3):232-235.
[2] 陳燕東,劉景琳,孟志強.新型實時光電混合圖像識別系統設計[J].電子測量與儀器學報,2007, 21(3):103-107.
[3] 李剛,任釗,吳開杰,等.Parallel spectral-domain optical?coherence tomography for non-scattering object imaging[J].天津大學學報(英), 2007,13(2):107-112.
[4] 胡廣書.數字信號處理理論－算法與實現[M].北京:清華大學出版社,2003.
[5] ADSP-BF53x/BF56x Blackfin processor programming?reference[Z]. USA：AD Inc., 2006.
[6]?陳峰. Blackfin系列DSP原理與系統設計[M].北京：電子工業出版社，2004.
[7] 楊向萍.提高FFT運算速度的幾項措施[J].中國紡織大學學報,1999,25(1):42-62.