目录

• 一、前言
• 二、傅里叶变换
  • 1.傅里叶级数
  • 2.傅里叶级数系数求解
    • 2.1.求解方法
    • 2.2.三角函数的正交性
    • 2.3.系数求解过程
    • 2.4.关于傅里叶级数的个人感悟
  • 3.引入复指数
  • 4.总结
• 三、离散傅里叶变换（DFT）
  • 1.离散傅里叶变换的求解
  • 2.C语言实现
  • 3.引入复指数
  • 4.什么是复平面
  • 5.为什么DFT表达式里是负的
  • 6.总结
• 四、快速傅里叶变换（FFT）
• 五、总结

说来惭愧，本科专业是测控技术与仪器，四舍五入也算个电子信息人（虽然我不怎么承认，毕竟本科也没怎么听课，天天在实验室玩单片机，实在是给专业丢人）。

前不久因为工作原因（实际上是因为接别人的锅，别人忙，所以就让我这个菜鸡接人家剩下的继续搞，两个周后出程序）。用户要求输出电压、电流周波数据，说是用于负荷分析。别的我不用关心，我只要能输出周波数据就行。但公司有流程，所有的程序出厂前都需要进行测试、出厂检等等步骤，考虑到测试组能力有限，所以给他们做了一个软件，模拟用户对数据进行处理（实际上就是简单的进行傅里叶变换，得到频谱然后显示，测试组看个幅值就可以了）。但最终软件做完了，测试组说只有138台，他们没时间测。好吧，写一篇博客记录一下整个学习过程。

1.傅里叶级数

最早接触到的傅里叶变换，估计大家都一样，都是从大学高数书上的，泰勒展开、级数后面就是这个玩意。我但是学的书，这章是打※号的，说白了就是不怎么重要，而且讲高数的老师说你们学信息的以后专业课上会详细学到（这句话好熟悉），但是只记得怎么解题，总结来说就是下面的这个公式：

公式1： \(f(t) = A_0 + \sum _{n=1}^{\infty} [A_n \cdot sin(n\omega t + \phi_n)]\)

更多的时候，我们见到的是下面的式子：

公式2： \(f(t) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(\frac{n\pi t}{l}) + b_n \cdot sin(\frac{n\pi t}{l})]\)

令\(\frac{\pi t}{l} = x\)即可得到：

公式3： \(f(t) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

由公式1到公式2的转换，简单证明：

利用公式：\(sin(a+b) = sin(a)cos(b) + cos(a)sin(b)\)

得到：\(A_n \cdot sin(n\omega t + \phi_n) = A_n \cdot sin(\phi _n)\cdot cos(n\omega t) + A_n \cdot cos(\phi _n) \cdot sin(n\omega t)\)

令\(\frac{a_0}{2} = A_0，a_n = A_n \cdot sin(\phi _n)，b_n = A_n \cdot cos(\phi _n)，\omega = \frac{\pi}{l}\)

即可得到：\(f(t) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(\frac{n\pi t}{l}) + b_n \cdot sin(\frac{n\pi t}{l})]\)

令 \(\frac{\pi t}{l} = x\)，得到：\(f(t) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

简单的说，就是任何一个周期信号都可被一系列三角函数表示。（至于为什么，我也不太清楚，暂且当回拿来主义吧，参考知乎大神：傅里叶系列（一）傅里叶级数的推导）

2.傅里叶级数系数求解

对于傅里叶级数，我们要求的就是这些系数：\(a_n、b_n\)

2.1.求解方法

解法也是很简单，利用三角函数的正交性，对公式3两边积分

\(\int_{-\infty}^{+\infty}f(x)\cdot sin(nx)dx = \int_{-\infty}^{+\infty}\{\frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\}\cdot sin(nx)dx\)

\(\int_{-\infty}^{+\infty}f(x)\cdot cos(nx)dx = \int_{-\infty}^{+\infty}\{\frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\}\cdot cos(nx)dx\)

2.2.三角函数的正交性

利用三角函数的正交性：

所谓正交性，书本概念请自行搜索，我只说简单提一句：正交性就是相乘为0

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}sin(nx)\cdot f(kx) dx = 0\)

