集美大学学士学位论文
(3) 用算法2.3.1求{Ak}的DFT，并记为xj(j?0,1,?,N?1) (4) 对k?0,1,?,N?1，令
Ak?1xk N计算结束得{xj}的DFT逆变换{Ak}。
算法2.3.1和算法2.3.2的程序（fft1.c）在附录中给出。fft1.c的主要函数 fft1(double A[2][N],int ifft)程序流程图如下： 开始
调用初始化函数initial(),并 Y ifirst==0? 置ifirst=1
N
令A[1][i]= -A[1][i] Y ifft== -1? N 用算法2.3.1求{A}的 DFT{x} 置A[0][i]=x[0][i]， A[1][i]=x[1][i]
置A[0][i]=A[0][i]/N， Y ifft== -1? A[1][i]=-A[1][i]/N
N
结束
图2-1 fft1()程序流程图
kk 16
叶东明：二维FFT的程序实现及其应用
下面我们给出一个实例。
例2.3.1 设f(t)?exp(?t)，为求其Fourier变换，将其离散化得序列{Ak}，再求
DFT，最后作DFT逆变换。
解：取?t?0.1,N?64，这时
?F(s)??exp(?t)exp(?i2?st)dt?? ??
取?s?N?t
?N?texp(?t)exp(?i2?st)dt1j,sj?j?s?，对F(s)离散化得 N?tN?txj?F(sj) i2?jk ??(exp[-(N-k)?t]?exp(-k?t))exp(-)?tNk?0N-1 记
Ak?[f(k?t)?f(k?t?N?t)]?t ?exp(-k?t)?t?exp[?(N?k)?t]?t k?0,1,?,N-1
得
-jk xj??AkWNk?0N-1
主函数fft1m1.c（附录中给出）主要功能：子函数functf()（附件中给出）由f(t)产生{Ak}，由{Ak}求其DFT{xj}，再由{xj}求其DFT逆变换{Ak}。并将结果{Ak}，
{xj}，{Ak}存入数据文件fft1m1.d。fft1m1.c中主函数的流程图如图2-2所示。 2.4 二维复序列2D－DFT的行列算法
2D－DFT的快速算法很多，最常用的是行列算法。
对N1?N2二维复序列A(k1,k2)定义中间序列
y(j1,k2)?N1?1k1?0?A(k,k12?j1k1)WN,j1?0,1,?,N1?1,k2?0,1,?,N2?1 (2-4-1) 1 这是N2个关于k1长度为N1的复序列的一维DFT。进而得2D－DFT正变换为
x(j1,j2)?
N2?1k2?0?y(j,k12?j2k2)WN,j1?0,1,?,N1?1,j2?0,1,?,N2?1 (2-4-2) 2这是N1个关于k2长度为N2的复序列的一维DFT。这样，我们就把计算
17
集美大学学士学位论文
开始 调用functf(A)， 由f(x)得到离散的序列{A} k输出{A} k把{A}作为参数调用 kfft1 (A,1)函数，由Fourier正变换得到{x}。 k输出{x} k把{x}作为参数调用 kfft1 (A,－1)函数，由Fourier逆变换得到{A}。 k输出{A} k结束 图2-2 fft1m1.c主函数的流程图
18
叶东明：二维FFT的程序实现及其应用
N1?N2个点的2D－DFT转化为计算N2个长度为N1的序列和N1个长度为N2的序列的一维DFT。以上计算2D－DFT的方法就称为行列算法。 以上给出的是2D－DFT行列算法的正变换，对应二维行列算法2D－DFT逆变换可以由下面两个过程来实现：
1y(j1,k2)?N21A(k1,k2)?N1N2?1j2?0?x(j,j112)WNj22k2,j1?0,1,?,N1?1,k2?0,1,?,N2?1 (2-4-3) )WNj11k1,k1?0,1,?,N1?1,k2?0,1,?,N2?1 (2-4-4)
N1?1j1?0?y(j,k2为了能用统一的形式和程序处理，将(2-4-3)取共轭得
1y(j1,k2)?N2N2?1j2?0?x(j,j12?j2k2)WN2 (2-4-5)
j1?0,1,?,N1?1,k2?0,1,?,N2?1即先将x(j1,j2)取共轭x(j1,j2)，关于j2对序列{x(j1,j2)}作一维DFT正变换得
z(j1,k2)
z(j1,k2)?N2?1j2?0?x(j,j1?j2k2)W2N2 (2-4-6)
j1?0,1,?,N1?1,k2?0,1,?,N2?1当N2?2m时，它可以用FFT正变换相关程序实现。{z(j1,k2)}求得后，令
y(j1,k2)?1z(j1,k2),j1?0,1,?,N1?1,k2?0,1,?,N2?1 (2-4-7) N2求得y(j1,k2)。
从以上算法分析可知对N1和N2，与一维的N的要求一样，需满足
N1?2M1,N2?2M2，当N1和N2不满足时，同样采用零元素扩充方法。这时，我们就可以使用一维基2FFT的程序，从而实现2D－DFT的快速算法。 算法2.4.1
N1?N2二维复序列{A(k1,k2)}2D－DFT行列算法正变换
由A(k1,k2)求x(j1,j2)
(1) 对k2?0,1,?,N2?1关于k1使用一维FFT相关算法求长度为N1的一维序列的
DFT:
y(j1,k2)?N1?1k1?0?A(k,k12?j1k1)WN,j1?0,1,?,N1?1 (2-4-8) 119
集美大学学士学位论文
(2) 对j1?0,1,?,N1?1关于k2使用一维FFT相关算法求长度为N2的一维序列的
DFT: x(j1,j2)?算法2.4.2
N2?1k2?0?y(j,k12?j2k2)WN,j2?0,1,?,N2?1 (2-4-9) 2N1?N2二维复序列{A(k1,k2)}2D－DFT行列算法逆变换
由x(j1,j2)求A(k1,k2)
(1) 对j1?0,1,?,N1?1关于j2使用一维FFT相关算法求长度为N2的一维序列的
DFT逆变换
1y(j1,k2)?N2N2?1j2?0?x(j,j12)WNj22k2 (2-4-10)
k2?0,1,?,N2?1(2) 对k2?0,1,?,N2?1关于j1使用一维FFT相关算法求长度为N1的一维序列的
DFT逆变换{A(k1,k2)}
1A(k1,k2)?N1N1?1j1?0?y(j,k1j1k1)W2N1 (2-4-11)
k1?0,1,?,N1?1算法2.4.1和算法2.4.2的程序(fft2.c，rowco2.c)在附录中给出,fft2.c包括初始化函数initial()、长度为N1的复序列{Ak}的FFT程序fft21()、长度为N2的复序列
{Ak}的FFT程序fft22()、逆排序号的函数inverseq()。fft21()和fft22()的程序流程
与流程图2.1一样，在此就不再描述，现在只给出rowco2.c的函数rowcolumn()
的程序流程图，如图2-3： 开始
调用初始化函数initial()
置j=0
20