滑动窗FFT递推算法研究+MATLAB仿真程序

菜单

摘要离散傅立叶变换（DFT）与它的快速算法快速傅立叶变换（FFT）是数字信号处理中非常重要的且强有力的数学工具之一。快速傅立叶变换因为运算效率较高的缘故，成为了数字信号处理中进行频谱分析的常用方法。但是，在滑动窗的窗口长度较大且窗口滑动步距较小的情况下，传统的FFT算法由于运算量相对来说很大，无法完成数据的实时处理，不能满足对实时性需求比较高的系统的要求。李文忠等人提出了滑动FFT递推算法，在多点滑动DFT算法的基础上，对局部序列运用FFT Pruning算法进行优化，充分利用了前窗计算结果并去除了蝶形运算中的无效路径，大大减少了计算量，提高了运算效率。本文对该算法进行了仔细的分析研究，并通过MATLAB对该算法的效果进行了验证。42465

毕业论文主关键词：FFT；滑动DFT算法；FFT Pruning算法；MATLAB仿真

毕业设计说明书外文摘要

Title RESEARCH ON THE SLIDING RECURSIVE FFT ALGORITHM

Abstract

Discrete Fourier transform (DFT) and its fast algorithm or fast Fourier transform (FFT) is one of the most important and useful mathematical tools in digital signal processing. Due to the high efficiency of the fast Fourier transform, it becomes a common method for spectrum analysis in digital signal processing. However, when the window-order is lager or the sliding-step is smaller, the traditional FFT algorithm cannot be realized in the real time system for the enormous computational complexity. Li Wenzhong et al propose an improved sliding DFT algorithm based on recursive FFT Pruning. The improved algorithm is fully using the last window FFT results and converts the input sequences to a special pruning sequence which only contains few nonzero data points. The improved algorithm not only reduces the calculation of the discrete Fourier transform (DFT), but also improves the flexibility and real time implementation. In this paper, the algorithm is carefully analyzed, and the effect of the algorithm is verified by MATLAB.

Keywords: FFT; Sliding DFT algorithm; FFT Pruning algorithm; MATLAB simulation

1 绪论… 1

1.1 引言 1

1.2 论文的主要工作 2

2 相关算法介绍… 3

2.1 FFT算法 3

2.2 滑动DFT算法 5

2.3 FFT Pruning算法 … 8

3 滑动FFT递推算法 … 11

3.1 滑动FFT递推算法推导 … 11

3.2 滑动FFT递推算法MATLAB仿真与验证 … 13

结论 18

致谢 19

参考文献20

附录 MATLAB仿真程序 22

1 绪论

1.1 引言

离散傅立叶变换（DFT）通过将信号从时域变换到频域进行处理，并将处理结果由离散傅里叶逆变换（IDFT）变换到时域，成为了数字信号处理中实现频谱分析最常用的工具[1]。同时，诸如滤波、相关、谱估计等许多算法也可以转化为DFT进行实现。可以说，DFT在数字信号处理领域中的地位举足轻重，要对信号与系统进行研究，无法绕开DFT这个核心课题。

离散傅立叶变换对的公式为：

根据式(1)我们可以得到，直接完成一次N点DFT运算要进行N 2次复数乘法运算以及N(N-1)次复数加法运算。而完成1次复数乘法运算则需进行4次实数乘法运算以及2次实数加法运算，完成1次复数加法运算则需要进行2次实数加法[2]。通过简单的计算我们发现，当对DFT进行直接计算时，整个过程的运算量与N 2成正比，随着DFT区间长度N的增加，运算量也急剧的增长。