\(当f(kx) = 0,1,sin(1x),cos(1x),sin(2x),cos(2x),\dots,sin(nx),cos(nx)，且n\neq k\)

\(其中：0=six(0\cdot x)，1=cos(0\cdot x)\)

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}cos(nx)\cdot f(kx) dx = 0\)

\(当f(kx) = 0,1,sin(1x),cos(1x),sin(2x),cos(2x),\dots,sin(nx),cos(nx)，且n\neq k\)

\(其中：0=six(0\cdot x)，1=cos(0\cdot x)\)

即，当\(n = k\)时，\(\int_{-\frac{T}{2}}^{\frac{T}{2}}cos(nx)\cdot f(nx) dx \neq 0\)

关于这个正交性很好证明，积分+倍角变换很容易就出来了，我这里就不去证明了。

2.3.系数求解过程

接下来我主要解释以下如何得到系数：

首先，求\(a_0\)：

\(\int_{-\infty}^{+\infty}f(x)\cdot cos(0)dx = \int_{-\infty}^{+\infty}\{\frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\}\cdot cos(0)dx\)

由于\(f(x)\)本身就是周期的，加上\(cos(nx)\)也是周期的，因此只需要求一个周期内的即可：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(0)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}\{\frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\}\cdot cos(0)dx\)

利用三角函数的正交性，以及\(cos(0)=1\)，得：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot 1dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}\frac{a_0}{2} \cdot 1dx\)

这里的\(T=2\pi\)，然后因为\(\frac{a_0}{2}\)不是被积量，所以替换、系数提出：

\(\int_{-\pi}^{\pi}f(x)\cdot 1dx = \frac{a_0}{2} \cdot \int_{-\pi}^{\pi} 1dx\)

然后就一目了然了：

\(\int_{-\pi}^{\pi} 1dx = 2\pi\)

所以：

\(a_0 = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)dx\)

然后是计算\(a_n\)和\(b_n\)：

同理，只不过带入的是\(n\)：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}\{\frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\}\cdot cos(nx)dx\)

同样利用的三角函数的正交性，得：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}[\frac{a_0}{2} +a_n\cdot cos(nx)]\cdot cos(nx)dx\)

实际上应该这么写：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}[\frac{a_0}{2} \cdot 1+a_n\cdot cos(nx)]\cdot cos(nx)dx\)

发现漏掉了一个正交为0的项：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}\frac{a_0}{2} \cdot [1\cdot cos(nx)]dx = \frac{a_0}{2} \cdot \int_{-\frac{T}{2}}^{\frac{T}{2}}[1\cdot cos(nx)]dx = 0\)

所以，就简化为：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}[a_n\cdot cos(nx)]\cdot cos(nx)dx\)

然后，按照和求\(a_0\)一样的处理：提出\(a_n\)、再积分…

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = a_n\cdot \int_{-\frac{T}{2}}^{\frac{T}{2}}[cos(nx)\cdot cos(nx)]dx\)

利用倍角公式：\(1+cos(2x)=2cos^2(x)\)

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}[cos(nx)\cdot cos(nx)]dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}\{\frac{1}{2}\cdot[1+cos(2nx)]\}dx\)

然后还是利用正交性：\(\int_{-\frac{T}{2}}^{\frac{T}{2}}[ 1 \cdot cos(2nx)]dx = 0\)

啰嗦一句：

\(\int_{-\frac{T}{2}}^{\frac{T}{2}}[ 1 \cdot cos(2nx)]dx = 0\)式中相当于把\(cos(nx)\)倍频了，即一个周期T内塞下了两倍的\(cos(nx)\)信号

因为\(1\cdot cos(nx)\)在一个周期内积分 = 0

所以\(1\cdot cos(2nx)\)在一个周期内积分也 = 0

所以，就剩下了：\(\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx = \int_{-\frac{T}{2}}^{\frac{T}{2}}[\frac{1}{2}\cdot a_n]dx\)

整理得到：\(a_n =\frac{2}{T} \cdot \int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx\)

同样\(T=2\pi\)，所以替换：

\(a_n = \frac{2}{2\pi} \cdot \int_{-\pi}^{\pi}f(x)\cdot cos(nx)dx = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)\cdot cos(nx)dx\)

再把之前算出来的\(a_0\)拿过来：

\(a_0 = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)dx\)

\(a_n = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)\cdot cos(nx)dx\)

其实可以统一用：\(a_n = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)\cdot cos(nx)dx\)表示

同理：\(b_n = \frac{1}{\pi} \cdot \int_{-\pi}^{\pi}f(x)\cdot sin(nx)dx\)

2.4.关于傅里叶级数的个人感悟

但是，很多教材上往往都是令这个等于那个，令那个等于这个，弄得云里雾里，比如前面我列举了：

傅里叶老先生费劲千辛万苦想出来：\(f(x) = A_0 + \sum_{n=1}^{\infty} [A_n \cdot sin(nx + \phi_n)]\)

后来的数学大师为了方便理解，转化出：\(f(x) = \frac{a_0}{2} + \sum_{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

这两个式子我在开篇就写过，就是通过三角变换得到：把表示相位的分量\(\phi _n\)去掉了，转而用两个基本的正交的三角函数——\(cos(x)\)和\(sin(x)\)——表示。

但是，为什么用\(\frac{a_0}{2}\)而不是\(a_0\)？

本身\(a_0\)就是一个待求系数，\(\frac{a_0}{2}\)或者\(a_0\)，你用哪一个都一样啊。

反正我本科学高数的时候，后来学信号与处理的时候，甚至再到后面考研刷数学，我都没有去想过这个。直到工作后重新学这个傅里叶变换，才真正静下心来去思考这个问题。

首先列举两个傅里叶级数的基本公式：

式子1：\(f(x) = a_0 + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

式子2：\(f(x) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

可以看出来，两个式子的区别就是式子1的第一项是\(a_0\)，式子2的第一项是\(\frac{a_0}{2}\)

然后按照前面我们求系数的方式来求解这个\(a_0\)，注意，两个式子都是求\(a_0\)

式子1：\(a_0\cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}dx = \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)dx\)

式子2：\(\frac{a_0}{2}\cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}dx = \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)dx\)

这里就不去对这个周期\(T\)进行处理了，就用\(T\)这个符号来表示：

式子1：\(a_0 = \frac{1}{T}\cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)dx\)

式子2：\(a_0 = \frac{2}{T}\cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)dx\)

然后对比之前求的\(a_n\)：\(a_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx\)

会发现：式子2中那种用\(\frac{a_0}{2}\)表示的系数，求的\(a_0\)可以直接套用\(a_n\)的求解公式求出，得到的这个\(a_0\)并不是傅里叶公式中的系数，你还需要除以2，因为给你的傅里叶表达式是\(f(x) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

总之用\(f(x) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)，你只需要记住两个式子（如果是需要应付考试速成的，请直接用下面的三个公式）：

①：\(f(x) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(nx) + b_n \cdot sin(nx)]\)

②：\(a_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot cos(nx)dx\)

③：\(b_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cdot sin(nx)dx\)

顺便提一嘴，\(a_n\)求解式中分子的\(2\)，来源于倍角公式转换引入的，第一项\(a_0\)没有用这个倍角公式，自然分子没有\(2\)。（纯属个人瞎掰）

3.引入复指数

引入复指数后的推导，在下一章节中详细说明。

4.总结

带公式求解，不是天朝的精髓么？可我们为什么要用公式去学习？公式不是为了方便使用才被创造出来的么？理解了，公式才有价值；懂都不懂，公式有什么用？如果仔细看教材，无论教材好坏都有这个的推导。但实际上，56学时的课、5个学分，有几个会真真正正去讲解、去推导？（本段纯属个人发牢骚，我的文章都是这个风格，多包涵）

