当前位置:首页 >> 信息与通信 >>

快速傅里叶变换的原理与方法


第 22 卷第 2 期 2006 年 6 月


Journal of










of


Electric


Power

Shan

ghai

University

Vol. 22,No. 2 June 2006

==============================================================================

文章编号:1006 - 4729 2006) - 0192 - 03 ( 02

快速傅里叶变换的原理与方法
曹伟丽
( 上海理工大学 理学院, 上海 200093) 摘 要:对样本点为 N = 2 γ 的离散傅里叶变换, 按照库利# 图基按时间抽取的方法, 得到一组等价的迭代方

程, 对方程中对偶结点对的性质作了详细分析, 由此简化了方程中的计算公式$ 与直接计算相比, 大大减少了 运算次数, 并且计算过程中除了 N 个初始数据所占的存储单元外, 不需再设置其他存储单元. 关键词:快速傅里叶变换; 离散傅里叶变换; 对偶结点对; 运算次数 中图分类号:O241 文献标识码:A

Principle and Methodology of the Fast Fourier Transform
CAO Wei8 li
( %&'()(*(+ ,- ./)+&/+,0&)1+2')(3 ,- .45&645) -,2 ./)+&/+ 5&7 8+/4&,9,63, .45&645): 200093,;4)&5)

Abstract: A99o:;in< =o Coole> 8 ?u@e> ;e9iAB=ion in =iAe,B Ce= oD eEuiFBlen= i=e:B=ion eEuB=ionC 9Bn Ge oG=Bine; in :e<B:; =o =He ;iC9:e=e Iou:ie: =:BnCo:A oD =He CBAJle Join= N = 2 γ . KlBGo:B=e BnBl>CiC on 9HB:B9=e:iC=i9C oD =He ;uBl no;e JBi:C in =He eEuB=ion =He:eou= CiAJliDieC i=C 9Bl9ulB=ionBl Do:AulB. Ln 9oAJB:iCon Mi=H ;i:e9= oJe:B=ion,=HiC Ae=Ho; <:eB=l> :e;u9eC i=C ;e<:ee oD oJe:B=ion. NeCi;eC,no Ao:e Ce==in<C B:e nee;e; on C=o:B<e 9ellC eO9eJ= =HoCe o99uJie; G> N =iAeC ini=iBl ;B=B in =He 9Bl9ulB=ion J:o9eCC. Key words: oJe:B=ion 傅 里叶变换的理论与 方 法 在 数 理 方 程" " , " 线性系统分析" 信号处理, , " 仿真" 等很多学科 领域都有着广泛的应用, 由于计算机只能处理有 限长度的离散的序列, 所以真正在计算机上运算 的是一种离散傅里叶变换. 次复数乘法及 N = 1 次复数加法, 要完成这组变 2 换共需 N 次复数乘法及 N N = 1) ( 次复数加法$ 但以下介绍的快速傅里叶变换的算法, 可大大减 少运算次数, 提高工作效率$ 当 N = 2 γ 时, 和 > 可用二进制数表示为 & γ =1 γ =2 & = 2 & γ = 1 A 2 & γ = 2 A … A &0 = & γ = 1 & γ = 2 …&0 · > = 2 γ = 1 > γ = 1 A 2 γ = 2 > γ = 2 A … A >0 = > γ = 1 > γ = 2 …>0 · 又记 W = e N , (1) 则式 可改写为 < & γ = 1 & γ = 2 …&0 ·)= (
>0 = 0 >1 = 0
- @2π

DBC= Iou:ie: =:BnCDo:A; ;iC9:e=e Iou:ie: =:BnCDo:A; ;uBl no;e JBi:; ;e<:ee oD

1

快速傅里叶变换算法
离散傅里叶正变换为 < &)= ∑ ?( >) ( e 0
> =0 N =1
- @2π&> N

: & = 0, 1…, = 1 (1) N [1]

可知, 对每一个 &, 计算 < &) ( 须作 N 由式 (1)
收稿日期:2006 - 04 - 17

WB ∑ ∑ … ∑ ?( > γ = 1 > γ = 2 …>0 ·) 0
>γ = 1 = 0

1

1

1

(2)

曹伟丽: 快速傅里叶变换的原理与方法

193

式中: = nk = γ - 1 n γ - 1 + 2 γ - 2 n γ - 2 + … + n0 )× P (2 (2 γ - 1 k γ - 1 + 2 γ - 2 k γ - 2 + … + k0 ) W =W W
p (2 γ - 1 n γ - 1 + 2 γ - 2 n γ - 2 + … + 2n1 + n0 ) γ - 1 k γ - 1 2 (2 γ - 1 n γ - 1 + 2 γ - 2 n γ - 2 + … + n0 ) γ - 2 k γ - 2 2
γ - 1n γ - 1 + … + n0 ) - j2π N

