§5快速 Fourier变换 离散 Fourier变换 人们刚开始利用无线电技术传输信号时,是将连续信号进行某种 调制处理后直接传送的(图16.5.1),本质上传送的还是连续信号(也 叫模拟信号)。这样的传输方式抗干扰能力差,失真严重,尤其是经 过长距离传送或多级传递后,信号可能面目全非,质量自然难尽人意。 传送 九调制 解调 图16.5.1
离散 Fourier 变换 人们刚开始利用无线电技术传输信号时，是将连续信号进行某种 调制处理后直接传送的（图 16.5.1），本质上传送的还是连续信号（也 叫模拟信号）。这样的传输方式抗干扰能力差，失真严重，尤其是经 过长距离传送或多级传递后，信号可能面目全非，质量自然难尽人意。 传送 调制 解调 图 16.5.1 §5 快速Fourier变换
以后发展了离散的传输方法,它不是传送连续信号本身,而是每 隔一段时间Δ,从信号中提取一个数值脉冲(称为数值抽样),将连 续信号转化成数据序列x(0),x(1),x(2),…,x(N-1)(图16.5.2), 再经编码后发送。只要抽取的时间间隔足够小,这列数据就能很好地 反映原信号,接收方通过逆向处理, (0)x(1) x(N- 1) 可以复原出所传递的信号(图 x(2) 16.5.3)。这种方法称为数字信号传 输,具有抗干扰能力强、信号还原 质量高、易于加密和解密等优点, 问世后便受到广泛的重视,至今方 兴未艾。 传送 抽样「编码}调制 解调}解码「还 图16.5.3
以后发展了离散的传输方法，它不是传送连续信号本身，而是每 隔一段时间 Δ t ，从信号中提取一个数值脉冲（称为数值抽样），将连 续信号转化成数据序列 x( ) 0 ， x( ) 1 ， x )2( ，…，x N( ) − 1 （图 16.5.2）， 再经编码后发送。只要抽取的时间间隔足够小，这列数据就能很好地 反映原信号，接收方通过逆向处理， 可以复原出所传递的信号（图 16.5.3）。这种方法称为数字信号传 输，具有抗干扰能力强、信号还原 质量高、易于加密和解密等优点， 问世后便受到广泛的重视，至今方 兴未艾。 N 1 t 2 − t 1 t 0t Δt x (0) x(1) x(2) x ( ) N − 1 传送 抽样 编码 调制 解调 解码 还原 图 16.5.3
可以想见的是,为了保证接收的质量,△必须取得很小,即N非 常之大。因此,直接发送这列数据将会长时间地占用传输设备和线路, 这不但需要支付昂贵的费用,在情况紧急时甚至会误事 所以,在抽样之后需要对数据序列x(O),x(1),…,x(N-1)进行 简化和压缩,但由于序列中数据的大小是散乱的,因此一方面我们不 能随意舍弃某些数据,另一方面压缩的效果也比较差。 后来经研究发现,若对数据序列xO),x(1),…,x(N-1)施以如 下的离散 Fourier变换 X()=∑x(m)e (j=012,…,N-1,i=√-1) 就可以有效地解决上面的问题
可以想见的是，为了保证接收的质量， Δ t 必须取得很小，即 N 非 常之大。因此，直接发送这列数据将会长时间地占用传输设备和线路， 这不但需要支付昂贵的费用，在情况紧急时甚至会误事。 所以，在抽样之后需要对数据序列 x( ) 0 ， x( ) 1 ，…， x N( ) − 1 进 行 简化和压缩，但由于序列中数据的大小是散乱的，因此一方面我们 不 能随意舍弃某些数据，另一方面压缩的效果也比较差。 后来经研究发现，若对数据序列 x( ) 0 ， x( ) 1 ，…， x N( ) − 1 施以如 下的离散 Fourier 变换1 2 πi 0 ( ) ( )e N nj N n X j xn − − = = ∑ （ j = " N −1,,2,1,0 ，i 1 = − ） 就可以有效地解决上面的问题
利用正交关系式 2 e 0,j≠k 可以导出离散 Fourier逆变换 2Ti- k x(k)=∑X()e k=01.2……N-1 这是因为 ∑X(e=N>>xmee 2π2ti ∑x(o)∑e ∑x(n)6nk=x(k)。 也就是说,若发送方将x(0),x(1),…,x(N-1)作了离散 Fourier变换 后传输出去,接收方可以对收到的数据进行离散 Fourier逆变换,再 现原始信号
利用正交关系式 1 2 πi 2 πi , 0 1 e e N n j nk N N j k N n δ − − = ∑ = ⎩ ⎨ ⎧ ≠ = = kj kj ,0 ,,1 可以导出离散 Fourier 逆变换1 2 πi 0 1 ( ) ( )e N j k N j xk X j N − = = ∑ ，k = " N −1,,2,1,0 ， 这是因为 1 2 πi 0 1 ( )e N j k N j X j N − = ∑ 1 1 2 πi 2 πi 0 0 1 ( )e e N N nj jk N N j n x n N − − − = = = ∑∑ 1 1 2πi 2 πi 0 0 1 () e e N N n j jk N N n j x n N − − − = = ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ ∑ ∑ ∑ − = = 1 0 , )( N n kn nx δ = x k( )。 也就是说，若发送方将 x( ) 0 ，x( ) 1 ，…，x N( ) − 1 作了离散 Fourier 变 换 后传输出去，接收方可以对收到的数据进行离散 Fourier 逆变换， 再 现原始信号
从表面看来,这么做似乎毫无必要,因为变换后的数据长度仍是 N,并没有缩短,况且还要额外支出两次变换的代价。其实不然。 从变换公式容易看出,变换后的序列中的每个X(),都包含了原 序列中所有信号的信息。因此,即使丢失了某些X(),仍可望由其余 数据基本正确地还原岀原始数据。这当然使得传输过程的抗干扰能力 进一步提高,但更重要的是,这可以让我们通过有意剔除某些模较小 的数据(通常这类数据数量很大)而使需传输的序列大为缩短。此外, X(0),X(1),…,ⅹ(N-l)的排列将很有规律,模较大的数据往往集中 在序列中一两个较窄的范围内,易于作高效的压缩处理
从表面看来，这么做似乎毫无必要，因为变换后的数据长度仍是 N ，并没有缩短，况且还要额外支出两次变换的代价。其实不然。 从变换公式容易看出，变换后的序列中的每个 X j ( )，都包含了原 序列中所有信号的信息。因此，即使丢失了某些 X j ( )，仍可望由其余 数据基本正确地还原出原始数据。这当然使得传输过程的抗干扰能力 进一步提高，但更重要的是，这可以让我们通过有意剔除某些模较小 的数据（通常这类数据数量很大）而使需传输的序列大为缩短。此外， X( ) 0 ，X( ) 1 ，…，X N( ) − 1 的排列将很有规律，模较大的数据往往集中 在序列中一两个较窄的范围内，易于作高效的压缩处理
例16.5.1对长度为64的序列{x(k)}做离散 Fourier变换,其取 值如图16.5.4(a)中的“+”所示,变换后的X()的模用“o”表示。 从图中可以看到,x(k)}的变化很大,有高低不同的四个起伏。 但做了 Fourier变换后,{|X()}只是在序列的起首和终止处附近有两 个高的起伏,而处于序列中部的数据,其模的波动范围是不大的。也 就是说,{X()排列确实很有规律,易于作进一步的处理 08000000 0000000000 0 o40 6-a 01020304050607001020 图16.5.4
例 16.5.1 对长度为 64 的序列{ ( )} x k 做离散 Fourier 变换，其取 值如图 16.5.4(a)中的“+”所示，变换后的 X j ( )的模用“o”表示。 从图中可以看到，{ ( )} x k 的变化很大，有高低不同的四个起伏。 但做了 Fourier 变换后，{| ( )|} X j 只是在序列的起首和终止处附近有两 个高的起伏，而处于序列中部的数据，其模的波动范围是不大的。也 就是说，{ ( )} X j 排列确实很有规律，易于作进一步的处理
此外,我们还发现,{X(m)}中约有三分之一的点(虚线以下)的 模接近于零。现在我们将这些点全部强行置为零后,再对整个序列进 行 Fourier逆变换,这相当在序列中删除了这些数据后再传输出去, 让对方仅用剩下的那部分模较大数据进行逆变换。图16.5.4(b)显示 了所得的结果,这里{x(k)仍用“+”表示,逆变换后得到的相应值 用“o”表示,我们发现,除了极个别点误差稍大之外,两者的近似 程度是相当令人满意的。 08000000 0000000000 0 o40 6-a 01020304050607001020 图16.5.4
此外，我们还发现，{ ( )} X j 中约有三分之一的点（虚线以下）的 模接近于零。现在我们将这些点全部强行置为零后，再对整个序列进 行 Fourier 逆变换，这相当在序列中删除了这些数据后再传输出去， 让对方仅用剩下的那部分模较大数据进行逆变换。图 16.5.4(b)显示 了所得的结果，这里{ ( )} x k 仍用“+”表示，逆变换后得到的相应值 用“o”表示，我们发现，除了极个别点误差稍大之外，两者的近似 程度是相当令人满意的
快速 Fourier变换 尽管早就发现离散 Fourier变换有如此诱人的好处,但在一个相当 长的时期中,人们对它基本上只限于纸上谈兵。这是因为,做一次变 换需要进行N次复数乘法和N(N-1)次复数加法,实际使用中的N总 是极为巨大的,相应的高昂代价令人望而却步
快速 Fourier 变换 尽管早就发现离散 Fourier 变换有如此诱人的好处，但在一个相当 长的时期中，人们对它基本上只限于纸上谈兵。这是因为，做一次变 换需要进行 N 2次复数乘法和 N N( ) −1 次复数加法，实际使用中的 N 总 是极为巨大的，相应的高昂代价令人望而却步
直到20世纪60年代中期, Cooley和 Tukey发现了计算离散 Fourier变换的高效(同时又特别适合于计算机硬件操作)的方法 一快速 Fourier变换(简称FFT- Fast Fourier transform)之后,它 才真正获得了生命力。可以毫不夸张地说,基于FFT的离散 Fourier 变换技术,是当今信息传输(图16.5.5)、频谱分析、图象处理、数 据压缩等领域中最重要的数学工具之一。目前,国际上任何一个综合 的数学软件中,必定含有FFT的计算程序。 传送 码乐缩调制倒解调解压解吗医厨 FFT L逆FFT 图16.5.5
一直到 20 世纪 60 年代中期，Cooley 和 Tukey 发现了计算离散 Fourier 变换的高效（同时又特别适合于计算机硬件操作）的方法 — — 快速 Fourier 变换（简称 FFT—Fast Fourier Transform）之后，它 才真正获得了生命力。可以毫不夸张地说，基于 FFT 的离散 Fourier 变换技术，是当今信息传输（图 16.5.5）、频谱分析、图象处理、数 据压缩等领域中最重要的数学工具之一。目前，国际上任何一个综合 的数学软件中，必定含有 FFT 的计算程序。 传送 抽样 编码压缩调制 解调解压解码 还原 FFT 逆 FFT 图 16.5.5
下面对FFT的思想作一简单介绍 设N=2m,将j和n分别改写成 0,1,…,m-1, J=mJ Jo 1 0.1 和 n, t no h 记W 2 w. W=e W2m=WN=1 e =(WN)j=(WN)(2m+lo X m ji+jo (WN) J(W)mnoA(W)2m Jo(W)"o Jo=(-1)"oh. Wmn)"l Jo. W)"o Jo
下面对 FFT 的思想作一简单介绍。 设 N = 2m，将 j 和n分别改写成 j mj j = 1 0 + ，⎩⎨⎧ = −= 1,0 ,1,,1,0 10jj " m 和 n nn = 2 1 0 + ，⎩⎨⎧ −== ,1,,1,0 ,1,0 10 n m n " 记 2πi e N WN − = ，则 2πi 2 e m W W N m − = = ， πi e 1 m WN − = = − ， W W N m N 2 N = = 1， 2πi e nj N − = ( ) WN n j = + + ( ) W ( )( ) N 2n n mj j 10 10 = ( ) WN 2mn j 1 1 ( ) WN mn j 0 1 ( ) WN 2n j 1 0 ( ) WN n j 0 0 = ( ) −1 0 1 n j ⋅( ) Wm n j 1 0 ⋅( ) WN n j 0 0