dft计算傅里叶级数系数_傅里叶变换（一）傅里叶级数

作者：是唐雨冰吗 | 来源：互联网 | 2023-02-01 11:21

开的这个坑大概就是写写从另一个视角来看快速离散傅里叶变换FFT。oi当中常见的FFT的推导方法是从多项式乘法出发，作为多项式乘法的优化算法出现，关于多项

开的这个坑大概就是写写从另一个视角来看快速离散傅里叶变换FFT。oi当中常见的FFT的推导方法是从多项式乘法出发，作为多项式乘法的优化算法出现，关于多项式的相关理论详见Miskcoo大佬的blog从多项式乘法到快速傅里叶变换 - Miskcoo&＃39;s Space，写的十分详细。

在这个专题下，将会依次讲解傅里叶级数FS，傅里叶变换FT，离散时间傅里叶变换DTFT，离散傅里叶变换DFT。主要是参考wys在WC2018上讲课的课件。

首先在这篇文章中介绍傅里叶级数的相关内容。傅里叶级数作为一种周期函数的无穷级数展开，它将周期函数表示为正弦函数和余弦函数构成的级数。正如泰勒级数将连续且在

equation?tex=x_0 处任意阶可导的函数表示为

$equation?tex=f%28x%29%3D%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%7B%5Cfrac%7Bf%5E%7B%28n%29%7D%28x_0%29%7D%7Bn%21%7D%28x-x_0%29%5En%7D$ 这样由幂函数构成的级数一样，傅里叶级数将周期函数表示为

$equation?tex=f%28t%29%3D%5Cfrac%7Ba_0%7D%7B2%7D%2B%5Csum_%7Bn%3D1%7D%5E%7B%5Cinfty%7D%28a_n+%5Cmathrm%7Bcos%7Dn+%5Comega+t%2Bb_n+%5Cmathrm%7Bsin%7Dn+%5Comega+t%29$ ，其中角频率

$equation?tex=%5Comega%3D%5Cfrac%7B2%5Cpi%7D%7BT%7D$ ，

equation?tex=T 为

equation?tex=f%28t%29 的周期。对于周期函数，可以很容易地联想到最典型的正余弦函数，而且它们的周期大小是十分易于调整的，这也就启发我们去使用它们来表示各类周期函数。

一、正交性

傅里叶级数的基础是三角函数系

equation?tex=1%2C%5Cmathrm%7Bsin%7Dx%2C%5Cmathrm%7Bcos%7Dx%2C%5Cmathrm%7Bsin%7D2x%2C%5Cmathrm%7Bcos%7D2x%2C...%2C%5Cmathrm%7Bsin%7Dnx%2C%5Cmathrm%7Bcos%7Dnx 的正交性。正交是对于线性无关的抽象概念，类比向量正交即为内积等于零的概念，函数的正交同样采用内积等于零来判断。

现定义两个实函数

equation?tex=f%28x%29%2Cg%28x%29 的内积。若

equation?tex=f%28x%29%2Cg%28x%29 在闭区间

equation?tex=%5Ba%2Cb%5D 上可积且平方可积，则它们的内积

equation?tex=%3Cf%2Cg%3E%3D%5Cint_%7Ba%7D%5E%7Bb%7Df%28x%29g%28x%29%5Cmathrm%7Bd%7Dx 。

在

equation?tex=%5B0%2C2%5Cpi%5D 上，三角函数系是两两正交的，它们满足如下性质，

equation?tex=%281%29%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bsin%7Dnx%5Cmathrm%7Bd%7Dx%3D0%28n%5Cin+%5Cmathbb%7BN%5E%2A%7D%29

equation?tex=%282%29%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bcos%7Dnx%5Cmathrm%7Bd%7Dx%3D0%28n%5Cin+%5Cmathbb%7BN%5E%2A%7D%29

equation?tex=%283%29%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bsin%7Dnx%5Cmathrm%7Bcos%7Dmx%5Cmathrm%7Bd%7Dx%3D0%28n%5Cne+m%2Cn%5Cin+%5Cmathbb%7BN%5E%2A%7D%2Cm%5Cin+%5Cmathbb%7BN%5E%2A%7D%29

