DFT的快速算法FFT.ppt

4 DFT的快速算法的快速算法FFT 时域抽取基时域抽取基时域抽取基时域抽取基-2FFT-2FFT算法（算法（算法（算法（DIT-FFTDIT-FFT）频域抽取基频域抽取基频域抽取基频域抽取基-2FFT-2FFT算法（算法（算法（算法（DIF-FFTDIF-FFT）逆逆逆逆 DFT DFT 的快速算法（的快速算法（的快速算法（的快速算法（IFFTIFFT）N N为合数的为合数的为合数的为合数的 FFT FFT 算法算法算法算法 （混合基）（混合基）（混合基）（混合基）1DFT的快速算法（的快速算法（FFT）综述）综述l lDFTDFT的运算量的运算量的运算量的运算量l l减少减少减少减少DFTDFT运算量的方法运算量的方法运算量的方法运算量的方法将长度将长度将长度将长度N N变短变短变短变短。例如若将长度变为。例如若将长度变为N/2N/2，则运算量变成：，则运算量变成：利用利用利用利用 的性质的性质的性质的性质 周期性：周期性：周期性：周期性：共轭对称性：共轭对称性：共轭对称性：共轭对称性：可约性：可约性：可约性：可约性：版权所有 违者必究2第三章第2讲DFT的快速算法（的快速算法（FFT）综述）综述l lFFTFFT的算法分类的算法分类的算法分类的算法分类FFTFFT算法首先由算法首先由Cooly-TukyCooly-Tuky提出了提出了基基基基2FFT2FFT算法算法算法算法，它对，它对DFTDFT的发展起到了极大推进作用。随后又出现了的发展起到了极大推进作用。随后又出现了混合基混合基混合基混合基算法算法算法算法。本节仅对本节仅对基基基基2FFT2FFT算法算法算法算法作介绍，内容包括：作介绍，内容包括：FFTFFT的基本的基本的基本的基本思想、时域与频域抽取的基思想、时域与频域抽取的基思想、时域与频域抽取的基思想、时域与频域抽取的基2FFT2FFT算法及其程序实现。算法及其程序实现。算法及其程序实现。算法及其程序实现。l l基基基基-2 FFT-2 FFT算法（算法（算法（算法（DIT-FFTDIT-FFT）指要求长度指要求长度N N满足满足 （MM为整数），若不满足可将为整数），若不满足可将序列补零延长，使其满足长度要求。序列补零延长，使其满足长度要求。l l时域抽取与频域抽取时域抽取与频域抽取时域抽取与频域抽取时域抽取与频域抽取版权所有 违者必究3第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）l l算法的推导算法的推导算法的推导算法的推导时域抽取算法时域抽取算法时域抽取算法时域抽取算法是按是按 的奇偶把时间序列的奇偶把时间序列 分解为两个长分解为两个长为为N/2N/2点的序列，即：点的序列，即：版权所有 违者必究4第三章第2讲上式中上式中 分别为分别为 的的N/2N/2点点DFTDFT，即：，即：这是这是 前前前前N/2N/2点点点点DFTDFT时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）版权所有 违者必究5第三章第2讲对于对于 后后后后N/2N/2点点点点的的DFTDFT显然，可采用显然，可采用蝶式运算图蝶式运算图蝶式运算图蝶式运算图来表示上述前来表示上述前N/2N/2和后和后N/2N/2两式两式 ，如下图所示：如下图所示：时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）版权所有 违者必究6第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）例如例如N=8N=8时的时的DFT,DFT,可以分解为两个可以分解为两个N/2=4N/2=4点点DFT,DFT,如下图：如下图：版权所有 违者必究7第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）同理：同理：,N/2N/2仍可能是偶数仍可能是偶数,可以进一步把每个可以进一步把每个N/2N/2点的序列再按其奇偶部分分解为两个点的序列再按其奇偶部分分解为两个N/4N/4的子序列。的子序列。版权所有 违者必究8第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）其中其中对对 也可进行同样的分解：也可进行同样的分解：版权所有 违者必究9第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）依次类推：依次类推：经过经过经过经过M-1M-1次分解后，可将次分解后，可将次分解后，可将次分解后，可将N N点点点点DFTDFT分解成分解成分解成分解成N/2N/2个个个个两点两点两点两点DFTDFT。这样又一次的分解得到这样又一次的分解得到4 4个个N/4N/4点点DFTDFT，见下图。，见下图。版权所有 违者必究10第三章第2讲典典 型型 例例 题题例：例：例：例：试画出试画出N=8N=8时的完整的时的完整的基基基基-2 DIT-FFT-2 DIT-FFT运算流图。运算流图。版权所有 违者必究11第三章第2讲l l运算量运算量运算量运算量时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）由有关算法的讨论知：当由有关算法的讨论知：当 时，总共应有时，总共应有MM级分解，级分解，每级有每级有N/2N/2个个“蝶式运算蝶式运算”。每个。每个“蝶式运算蝶式运算”需一次复数需一次复数乘、两次复数加运算，这样乘、两次复数加运算，这样MM级总共需要的运算量为：级总共需要的运算量为：如：若如：若N N10241024，直接计算，直接计算DFTDFT与采用与采用FFTFFT运算量之比约为运算量之比约为205205，“快速快速”得以充分体现。得以充分体现。若若若若N N足够大，通过直接计算足够大，通过直接计算足够大，通过直接计算足够大，通过直接计算DFTDFT与采用与采用与采用与采用FFTFFT计算其运算量计算其运算量计算其运算量计算其运算量之比为：之比为：之比为：之比为：版权所有 违者必究12第三章第2讲l lFFTFFT算法的特点算法的特点算法的特点算法的特点时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）倒码倒码倒码倒码观察完整的观察完整的FFTFFT流图能发现有两个特点：流图能发现有两个特点：倒码倒码倒码倒码和和原位运算原位运算原位运算原位运算倒码即码位倒置：是指将原二进制数的码位倒过来倒码即码位倒置：是指将原二进制数的码位倒过来 按从低位到高位排按从低位到高位排列。列。顺序与倒码顺序对照表顺序与倒码顺序对照表顺序与倒码顺序对照表顺序与倒码顺序对照表 顺序顺序顺序顺序 二进制数二进制数二进制数二进制数 倒码倒码倒码倒码 倒码顺序倒码顺序倒码顺序倒码顺序 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 000000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 000000 100 100 010 010 110 110 001 001 101 101 011 011 000 000 0 0 4 4 2 2 6 6 1 1 5 5 3 3 7 7如：如：如：如：N=8N=8时，序号时，序号 “4”4”用三位二进制表示正常码为用三位二进制表示正常码为“100”100”，而其倒，而其倒码为码为 “001”001”，变成了序号，变成了序号“1”1”。版权所有 违者必究13第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）原位运算原位运算原位运算原位运算由完整的由完整的FFTFFT流图可见：流图可见：从左到右计算下一级蝶式运算时，从左到右计算下一级蝶式运算时，从左到右计算下一级蝶式运算时，从左到右计算下一级蝶式运算时，仅需要用到本级的数据而不需要前一级的数据仅需要用到本级的数据而不需要前一级的数据仅需要用到本级的数据而不需要前一级的数据仅需要用到本级的数据而不需要前一级的数据。例如在实施。例如在实施第二级蝶式运算时，仅需要第一级蝶式运算的结果，而不需第二级蝶式运算时，仅需要第一级蝶式运算的结果，而不需要用到原来的输入数据要用到原来的输入数据 。据此就可在数据输入到存储器。据此就可在数据输入到存储器以后，每一级运算的结果存储在同一组存储单元中。直到最以后，每一级运算的结果存储在同一组存储单元中。直到最后输出，中间无需其他存储器。后输出，中间无需其他存储器。利用同一存储单元存放蝶式运算输入和输出数据的方法称为利用同一存储单元存放蝶式运算输入和输出数据的方法称为原位运算原位运算原位运算原位运算。原位运算可节省存储单元，降低原位运算可节省存储单元，降低原位运算可节省存储单元，降低原位运算可节省存储单元，降低FFTFFT硬件实现的硬件实现的硬件实现的硬件实现的设备成本，从而使得设备成本，从而使得设备成本，从而使得设备成本，从而使得FFTFFT算法简单、快速、高效。算法简单、快速、高效。算法简单、快速、高效。算法简单、快速、高效。l lDIT-FFTDIT-FFT算法其他形式的流图算法其他形式的流图算法其他形式的流图算法其他形式的流图由信号流图理论知道：由信号流图理论知道：只要保证各节点所连接的支路及其传只要保证各节点所连接的支路及其传只要保证各节点所连接的支路及其传只要保证各节点所连接的支路及其传输系数不变，无论各节点相对位置如何排列，所得到的流图输系数不变，无论各节点相对位置如何排列，所得到的流图输系数不变，无论各节点相对位置如何排列，所得到的流图输系数不变，无论各节点相对位置如何排列，所得到的流图等效，等效，等效，等效，DFTDFT的结果相同的结果相同的结果相同的结果相同。版权所有 违者必究14第三章第2讲时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）N=8 N=8 时输入是正序、输出是倒码的时输入是正序、输出是倒码的时输入是正序、输出是倒码的时输入是正序、输出是倒码的DIT-FFTDIT-FFT运算流图运算流图运算流图运算流图例如将例如将N=8N=8时基时基2DIT-FFT2DIT-FFT信号流图中与信号流图中与 、水平相连水平相连的所有节点分别同与的所有节点分别同与 、水平相连的所有节点对调，保水平相连的所有节点对调，保持其余节点位置不变，得到新形式的信号流图。持其余节点位置不变，得到新形式的信号流图。版权所有 违者必究15第三章第2讲频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）l l算法的推导算法的推导算法的推导算法的推导频域抽取算法频域抽取算法频域抽取算法频域抽取算法是把时间序列是把时间序列 前后对半分解为两个长前后对半分解为两个长为为N/2N/2点的序列，则：点的序列，则：版权所有 违者必究16第三章第2讲频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）当当当当 k k 取偶数时（取偶数时（k k=2=2 r r，r r=0,1,.,=0,1,.,N N/2/2 1 1）的的N N点点DFT DFT 按按 k k 的奇偶分组可分为两个的奇偶分组可分为两个N/2N/2的的DFTDFT当当当当 k k 取奇数时（取奇数时（k k=2=2 r r1 1，r r=0,1,.,=0,1,.,N N/2/2 1 1）版权所有 违者必究17第三章第2讲频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）这一结论表明：这一结论表明：求求求求 的的的的N N点点点点DFT DFT 再次分解成再次分解成再次分解成再次分解成 求两个求两个求两个求两个N/2N/2 点点点点DFTDFT l lDIF-FFTDIF-FFT的蝶式运算流图的蝶式运算流图的蝶式运算流图的蝶式运算流图版权所有 违者必究18第三章第2讲l lDIF-FFTDIF-FFT的一次分解运算流图的一次分解运算流图的一次分解运算流图的一次分解运算流图频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）先蝶式运算，后先蝶式运算，后先蝶式运算，后先蝶式运算，后 DFTDFT。例如：。例如：。例如：。例如：N=8N=8时时时时版权所有 违者必究19第三章第2讲频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）l lDIF-FFTDIF-FFT的二次分解运算流图的二次分解运算流图的二次分解运算流图的二次分解运算流图通常通常 N/2 N/2 仍然为仍然为 2 2 的整数幂，继续将的整数幂，继续将 N/2 N/2 点点DFTDFT分成偶数分成偶数组和奇数组，这样每个组和奇数组，这样每个 N/2 N/2 点点DFTDFT又可分解成两个又可分解成两个 N/4 N/4 点点DFTDFT，其输入序列分别是，其输入序列分别是 和和 按上下对半分开后通按上下对半分开后通过蝶式运算构成的过蝶式运算构成的 4 4 个子序列，如下图所示：个子序列，如下图所示：版权所有 违者必究20第三章第2讲频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）按照以上方法继续分解下去，经过按照以上方法继续分解下去，经过 M-1M-1 次分解，最后分次分解，最后分解为解为 N/2N/2 个两点个两点DFTDFT，这，这 N/2 N/2 个个2 2点点DFTDFT的输出就是的输出就是 N N 点点DFTDFT的结果的结果X X(k k)，如下图所示：，如下图所示：版权所有 违者必究21第三章第2讲l l有关说明有关说明有关说明有关说明频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）以上给出了以上给出了 N=8 N=8 时完整的时完整的 DIF-FFTDIF-FFT 的运算流图。由于的运算流图。由于这种方法是这种方法是 按按 在频域进行奇偶分解，因此称之为在频域进行奇偶分解，因此称之为频域抽取基频域抽取基频域抽取基频域抽取基2 2 运算运算运算运算。比较比较比较比较与与相同点：相同点：运算次数与存储量相同运算次数与存储量相同运算次数与存储量相同运算次数与存储量相同不同点：不同点：输入序列为自然序列而输输入序列为自然序列而输出为码位倒置序列出为码位倒置序列 蝶式运算过程不同蝶式运算过程不同 是序列先乘旋转因子后相加减是序列先乘旋转因子后相加减 是序列先相加减后乘旋转因子是序列先相加减后乘旋转因子版权所有 违者必究22第三章第2讲逆逆DFT的快速算法（的快速算法（IFFT）l lIFFTIFFT算法的推导算法的推导算法的推导算法的推导比较两式可知：比较两式可知：只要将只要将只要将只要将FFTFFT中的旋转因子中的旋转因子中的旋转因子中的旋转因子 改为改为改为改为 ，再乘以再乘以再乘以再乘以 1/N1/N 即可得到即可得到即可得到即可得到 IDFT IDFT 的快速算法的快速算法的快速算法的快速算法 IFFTIFFT。IFFTIFFT基基基基本思想本思想本思想本思想 ，还可将常数还可将常数 1/N 1/N 分配到每级运算中，分配到每级运算中，也就是每级蝶形运算均乘以也就是每级蝶形运算均乘以 。这样就实现了。这样就实现了 FFT FFT 与与IFFT IFFT 运算的统一。运算的统一。版权所有 违者必究23第三章第2讲1 1、纯软件实现、纯软件实现2 2、硬件实现、硬件实现3 3、DSPDSP（软硬件结合）（软硬件结合）逆逆DFT的快速算法（的快速算法（IFFT）l lFFTFFT（IFFTIFFT）算法的实现）算法的实现）算法的实现）算法的实现版权所有 违者必究24第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）基基2FFT2FFT的各种算法要求的各种算法要求 。若该条件不满足，虽可通过在序列尾部补若该条件不满足，虽可通过在序列尾部补0 0的方法使的方法使 增增加到最邻近的一个加到最邻近的一个 值，从而采用值，从而采用DIT-FFTDIT-FFT或或DIF-FFTDIF-FFT算算法。该方法并不影响法。该方法并不影响DFTDFT的结果，只是增加了采样频率点的结果，只是增加了采样频率点的位置和点数，但该方法至少存在以下两个缺陷：的位置和点数，但该方法至少存在以下两个缺陷：补补补补0 0 0 0太多，长度增加，运算量加大，效率降低太多，长度增加，运算量加大，效率降低太多，长度增加，运算量加大，效率降低太多，长度增加，运算量加大，效率降低 若欲求得指定频率点上的若欲求得指定频率点上的若欲求得指定频率点上的若欲求得指定频率点上的 DFT,DFT,DFT,DFT,无法做到无法做到无法做到无法做到故必须探索新方法故必须探索新方法故必须探索新方法故必须探索新方法版权所有 违者必究25第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）l l算法的推导算法的推导算法的推导算法的推导若序列若序列 的长度的长度 是是合数合数合数合数 ，即：，即：将将 每隔每隔 点抽取一点，则可形成点抽取一点，则可形成 个长度为个长度为 点的点的序列如下：序列如下：版权所有 违者必究26第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）例如：例如：例如：例如：按以上的方法将按以上的方法将 分为分为3 3组，每组长度为组，每组长度为6 6 版权所有 违者必究27第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）将将 代入序列代入序列 的的N N点点DFTDFT有：有：版权所有 违者必究28第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）如此进行下去直到最后变为如此进行下去直到最后变为 点点DFTDFT显然此算法中采用了不同长度来进行抽取，故有时又将显然此算法中采用了不同长度来进行抽取，故有时又将该算法称为该算法称为混合基混合基混合基混合基FFTFFT算法算法算法算法。l l例：例：例：例：试作出试作出 时混合基一次分解为时混合基一次分解为3 3个个6 6点点DFTDFT的的流程图流程图版权所有 违者必究29第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）版权所有 违者必究30第三章第2讲N为合数的为合数的FFT算法（混合基）算法（混合基）经一次分解后的经一次分解后的3 3个个6 6点点DFTDFT，每个又可分解为，每个又可分解为3 3个个2 2点的点的DFT DFT ，如图：，如图：版权所有 违者必究31第三章第2讲l l算法的运算量算法的运算量算法的运算量算法的运算量N为合数的为合数的FFT算法（混合基）算法（混合基）第一次抽取后的运算量：第一次抽取后的运算量：第二次抽取后的运算量：第二次抽取后的运算量：总运算量总运算量总运算量总运算量：总乘法运算次总乘法运算次总乘法运算次总乘法运算次数数数数版权所有 违者必究32第三章第2讲5 DFT 与与 FFT 的应用的应用 利用利用利用利用 FFT FFT 进行频谱分析进行频谱分析进行频谱分析进行频谱分析 用用用用FFTFFT计算线性卷积计算线性卷积计算线性卷积计算线性卷积 线性调频线性调频线性调频线性调频 Z Z 变换（变换（变换（变换（Chirp-ZChirp-Z变换）及快速算法变换）及快速算法变换）及快速算法变换）及快速算法33利用利用 FFT 进行频谱分析进行频谱分析l l利用利用利用利用FFTFFT进行频谱分析的基本方法进行频谱分析的基本方法进行频谱分析的基本方法进行频谱分析的基本方法设设设设 为长为为长为为长为为长为 N N 的有限长序列，则：的有限长序列，则：的有限长序列，则：的有限长序列，则：利用利用利用利用 FFT FFT 进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：版权所有 违者必究34第三章第2讲l l几个常用基本概念几个常用基本概念几个常用基本概念几个常用基本概念利用利用 FFT 进行频谱分析进行频谱分析1 1、数字频率分辨率：、数字频率分辨率：、数字频率分辨率：、数字频率分辨率：2 2、模拟频率分辨率：、模拟频率分辨率：、模拟频率分辨率：、模拟频率分辨率：3 3、用于、用于、用于、用于FFTFFT的采样点数：的采样点数：的采样点数：的采样点数：4 4、频率刻度值：、频率刻度值：、频率刻度值：、频率刻度值：5 5、模拟信号长度：、模拟信号长度：、模拟信号长度：、模拟信号长度：6 6、分辨率：、分辨率：、分辨率：、分辨率：版权所有 违者必究35第三章第2讲典典 型型 例例 题题例：例：用FFT来分析信号的频谱，若已知信号的最高频率为 ，要求频率分辨率为 ，试确定：1、采样间隔 T；2、采用基-2FFT的最小样点数 N，以及与此相对应的最小记录长度；3、按您确定的参数所获得的实际分辨率。解：解：解：解：1 1、据采样定理，采样间隔据采样定理，采样间隔2 2、基基-2FFT-2FFT的最小样点数的最小样点数N N当采用基当采用基-2FFT-2FFT算法时，要求算法时，要求版权所有 违者必究36第三章第2讲典典 型型 例例 题题与此相对应的最小记录长度为：与此相对应的最小记录长度为：3 3、按确定的参数所获得的实际分辨率按确定的参数所获得的实际分辨率版权所有 违者必究37第三章第2讲l l用用用用FFTFFT进行频谱分析存在的两个问题进行频谱分析存在的两个问题进行频谱分析存在的两个问题进行频谱分析存在的两个问题利用利用 FFT 进行频谱分析进行频谱分析1 1、频谱泄漏、频谱泄漏、频谱泄漏、频谱泄漏在实际应用中，通常将所观测与处理的信号限制在一定的时间间隔内，即在时域对信号进行“截断操作”，或 称作加时间窗加时间窗（用时间窗函数乘以信号）。由卷积定理可知：时域相乘、频域卷积，这就造成“拖尾现象”，称之为频谱泄漏频谱泄漏。若序列若序列 的长度为无限长，为了利用的长度为无限长，为了利用 FFT FFT 进行频谱分进行频谱分析，首先必须将其截断为有限长序列析，首先必须将其截断为有限长序列卷积定理卷积定理卷积定理卷积定理显然，两种频谱是有差别的，该现象就是显然，两种频谱是有差别的，该现象就是频谱泄漏频谱泄漏频谱泄漏频谱泄漏解决办法解决办法解决办法解决办法：采用其它形式的窗函数（第六章详论）采用其它形式的窗函数（第六章详论）对于周期序列，取其过零点截取对于周期序列，取其过零点截取版权所有 违者必究38第三章第2讲利用利用 FFT 进行频谱分析进行频谱分析2 2、栅栏效应、栅栏效应、栅栏效应、栅栏效应利用利用 FFT FFT 进行频谱分析时，只知道离散频率点进行频谱分析时，只知道离散频率点 的整数的整数倍处的频谱。在两个谱线之间的情况就不知道，这如同倍处的频谱。在两个谱线之间的情况就不知道，这如同通过一个栅栏观察景象一样，故称作通过一个栅栏观察景象一样，故称作栅栏效应栅栏效应栅栏效应栅栏效应。解决办法：解决办法：解决办法：解决办法：在序列后面补零点加大在序列后面补零点加大FFTFFT点数点数 ，可使谱线，可使谱线间隔变小来提高分辨力，以减少栅栏效应。间隔变小来提高分辨力，以减少栅栏效应。注意：注意：注意：注意：若需要加窗，则应先加窗再补零。若需要加窗，则应先加窗再补零。版权所有 违者必究39第三章第2讲用用FFT计算线性卷积计算线性卷积l l线性卷积线性卷积线性卷积线性卷积设设 是是 和和的线性卷积：的线性卷积：总运算量为：总运算量为：可见，直接运算时运算量很大，必须寻找新思路。可见，直接运算时运算量很大，必须寻找新思路。思路：思路：思路：思路：利用利用利用利用 FFT,FFT,通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积版权所有 违者必究40第三章第2讲l l利用循环卷积计算线性卷积的条件利用循环卷积计算线性卷积的条件利用循环卷积计算线性卷积的条件利用循环卷积计算线性卷积的条件用用FFT计算线性卷积计算线性卷积设设 是是x(nx(n)和和h(nh(n)长为长为L L的循环卷积：的循环卷积：其中其中 LLMaxN,MMaxN,M,版权所有 违者必究41第三章第2讲用用FFT计算线性卷积计算线性卷积版权所有 违者必究42第三章第2讲用用FFT计算线性卷积计算线性卷积上式表明上式表明上式表明上式表明：是将是将 以以L L为周期进行延拓后再取为周期进行延拓后再取主值区间所得的序列。主值区间所得的序列。利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的条件为：条件为：条件为：条件为：利用循环卷积计算线性卷积如下图利用循环卷积计算线性卷积如下图版权所有 违者必究43第三章第2讲用用FFT计算线性卷积计算线性卷积l l利用利用利用利用FFTFFT进行线性卷积的步骤进行线性卷积的步骤进行线性卷积的步骤进行线性卷积的步骤、将已知序列、将已知序列 （长为（长为N N）和）和 （长为（长为MM）补零）补零延长，使它们的长度延长，使它们的长度 。若采用基。若采用基 -2-2 FFTFFT算法，还应使算法，还应使 大于或等于大于或等于 的的 2 2 的最小整数次的最小整数次幂。幂。、做、做 和和 的长为的长为 点的点的 FFT FFT 得到得到 和和 ，并求它们的积并求它们的积 。、求、求 的的 IFFTIFFT并取前并取前 点获得线性卷积的结果为点获得线性卷积的结果为版权所有 违者必究44第三章第2讲l l长序列长序列长序列长序列FFTFFT卷积的计算方法卷积的计算方法卷积的计算方法卷积的计算方法用用FFT计算线性卷积计算线性卷积实际中常常出现两个待卷积序列长度相差很大的情形，实际中常常出现两个待卷积序列长度相差很大的情形，例如输入序列例如输入序列 的长度的长度 远远大于滤波器的脉冲响远远大于滤波器的脉冲响应应 的长度的长度 时时,若仍然取若仍然取 FFT FFT 的长度的长度 ,则必须对则必须对 补很多补很多0 0，同时也做不到，同时也做不到“实时处理实时处理”。此时常采用以下两种分段处理方法。此时常采用以下两种分段处理方法。版权所有 违者必究45第三章第2讲用用FFT计算线性卷积计算线性卷积1 1、重叠相加法、重叠相加法、重叠相加法、重叠相加法设设 长度为长度为 ,为无限长。取为无限长。取“段长段长 ”尽可尽可能能 与与 接近。则：接近。则：是两个长度接近且分别为是两个长度接近且分别为和和 的序列的线性卷积，可很有效地求其的序列的线性卷积，可很有效地求其L L点的点的FFT.FFT.版权所有 违者必究46第三章第2讲用用FFT计算线性卷积计算线性卷积分别求得各段卷积后再将结果相加，即可求得分别求得各段卷积后再将结果相加，即可求得 和和 的完整的线性卷积。的完整的线性卷积。该方法中由于运用了该方法中由于运用了“分段卷积的重叠分段卷积的重叠”和和“各段卷积结各段卷积结果的相加果的相加”，故称为，故称为重叠相加法重叠相加法重叠相加法重叠相加法。用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：将 补零延长到 ，并计算其 点FFT，得 到 分别将各 补零延长到 ，并计算其 点FFT，得到 计算计算 ，并求其，并求其L L点的反变换，即：点的反变换，即：将将 的重叠部分相加，最后得到结果的重叠部分相加，最后得到结果版权所有 违者必究47第三章第2讲用用FFT计算线性卷积计算线性卷积l l重叠相加法卷积示意图重叠相加法卷积示意图重叠相加法卷积示意图重叠相加法卷积示意图版权所有 违者必究48第三章第2讲2 2、重叠保留法、重叠保留法、重叠保留法、重叠保留法用用FFT计算线性卷积计算线性卷积设序列设序列 的长度为的长度为 ，则对长序列，则对长序列 的分段方法如的分段方法如下：先在序列下：先在序列 前补前补 个个0 0，然后对补，然后对补0 0后的序列后的序列进行分段，每段的长度为进行分段，每段的长度为 ,即：即：对每一段对每一段 ，通过循环卷积，通过循环卷积 ，获，获得俩者的线性卷积得俩者的线性卷积 。而输入的每段。而输入的每段序列重叠序列重叠N-1N-1点，故每段的循环卷积的输出应去掉前面点，故每段的循环卷积的输出应去掉前面N-1N-1点只保留后面点只保留后面MM点，即点，即 ：版权所有 违者必究49第三章第2讲用用FFT计算线性卷积计算线性卷积重重重重叠叠叠叠保保保保留留留留法法法法分分分分段段段段方方方方法法法法示示示示意意意意图图图图版权所有 违者必究50第三章第2讲用用FFT计算线性卷积计算线性卷积版权所有 违者必究51第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法l l问题的引入问题的引入问题的引入问题的引入仅管采用仅管采用 FFT FFT 可计算出有限长序列的可计算出有限长序列的DFT DFT，但它要求序，但它要求序列长度列长度 为为2 2的整数幂或合数。实际中的整数幂或合数。实际中有时只对信号有时只对信号的某一频段感兴趣，即只需要计算单位圆上某一段的频的某一频段感兴趣，即只需要计算单位圆上某一段的频谱值，例如对窄带信号进行频谱分析时，总是要求在窄谱值，例如对窄带信号进行频谱分析时，总是要求在窄带范围内的抽样点足够密集，而窄带范围外则不需考虑。带范围内的抽样点足够密集，而窄带范围外则不需考虑。此时若依然采样以上方法，则需增加频域抽样点数，增此时若依然采样以上方法，则需增加频域抽样点数，增加了窄带范围外的不需要的计算量；加了窄带范围外的不需要的计算量；在语声信号处理在语声信号处理时信号极点处的频谱十分关键，而极点位置往往离单位时信号极点处的频谱十分关键，而极点位置往往离单位圆较远，此时不能采用圆较远，此时不能采用FFTFFT；若若 是大素数时也无法是大素数时也无法采用采用FFTFFT。上述几种情形可采用上述几种情形可采用线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法加以解决。版权所有 违者必究52第三章第2讲l l算法的基本原理算法的基本原理算法的基本原理算法的基本原理线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法设设 是有限长序列，是有限长序列，沿沿Z Z平面上的一段螺线做平面上的一段螺线做MM点抽样，得到以下抽样点：点抽样，得到以下抽样点：其中其中A A和和WW为复数为复数,极坐标形式分别为：极坐标形式分别为：式中式中 和和 为实数，当为实数，当K=0K=0时有时有可见，可见，决定谱分析起始点决定谱分析起始点 的位置；的位置；的值决定分析的值决定分析路径的盘旋趋势；路径的盘旋趋势；表示两个相邻分析点之间的夹角表示两个相邻分析点之间的夹角版权所有 违者必究53第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法如果如果 ，则则 的抽样点位于半径为的抽样点位于半径为 r r 的的圆上；如果圆上；如果 ，则，则 的抽样点位于单位圆的抽样点位于单位圆上（常规的上（常规的DFTDFT变换）；如果变换）；如果 ，则随着，则随着k k增大，分增大，分析点析点 以以 为步长向外盘旋；为步长向外盘旋；时向内旋。时向内旋。C Ch hi ir rp p-Z Z变变变变换换换换的的的的频频频频率率率率抽抽抽抽样样样样点点点点版权所有 违者必究54第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法版权所有 违者必究55第三章第2讲lChirp-Z 变换的方框图变换的方框图线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法Chirp-ZChirp-Z变换变换的方框图如下：如下：版权所有 违者必究56第三章第2讲l l说明说明说明说明线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法 上面框图中，上面框图中，可看成一个数字网络的可看成一个数字网络的单位脉冲响应。单位脉冲响应。所对应的系统的输出为：所对应的系统的输出为：这可以设想为频率随时间线性增长的复指数序列这可以设想为频率随时间线性增长的复指数序列,即即线性调频线性调频线性调频线性调频(Chirp)(Chirp)信号信号信号信号。故将上述变换称为。故将上述变换称为线性调频线性调频Z变换变换(Chirp-Z 变换变换)（简称为CZT）版权所有 违者必究57第三章第2讲lChirp-Z变换的实现变换的实现线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法 确定线性卷积的区间。序列 的长度为N，的长度也应是N，而而 是无限长的，需是无限长的，需截取。但因谱分析点数仅为截取。但因谱分析点数仅为MM点，故只需要计算点，故只需要计算 在在 00，M-1M-1上上MM个值。个值。为计算出V(n)在区间0,M-1上的M个值，只要截取h(n)在区间-(N-1),(M-1)上的(N+M-1)个值。这时经线性卷积所得V(n)的非零值区间为-(N-1)，(N+M-2)，长度为2N+M-2。版权所有 违者必究58第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法 确定用循环卷积计算线性卷积时的循环卷积计算线性卷积时的 FFT FFT 长度长度 L L。为了用循环卷积代替线性卷积计算出V(n)在0,(M-1)区间上的 M个序列值，必须保证在上式的周期延拓中，在0，M-1区间上不能有混叠，循环卷积区间长度 L应大于或等于N+M-1。故在用基-2 FFT算法进行快速卷积计算时，应选择应选择L L(N+M-1)(N+M-1)且满足且满足且满足且满足 (m(m为自然数为自然数为自然数为自然数)的最小值的最小值的最小值的最小值。计算计算Chirp-Z 变换变换所用的序列见下图版权所有 违者必究59第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法版权所有 违者必究60第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法注意注意:若选择L=N+M-1，那么y(n)尾部应补M-1个零。并将h(n)从-(N-1)到(M-1)所截取的一段序列以L为周期进行周期延拓，取主值序列形成 ，这时可以用快速卷积法计算如上构造的两个序列y(n)和 的循环卷积。当选择 N+M-1时，y(n)应补L-N个零点，而h(n)从区间(-N+1)，(M-1)截取后在-N+1点前面补 L-N+M-1)个零点后，以L为周期进行周期延拓。或直接截取-（L-M），（M-1）上的值后，再以L为周期进行周期延拓取主值。版权所有 违者必究61第三章第2讲lChirp-Z 变换算法具体步骤变换算法具体步骤线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法 形成形成 序列序列 计算计算 的的 FFTFFT 作序列作序列版权所有 违者必究62第三章第2讲线性调频线性调频Z变换变换(Chirp-Z 变换变换)算法算法 计算计算 的的 FFTFFT 计算计算 的的 IFFT IFFT 得得 求求版权所有 违者必究63第三章第2讲