下载文档原格式
⽂中内容均为个⼈理解，如有错误请指出，不胜感激前⾔先解释⼏个⽐较容易混淆的缩写吧FMT 快速莫⽐乌斯变化—>感谢stump提供多项式复数在介绍复数之前，⾸先介绍⼀些可能会⽤到的东西(好像画的不是很标准。
)定义设a ,b 为实数，i 2=−1，形如a +bi 的数叫复数，其中i 被称为虚数单位，复数域是⽬前已知最⼤的域在复平⾯中，x 代表实数，y 轴（除原点外的点）代表虚数，从原点(0,0)到(a ,b )的向量表⽰复数a +bi模长：从原点(0,0)到点(a ,b )的距离，即√a 2+b 2幅⾓：假设以逆时针为正⽅向，从x 轴正半轴到已知向量的转⾓的有向⾓叫做幅⾓运算法则加法：因为在复平⾯中，复数可以被表⽰为向量，因此复数的加法与向量的加法相同，都满⾜平⾏四边形定则（就是上⾯那个）乘法：⼏何定义：复数相乘，模长相乘，幅⾓相加代数定义：(a +bi )∗(c +di )=ac +adi +bci +bdi 2=ac +adi +bci −bd=(ac −bd )+(bc +ad )i单位根下⽂中，默认n 为2的正整数次幂在复平⾯上，以原点为圆⼼，1为半径作圆，所得的圆叫单位圆。
以圆点为起点，圆的n 等分点为终点，做n 个向量，设幅⾓为正且最⼩的向量对应的复数为ωn ，称为n 次单位根。
根据复数乘法的运算法则，其余n −1个复数为ω2n ,ω3n ,…,ωn n 注意ω0n =ωn n =1（对应复平⾯上以x 轴为正⽅向的向量）那么如何计算它们的值呢？这个问题可以由欧拉公式解决ωk n =cos k ∗2πn +i sin k ∗2πn例如图中向量AB 表⽰的复数为8次单位根单位根的幅⾓为周⾓的1n在代数中，若z n =1，我们把z 称为n 次单位根单位根的性质ωk n =cos k2πn +i sin k 2πn （即上⾯的公式）ω2k 2n =ωk n证明：ω2k 2n =cos2k ∗2π2n +i sin2k ∗2π2n =ωk nωk +n2n =−ωk n ωn2n =cos n 2∗2πn +i sin n 2∗2πn =cos π+i sin π=−1ω0n =ωn n =1讲了这么多，貌似跟我们的正题没啥关系啊。
快速傅里叶变换（Fast Fourier Transform，FFT）是一种在数字信号处理和数值分析中广泛应用的算法，它能够高效地计算离散傅里叶变换（Discrete Fourier Transform，DFT），从而在频域中分析信号的频谱特性。
而在matlab中，使用FFT函数可以方便地进行快速傅里叶变换的计算和处理。
1. FFT的基本原理在介绍matlab中的FFT函数之前，我们先来了解一下FFT的基本原理。
FFT算法是一种分治法的思想，在计算傅里叶变换时通过将原始信号分解为奇偶部分，然后递归地进行计算，最终得到傅里叶变换的结果。
这种分治的思想使得FFT算法的计算复杂度降低到了O(n log n)，比直接计算DFT的O(n^2)复杂度要低很多，因此在实际应用中得到了广泛的应用。
2. matlab中的FFT函数在matlab中，可以使用fft函数来进行快速傅里叶变换的计算。
fft函数的基本语法如下：```Y = fft(X)```其中，X表示输入的信号序列，可以是实数或复数序列；Y表示经过FFT变换后得到的频谱结果。
在使用fft函数时，最常见的是对时域信号进行FFT变换，然后得到其频谱特性。
3. FFT在信号处理中的应用FFT算法在信号处理中有着广泛的应用，其中最常见的就是对信号的频谱特性进行分析。
通过对信号进行FFT变换，可以得到其频谱图，从而可以直观地了解信号的频域特性，包括频率成分、幅度特性等。
这对于音频处理、振动分析、通信系统等领域都是非常重要的。
4. FFT在图像处理中的应用除了在信号处理中的应用，FFT算法也在图像处理中有着重要的地位。
在图像处理中，FFT可以用来进行频域滤波，包括低通滤波、高通滤波、带通滤波等操作。
通过FFT变换，我们可以将图像从空域转换到频域，在频域中进行滤波操作，然后再通过逆FFT变换将图像恢复到空域，从而达到图像增强、去噪等效果。
5. FFT在数学建模中的应用除了在信号处理和图像处理中的应用外，FFT算法还在数学建模和仿真计算中有着重要的作用。
fft与傅里叶变换的区别FFT（快速傅里叶变换）与傅里叶变换是数字信号处理领域中常用的两种信号变换方法。
它们在频域分析和信号处理中起着重要作用。
虽然它们都基于傅里叶分析理论，但在实际应用中存在一些区别。
傅里叶变换是一种将信号从时域转换到频域的方法。
它将一个连续时间域的信号分解成一系列正弦和余弦函数的和，得到信号的频谱信息。
傅里叶变换可以用于分析信号的频率成分、频谱特性等，适用于连续时间和连续频率的信号。
而FFT是一种快速计算傅里叶变换的算法。
它通过对离散时间域信号进行有限点数的离散傅里叶变换来实现。
FFT算法利用了信号的周期性和对称性质，将复杂度为O(n^2)的计算简化为O(nlogn)，提高了计算速度。
因此，FFT广泛应用于数字信号处理、频谱分析、图像处理等领域。
傅里叶变换是一种精确的信号分析方法，能够得到信号的精确频谱信息。
但是，傅里叶变换需要进行大量的运算，计算复杂度较高，对于大规模数据处理可能会耗费较长的时间。
而FFT通过采用分治的思想，将大规模的傅里叶变换问题分解为多个小规模的傅里叶变换问题，从而提高了计算效率。
傅里叶变换和FFT在数据处理和实现方式上也存在一些差异。
傅里叶变换通常应用于连续时间和连续频率的信号，需要对信号进行采样和插值处理，以满足变换的要求。
而FFT适用于离散时间和离散频率的信号，可以直接对离散数据进行变换，无需额外处理。
在实际应用中，由于FFT算法的高效性和优势，它被广泛应用于信号处理、图像处理、音频处理等领域。
例如，在音频压缩和解码中，FFT算法可以用于将音频信号从时域转换为频域，提取信号的频谱信息，并进行压缩和解码操作。
而傅里叶变换由于计算复杂度较高，通常在对信号进行精确频谱分析时使用。
FFT是一种快速计算傅里叶变换的算法，相比于傅里叶变换具有计算效率高的优势。
傅里叶变换是一种精确的信号分析方法，适用于连续时间和连续频率的信号。
两者在理论基础和实际应用上有所差异，但都在数字信号处理中起着重要作用。
fft公式
FFT（快速傅里叶变换）是一种高效计算离散傅里叶变换（DFT）的算法。
它可以将时域信号转换为频域信号，并用于许多领域的信号处理和频谱分析。
FFT的公式可以表示为：
X(k)=Σ[x(n)*e^(-i*2π*k*n/N)]
其中，X(k)表示频域中的第k个离散频率，x(n)表示时域信号的第n个采样点，N表示信号的总采样数。
上述公式中的e^(-i*2π*k*n/N)可以理解为复数的旋转因子，它表示了相位和幅度信息。
在计算过程中，使用了蝶形算法（Butterfly Algorithm）来加速计算，通过分
组计算多个蝶形运算，从而减少计算量。
FFT算法的输入是时域信号，输出是频域信号，可以得到信号的幅度谱和相位谱。
这使得FFT成为许多应用中重要的工具，如频谱分析、滤波、信号压缩、图像处理等。
需要注意的是，FFT是DFT的一种高效实现方式，并且要求输入信号的采样数是2的幂次方。
当输入信号不满足这一条件时，可以进行零填充或使用其他插值方法来满足要求。
快速傅⾥叶变换快速傅⾥叶变换快速傅⾥叶变换（FFT ）是根据计算量的最⼩化原理来设计和实施离散傅⾥叶变换(DFT)计算的⽅法。
1965年，库利（T.W.Cooley ）和图基（J.W.tukey ）发表了著名的《计算机计算傅⾥叶级数的⼀种算法》论⽂。
从此掀起了快速傅⾥叶变换计算⽅法研究的热潮。
快速傅⾥叶变换（FFT ）的出现，实现了快速、⾼效的信号分析和信号处理，为离散傅⾥叶变换(DFT)的⼴泛应⽤奠定了基础。
1.1离散傅⾥叶变换(DFT)的计算设x(n)是⼀个长度为M 的有限长序列，则定义x(n)的N 点离散傅⾥叶变换为∑-===10)()]([)(N n kn NW n x n x DFT k X 其中由于计算⼀个X(k)值需要N 次复乘法和(N-1)次复数加法，因⽽计算N 个X(k)值，共需N2次复乘法和N(N-1)次复加法。
每次复乘法包括4次实数乘法和2次实数加法，每次复加法包括2次实数加法，因此计算N 点的DFT 共需要4N2次实数乘法和(2N2+2N ·(N-1))次实数加法。
当N 很⼤时，这是⼀个⾮常⼤的计算量。
1.2减少DFT 计算量的⽅法减少DFT 的计算量的主要途径是利⽤k N W 的性质和计算表达式的组合使⽤，其本质是减少DFT 计算的点数N 以便减少DFT 的计算量。
k N W 的性质：（1）对称性： (2)周期性： (3) 可约性： (4) 特殊点：选择其中⼀个证明N N j k N j N k N j N k N e e e W 222)2(22πππ--+-+==ππj k N j e e --=2k N j e π2--=k N W -=FFT 算法是基于可以将⼀个长度为N 的序列的离散傅⾥叶变换逐次分解为较短的离散傅⾥叶变换来计算这⼀基本原理的。
这⼀原理产⽣了许多不同的算法，但它们在计算速度上均取得了⼤致相当的改善。
0,1,,1k N =-()*nk nk N N W W -=()()nk N n k n N k N N NW W W ++==nk mnk N mN W W =//nk nk m N N mW W =01N W =/21N N W =-(/2)k N k N NW W +=-在这⾥讨论两类基本的FFT 算法。
第四章快速傅立叶变换（FFT）
1. N=16，画出基-2按时间抽取法及按频率抽取法的FFT流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。
分析
①DIF法与DIT法的异同；
不同点：DIT与DIF的基本蝶形图不同，DIF的复数乘法出现在减法之后，DIT的复数乘法出现在加法、减法之前。
相同点：DIT与DIF的运算量是相同的。
②DIF法与DIT法的关系：它们的基本蝶形是互为转置的。
解
（1）按时间抽取，见图P4-3(a)。
（2）按频率抽取，见图P4-3（b）.
2. 研究一个长度为M 点的有限长序列x(n)。
(),01()0,
x n n M x n n ≤≤-⎧=⎨⎩其他 我们希望计算求z 变换1
0()()M n n X z x n z --==∑在单位圆上N 个等间隔点上的抽样，即在2j k N z e π=，k=0,1, ,N-1上的抽样。
试对下列情况，找出只用一个N 点DFT 就能计算
X （z ）N 个抽样的方法，并证明之。
（1）N M ≤ （2）N M >
分析
当时域序列点数为M ，频域抽样点数为N 点时，
①N>M ，将x （n ）从M 到N-1点补零值，然后计算。
②N<M ，可将x （n ）分成以N 点为间隔的许多段（视N, M 具体值而定，最后一段点数不一定正好是N ），这样把计算x （n ）的M 点DFT 就可分解成计算每一段的N 点DFT ，再经化简即可解出。
解
(1)依题意 2210()()M j k j nk N N n X e
x n e ππ--==∑
设(1)l N M lN -≤<，则
222212110(1)()()()()N N M j k j nk j nk j nk N N N N n n N n l N X e x n e
x n e x n e ππππ------===-=+++∑∑∑
222(1)111()[(1)]000()()[(1)]M l N N N j nk j n N k j n l N k N N N n n n x n e
x n N e x n l N e πππ-------+-+-====+++++-∑∑∑ 因为 22()j n lN k j nk N N e
e ππ-+-=
且令 0121()(),
()(),01()[(2)],()[(1)],0(1)1
l l y n x n y n x n N n N y n x n l N y n x n l N n M l N --==+≤≤-=+-=+-≤≤---
所以 221100()[()]N l j k j nk N N m n m X e y n e
ππ---===∑∑
由此可见，对于N M ≤,可先计算1
0()l m m y n -=∑，然后对它求一次N 点DFT ，即
可计算X(z)在单位圆上的N 点抽样。
(2) 若N>M ，可将x （n ）补零到N 点，即
0(),01()0,1x n n M x n M n N ≤≤-⎧=⎨≤≤-⎩
则 22100()(),01N j k j nk N N n X e
x n e k N ππ--==≤≤-∑。