equation?tex=%284%29%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bsin%7Dnx%5Cmathrm%7Bsin%7Dmx%5Cmathrm%7Bd%7Dx%3D0%28n%5Cne+m%2Cn%5Cin+%5Cmathbb%7BN%5E%2A%7D%2Cm%5Cin+%5Cmathbb%7BN%5E%2A%7D%29

equation?tex=%285%29%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bcos%7Dnx%5Cmathrm%7Bcos%7Dmx%5Cmathrm%7Bd%7Dx%3D0%28n%5Cne+m%2Cn%5Cin+%5Cmathbb%7BN%5E%2A%7D%2Cm%5Cin+%5Cmathbb%7BN%5E%2A%7D%29

前两个式子显然成立，后三个式子的推导主要是利用积化和差公式，在这里给出最后一个式子的推导过程。

$equation?tex=%5Cbegin%7Balign%7D+%26%5Cquad%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cmathrm%7Bcos%7Dnx%5Cmathrm%7Bcos%7Dmx%5Cmathrm%7Bd%7Dx+%5C%5C+%26%3D+%5Cint_%7B0%7D%5E%7B2%5Cpi%7D%5Cfrac%7B%5Cmathrm%7Bcos%7D%28n%2Bm%29x%2B%5Cmathrm%7Bcos%7D%28n-m%29x%7D%7B2%7D%5Cmathrm%7Bd%7Dx%5C%5C+%26%3D%5Cfrac%7B1%7D%7B2%7D%5B%5Cfrac%7B%5Cmathrm%7Bsin%7D%28n%2Bm%29x%7D%7Bn%2Bm%7D%2B%5Cfrac%7B%5Cmathrm%7Bsin%7D%28n-m%29x%7D%7Bn-m%7D%5D%5E%7B2%5Cpi%7D_%7B0%7D%5C%5C+%26%3D0+%5Cend%7Balign%7D$

由此可以得到三角函数系

equation?tex=1%2C%5Cmathrm%7Bsin%7D%5Comega+x%2C%5Cmathrm%7Bcos%7D%5Comega+x%2C%5Cmathrm%7Bsin%7D2%5Comega+x%2C%5Cmathrm%7Bcos%7D2%5Comega+x%2C...%2C%5Cmathrm%7Bsin%7Dn%5Comega+x%2C%5Cmathrm%7Bcos%7Dn%5Comega+x 在

equation?tex=%5B0%2CT%5D 上同样正交。

二、展开为傅里叶级数

傅里叶级数表示为

$equation?tex=f%28t%29%3D%5Cfrac%7Ba_0%7D%7B2%7D%2B%5Csum_%7Bn%3D1%7D%5E%7B%5Cinfty%7D%28a_n+%5Cmathrm%7Bcos%7Dn+%5Comega+t%2Bb_n+%5Cmathrm%7Bsin%7Dn+%5Comega+t%29$ ，其中需要求出的是展开后的系数

equation?tex=a_n%2Cb_n 。

首先考虑最为特殊的

equation?tex=a_0 ，对上式两侧同时从

equation?tex=0 到

equation?tex=T 积分，可以由三角函数系的正交性发现求和号内的项均为0，

因而得到

$equation?tex=%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bd%7Dt%3D%5Cint_%7B0%7D%5E%7BT%7D%5Cfrac%7Ba_0%7D%7B2%7D%5Cmathrm%7Bd%7Dt$ ，

求出

$equation?tex=a_0%3D%5Cfrac%7B2%7D%7BT%7D%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bd%7Dt$ 。

然后要求的是除

equation?tex=a_0 外的其余系数

equation?tex=a_n%2Cb_n 。先求

equation?tex=a_n ，在等号两侧同乘

equation?tex=%5Cmathrm%7Bcos%7Dn%5Comega+t ，再同时从

equation?tex=0 到

equation?tex=T 积分，同样是由三角函数的正交性，可以得到等号右侧除了

