§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), 再经编码后发送。只要抽取的时间间隔足够小,这列数据就能很好地 反映原信号,接收方通过逆向处理, x(o)x() 可以复原出所传递的信号(图 16.5.3)。这种方法称为数字信号传 输,具有抗干扰能力强、信号还原「A 质量高、易于加密和解密等优点, 问世后便受到广泛的重视,至今方 兴未艾。 t041t2 传送 抽样}编码「调制 解调解码十还原 图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 0 t t x(0) x(1) x(2) x( ) N − 1 传送 抽样 编码 调制 解调 解码 还原 图 16.5.3
可以想见的是,为了保证接收的质量,△必须取得很小,即N非 常之大。因此,直接发送这列数据将会长时间地占用传输设备和线路, 这不但需要支付昂贵的费用,在情况紧急时甚至会误事。 所以,在抽样之后需要对数据序列x(0),x(1),…,x(N-1)进行 简化和压缩,但由于序列中数据的大小是散乱的,因此一方面我们不 能随意舍弃某些数据,另一方面压缩的效果也比较差。 后来经研究发现,若对数据序列x(0),x(1),…,x(N-1)施以如 下的离散 Fourier变换 XO) x(ne j=012,…,N-1,i=√-1) n=0 就可以有效地解决上面的问题
可以想见的是，为了保证接收的质量， 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 x n − − = = （ j = 0,1,2, ,N −1，i 1 = − ） 就可以有效地解决上面的问题
利用正交关系式 e 0,j≠k 可以导出离散 Fourier逆变换 x(k 1之X()3,h=012…N-1, 这是因为 N-1 N-1N-1 2r12 x(n)e N ∑X(e N H2xi丿 ∑x(m)∑ee|=∑x(n),k=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 − − = = = = j k j k 0, 1, , 可以导出离散 Fourier 逆变换1 2πi 0 1 ( ) ( )e N j k N j x k X j N − = = ，k = 0,1,2, ,N −1， 这是因为 1 2πi 0 1 ( )e N jk 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 j k N N n j x n N − − − = = = − = = 1 0 , ( ) N n n n k x = x(k )。 也就是说，若发送方将x(0)，x(1)，…，x(N −1)作了离散 Fourier 变换 后传输出去，接收方可以对收到的数据进行离散 Fourier 逆变换，再 现原始信号
从表面看来,这么做似乎毫无必要,因为变换后的数据长度仍是 N,并没有缩短,况且还要额外支出两次变换的代价。其实不然。 从变换公式容易看出,变换后的序列中的每个X(,都包含了原 序列中所有信号的信息。因此,即使丢失了某些X(),仍可望由其余 数据基本正确地还原出原始数据。这当然使得传输过程的抗干扰能力 进一步提高,但更重要的是,这可以让我们通过有意剔除某些模较小 的数据(通常这类数据数量很大)而使需传输的序列大为缩短。此外 κ(0),ⅹ(1),…,ⅹ(N-1)的排列将很有规律,模较大的数据往往集中 在序列中一两个较窄的范围内,易于作高效的压缩处理
从表面看来，这么做似乎毫无必要，因为变换后的数据长度仍是 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()排列确实很有规律,易于作进一步的处理。 90 50 0000000 20 10 88日 0248:P0aa -10 图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”表示,我们发现,除了极个别点误差稍大之外,两者的近似 程度是相当令人满意的 90 50 00000000 20 10 88日a 0248:P0aa -10 图16.5.4
此外，我们还发现， {X( j)} 中约有三分之一的点（虚线以下）的 模接近于零。现在我们将这些点全部强行置为零后，再对整个序列进 行 Fourier 逆变换，这相当在序列中删除了这些数据后再传输出去， 让对方仅用剩下的那部分模较大数据进行逆变换。图 16.5.4(b)显示 了所得的结果，这里{x(k )}仍用“+”表示，逆变换后得到的相应值 用“o”表示，我们发现，除了极个别点误差稍大之外，两者的近似 程度是相当令人满意的
快速 Fourier变换 尽管早就发现离散 Fourier变换有如此诱人的好处,但在一个相当 长的时期中,人们对它基本上只限于纸上谈兵。这是因为,做一次变 换需要进行N2次复数乘法和N(N-1)次复数加法,实际使用中的N总 是极为巨大的,相应的高昂代价令人望而却步
快速 Fourier 变换 尽管早就发现离散 Fourier 变换有如此诱人的好处，但在一个相当 长的时期中，人们对它基本上只限于纸上谈兵。这是因为，做一次变 换需要进行 N 2 次复数乘法和 N(N −1)次复数加法，实际使用中的 N 总 是极为巨大的，相应的高昂代价令人望而却步
直到20世纪60年代中期, Cooley和 Tukey发现了计算离散 Fourier变换的高效(同时又特別适合于计算机硬件操作)的方法 快速 Fourier变换(简称FFI- Fast Fourier transform)之后,它 才真正获得了生命力。可以毫不夸张地说,基于FFT的离散 Fourier 变换技术,是当今信息传输(图16.5.5)、频谱分析、图象处理、数 据压缩等领域中最重要的数学工具之一。目前,国际上任何一个综合 的数学软件中,必定含有FFT的计算程序 传送 ∪“抽样」编码压缩调制 解调解压解码还原 FFT 逆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, 丿=m/1+Jo 1 0.1 和 n, t no n1=01…,m-1 2πi 记W Wm=e e N=(WNJ=(W)(2m+o X m /+yo) (WN)mnh(W)mmo(Wn)2m Jo(Wn)"o Jo=(1)oh.(Wn)"I Jo. WN)"o Jo
下面对 FFT 的思想作一简单介绍。 设 N = 2m，将 j 和n分别改写成 j = m j + j 1 0， = = − 0,1 0,1, , 1, 1 0 j j m 和 n = 2 n1 + n0 ， = − = 0,1, , 1, 0,1, 1 0 n m n 记 2πi e N WN − = ，则 2πi 2 e m W W N m − = = ， πi e 1 m WN − = = − ， WN m WN 2 N = = 1， 2πi e nj N − = (W ) N n j = + + ( ) W ( )( ) N 2n n m j j 1 0 1 0 = (W ) N 2mn j 1 1 (W ) N mn j 0 1 (W ) N 2n j 1 0 (W ) N n j 0 0 = (−1) n0 1 j (W ) m n j 1 0 (W ) N n j 0 0