当前位置:首页 >> 教育学/心理学 >>

FFT算法研究及基2-FFT算法的C语言实现


毕 业 设 计 [ 论 文]

题 学 专 姓 学

目:FFT 算法研究及基 2-FFT 算法的 C 语言实现 院: 业: 名: 号: 电气与信息工程学院 电气工程及其自动化 XXX XXXXXX XXX 2015 年 06 月 01 日

指导老师: 完成时间:

河南城建学院本科毕业设计(论文)

摘要

摘 要
离散傅立叶变换(DFT)常常用于计算信号处理。DFT 算法可以得到信号的 频域特性,因为该算法在计算上是密集的,长时间的使用时,计算机不能实时进 行信号处理。所以 DFT 被发现之后的相当长时间内是没被应用到实际的项目。到 了二十世纪六十年代中期一种新的计算方法被研究者发现出来,它就是 FFT。FFT 并不是一种新的获取频域特征的方式,而是离散傅里叶变换的一种快速实现算法。 数字信号处理在当今科技发展中发展很迅速,不但是在传统的通信领域,其 他方面也经常用到。利用快速傅里叶变换,实现了信号频域的变换处理。对于信 号的处理,往往会和数学中的算法联系到一起。如果处理得当,将会对气象,地 理信息等的发展,起到举足轻重的作用,同时对世界其他领域的发展有很大的促 进作用。 关键词: FFT 算法,C 语言,编译实现

I

河南城建学院本科毕业设计(论文)

Abstract

Abstract
Discrete Fourier Transform (DFT) is often used to calculate the signal processing to obtain frequency domain signals. DFT algorithm can get the frequency domain characteristics of the signal, because the algorithm is computationally intensive, long-time use, the computer is not conducive to real-time signal processing. So DFT since it was discovered in a relatively long period of time is not to be applied to the actual projects until a new fast discrete Fourier calculation method --FFT is found in discrete Fourier transform was able to actually project has been widely used. FFT is not a new way to get the frequency domain, but the discrete Fourier transform of a fast algorithm. Fast Fourier Transform (FFT) is a digital signal processing important tool that the time domain signal into a frequency-domain signal processing. matched filtering has important applications. FFT is a discrete Fourier transform (DFT) is a fast algorithm, it can be a signal from the time domain to the frequency domain. Some signals in the time domain is not easy to observe the characteristics of what is, but then if you change the signal from the time domain to the frequency domain, it is easy to see out of. This design is required to be familiar with the basic principles of FFT algorithm, based on the preparation of C language program to achieve FFT algorithm real number sequence. Keywords: FFT algorithm, C language compiler to achieve

II

河南城建学院本科毕业设计(论文)

Abstract

目 录
摘 要 ................................................................................................................................. I Abstract ............................................................................................................................. II 目 录 .............................................................................................................................III 1 引言 ...............................................................................................................................4 1.1 课题背景 ............................................................................................................4 1.2 FFT 算法的现状 .................................................................................................4 1.3 研究内容 ...........................................................................................................2 1.4 论文的研究成果 ...............................................................................................2 2 数字信号处理综述 .......................................................................................................3 2.1 数字信号理论 ...................................................................................................3 2.2 数字信号处理的实现 .......................................................................................4 2.3 数字信号处理的应用及特点 ...........................................................................4 3 基本理论 .......................................................................................................................6 3.1 FFT 算法的基本概念 .........................................................................................6 3.1.1 离散傅里叶变换(DFT) .......................................................................6 3.1.2 快速傅里叶变换(FFT) ......................................................................7 3.2 FFT 算法的分类 ..............................................................................................8 3.2.1 按时间抽取(DIT)的 FTT ...................................................................8 3.2.2 按频率抽取(DIF)的 FTT ................................................................12 3.2.3 快速傅里叶分裂基 FFT 算法 .............................................................15 3.2.4 N 为组合数的 FFT——混合基算法 ....................................................18 3.3 傅里叶变换的应用 ..........................................................................................20 4 基-2FFT 算法的 C 语言实现及仿真 ........................................ 错误!未定义书签。 4.1 码位倒序 ..........................................................................................................21 4.2 蝶形运算 ..........................................................................................................23 结论 .................................................................................................................................24 参考文献 .........................................................................................................................25 附录 A .............................................................................................................................26 附录 B .............................................................................................................................36 致谢 .................................................................................................................................44

III

河南城建学院本科毕业设计(论文)

目录

1 引言
1.1 课题背景
离散傅里叶变换(DFT)可以将有限长序列的的频域也离散化成有现长序列, 但是计算量很大,不利于应用于实际工程。直到 1965 年 J.W.库利和 T.W.图基提出 了一种快速计算离散复傅里叶的计算方法,DFT 的计算量减少了几个数量级,特 别是被变换的抽样点数 N 越多,FFT 算法计算量的就越少。 快速傅立叶变换作为一种数学计算方法,已经被广泛地运用在几乎所有领域 的频谱分析中,而且长久不衰,因为信号处理方法不分先进和落后之说。只有经 典的和现代的之别,在实际系统中用得最好的方法就是实用的方法。换句话说信 号处理方法与应用背景和目的的近程度是衡量信号处理方法优劣的唯一标准。快 速傅里叶变换(FFT),它在当今的科技世界表现的很是活跃。无论是在信号分析 中,还是应用在高科技领域中的不断发展研究中都占有很重要的位置。

1.2 FFT 算法的现状
在过去的几十年里,数字信号处理技术,数字计算机,LSI 等先进技术发展一 直较快,日新月异,已成为科学技术里面具有强大的生命力。由于它本身具有许 多优点,它可以有效地推动技术创新和各种工程学科的发展,在应用领域更加广 泛,深入,越来越多的人们关注这一领域。 在数字信号处理里,离散傅立叶变换(DFT)是一种常见的变换方法,它在各 种各样的数字信号处理系统中占有很重要的位置。快速傅立叶变换(FFT)与离散 傅里叶变换(DFT)不是两种不同的计算方法,FFT 只是为了更快捷有效的计算离 散傅里叶变换。 傅立叶变换已经出现了一个多世纪,众所周知,信号的频域分析往往比时域 分析更好,它不仅简单,易于分析较为复杂的信号。但有一个更准确的数值计算 方法, 就是利用离散傅里叶变换进行信号的频谱分析, 但是由于 DFT 的计算量大, 耗费更多的时间,此法没有很好地得到应用。直到二十世纪六十年代中期,一种 更为便捷的算法出现即 FFT,数字信号处理这门技术才得以快速的发展。 IV

河南城建学院本科毕业设计(论文)

1 引言

应当注意的是,在二十世纪六十年代中后期的时候 FFT 在电子计算机的帮助 下已经提出了,此时 FFT 的硬件电路部分也已可以制作了。在这个时候 DFT 运算 较之以前减少了很多,计算的时间较之以前也大大减少。因此,FFT 算法大量运 用到各种学科和技术领域,信号处理技术在近半个世纪的时间里得到了很好地发 展,变为数字信号处理这门学科在应用领域中功能强大的工具,广泛应用于各种 领域里。

1.3 研究内容
研究 FFT 算法,掌握其原理,针对目前 FFT 算法的广泛使用,本文提出了 (1)设计出一个 FFT 算法的实验项目,用 C 语言来编译实现。 (2)为了验证该程序的准确性,用 C 语言仿真。

1.4 论文的研究成果
通过查阅图书等更深入的了解 FFT 算法,熟悉 FFT 算法的的基本原理, 掌握 FFT 算法及应用,培养 C 语言编程能力,用 C 语言完成基 2-FFT 算法的 C 语言实现,最后使用 C 语言实现软件仿真。 本次设计的程序又较强的适应性,对于有相关需求的相关,可以快速扩 展。

2

河南城建学院本科毕业设计(论文)

1 引言