上一章介绍了傅里叶级数和傅里叶变换，其实就是利用了一个思想：任何周期函数都可以用正弦函数或者余弦函数的无穷级数来表示。这句话很容易理解，就是证明嘛。用数学公式也是更加简洁：

\(f(t) = \sum _{n=0}^\infty [A_n \cdot cos(n\omega t + \phi _1) ]\)

或者：

\(f(t) = \sum _{n=0}^\infty [B_n \cdot sin(n\omega t + \phi _2) ]\)

可见，我们要求的就是这个\(A_n\)和\(\phi _1\)或者\(B_n\)和\(\phi _2\)

可能有的人会有疑问了？为什么是\(n\omega t\)？

其实什么都行，上一章节再推导傅里叶级数时我时从\(cos(nx)\)开始的，然后不断的替换、替换。$n\omega \(只是表征了\)cos()\(的频率，也就是周期。你要是高兴，你用\)f(t) = \sum _{n=0}^\infty [A_n \cdot cos(狗t + \phi _1) ]$ 都行。

用\(\omega\)，你就可以替换成\(\omega = 2\pi f\)；而这个\(f\)，不就是我们平常说的多少多少赫兹么。同样，你如果不按照这个替换流程，只不过你最终得到的\(f\)可能为\(0.01\)赫兹？\(\sqrt{2}\)赫兹？这谁顶得住？本身我们得到的就是频谱图，画图而已；况且傅里叶变换的思想就是无限的去逼近，能不能逼近是质的问题，有多逼近是量的问题。而且如果你要是突发奇想用\(nE\)来表征，说不定你就能用\(E=mc^2\)来搞事情了。

扯的有点多，接下来该进入正题了。

1.离散傅里叶变换的求解

既然已经知道了傅里叶变换的本质，那么我们不妨就以一个例子来说明：

\(f(t) = \sum _{n=0}^\infty [A_n \cdot cos(n\omega t + \phi _1) ]\)

这个式子很清楚表示了任何一个周期函数\(f(x)\)如何被无穷多个余弦函数逼近的。为了求解相对简单，求解的余弦函数\(cos(n\omega x)\)的频率都是整数（如果你愿意，你可以把\(\sum _{n=0}^\infty\)换成\(\int_{n=0}^\infty\)，因为积分的本质就是累和，只是累和的步进值无穷小；为什么从0开始？因为没有负频率，当然现在还不去牵扯复指数的那一套东西）

然后利用我们上一章节推导的，利用三角函数的正交性，积分求系数

这里我抄过来：

①：\(f(t) = \frac{a_0}{2} + \sum _{n=1}^\infty [a_n \cdot cos(n\omega t) + b_n \cdot sin(n\omega t)]\)

②：\(a_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(t)\cdot cos(n\omega t)dt\)

③：\(b_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(t)\cdot sin(n\omega t)dt\)

因为式子①把\(A_n\cdot cos(n\omega t + \phi _1)\)分解成了一个\(a_n\cdot cos(n\omega t)\)和一个\(b_n\cdot sin(n\omega t)\)

所以求出来的\(a_n\)和\(b_n\)还要转换回去：

\(a_n\cdot cos(n\omega t) + b_n\cdot sin(n \omega t) = \sqrt{a_n^2+b_n^2}\cdot [\frac{a_n}{\sqrt{a_n^2+b_n^2}}\cdot cos(n\omega t) + \frac{b_n}{\sqrt{a_n^2+b_n^2}}\cdot sin(n\omega t)] = \sqrt{a_n^2+b_n^2}\cdot cos(n\omega t + \phi_1)\)

所以最终的系数为：\(\sqrt{a_n^2+b_n^2}\)

相位为：\(\phi_1\)，这个需要大家自己去计算下，我这里就不去计算了

好了现在问题来了，如何求离散变换下的\(a_n\)和\(b_n\)？

下面两个式子是我们已经推导出的连续变换下的\(a_n\)和\(b_n\)：

\(a_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(t)\cdot cos(n\omega t)dt\)