有 k = i, k = j = i + N / 2 l . 因此, 与 用上一组的两个 数据计算所得的两个新数据仍可储存在原来位 与 置, 计算过程中只需要 N 个存储器. 将 x( i) x l l (i + N / 2 l ) 称为第 L 个数组中的对偶结点对. 计算

… (3)

0 W k(2

每个对偶结点对只需一次乘法, 事实上由式 (6) 可得

因为 W W
2 γ - 1 n0 k γ - 1



= W N =[ e

N ] = 1, 以 W p = 所 k γ - 1 + … + n0 ) 0

W

(2n1 + n0 ) γ - 2 k γ - 2 2

…W

(2 γ - 1 n

式 (2) 可改写为 X nγ -1 nγ -2 …n0 ·) ∑ … ∑ x(kγ -1 kγ -2 …k0 ·) ( ∑ 0
k0 =0k1 =0
γ -2

1

1

1

k γ -1 =0

{ {

x( i)= x l -( i)+ x l - 1 i + l 1

(

N W P1 2l

N N x( i + l )= x l -( i)+ x l - 1 i + l W P2 l 1 2 2
γ -2

(

)

)

(8)

W2 令

γ - 1n k 0 γ -1

(2n 2 W 1 + n0 )

γ - 2k

(2 …W

γ - 1n

k γ - 1 + … + n0 ) 0

(4)

P 式中: 1 = 2

nl - 2 + … + 2

γ-l

n0 ; 2 = 2 γ - l + 2 γ - 2 P

n l - 2 + … + 2 γ - l n0 分别为式 (7) n l - 1 取 0, 时对 中 1
1

1 0 x(n0 kγ - 2 …k0 ·)= kγ∑= 0x(kγ - 1 kγ - 2 …k0 ·) -1 γ -1 W2 n0kγ - 1 1 x(n0 n1 kγ - 3 …k0 ·)= k ∑= 0x(n0 kγ - 2 …k0 ·) 2 1 γ -2 (2n 2γ - 2 W 1 + n0) kγ - 2 (5) 1 1 γ x(n0 n1 …nγ - 1 ·)= k∑0xγ -(n0 n1 …nγ - 2 k0 ·) 0= γ - 1n γ - 2n (2 k γ -1 +2 γ - 2 + … + n0)0 W X γ - 1 nγ - 2 …n0 ·)= x(n0 n1 …nγ - 1 ·) (n γ

应的 P 值. 因 P2 = P1 + 2 γ - 1 = P1 + N / 2, 于是对偶 结点的 W P 有如下关系: W P2 = W P1 + 2 =[ e (6) 可表为 x( i)= x l -( i)+ x l -( i + l 1 1 N ) P W 2l
N - j2π N

P ]1 + 2 = - W P1 , 此 式 因

N

则式 (5) 即为式 (4) 的分解形式. 将初始数据 x( k)= x( k γ - 1 k γ - 2 …k0 ·) 代入式 (5) 的第一个 0 0 等式, 可得第一组计算数据, 一般将第 L - 1 组计 算数据代入式 (5) 的第 L 个等式, 计算后可得第 L 组计算数据 L = 1, …, ) 计算公式也可表示 ( 2, γ , 为 x( n0 n1 …n l - 1 k γ - l - 1 …k0 ·)= 1
kγ - 1 = 0 (2 W 1

∑ x l -( n0 n1 …n l - 2 k γ - l k γ - l - 1 …k0 ·) 1
l - 1n γ - 2n γ - ln ) l -1 +2 l -2 + … +2 0 kγ - l

x l -( n0 n1 …n l - 2 0k γ - l - 1 …k0 ·)+ 1 x l -( n0 n1 …n l - 2 1k γ - l - 1 …k0 ·) W 1 式中 P =2
γ -1 p γ -1

根据式 (6) ,第 L 个数组中每个 x( k)= x l l (n0 n1 …n l - 1 k γ - l - 1 …k0 ·) 的计算只依赖于上一数 组的两个数据 x l -( i)= x l -( n0 n1 …n l - 2 0k γ - l - 1 … 1 1 k0 ·) x l - 1 j)= x l - 1 n0 n1 … n l - 2 1k γ - l - 1 … k0 与 ( ( ·) ,这两个数据的标号相差 2 γ - 1 = N / 2 l , j = i 即 + n / 2l, 而且这两个数据只用于计算第 L 个数组 中标号为 k = n0 n1 …n l - 1 k γ - l - 1 …k0 ·的数据 等号 ( . 分别 右端为二进制数) 当 n l - 1 分别取 0 和 1 时,



N N x( i + l )= x l -( i)+ x l -( i + l ) P W l 1 1 2 2

(9)

P 的求法: x( i) i 写成二进制数 n0 n1 … 在 l 中, n l - 1 k γ - l - 1 …k0 ·, 右移 γ - l 位, 就成为 00…0n0 n1 …n l - 1 ·, 颠倒位序得: = n l - 1 n l - 2 …n1 n0 0 …0 · P ( l = 1, …, ) 式 2, γ . (5) 前面的 γ 个等式, 中, 每个 等式均对应一组数据进行计算, 每组数据都有 N / 2 对结点, 根据式 (9) 每对结点只需作 1 次乘法 , 和 2 次加法, 因此, 每组数据只需 N / 2 次乘法和 N 次加法, 因而完成 γ 组数据的计算共需 Nγ / 2 次 乘法和 Nγ 次加法.

2

快速算法的计算机程序流程图
图 1 是快速傅里叶变换算法的计算机程序流

= (6) n0 (7)

程图. 图中的 i = IBR k) ( 为位序颠倒程序, k = 设 n0 n1 …n l ·, i = n1 n l - 1 …n0 ·. 则

nl - 1 + 2

γ -2

nl - 2 + … + 2

3

计算实例
下面给出用离散傅里叶变换近似计算连续傅

里叶变换的一个例子, 并比较传统算法与快速算 法的运算次数. 设 ( t)= f [f ] # ( t) .

{

e - t ,> 0 t 0, < 0 t

,求 ( t) f 的傅里叶变换

194

















2006 年

图1

快速傅里叶变换算法的计算机程序流程图

解: 取样本数为 N = 2 5 = 32, 以时间间隔 T = 0. 25 对 ( t) f 抽样, 则周期为 NT = 8, 在间断点 t = 0 处, 样本点取中值 0. 5. 计算 F n ( NT) = T ∑ e
N -1 k =0 - kt
- j2πnk N

将每对数据对应的复数均乘以 T = 0. 25,即 ( 在 为连续 傅 里 叶 变 换#[ e - t ]= F ω ) ω = n / ( NT) 处的值的近似值.

e

, = 0, …, - 1. n 1, N

4





若用传统算法, 共须作 32 × 32 = 1 024 次复 数乘法, 而用快速傅里叶变换的算法, 只需作 16 × 5 = 80 次乘法. 将 32 个样本点对应的原始数据 输入快速傅里叶变换的程序, 可得到输出的频率 函数的 32 个样本值, 由于离散傅里叶变换的频率 函数以 N = 32 为周期, 又因为其实部与虚部分别 为偶函数与奇函数, 所以只需取前面的 N / 2 = 16 个值. 其实部与虚部见表 1.
表1
序号 1 2 3 4 5 6 7 8

直接计算离散傅里叶变换共需作 N2 次复数 乘法及 N N - 1) ( 次复数加法, 而用快速傅里叶变 换, 只需 Nγ / 2 次乘法和 Nγ 次加法. 直接算法和 加法次数之 快速算法的乘法次数之比为 2 γ + 1 / γ, 比为 γ - 1) γ. 当 γ 增大时, (2 / 比值明显增大, 快 速算法效果更为明显. 因此, 与直接计算相比, 用 快速傅里叶变换算法可大大减少运算次数, 提高 工作效率. 参考文献:

快速傅里叶变换算法的频率函数
虚部 - 0. 00 - 1. 93 - 1. 78 - 1. 39 - 1. 09 - 0. 87 - 0. 71 - 0. 59 序号 9 10 11 12 13 14 15 16 实部 0. 12 0. 10 0. 09 0. 08 0. 07 0. 07 0. 06 0. 06 虚部 - 0. 48 - 0. 40 - 0. 33 - 0. 26 - 0. 20 - 0. 15 - 0. 10 - 0. 05

实部 4. 02 2. 49 1. 17 0. 63 0. 39 0. 27 0. 19 0. 15

[1] E. O. 布赖姆. 快速傅里叶变换 M] 柳 [ . 科学技术出版社, 1979.

群译. 上海: 上海

[2] H. J. 努斯鲍默. 快速傅里叶变换和卷积算法 M] 胡光锐 [ . 译. 上海: 上海科学技术文献出版社, 1984. [3] 程佩青. 数字信号处理教程. 第 2 版 M] 北京: [ . 清华大学出 版社, 2001. [4] 张易知. 虚拟仪器的设计与实现 M] 西安: [ . 西安电子科技 大学出版社, 2002. [5] 蒋正萍. 数字信号处理 M] 北京: [ . 电子工业出版社, 2004.

相关文章:
快速傅里叶变换FFT算法及其应用_———
快速傅里叶变换 FFT 算法及其应用摘 要 本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等 工程技术中的应用。根据抽取方法的不同,一维基 2 ...
快速傅里叶变换的通俗解释_图文
就可以被看成是非周期性 离解信号,我们就可以用到离散时域傅立叶变换的方法。...要知道傅立叶变换算法的意义, 首先要 了解傅立叶原理的意义。傅立叶原理表明:...
离散傅里叶变换和快速傅里叶变换
一、实验目的 1.1 掌握离散傅里叶变换(DFT)的原理和实现; 1.2 掌握快速傅里叶变换(FFT)的原理和实现,掌握用 FFT 对连续信号和离散信号进行谱分析的方法。 ...
快速傅里叶变换
实验二 快速傅立叶变换 一、 实验目的 学习和掌握快速傅立叶变换(FFT) 1. ...二、实验原理与方法 不同的另一种变换, 运算次数的一种快速算法。 FFT 并不...
傅里叶变换的原理及matlab实现
(2)计算方法 连续傅里叶变换将平方可积的函数 f(t)表示成复指数函数的积分...进一步加深对DFT算法原理 和基本性质的理解(因为FFT只是DFT的一种快速算法,所以...
快速傅立叶变换及应用 本科毕业论文
23 大连交通大学 2013 届本科生毕业论文 一、快速傅里叶变换原理及性质数字信号的傅里叶变换,通常采用离散傅里叶变换(DFT)方法。DFT 存在的不足是 2 计算量太...
傅立叶变换的原理、意义和应用
傅立叶变换的原理、意义和应用 1 概念:编辑 傅里叶变换是一种分析信号的方法...的傅立叶变换可以利用数字计算机快速地算出 (其算法称 为快速傅里叶变换算法(...
分治法:快速傅里叶变换算法
myFFT()方法对补 0 重排后序列进行快速傅里叶变换操作,方法的原理是用 三层嵌套的循环来完成 M=log2N(阶数)次迭代,三层循环的功能是:最里的一 层循环完成...
实验五 快速傅里叶变换
三、实验原理 1、FFT 的原理: 快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的一种高效运算方法,它大大简化了 DFT 的运算过程,使运算时间缩短几个数量级。FFT ...
快速傅里叶变换 (FFT)
2. [实验 4.3] 快速傅里叶变换 (FFT) 实现 掌握 FFT 算法的基本原理; 掌握用 C 语言编写 DSP 程序的方法。 二、实验设备 1. 2. 3....
更多相关标签: