[發明專利]基于基24算法的多路FFT處理器中乘法器的復用方法

有效

• 申請號: 201010257622.4
• 申請日: 2010-08-19
• 公開（公告）號: CN101937332A
• 公開（公告）日: 2011-01-05
• 發明（設計）人: 周曉方;汪文義;王琳凱
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/302
• 分類號: G06F9/302
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種改進的基2⁴算法，其特征在于具體步驟如下：

對于N點序列x(n)，其離散傅立葉變換定義為：

X(k)=Σn=0N-1x(n)WNnk,k=0,1,2...N-1---(1)]]>

其中，N是2的冪，x(n)和X(k)是復數序列，旋轉因子：

WNnk=e-j(2πnk/N)=cos(2πnk/N)-jsin(2πnk/N);]]>

n=<N2n1+N4n2+N8n3+N16n4+n5>N,n1,n2,n3,n4=0,1;n5=0...N16-1]]>

k=<k1+2k2+4k3+8k4+16k5>N,k1,k2,k3,k4=0,1;n5=0...N16-1]]>

將上式代入(1)中有：

X(k1+2k2+4k3+8k4+16k5)=Σn5=0N16-1Σn4=01Σn3=01Σn2=01Σn1=01x(N2n1+N4n2+N8n3+N16n4+n5)WNnk---(2)]]>

其中旋轉因子表示為：

WNnk=WN(N2n1+N4n2+N8n3+N16n4+n5)(k1+2k2+4k3+8k4+16k5)]]>

=WNN2n1k1WNN4n2(k1+2k2)WNN8n3(k1+2k2+4k3)*WNN16n4(k1+2k2+4k3+8k4)WNn5(k1+2k2+4k3+8k4+16k5)]]>

=(-1)n1k1(-j)n2(k1+2k2)WNN8n3(k1+2k2+4k3)*WNN16n4(k1+2k2+4k3+8k4)WNn5(k1+2k2+4k3+8k4)WN16n5k5---(3)]]>

將(3)代入(2)式中，并簡化得到一組長度為N/16D?FT的集合如下：

X(k1+2k2+4k3+8k4+16k5)=Σn5=0N16-1[QN16(n5,k1,k2,k3,k4)WNn5(k1+2k2+4k3+8k4)]WN16n5k5]]>

其中，令Q(n₅，k₁，k₂，k₃，k₄)為第四級蝶形運算，表達式為：

其中T(n₅，k₁，k₂，k₃)為第三級蝶形運算，表達式為：

其中H(n₅，k₁，k₂)為第二級蝶形運算，表達式為：

其中B(n₅，k₁)為第一級蝶形運算，表達式為：

BN2(N4n2+N8n3+N16n4+n5,k1)=x(N4n2+N8n3+N16n4+n5)+(-1)k1x(N4n2+N8n3+N16n4+n5+N2)---(7)]]>