\(b_n = \frac{2}{T} \cdot \int _{-\frac{T}{2}}^{\frac{T}{2}}f(t)\cdot sin(n\omega t)dt\)

那么我们不妨设一个周期中采样了16个离散点，即\(N=16\)

则：

\(a_n = \frac{2}{N} \cdot \sum _{0}^{N-1}f(\frac{t}{N})\cdot cos(n\omega \frac{t}{N})\)

\(b_n = \frac{2}{N} \cdot \sum _{0}^{N-1}f(\frac{t}{N})\cdot sin(n\omega \frac{t}{N})\)

要是觉得这个和一些教材上的不一样，我们再变换一下，用\(\omega = 2\pi f\)替换：

\(a_n = \frac{2}{N} \cdot \sum _{0}^{N-1}f(\frac{t}{N})\cdot cos(2n\pi f\frac{t}{N})\)

\(b_n = \frac{2}{N} \cdot \sum _{0}^{N-1}f(\frac{t}{N})\cdot sin(2n\pi f\frac{t}{N})\)

然后，然后就没了。

2.C语言实现

其实，C语言中实现DFT很简单，就是两层循环：内层循环算这个\(\sum\)得到一个\(a_n\)，外层循环算全部\(N\)个点的\(a_n\)。

#define PI    3.1415926f
#define N    8

//@brief:    离散傅里叶变换DFT
//@param:    *raw_data[in],      原始数据
//@param:    *dft_coeffi[out],   变换后的幅值序列
//@param:    len[in],        数据长度
//@return:    void
//@note:    输入raw_data和输出dft_result长度相同，都为len
//@note:    暂未求相位
//@note:    最高支持N=32768
void dft(double *raw_data, double *dft_coeffi, int len)
{
    double coeffi_cos;
    double coeffi_sin;

    for(short freq=0; freq<N; freq++)
    {
        coeffi_cos = 0;
        coeffi_sin = 0;

        for(short n=0; n<N; n++)
        {
            coeffi_cos += raw_data[n] * cos(2*PI*freq*n/N);
            coeffi_sin += raw_data[n] * sin(2*PI*freq*n/N);
        }

        dft_coeffi[freq]  = sqrt(coeffi_cos*coeffi_cos + coeffi_sin*coeffi_sin); //可优化，sin(0)=0
        dft_coeffi[freq] *= (freq == 0) ? (1.0/N) : (2.0/N);
    }
}

但是很多时候我们在网上找到的代码貌似不是这样，很多都是告诉我们：

1. 先定义一个新的类型：复数类型，就是a+bi或者a+bj
2. 然后重载一下+和*这两个运算符
3. 然后就巴拉巴拉运算

实际上，这只用了一些高级语言（如C++）的运算符重载技术，以及引入了复指数、复平面的概念（如果你有留意到，同时这些代码如果写注释的话，一般是这样子的：\(a_ncos(2\pi f\frac{t}{N}) - j\cdot b_n(2\pi f\frac{t}{N})\)，虚部带个负号）

但本质上，就是我用C语言中写的那个处理流程，随着\(N\)增大，时间复杂度可想而知。但是，这个就是离散傅里叶最原始的样子，暴力求解。时间复杂度很好计算，两层循环，\(O(n^2)\)。如果还要去区分什么加法、乘法次数，数两次循环的+和*个数就行了，但是有一点得提醒一下：你得先理解大O怎么求时间复杂度的；以及实际代码需不需要先被优化，然后再去求。

下面，来解释一下为什么：\(a_ncos(2\pi f\frac{t}{N}) - j\cdot b_n(2\pi f\frac{t}{N})\)，虚部带个负号。

3.引入复指数

最常见的离散傅里叶变换的表达式

\(X[k] = \sum _{n=0}^{N-1} x(n)\cdot e^{-j2\pi kf\frac{n}{N}}\)

如果你有兴趣，直接用欧拉公式\(e^{jx} = cos(x) + jsin(x)\)替换展开就可以了

\(X[k] = \sum _{n=0}^{N-1} x(n)\cdot [cos(-2\pi k \frac{n}{N}) + jsin(-2\pi k \frac{n}{N})]\)

