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 表示如下信号

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

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

算法

推荐阅读

算法
深入解析Android自定义View面试题

本文探讨了Android Launcher开发中自定义View的重要性，并通过一道经典的面试题，帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识，还提供了实际操作建议。 ... [详细]

蜡笔小新 2024-12-28 11:15:04
算法
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
算法
使用动态规划算法求解0-1背包问题

本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现，详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]

蜡笔小新 2024-12-27 19:17:15
算法
深入理解设计模式与七大原则

本文详细探讨了Java中的24种设计模式及其应用，并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类，帮助开发者更好地理解和应用这些模式，提升代码质量和可维护性。 ... [详细]

蜡笔小新 2024-12-27 19:10:10
算法
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
算法
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
机器学习
深入理解C++中的KMP算法：高效字符串匹配的利器

本文详细介绍C++中实现KMP算法的方法，探讨其在字符串匹配问题上的优势。通过对比暴力匹配（BF）算法，展示KMP算法如何利用前缀表优化匹配过程，显著提升效率。 ... [详细]

蜡笔小新 2024-12-27 14:45:30
算法
LeetCode 991：故障计算器的最优解法

探讨一个显示数字的故障计算器，它支持两种操作：将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]

蜡笔小新 2024-12-27 14:34:44
算法
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
算法
设计一个安全的加密与验证算法

本文探讨如何设计一个安全的加密和验证算法，确保生成的密码具有高随机性和低重复率，并提供相应的验证机制。 ... [详细]

蜡笔小新 2024-12-27 13:49:45
机器学习
深入解析：手把手教你构建决策树算法

本文详细介绍了机器学习中广泛应用的决策树算法，通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字，建议阅读时间5分钟。 ... [详细]

蜡笔小新 2024-12-27 13:44:59
算法
C语言实现小写金额转换为大写金额

在金融和会计领域，准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据，还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法，确保数据的标准化和规范化。 ... [详细]

蜡笔小新 2024-12-27 12:39:06
算法
每日一题：寻找与众不同的数字

在给定的数组中，除了一个数字外，其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如，findUniq([1, 1, 1, 2, 1, 1]) 返回 2，findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]

蜡笔小新 2024-12-27 12:19:16
算法
理解感受野与锚框在目标检测中的应用

本文探讨了卷积神经网络（CNN）中感受野的概念及其与锚框（anchor box）的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小，而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]

蜡笔小新 2024-12-27 12:03:44
算法
网络攻防实战：从HTTP到HTTPS的演变

本文通过一系列日记记录了从发现漏洞到逐步加强安全措施的过程，探讨了如何应对网络攻击并最终实现全面的安全防护。 ... [详细]

蜡笔小新 2024-12-27 11:34:50

是唐雨冰吗

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

Tags | 热门标签

RankList | 热门文章