【算法】离散傅里叶变换(DFT)

• 真实的系统是会离散的，时变的。理想者将瞬时态看成时线性的系统，将时变系统分成了不同阶段。离散在围观层面是连续的，但从表层感受时，变化是迅猛的，可以忽略不计变化的过程，因而成为了离散。

一、离散系统

离散控制系统是指在控制系统的一处或数处信 为脉冲序列或数码的系统。如果在系统中使用了采样开关,将连续信 转变为脉冲序列去控制系统,则称此系统为采样控制系统。如果在系统中采用了数字计算机或数字控制器,其信 是以数码形式传递的,则称此系统为数字控制系统。通常把采样控制系统和数字控制系统统称为离散控制系统。离散系统与连续系统相比,既有本质上的不同,又有分析研究方面的相似性。
利用z变换法研究离散系统,可以把连续系统中的许多概念和方法推广应用于离散系统。目前,离散系统的最广泛应用形式是以数字计算机,特别是以微型计算机为控制器的数字控制系统。也就是说,数字控制系统是一种以数字计算机为控制器去控制具有连续工作状态的被控对象的闭环控制系统。因此,数字控制系统包括工作于离散状态下的数字计算机和工作于连续状态下的被控对象两大部分。
图6-1给出了数字控制系统的原理框图。图中,计算机作为校正装置被引进系统,它只能接受时间上离散、数值上被量化的数码信 。而系统的被控量c(t)、给定量r(t)一般在时间上是连续的模拟信 。因此要将这样的信 送入计算机运算,就必须先把偏差量e(1)用采样开关在时间上离散化,再由模数转换器(A/D)将其在每个离散点上进行量化,转换成数码信 ,这两项工作一般都由A/D来完成,然后进人计算机进行数字运算,输出的仍然是时间上离散、数值上量化的数码信 。数码信 不能直接作用于被控对象,因为在两个离散点之间是没有信 的,必须在离散点之间补上输出信 值。一般可采用保持器的办法。最简单的保持器是零阶保持器,它将前一个采样点的值一直保持到后一个采样点出现之前,因此其输出是阶梯状的连续信 (如图6-1中信 u(t)),作用到被控对象上（RS触发器）。数模转换和信 保持都是由数模转换器(D/A)完成的。

三、离散时间傅立叶变换（DTFT）

离散时间傅立叶变换（DTFT）
DTFT计算公式，中的w取值是连续的而且从负无穷大到正无穷大，对于计算机处理是不可能的，需要无限细分无限区间。即使在DTFT小节中用matlab实现计算，也只是将(-pi,pi)区间划分成1600份来逼近DTFT的效果。

三、离散傅里叶变换（DFT）

参考：如何理解离散傅里叶变换DFT—-实验数据说话

例如pwm信 是400kHz，则采样信 至少两倍于信 中最高频率的频率对其进行采样，为800kHz，每秒至少对声音信 进行 800,000 次（800kHz）采样。

参考文献
深入理解离散傅里叶变换(DFT)
但是在工程应用中，得益于数字技术的应用，绝大多数傅里叶变换的应用都是采用离散傅里叶变换（DFT），更确切的说，是它的快速算法FFT。这篇文章再来写写有关离散傅里叶变换的关键点。
这篇属于纯理论推导，全是公式。
参考：离散傅里叶变换（DFT）
这篇实践性比较强，用matlab分析。
DTFT计算公式，中的w取值是连续的而且从负无穷大到正无穷大，对于计算机处理是不可能的，需要无限细分无限区间。即使在DTFT小节中用matlab实现计算，也只是将(-pi,pi)区间划分成1600份来逼近DTFT的效果。
实际上真正用的是DFT，离散傅里叶变换。离散傅里叶变换可以将连续的频谱转化成离散的频谱去计算，这样就易于计算机编程实现傅里叶变换的计算。FFT算法的出现，使得DFT的计算速度更快。
说明：上图结果证明了离散傅里叶变化是对FT变化在区间（0,2*pi）的等间距N点采样

频谱泄漏：相同的信 显示出非常不同的频率响应。但是，这怎么可能们没有改变信 本身，我们只是缩短了每个块的长度。我们在第一张图中看到的峰值的频率分量已被压缩，它们的一些能量已经泄漏到相邻的频率中，这是频谱泄漏。

Hann 窗函数

以 奥地利气象学家Julius Ferdinand von Hann (1839 – 1921) 的名字命名。他发明了一种加权移动平均技术，用于结合邻近地区的气象数据。他的技术后来被Blackman 和 Tukey用来推导 Hann 窗口函数，如下图左图所示。

举个例子，下图就是一个周期为2π的余弦波，即时域每隔2π (相应的索引间隔为8)，他们的值是相等的，这是第一个结论，可以帮组我们进行分组

另一个结论是随着我们增加余弦波的频率，也会出现周期性，注意目前只观察2个点，索引为0和8的位置（间隔为一个周期的点对）。

假定目前有一个样本点数为16的原始离散信 ，如下图绿线，其中蓝线是余弦波，当前的傅里叶级数就是将信 值乘以对应的余弦波值再求累加。

随着频率的增加，0这个点是不变的，而8这个点的值一直在1到-1之间震荡，频谱增加2HZ之后回到原来的值为1。那么对于这个案例，其实就每间隔2hz，就是 0Hz、2Hz、4Hz、6Hz、8Hz 等这些频率中，组合0和8计算DFT的值是相等的。简而言之，每隔 2Hz，无需再次进行乘加运算。这样就可以简单地记住结果并在再次出现相同的点组合时再次使用它。

对于另外一个点组合4和12，也有如上规律，这一次，重复出现的值发生在 0Hz、4Hz、8Hz 等；简而言之，这个组合结果，每隔 4Hz重复一次，那么我们依次类推还有其他这样的两个点组合，正是通过这种重复利用前期的结果，可以节省计算次数，这也就是快速傅立叶变换快速的原因。

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的.

目前为止，已经通过分治算法，成功地将整个计算划分为很小的块，至于每个小块如何快速计算，需要参见下一章内容：蝴蝶操作

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34393 人正在系统学习中