2 数字信号处理综述
2.1 数字信号理论
数字信号的处理,在理论上所涉及的范围非常广泛。在数学领域中 ,不但 在微积分、概率统计、随机过程,还在高等代数、数值分析和复变函数等等,都 是它基本的工具,网络理论和信号以及系统等,均都是它的理论基础。在学科的 发展上,数字信号处理不但和最优控制、通信理论以及故障诊断等紧密相连,近 年来又成为了人工智能、模式识别以及神经网络等新兴的学科理论基础之一,其 算法的实现不但和计算机学科紧密相连,而且与微电子技术密不可分。故可以说, 数字信号处理是将经典的理论体系(如数学、系统)当作自己的理论基础。 一般把二十世纪六十年代中期快速傅里叶(FFT)的出现,作为数字信号处理 这门新学科的开端。在这几十年的发展中,数字信号处理这门学科本身已经基本 形成了比较完整的理论体系。这些理论包括: (1)信号采集; (2)离散信号分析; (3)离散系统分析; (4)信号处理中的快速计算; (5)信号的估值; (6)滤波技术; (7)信号的建模; (8)信号处理中的特殊算法; (9)信号处理技术的实现; (10)信号处理技术的运用。 上述 10 个方面可以看出有着千丝万缕的联系。把信号处理技术应用到实际工 程项目中,并需要结合相应的算法来实现。 随着科学技术的飞速发展,数字信号处理理的论不断丰富和完善各种新的算 法,新理论不断被提出,在未来,数字信号处理的理论,会获得更快速发展。 3

河南城建学院本科毕业设计(论文)

2 数字信号处理综述

2.2 数字信号处理的实现
数字信号处理的实现,大体上有如下几种方法: (1)在计算机上用使用者自己编写,或者使用现成的软件来实现。这种实现 的方法多用于教学与科研,但是速度较慢。 (2)用微控制器来实施。微控制器发展迅速,它的功能也非常强大。依靠微 控制器的硬件环境与信号处理的软件可以在工程实践中使用,诸如数字控制,医 疗设备。 (3)使用专门的 DSP 芯片进行信号处理来实现。 DSP 芯片比微控制器有一 个更突出的优点,例如内部有乘法累加器,其工作方式采用并行结构,多总线, 速度快,以适于指示信号处理等。信号处理技术应用于工程实际成为可能是由于 DSP 芯片的问世及飞速发展。 (4)采用专用的 DSP 芯片。现在国际社会已推出的专门的 DSP 芯片进行卷 积、FFT、FIR 滤波、相关和其它专用的芯片,在芯片的硬件电路中实现软件算法, 用户给定输出数据,其结果,可直接在输出端获得。

2.3 数字信号处理的应用及特点
数字信号处理技术有着非常广泛的应用领域。在声呐、雷达、地球物理、广 播电视、消费电子、军事等众多领域都活的了极其广泛的应用,它有效地促进了 众多领域的迅速发展。 数字信号处理具有以下优点: (1)高可靠性、高精度性和高稳定性 在传输和处理过程中,数字信号用二进制数 0 和 1 的码字序列表示,而 0 和 1 又是用脉冲的有无或脉冲的正负表示,即使在有噪声干扰存在的情况下,只要能 够判别出脉冲的有无和正负,就能够准确传输和处理 0 和 1 表示的数字序列,因 此,这种表示几乎不受噪声和干扰的影响。 (2)时分复用 在数字信号相邻取样值之间,存在着比较长的空闲时间。在这个期间内,可 以利用同一个数字信号处理设备来处理其他通道的信号,这就是所谓的时分复用 的过程。 (3)灵活、方便、易于集成 在数字信号处理中,无论视频信号、图像信号和声音信号,还是其他任何信

4

河南城建学院本科毕业设计(论文)

2 数字信号处理综述

号,都统一由二进制数 0 和 1 表示成数字序列,数字序列可以很方便的进行保存、 复制、剪裁、融合、加密、传输和处理。数字信号处理归结为对数字序列进行一 序列运算,这些运算够成了各种数字信号处理算法。将数字信号处理算法编写成 程序,可以在计算机上运行。 (4)其他的独特优点 数字信号处理还具有模拟信号处理完全不可能有的其他一些独特的优点。例 如,利用数字滤波器组可以实现多速率信号处理;数字系统的级联不需要考虑负 载匹配问题;能够处理如地震信号那样的非常低频率的信号,如果采用模拟信号 处理,模拟元件的尺寸将大到无法容忍的地步。

5

河南城建学院本科毕业设计(论文)

2 数字信号处理综述

3 基本理论
3.1 FFT 算法的基本概念
离散傅立叶变换(DFT)是信号分析与处理中的一种重要的变换。DFT 的计 算,需要作 N 2 次复数乘法运算和 N(N ? 1) 次复数加法运算,当 N 比较大时,计 算量就非常大,为了快速计算 DFT,近几十年以来,科学工作者们对离散傅立叶 变换的计算进行了大量的研究,提出了很多有效的快速计算 DFT 的方法。这些算 法,称之为快速傅立叶变换(FFT)。快速傅立叶变换并不是不同于离散傅立叶变 换的另一个变换,而是减少了 DFT 计算次数的一种快速的算法。其突出的优点是 可以快速,更精确的,高效地完成 DFT 的计算。

3.1.1 离散傅里叶变换(DFT)
随着科技发展的日新月异,人们对开发和应用频率分析技术充满了希望。先 前进行一次频率分析,既费时又费力。今天,随着电脑的硬件设备工艺提升了很 多,计算机的性能也不断提升,因此计算机的计算速度才变得越来越快。由于计 算机不可以对连续的信号进处理,它只能处理一个有限的离散数据。为了便于使 用计算机对傅立叶积分变换,计算机需要对连续信号进行采样和分析,从而产生 一系列离散的数据。这个离散傅里叶变换,称为离散傅立叶变换,简称 DFT。 DFT 的定义: 设 x(n) 是一个长度为 N 的有限长序列, 定义 x(n) 的 N 点离散傅立叶变换为
2? nk N

X (k ) ? DFT [ x(n)] ? ? x(n)e
n ?0

N ?1

?j

nk ? ? x(n)WN n ?0

N ?1

式 (3.1)

其中 k=0,1,…,N-1 X (k) 的傅立叶反变换为

6

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

x(n) ? IDFT [ X (k )] ?
其中 n= 0,1,…,N-1

2? N ?1 j nk 1 N ?1 ? nk N X ( k ) e ? x(k )WN ? ? N k ?0 k ?0

式(3.2)

在(式 3.1)式和(式 3.2)式中, x(n) 和 X(k)均可以是复数。因为在(式 3.1)式和 (式 3.2)式的右边仅在 WN 指数上差一个符号,并相差一个比例因子 (式 3.1)式计算步骤的讨论稍加修改可以直接用于(式 3.2)式。
1 N

,所以有关

3.1.2 快速傅里叶变换(FFT)
二十世纪六十年代中期,Cooley 和 Tukey 两人经过研究,提出了一种可以快 速算出 DFT 的算法,那就是 FFT。从此以后,在计算机上 DFT 的计算时间减少了很 多。在随后的几十年中,研究员们经过更透彻的对 FFT 的研究,DSP 这门学科才得 以快速发展。由于不同的有限长序列选择的分解方法不同,因此就出现了一些不 同的 FFT 算法,其基本算法是 2DIT 和基 2DIF。快速傅里叶变换(FFT)是计算离 散傅里叶变换(DFT)的快速算法。 DFT 的定义式为
kn X ( k ) = ? x(n)WN RN ( k ) n ?0 N ?1

式(3.3)

在所有复指数值 W 的值全部已算好的情况下,要计算一个 X ( k ) 需要 N 次复 数乘法和 N -1 次复数加法。 要算出所有 N 点 X ( k ) 共需 N 2 次复数乘法和 N( N ? 1) 次 复数加法。即其计算量是与 N 2 成正比的。 旋转因子 W N 具有如下两个特性,可以使 DFT 运算量尽可能分解为多个小点 数的 DFT 运算:
(k ? N )n kn ( n? N ) k (1)周期性: WN ? WN ? WN

