下载文档原格式
1 设计任务描述1.1 设计题目快速傅里叶变换程序设计设计要求1.2.1 设计目的1）理解FFT的算法以及利用DSP实现的方法。
2）能熟练的调试程序并能观察其结果。
3）熟悉TMS320C54x系列DSP芯片的软件设计方法。
基本要求1）研究FFT原理以及利用DSP实现的方法。
2）编写FFT程序。
3）调试程序，观察结果。
2 设计思路2.1 FFT 算法原理若给定由N 个信号样本{x （0），x （1），…，x （N -1）}组成的信号序列x （n ），DFT 可用式2-1给出：1()()N nkNn X k x n W-==∑ k =0,1，…，N -1（2-1）式2-1中，nk N W 称为旋转因子或蝶形因子，nkN W =2/j nk Neπ-。
从中可以看出：当信号样本为复数时，计算单个()X k 需经过N 次复数乘法和N -1次复数加法运算，相当于4N 次实数乘法和2（2N -1）次实数加法。
完成全部N 点DFT 共需2N 次复数乘法和N （N -1）复数加法运算。
可见，随着N 不断增加，整个DFT运算量是相当庞大的，而FFT 算法通过对计算过程的深入分析，利用旋转因子nkNW 具有的周期性与对称性，实现了降低运算复杂度的目的。
当序列长度N 为偶数时，信号序列x （n ）可被分解为奇、偶两个子序列，相应的N 点DFT 被分解为两个N /2点的DFT ：()()()kN X k G k W H k =+ k =0,1, …，N /2-1（2-2）(/2)()()k N X N k G k W H k +=- k =0,1, …，N /2-1（2-3）式（2-2）和（2-3）中，G(k)和()H k 分别表示x （n ）分解后得到的N /2点偶序列点奇序列的DFT 。
式（2-2）和式（2-3）表明，只要求出G(k)和()H k ，x （n ）前N /2点和后N /2点的DFT 就得到了，整个序列的DFT 也就得到了。
快速傅立叶变换（FFT ）的实现一、实验目的1.了解FFT 的原理及算法；2.了解DSP 中FFT 的设计及编程方法；3.熟悉FFT 的调试方法；二、实验原理FFT 是一种高效实现离散付立叶变换的算法，把信号从时域变换到频域，在频域分析处理信息。
对于长度为N 的有限长序列x (n )，它的离散傅里叶变换为：(2/)j N nk N W e π-=，称为旋转因子，或蝶形因子。
在x (n )为复数序列的情况下，计算X (k )：对某个k 值，需要N 次复数乘法、(N -1)次复数加法；对所有N 个k 值，需要2N 次复数乘法和N (N -1)次复数加法。
对于N 相当大时（如1024）来说，直接计算它的DFT 所作的计算量是很大的，FFT 的基本思想在于： 利用2()j nk N N W e π-=的周期性即：k N k N N W W +=对称性：/2k k N N N W W +=-将原有的N 点序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。
按时间抽取的FFT ——DIT FFT 信号流图如图5.1所示：图5.1 时间抽取的FFT —DIT FFT 信号流图FFT 算法主要分为以下四步。
第一步 输入数据的组合和位倒序∑=-=10)()(N n nk N W n x k X把输入序列作位倒序是为了在整个运算最后的输出中得到的序列是自然顺序。
第二步 实现N 点复数FFT第一级蝶形运算；第二级蝶形运算；第三级至log2N 级蝶形运算；FFT 运算中的旋转因子N W 是一个复数，可表示：为了实现旋转因子N W 的运算，在存储空间分别建立正弦表和余弦表，每个表对应从0度到180度，采用循环寻址来对正弦表和余弦表进行寻址。
第三步 功率谱的计算X (k )是由实部()R X k 和虚部()I X k 组成的复数：()()()R I X k X k jX k =+；计算功率谱时只需将FFT 变换好的数据，按照实部()R X k 和虚部()I X k 求它们的平方和，然后对平方和进行开平方运算。
fft课程设计一、教学目标本课程的教学目标是让学生掌握快速傅里叶变换（FFT）的基本原理和应用方法。
具体包括以下三个方面：1.知识目标：学生需要了解FFT的基本概念、原理和算法，理解FFT在信号处理、图像处理等领域的应用。
2.技能目标：学生能够运用FFT对实际问题进行分析和解决，具备使用FFT进行数据处理和分析的能力。
3.情感态度价值观目标：培养学生对科学研究的兴趣和热情，使学生认识到FFT在现代科技发展中的重要性，培养学生的创新意识和团队合作精神。
二、教学内容本课程的教学内容主要包括以下几个部分：1.FFT的基本概念：介绍FFT的定义、特点和应用领域，使学生了解FFT在信号处理、图像处理等领域的基本作用。
2.FFT的原理：讲解FFT的基本算法，包括DFT、FFT的计算过程，让学生理解FFT的实现原理。
3.FFT的应用：通过具体案例分析，使学生掌握FFT在信号处理、图像处理等领域的应用方法。
4.FFT的优化：介绍FFT的算法优化方法，让学生了解如何提高FFT的计算效率。
三、教学方法为了实现本课程的教学目标，将采用以下几种教学方法：1.讲授法：通过讲解FFT的基本概念、原理和应用，使学生掌握FFT的基本知识。
2.案例分析法：通过分析具体案例，让学生了解FFT在实际问题中的应用方法。
3.实验法：安排实验课程，让学生动手实践，加深对FFT的理解和运用能力。
4.小组讨论法：学生进行小组讨论，培养学生的团队合作精神和创新能力。
四、教学资源为了支持本课程的教学内容和教学方法，将准备以下教学资源：1.教材：选择合适的教材，为学生提供系统的学习资料。
2.参考书：提供相关领域的参考书籍，丰富学生的知识体系。
3.多媒体资料：制作PPT、视频等多媒体资料，增强课堂教学的趣味性和生动性。
4.实验设备：准备计算机、信号发生器等实验设备，为学生提供实践操作的机会。
五、教学评估本课程的评估方式包括以下几个方面：1.平时表现：通过观察学生在课堂上的参与程度、提问回答等情况，评估学生的学习态度和理解能力。
§2.4 快速傅里叶变换 (FFT) 实现一、实验目的 1. 掌握FFT 算法的基本原理；2. 掌握用C 语言编写DSP 程序的方法。
二、实验设备 1. 一台装有CCS3.3软件的计算机； 2. DSP 实验箱的TMS320F2812主控板；3. DSP 硬件仿真器。
三、实验原理傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。
离散傅里叶变换（DFT ）是傅里叶变换在离散系统中的表示形式。
但是DFT 的计算量非常大， FFT 就是DFT 的一种快速算法, FFT 将DFT 的N 2 步运算减少至 ( N/2 )log 2N 步。
离散信号x(n)的傅里叶变换可以表示为∑=-=10][)(N N nk N W n x k X ， Nj N e W /2π-=式中的W N 称为蝶形因子，利用它的对称性和周期性可以减少运算量。
一般而言，FFT 算法分为时间抽取（DIT ）和频率抽取（DIF ）两大类。
两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。
本实验以时间抽取方法为例。
时间抽取FFT 是将N 点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。
偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。
这样x(n) 的N 点DFT 可写成：()()∑++∑=-=+-=12/0)12(12/02122)(N n kn NN n nkNW n x Wn x k X考虑到W N 的性质，即2/)2//(22/)2(2][N N j N j N W e e W ===--ππ因此有：()()∑++∑=-=-=12/02/12/02/122)(N n nkN kNN n nkN W n x W Wn x k X或者写成：()()k Z W k Y k X kN +=)(由于Y(k) 与Z(k) 的周期为N/2，并且利用W N 的对称性和周期性，即：k NN k N W W -=+2/可得：()()k Z W k Y N k X kN -=+)2/(对Y(k) 与Z(k) 继续以同样的方式分解下去，就可以使一个N 点的DFT 最终用一组2点的DFT 来计算。
快速傅里叶变换[编辑]维基百科，自由的百科全书跳转至：导航、搜索傅里叶变换Z变换傅里叶级数傅里叶变换离散傅里叶级数离散时间傅里叶变换离散傅里叶变换快速傅里叶变换分数傅里叶变换短时距傅立叶变换小波变换离散小波变换连续小波变换快速傅里叶变换（英语：Fast Fourier Transform, FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。
快速傅里叶变换有广泛的应用，如数字信号处理、计算大整数乘法、求解偏微分方程等等。
本条目只描述各种快速算法。
对于复数序列，离散傅里叶变换公式为：直接变换的计算复杂度是（参见大O符号）。
快速傅里叶变换可以计算出与直接计算相同的结果，但只需要的计算复杂度。
通常，快速算法要求n能被因数分解，但不是所有的快速傅里叶变换都要求n是合数，对于所有的整数n，都存在复杂度为的快速算法。
除了指数的符号相反、并多了一个1/n的因子，离散傅里叶变换的正变换与逆变换具有相同的形式。
因此所有的离散傅里叶变换的快速算法同时适用于正逆变换。
目录[隐藏]∙ 1 一般的简化理论∙ 2 快速傅里叶变换乘法量的计算∙ 3 Cooley-Tukey算法o 3.1 设计思想∙ 4 其他算法∙ 5 实数或对称资料专用的算法∙ 6 复杂度以及运算量的极限∙7 参考资料∙8 参阅一般的简化理论[编辑]假设一个M*N Sub-rectangular matrix S可分解成列向量以及行向量相乘：若有个相异的non-trivialvalues( where )有个相异的non-trivial values则S共需要个乘法。
Step 1：Step 2：简化理论的变型：也是一个M*N的矩阵。
若有个值不等于0，则的乘法量上限为。
快速傅里叶变换乘法量的计算[编辑]假设，其中彼此互质点DFT的乘法量为，则点DFT的乘法量为：假设，P是一个质数。
若点的DFT需要的乘法量为且当中 () 有个值不为及的倍数，有个值为及的倍数，但不为的倍数，则N点DFT的乘法量为：Cooley-Tukey算法[编辑]主条目：Cooley-Tukey快速傅里叶变换算法Cooley-Tukey算法是最常见的FFT算法。
实验五 快速傅立叶变换（FFT ）的实现一、 实验目的在数字信号处理系统中，FFT 作为一个非常重要的工具经常使用，甚至成为DSP 运算能力的一个考核因素。
FFT 是一种高效实现离散付氏变换的算法。
离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。
本实验的目的在于学习FFT 算法，及其在TMS320C54X 上的实现，并通过编程掌握C54X 的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS 的探针和图形工具。
另外在BIOS 子目录下是一个使用DSP/BIOS 工具实现FFT 的程序。
通过该程序，你可以使用DSP/BIOS 提供的分析工具评估FFT 代码执行情况。
二、 实验原理㈠ 基—2按时间抽取FFT 算法对于有限长离散数字信号{x[n]}，0 ≤ n ≤ N-1，其离散谱{x[k]}可以由离散付氏变换（DFT ）求得。
DFT 的定义为可以方便的把它改写为如下形式：不难看出，W N 是周期性的，且周期为N ，即W N 的周期性是DFT 的关键性质之一。
为了强调起见，常用表达式W N 取代W 以便明确其周期是N 。
由DFT 的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N 点DFT 需()1,...,1,0][)2(1-==--=∑N k en x k X nk Nj N n π()1,...,1,0][10-==∑-=N k W n x k X nk NN n ...2,1,0,))((±±==++l m W W nkNlN k mN n N要（N-1）2次复数乘法和N （N-1）次加法。
因此，对于一些相当大的N 值（如1024）来说，直接计算它的DFT 所作的计算量是很大的。
FFT 的基本思想在于，将原有的N 点序列序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。
数字信号处理_快速傅里叶变换FFT实验报告快速傅里叶变换(FFT)实验报告1. 引言数字信号处理是一门研究如何对数字信号进行处理、分析和提取信息的学科。
傅里叶变换是数字信号处理中常用的一种方法，可以将信号从时域转换到频域。
而快速傅里叶变换(FFT)是一种高效的计算傅里叶变换的算法，广泛应用于信号处理、图象处理、通信等领域。
2. 实验目的本实验旨在通过编写程序实现快速傅里叶变换算法，并对不同信号进行频谱分析。
3. 实验原理快速傅里叶变换是一种基于分治策略的算法，通过将一个N点离散傅里叶变换(DFT)分解为多个较小规模的DFT，从而实现高效的计算。
具体步骤如下： - 如果N=1，直接计算DFT；- 如果N>1，将输入序列分为偶数和奇数两部份，分别计算两部份的DFT；- 将两部份的DFT合并为整体的DFT。
4. 实验步骤此处以C语言为例，给出实验的具体步骤：(1) 定义输入信号数组和输出频谱数组；(2) 实现快速傅里叶变换算法的函数，输入参数为输入信号数组和输出频谱数组；(3) 在主函数中调用快速傅里叶变换函数，得到输出频谱数组；(4) 对输出频谱数组进行可视化处理，如绘制频谱图。
5. 实验结果与分析为了验证快速傅里叶变换算法的正确性和有效性，我们设计了以下实验：(1) 生成一个正弦信号，频率为100Hz，采样频率为1000Hz，时长为1秒；(2) 对生成的正弦信号进行快速傅里叶变换，并绘制频谱图；(3) 生成一个方波信号，频率为200Hz，采样频率为1000Hz，时长为1秒；(4) 对生成的方波信号进行快速傅里叶变换，并绘制频谱图。
实验结果显示，对于正弦信号，频谱图中存在一个峰值，位于100Hz处，且幅度较大；对于方波信号，频谱图中存在多个峰值，分别位于200Hz的奇数倍处，且幅度较小。
这与我们的预期相符，说明快速傅里叶变换算法能够正确地提取信号的频谱信息。
6. 实验总结通过本次实验，我们成功实现了快速傅里叶变换算法，并对不同信号进行了频谱分析。
实践课名称设计报告题目：居中填写院系：电气信息工程系专业：组长：学号：组员1 ：学号：组员2 ：学号：组员3 ：学号：组员4 ：学号：组员5 ：学号：组员6 ：学号：指导教师：XXXX年XX月XX日实践课名称设计报告一、选题目的和意义：傅里叶分析的研究与应用至今已经历了一百余年。
进入二十世纪后，谐振电路、滤波器、正弦振荡器等一系列具体问题的解决为正弦函数与傅里叶分析的进一步应用开辟了广阔的前景。
从此，人们逐渐认识到，在通信与控制系统的理论研究与实际6.门函数信号时域波形图、频域图非周期信号的傅里叶变换原理及性质信号的傅立叶变换定义为：（1-1）值得注意的是，的傅立叶变换存在的充分条件是在无限区间内绝对可积，即满足式子：。
但此式并非是的必要条件。
当引入奇异函数概念后，使一些不满足绝对可积的也能进行傅立叶变换。
傅立叶逆变换定义是：（1-2）称为的频谱密度函数。
傅立叶变换的性质（1）线性性质：（1-3）（2）频移性质：（1-4）（3）时移性质：（1-5）（4）尺度变换性质：（1-6）（5）对称性质：（1-7）（6）时域微分性质：（1-8）（7）频域微分性质：（1-9）（8）时域积分性质：（1-10）（9）频域卷积定理：则（1-11）（10）时域卷积定理：则（1-12）傅立叶变换及逆变换的MATLAB实现MATLAB 的Symbolic Math Toolbox 提供了能直接求解傅里叶变换及逆变换的函数fourier()及ifourier()。
三、设计的方法及步骤：使用以下MATLAB函数对本次研究内的6个非周期信号函数进行仿真实现。
傅立叶变换(1) F=fourier(f)(2) F=fourier(f,v)(3) F=fourier(f,u,v)说明：(1) F=fourier(f)是符号函数f 的傅立叶变换，缺省返回是关于ω的函数。
如果f=f(ω),则fourier 函数返回关于t 的函数。
(2)F=fourier(f,v)返回函数F 是关于符号对象v 的函数，而不是默认的ω，即(3)F=fourier(f,u,v)对关于u 的函数f 进行变换，返回函数F 是关于v 的函数，即傅立叶逆变换(1) f=ifourier(F)(2) f=ifourier(F,u)(3) f=ifourier(F,v,u)说明：(1) f=ifourier(F)是函数F的傅立叶逆变换。
快速傅里叶变换快速傅里叶变换在信号处理等领域有着广泛的应用。
在竞赛中，TTF 主要用途是求两个多项式的乘积，即给定两个阶小于n 的多项式∑-==1)(n k kk xa x A ，∑-==1)(n k kk xb x B ，需要求解)()()(220x B x A x C x C n k k k==∑-=。
注意)(x C 的阶是不超过n 2，而不是n 。
朴素算法依次计算)(x C 的各个系数∑=-=ki ik i k ba C 0，复杂度为)(2n O ，而通过FFT 可以做到)log (n n O 。
在FFT 中需要应用到一些复数的知识。
方程1=nx 在复数域上一共有n 个不同的解，可以表示为nk i n k ππ2sin 2cos+或是等价的)1..0(/2-=n k e ni k π。
记n i e /2π为n ω，则这n 个解也可以表示成1...-n n n ωω。
n ω被称为单位根。
从几何的角度来看，这n 个解对应到的是复平面上单位圆的n 等分点。
对于一个小于n 阶的多项式，如果给出它在n 个不同位置的取值，则该多项式的系数是唯一确定的 。
例如若已知一个小于3阶的多项式)(x F 满足1)0(=F 、3)1(=F 、1)1(=-F ，则可以知道1)(2++=x x x F 。
如果已知一个小于n 阶多项式的系数，则可以在)(2n O 的时间内求得它在任意n 个不同位置上的取值。
如果已知一个小于n 阶的多项式在n 个不同位置上的取值，则可以通过拉格朗日插值公式（)(2n O 的复杂度）或是求解线性方程组()(3n O 的复杂度）得到它的系数。
若n 为偶数，则kn k n 2/2ωω=。
FFT 基本思路是通过计算)(x A 在n 2个不同位置上的取值以及)(x B 同样在这n 2个位置上的取值之后，将这两组取值按位置相乘，就得到了)(x C 在这n 2个位置上去取值。
最后再将)(x C 的系数推出来。
河北联合大学本科毕业设计（论文）2011年 5月24日题目傅里叶变换在信号与系统中的应用专业数学与应用数学姓名刘帅学号 200710050113主要内容、基本要求、主要参考资料等主要内容傅里叶变换是一种重要的变换,且在与通信相关的信号与系统中有着广泛的应用。
本文主要研究傅里叶变换的基本原理；其次，掌握其在滤波，调制、解调,抽样等方面中的应用。
分析了信号在通信系统中的处理方法，通过傅里叶变换推导出信号调制解调的原理，由此引出对频分复用通信系统的组成原理的介绍.基本要求通过傅里叶变换实现一个高通滤波，低通滤波,带通滤波。
用傅里叶变换推导出信号调制解调的原理。
通过抽样实现连续信号离散化,简化计算.另外利用调制的原理推导出通信系统中的时分复用和频分复用。
参考资料[1］《信号与系统理论、方法和应用》徐守时著中国科技大学出版社 2006年3月修订二版［2］《信号与系统》第二版上、下册郑君里、应启珩、杨为理著高等教育出版社[3]《通信系统》第四版 Simon Haykin 著宋铁成、徐平平、徐智勇等译沈连丰审校电子工业出版社[4]《信号与系统—连续与离散》第四版 Rodger E.Ziemer 等著肖志涛等译腾建辅审校电子工业出版社[5]《现代通信原理》陶亚雄主编电子工业出版社[6］《信号与系统》乐正友著清华大学出版社[7］《信号与线性系统》阎鸿森、王新风、田惠生编西安交通大学出版社［8］《信号与线性系统》张卫钢主编郑晶、徐琨、徐建民副主编西安电子科技大学出版社［9] http：//baike.baidu。
com/view/191871.htm//百度百科傅里叶变换[10]《通信原理》第六版樊昌信曹丽娜编著国防工业出版社[11］A．V．Oppenheim，A。
S。
Willsky with S。
H.Nawab.Siganals and systems（Second edition).Prentice-Hall，1997.中译：刘树棠.信号与系统。
华中科技大学信号与系统课程设论文快速傅里叶变换（FFT）的计算机实现学院：班级：学号：姓名：指导老师：二〇一三年八月摘要用C语言编程完成对输入波形的时域采样的FFT变换以及频域分析，同时用DFT 变换来验证FFT变换结果的正确性。
时域信号的输入有两种方式：一种是依次输入时域信号（仅支持多个正弦及余弦信号之和的形式）各谐波分量的幅值和角频率值，另一种是直接输入时域信号的采样值。
然后进行DFT变换和FFT变换，两者结果应该是一样的。
DFT变换的实现直接脱胎于定义，FFT变换采用的是基2时间抽取算法，用倒位序算法和蝶形算法实现。
关键词：傅里叶变换；DFT； FFT；倒位序1背景知识1.1 为什么要进行傅里叶变换在进行科学研究的过程中，很重要的一点就是为一个系列的问题找到一个通法，从而为实际的应用打下基础。
在信号分析这个方向，如果直接对时域信号进行分析，那么我们将发现，很难找到一种固定的方法来进行分析，这是因为信号对时间t的函数形式存在无数种，我们是无法将这些函数以及这些函数的各种形式的组合都统一起来进行研究的。
而进行傅里叶变换之后，我们就能很好达到这个目的——用一种方法来研究所有的信号（这些信号也需要满足一定的条件，但范围是非常广的）。
那么为什么傅里叶变换可以达到这样的目的呢？对于一个时域信号，我们习惯从时间的角度进行理解，也就是以时间为自变量，以信号值为因变量，一个信号是该信号在所有的时间点的值的叠加，每个信号分量在时间域上只占据了一个点，要想得到这个信号的所有信息，我们需要知道这个信号在时间轴上每一点的值，缺一不可。
傅里叶变换之后，依然是一个叠加的问题，只不过由时间角度的叠加变成了频率角度的叠加，这时每一个信号分量都覆盖了一个时间域上的整个区间，并且每一个信号分量都是周期性的（三角函数的周期性），这样，只需要知道每个信号分量的幅值、频率、相位就能在时间轴上得到它的所有信息，而所有信号分量的叠加就得到了原来的信号。
并且我们并非需要将所有信号分量都叠加起来，这是因为傅里叶变换之后，随着信号分量频率值的上升，信号分量幅值呈一个较快的下降趋势，在精度允许的范围内，我们并不需要去考虑频率值超出某个范围的那部分信号分量，我们所考虑的那个频率区间的信号分量的叠加已经能够很好的还原出原信号，而这个频率区间只占据了频率轴很少的部分，从而简化了后面的分析过程。
同时，若原信号是周期性的，那该信号在频率轴上将只占据有限个点，分析难度更是大大减小。
1.2傅里叶级数1.2.1频率分量与频率成分对于时域信号来说，频率含量就是信号被分成的正弦波簇所确定的所有频率分量。
例如，有（1-1）式中，N rad/s正弦波的相位。
根据式（1-1）其1-1）定义的信号完全由频率，振幅和相信的相位所确定。
由式（1-1）定义的信号特征，可以通过对组成该信号的正弦频率，振幅，相位来研究。
1.2.2周期信号的三角傅里叶级数式：在式（1-2）rad/s）在式（1-21-6）确定：表达式（1-2k次谐波项为的重要特性。
由式（1-2）给定的三角傅里叶级数可以在写成余弦函数和相位的形式：式中：并且：1.2.3复指数级数由式（1-2）给定的三角傅里叶级数可以表示成如下的指数形式：在式（1-10rad/s），且式（1-10应该注意到，式（1-11）给定的也能在任何整周期上的积分计算出来，例如：1.3傅里叶变换及其直角和极坐标表达式一般意义上，（1-13）式中的积分收敛（存在），是“表现良好”的和绝对可积的，那么积分就是收敛的。
绝对可积是指下式成立：“表现良好”就是信号在任何有限的时间段内存在有限的间断点和最大、最小值。
除了脉冲信号，我们感兴趣的大部分信号都是“表现良好”的。
所有实际信号（即物理上可以产生的信号）都是“表现良好”的，且满足（1-14）式。
数。
因为复数既可以表示成直角坐标形式，也可以表示成极坐标形式，所以，也可以表示成这两种形式。
下面将定义这两种形式。
则的直角坐标表达式为：式中，是的模，是的辐角。
利用下面的关系，可以由直角坐标表达式换成极坐标表达式：1.4 离散时间信号的傅里叶分析1.4.1离散时间傅里叶变换DTFT他的离散时间傅里叶变换（DTFT ）定义为：一般地，由上式定义的般意义的DTFTDTFT如果是时限的离散时间信号，显然，上式中的和是有限值，类似这样的信号都存在一般意义下的DTFT 。
-DTFT坐标其中：:其中：1.4.2离散傅里叶变换DTFT实现DTFT ，必须在频率上离散化，从而引出了下面定义的离散傅里叶变换的概念。
DFT义为：由式（1-16）可见，k角坐标形式。
极坐标形式是：直角坐标形式是：其中：1.5 FFT 算法时间抽取算法的基本思想是把时间间隔细分，计算可以分成两部分，首先对符号进行简化，1的N 次开放，即：假设N>1N 点DFT 和DFT 反变换为：现在令N 是一个偶整数，以便N/2是一个整数。
已知信号x[n],令a[n]为x[n]的偶数次项，b[n]为x[n]N/2）点DFT ，即：N 点DFT ，可有：次乘法。
为了看清这一点，首先注意到计算kN/2次乘法，所以，总N 非常大时，可以大大减少乘法次数。
如果N/2q为正整数，这个递减的过程可以重复进行，知道信号只剩下一个非零值。
下图给出了N=8时FFT算法的流程图（图1-1）n的范围是0~N-1，时间标号n可以用q位二进制数来表示，把这q位二进制数进行倒位序排列，记得FFT1-1给出了图1-1中FFT算法的输入信号值的顺序。
图1-1 N=8时的FFT算法流程图表1-1 N=8时的倒位序排列时间（n）二进制代码倒位序代码排序0000000x[0]1001100x[4]2010010x[2]3011110x[6]4100001x[1]5101101x[5]6110011x[3]7111111x[7]1.5.1倒位序算法在进行FFT运算时，第一步要实现的就是倒位序排列。
假设使用A[I]存的是顺序位序，而B[J]存的是倒位序。
I<J的时候需要变序，I>J的时候就不用。
不然就相当于作了两次变序，又变回去了。
从表1-1可知，按自然顺序排列的二进制数，其下面的数总是比其上面的数大1，即下面的数是上面的数在最低位加1并向高位进位而得到的。
而倒位序二进制数的下面的数是上面的数在最高位加1并由高位向低位进位而得到。
由数组的性质可知，I、J都是从0开始，若已知某个倒位序J，要求下一个倒位序数，则应先判断J的最高位是否为0，这可与flag=N/2相比较。
如果flag>J，则J的最高位为0，只要把该位变为1（J与flag=N/2相加即可），就得到下一个倒位序数；如果flag<=J，则J的最高位为1，可将最高位变为0（J与flag=N/2相减即可）。
然后还需要判断次高位，这可与flag’=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到下一个倒位序数；若次高位是1，则需将它也变为0。
依此类推即可得到最后的倒位序排列。
2c语言实现见附录3利用c程序进行频谱分析3.1直接输入离散信号取样值进行DFT和FFT3.1.1取样点N=4，时域信号取样值xn[]={1，2，2，1}结果见下图可见FFT和DFT的结果基本上是一样的，仅在小数点第六位才有一点差别，见XK[3]。
3.1.2取样点N=5，时域信号取样值xn[]={1，2，2，4，5}结果见下图当N=时，DFT仍然可以进行，因为DFT的代码“翻译”自DFT的定义而来，而FFT的代码是“翻译”自倒位序算法和蝶形算法，这两种算法对取样点数有要求，N必须是以2为底的正指数。
同时，此c程序还对取样点最大值有要求，不得超过128.3.2输入正弦谐波分量信息，让计算机进行取样3.2.1N=4、8、16此时，，最大谐波次数maxharmanicorder=5，谐波分量系数为a[1]=9,a[3]=3,a[5]=1。
N=4时结果见下图：N=8时结果见下图：N=16时，结果见下图（仅出示FFT）幅度谱图（从左至右N=4、6、8）：幅度谱分析：由上图可知，随着取样点数的增加，边界点的幅值急剧上升，不过图像的整体趋势不变相位谱（从左至右N=4、6、8）：由上图可知，随着取样点数的增加，相位谱的变化趋势没有发生变化，只是将原本的取样点变得更密集了而已。
3.2.2取样点数N=8，时域信号函数filemaxharmanicorder=5，a[1，3，5]={9，3，1}，此时，maxharmanicorder=7，a[1，3，5，7]={9，3，1，0.5}，此时，maxharmanicorder=9，a[1，3，5，7，9]={9，3，1，0.5，0.25}幅度谱（从左至右高次谐波分量有增加）：由上图可知，随着谐波分量的增加，幅度谱的个别取样点幅值有变化，由于谐波分量增量很小，因此幅值变化也很小，同时，整体波形变化也不大。
由上图分析可知，随着谐波分量的增加，相位谱完全没有变化。
这是因为增加的谐波分量的频率值时基波的整数倍。
4总结在此次的课程设计中，我是用C语言和MS Visual Studio 2010完成C语言编程部分，Matlab 完成绘图部分，Word完成文字部分。
完成这份课设让我收获良多。
从课程的角度来说，加深了对傅里叶变换和快速傅里叶变换的理解，学会了从频域的角度来理解信号，让我体会到，换一个角度来解决相同的问题，是可以得到更简单的方法的，不过前提是变换和逆变换必须是等价的。
从课程之外的角度来说，这是我第一次用C语言来解决一个问题，这个过程可以说是对C语言的一个重新学习，Matlab同样如此，学过之后就放下了，也很快就忘记了，这次虽然用到的不多，但是也让我更加体会到实践运用才是学习的最好方法；同时，完成课设报告的过程也让我学习了论文的格式和排版。
附录 C语言代码#include<stdio.h>#include<math.h>#define maxnum 128 //宏定义最大数：用以初始化数组，且限制了时域信号取样点数须小于128#define PI 3.1415926 //宏定义圆周率struct XKstruct//频域信号采样点结构体{double real; //实部double image; //虚部double absolutevalue; //绝对值double phaseangle; //相位角double radianmeasureangle; //用圆周率表示的角度};struct complexnum//复数结构体{double real; //实部double image; //虚部};struct complexnum complexmul(struct complexnum ,struct complexnum ); //函数声明语句，在定义处进行功能介绍void ComplexnumToXKStruct(int,struct complexnum*,struct XKstruct*);void DFTfunction(int ,double*,struct complexnum*);void FFTfunction(int ,double *,struct complexnum *);void xndistribute(int N,double *xn,double *an,double *bn);void initfunction();void display(int ,struct XKstruct*);void stardivision();void timedomainsignalsample(int ,double *);void main(){int i,N; //i为辅助变量，N为时域信号取样点数double xn[maxnum]; //xn[N]存放时域信号采样值struct complexnum XK[maxnum]; //XK[N]存放频域信号采样值struct XKstruct XK1[maxnum],XK2[maxnum]; //XK1[N]存放DFT变换后的频域信号采样值，XK2[N]存放FFT变换后的频域信号采样值//double w; //基波角频率//double a[maxnum]; //谐波分量系数initfunction(); //初始化函数，在定义出进行功能介绍while(1){printf("开始运行:\n");printf("1、输入时域信号取样点数N \n N="); //步骤1：输入时域信号取样点数Nscanf("%d",&N);printf("\n2、输入时域信号N点离散取样值，存于数组xn[N]\n"); //步骤2：依次输入时域信号N点离散取样值，存于数组xn[N]printf(" 选项1：直接输入离散取样值\n 选项2：输入正弦谐波分量信息，让计算机进行取样\n 选择（1/2）");scanf("%d",&i);while((i!=1)&&(i!=2)){printf("请重新选择：（1/2）");scanf("%d",&i);}switch(i){case 1:for(i=0;i<N;i++){printf(" xn[%d]=",i);scanf("%lf",&(xn[i]));}break;case 2:timedomainsignalsample(N,xn);break;}printf("\n3、进行DFT变换并显示变换结果\n "); //步骤3：进行DFT变换并显示变换结果DFTfunction(N,xn,XK); //DFT函数，将时域信号采样数组xn[N]进行DFT，在定义处进行功能介绍ComplexnumToXKStruct(N,XK,XK1); //将复数结构体XK转化成复频域信号取样点XK1display(N,XK1); //显示函数，在定义处进行功能介绍printf("\n4、进行FFT变换并显示变换结果\n "); //步骤4：进行FFT变换并显示变换结果switch(N) //根据N的值判定能否进行FFT，仅当N是以2为底的正指数数时才可进行，否则直接跳出{case -1: return;case 0:case 2:case 4:case 8:case 16:case 32:case 64:case 128:{FFTfunction(N,xn,XK); //FFT函数，将时域信号采样数组xn[N]进行FFT，在定义处进行功能介绍ComplexnumToXKStruct(N,XK,XK2); //将复数结构体XK转化成复频域信号取样点XK1display(N,XK2); //显示函数，在定义处进行功能介绍printf(""); //格式控制语句stardivision();printf("\n");stardivision();}break;default:{printf(" 错误：无法进行FFT变换!!\n 原因：时域信号取样点数N不是以2为底的正指数，或者N大于128\n\n");stardivision(); //格式控制语句printf("\n");stardivision();}}}}void stardivision() //格式控制函数：输出一整排星号作为分隔符{printf("******************************************************************** ***********\n");}void initfunction() //初始化函数{stardivision(); //输出一排星号，以下为学生信息printf(" 班级：1106班\n");printf(" 学号：U201111932\n");printf(" 姓名：曾超\n");stardivision();stardivision();//本程序解说语句，程序总共分为4个步骤，然后为重复printf("运行此程序后：\1、输入时域信号取样点数N \n\n \2、依次输入时域信号N点离散取样值，存于数组xn[N]\n\n \3、进行DFT变换并显示变换结果\n\n \4、进行FFT变换并显示变换结果\n\n \5、重复之前步骤\n");stardivision();stardivision();printf("注意事项： 1、欲进行DFT，N必须为正整数；\n\n\2、欲进行FFT变换，N必须是为2为底的正指数数；\n\n\3、欲直接退出，N必须为-1\n"); //注意事项stardivision();stardivision();}/*********************************************时域信号取样函数功能：交互输入时域谐波信号，输出时域取样值输入：取样点数N，取样值存储数组指针xn输出：取样值**********************************************/void timedomainsignalsample(int N,double *xn){/*变量说明：w：基波角频率T:基波周期t：时间变量maxharmanicorder：波形所含的最大谐波次数，必须为奇数例如：对于y=a[1]sin(wt)+a[3]sin(3wt)+a[5]sin(5wt)+……+a[11]sin(11wt)，maxharmanicorder=11a[maxharmanic]：存储谐波分量系数的数组，仅取其奇数项y:t变量的因变量，暂存取样值*/double y=0,a[maxnum],w=0,T=0,t=0;int maxharmanicorder=0,i,j;printf("\n 下面请初始化时域信号\n 表达式举例：y=a[1]sin(wt)+a[3]sin(3wt)+a[5]sin(5wt)……+a[11]sin(11wt)，请依据提示输入\n");printf(" 1、请输入基波角频率w（rad/s）\n w=");scanf("%lf",&w);T=2*PI/w;printf(" 2、请输入最大谐波次数maxharmanicorder,例如上面举例中的最大谐波次数maxharmanicorder=11\n maxharmanicorder=");scanf("%d",&maxharmanicorder);while((maxharmanicorder<=0)||(maxharmanicorder%2)==0){printf(" 错误：最大谐波次数应为正奇数，请重新输入\nmaxharmanicorder=");scanf("%d",&maxharmanicorder);}printf(" 3、请依次输入谐波分量系数\n");for(i=1;i<=maxharmanicorder;i+=2){printf(" %d次谐波分量系数a[%d]=",i,i);scanf("%lf",&(a[i]));}for(j=0;j<N;j++){t=T/N*j;for(i=1;i<=maxharmanicorder;i+=2){y+=a[i]*sin((i)*w*t);}xn[j]=y;}}/****************************************************显示函数输入：时域信号取样点数N，频域信号取样数组指针输出：以两种形式在命令行显示出频域信号取样点的值，分别是“实部+虚部”“绝对值*角度值”****************************************************/void display(int N,struct XKstruct *XK){int i;for(i=0;i<N;i++){printf(" XK[%d] = %f + i(%f)\n",i,XK[i].real,XK[i].image); //以“实部+虚部”形式显示频域信号取样点printf(" XK[%d] =(%f)exp(%fPIi):\n",i,XK[i].absolutevalue,XK[i].radianmeasureangle); //以“绝对值*角度值”形式显示频域信号取样点}/**********************************************************************格式转换函数功能：将复数结构体数组转化成复频域信号取样点结构体数组输入：时域信号取样点数N，复数结构体指针cnum，频域信号取样点指针XK**********************************************************************/void ComplexnumToXKStruct(int N,struct complexnum *cnum,struct XKstruct* XK){int i;for(i=0;i<N;i++){XK[i].real=cnum[i].real;XK[i].image=cnum[i].image;XK[i].absolutevalue=sqrt(XK[i].real*XK[i].real+XK[i].image*XK[i].image);XK[i].phaseangle=atan(XK[i].image/XK[i].real);XK[i].radianmeasureangle=XK[i].phaseangle/PI;}}/****************************************************复数乘法函数输入：两个复数结构体，不分先后返回值：两个复数的乘积的复数结构体****************************************************/struct complexnum complexmul(struct complexnum mul1,struct complexnum mul2){struct complexnum result;result.image=mul1.image*mul2.real+mul1.real*mul2.image;result.real=mul1.real*mul2.real-mul1.image*mul2.image;return result;}/****************************************************************************** ****//*DFT函数输入：时域信号取样点数NDFT，时域信号取样数组指针xnDFT，频域信号取样数组指针XKDFT功能：进行DFT，离散时域信号值存储在xnDFT[NDFT]，离散频域信号值存储在XKDFT[NDFT]*//****************************************************************************** *****/void DFTfunction(int NDFT,double *xnDFT,struct complexnum *XKDFT)int k,n; //辅助变量double *xnDFTtemp=xnDFT; //为了不改变原指针的值，定义了暂时指针struct complexnum *XKDFTtemp=XKDFT;for(k=0;k<NDFT;k++){(*XKDFTtemp).real=0; //初始化为0(*XKDFTtemp).image=0;for(n=0;n<NDFT;n++) //变换公式参见报告DFT定义{(*XKDFTtemp).real+=(*xnDFTtemp)*cos(2*PI*k*n/NDFT);(*XKDFTtemp).image+=-(*xnDFTtemp)*sin(2*PI*k*n/NDFT);xnDFTtemp++;}xnDFTtemp=xnDFT;XKDFTtemp++;}}/****************************************************************************** ****//*FFT函数输入：时域信号取样点数NFFT，时域信号取样数组指针xnFFT，频域信号取样数组指针XKFFT功能：进行DFT，离散时域信号值存储在xn[N]，离散频域信号值存储在XK[N]*//****************************************************************************** *****/void FFTfunction(int NFFT,double *xnFFT,struct complexnum *XKFFT){/*变量说明：coefficient指蝶形结运算系数coquotient指运算系数商，当前系数与之前一个系数的商complextemp为辅助变量，临时存储XKtemp用XKtemp：为不改变XKFFT指针值所设置的替代数组flag1、flag2：倒位序算法的变址标志Ntemp：为不改变NFFT值所设置的替代数i、j、k:辅助变量*/struct complexnum coefficient,coquotient,complextemp,XKtemp[maxnum];int flag2,flag1,Ntemp,level,step,length,lenght1,ip;int i,j,k;for(i=0;i<NFFT;i++){XKtemp[i].real=xnFFT[i];XKtemp[i].image=0;}//变址运算，即把自然顺序变成倒位序flag2=NFFT/2;flag1=NFFT-1;for(i=0,j=0;i<flag1;i++){if(i<j) //如果i<j,即进行变址{complextemp=XKtemp[j];XKtemp[j]=XKtemp[i];XKtemp[i]=complextemp;}k=flag2; //求j的下一个倒位序while(k<=j) //如果k<=j,表示j的最高位为1{j=j-k; //把最高位变成0k=k/2; //k/2，比较次高位，依次类推，逐个比较，直到某个位为0}j=j+k; //把0改为1}//使用蝶形运算完成FFT运算Ntemp=NFFT;for(level=1;(Ntemp=Ntemp/2)!=1;level++); //计算level的值，即计算蝶形总级数level=log（2）Nfor(step=1;step<=level;step++) // 控制蝶形结级数{ //step表示第step级蝶形length=2<<(step-1); //length蝶形结距离，即第m级蝶形的蝶形结相距length点lenght1=length/2; //同一蝶形结中参加运算的两点的距离coefficient.real=1; //coefficient为蝶形结运算系数，初始值为1coefficient.image=0;coquotient.real=cos(PI/lenght1); //coquotient为系数商，即当前系数与前一个系数的商coquotient.image=-sin(PI/lenght1);for(j=0;j<=lenght1-1;j++) //控制计算不同种蝶形结，即计算系数不同的蝶形结{for(i=j;i<=NFFT-1;i=i+length) //控制同一蝶形结运算，即计算系数相同蝶形结{ip=i+lenght1; //i，ip分别表示参加蝶形运算的两个节点complextemp=complexmul(XKtemp[ip],coefficient); //蝶形运算，详见报告中定义XKtemp[ip].real=XKtemp[i].real-complextemp.real;XKtemp[ip].image=XKtemp[i].image-complextemp.image;XKtemp[i].real=XKtemp[i].real+complextemp.real;XKtemp[i].image=XKtemp[i].image+complextemp.image;}coefficient=complexmul(coefficient,coquotient); //改变系数，进行下一个蝶形运算}}for(i=0;i<NFFT;i++) //将XKtemp暂存的频域取样信号转存在XKFFT数组中{XKFFT[i]=XKtemp[i];}（本资料素材和资料部分来自网络，仅供参考。
