第4章快速傅里叶变换(FFT)--补充

1、第4章 快速傅里叶变换 第4章 快速傅里叶变换 补充 N为复合数的为复合数的FFT算法算法 第4章 快速傅里叶变换 4.6 N为复合数的为复合数的FFT算法算法 上面讨论的是序列的点数N为2的幂次(即N=2M)情况下，按时 间抽取和按频率抽取的基 -2FFT算法的基本原理。这种基-2FFT 算法在实际中使用得最多，因为它的程序简单，效率高，使用方 便。但实际上无法保证总是处理长度为2的整数幂次的序列。 若不满足N=2M，处理方法有以下几种: （1）可将x(n)增补一些零值点，以使N增长到最邻近的一个2M 数值。 第4章 快速傅里叶变换 有限长序列补零之后，并不影响其频谱X(ej)，只不过其频谱

2、的抽 样点数增加了，所造成的结果是增加了计算量而已。 但是，有时计算 量增加太多，浪费较大。例如, x(n)的点数N=300，则须补到N=29=512， 要补212个零值点，因而人们才研究N2M时的FFT算法。 有限长度序列补零后并不影响其频谱x(ejw)，只是频谱的采样点数 增加了,当然，采样点的位置也有相应的变化。上例中由30点增加到 32点，采样点则由2/30的整数倍变为2/32的整数倍，对应的绝对 频率也由fs/30的整数倍变为fs/32的整数倍。在许多场合这种处理是 可接受的，不适应对某些特殊频率点有特别要求的场合。 第4章 快速傅里叶变换 （2）若N是一个复合数，即它可以分解成一些

3、因子的乘积， 则可以用FFT的一般算法，即混合基FFT算法，如库利-图基 （CooleyTukey）算法，而基 -2 算法只是这种一般算法的特 例。 总之，不管采用什么方法，计算DFT的高效算法是把计算长度 为N的序列的DFT逐次分解成计算长度较短序列的DFT。这是 很多高效算法的标准方法和基本原理。 第4章 快速傅里叶变换 （3）若）若N为一个素数，要求准确的求出为一个素数，要求准确的求出N点点DFT 可用线性调频可用线性调频Z变换（变换（Chirp-Z变换）算法变换）算法 第4章 快速傅里叶变换 一、整数的多基多进制表示形式 1.二进制（ ）数n 12 101210 ( )22.2 LL

