数字信号处理和信号与系统（薛云）第3章3.5-3.7 快速傅里叶变换FFT本.pptVIP

* 和前面的分式比较，分母不变，分子N1变成2N2，所以比值变小。 例如N2＝16，N1＝1024 ere * 从上面的讨论知道，当信号x(n)的长度和滤波器的单位取样响应h(n)的长度相差不大时，用循环卷积计算线性卷积比直接计算线性卷积的速度要快。 但是，当x(n)是一个很长的序列时，由于h(n)必须补很多零，因而循环卷积计算方法的效率将降低。同时，如果一次输入点数太多，则要求计算时占用很大的存储量。长序列的输入需要从存贮器上传输过来，这会浪费cpu资源. 为了克服这些困难，可采用分段卷积的方法。分段卷积方法的计算过程是：首先把x(n)分成长度为L的若干段，这里L比h(n)的长度略长，但确实是同一个数量级，这样便于利用fft的优势；然后用循环卷积方法计算每段与h(n)的卷积；最后利用线性性质,把各段的卷积结果以适当的方式拟合在一起。 L=N-M+1,N为大于短序列长度M的2的整次幂数.然后利用线性性质组合得到结果 本质上,这样做的目的是为了化整为零之后更好的利用fft节省计算量. 那么方法的关键点就是如何对原有的长序列进行分段，如何计算每一段和h(n)的卷积，最后又如何把结果整合起来，根据这方面的思路不同， 分段卷积方法有重叠相加法和重叠保留法两种。 * 利用线性时不变系统的性质说明，因为x_k(n)的起点不是原点，所以各自和h(n)的线性卷积也做相应的移位. 注意，现在每一部分的序列长度和M接近，所以那么每一部分对应的卷积都可以采用fft进行计算。 链接到p67 * 末尾补0之后计算两个长度为N的序列的循环卷积， 但是注意每段x_k(n)利用fft做完循环卷积之后，结果y_k(n)在时间轴上要做相应的移位L，这才对应原来的线性卷积. 注意：是移位L,然后相加，所以有重叠部分 * 从图(a)上可以看成，确实把原序列分成长度为L的短序列，并且尾部补0，这样得到的结果(b)图，可以看出每一段的卷积结果都彼此移位L，但是长度都是N，所以有重叠 * 这种方法比较直观，使用的也比较多，要求能够掌握。 * 在重叠相加法中，将长序列分解为互不重叠的子段，然后将子段和单位脉冲响应进行快速线性眷积运算，再相加得到最终的结果。 此时卷积的结果是有重叠的. 而重叠保留法则通过不同的方式对长序列进行分解，然后也将子段和单位脉冲响应进行循环卷积，然后取出循环卷积中和线性卷积相同的部分。 . 从（1）中可以看出，实际上现在的序列长度是N，那么（2）中做循环卷积的话会出现什么情况呢 * 根据前面的内容，可以知道序列周期卷积是它们的线性卷积的周期N延拓。对周期卷积取主值得到循环卷积,所以 结果将出现混叠，混叠发生在y‘_k(n)的起始部分，因此，y’_k(n)的开始部分有M一1个点是不正确的， * 在重叠相加法中，将长序列分解为互不重叠的子段，然后将子段和单位脉冲响应进行快速线性眷积运算，再相加得到最终的结果。 此时卷积的结果是有重叠的. 而重叠保留法则通过不同的方式对长序列进行分解，然后也将子段和单位脉冲响应进行循环卷积，然后取出循环卷积中和线性卷积相同的部分。 * 最后对循环卷积的结果进行移位得到对应的线性卷积中的一段数据。 * 但是，另外一个问题产生了，因为每次舍弃卷积的前面M-1个点，那么实际的y(n)最前面M-1个点也会被丢掉，因此需要在最前面干脆加上M-1个0，那么此时前面的M-1个点卷积结果本来就是0，舍弃掉也没有影响了。 * * * * 可以看出，M=3, * 实际上，重叠相加法的应用更多 * 本章内容结束，之后ppt页码都是前面的超级链接内容 * 为什么采用这两条规则，我们在运算中加以分析和验证 * 两种变换都是针对序列,我们可以通过定义式比较ＤＦＴ与序列傅立叶变换ＤＴＦＴ的关系. 虚线包络是DTFT, 在这些离散点上的取样值就是X(k)， DFT * 延长序列的原因是为了满足L=2N-1 * * 定义了序列的循环移位之后, 我们可以进一步定义循环卷积 如果频域当中y(k)是两个序列各自dft的逐点乘积,那么类似与以前介绍的卷积定理,时域中我们可以有:…. 和周期卷积比较: 相同点: 序列的乘积对m也是以N为周期的，仅在一个周期内求和。 2.差异:卷积符号不同,周期卷积是n的一个周期函数,循环卷积则是他的主值. P88：加上缺失内容 * here 考虑增加一个插图，即保存的fft计算量.fig，对应源码为 expn=[1:8]; n=2.^expn; %·?±e?????±?óà?ó??¨ò?oífftμ??′êy3?·¨′?êy dftmul=n.^2; fftmul=n./2.*log2(n); plot(n,dftmul); hold on; plot(