equation?tex=%5Cint_%7B0%7D%5E%7BT%7Da_n%5Cmathrm%7Bcos%5E2%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt 不为0外，其余项皆等于0。

于是便有

equation?tex=%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bcos%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt%3D%5Cint_%7B0%7D%5E%7BT%7Da_n%5Cmathrm%7Bcos%5E2%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt ，

计算得

$equation?tex=a_n%3D%5Cfrac%7B2%7D%7BT%7D%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bcos%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt$ 。

对于

equation?tex=b_n 也是采取类似的方法，得

$equation?tex=b_n%3D%5Cfrac%7B2%7D%7BT%7D%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bsin%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt$ 。

equation?tex=a_0 同样满足

equation?tex=a_n 的等式，这便是傅里叶级数当中写成

$equation?tex=%5Cfrac%7Ba_0%7D%7B2%7D$ 而非

equation?tex=a_0 的目的所在。因而可以将所有情况综合起来写为

$equation?tex=a_n%3D%5Cfrac%7B2%7D%7BT%7D%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bcos%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt%28n%5Cin%5Cmathbb%7BN%7D%29$ ，

$equation?tex=b_n%3D%5Cfrac%7B2%7D%7BT%7D%5Cint_%7B0%7D%5E%7BT%7Df%28t%29%5Cmathrm%7Bsin%7Dn%5Comega+t%5Cmathrm%7Bd%7Dt%28n%5Cin%5Cmathbb%7BN%5E%2A%7D%29$ 。

三、傅里叶级数的收敛性

与其它的级数展开相同，傅里叶级数同样需要判断收敛性，若级数不收敛于

equation?tex=f%28t%29 ，则不能在两者之间画等号。关于傅里叶级数的收敛性目前没有它的充分必要条件，只有一些可以用来判断收敛的充分不必要条件。其中最常用的为狄利克雷条件对于一个周期为

equation?tex=2%5Cpi 的函数

equation?tex=f%28x%29 ，如果它满足：

(1)在一个周期内连续或只有有限个第一类间断点；

(2)在一个周期内只有有限个极值点。

那么

equation?tex=f%28x%29 的傅里叶级数收敛于

$equation?tex=%5Cfrac%7Bf%28x%2B0%29%2Bf%28x-0%29%7D%7B2%7D$ 。

狄利克雷条件只是傅里叶级数收敛的充分条件，而非必要条件，级数收敛不代表该条件成立。

由以上推导，我们便可以写出一个周期函数的傅里叶级数。

例如周期为

equation?tex=2%5Cpi 的函数

equation?tex=f%28x%29 ，在

equation?tex=%28-%5Cpi%2C%5Cpi%5D 上

equation?tex=f%28x%29%3Dx ，求

equation?tex=f%28x%29 的傅里叶级数。

$equation?tex=a_n%3D%5Cfrac%7B1%7D%7B%5Cpi%7D%5Cint_%7B-%5Cpi%7D%5E%7B%5Cpi%7Dx%5Cmathrm%7Bcos%7Dnx%5Cmathrm%7Bd%7Dx%3D0$

$equation?tex=b_n%3D%5Cfrac%7B1%7D%7B%5Cpi%7D%5Cint_%7B-%5Cpi%7D%5E%7B%5Cpi%7Dx%5Cmathrm%7Bsin%7Dnx%5Cmathrm%7Bd%7Dx%3D%28-1%29%5E%7Bn%2B1%7D%5Cfrac%7B2%7D%7Bn%7D$

狄利克雷条件显然成立，所以

$equation?tex=f%28x%29%3D%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D1%7D%28-1%29%5E%7Bn%2B1%7D%5Cfrac%7B2%7D%7Bn%7D%5Cmathrm%7Bsin%7Dnx$ 。

四、傅里叶级数的指数形式

通过观察傅里叶级数的形式，不难发现它的每一项与欧拉公式的形式十分相似，可以通过代数变形来使用复指数表示傅里叶级数。

令

equation?tex=i 表示虚数单位，傅里叶级数的指数形式为