4、LL nnnnn 12 100121 ( )22.2 LL LL p nnnnn 二进制数倒位序 212102 ( )(.) LL nnnn n 20121 2 ( )(.) LL p nn nnn 2LN 2L 第4章 快速傅里叶变换 2. r进制（ ）数n 12 101210 ( ). LL LL nnrnrn rn 12 100121 ( ). LL LL p nn rn rnrn r进制数倒位序 1210 ( )(.) rLLr nnnn n 0 121 ( )(.) rLLr p nn nnn L Nr L r 第4章 快速傅里叶变换 3.多基多进制(混合基 ）数n1 时，随着k的增

5、加螺 线内缩; W0M，则只 需要求得0nM-1一段N点序列值即可; h(n)也可事先准备好，不 必实时分析时计算，因此，可不用考虑其计算量。 同时，h(n) 的L点FFT即H(r)也可预先计算好。 2 2 n W 2 2 n W 第4章 快速傅里叶变换 （3）计算G(r)，q(n), 需要二次L点FFT（或IFFT），共需要L lbL次复乘。 （4） 计算Q(r)=G(r)H(r), 需要L次复乘。 （5）计算X(zk)= （0kM-1），需要M次复乘。 )( 2 2 kqW k 综上所述，CZT总的复数乘法次数为 mc=L lbL+N+M+L （4-46） 前面说过，直接计算式（4-33）

6、的X(zk)需要NM次复数乘法。 可以看出，当N, M都较大时（例如N, M都大于50时），CZT的 FFT算法比直接算法的运算量要小得多。 第4章 快速傅里叶变换 4.8 FFT的其他应用的其他应用 4.8.1 线性卷积的线性卷积的FFT算法算法快速卷积快速卷积 1. FFT的快速卷积法的快速卷积法 以FIR滤波器为例，因为它的输出等于有限长单位脉冲响应 h(n)与有限长输入信号x(n)的离散线性卷积。 设x(n)为L点，h(n)为M点， 输出y(n)为 1 0 )()()( M m mnxmhny 第4章 快速傅里叶变换 y(n)也是有限长序列，其点数为L+M-1 点。 下面首先讨论直 接

7、计算线性卷积的运算量。 由于每一个x(n)的输入值都必须和全 部的h(n)值相乘一次，因而总共需要LM次乘法，这就是直接计 算的乘法次数，以md表示为 md=LM 用FFT算法也就是用圆周卷积来代替这一线性卷积时，为了 不产生混叠，其必要条件是使x(n)，h(n)都补零值点，补到至少 N=M+L-1， 即: （4-65） 0 )( )( nx nx 0nL-1 LnN-1 0 )( )( nh nh 0nM-1 MnN-1 第4章 快速傅里叶变换 然后计算圆周卷积 )()()(nhnxnyN 这时，y(n)就能代表线性卷积的结果。 用FFT计算y(n)的步骤如下： 求H(k)=DFTh(n)，

8、N点； 求X(k)=DFTx(n), N点； 计算Y(k)=X(k)H(k); 求y(n)=IDFTY(k)，N点。 第4章 快速傅里叶变换 步骤、都可用FFT来完成。 此时的工作量如下： 三次FFT运算共需要 次相乘，还有步骤的N次相乘， 因此共需要相乘次数为 bNN 1 2 3 bNNNbNNmF1 2 3 11 2 3 （4-66） 比较直接计算线性卷积(简称直接法)和FFT法计算线性卷积 (简称FFT法)这两种方法的乘法次数。设式（4-65）与式（4-66） 的比值为Km，则 ) 1(1 2 3 1) 1( 1 2 3 1 LMbLM ML bNN ML m m K F d m （4-

9、67） 第4章 快速傅里叶变换 分两种情况讨论如下： （1）x(n)与h(n)点数差不多。 例如，M=L，则N=2M-12M，则 bM M bM M Km 135 1 2 3 2 5 2 这样可得下表： M=L8163264128256512102420484096 Km0.572 0.9411.62.785.928.821629.2454.999.9 当M=8 时，FFT法的运算量大于直接法；当M=32 时，二者 相当；当M=512 时，FFT法运算速度可快16倍；当M=4096 时， FFT法约快100倍。可以看出，当M=L且M超过32以后，M越长， FFT法的好处越明显。因而将圆周卷积称

10、为快速卷积。 第4章 快速傅里叶变换 （2） 当x(n)的点数很多时，即当LM。通常不允许等x(n) 全部采集齐后再进行卷积; 否则，使输出相对于输入有较长的延 时。此外，若N=L+M-1 太大，h(n)必须补很多个零值点，很不经 济，且FFT的计算时间也要很长。这时FFT法的优点就表现不出 来了，因此需要采用分段卷积或称分段过滤的办法。即将x(n)分 成点数和h(n)相仿的段，分别求出每段的卷积结果，然后用一定 方式把它们合在一起，便得到总的输出，其中每一段的卷积均采 用FFT方法处理。有两种分段卷积的办法: 重叠相加法和重叠保 留法。 第4章 快速傅里叶变换 在这一公式中，已经把每一段的时

11、间原点放在该段的起始 点，而不是x(n)的原点。这种分段方法示于图4-28中，每段xi(n) 和h(n)的圆周卷积结果以yi(n)表示，如图 4-28（b）所示，图中 已标出每一段输出段开始的(M-1)个点，0nM-2部分舍掉不用。 把相邻各输出段留下的序列衔接起来，就构成了最后的正确输 出， 即 0 )1()( i i MNinyny （4-73） 式中: 0 )( )( ny ny i i M-1nN-1 其他n （4-74） 这时，每段输出的时间原点放在yi (n)的起始点，而不是y(n)的原 点。 第4章 快速傅里叶变换 线 性 相 关 的 FFT 算 法 利 用 FFT 来 计算 相

12、 关 函 数, 也 就 是 利 用 圆 周 相 关 来 代 替 线 性 相 关, 常 称 之 为 快 速 相 关 . 这 与 利 用 FFT 的 快 速 卷 积 相 类 似 ( 它 是 利 用 圆 周 卷 积 代 替 线 性 卷 积 ), 也 要 利 用 补 零 值 点 的 办 法 来 避 免 混 叠 失 真. 第4章 快速傅里叶变换 方法 设 x(n) 的 长 度 为 L 点,y(n) 的 长 度 为 M 点, 要 求 线 性 相 关 利 用 FFT 法 来 求 线 性 相 关, 是 用 圆 周 相 关 来 代 替 线 性 相 关, 选 择 , 令 第4章 快速傅里叶变换 第4章 快速傅里叶

13、变换 4.8.2 信号消噪信号消噪 假设信号在传输过程中，受到噪声的干扰，则在接收端得 到的信号由于受到噪声的干扰，信号将难以辨识。用FFT方法消 噪就是对含噪信号的频谱进行处理，将噪声所在频段的X(k)值全 部置零后，再对处理后的X(k)进行离散傅里叶反变换（IFFT）可 得原信号的近似结果。这种方法要求噪声与信号的频谱不在同 一频段， 否则， 将很难处理。 第4章 快速傅里叶变换 例例 4-5 将上述消噪原理用于语音消噪。图4-30是一个实际例 子，语音信号受到了强烈的啸叫噪声干扰，无法听清语音意思， 如图4-30(a)， 信号淹没在噪声中（信噪比只有-10dB）。试用 FFT方法消噪。

14、先作FFT分析，得到其功率谱如图4-30(b)，可见在频率2.5 kHz附近有一极强分量。 这就是啸叫噪声干扰。图4-30(b)中频 率在30800Hz范围是语音信号。对频谱进行修正，去除噪声频 段，即将大于2.5 kHz部分的X(k)值全部置为零， 图4-30(c)是去 噪后的功率谱。再由反变换（IFFT）重构信号得到原语音信号 如图4-30(d)。这时信噪比为14dB，提高了24dB。 这就是早期的 数字式录音音乐中所采用的消噪方法。 第4章 快速傅里叶变换 图 4-30 语音信号消噪过程 信号淹没在啸叫噪声中； (b) 信号与噪声的功率谱； (a) (c) 去噪后的功率谱； (d) 重构

15、原语音信号 第4章 快速傅里叶变换 4.8.3 FFT在双音多频（在双音多频（DTMF）信号中的应用）信号中的应用 双音多频信号DTMF是按键式电话信令中的一般名称，它等效 于在贝尔系统内部正在使用的按钮式拨号系统。近几年DTMF信号 已经可以应用于需要交互控制的系统中，例如，语音控制、电子 邮件和 ATM交换机等。 在DTMF信令系统中共有八个频率，分为四个高频音和四个 低频音，用一个高频音和一个低频音的组合来代表某一特定的数 字，或字符*和#。按键拨号设计中八个频率的分配方案如图4-31所 示。其中，697 Hz、770 Hz、852 Hz和941 Hz为低频音，1209 Hz、 1336

16、 Hz 和1447 Hz为高频音。例如，按下“*”键时，所选频率为 941 Hz和1209 Hz，反之，如果这两个频率被检测出来，也就是收 到了“*”。此外，还有第四种高频音，为 1633 Hz，目前还未被采 用，留作日后用于特殊服务的四个附加按钮的应用。 第4章 快速傅里叶变换 图 4-31 按键拨号设计中八个频率的分配方案 1633 Hz1477 Hz1336 Hz 123A697 Hz 456B770 Hz 789C852 Hz *0#D941 Hz 1209 Hz 第4章 快速傅里叶变换 DTMF系统可以用模拟手段或数字手段来实现。 当用数字手段 实现时，可以通过软件来模拟合成DTMF

17、信号。在检测端可以用八 个数字滤波器检测DTMF信号， 也可以用其他软件实现信号的检测。 当信号需要在模拟信道上发送时还需加A/D和D/A转换器。 按键频率的识别方案见图4-32。图中，双音信号先被低通滤波 器和高通滤波器分离。低通滤波器的通带截止频率略高于1000 Hz， 而高通滤波器通带截止频率略低于1200 Hz。每一个滤波器的输出 被一个限幅器限制在一个方波内，然后进入窄带带通滤波器。低频 信道中的四个带通滤波器的中心频率分别为697 Hz、 770 Hz、 852 Hz和941 Hz。 高频信道中的四个带通滤波器的中心频率分别为 1209 Hz、1336 Hz、1477 Hz和1633 Hz。当带通滤波器的输出高于 一个特定的门限值时，检波器将显示直流电转换信号。 第4章 快速傅里叶变换 对于DTMF数字信号的检测也可以利用FFT算法来实现，首 先通过FFT计算DTMF信号的频谱，然后检测八个对应频率点的 幅值来确定输入的信号。 如在具有DTMF功能的电话机上按数字键时，电话机自动将 该信号转换成为DTMF信号，并通过电话线将信号传到交换机， 交换机再将该DTMF信号转换为原来的