利用\(cos(x)\)和\(sin(x)\)的奇偶性

\(X[k] = \sum _{n=0}^{N-1} x(n)\cdot [cos(2\pi k \frac{n}{N}) - jsin(2\pi k \frac{n}{N})]\)

然后再告诉你，这个\(j\)是一个表示旋转的标识，和\(-1\)一样。在复平面里，\(j\)标识逆时针转\(90°\)；\(-1\)就表示逆时针转\(180°\)，因为\(-1 = j \times j\)。总之\(j\)在表达式中的存在只是为了告诉我们：我后面的数据是被旋转了的，你要注意。所以我们在处理时没必要管这个\(j\)。

再因为最后我们求的\(X[k]=\sqrt{a_k^2 + b_k^2}\)，平方和求开根号，所以\(X[k]=\sqrt{a_k^2 + (-b_k)^2} = \sqrt{a_k^2 + b_k^2}\)

所以，可以得出一个结论：DFT在引入复指数、复平面概念后去求\(cos(x)\)和\(sin(x)\)的系数，所以用绝对值就可以了，系数的正负是无所谓的。

4.什么是复平面

关于复平面，我直接引用一位大神slowmovingsnail的CSDN文章

傅里叶分析的方方面面：复正弦、负频率

这张图，如果幸运的话，我可能还会讲到，不过现在只是用它来说明一个问题：通过欧拉公式的替换，把\(cos(x)\)或者\(sin(x)\)用两个复数来表示。

即：

\(cos(\theta) = \frac{1}{2} \cdot [e^{j\theta} + e^{-j\theta}]\)

\(sin(\theta) = \frac{1}{2j} \cdot [e^{j\theta} - e^{-j\theta}]\)

而我们已经知道，任何周期函数都可以展开成：

这里我就不单独写\(a_0\)了，反正既然能看到这，想必也都知道为什么了

\(f(t) = \int _{n=0}^\infty [a_n \cdot cos(n\omega t) + b_n \cdot sin(n\omega t)]\)

带入替换：

\(f(t) = \int _{n=0}^\infty [a_n \cdot \frac{1}{2} \cdot (e^{jn\omega t} + e^{-jn\omega t}) + b_n \cdot \frac{1}{2j} \cdot (e^{jn\omega t} - e^{-jn\omega t})]\)

整理：

\(f(t) = \int _{n=0}^\infty [a_n \cdot \frac{1}{2} \cdot (e^{jn\omega t} + e^{-jn\omega t}) + b_n \cdot \frac{1}{2j} \cdot (e^{jn\omega t} - e^{-jn\omega t})]\)

说实话，我也很难看出还能怎么往下做。但我只能说我们的目的是尽可能转化成只有一个\(e^{j\theta}\)的形式，所以，凑就完了。

\(f(t) = \int _{n=0}^\infty [\frac{a_n}{2} \cdot (e^{jn\omega t} + e^{-jn\omega t}) + \frac{b_n }{2}\cdot (-j) \cdot (e^{jn\omega t} - e^{-jn\omega t})]\)

上式的处理中，利用了：\(1 = j^4 = j^2 \cdot j \cdot j = (-j) \cdot j\)

所以，再整理：

\(f(t) = \int _{n=0}^\infty [\frac{(a_n - jb_n)}{2} \cdot e^{jn\omega t} + \frac{(a_n + jb_n)}{2} \cdot e^{-jn\omega t}]\)

令：\(c_{n1} = \frac{(a_n - jb_n)}{2}\)，\(c_{n2} = \frac{(a_n + jb_n)}{2}\)

可以发现，\(c_{n1}\)和\(c_{n2}\)是共轭的（即模相等，虚部相反）

\(f(t) = \int _{n=0}^\infty [c_{n1} \cdot e^{jn\omega t} + c_{n2} \cdot e^{-jn\omega t}] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{jn\omega t}\) （注意，这里先这么写，这里不是最终的！）