kn N

( k ? N / 2) k (2)对称性: WN ? ?WN

利用旋转因子 W N 这两个性质,可以使 DFT 运算中的某些项合并,以便减少 乘法的次数。例子:求当 N=4 时,X(2)的值
X (2) ? ? x(n)W42 n ? x(0)W40 ? x(1)W42 ? x(2)W44 ? x(3)W46
n ?0 3

? [ x(0) ? x(2)]W40 ? [ x(1) ? x(3)]W42 =[ x(0) ? x(2)]-[ x(1) ? x(3)]W
0 4

(周期性)

(对称性)

通过合并,使乘法次数由原来的 4 次减少到现在的 1 次,因此运算量减少了。 FFT 算法有许多种表示形式,但从基本上可以分为两大类:一种是按时间抽 取(DIT),另一种是按频率抽取(DIF)。 7

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

3.2 FFT 算法的分类
DFT 从基本上可以分为两类分解方法:一类是把时间序列 x(n) 进行连续的分 解,于是得到的 FFT 算法可以称之为按时间抽取的算法,另一类是把傅立叶变换 序列 X(k) (k 为频率基准)进行连续的分解 ,叫做按频率抽取的算法。对于每一种 算法,根据基本的蝶形运算的构成,又可把 FFT 算法分为基 2、基 4、基 8 以及 任意因子等的 FFT 算法,FFT 算法对于不同基所需要的计算量是有所不同的,之 所以说有差异是指的是并没有数量级的差别。表 3.1 列出了 N=4096 时各种基的 FFT 算法所需运算量次数的的比较。
表 3.1 算法运算量的比较

算法 基2 基4 基8 基 16

实数乘法次数 81 924 57 348 49 156 48 132

实数加法次数 139 266 126 978 126 978 125 422

从上述表格可以看出,计算的时候基数和计算总量成反比。从计算量这一个 角度进行判断显然是片面的,在计算中基数越高的算法越好。判断一个算法不仅 需要从计算量本身而且还需从算法的复杂程度方面来加以分析。往往算法的复杂 性伴随着计算中高基数而变化。所以,在选择算法分析的时候要视情况而定。

3.2.1 按时间抽取(DIT)的 FTT
基 2FFT 变换主要就是为了解决大数拆分成小点数 DFT 运算这个问题的,这 时需要取 N ? 2 M (M 为正整数、N 为复合数)。对该算法讨论如下。 视奇偶项把 x(n)一分为二

? x(2r ) ? x1 (r ) ? ? x(2r ? 1) ? x2 (r )
将 DFT 运算也相应分为两组
X (k ) ? DFT[ x(n)] ?

r ? 0,1,?,

N ?1 2

? x(n)W
n ?0

N ?1

kn N

8

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

?

n ?0 n为偶数
N / 2?1 r ?0

? x(n)WNkn+

N ?1

n ?0 n 为奇数

? x(n)W
N / 2?1 r ?0

N ?1

kn N

2 rk = ? x(2r )WN ?

? x(2r ? 1)W
k N N / 2 ?1 r ?0

( 2 r ?1) k N

= ? x1 (r )W
r ?0
N / 2 ?1 r ?0

N / 2 ?1

2 rk N

?W

?x
2

2

2 rk (r )WN

rk k = ? x1 (r )WN / 2 ? WN

N / 2 ?1 r ?0

? x (r )W

rk N /2

2 rk rk (因为 WN ? WN /2 )

k ? X 1 (k ) ? WN X 2 (k )

其中 X 1 ( k ) 、 X 2 ( k ) 分别是 x1 (n)、x2 (n) 的 N/2 点的 DFT
rk X 1 ( k ) = ? x1 (r )WN /2 ? r ?0 N / 2 ?1 N / 2?1 r ?0

? x(2r )W
rk N /2

rk N /2

,0 ? k ?

N ?1 2

式(3.4)

rk X 2 ( k ) = ? x2 (r )WN /2 ? r ?0

N / 2 ?1

N / 2?1 r ?0

? x(2r ? 1)W

,0 ? k ?

N ?1 2

式 (3.5)

至此,一个 N 点 DFT 被分解为两个 N/2 点的 DFT。 上面能将全部 N 点的 X ( k ) 求解出来。
k X ( k ) ? X 1 (k ) ? WN X 1 ( k ) 和 X 2 (k ) 只有 N/2 个点 分析: ( k ? 0,1,?, N 2 -1 ) , X 2 (k )

只能求出 X ( k ) 的前 N/2 个点的 DFT,要求出全部 N 点的 X ( k ) ,需要找出 X 1 ( k ) 、
X 2 ( k ) 和 X (k ? N / 2) 的关系,其中 k ? 0,1,?, N 2 ? 1 。
k 是由式子 X ( k ) ? X 1 (k ) ? WN X 2 (k ) 可得

k?N / 2 X (k ? N / 2) ? X 1 (k ? N / 2) ? WN X 2 (k ? N / 2)

式(3.6)

化简得
k X (k ? N / 2) = ? X 1 (k ) ? WN X 2 (k ) , k ? 0,1,?,

N ?1 2

这样 N 点 DFT 可全部由下式确定出来:
k ? ? X (k ) ? X 1 (k ) ? W N X 2 (k ) ? k ? ? X (k ? N / 2) ? X 1 (k ) ? W N X 2 (k )

k ? 0,1,?,

N ?1 2

上式可用一个专用的碟形符号来表示,这个符号对应一次复数乘法和两次复 数加法运算 9

河南城建学院本科毕业设计(论文)
a
k a ? WN b

4 基-2FFT 算法的 C 语言实现及仿真

b

W

k N

-1

k a ? WN b

图 3.1 蝶形运算符号

DFT 通过这样的分解以后,每一个 N 2 点的 DFT 只需要 ( N 2 ) 2 ? N 4 次复数乘法
2

两个 N/2 点的 DFT 需要 2( N 2 ) 2 ? N 2 次复乘, 再加上将两个 N 2 点 DFT 合并成为 N
2 2

点 DFT 时有 N 2 次与 W 因子相乘,一共需要 N 2 ? N 2 ? N
2

2

2

次复乘。可见,通过这样

的分解,计算量就会减少很多。 因为 N ? 2 M ,且 N/2 仍然是偶数,因此就可以对两个 N/2 点的 DFT 再次分别 作进一步的分解,于是将两个 N/2 点的 DFT 分解成两个 N/4 点的 DFT。 例如对 x1 (r ) ,可以在按其偶数部分及奇数部分进行分解:

? x1 (2l ) ? x3 (l ) ? ? x1 (2l ? 1) ? x4 (l )
则的运算可相应分为两组:

l ? 0,1,?,

N ?1 4

2lk X 1 ( k ) = ? x1 (2l )WN /2 ? l ?0

N / 4 ?1

N / 4?1 l ?0

? x (2l ? 1)W
1 N / 4?1 l ?0

( 2l ?1) k N /2

lk k = ? x3 (l )WN / 4 ? WN / 2 l ?0

N / 4?1

?x

4

lk (l )WN /4

k ? X 3 (k ) ? WN / 2 X 4 (k )

k ? 0,1,?,

N ?1 4

式 (3.7)

k 2k 将系数统一为以N为周期,即 WN / 2 ? WN ,可得
2k ? ? X 1 (k ) ? X 3 (k ) ? W N X 4 (k ) ? 2k ? ? X 1 (k ? N / 4) ? X 3 (k ) ? W N X 4 (k )

k ? 0,1,?,

N ?1 4

相同的, X 2 ( k ) 分解类似。经过分解后,DFT 就只有 2 点,下图的蝶形符号 表示其运算。依据时间抽取的分解 N ? 23 ? 8 的过程,下图是其完整的流程图:

10

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

图 3.2 8 点的 DFT 分解