equation?tex=f%28t%29%3D%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D-%5Cinfty%7Dc_ne%5E%7Bin%5Comega+t%7D

其中

$equation?tex=c_n%3D%5Cfrac%7B1%7D%7BT%7D%5Cint%5E%7BT%7D_%7B0%7Df%28t%29e%5E%7B-in%5Comega+t%7D%5Cmathrm%7Bd%7Dt$

指数形式与三角形式是相等的，推导如下

$equation?tex=%5Cbegin%7Balign%7D+%26%5Cquad%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D-%5Cinfty%7Dc_ne%5E%7Bin%5Comega+t%7D+%5C%5C+%26%3Dc_0%2B%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D1%7D%28c_ne%5E%7Bin%5Comega+t%7D%2Bc_%7B-n%7De%5E%7B-in%5Comega+t%7D%EF%BC%89+%5C%5C+%26%3Dc_0%2B%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D1%7D%5B%28c_n%2Bc_%7B-n%7D%29%5Cmathrm%7Bcos%7Dn%5Comega+t%2Bi%28c_n-c_%7B-n%7D%29%5Cmathrm%7Bsin%7Dn%5Comega+t%5D+%5C%5C+%26%3D%5Cfrac%7Ba_0%7D%7B2%7D%2B%5Csum_%7Bn%3D1%7D%5E%7B%5Cinfty%7D%28a_n+%5Cmathrm%7Bcos%7Dn+%5Comega+t%2Bb_n+%5Cmathrm%7Bsin%7Dn+%5Comega+t%29+%5Cend%7Balign%7D$

五、傅里叶级数的几何意义

关于傅里叶级数的几何意义，可以类比向量基底的概念。在欧几里得空间当中，可以通过选取一组正交基，使得空间内的所有向量都可以由这组正交基线性表出。

傅里叶级数是利用三角函数系的正交性，通过这样一组正交基张成了函数空间，将这个函数空间当中的函数全部表示为三角函数的线性组合。

考虑傅里叶级数的系数

equation?tex=a_n%2Cb_n ，令

equation?tex=g%28x%29%3D%5Cmathrm%7Bcos%7Dn%5Comega+t ，

equation?tex=h%28x%29%3D%5Cmathrm%7Bsin%7Dn%5Comega+t ，则系数可以写作

$equation?tex=a_n%3D%5Cfrac%7B2%7D%7BT%7D%3Cf%2Cg%3E$ ，

$equation?tex=b_n%3D%5Cfrac%7B2%7D%7BT%7D%3Cf%2Ch%3E$ 。正如向量空间当中基底分解的系数为

$equation?tex=%5Cfrac%7B1%7D%7B%7C%5Cvec%7Bx%7D%7C%7D%3C%5Cvec%7Bx%7D%2C%5Cvec%7Be%7D%3E$ ，其中

equation?tex=%5Cvec%7Be%7D 为基向量，傅里叶级数所做的就是将函数

equation?tex=f%28t%29 投影到三角函数系这样一组正交基上，通过这组基线性表出

equation?tex=f%28t%29 。

六、傅里叶级数的物理意义

如果将

equation?tex=f%28t%29 看作是一个周期信号，则傅里叶级数将

equation?tex=f%28t%29 分解到各个频率的正余弦波之上。

例如

equation?tex=f%28t%29 表示如下信号

傅里叶级数将其分解为以下四种信号

傅里叶级数的局限性在于其只适用于周期函数，对于非周期函数我们需要更为强大的工具，通过对傅里叶级数的推广将会得到适用范围更加广泛的傅里叶变换。

算法

推荐阅读

人工智能
智能网页分类：识别详情页与列表页

本文探讨如何利用人工智能算法自动区分网页是详情页还是列表页，介绍具体的实现思路和技术细节。 ... [详细]

蜡笔小新 2024-12-26 16:00:58
算法
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
算法
图数据库中的知识表示与推理机制