上一步的推导好像理解起来没问题，可又好像有问题。上一步还是\(a_n - jb_n\)，下一步直接\(|d_n|\)了，\(j\)直接没了？

其实，这里借助了一个概念：旋转因子

旋转因子就是\(e^{jn\omega t}\)和\(e^{-jn\omega t}\)，前者表示逆时针转\(n\omega t\)，后者表示顺时针转\(n\omega t\)

再加上：\(c_{n1} = \frac{(a_n - jb_n)}{2}\)，\(c_{n2} = \frac{(a_n + jb_n)}{2}\)是共轭的，也就是在复平面内，\(c_{n1}\)和\(c_{n2}\)这两个向量关于横轴（也就是实轴）对称（我们这里称\(c_{n1}\)和\(c_{n2}\)为复平面里的两个向量，绕原点旋转的向量）。再加上旋转因子\(e^{jn\omega t}\)和\(e^{-jn\omega t}\)分别表示向相反方向旋转相同的角度，所以\(c_{n1} \cdot e^{jn\omega t}\)和\(c_{n2} \cdot e^{-jn\omega t}\)也是关于横轴（实轴）对称。

然后我们把\(c_{n1} \cdot e^{jn\omega t}\)和\(c_{n2} \cdot e^{-jn\omega t}\)这两个向量的模长拿出来，就是\(|d_n|\)，其中\(|d_n| = |c_{n1}| = |c_{n2}|\)。但是这样就丢失了\(c_{n1}\)和\(c_{n2}\)本身的角度信息，所以我们就需要把丢失的角度补到后面，即：\(|d_n|e^{j(n\omega t + \theta _{c_n})}\)和\(|d_n|e^{-j(n\omega t + \theta _{c_n})}\)

所以，我们把前面挖的坑填上：

\(f(t) = \int _{n=0}^\infty [c_{n1} \cdot e^{jn\omega t} + c_{n2} \cdot e^{-jn\omega t}] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{j(n\omega t + \theta _{c_n})}\)

当然，也可以从图形结合来理解：

\(\frac{1}{2}a_n + j\frac{1}{2}b_n => |c_n|e^{j\theta _{c_n}}\)，注意我这里用的不是一个等于号，我只是想表达一个意思：\(\frac{1}{2}a_n + j\frac{1}{2}b_n\)可以在复平面中找到一个绕原点旋转\(\theta _{c_n}\)的向量来对应，这个向量的长度为\(|c_n|\)。借助图形可以很容易分析出来，只是我写这些公式太麻烦了。

好了，通过以上的分析，我们就得到了引入复指数、复平面后的展开式：

\(f(t) = \int _{-\infty}^{+\infty} |d_n| \cdot e^{j(n\omega t + \theta _{c_n})}\)

但更多的时候，我们关注的是这个幅值：\(|d_n|\)

同样，上式是连续函数的展开，离散函数的展开如下

\(f[n] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{j(k\omega \frac{n}{N} + \theta _{c_n})}\)

但是，展开式中带着\(\theta _{c_n}\)，在求解时很麻烦。

既然这样，我们不妨从复指数展开式倒推回三角展开式

只不过，用的：\(f[n] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{j(k\omega \frac{n}{N})}\)

相当于，我们只用了\(cos(x)\)来展开

即：\(f[n] = \sum _{k=0}^{\infty} a_n \cdot cos(k\omega \frac{n}{N}) = \sum _{k=0}^{\infty} \frac{a_n}{2}\cdot [e^{jk\omega \frac{n}{N}} + e^{-jk\omega \frac{n}{N}}] = \sum _{-\infty}^{+\infty} |c_n| \cdot e^{jk\omega \frac{n}{N}}\)

这样就是说：我们假定是用\(cos(k \omega)\)来展开，而且我们丢失拟合精度，因为正统的傅里叶级数是由两部分构成的，\(cos(k \omega)\)和\(sin(k \omega)\)，我们这里丢失了\(sin(k \omega)\)部分。实际上，我实在无法用这个说法来说服自己，可能是我推导错了