图 3.3 按时间抽取将一个 N 点的 DFT 分解为两个 4 点的 DFT

图 3.4 一个 N=8 点 DFT 分解为 4 个 2 点的 DFT

图 3.5 N=8 按时间抽取的 FFT 运算信号流图

“时间抽取法”就是在每一次分解时,其步骤是按有限长序列顺序在时域上的 奇偶进行抽取。 根据上面流图的分析, N ? 2 M ,总共需要进行 M 次分解,于是构成了从 x(n) 至 X(k)的 M 级运算过程。每一级的计算都是由 N/2 个蝶形运算构成的,因此每一 级计算都需要 N/2 次复数乘法和 N 次复数加法,因此按时间抽取的 M 级运算后总 共需要 复数乘法次数: m F ?
N N ? M ? log 2 N 2 2

11

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

复数加法次数: aF ? N ? M ? N log2 N 根据上面的运算流图,需要对 FFT 算法的两个特点来进行分析,这两个特点 对 FFT 的软硬件造成的影响很大。 (1)原位运算 也叫做同址运算,计算过程中每一级蝶形的输入与输出在运算前后都可以存 储在同一个地址上,直到最后输出,中间没有任何其它的存储器。根据运算流图 分析原位运算是如何进行的。原位运算的这种结构可以为硬件节省存储单元,从 而降低对计算机存储量的要求,同时也可以大大的降低硬件设备成本。 (2)变址 分析运算流图中的输入和输出序列的顺序,输出是按顺序,而输入是“码位 倒置”的顺序。如下图所示:
表 3.2 码位倒置顺序

码位倒置顺 自然顺序 0 1 2 3 4 5 6 7 二进制表示 000 001 010 011 100 101 110 111 码位倒置 序 000 100 010 110 001 101 011 111 0 4 2 6 1 5 3 7

为了解决计算过程中输入数据由码位倒置的顺序排好再次输入的不便,这里 借助于存储单元这个中间桥梁来实现,避免了数据发生冲突的可能。上图就是变 址的功能。码位倒置顺序在软件上利用雷德算法进行运算。高要求应用实现变址 必须保证具有恰当的电路。

3.2.2 按频率抽取(DIF)的 FTT
12

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

频率抽取法遵循两个规则:一是把频率进行偶、奇分组,二是把时间前后分 为两部分:
X (k ) ? DFT[ x(n)] ?
( N / 2 ) ?1 n ?0

? x(n)W
n ?0

N ?1

kn N

?

? x(n)WNkn+ ? x(n)WNkn
n? N / 2
nk N

N ?1

= ? x(n)W
n ?0 N / 2 ?1 n ?0

N / 2 ?1

?

N / 2?1 n ?0

? x(n ? N / 2)W

( n ? N / 2) k N

( N / 2) k nk = ? [ x ( n) ? W N x(n ? N / 2)] WN

式 (3.8)

N/2 ( N / 2) k 因为 WN ? ?1,WN ? (?1) k ,k 为偶数时 (?1) k ? 1,k 为奇数时 (?1) k ? ?1 ,

因此可以把 X(k)分为两组,分别为偶数组和奇数组:
nk X (k )= ?[ x(n) ? (?1) k x(n ? N / 2)] WN n ?0 N / 2 ?1

式(3.9)

2 nr X (2r )= ? [ x(n) ? x(n ? N / 2)] WN n ?0

N / 2 ?1

?

N / 2 ?1 n ?0

?[ x(n) ? x(n ? N / 2)]W
N / 2 ?1 n ?0

式 (3.10)
nr N /2

( 2 r ?1) n X (2r ? 1)= ? [ x(n) ? x(n ? N / 2)] WN

?

N / 2 ?1 n ?0

?[ x(n) ? x(n ? N / 2)]W

式 (3.11)
n N

W

nr N /2

? x1 (n) ? x(n) ? x(n ? N / 2) 令? n ? x 2 (n) ? [ x(n) ? x(n ? N / 2)]W N

n ? 0,1,?, N / 2 ? 1

这两个序列都是 N/2 点的序列,下面是一半的 DFT 计算:
nr X (2r )= ? x1 (n)] WN /2 n ?0 N / 2 ?1

rn X (2r ? 1)= ? x2 (n)WN /2 n ?0

N / 2 ?1

这样,同样是将一个 N 点的 DFT 分解为两个 N/2 点的 DFT 了。频率抽选法对应 13

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

的碟形运算关系图如下:
a

a?b
n (a ? b)WN

b -1

W

n N

对于 N=8 时频率抽取法的 FFT 流图如下:

图 3.6 8 点的 DFT 分解

图 3.7 按频率抽取的第一次分解

图 3.8 按频率抽取的第二次分解

14

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

图 3.9 按频率抽取的 FFT(N=8)运算信号流图

每一个操作是根据该输出序列 X (k) 的顺序在频域是属于奇数或偶数来分组, 这种方法被称为频率抽取分组方法。常见的问题是:使用快速算法 IDFT。 分析 IDFT 的公式:

x(n) ? IDFT[ X (k )] ?
比较 DFT 的公式:

1 N ?1 ? nk X (k )WN , n ? 0,1,?, N ? 1 ? N k ?0

式 (3.12)

nk X (k ) ? DFT[ x(n)] ? ? x(n)WN , k ? 0,1,?, N ? 1 n ?0

N ?1

式(3.13)

3.2.3 快速傅里叶分裂基 FFT 算法
自从基-2FFT 算法出现以来,人们仍在研究追寻更快的算法。从理论上讲,用 较大的基数还可以进一步减少计算的次数,但是要以程序或硬件复杂为代价,所 以取大于 8 的基数没有多大实际意义。1984 年,法国的研究员们提出了一种把基 2FFT 和基 4FFT 连接在一起的算法叫做分裂基算法。基运算量比基 2 少,运算流 图和和基 2-FFT 接近,运算程序也不长,也是一种高效实用算法。 由于出现的基础-2FFT 算法,人们仍在寻找更快的算法。从理论上讲,具有较 大的碱可以进一步减少操作的数量,但在该程序或硬件复杂度为代价,它需要不 大于实际意义的基础部 8 大得多。 用分裂基算法计算 N ? 2 M 点的 DFT,基本方法与频选 FFT 类比相似,是建立 在把 X(k)分解成越来越多的小点数的子序列基础上,每次都是均等分解。 二十世纪八十年代中期研究出来的算法——分裂基算法,这种算法把基 2 和 基 4 算法结合在一起,是对于解决 N=2L 各类算法中最好的一个。 当 n=p*q,且 p=N/4,q=4时,n 可表示为

15

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

n ? pn1 ? n0 ?

N n1 ? n0 , 4

0 ? n1 ? 3, 0 ? n0 ?

N ?1 4

并有
kn X (k ) ? ? x(n)WN n ?0 N ?1

?

N /4?1 3

??
n ?0 n1 ?0
N /4?1

x(

N k ( n1 ? n0 ) N n1 ? n0 )WN 4 4

?

?
n0

kn0 WN ? x( n1

3

N n1 ? n0 )W4kn1 ] 4 N k N )W4 ? x(n0 ? )W42 k 4 2
式(3.14)

?

N/ 4 ? 1 n0 ?0

?

[ x(n)W40 ? x(n0 ?

? x(n0 ?

3N 3k 3k kn0 )W4 WN ]WN 4

再将上式中的 k 表示为 N k ? 4k1 ? k0 , 0 ? k1 ? ? 1, 0 ? k0 ? 3 4 可得

X (k ) ? X (4k1 ? k0 ) ?
N /4 ?1 n0 ? 0

?

[ x(n0 ) ? x(n0 ?

N (4 k1 ? k0 ) )W4 4

? x(n0 ? ?
N /4 ?1 n0 ? 0

?

N 81 ? 2 k0 3N 3(4 k1 ? k0 ) (4 k1 ? k0 ) n0 )W4 ? x(n0 ? )W4 ]WN 2 4 N N [ x(n0 ) ? x((n0 ? )W4k0 ? x(n0 ? )W42 k0 4 2 3N 3k0 (4 k1 ? k0 ) n0 )W4 ]WN 4

? x(n0 ?

对 k 0 =0,1,2,3,并用 k 表示 k1 ,用 n 表示 n 0 ,可以写出

16

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

N /2 ?1 N N ? X (2 k ) ? [ x(n) ? x(n ? )]WN2 kn , 0 ? k ? ? 1 ? ? 2 2 n ?0 ? N /4 ?1 ? ? N N 3N ? 4 kn )]WNn ?WN ? X (4k ? 1) ? ? ?[ x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? 4 2 4 ? n ?0 ? ? ? N ? 0 ? k ? ?1 ? 4 ? N /4 ? 1 ? ? N N 3N 3n ? 4 kn )]WN ?WN ? X (4k ? 3) ? ? ?[ x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? 4 2 4 ? n?0 ? ? ? N 0 ? k ? ?1 ? 4 ? ?

N /2 ?1 N N ? X (2 k ) ? [ x(n) ? x(n ? )]WN2 kn , 0 ? k ? ? 1 ? ? 2 2 n ?0 ? N /4 ? 1 ? ? N N 3N ? 4 kn )]WNn ?WN ? X (4k ? 1) ? ? ?[ x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? 4 2 4 ? n ?0 ? ? ? N ? 0 ? k ? ?1 ? 4 ? N /4 ? 1 ? ? N N 3N 3n ? 4 kn )]WN ?WN ? X (4k ? 3) ? ? ?[ x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? 4 2 4 ? n?0 ? ? ? N 0 ? k ? ?1 ? 4 ? ? N N ? 0 ? n ? ?1 ? x2 (n) ? x(n) ? x(n ? 2 ), 2 ? N N ? x1 (n) ? [ x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? 3N )]W n N ? 4 4 2 4 ? ? x 2 (n) ? [ x(n) ? jx(n ? N ) ? x(n ? N ) ? jx(n ? 3N )]W 3n N ? 4 4 2 4 ? N ? 0 ? n ? ?1 ? 4

则上式可写成如下更简明的形式
N /2 ?1 N ? X (2 k ) ? x2 (n)WN2 kn ? DFT [ x2 (n)], 0 ? k ? ? 1 ? ? 2 n ?0 ? N /4 ?1 ? N 1 4 kn 1 ? X (4k ? 1) ? ? x4 (n)WN ? DFT [ x4 (n)], 0 ? k ? ? 1 4 n ?0 ? N /4 ? 1 ? N 2 4 kn 2 ? X (4k ? 3) ? ? x4 (n)WN ? DFT [ x4 (n)], 0 ? k ? ? 1 4 n ?0 ?

17

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

3.2.4 N 为组合数的 FFT——混合基算法
以 2 的基数的 FFT 算法,即 N ? 2 M ,由于此计算方法具有程序简单,计算效 率高、对存储要求不是很高等特点,其在实际工程中得到了大范围的使用。在实 际应用中,人们决定了有限长序列的长度 N,因此多数场合可取 N ? 2 M ,因此可 以直接使用 FFT 的算法是以 2 的基数为准。 假设 N 不能人为确定的,N 的数值也不等于 2 的幂 2M ,通常有下列两种处理 方法: (1)补零:将 x(n) 补零,使得 N ? 2 M 。例如 N=60,可在序列 x(n) 的末尾 填补上 4 个 0,即另 x(60) ? x(61) ? x(62) ? x(63) ? 0 ,使 N 达到 2 6 ? 64 ,这样就可 以使用基 2FFT 算法。有限长序列在补零以后,只是频谱的采样点有所变化而不会 影响它的频谱 X(e jw) 的形状。 (2) 如果要求准确度高的 N 点 DFT 值,也可采用任意数作为基数的 FFT 算法 , 其计算的速度远低于以2为基数 FFT 算法。 如 N 为复合数,设 N 等于两个整数 p 与 q 的乘积,即 N=p.q 如前面所述的以2 为基数时一样,FFT 的计算就是把 DFT 的运算尽可能分小,于是,在 N=p.q 的情况下, 则可将 N 点的 DFT 分解为 p 个 q 点 DFT 或 q 个 p 点 DFT 来计算,以便减少计算量。 其步骤如下:

?n ? n1Q ? n0 ? ?k ? k1P ? k0
n0 , k1 ,分别为0, 1,…,Q-1, n1 , k0 ,分别为0, 1,…,P-1

N 点 DFT 可以重新写成为

X (k ) ? X (k1P ? k0 ) ? X ? k1 , k0 ?
kn ? ? x(n)WN n ?0 N ?1

( k1P ? k0 )( n1Q ? n0 ) ? ? ? x ? n1Q ? n0 ?WN n0 ?0 n1 ?0

Q ?1 P ?1

式(3.15)

X ? k1 , k0 ? ? ?

n0 ? 0 n1 ? 0 Q ?1 P ?1

? ? x ? n , n ?W
1 0 1 0

Q ?1 P ?1

k1n1PQ N

k0 n1Q k1n0 P k0 n0 WN WN WN

n0 ? 0 n1 ? 0

? ? x ? n , n ?W

k0 n1Q N

k1n0 P k1n0 WN WN

18

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真
k0 n1Q N

考虑到

W
Q ?1

?W

k0 n1 P

X ? k1 , k0 ? ?

? P ?1 ? kn ? k n k n ? ?[ ? x ? n1 , n0 ?WP 0 1 ]WN 0 0 ?WQ 1 0 ? n0 ? 0 ? ? n1 ?0 ? ?
P ?1

kn 令 X1 ? k0 , n0 ? ? ? x ? n1 , n0 ?WP 0 1 n1 ?0
Q ?1

X ? k1 , k0 ? ?

n0 ?0

? [X ? k , n ? ? W
1 0 0

k0 n0 N

k1n0 ]WQ

再令

X1? ? k0 , n0 ? ? X1 ? k0 , n0 ? ?WNk0n0
X ? k1 , k0 ? ?
n0 ?0

? X ? ? k , n ? ?W
1 0 0

Q ?1

k1n0 Q

以 P=3,Q=4,N=12为例 (1) 先将 x(n) 通过 x(n1 ? n0 ) 改写成 x(n1 , n0 ) 。 因为 Q=4, n1 ? 0,1,2, n0 ? 0,1,2,3,
x(0,0) ? x(0), x(0,1) ? x(1), x(0,2) ? x(2), x(0,3) ? x(3)
x(1,0) ? x(4), x(1,1) ? x(5), x(1,2) ? x(6), x(1,3) ? x(7) x(2,0) ? x(8), x(2,1) ? x(9), x(2,2) ? x(10), x(2,3) ? x(11)

(2)求 Q 个 P 点的 DFT

X1 (k 0, n0 ) ? ? x(n1 , n0 )W3k0n1
n1 ?0

2

(3) X1 (k0 , n0 ) 乘以得到 X1' (k0 , n0 ) 。 (4)求 P 个 Q 点的 DFT,参变量是 k 0
3

X 2 ? k0 , k1 ? ? ? X1' ? k0 , n0 ?W4k1n0
n0 ?0

(5) 将 x2 (k0 , k1 ) 通过 X (k0 ? k1P) 恢复为 X ( k ) (1)求 Q 个 P 点 DFT 需要 QP2次复数乘法和 Q· P· (P-1)次复数加法; (2)乘 N 个 W 因子需要 N 次复数乘法; (3)求 P 个 Q 点 DFT 需要 PQ2 次复数乘法和 P· Q(Q-1)次复数加法。 总的复数乘法量:QP2+N+PQ2=N(P+Q+1); 总的复数加法量:QP(P-1)+PQ(Q-1)=N(P+Q-2); 上述分解原则可推广至任意基数的更加复杂的情况。 例如,如果 N 可分解为 m 个质数因子 p1 , p2 ,?, pm 即 19

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

N ? p1 , p2 ,? pm

则 第一步:可把先把 N 分解成两个因子, N ? p1q1 ,其中 q1 ? p2 p3 ? pm ,并用 上述讨论的方法将 DFT 分解为 p1 个 q1 点 DFT; 第二步:将 q1 分解为 q1 ? p2 q2 ,q2 ? p3q4 ? pm 然后将每个 q1 点 DFT,之后再分 解为 p 2 个 q 2 点 DFT; 因为要获得最高的运算效率,要经过 m 次分解,直到分解到最小点数的 DFT 运算。 但计算效率的提高是要以编程的复杂性为代价的,一般较少应用。

p1 ? p2 ? ? ? pm ? 2 为基2FFT 算法。
当组合数 N ? P 就是基4FFT 算法 , 以 N ? 43 为 1P 2P 3 ?P m 中所有的 Pi 均为4时, 例,第一级运算的一般形式为:
X1 (k0 , n1 , n0 ) ? ? x(n2 , n1 , n0 )W4n2k0 ,
n2 ?0 3

0 ? k0 ? 3

? X 1 (0, n1 , n0 ) ? ?W40 W40 W40 W40 ? ? x(0, n1 , n0 ) ? ? X (1, n , n ) ? ? 0 ? 1 2 3?? ? 1 1 0 ? ? ?W4 W4 W4 W4 ? ? x(1, n1 , n0 ) ? ? X 1 (2, n1 , n0 ) ? ?W40 W42 W44 W46 ? ? x(2, n1 , n0 ) ? ? ? ? 0 ? 3 6 9?? ? X 1 (3, n1 , n0 ) ? ? ?W4 W4 W4 W4 ? ? ? x(3, n1 , n0 ) ? ?1 1 1 1 ? ? x(0, n1 , n2 ) ? ?1 ? j ?1 j ? ? x(1, n , n ) ? 1 2 ? ?? ?? ?1 ?1 1 ?1? ? x(2, n1 , n2 ) ? ? ? ?? ?1 j ?1 ? j ? ? x(3, n1 , n2 ) ?

3.3 傅里叶变换的应用
FFT 算法可以分析处理每一个可以使用傅里叶变换来进行分析、处理的领域, FFT 算法会对这些地方用数字计算处理然后利用软件实现其所表现出来的功能。 其表现形式为包括卷积分的积分,它是傅里叶变换实现近似处理的理论基础。 不仅在信号、通信里会用到它,还在需要仿真、分析一些系统,对语音功率谱的 估计时会用到。

20

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

4 基-2FFT 算法的 C 语言实现及仿真
对于 FFT 算法的 C 语言实现,要解决码位倒序和蝶形运算这两个问题。

4.1 码位倒序
首先需要解决的就是码位倒序的问题,只有这样在 FFT 的结果中才会按自然 顺序排列。 假设一个 N 点的输入序列,那么它的序号二进制数位数就是 t=log2N. 有两个问题是需要码位倒序解决:(1)把 t 位进行二进制数倒序;(2)然后 两个存储单元要在倒序后进行交换。 倒序流程图如下:

21

i<j? Y x(i)和 x(j)交换
河南城建学院本科毕业设计(论文) 4 基-2FFT 算法的 C 语言实现及仿真

k?N/2

k<j+1? N j?j+k

Y

j?j-k k?k/2

下面是码位倒序函数的程序代码: void Reverse(void) { unsigned int i,j,k; unsigned int t; complex temp;//临时交换变量 for(i=0;i<N;i++)//从第 0 个序号到第 N-1 个序号 { k=i;//当前第 i 个序号 j=0;//存储倒序后的序号,先初始化为 0 for(t=0;t<log2N;t++)//共移位 t 次,其中 log2N 是事先宏定义算好的 { j<<=1; j|=(k&1);//j 左移一位然后加上 k 的最低位 k>>=1;//k 右移一位,次低位变为最低位 } if(j>i)//如果倒序后大于原序数, 就将两个存储单元进行交换 (判断 j>i 是为了 防 止重复交换) { temp=x[i]; x[i]=x[j]; x[j]=temp; } 22

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

} }

4.2 蝶形运算
FFT 的 C 语言编程只需用 3 层循环即可实现,这是由 N 点的 FFT 从左到右共 有 log2N 级蝶形,每级有 N/2L 组,每组有 L 个,具体的三层是:完成整个 FFT 共 log2N 级每一级的蝶形运算的最外层循环, 完成每一组的蝶形运算 (每一级有 N/2L 组)的中间层循环,完成每一组有 L 个的单独 1 个蝶形运算的最内层循环。 第一层循环:运算的级数进行控制是第一层循环完成的,需要 m 级计算 N=2^m。 第二层循环: 根据乘数进行控制第二层循环, 这是由有 2^(L-1)个蝶形因子 (乘 数)第 L 级决定的。第三层循环里面的每一个蝶形因子都必须要执行一次,每一 级要进行 2^(L-1)次循环计算,第三层循环此时是在第二层循环控制下。 第三层循环:第三层循环在第二层循环确定某一乘数后要将本级中每个群中 具有这一乘数的蝶形计算一次,因为同一级内不同群的乘数分布相同,第 L 级共 有 N/2^L 即 2^ (n-L) 个群, 即第三层循环每执行完一次要进行 N/2^L 个碟形计算。 (执行不同 group 中具有相同 W 的蝶形运算) 可以得出结论:第三层循环在每一级中需要完成 N/2^L 个碟形计算;第三层 循环在第二层循环下进行 2^(L-1)次, 碟形计算在第二层循环完成时共进行 2^(L-1) *N/2^L=N/2 个。第 L 级的计算在第二、第三层循环得以完成。 实序列 256 点 FFT 运算的主程序代码基 2FFT 算法的 C 语言程序编制,是在 利用 C 语言软件调用上述 FFT 算法实现的,这是在设计要求下完成的。 在这里 x(n) 是一个有限长序列,共有 256 点,由于 N ? 256 ? 28 ,M=8,所以 总共有 8 级蝶形运算,每级有 N 2 ? 128个蝶形,共需要 1024 次复数乘法和 2048 次 复数加法。 用 C 语言实现 256 点实序列基 2FFT 的源程序见附录 A,仿真见附录 B。

23

河南城建学院本科毕业设计(论文)

4 基-2FFT 算法的 C 语言实现及仿真

结论
对于这次毕业设计,我做了很多准备。在确定了设计课题后,我立刻就去了 学校的图书馆,花了整整一下午时间,终于找齐了相关书籍,并借阅出去。然后 就又把之前学习的有关快速傅里叶变换的知识重新温习了一遍。另外又上网查阅 了各方面知识与资料。为后期设计打下基础。 通过了一段时间的学习,知道了 FFT 是离散傅里叶(DFT)的快速算法,它 利用旋转因子特性: 周期性和对称性两个性质, 先把 DFT 的尽可能多的连续分解, 使其变为许多个比较短序列的 DFT,计算较短序列的 DFT,再组合成原序列,从 而减少了运算量,使运算更加高效。 在一系列工作完成后,就开始论文方面的编写,这里对于每个学校而言,在 论文格式方面,都有着相当规范的格式要求。不仅仅在字体方面,格式方面,在 页面设置方面,还有标题,都有很多相关要求。对于这个工作,我特意在网上下 载了有关 WORD 的学习视频与教程,另外为了防止一些方面没有讲解到位,我又 从图书馆借阅了很多书籍。之后学习了将近一个星期,终于可以单独掌握了各个 编写技巧,格式的整理等等。在这个过程中,难免会有些地方遗漏和淡忘,身边 的同学和老师,给予了我很多帮助。在学校范文的参考下,顺利完成了论文写作。 最后总结一下这个设计过程,我意识到自己在这方面知识的欠缺。不仅仅在 专业知识方面,对于常用的 WORD 基本操作,都相当缺乏。另外对于自己的整体 意识,也有待提高。对于即将参加工作的我来说,真的有许多知识需要学习和补 充以及基本操作与技巧的强化与练习。在以后的工作中,肯定会大有帮助。虽然 即将离开学校,但是学习这事一刻也不能停止。坚持不懈,方能取得更大的成功。 24

河南城建学院本科毕业设计(论文)

参考文献

参考文献
[1] 郑君里, 应启珩, 杨为理. 信号与系统. 第二版.北京: 高等教育出版社, 2000. [2] 管致中,夏恭恪.孟桥.信号与线性系统.第四版.北京:高等教育出版社, 2004. [3] 刘永健.信号与线性系统.修订版.北京:人民邮电出版社,1994. [4] 奥本海姆 A V 等.信号与系统.第二版.刘树棠译.西安:西安交通大学出 版社,2002. [5] 刘培森.应用傅里叶变换.北京:北京理工大学出版社,1990. [6] 奥本海姆 A V 等.离散时间信号处理.黄建国,刘树棠译.北京:科学出版 社,1998. [7] 帕普利斯 A .信号分析.毛培法译.北京:科学出版社,1981. [8] 丁玉美.高西全.数字信号处理.第二版.西安:西安电子科技大学出版社, 2001. [9] 乌镇杨.数字信号处理.北京:高等教育出版社.2004. [10] 斯坦利 W D.数字信号处理.常迥,译.北京:科学出版社,1979. [11] 王华奎.数字信号处理及应用.北京:高等教育出版社,2009. [12] 姚天任.江太辉.数字信号处理.第三版.华中科技大学出版社,2007. [13] 周耀华,汪凯仁.数字信号处理[M].上海:复旦大学出版社,1993. [14] 赵红怡.DSP 技术[M].北京:电子工业出版社,2008. [15] 刘松强.数字信号处理系统及其应用[M].北京:清华大学出版社,1996. [16] 陈后金主编.数字信号处理[M].北京:高等教育出版社,2004. [17] 胡广书.数字信号处理—理论、 算法与实现[M].北京: 清华大学出版社,1997. [18] 陈佩青.数字信号处理教程[M].2 版.北京.清华大学出版社,2001. [19] 门爱东,杨波,全子一.数字信号处理[M].北京:人民邮电出版社,2003. [20] 冷建华,李萍,王良红.数字信号处理[M].北京:国防工业出版社,2002. [21] 王风文,舒冬梅,赵宏才 .数字信号处理[M].北京:北京邮电大学出版社, 2005. [22] 邹彦,唐冬,宁志刚.DSP 原理与应用[M].北京:邮电大学出版社,2004. [23] 吴湘淇.信号、系统与信号处理(上下册)[M].北京:电子工业出版社,199

25

河南城建学院本科毕业设计(论文)

附录 A

附录 A
#include <iostream> #include <iomanip> #include "math.h" using namespace std; double pi = 3.1415926535897932; class complex { public: //无参构造函数 complex() { re=0; im=0; } //有参构造函数 complex(double real,double imag) { re=real; im=imag; } //加法 complex operator + (complex& c) { return complex( re + c.re , im + c.im ); } //减法 complex operator - (complex& c) { return complex( re - c.re , im - c.im ); 26

河南城建学院本科毕业设计(论文)

附录 A

} //乘法 complex operator * (complex& c) { return complex( (re * c.re)-(im * c.im) , (re * c.im)+(im * c.re) ); } //除法 complex operator / (complex& c) { return complex( ( re*c.re + im*c.im )/( c.re*c.re + c.im*c.im ), ((im * c.re)-(re * c.im))/((c.re*c.re)+(c.im*c.im)) ); } //除 2 void half() { re=re/2; im=im/2; } //输出到 ostream void insert(ostream& out) { if(re>=0) cout<<" "; out<<re<< ((im>=0)?'+':'-') <<'j'<< ((im>=0)?im:(0-im)); } //显示 void show() { cout<<re<< ((im>=0)?'+':'-') <<'j'<< ((im>=0)?im:(0-im)) ; } //设值 void setValue(double real,double imag) { if(real>0.00000001||real< -0.00000001) re=real; 27

河南城建学院本科毕业设计(论文)

附录 A

else re=0; if(imag>0.00000001||imag< -0.00000001) im=imag; else im=0; } friend complex c_pow(complex c,int y); private: double re,im; }; //流输出 ostream& operator << (ostream& out, complex c) { c.insert(out); return out; } //乘方 complex c_pow(complex c,int y) { complex returnValue = c ; for(int i = 1 ; i < y ; i++ ) { returnValue = returnValue * c ; } return returnValue; } //获得 Wn void getW(complex w[],int len) { for(int i=0 ; i<len ; i++ ) { w[i].setValue( cos(0 - pi*2*(i)/len) , sin(0 - pi*2*(i)/len) ); 28

河南城建学院本科毕业设计(论文)

附录 A

} } //获得 mWn void getMW(complex w[],int len) { for(int i=0 ; i<len ; i++ ) { w[i].setValue( cos(pi*2*(i)/len) , sin(pi*2*(i)/len) ); } } //倒序重排 void resort(complex x[],int len) { //初始化 int half=len/2; int p1=0,p2; int k; complex temp; //重排 for( p2=0 ; p2+1<len ; p2++ ) { if(p2<p1 && p1+1<len) { temp=x[p1]; x[p1]=x[p2]; x[p2]=temp; } k=half; while(k<p1+1 && p1+1<len) { p1=p1-k; k=k/2; } p1=p1+k; 29

河南城建学院本科毕业设计(论文)

附录 A

} } //基 2 时间 FFT void FFT2t(complex x[],complex y[],int len) { //初始化 int m=0,n,k,j,q; int tlen=len/2; while(tlen!=0) { m++; tlen=tlen/2; } resort(x,len); //倒序重排 for(j=0;j<len;j++) { y[j]=x[j]; } complex *xt = new complex[len]; complex *w = new complex[len]; getW(w,len); //开始迭代运算 q=len; for(int i=1;i<=m;i++) { q=q/2; n=len/q/2; for(j=0;j<len;j++) { xt[j]=y[j]; } if(i!=1) { for(j=0;j<q;j++) 30

河南城建学院本科毕业设计(论文)

附录 A

{ for(k=0;k<n;k++) { xt[n+j*2*n+k]=xt[n+j*2*n+k]*w[k*q]; } } } for(j=0;j<n;j++) { for(k=0;k<q;k++) { y[j+k*2*n]=xt[j+k*2*n]+xt[j+n+k*2*n]; } } for(;j<2*n;j++) { for(k=0;k<q;k++) { y[j+k*2*n]=xt[j-n+k*2*n]-xt[j+k*2*n]; } } } delete[]xt,w; } //基 2 频率 FFT 和 IFFT void FFT(complex x[],complex y[],int len,bool IFFT = false) { //初始化 int m=0,n,k,j,q; int tlen=len/2; while(tlen!=0) { m++; tlen=tlen/2; 31

河南城建学院本科毕业设计(论文)

附录 A

} for(j=0;j<len;j++) { y[j]=x[j]; } complex *xt = new complex[len]; complex *w = new complex[len]; if(IFFT==true) //若是 IFFT 则获取 Wn 序列 { getMW(w,len); } else //若是 FFT 则获取 mWn 序列 { getW(w,len); } //开始迭代运算 n=len; for(int i=1;i<=m;i++) { n=n/2; q=len/n/2; for(j=0;j<len;j++) { xt[j]=y[j]; } for(j=0;j<n;j++) { for(k=0;k<q;k++) { y[j+k*2*n]=xt[j+k*2*n]+xt[j+n+k*2*n]; } } for(;j<2*n;j++) { 32

河南城建学院本科毕业设计(论文)

附录 A

