关于DSP的FFT算法的分析

摘要：快速傅立叶变换(FFT)技术是数字信号处理中的核心技术，它己广泛应用于数字信号处理的各个领域，长期以来一直是一个重要的研究课题。本文笔者阐述了FFT概述，讨论了快速傅立叶变换数学理论原理以及算法。

关键词：dsp；fft算法

Abstract: the fast Fourier transform (FFT) technique is the core of digital signal processing technology, it has widely used in various fields of digital signal processing, has long been an important research subject. In this paper, the author expounds the summary of FFT, discussed the mathematic theory principle and fast Fourier transform algorithm.

Key words: DSP; FFT algorithm

中图分类号：TN911.7文献标识码：A

引言

近些年来，数字信号处理技术得到了迅速的发展，特别是随着微计算机和超大规模集成电路的飞跃发展，数字信号处理技术亦得到了更大的发展，并且广泛地应用到了国民经济的各行各业，如雷达、声纳、通信、语音处理、图像处理、地震信号处理、生物医学电子学、数字音频和视频设备、电子测量仪器、噪声控制、电力系统的谐波分析、振动分析和故障诊断等方面，取得了突出的成就。

快速傅立叶变换(FFT)技术是数字信号处理中的核心技术，它己广泛应用于数字信号处理的各个领域。

1. 快速傅立叶变换(FFT)的概述

快速傅立叶变换(FFT)是离散傅立叶变换的快速算法，它利用旋转因子W的周期性及对称性，使N点DFT的乘法计算量由N2次降为N/2㏒2N次，以N=1024点为例，计算量仅为原来的4.88%。因此人们公认这一重要发现的问世是数字信号处理发展史上的一个重大的转折点，也可以称之为一个里程碑。以此为契机，加之超大规模集成电路和计算机的飞速发展，使得数字信号处理的理论在过去的40年中获得了飞速的发展，并广泛用于众多的技术领域。总的来说，这40年中FFT的发展方向有两个：

一是针对N等于2的整数次幂的算法，如基2算法、基4算法、分裂基算法等；

一个是N不等于2的整数次幂的算法，它与第一类算法在理论上有着根本的差别，是建立在下标映射和数论上的一套完全新颖的算法。

由于N不等于2的整数次幂的算法编程较为困难，而且数据长度受到较大的限制，实际的应用也比较少，所以本论文只讨论N等于2的整数次幂的算法。

2. 快速傅立叶变换数学理论原理

2.1离散傅立叶变换原理

离散傅立叶变换(DFT)开辟了频域离散化的道路，使得数字信号处理也可以在频域采用数字运算方法进行，它可以作为一种数学工具来描述离散信号的时域与频域表示的关系，大大增加了数字信号处理的灵活性，特别是它的多种快速算法，使得信号的实时处理和设备的简化得以实现，所以离散傅立叶变换不仅在理论上有重要意义，而且在各种数字信号处理中起着核心的作用。

一维傅立叶变换中，设Xn是长为N的复序列，其DFT定义为：

2.2快速傅立叶变换原理

FFT的基本思想在于，将原有的N点序列分解成两个或更多的较短序列，这些较短序列的DFT可重新组合成元序列的DFT，而总的运算次数却比直接的DFT运算少的多，从而达到提高速度的目的。这种分解基本上可分为两类：一类是时间序列X (n)进行逐次分解，称为按时间抽取算法;另一类是将傅立叶变换序列X(k)进行分解，称为按频率抽取算法。

3. 快速傅立叶变换(FFT)数学算法

3.1 基2算法的讨论

（1）级的概念

将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT，进而八个N/8点DFT，N/2个两点DFT。每分一次，成为一“级”运算。因为M=㏒2N，所以N点DFT可分成M级，如图1所示.图中从左到右，依次为m=0级，m=1级,…，m=M-1级。

图1：8点FFT时间抽取算法流程图

（2）蝶形单元

在图1中由于运算形状结构的几何形状像似蝴蝶，故成“蝶型运算单元”，在第m级，有：

p，q是参与本蝶形单元运算的上、下节点的序号，只参与第m级这一个蝶形单元的运算，其输出在第m+1级。每一级运算都含有N/2个蝶形单元，每一个蝶形单元又只需要一次复数乘法，两次复数加法，所以，完成M=Log2N级运算共需要MN/2次复数乘和MN次复数加法。

在第m级，上、下节点q，p之间的距离为

（3）“组”的概念

每一级的N/2个蝶形单元可以分成若千组，每一组有着相同的结构以及牙护因子分布。如m=0级分成了四组，m=1级分成了两组m=M-1分成了一组。因此，可以得出，第m级的组数是N/2m+1,m=0,1,…，M-l

（4）Wr 因子的分布

从每一级Wr因子分布的规律：

m=0级，Wr2，r=0

m=1级，Wr4，r=0,1

…

m=M-1级，WrN，r=0,1, …, N/2-1

3.2基4算法的讨论

令N=4M，对N点DFT可按如下方式作频率抽取：

分别令k=4r，k=4r+2，k=4r+1，k=4r+3，r=0，l，…，N/4-1.有：

一个16点的DFT分成四个四点的DFT，FFT运算只需要两级，基4FFT

算法的基本单元仅有一个纯虚数一j需要做乘法运算。由于基4算法使得FFT运算的级数减少一半，所需的乘法运算量也相应减少。

结语

笔者谈论了快速傅立叶变换(FFT)数学算法，由于自己的水平和篇幅有限，还有许多不足之处，比如：对FFT算法的硬件平台设计、实序列FFT算法等没有讨论到，在今后工作中笔者将继续努力。

参考文献：

[1]赵桂芳等.基于DsP的快速傅立叶变换的实现[J.黄石理工学院学报.2007

[2]苏奎峰，吕强.DSP嵌入式应用系统开发典型实例.电子工业出版社.2005