我目前无法解决的问题是：为什么从三角推导过来的复指数展开式\(f[n] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{j(k\omega \frac{n}{N} + \theta _{c_n})}\) 明明有这个\(\theta _{c_n}\)，可实际的展开式却没有\(f[n] = \sum _{-\infty}^{+\infty} |d_n| \cdot e^{j(k\omega \frac{n}{N})}\)？如果有答案，还请不吝赐教，谢谢。

5.为什么DFT表达式里是负的

\(e^{-j2\pi kf\frac{n}{N}}\)

把DFT表达式抄过来镇楼：

\(X[k] = \sum _{n=0}^{N-1} x(n)\cdot e^{-j2\pi kf\frac{n}{N}}\)

再抄一个离散傅里叶展开式来镇二楼：

\(x[n] = \sum _{-\infty}^{+\infty} X[k] \cdot e^{j2\pi kf \frac{n}{N}}\)

冷不丁看这两个式子很像，但实际上差的很远，不仅仅是一个是DFT，一个是展开，主要是两个式子的\(\sum\)是不同的：

1. DFT中\(\sum\)是指对一个周期的所有采样点进行处理，即步进变量是\(n\)
2. 展开式中\(\sum\)是指的所有频率，即步进变量是\(k\)

利用正交性，再对展开式两边的\(n\)积分累和，就可以得到DFT：

\(\sum _{n=0}^{N-1} x[n]\cdot e^{j2\pi kf \frac{n}{N}} = \sum _{n=0}^{N-1} \{\sum _{-\infty}^{+\infty} X[k] \cdot e^{j2\pi kf \frac{n}{N}}\}\cdot e^{j2\pi kf \frac{n}{N}}\)

\(X[k]\)是一个待求的值，不包含被积量，所以提出：

\(\sum _{n=0}^{N-1} x[n]\cdot e^{j2\pi kf \frac{n}{N}} = X[k] \cdot \sum _{n=0}^{N-1} \{\sum _{-\infty}^{+\infty} e^{j2\pi kf \frac{n}{N}}\}\cdot e^{j2\pi kf \frac{n}{N}}\)

\(\sum _{n=0}^{N-1} x[n]\cdot e^{j2\pi kf \frac{n}{N}} = X[k] \cdot e^{j2\pi kf \frac{n}{N}} \cdot e^{j2\pi kf \frac{n}{N}}\)

整理，就得到：

\(X[k] = \sum _{n=0}^{N-1} x[n]\cdot e^{-j2\pi kf \frac{n}{N}}\)

所以，好像这一小节我推导了个寂寞。

简单用复指数证明一下正交性：

用欧拉公式替换成三角表示，用三角函数的正交性来解释。偷懒ing。

6.总结

其实这里总结的不仅仅是离散傅里叶变换，实际上我把复指数表示方式的证明也放在了本章节。

1. 引入复指数、复平面概念后，引入了负频率，这个在实际生活中是没有意义的，因为你找不到频率<0（或者说，在目前的认知中，尚且无法解释负频率的实际物理意义，只能暂时认为是数学运算产生的中间过程量）
2. 很无奈，有一个问题至今无法解释，实在是个人能力有限

未完待续。

世界上的每一个人，都被同一句谎话欺骗着：站在巨人的肩膀上看世界，会看的更远。我们都牢牢记住了这句话，确实看的更远，不过也仅此而已。

最后，再引用知乎leinlin文章的最后的一句话作为结束：

我们眼中的世界就像皮影戏的大幕布，幕布的后面有无数的齿轮，大齿轮带动小齿轮，小齿轮再带动更小的。在最外面的小齿轮上有一个小人——那就是我们自己。我们只看到这个小人毫无规律的在幕布前表演，却无法预测他下一步会去哪。而幕布后面的齿轮却永远一直那样不停的旋转，永不停歇。这样说来有些宿命论的感觉。说实话，这种对人生的描绘是我一个朋友在我们都是高中生的时候感叹的，当时想想似懂非懂，直到有一天我学到了傅里叶级数……

其实，懂得人都懂了，不懂的还是不懂。