本文探讨了图数据库及其技术生态系统在知识表示和推理问题上的应用。通过理解图数据结构，尤其是属性图的特性，可以为复杂的数据关系提供高效且优雅的解决方案。我们将详细介绍属性图的基本概念、对象建模、概念建模以及自动推理的过程，并结合实际代码示例进行说明。 ... [详细]

蜡笔小新 2024-12-26 12:11:47
算法
获取计算机硬盘序列号的方法与实现

本文介绍了如何通过编程方法获取计算机硬盘的唯一标识符（序列号），并提供了详细的代码示例和解释。此外，还涵盖了如何使用这些信息进行身份验证或注册保护。 ... [详细]

蜡笔小新 2024-12-26 11:22:11
算法
React Hook 基础：深入理解 useState 和 useEffect

本文详细介绍了 React 中的两个重要 Hook 函数：useState 和 useEffect。通过具体示例，解释了如何使用它们来管理组件状态和处理副作用。 ... [详细]

蜡笔小新 2024-12-26 11:09:53
算法
libsodium 1.0.15 发布：引入重大不兼容更新

最新发布的 libsodium 1.0.15 版本带来了若干不兼容的变更，其中包括默认密码散列算法的更改和其他重要调整。 ... [详细]

蜡笔小新 2024-12-26 11:03:58
算法
涡喷发动机动平衡技术解析

本文总结了涡喷发动机动平衡的几种有效方法，探讨了不同传感器和软件工具的应用，旨在帮助爱好者和工程师更好地理解和实现动平衡调整，确保发动机高效稳定运行。 ... [详细]

蜡笔小新 2024-12-26 10:44:53
算法
汇编语言等号伪指令解析：探究其陡峭的学习曲线

汇编语言以其独特的特性和复杂的语法结构，一直被认为是编程领域中学习难度较高的语言之一。本文将探讨汇编语言中的等号伪指令及其对初学者带来的挑战，并结合社区反馈分析其学习曲线。 ... [详细]

蜡笔小新 2024-12-26 10:34:21
算法
离散型随机变量的典型分布：超几何、几何、二项及泊松分布

本文探讨了几种常见的离散型随机变量分布，包括超几何分布、几何分布、二项分布及其衍生的负二项分布和泊松分布。通过具体的模型和推导过程，详细介绍了这些分布的概率质量函数、期望和方差等关键特征。 ... [详细]

蜡笔小新 2024-12-25 21:29:59
算法
探索1000以内的完美数：因数和等于自身

本文探讨了如何在1000以内找到所有完美数，即一个数的因数（不包括自身）之和等于该数本身。例如，6是一个完美数，因为1 + 2 + 3 = 6。通过编程实现这一过程，可以更好地理解完美数的特性。 ... [详细]

蜡笔小新 2024-12-25 19:21:06
算法
深入理解Java中的Collection接口与Collections工具类

本文详细解析了Java中Collection接口和Collections工具类的区别与联系，帮助开发者更好地理解和使用这两个核心组件。 ... [详细]

蜡笔小新 2024-12-25 19:00:15
算法
对MariaDB未来发展的思考与担忧

本文探讨了MariaDB在当前数据库市场中的地位和挑战，分析其可能面临的困境，并提出了对未来发展的几点看法。 ... [详细]

蜡笔小新 2024-12-25 18:20:32
算法
DLP数据泄露检测原理浅析

最近团队在部署DLP，作为一个技术人员对于黑盒看不到的地方还是充满了好奇心。多次咨询乙方人员DLP的算法原理是什么，他们都以商业秘密为由避而不谈，不得已只能自己查资料学习，于是有了下面的浅见。身为甲方，虽然不需要开发DLP产品，但是也有必要弄明白DLP基本的原理。俗话说工欲善其事必先利其器，只有在懂这个工具的原理之后才能更加灵活地使用这个工具，即使出现意外情况也能快速排错，越接近底层，越接近真相。根据DLP的实际用途，本文将DLP检测分为2部分，泄露关键字检测和近似重复文档检测。 ... [详细]

蜡笔小新 2024-12-25 18:19:32
算法
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
机器学习
毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]

蜡笔小新 2024-12-25 17:38:50

是唐雨冰吗

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章