傅里叶级数和傅立叶变换是傅里叶分析的两个主要工具，它们之间有密切的关系。
什么是傅里叶级数
傅里叶级数是将一个周期函数分解为一系列正弦和余弦函数的和。它适用于周期性信号，可以将周期函数表示为一组振幅和相位不同的谐波分量的和。傅里叶级数展示了一个周期函数在不同频率上的频谱内容。这样说太学究了，刚开始接触的人的可能看到这就头大了……
所以傅里叶级数到底是什么呢？
引子：
我们平时理解的更多是平面中的点，一个数A，都可以找到一些数B,C线性组合相加等于A， A = k 1 B + k 2 C A = k_1 B+k_2C A=k1B+k2C。 k 1 , k 2 是常数 k_1,k_2是常数 k1,k2是常数。我们将 k 1 , k 2 k_1,k_2 k1,k2改写一下， A = B x + C y A=Bx+Cy A=Bx+Cy，变成了我们熟悉的形式。一个正交坐标系可以描述平面上的任意一点。
平面坐标系找到一组正交x,y即可以线性组合拟合A。如果A代表的不是一个数，是一个函数呢？是不是也可以找到类似的正交系x,y。但是函数的一组正交系是什么呢？
周期性函数呢？周期性函数可是有无数个点呀？用什么去拟合呢，此时可能看到这个问题的你在内心里已经有了一些小的想法了，就是找到一组周期性线的函数去拟合。
傅里叶老前辈找到了帮我们找到了，就是下列的三角函数！！！！！！！
1 ， cos ( x ) ， sin ( x ) ， cos ( 2 x ) ， sin ( 2 x ) ， … ， cos ( n x ) ， sin ( n x ) 1，\cos(x)，\sin(x)，\cos(2x)，\sin(2x)，…，\cos(nx)，\sin(nx) 1，cos(x)，sin(x)，cos(2x)，sin(2x)，…，cos(nx)，sin(nx)，… 称为三角函数系。
傅立叶级数可以用以下公式表示：
f T ( x ) = a 0 2 + ∑ n = 1 N ( a n cos ( 2 π n T x ) + b n sin ( 2 π n T x ) ) f_T(x) = \frac{a_0}{2} + \sum_{n=1}^{N} \left(a_n \cos\left(\frac{2\pi n}{T}x\right) + b_n \sin\left(\frac{2\pi n}{T}x\right)\right) fT(x)=2a0+∑n=1N(ancos(T2πnx)+bnsin(T2πnx))
展开写理解起来会容 易一些：
f ( x 0 ) = a 0 2 + a 1 cos ( 2 π n 1 T x 0 ) + b 1 sin ( 2 π n 1 T x 0 ) + a 2 cos ( 2 π n 2 T x 0 ) + b 2 sin ( 2 π n 2 T x 0 ) + … + a N cos ( 2 π N T x 0 ) + N sin ( 2 π N T x 0 ) f(x_0)= \frac{a_0}{2}+a_1\cos\left(\frac{2\pi n_1}{T}x_0\right) + b_1 \sin\left(\frac{2\pi n_1 }{T}x_0\right) +a_2\cos\left(\frac{2\pi n_2}{T}x_0\right) + b_2 \sin\left(\frac{2\pi n_2}{T}x_0\right) \\ +\dots \\ +a_N\cos\left(\frac{2\pi N}{T}x_0\right) + N \sin\left(\frac{2\pi N}{T}x_0\right) f(x0)=2a0+a1cos(T2πn1x0)+b1sin(T2πn1x0)+a2cos(T2πn2x0)+b2sin(T2πn2x0)+…+aNcos(T2πNx0)+Nsin(T2πNx0)
f ( x 1 ) = a 0 2 + a 1 cos ( 2 π n 1 T x 1 ) + b 1 sin ( 2 π n 1 T x 1 ) + a 2 cos ( 2 π n 2 T x 1 ) + b 2 sin ( 2 π n 2 T x 1 ) + … + a N cos ( 2 π N T x 1 ) + N sin ( 2 π N T x 1 ) f(x_1)= \frac{a_0}{2}+a_1\cos\left(\frac{2\pi n_1}{T}x_1\right) + b_1 \sin\left(\frac{2\pi n_1 }{T}x_1\right) +a_2\cos\left(\frac{2\pi n_2}{T}x_1\right) + b_2 \sin\left(\frac{2\pi n_2}{T}x_1\right) \\ +\dots \\ +a_N\cos\left(\frac{2\pi N}{T}x_1\right) + N \sin\left(\frac{2\pi N}{T}x_1\right) f(x1)=2a0+a1cos(T2πn1x1)+b1sin(T2πn1x1)+a2cos(T2πn2x1)+b2sin(T2πn2x1)+…+aNcos(T2πNx1)+Nsin(T2πNx1)
f ( x 2 ) = a 0 2 + a 1 cos ( 2 π n 1 T x 2 ) + b 1 sin ( 2 π n 1 T x 2 ) + a 2 cos ( 2 π n 2 T x 2 ) + b 2 sin ( 2 π n 2 T x 2 ) + … + a N cos ( 2 π N T x 2 ) + N sin ( 2 π N T x 2 ) f(x_2)= \frac{a_0}{2}+a_1\cos\left(\frac{2\pi n_1}{T}x_2\right) + b_1 \sin\left(\frac{2\pi n_1 }{T}x_2\right) +a_2\cos\left(\frac{2\pi n_2}{T}x_2\right) + b_2 \sin\left(\frac{2\pi n_2}{T}x_2\right) \\ +\dots \\ +a_N\cos\left(\frac{2\pi N}{T}x_2\right) + N \sin\left(\frac{2\pi N}{T}x_2\right) f(x2)=2a0+a1cos(T2πn1x2)+b1sin(T2πn1x2)+a2cos(T2πn2x2)+b2sin(T2πn2x2)+…+aNcos(T2πNx2)+Nsin(T2πNx2)
⋮ \vdots ⋮
f ( x N ) = a 0 2 + a 1 cos ( 2 π n 1 T x N ) + b 1 sin ( 2 π n 1 T x N ) + a 2 cos ( 2 π n 2 T x N ) + b 2 sin ( 2 π n 2 T x N ) + … + a N cos ( 2 π N T x N ) + N sin ( 2 π N T x N ) f(x_N)= \frac{a_0}{2}+a_1\cos\left(\frac{2\pi n_1}{T}x_N\right) + b_1 \sin\left(\frac{2\pi n_1 }{T}x_N\right) +a_2\cos\left(\frac{2\pi n_2}{T}x_N\right) + b_2 \sin\left(\frac{2\pi n_2}{T}x_N\right) \\ +\dots \\ +a_N\cos\left(\frac{2\pi N}{T}x_N\right) + N \sin\left(\frac{2\pi N}{T}x_N\right) f(xN)=2a0+a1cos(T2πn1xN)+b1sin(T2πn1xN)+a2cos(T2πn2xN)+b2sin(T2πn2xN)+…+aNcos(T2πNxN)+Nsin(T2πNxN)
这里的合成的概念是时域上的叠加的概念，图片来源wikipedia
其中， f ( x ) f(x) f(x)是周期为 T T T的函数， a 0 a_0 a0是直流分量（平均值）， a n a_n an和 b n b_n bn是傅立叶系数，表示在频率为 2 π n T \frac{2\pi n}{T} T2πn的正弦和余弦函数的振幅。这个公式表示了周期函数 f ( x ) f(x) f(x)可以由一系列不同频率的正弦和余弦函数的和来逼近。
为什么可以这样展开
傅里叶级数的证明是一个相对复杂的过程，涉及到数学分析和傅里叶变换的理论。这里我将提供一个简要的概述，介绍傅里叶级数的基本思想和证明思路。
傅里叶级数的证明基于以下两个主要思想：
- 正交性：傅里叶级数利用了三角函数的正交性质。正弦和余弦函数在一个周期内是正交的，即它们的内积在不同频率下为零，而在相同频率下非零。这意味着不同频率的正弦和余弦函数是线性无关的基函数，可以用来表示不同频率的分量。
- 逼近性：傅里叶级数的另一个关键思想是逼近函数的概念。根据逼近定理，任何一个具有有限能量的周期函数，都可以用无限多个正弦和余弦函数的线性组合来逼近。通过增加正弦和余弦函数的振幅和相位，可以越来越接近原始函数。
基于这两个思想，傅里叶级数的证明过程可以大致概括为以下步骤： 首先，我们考虑一个周期为T的函数f(x)。我们要证明，可以将它表示为一系列正弦和余弦函数的和。 假设f(x)可以表示为以下形式的级数：
f ( x ) = a 0 2 + ∑ n = 1 ∞ ( a n cos ( ω n x ) + b n sin ( ω n x ) ) f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty} (a_n \cos(\omega_n x) + b_n \sin(\omega_n x)) f(x)=2a0+∑n=1∞(ancos(ωnx)+bnsin(ωnx))
其中， a 0 a_0 a0、 a n a_n an、 b n b_n bn是待定的系数， ω n \omega_n ωn是频率。
接下来，我们将使用正交性质来计算各个系数。通过将f(x)与正弦和余弦函数进行内积运算，并利用正交性质，我们可以得到各个系数的表达式。
通过计算内积，我们可以得到以下公式
a 0 = 1 π ∫ − π π f ( x ) cos ( ω n x ) d x , ω n = 0 a_0 = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos(\omega_n x)dx, \omega_n = 0 a0=π1∫−ππf(x)cos(ωnx)dx,ωn=0
a n = 1 π ∫ − π π f ( x ) cos ( ω n x ) d x a_n = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos(\omega_n x) dx an=π1∫−ππf(x)cos(ωnx)dx
b n = 1 π ∫ − π π f ( x ) sin ( ω n x ) d x b_n = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin(\omega_n x) dx bn=π1∫−ππf(x)sin(ωnx)dx
ω n = 2 π n T \omega_n = \frac{2\pi n}{T} ωn=T2πn
其中， a 0 a_0 a0是直流分量， a n a_n an和 b n b_n bn是频率为 ω n \omega_n ωn的余弦和正弦分量的振幅。
由欧拉公式：
cos θ = e i θ + e − i θ 2 \cos\theta = \frac{e^{i\theta}+e^{-i\theta}}{2} cosθ=2eiθ+e−iθ
sin θ = − i e i θ − e − i θ 2 \sin\theta =-i \frac{e^{i\theta}-e^{-i\theta}}{2} sinθ=−i2eiθ−e−iθ
下面的证明摘抄自复变函数与积分变换的教材：
F ( ω ) = ∫ − ∞ ∞ f ( t ) e − j ω t d t F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-j\omega t}dt F(ω)=∫−∞∞f(t)e−jωtdt
就是傅里叶变换了
什么是傅里叶变换
傅里叶变换则是将非周期性函数或信号分解为一组连续的正弦和余弦函数（复指数函数）的积分。傅立叶变换将一个时域函数转换为频域函数，显示了信号在不同频率上的频谱特征。
F ( ω ) = ∫ − ∞ ∞ f ( t ) e − j ω t d t F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-j\omega t}dt F(ω)=∫−∞∞f(t)e−jωtdt
1 2 π ∫ − ∞ ∞ F ( ω ) e j ω t d ω \frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{j\omega t}d\omega 2π1∫−∞∞F(ω)ejωtdω
f T ( x ) = a 0 2 + ∑ n = 1 N ( a n cos ( 2 π n T x ) + b n sin ( 2 π n T x ) ) f_T(x) = \frac{a_0}{2} + \sum_{n=1}^{N} \left(a_n \cos\left(\frac{2\pi n}{T}x\right) + b_n \sin\left(\frac{2\pi n}{T}x\right)\right) fT(x)=2a0+∑n=1N(ancos(T2πnx)+bnsin(T2πnx))
两者之间的关系可以用以下方式表达：
傅里叶级数是傅立叶变换的一种特殊情况。当一个周期为T的函数被表示为傅里叶级数时，其傅立叶变换是一个离散的频谱，只包含一系列离散的频率分量。对于一个连续非周期函数，傅立叶变换将其表示为一个连续的频谱，包含了所有可能的频率分量。这相当于将傅里叶级数中的频率分量离散化为连续的频谱。傅立叶变换可以视为傅里叶级数的极限情况，当周期趋向于无穷大时，傅里叶级数的频率间隔趋向于零，从而得到了连续的频谱。
总的来说，傅里叶级数和傅立叶变换是傅里叶分析的两种表示方法，它们可以相互转换，但适用于不同的函数类别和分析需求。傅里叶级数适用于周期函数的频谱分析，而傅立叶变换适用于非周期函数的频谱分析。
FFT快速傅里叶变换
DFT定义：
X k = ∑ n = 0 N − 1 x n e − i 2 π n N k ， k = 0 , 1 , … , N − 1 X_k = \sum_{n=0}^{N-1}x_ne^{-i\frac{2\pi n}{N}k}，k = 0,1,\dots,N-1 Xk=∑n=0N−1xne−iN2πnk，k=0,1,…,N−1
展开各项：
X 0 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 0 X_0=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=0 X0=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=0
X 1 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 1 X_1=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=1 X1=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=1
… \dots …
X N − 1 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = N − 1 X_{N-1}=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=N-1 XN−1=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=N−1
还是不够直观？举个离散数据的例子来看：
x 0 = 1 x_0 = 1 x0=1
x 1 = 2 x_1 = 2 x1=2
x 3 = 3 x_3 = 3 x3=3
x 4 = 4 x_4 = 4 x4=4
X 0 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 0 , N = 4 X_0=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=0,N=4 X0=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=0,N=4
X 1 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 1 , N = 4 X_1=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=1,N=4 X1=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=1,N=4
X 2 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 2 , N = 4 X_2=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=2,N=4 X2=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=2,N=4
X 3 = x 0 e − i 2 π 0 N k + x 1 e − i 2 π 1 N k + ⋯ + x N − 1 e − i 2 π ( N − 1 ) N k , k = 3 , N = 4 X_3=x_0e^{-i\frac{2\pi 0}{N}k}+x_1e^{-i\frac{2\pi 1}{N}k}+\dots+x_{N-1}e^{-i\frac{2\pi (N-1)}{N}k},k=3,N=4 X3=x0e−iN2π0k+x1e−iN2π1k+⋯+xN−1e−iN2π(N−1)k,k=3,N=4
X 0 = 1 e − i 2 π 0 4 0 + 2 e − i 2 π 1 4 0 + 3 e − i 2 π ( 2 ) 4 0 + 4 e − i 2 π ( 3 ) 4 0 = 10 + 0 i X_0=1e^{-i\frac{2\pi 0}{4}0}+2e^{-i\frac{2\pi 1}{4}0}+3e^{-i\frac{2\pi (2)}{4}0}+4e^{-i\frac{2\pi (3)}{4}0}=10+0i X0=1e−i42π00+2e−i42π10+3e−i42π(2)0+4e−i42π(3)0=10+0i
X 1 = 1 e − i 2 π 0 4 1 + 2 e − i 2 π 1 4 1 + 3 e − i 2 π ( 2 ) 4 1 + 4 e − i 2 π ( 3 ) 4 1 = − 2 + 2 i X_1=1e^{-i\frac{2\pi 0}{4}1}+2e^{-i\frac{2\pi 1}{4}1}+3e^{-i\frac{2\pi (2)}{4}1}+4e^{-i\frac{2\pi (3)}{4}1}=-2+2i X1=1e−i42π01+2e−i42π11+3e−i42π(2)1+4e−i42π(3)1=−2+2i
X 2 = 1 e − i 2 π 0 4 2 + 2 e − i 2 π 1 4 2 + 3 e − i 2 π ( 2 ) 4 2 + 4 e − i 2 π ( 3 ) 4 2 = − 2 + 0 i X_2=1e^{-i\frac{2\pi 0}{4}2}+2e^{-i\frac{2\pi 1}{4}2}+3e^{-i\frac{2\pi (2)}{4}2}+4e^{-i\frac{2\pi (3)}{4}2}=-2+0i X2=1e−i42π02+2e−i42π12+3e−i42π(2)2+4e−i42π(3)2=−2+0i
X 3 = 1 e − i 2 π 0 4 3 + 2 e − i 2 π 1 4 3 + 3 e − i 2 π ( 2 ) 4 3 + 4 e − i 2 π ( 3 ) 4 3 = − 2 − 2 i X_3=1e^{-i\frac{2\pi 0}{4}3}+2e^{-i\frac{2\pi 1}{4}3}+3e^{-i\frac{2\pi (2)}{4}3}+4e^{-i\frac{2\pi (3)}{4}3}=-2-2i X3=1e−i42π03+2e−i42π13+3e−i42π(2)3+4e−i42π(3)3=−2−2i
令： w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π
把这个案例写成矩阵的形式：
[ X 0 X 1 X 2 X 3 ] = [ 1 1 1 1 1 w w 2 w 3 1 w 2 w 4 w 6 1 w 3 w 6 w 9 ] [ x 0 x 1 x 2 x 3 ] \begin{bmatrix} X_0 \\ X_1 \\ X_2 \\ X_3 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 &1 &1 \\ 1 &w&w^2&w^3 \\ 1 &w^2 & w^4 &w^6 \\ 1 & w^3 & w^6 & w^9 \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix} X0X1X2X3 = 11111ww2w31w2w4w61w3w6w9 x0x1x2x3
完成这4个点DFT，需计算 16次乘法，即矩阵F中每个元素都会参与一次乘法，共 4个元素；12次加法，即每完成一个点需要3次加法。直到现在DFT终于高懂了，但是计算起来太麻烦了，效率太低。数据越大，计算量越大。FFT出现解决了计算量大的问题。
w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π 具有对称性，这是FFT简化的计算的方法，即：
W N k + N 2 = − W N k W_N^{k+\frac{N}{2}} = -W_N^k WNk+2N=−WNk
X k = ∑ n = 0 N − 1 x n e − i 2 π n N k X_k = \sum_{n=0}^{N-1}x_ne^{-i\frac{2\pi n}{N}k} Xk=∑n=0N−1xne−iN2πnk
再写一遍，加深印象： w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π
X k = ∑ n = 0 N − 1 x n w n k X_k = \sum_{n=0}^{N-1}{x_nw^{nk}} Xk=∑n=0N−1xnwnk
再看这个公式，变化即是信号值乘以对应的复数 e − i 2 π n N k e^{-i\frac{2\pi n}{N}k} e−iN2πnk再求累加。
根据对称性可以简化傅里叶的计算，这就是FFT的意义。
分治法实现
上面的式子再写一遍，就当加深印象了，好累！！！！！
令： w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π
X 0 = 1 e − i 2 π 0 4 0 + 2 e − i 2 π 1 4 0 + 3 e − i 2 π ( 2 ) 4 0 + 4 e − i 2 π ( 3 ) 4 0 = 10 + 0 i X_0=1e^{-i\frac{2\pi 0}{4}0}+2e^{-i\frac{2\pi 1}{4}0}+3e^{-i\frac{2\pi (2)}{4}0}+4e^{-i\frac{2\pi (3)}{4}0}=10+0i X0=1e−i42π00+2e−i42π10+3e−i42π(2)0+4e−i42π(3)0=10+0i
X 1 = 1 e − i 2 π 0 4 1 + 2 e − i 2 π 1 4 1 + 3 e − i 2 π ( 2 ) 4 1 + 4 e − i 2 π ( 3 ) 4 1 = − 2 + 2 i X_1=1e^{-i\frac{2\pi 0}{4}1}+2e^{-i\frac{2\pi 1}{4}1}+3e^{-i\frac{2\pi (2)}{4}1}+4e^{-i\frac{2\pi (3)}{4}1}=-2+2i X1=1e−i42π01+2e−i42π11+3e−i42π(2)1+4e−i42π(3)1=−2+2i
X 2 = 1 e − i 2 π 0 4 2 + 2 e − i 2 π 1 4 2 + 3 e − i 2 π ( 2 ) 4 2 + 4 e − i 2 π ( 3 ) 4 2 = − 2 + 0 i X_2=1e^{-i\frac{2\pi 0}{4}2}+2e^{-i\frac{2\pi 1}{4}2}+3e^{-i\frac{2\pi (2)}{4}2}+4e^{-i\frac{2\pi (3)}{4}2}=-2+0i X2=1e−i42π02+2e−i42π12+3e−i42π(2)2+4e−i42π(3)2=−2+0i
X 3 = 1 e − i 2 π 0 4 3 + 2 e − i 2 π 1 4 3 + 3 e − i 2 π ( 2 ) 4 3 + 4 e − i 2 π ( 3 ) 4 3 = − 2 − 2 i X_3=1e^{-i\frac{2\pi 0}{4}3}+2e^{-i\frac{2\pi 1}{4}3}+3e^{-i\frac{2\pi (2)}{4}3}+4e^{-i\frac{2\pi (3)}{4}3}=-2-2i X3=1e−i42π03+2e−i42π13+3e−i42π(2)3+4e−i42π(3)3=−2−2i
X 0 = w 0 × 0 x 0 + w 1 × 0 x 1 + w 2 × 0 x 2 + w 3 × 0 x 3 X_0 = w^{0\times 0}x_0+w^{1 \times 0}x_1+w^{2\times 0}x_2+w^{3 \times 0}x_3 X0=w0×0x0+w1×0x1+w2×0x2+w3×0x3
X 1 = w 0 × 1 x 0 + w 1 × 1 x 1 + w 2 × 1 x 2 + w 3 × 1 x 3 X_1= w^{0\times 1}x_0+w^{1 \times 1}x_1+w^{2 \times 1}x_2+w^{3 \times 1}x_3 X1=w0×1x0+w1×1x1+w2×1x2+w3×1x3
X 2 = w 0 × 2 x 0 + w 1 × 2 x 1 + w 2 × 2 x 2 + w 3 × 2 x 3 X_2=w^{0\times 2}x_0+w^{1 \times 2}x_1+w^{2 \times 2}x_2+w^{3 \times 2}x_3 X2=w0×2x0+w1×2x1+w2×2x2+w3×2x3
X 3 = w 0 × 3 x 0 + w 1 × 3 x 1 + w 2 × 3 x 2 + w 3 × 3 x 3 X_3=w^{0\times 3}x_0+w^{1 \times 3}x_1+w^{2 \times 3}x_2+w^{3 \times 3}x_3 X3=w0×3x0+w1×3x1+w2×3x2+w3×3x3
这样我们将上式分下组，接着讲，将奇数分为一组，偶数分为一组！！！！！！
X 0 = w 0 × 0 x 0 + w 2 × 0 x 2 + w 1 × 0 x 1 + w 3 × 0 x 3 X_0=w^{0\times 0}x_0+w^{2\times 0}x_2+w^{1 \times 0}x_1+w^{3 \times 0}x_3 X0=w0×0x0+w2×0x2+w1×0x1+w3×0x3
X 1 = w 0 × 1 x 0 + w 2 × 1 x 2 + w 1 × 1 x 1 + w 3 × 1 x 3 X_1=w^{0\times 1}x_0+w^{2 \times 1}x_2+w^{1 \times 1}x_1+w^{3 \times 1}x_3 X1=w0×1x0+w2×1x2+w1×1x1+w3×1x3
X 2 = w 0 × 2 x 0 + w 2 × 2 x 2 + w 1 × 2 x 1 + w 3 × 2 x 3 X_2=w^{0\times 2}x_0+w^{2 \times 2}x_2+w^{1 \times 2}x_1+w^{3 \times 2}x_3 X2=w0×2x0+w2×2x2+w1×2x1+w3×2x3
X 3 = w 0 × 3 x 0 + w 2 × 3 x 2 + w 1 × 3 x 1 + w 3 × 3 x 3 X_3=w^{0\times 3}x_0+w^{2 \times 3}x_2+w^{1 \times 3}x_1+w^{3 \times 3}x_3 X3=w0×3x0+w2×3x2+w1×3x1+w3×3x3
[ w 0 × 0 w 2 × 0 w 1 × 0 w 3 × 0 w 0 × 1 w 2 × 1 w 1 × 1 w 3 × 1 w 0 × 2 w 2 × 2 w 1 × 2 w 3 × 2 w 0 × 3 w 2 × 3 w 1 × 3 w 3 × 3 ] [ x 0 x 2 x 1 x 3 ] = [ w 0 w 0 w 0 w 0 w 0 w 2 w 1 w 3 w 0 w 4 w 2 w 6 w 0 w 6 w 3 w 9 ] [ x 0 x 2 x 1 x 3 ] \begin{bmatrix} w^{0\times 0} & w^{2\times 0} &w^{1 \times 0} &w^{3 \times 0} \\ w^{0\times 1}&w^{2 \times 1}&w^{1 \times 1}&w^{3 \times 1} \\ w^{0\times 2} &w^{2 \times 2} & w^{1 \times 2}&w^{3 \times 2} \\ w^{0\times 3} & w^{2 \times 3} & w^{1 \times 3} &w^{3 \times 3} \end{bmatrix} \begin{bmatrix} x_0 \\ x_2 \\ x_1 \\ x_3 \end{bmatrix}= \begin{bmatrix} w^{0} & w^{0} &w^{0} &w^{0} \\ w^{0}&w^{2 }&w^{1}&w^{3} \\ w^{0} &w^{4} & w^{2}&w^{6} \\ w^{0} & w^{6} & w^{3} &w^{9} \end{bmatrix} \begin{bmatrix} x_0 \\ x_2 \\ x_1 \\ x_3 \end{bmatrix} w0×0w0×1w0×2w0×3w2×0w2×1w2×2w2×3w1×0w1×1w1×2w1×3w3×0w3×1w3×2w3×3 x0x2x1x3 = w0w0w0w0w0w2w4w6w0w1w2w3w0w3w6w9 x0x2x1x3
w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π
根最美公式欧拉公式：
e i x = cos ( x ) + i sin ( x ) e^{ix} = \cos(x) + i\sin(x) eix=cos(x)+isin(x)
上述的矩阵还可以写成：
w n × k = cos ( 2 π N × n × k ) − i sin ( 2 π N × n × k ) w^{n\times k } = \cos(\frac{2\pi}{N}\times n\times k)-i\sin(\frac{2\pi}{N}\times n\times k) wn×k=cos(N2π×n×k)−isin(N2π×n×k)
[ cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π N × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 2 ) − i sin ( 2 π 4 × 2 ) cos ( 2 π 4 × 1 ) − i sin ( 2 π 4 × 1 ) cos ( 2 π N × 3 ) − i sin ( 2 π 4 × 3 ) cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 4 ) − i sin ( 2 π 4 × 4 ) cos ( 2 π 4 × 2 ) − i sin ( 2 π 4 × 2 ) cos ( 2 π N × 6 ) − i sin ( 2 π 4 × 6 ) cos ( 2 π 4 × 0 ) − i sin ( 2 π 4 × 0 ) cos ( 2 π 4 × 6 ) − i sin ( 2 π 4 × 6 ) cos ( 2 π 4 × 3 ) − i sin ( 2 π 4 × 3 ) cos ( 2 π N × 9 ) − i sin ( 2 π 4 × 9 ) ] [ x 0 x 2 x 1 x 3 ] \begin{bmatrix} \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0) & \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0) & \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0) & \cos(\frac{2\pi}{N}\times0)-i\sin(\frac{2\pi}{4}\times 0) \\ \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0)& \cos(\frac{2\pi}{4}\times2)-i\sin(\frac{2\pi}{4}\times 2)& \cos(\frac{2\pi}{4}\times1)-i\sin(\frac{2\pi}{4}\times 1)& \cos(\frac{2\pi}{N}\times3)-i\sin(\frac{2\pi}{4}\times 3) \\ \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0) & \cos(\frac{2\pi}{4}\times4)-i\sin(\frac{2\pi}{4}\times 4) & \cos(\frac{2\pi}{4}\times2)-i\sin(\frac{2\pi}{4}\times 2)& \cos(\frac{2\pi}{N}\times6)-i\sin(\frac{2\pi}{4}\times6) \\ \cos(\frac{2\pi}{4}\times0)-i\sin(\frac{2\pi}{4}\times 0) & \cos(\frac{2\pi}{4}\times6)-i\sin(\frac{2\pi}{4}\times 6) & \cos(\frac{2\pi}{4}\times3)-i\sin(\frac{2\pi}{4}\times 3) & \cos(\frac{2\pi}{N}\times9)-i\sin(\frac{2\pi}{4}\times 9) \end{bmatrix} \begin{bmatrix} x_0 \\ x_2 \\ x_1 \\ x_3 \end{bmatrix} cos(42π×0)−isin(42π×0)cos(42π×0)−isin(42π×0)cos(42π×0)−isin(42π×0)cos(42π×0)−isin(42π×0)cos(42π×0)−isin(42π×0)cos(42π×2)−isin(42π×2)cos(42π×4)−isin(42π×4)cos(42π×6)−isin(42π×6)cos(42π×0)−isin(42π×0)cos(42π×1)−isin(42π×1)cos(42π×2)−isin(42π×2)cos(42π×3)−isin(42π×3)cos(N2π×0)−isin(42π×0)cos(N2π×3)−isin(42π×3)cos(N2π×6)−isin(42π×6)cos(N2π×9)−isin(42π×9) x0x2x1x3
由于 w = e − i 2 π N w = e^{\frac{-i2\pi}{N}} w=eN−i2π 具有周期性，所以可以将w的幂次方简化，由于N=4。所以可以看成周期为4。
例如：
在N=4的条件下根据周期性可得以下结论：
根据周期性：
w 4 = 1 w^4 = 1 w4=1
w 9 = w 1 w^9 = w^1 w9=w1
w 6 = w 2 w^6 = w^2 w6=w2
根据对称性：
w 1 = − w 3 w^1 = -w^3 w1=−w3
w 0 = − w 2 w^0 = -w^2 w0=−w2
证明：
可以发现红色区域的内容相同，蓝色区域的内容相差一个 ω 2 \omega^2 ω2 因此我们只需要计算一半的内容即可。由于加法次数多于乘法，因此复杂度只需考虑加法使用的次数，本次计算耗时：2 （ 红 色 用 两 次 加 法 ） + 2 （ 蓝 色 用 两 次 加 法 ） + 4 （ 中 间 的 4 个 加 法 ） = 4 l o g 2 4 2（红色用两次加法）+ 2（蓝色用两次加法）+4（中间的4个加法）= 4 log 2 ( 4 ) 4\log_2 (4) 4log2(4)
当n=8时
其中，绿色区域覆盖全部，表示开始需要计算的内容，棕色区域只包含了上半部分的两块内容，在得到棕色区域结果后可以顺势得到下半部分的绿色区域，橙色区域包含上面1/4部分的两块区域，红色区域则值包含最上面一行的两块区域。 绿(要求)->棕(要求)->橙(要求)->红(解)->橙(解)->棕(解)->绿(解)，这是一个很明显的递归过程。
FFT
IFFT
本身是一个求逆的过程，由于范德蒙矩阵的特性，得到结果如下
再写一遍：
X k = ∑ n = 0 N − 1 x n e − i 2 π n N k ， k = 0 , 1 , … , N − 1 X_k = \sum_{n=0}^{N-1}x_ne^{-i\frac{2\pi n}{N}k}，k = 0,1,\dots,N-1 Xk=∑n=0N−1xne−iN2πnk，k=0,1,…,N−1
X k = ∑ n = 0 N − 1 x ( n ) × cos ( 2 π n N k ) − i ∑ n = 0 N − 1 x ( n ) × sin ( 2 π n N k ) X_k = \sum_{n=0}^{N-1}x(n)\times\cos(\frac{2\pi n}{N}k)-i\sum_{n=0}^{N-1}x(n)\times\sin(\frac{2\pi n}{N}k) Xk=∑n=0N−1x(n)×cos(N2πnk)−i∑n=0N−1x(n)×sin(N2πnk)
应用
等有时间再作整理……
C++代码实现
等有时间再作整理……
