[發明專利]一種基于融合乘加指令加速FFT計算的方法

在審

• 申請號: 201310364339.5
• 申請日: 2013-08-20
• 公開（公告）號: CN103440228A
• 公開（公告）日: 2013-12-11
• 發明（設計）人: 劉仲;竇強;郭陽;鄧讓鈺;向宏衛;龔國輝;唐遇星;王永文;陳海燕;彭元喜;陳躍躍;吳家鑄
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 湖南兆弘專利事務所 43008
• 代理人: 周長清

1.一種基于融合乘加指令加速FFT計算的方法，設計算的FFT點數為N=2ⁿ，其中n為大于1的整數，其特征在于，步驟為：

步驟1：判斷n是否為偶數；

步驟2：若n是偶數，可表達為n=2m，其中m為大于0的整數，則N=2ⁿ=2^2m=4^m，這時，FFT的計算轉化為m級基于融合乘加指令的時域抽取基4FFT的計算；若n不是偶數，n為奇數，可表達為n=2m+1，其中m為大于0的整數，則N=2ⁿ=2^2m+1=4^m*2，這時，FFT的計算轉化為先進行m級基于融合乘加指令的時域抽取基4FFT計算，最后進行一級基于融合乘加指令的時域抽取基2FFT計算；

其中，計算m級基于融合乘加指令的時域抽取基4FFT，時域抽取基4FFT的每個蝶形單元計算由24條融合乘加指令完成；計算一級基于融合乘加指令的時域抽取基2FFT，時域抽取基2FFT的每個蝶形單元計算由6條融合乘加指令完成；

步驟3：FFT的計算完成。

2.根據權利要求1所述的基于融合乘加指令加速FFT計算的方法，其特征在于，進行一個時域抽取基4FFT的蝶形單元的計算方法包括以下步驟：

步驟2.1.1：預先計算出時域抽取基4FFT算法所需的旋轉因子W₁,W₂，并且分別把兩個旋轉因子W₁,W₂按實部1為W_1r、虛部1/實部1為W_1i/W_1r、實部2為W_2r、虛部2/實部2為W_2i/W_2r的方式存放；

步驟2.1.2：給定4個輸入數據A，B，C，D；其中，A的實部和虛部分別表示為A_r,A_i；B的實部和虛部分別表示為B_r,B_i；C的實部和虛部分別表示為C_r,C_i；D的實部和虛部分別表示為D_r,D_i；計算蝶形單元的4個輸出結果Y₁，Y₂，Y₃，Y₄；其中，Y₁的實部和虛部分別表示為Y_1r,Y_1i；Y₂的實部和虛部分別表示為Y_2r,Y_2i；Y₃的實部和虛部分別表示為Y_3r,Y_3i；Y₄的實部和虛部分別表示為Y_4r,Y_4i；

步驟2.1.3：依據下式（1），通過12條融合乘加指令完成對4個中間結果的實部和虛部的計算；其中，分別為第一個中間結果的實部和虛部；分別為第二個中間結果的實部和虛部；分別為第三個中間結果的實部和虛部；分別為第四個中間結果的實部和虛部；

A‾r=Ar+W2r×(Cr-W2i/W2r×Ci)A‾i=Ai+W2r×(Cr×W2i/W2r+Ci)B‾r=Ar-W2r×(Cr-W2i/W2r×Ci)B‾i=Ai-W2r×(Cr×W2i/W2r+Ci)C‾r=Br+W2r×(Dr-W2i/W2r×Di)C‾i=Bi+W2r×(Dr×W2i/W2r+Di)D‾r=Br-W2r×(Dr-W2i/W2r×Di)D‾i=Bi-W2r×(Dr×W2i/W2r+Di)---(1)]]>

步驟2.1.2：依據下式（2），通過12條融合乘加指令完成4個輸出結果Y₁，Y₂，Y₃，Y₄的實部和虛部的計算；其中，Y₁的實部和虛部分別表示為Y_1r,Y_1i；Y₂的實部和虛部分別表示為Y_2r,Y_2i；Y₃的實部和虛部分別表示為Y_3r,Y_3i；Y₄的實部和虛部分別表示為Y_4r,Y_4i；

Y1r=Ar‾+W1r×(C‾r-W1i/W1r×C‾i)Y1i=Ai‾+W1r×(C‾r×W1i/W1r+C‾i)Y2r=B‾r-W1r×(D‾i+W1i/W1r×D‾r)Y2i=B‾i+W1r(D‾r-D‾i×W1i/W1r)Y3r=Ar‾-W1r×(C‾r-W1i/W1r×C‾i)Y3i=Ai‾-W1r×(C‾r×W1i/W1r+C‾i)Y4r=B‾r+W1r×(D‾i+W1i/W1r×D‾r)Y4i=B‾i-W1r×(D‾r-D‾i×W1i/W1r)---(2).]]>

3.根據權利要求1或2所述的基于融合乘加指令加速FFT計算的方法，其特征在于，進行一個時域抽取基2FFT的蝶形單元的計算方法包括以下步驟：

步驟2.2.1：預先計算出時域抽取基2FFT算法所需的旋轉因子W，并且按實部為W_r、虛部/實部為W_i/W_r的方式存放；

步驟2.2.2：給定2個輸入數據A，B；其中，A的實部和虛部分別表示為A_r,A_i；B的實部和虛部分別表示為B_r,B_i；計算蝶形單元的2個輸出結果Y₁，Y₂；其中，Y₁的實部和虛部分別表示為Y_1r,Y_1i；Y₂的實部和虛部分別表示為Y_2r,Y_2i；

步驟2.2.3：依據下式（3），通過2條融合乘加指令完成2個中間結果的實部和虛部的計算；其中，分別為第一個中間結果的實部和虛部；分別為第二個中間結果的實部和虛部；

A‾r=ArA‾i=AiB‾r=Br-Wi/Wr×BiB‾i=Br×Wi/Wr+Bi---(3)]]>

步驟2.2.4：依據下式（4），通過4條融合乘加指令完成2個輸出結果Y₁，Y₂的實部和虛部的計算；其中，Y₁的實部和虛部分別表示為Y_1r,Y_1i；Y₂的實部和虛部分別表示為Y_2r,Y_2i；

Y1r=A‾r+Wr×B‾rY1i=A‾i+Wr×B‾iY2r=A‾r-Wr×B‾rY2i=A‾i-Wr×B‾i---(4).]]>