离散傅里叶变换
离散傅里叶变换(discrete Fourier transform) 傅里叶分析方法是信号分析的最基本方法，傅里叶变换是傅里叶分析的核心，通过它把信号从时间域变换到频率域，进而研究信号的频谱结构和变化规律。
基本定义
离散傅里叶变换（DFT），是傅里叶变换在时域和频域上都呈现离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效计算DFT。
物理意义
（1）物理意义
设x(n)是长度为N的有限长序列，则其傅里叶变换，Z变换与离散傅里叶变换分别用以下三个关系式表示
X(e^jω)= ∑n={0,N-1}x(n) e^j-ωn
X(z)= ∑n={0,N-1}x(n)z^-n
X(k)= ∑n={0,N-1}x(n) e^-j2πkn/N
单位圆上的Z变换就是序列的傅里叶变换
离散傅里叶变换是x(n)的频谱X(ejω)在[0,2π]上的N点等间隔采样，也就是对序列频谱的离散化，这就是DFT的物理意义.
主要性质
1.线性性质
如果X1（n）和X2(N)是两个有限长序列，长度分别为N1和N2，且Y(N)=AX1(N)+BX2(N)
式中A,B为常数，取N=max[N1,N2]，则Y(N）地N点DFT为
Y(K)=DFT[Y(N)]=AX1(K)+BX2(K), 0≤K≤N-1;
2.循环移位特性
设X(N)为有限长序列，长度为N，则X(N)地循环移位定义为
Y(N)=X((N+M))下标nR（N）
式中表明将X(N）以N为周期进行周期拓延得到新序列X'(N)=X((N))下标n，再将X'(N）左移M位，最后取主值序列得到循环移位序列Y(N)
隐含的周期性
DFT的一个重要特点就是隐含的周期性，从表面上看，离散傅里叶变换在时域和频域都是非周期的，有限长的序列，但实质上DFT是从DFS引申出来的，它们的本质是一致的，因此DTS的周期性决定DFT具有隐含的周期性。可以从以下三个不同的角度去理解这种隐含的周期性
(1)从序列DFT与序列FT之间的关系考虑X(k)是对频谱X(ejω)在[0,2π]上的N点等间隔采样，当不限定k的取值范围在[0,N-1]时，那么k的取值就在[0,2π]以外，从而形成了对频谱X(ejω)的等间隔采样。由于X(ejω)是周期的，这种采样就必然形成一个周期序列
(2)从DFT与DFS之间的关系考虑。X(k)= ∑n={0,N-1}x(n) WNexp^nk，当不限定N时，具有周期性
(3)从WN来考虑，当不限定N时，具有周期性
分析方法
在工程实际中经常遇到的模拟信号xn(t),其频谱函数Xn(jΩ)也是连续函数，为了利用DFT对xn(t)进行谱分析，对xn(t)进行时域采样得到x(n)= xn(nT),再对x(n)进行DFT，得到X(k)则是x(n)的傅里叶变换X(ejω)在频率区间[0,2π]上的N点等间隔采样，这里x(n)和X(k)都是有限长序列
然而，傅里叶变换理论证明，时间有限长的信号其频谱是无限宽的，反之，弱信号的频谱有限款的则其持续时间将为无限长，因此，按采样定理采样时，采样序列应为无限长，这不满足DFT的条件。实际中，对于频谱很宽的信号，为防止时域采样后产生‘频谱混叠’，一般用前置滤波器滤除幅度较小的高频成分，使信号的带宽小于折叠频率；同样对于持续时间很长的信号，采样点数太多也会导致存储和计算困难，一般也是截取有限点进行计算。上述可以看出，用DFT对模拟信号进行谱分析，只能是近似的，其近似程度取决于信号带宽、采样频率和截取长度
模拟信号xn(t)的傅里叶变换对为
X(jΩ)={-∞,+∞}x(t)*exp^-jΩt dt
x（t）=1/2π{-∞,+∞} X(JΩ)*e^jΩt dt
用DFT方法计算这对变换对的方法如下：
（a）对xn(t)以T为间隔进行采样，即xn(t)|t=nT= xa(nT)= x(n),由于
t→nT,dt→T, {-∞,+∞}→∑n={-∞,+∞}
因此得到
X(jΩ)≈∑n={-∞,+∞}x(nT)*exp^-jΩnT*T
x（nT）≈1/2π{0, Ωs} X(JΩ)*e^jΩnT Dω
（b）将序列x(n)= xn(t)截断成包含有N个抽样点的有限长序列
X(jΩ)≈T∑n={0,N-1}x(nT)*exp^-jΩnT*T
由于时域抽样，抽样频率为fs=1/T,则频域产生以fs为周期的周期延拓，如果频域是带限信号，则有可能不产生频谱混叠，成为连续周期频谱序列，频谱的周期为fs=1/T
（c）为了数值计算，频域上也要抽样，即在频域的一个周期中取N个样点，fs=NF0,每个样点间隔为F0，频域抽样使频域的积分式变成求和式，而在时域就得到原来已经截断的离散时间序列的周期延拓，时间周期为T0=1/F0。因此有
Ω→kΩ0，dΩ→Ω0，{-∞,+∞} dΩ→∑n={-∞,+∞}Ω0
T0=1/F0=N/fs=NT
Ω0=2ΠF0
Ω0T=Ω0/fs=2π/N
X(jkΩ0)≈T∑n={0,N-1}x(nT)*exp^-jkΩ0nT
判断方法
判断系统是否为最小相位系统的简单方法是：如果两个系统的传递函数分子和分母的最高次数都分别是m，n，则频率ω趋于无穷时，两个系统的对数幅频曲线斜率均为－20（n－m）dB/dec但对数相频曲线却不同：最小相位系统趋于－90°（n－m），而非最小相位系统却不这样。
注意事项
根据采样定理，只有当采样频率大于信号最高频率的两倍时，才能避免频域混叠。实际信号的持续时间是有限的，因而从理论上来说，其频谱宽度是无限的，无论多 大的采样频率也不能满足采样定理。但是超过一定范围的高频分量对信号已没有多大的影响，因而在工程上总是对信号先进性低通滤波
另一方面，DFT得到的频率函数也是离散的，其频域抽样间隔为F0，即频率分辨力。为了对全部信号进行采样，必须是抽样点数N满足条件
N=T0/T=fs/F0
从以上两个公式来看，信号最高频率分量fc和频率分辨力F0有矛盾。若要fc增加，则抽样间隔T就要减小，而FS就要增加，若在抽样点数N不变的情况下，必然是F0增加，分辨力下降。唯一有效的方法是增加记录长度内的点数N，在fc和F0给定的条件下，N必须满足
N\u003e2fc/F0
（2）截断效应
在实际中遇到的序列x(n)，其长度往往是有限长，甚至是无限长，用DFT对其进行谱分析时，必须将其截断为长度为N的有限长序列
Y(n)=x(n).R(n)
根据频率卷积定理
Y(e)=1/2Πx(e)*H(e)
|ω|\u003c2π/N叫做主瓣，其余部分叫做旁瓣
（3）频谱泄露
原序列x(n)的频谱是离散谱线，经截断后使每根谱线都带上一个辛格谱，就好像使谱线向两边延申，通常将这种是遇上的截断导致频谱展宽成为泄露，泄露使得频谱变得模糊，分辨率降低
（4）谱间干扰
因截断使主谱线两边形成许多旁瓣，引起不同分量间的干扰，成为谱间干扰，这不仅影响频谱分辨率，严重时强信号的旁瓣可能湮灭弱信号的主谱线。
截断效应是无法完全消除的，只能根据要求折中选择有关参量。
（5）栅栏效应
N点DFT是在频率区间[0,2π]上对信号的频谱进行N点等间隔采样，得到的是若干个离散点X(k)，且它们之限制为基频F0的整数倍，这部好像在栅栏的一边通过缝隙看另一边的景象，只能在离散点的地方看到真实的景象，其余部分频谱成分被遮拦，所以称为栅栏效应。
减小栅栏效应，可以在时域数据末端增加一些零值点，是一个周期内的点数增加
（6）信号长度的选择
在时域内对信号长度的选择会影响DFT运算的正确性。实际的信号往往是随机的，没有确定的周期，因此在实际中，应经可能估计出几个典型的、带有一定周期性的信号区域进行频谱分析，然后在取其平均值，从而得到合理的结果。
C语言实现代码
int DFT(int dir,int m,double *x1,double *y1)
{
龙姓 i,k;
double arg;
double cosarg,sinarg;
double *x2=NULL,*y2=NULL;
x2=malloc(m*sizeof(double));
y2=malloc(m*sizeof(double));
if(x2==NULL||y2==NULL)回车键(FALSE);
for(i=0;i\u003cm;i++)
{
x2[i]=0;
y2[i]=0;
arg=-dir*2.0*3.141592654*(double)i/(double)m;
for(k=0;k\u003cm;k++)
{
cosarg=cos(k*arg);
sinarg=sin(k*arg);
x2[i]+=(x1[k]*cosarg-y1[k]*sinarg);
y2[i]+=(x1[k]*sinarg+y1[k]*cosarg);
}
}
/*Copythedataback*/
if(dir==1)
{
for(i=0;i\u003cm;i++)
{
x1[i]=x2[i]/(double)m;
y1[i]=y2[i]/(double)m;
}
}
else
{
for(i=0;i\u003cm;i++)
{
x1[i]=x2[i];
y1[i]=y2[i];
}
}
free(x2);
free(y2);
回车键(TRUE);
}
对换实例
变换对
对于N点序列 {x[n ]} 0 ≤ n \u003c N ，它的离散傅里叶变换（DFT）为
其中e 是自然对数的底数，i 是虚数单位。通常以符号F表示这一变换，即
离散傅里叶变换的逆变换（IDFT）为：
可以记为：
实际上，DFT和IDFT变换式中和式前面乘上的归一化系数并不重要。在上面的定义中，DFT和IDFT前的系数分别为1 和1/N。有时会将这两个系数都改成
，这样就有，即DFT成为酉变换。
几何观点
由于周期为N的离散信号构成N维欧几里得空间，定义其上任意两向量x,y内积为：
那么我们有对于 上的一组正交基：
将向量x在此基上进行分解，可以得到：
令，此即为离散傅里叶变换。又，我们有：
此即为离散傅里叶变换的逆变换。
事实上由点积的性质我们有：
特别的令x=y，我们有：
圆周卷积
对于任意N维向量，我们定义 为 中各项向前循环移 位。那么对于N维任意向量 我们定义其圆周卷积为如下向量：
我们容易知道，即圆周卷积可交换。同样圆周卷积可结合即，证明如下：
易知： ，所以此数列第 项为：
同理可证，的第 项为：
显然：
因此，我们有。事实上，对于任意N维向量x，我们有：
因此：
由圆周卷积的结合性我们有：
即有：
因此离散傅里叶变换可将圆周卷积变为乘积运算。
从连续到离散
连续时间信号x(t) 以及它的连续傅里叶变换（CT）?
x
( ω)
都是连续的。由于数字电路只能处理有限长的、离散的信号，因此必须将x 和?
x
数字系统只能处理有限长的信号，为此假设x(t)时限于[0, L]，再通过时域采样将x(t)离散化，就可以得到有限长的离散信号。设采样周期为T，则时域采样点数N=L/T。
x discrete (t) = x (t) N - 1
Σ
n = 0 δ(三硝基甲苯) = N - 1
Σ
n = 0 x (nT) δ(t-nT)
它的傅里叶变换为
?
x
discrete ( ω) = N - 1
Σ
n = 0 x (nT)F δ(t-nT) = 1
––
T N - 1
Σ
n = 0 x (nT)e - i 2 π n ω T
这就是x(t)时域采样的连续傅里叶变换，也就是离散时间傅里叶变换，它在频域依然是连续的。
类似的，频域信号也应当在带限、离散化之后才能由数字电路处理。依据采样定理，时域采样若要能完全重建原信号，频域信号?
x
( ω)
应当带限于(0,1/T)。由于时域信号时限于[0, L]，由采样定理以及时频对偶的关系，频域的采样间隔应为1/L。故，频域采样点数为
1/T
–––––
1/L = N
即频域采样的点数和时域采样同为N，频域采样点为 { ω k = k/NT} 0 ≤ k \u003c N 在DTFT频域上采样：
?
x
[k ] = ?
x
discrete ( ω k ) = 1
––
T N - 1
Σ
n = 0 f[n ]e - i 2 π
– – – – –
N n k
令T=1，将其归一化，就得到前面定义的离散傅里叶变换。因此，DFT就是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果。
DFT与CT
下面考察离散傅里叶变换与连续傅里叶变换的关系。
Fx ( ω) = ?
x
( ω) = 1
––
L ∫ L
0 x (t)e - i ω t dt
其采样为
?
x
( ω k ) = 1
––
L ∫ L
0 x (t)e - i ω k t dt
将这个积分以伯恩哈德·黎曼和的形式近似，有
?
x
( ω k ) ≈ 1
––
L N - 1
Σ
n = 0 x[n ] e - i ω k n T T = 1
––
N ?
x
[k ]
DFT与DTFT
参见离散时间傅里叶变换
离散时间傅里叶变换（DTFT）是在时域上对连续傅里叶变换的采样。DFT则是在频域上对DTFT的均匀采样。离散信号x[n ]（n=0,...,N-1）的DTFT为：
?
x
(e i ω ) = N - 1
Σ
n = 0 x[n ] e - i n ω
对?
x
(e i ω )
在离散的频点{ ω k = k 2 π
–––––
N } 0 ≤ k \u003c N
上采样
?
x
[k ] = ?
x
(e i ω k ) = N - 1
Σ
n = 0 x[n ]e - i 2 π
– – – – –
N k n k = 0, …,N-1
即为x 的DFT。由于DTFT在频域是周期的，所以在DTFT频域上的均匀采样也应是周期的。?
x
[k ]
实际上是这个周期序列的主值序列。
栅栏效应
N 点序列的DFT只能在有限的N个频点上观察频谱，这相当于从栅栏的缝隙中观察景色，对于了解信号在整个频域上的特性是不够的。为了观察到其他频率的信息，需要对原信号x[n]做一些处理，以便在不同的频点上采样。
将原来在DTFT频域上的采样点数增加到M 点，这样采样点位置变为{ ω ' k = e i k 2 π
– – – – –
M } 0 ≤ k \u003c M
。则对应的DFT成为
?
x
'[k ] = ?
x
(e ik ω ' k ) = N - 1
Σ
n = 0 x[n ]e - i 2 π
– – – – –
M k n
若在序列x[n] 之后补上M-N个零，设为x'[n]，则上式变为
?
x
'[k ] = M - 1
Σ
n = 0 x '[n ]e - i 2 π
– – – – –
M k n = Fx '
因此将x[n]补零再做DFT就可以得到x[n]的DTFT在其他频率上的值，相当于移动了栅栏，因而能够从其他位置进行观察。
频谱分辨率
N 点DFT的频谱分辨率是2 π/N。一节指出可以通过补零观察到更多的频点，但是这并不意味着补零能够提高真正的频谱分辨率。这是因为x[n] 实际上是x(t) 采样的主值序列，而将x[n]补零得到的x'[n]周期延拓之后与原来的序列并不相同，也不是x(t) 的采样。因此?
x
'
与?
x
是不同离散信号的频谱。对于补零至M点的x'的DFT，只能说它的分辨率2 π/M仅具有计算上的意义，?
x
'
并不是真正的、物理意义上的频谱。频谱分辨率的提高只能通过提高采样频率实现。
计算机代码
参考资料
离散傅里叶变换.blog.csdn.net.2016-10-14