for(k=0;k<q;k++) { y[j+k*2*n]=xt[j-n+k*2*n]-xt[j+k*2*n]; } } if(i!=m) { for(j=0;j<q;j++) { for(k=0;k<n;k++) { y[n+j*2*n+k]=y[n+j*2*n+k]*w[k*q]; } } } if(IFFT==true)//若是 IFFT 则除以 2 { for(j=0;j<len;j++) { y[j].half(); } } } resort(y,len); //倒序重排 delete[]xt,w; } //主函数 void main() { //初始化 complex q(0.9,0.3); complex x[256],y[256],z[256],w[256],v[256],w1; w1.setValue(1,0); getW(w,256); //获取 Wn 序列 33

河南城建学院本科毕业设计(论文)

附录 A

x[0].setValue(1,0); for(int i=1;i<256;i++)//定原序列的值 { x[i]=x[i-1]*q; } //输出原序列 cout<<"原序列:"<<endl; for(i=0;i<256;i+=2) { cout<<setiosflags(ios::fixed)<<setprecision(6)<<x[i]<<"\t"<<x[i+1]<<endl; } for(i=0;i<256;i++) //进行公式计算 { complex a=w1-(x[255]*q),b=w1-q*w[i]; v[i]=a/b; } //输出公式计算值 cout<<"公式计算值:"<<endl; for(i=0;i<256;i+=2) { cout<<v[i]<<"\t"<<v[i+1]<<endl; } FFT2t(x,y,256); //进行基 2 时间变换 //输出基 2 时间变换后序列 cout<<"基 2 时间变换后序列:"<<endl; for(i=0;i<256;i+=2) { cout<<y[i]<<"\t"<<y[i+1]<<endl; } FFT(y,z,256,1); //进行反变换 34

河南城建学院本科毕业设计(论文)

附录 A

//输出反变换后的序列 cout<<"反变换后的序列:"<<endl; for(i=0;i<256;i+=2) { cout<<z[i]<<"\t"<<z[i+1]<<endl; } }

35

河南城建学院本科毕业设计(论文)

附录 B

附录 B

36

河南城建学院本科毕业设计(论文)

附录 B

37

河南城建学院本科毕业设计(论文)

附录 B

38

河南城建学院本科毕业设计(论文)

附录 B

39

河南城建学院本科毕业设计(论文)

附录 B

40

河南城建学院本科毕业设计(论文)

附录 B

41

河南城建学院本科毕业设计(论文)

附录 B

42

河南城建学院本科毕业设计(论文)

附录 B

43

河南城建学院本科毕业设计(论文)

致谢

致谢
时光荏苒,岁月匆匆,转眼间,几个月的时间已经过去了,我的毕业设计也 终于顺利完成。对此我既感到由衷的欣慰,又感到了巨大的鼓舞。光阴似箭,转 眼间我们的大学生涯已经接近尾声,此时此刻,我们脑海中会不断出现刚进入大 学校园那张青涩的脸庞,那张天真的笑容,那种对大学生活充满无数期待的表情。 我们是带着梦想踏入大学校门,而如今我们却带着碎梦将要离开这里。 在这几个月的毕业设计过程中,老师认真地指导我,解答我提出的问题,给 了我很多论文方面的设计建议。在此,我衷心的感谢我的指导老师,非常感谢他 的付出。在我刚拿到设计题目时,我就好像拿了一张空白的纸张,不知道从哪里 开头,老师一点点不断的给我启发,给我教导,作为指导老师,他由衷的希望自 己所带的学生能够真正从本次设计中学到很多知识,耐心的给我讲解,和我一起 探讨我的设计,作为学生的我,没有理由不认真完成这次设计。 在论文的写作中,我和小组中的同学,整天在一起相互探讨,相互帮忙,大 家一起去图书馆查找相关资料,借阅有关书籍,同时相互分享大家所掌握的资料 和工具书。在此期间,大家都从对方那里学到了很多自己不曾学到的知识,了解 了许多自己不曾知道的技术,可以说大家在一起互相学习,共同进步。同样,感 谢我的同学们,我们就是在一个大家庭里,互相帮助、 互相学习,很感谢他们, 我会用我的行动来证明这一切。在此对这些给予我很大帮助的同学表示衷心的感 44

河南城建学院本科毕业设计(论文)

致谢

谢! 我很爱我的大学,我也相信每一位同学也都深爱着自己的母校,因为这里的 确使我们蜕变的地方,是我们把所有梦想汇聚在一起的地方,好像这个时候用梦 想这两个字有点牵强,但是,我实在想不出我在这里除了梦想还有什么?到底还 有什么?我可能会知道的。我们就好像又站在了一个无边无际的十字街头,开始 重新的定位和选择,我们面对着眼前模糊的一切,只能偷偷的擦去眼角边的泪水。 最后,还要感谢我们电气工程及其自动化专业的老师们,是你们几年的呕心 沥血,孜孜不倦的教诲,让我学到了很多我的毕业设计课题所涉及到的相关知识, 为我这次能够顺利完成自己的毕业设计打下了一个坚实的基础。很感谢在校园中 认识的所有人,老师、同学他们都是我一生的好朋友,使它们和我一起共同度过 了美好的大学时光,百感交集的心情让我的心很是沉痛,我不舍得这里,这里有 我们无尽的欢笑,无尽的想象。 相信经过这次的毕业设计的圆满完成,一定会对我以后的工作有所帮助,同 时也为自己以后事业的发展有一个很好的促进作用。

45


赞助商链接
相关文章:
按时间抽取的基2FFT算法分析及MATLAB实现
按时间抽取的基2FFT算法分析及MATLAB实现 - 按时间抽取的基 2FFT 算法分析及 MATLAB 实现 一、DIT-FFT 算法的基本原理 基 2FFT 算法的基本思想是把原始的 N ...
按时间抽取的基2FFT算法分析及MATLAB实现
C语言实现基2FFT算法-时... 4页 1下载券喜欢此文档的还喜欢 基2DIT-FFT的...2 DIT-FFT 算法的运算规律及编程思想为了编写 DIT-FFT 算法的运算程序, 首先...
C语言实现基2FFT算法-时间抽选
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 C语言实现基2FFT算法-时间抽选 C语言实现基2FFT算法-时间抽选C语言实现...
三种C语言实现的FFT例程
三种C语言实现的FFT例程_工程科技_专业资料。快速福利...FFT_N/2&&n<FFT_N) a=-SIN_TAB[n-FFT_N/2...FFT算法研究与实现(C语言... 3页 1下载券 FFT_...
FFT的C语言算法实现
FFT的C语言算法实现_信息与通信_工程科技_专业资料。一个用C语言写的简易的FFT...(); return 0; } /*进行基-2 FFT 运算*/ void fft() { int i=0,j...
C语言实现基2FFT算法-频域
C语言实现基2FFT算法-频域_IT/计算机_专业资料。C语言实现基2FFT算法-频域/*基二频域算法*/ #include "math.h" #include "stdio.h" struct compx { double...
用C语言编写FFT算法
C语言编写FFT算法_数学_自然科学_专业资料。用 C 语言编写 FFT 算法 用 simulink 建模的方法实现 FFT 的问题特别多,还不如手工编写,也不是很复杂。 以下是 ...
C语言实现FFT
采用雷德算法 //如果 i<j,即进行变址 } k=nv2; while(k<=j) { j=j...(n>=FFT_N/2&&n<FFT_N) a=-SIN_TAB[n-FFT_N/2]; return a; } /...
用c语言实现的FFT
c语言实现的FFT_计算机软件及应用_IT/计算机_专业...2.FFT 算法的基本原理 FFT 算法是把长序列的 DFT...按蝶形运算的构成不同可分为基 2,基 4,基 8,...
FFT算法设计与实现
FFT算法设计与实现_信息与通信_工程科技_专业资料。c语言实现FFT算法 ...2页 1下载券 基于VB的FFT算法的设计... 3页 1下载券 1M点FFT算法的...
更多相关标签: