二维FFT的程序实现及其应用(3)

叶东明：二维FFT的程序实现及其应用

F(u,v)?????????f(x,y)exp[?i2?(ux?vy)]dxdy (1-6-1)

为f(x,y)的二维Fourier变换2D－FT（2 dimensional Fourier transform或称为二维谱函数。

对应地称

f(x,y)?????????F(u,v)exp[i2?(ux?vy)]dudv (1-6-2)

为(1-6-1)的二维Fourier变换的逆变换，又称为反演公式。 1.7 二维离散Fourier变换

定义1.7.1

对N1?N2二维复序列A(k1,k2)，称

x(j1,j2)?N1?1N2?1k1?0k2?0??A(k,k12?k1j1?k2j2 )WNW N12 (1-7-1)

j1?0,1,?,N1-1, j2?0,1,?,N2-1为二维离散Fourier变换2D－DFT（2 dimensional discrete Fourier transform）。对应

地称

1A(k1,k2)x(j1,j2)?N1N2N1?1N2?1j1?0j2?0??x(j,j12k1j1k2j2 )WNW N12 (1-7-2)

k1?0,1,?,N1-1, k2?0,1,?,N2-12?i2?i为二维离散Fourier变换（1-7-1）的逆变换。这里WN1?exp(),WN2?exp()。

N1N22 DFT快速计算(FFT)算法分析及其程序实例

2.1 DFT的快速算法

本文将长度为N的序列{Ak}变为长度为N的序列{xj}的DFT及其逆变换形式

取为

?jkxj??AkWN j?0,1,?,N-1 (2-1-1)

k?0N?11N?1Ak??xjWNjk k?0,1,?,N-1 (2-1-2)

Nj?0为了可以用统一的程序处理DFT及其逆变换，我们将(2-1-2)改写为

1N?1?jkAk??xjWN k?0,1,?,N-1 (2-1-3)

Nj?0两个只差一个常数因子，求xj和Ak可以使用相同的程序。

Danielson和Lanczos两人提出一种将长度为N的序列{Ak}的DFT分为两个长度

11

集美大学学士学位论文

为

N的序列的DFT。其中一个序列由原序列{Ak}的偶数项构成，记其DFT为x0j，2而另一个序列由{Ak}的奇数项构成，记其DFT为xej。这时原序列的DFT为

?jkxj??AkWN k?0N?12k?0N?12k?0N?1?2kj?(2k?1)j ??A2kWN ? ?A2k?1WNN?12k?0N?12k?0 (2-1-4)

?kj?j?kj ??A2kWN ? WN ?A2k?1WN22?j0 ?xej?WNxj , j?0,1,?,N-1 2xN2?j??AkWNk?0N?1k?0N?1?(N?j)k2 ?jk ? ?(?1)kAkWN N?12k?0N?12k?0 ??A2k2k?2kj?(2k?1)j (2-1-5) WN ??A2k?1WNN?12k?0 ??Ak?0N?12?kj?j?kjWN ? WN ?A2k?1WN22?j0 ?xej?WNxj , j?0,1,?,N-1 2如此将长度为N的序列{Ak}的DFT{xj}用它的偶序列{A2k}和奇序列{A2k?1}的DFT，

e即{x0由于{xe{x0j}和{xj}表示。j}，j}长度为

N可以分别计算。而长度为N的序列{xj}2可按(2-1-4),(2-1-5)求得。 为

只要我们预先取N?2r，当我们将长度为N的序列{Ak}的DFT转变为求两个长

N的序列{A2k}，我们可再对{A2k}，{A2k?1}的DFT后，{A2k?1}分别作同样的转变，2N即转变为求长度的序列的DFT，这样该算法便可以递归地使用。

42.2 基2FFT算法分析

现在我们讨论N?2m，m为整数的FFT算法。将j,k写成m位2进制数，即

j?jm?12m?1?jm?22m?2???j121?j0?(jm?1,jm?2,?,j0)k?km?12

m?1?km?22m?2???k12?k0?(km?1,km?2,?,k0)12

1 (2-2-1)

叶东明：二维FFT的程序实现及其应用

其中jp,kp只取0或1，p?0,1,?,m?1。记

xj?x(jm?1,jm?2,?,j0)Ak?A(km?1,km?2,?,k0) j,k?0,1,?,N?1 (2-2-2)

j?k?(jm?1,jm?2,?,j0)(km?1,km?2,?,k0) ?j0km?12由{Ak}的DFT定义得

m?1?(j1,j0)km?22m?2???(jm?1,jm?2,?,j0)k0(modN) (2-2-3)

xj?x(jm?1,jm?2,?,j0) ? ?其中

A1(j0,km?2,?,k0) ?km?1?0k0?0k1?011???11km?1?01?j(km?1,km?2,?,k0)A(k,k,?,k)W?m?1m?20N1 (2-2-4)

k0?0k1?0????A(j,k10km?2?0m?2?j(0,km?2,?,k0),?,k0)WN j0,j1,?,jm?1?0,1 ?A(k1m?1?j(km?1,0,?,0),km?2,?,k0)WN (2-2-5)

?(j0,0,?,0) ?A(0,km?2,?,k0)?A(1,km?2,?,k0)WN j0,km?2,?,k0?0,1

显然A1(j0,km?2,?,k0)的第一项的因子为1，只有第二项需要作一次复数乘法。所

以计算A1(j0,km?2,?,k0)需要2m次乘法。而A1的序号(j0,km?2,?,k0)的左第一位为

j0，将j0左移m-1位和WN的指数相符。

继续对xj分解得

xj?x(jm?1,jm?2,?,j0) ? ?其中

A2(j0,j1,km?3,?,k0) ?km?2?0k0?0k1?011???11km?1?01?j(0,km?2,?,k0)A(j,k,?,k)W j0,j1,?,jm?1?0,1 (2-2-6) ?10m?20N1k0?0k1?0????A(j,j,k201km?3?0m?3?j(0,0,km?3,?,k0),?,k0)WN ?A(j,k101m?2?j(0,km?2,0,?,0),?,k0)WN (2-2-7)

?(j1,j0,0,?,0) ?A1(j0,0,km?3,?,k0)?A1(j0,1,km?3,?,k0)WN j0,j1,km?3,?,k0?0,1

13

集美大学学士学位论文

计算A2(j0,j1,km?3,?,k0)需要2m次复数乘法，同时A2的序号(j0,j1,km?3,?,k0)的左两位为(j0,j1)，将其逆排后左移m-2位和WN的指数相符。继续分解则有

Al ( l?1,2,?,m) 。若记

A0(km?1,km?2,?,k0)?A(km?1,km?2,?,k0) (2-2-8)

则有

Al(j0,j1,?,jl?1,km?l?1,?,k0) ?km?l?0?A1l?1?j(0,?,km?l,0,?,0)(j0,?,jl?2,km?l,?,k0)WN ?Al?1(j0,?,jl?2,0,km?l?1,?,k0)?(jl?1,?,j0,0,?,0) ?Al?1(j0,?,jl?2,1,km?l?1,?,k0)WN (2-2-9)

j0,?,jl?1,km?l?1,?,k0?0,1 l?1,2,?,m

对某一确定的l，计算Al(j0,j1,?,jl?1,km?l?1,?,k0)需要2m次复数乘法，同时Al的

序号(j0,j1,?,jl?1,km?l?1,?,k0)的左l位为(j0,j1,?,jl?1)，将其逆排后左移m?l位和

WN的指数相符。

当完成l?m步计算后得

xj?x(jm?1,jm?2,?,j0)?Am(j0,j1,?,jm?1) j0,j1,?,jm?1?0,1 (2-2-10)

可以看到，xj的序号(jm?1,jm?2,?,j0)逆排后得(j0,j1,?,jm?1)恰好为Am的序号。计算每一Al需要2m次复数乘法，所以由{Ak}求得{xj}共需要m?2m次复数运算。即当

N?2m时，求长度为N复序列{Ak}的DFT基2FFT算法运算总次数为

N (2-2-11) m2m?Nlog2

从以上分析可得： 基2FFT算法实现的关键在于下标的组织；

基2FFT算法的必要条件为N?2m，m为整数。

对不满足N?2m条件的序列{Ak}，我们可用零扩充的方法，即取最小的m，满

足2m?1?N?2m，则可令：

14

叶东明：二维FFT的程序实现及其应用

?Ak 0?k?NAk?? (2-2-12) m?0 N?k?2当回到时间域后，我们可以将扩充的零元素删除。 2.3 复序列基2FFT算法

设{Ak}是长度为N的复序列，其中N?2m。 算法2.3.1 记A0?A： (1) 计算WNj?cos2?j2?j?isin, j?0,1,?,N-1 ； NN基2FFT正变换

(2) 对l?1,2,?,m计算Al：

a.记k?(km?l?1,?,k0) ,j?(j0,j1,?,jl?1)； b.逆排(j0,j1,?,jl?2)得(jl?2,?,j0)；

c.左移(jl?2,?,j0)m?l位得(0,jl?2,?,j0,0,?,0)，由此查得WNd.对j0,j1,?,jl?2,km?l?1,?,k0?0,1计算

?(0,jl?2,?,j0,0,?,0)；

Al(j0,j1,?,jl?2,0,km?l?1,?,k0) ?Al?1(j0,?,jl?2,0,km?l?1,?,k0)?(0,jl?2,?,j0,0,?,0) ?Al?1(j0,?,jl?2,1,km?l?1,?,k0)WN

Al(j0,j1,?,jl?2,1,km?l?1,?,k0) ?Al?1(j0,?,jl?2,0,km?l?1,?,k0)?(0,jl?2,?,j0,0,?,0) ?Al?1(j0,?,jl?2,1,km?l?1,?,k0)WN

(3) 对j0,j1,?,jm?1?0,1完成： a. 逆排(jm?1,?,j0)得(j0,j1,?,jm?1) b. 令

x(jm?1,jm?2,?,j0)?Am(j0,j1,?,jm?1)

正变换完成，由{Ak}得其DFT{xj}。

算法2.3.2

基2FFT逆变换

置Ak?xk,k?0,1,?,N?1： (1) 计算WNj?cos2?j2?j?isin, j?0,1,?,N-1 NN15

(2) 置ImAk??ImAk,k?0,1,?,N?1

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库二维FFT的程序实现及其应用(3)在线全文阅读。