这就是使用离散傅里叶变换来实现OFDM的原理图：



那分帧分组，编码映射是什么情况呢？


用途是将输入的比特流先分帧，然后在帧中分组，然后再串并转换：


然后再将这些分组编码，并使编码与QAM或QPSK的星座点一一对应，


这也就是映射的意思。
接下来，由我自己来讲自己的理解：（润色中，仅供参考！不断修改。。。）
假设编码映射使用的是QPSK调制，则映射后的码元是由不同相位的波形构成，同时一个码元携带2个二进制信息，经过数字调制后的码元用  来表示；
下图是OFDM的调制原理图：




由上图可知：


乘上的过程是将OFDM基带信号调制到OFDM射频信号的过程。
单独取出上式中的一部分：


离散化，抽样N个点得到：


这TM不就是离散傅里叶逆变换吗！（原谅我放纵下自己的语言！）
在这张图中：


对  进行傅里叶逆变换，再经过并串转换，即：


然后对每一个码元经过DAC，得到x(t):


然后经过IQ调制，得到OFDM射频信号s(t)；
这样不就是这个使用IDFT实现的OFDM调制的过程吗？
IDFT等价于IFFT，这样计算机就可以处理了。
到现在为止，只是大概叙述了OFDM的过程，路漫漫，需要进一步了解的东西还要很多，OFDM的调制中的细节问题，以及OFDM的解调，我会时而持续，时而中断更新，别问我为什么，万恶的期末考试害的。（为什么用蓝色字体，因为我的心情是蓝色的。）
————————————————————————————————————————————————————
下面是视频的原话，我认为错了不少。如果信我，就别看了。
————————————————————————————————————————————————————


下面借助数学的方法，简单说明这两幅图之间的关系：


从前面的这个原理图中，我们可以写出信号s(t)的表达式：


这里是输入的基带信号，复指数函数表示子载波，Re表示取复数的实部，为什么要只取实部呢？
因为物理信号s（t）是实函数；
设f0是信号s(t)的总带宽中心频率，根据子载波频率间隔
，等于输入码元持续时间的倒数，，可以将上式变为：


这个复指数函数，就是由绿色部分电路实现的；
而公式中的这一块，我们把它设为：


它的意义是：
所有子信道基带信号的一个总体包络，


这是一个模拟函数，


如果用频率为m/T的脉冲进行抽样，那么抽样所得的样本函数：


其实就相当于对进行逆傅里叶变换，


所以对输入的序列{}进行逆傅里叶变换，得到离散序列{}，将离散序列相加合并，得到离散信号，也就是x(t)的抽样样本：


将离散的样本通过模数转换，即可得到连续的包络信号x(t)：


最后将x(t)调制到载波上，即是OFDM的调制信号s(t)。


这和之前的原理图效果是一样的，但成本降低了很多：

FFT前言
 
 
 
快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
 
 
FFT（Fast Fourier Transformation） 是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
 
 
——百度百科
 
 
FFT（Fast Fourier Transformation），中文名快速傅里叶变换，用来加速多项式乘法
 朴素高精度乘法时间$O(n^2)$，但$FFT$能$O(n{\log }_{2}n)$的时间解决
 $FFT$名字逼格高，也难懂，其他教程写得让人看不太懂，于是自己随便写一下
 
 
 
 
建议对复数、三角函数相关知识有所耳闻 （不会也无所谓）
 
 
下面难懂的点我会从网上盗
 
 
 
 
多项式的系数表示法和点值表示法
 
 
$FFT$其实是一个用$O(n{\log }_{2}n)$的时间将一个用系数表示的多项式转换成它的点值表示的算法
 
 
多项式的系数表示和点值表示可以互相转换
 
 
 
 
系数表示法
 
 
一个n-1次n项多项式$f(x)$可以表示为$f(x)={\sum }_{i=0}^{n-1}{a}_i{x}^i$
 也可以用每一项的系数来表示$f(x)$，即
     
      
       
        
         f
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         {
        
        
         
          a
         
         
          0
         
        
        
         ,
        
        
         
          a
         
         
          1
         
        
        
         ,
        
        
         
          a
         
         
          2
         
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         
          a
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         }
        
       
       
        f(x)=\{a_0,a_1,a_2,...,a_{n-1} \}
       
      
     f(x)={a0​,a1​,a2​,...,an−1​}
 这就是系数表示法，也就是平时数学课上用的方法
 
 
 
点值表示法
 
 
 
把多项式放到平面直角坐标系里面，看成一个函数
 
 
把$n$个不同的$x$代入，会得出$n$个不同的$y$，在坐标系内就是$n$个不同的点
 
 
那么这$n$个点唯一确定该多项式，也就是有且仅有一个多项式满足$\forall k,f(x_k)=y_k$
 
 
理由很简单，把$n$条式子联立起来成为一个有n条方程的n元方程组，每一项的系数都可以解出来
 
 
那么$f(x)$还可以用
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        {
       
       
        (
       
       
        
         x
        
        
         0
        
       
       
        ,
       
       
        f
       
       
        (
       
       
        
         x
        
        
         0
        
       
       
        )
       
       
        )
       
       
        ,
       
       
        (
       
       
        
         x
        
        
         1
        
       
       
        ,
       
       
        f
       
       
        (
       
       
        
         x
        
        
         1
        
       
       
        )
       
       
        )
       
       
        ,
       
       
        (
       
       
        
         x
        
        
         2
        
       
       
        ,
       
       
        f
       
       
        (
       
       
        
         x
        
        
         2
        
       
       
        )
       
       
        )
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        (
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        ,
       
       
        f
       
       
        (
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        )
       
       
        )
       
       
        }
       
      
      
       f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),...,(x_{n-1},f(x_{n-1}))\}
      
     
    f(x)={(x0​,f(x0​)),(x1​,f(x1​)),(x2​,f(x2​)),...,(xn−1​,f(xn−1​))}来表示
 这就是点值表示法
 
 
高精度乘法下两种多项式表示法的区别
 
对于两个用系数表示的多项式，我们把它们相乘
 设两个多项式分别为$A(x),B(x)$
 我们要枚举$A$每一位的系数与$B$每一位的系数相乘
 那么系数表示法做多项式乘法时间复杂度$O(n^2)$
 
但两个用点值表示的多项式相乘，只需要$O(n)$的时间
 
 
 
什么意思呢？
 
 
设两个点值多项式分别为
     
      
       
        
         f
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         {
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         )
        
        
         )
        
        
         }
        
       
       
        f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),...,(x_{n-1},f(x_{n-1}))\}
       
      
     f(x)={(x0​,f(x0​)),(x1​,f(x1​)),(x2​,f(x2​)),...,(xn−1​,f(xn−1​))}
     
      
       
        
         g
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         {
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         ,
        
        
         g
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         ,
        
        
         g
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         ,
        
        
         g
        
        
         (
        
        
         
          x
         
         
          2
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         ,
        
        
         g
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         )
        
        
         )
        
        
         }
        
       
       
        g(x)=\{(x_0,g(x_0)),(x_1,g(x_1)),(x_2,g(x_2)),...,(x_{n-1},g(x_{n-1}))\}
       
      
     g(x)={(x0​,g(x0​)),(x1​,g(x1​)),(x2​,g(x2​)),...,(xn−1​,g(xn−1​))}
 设它们的乘积是$h(x)$，那么
     
      
       
        
         h
        
        
         (
        
        
         x
        
        
         )
        
        
         =
        
        
         {
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         )
        
        
         ⋅
        
        
         g
        
        
         (
        
        
         
          x
         
         
          0
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         )
        
        
         ⋅
        
        
         g
        
        
         (
        
        
         
          x
         
         
          1
         
        
        
         )
        
        
         )
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         ,
        
        
         f
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         )
        
        
         ⋅
        
        
         g
        
        
         (
        
        
         
          x
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
        
         )
        
        
         )
        
        
         }
        
       
       
        h(x)=\{(x_0,f(x_0)·g(x_0)),(x_1,f(x_1)·g(x_1)),...,(x_{n-1},f(x_{n-1})·g(x_{n-1}))\}
       
      
     h(x)={(x0​,f(x0​)⋅g(x0​)),(x1​,f(x1​)⋅g(x1​)),...,(xn−1​,f(xn−1​)⋅g(xn−1​))}
 
所以这里的时间复杂度只有一个枚举的$O(n)$
 
 
突然感觉高精度乘法能$O(n)$暴艹一堆题？
 
 
但是朴素的系数表示法转点值表示法的算法还是$O(n^2)$的，逆操作类似
 
 
朴素系数转点值的算法叫DFT（离散傅里叶变换），点值转系数叫IDFT（离散傅里叶逆变换）
 
 
难道高精度乘法只能$O(n^2)$了吗？
 
 
 
DFT前置知识&技能
 
 
 
复数
 
 
毕竟高中有所以不多说
 
 
 
我们把形如a+bi（a,b均为实数）的数称为复数，其中a称为实部，b称为虚部，i称为虚数单位。当虚部等于零时，这个复数可以视为实数；当z的虚部不等于零时，实部等于零时，常称z为纯虚数。复数域是实数域的代数闭包，也即任何复系数多项式在复数域中总有根。 复数是由意大利米兰学者卡当在十六世纪首次引入，经过达朗贝尔、棣莫弗、欧拉、高斯等人的工作，此概念逐渐为数学家所接受。
 ——百度百科
 
 
初中数学老师会告诉你没有$\sqrt{-1}$，但仅限$R$
 扩展至复数集$C$，定义$i^2=-1$，一个复数$z$可以表示为$z=a+bi(a,b\in R)$
 其中$a$称为实部，$b$称为虚部，$i$称为虚数单位
 
在复数集中就可以用$i$表示负数的平方根，如$\sqrt{-7}=\sqrt{7}i$
 
还可以把复数看成复平面直角坐标系上的一个点，比如下面
 
 
 

 $x$轴就是实数集中的坐标轴，$y$轴就是虚数单位$i$轴
 
 
这个点$(2,3)$表示的复数就是$2+3i$，或者想象它代表的向量为$(2,3)$
 其实我们还可以自己想象 （其实没有这种表达方式） 它可以表示为$(\sqrt{13},\theta )$
 一个复数$z$的模定义为它到原点的距离，记为$|z|=\sqrt{a^2+b^2}$
 一个复数$z=a+bi$的共轭复数为$a-bi$（虚部取反），记为$\overline{z}=a-bi$
 
 
 
复数的运算
 
 
复数不像点或向量，它和实数一样可以进行四则运算
 设两个复数分别为$z_1=a+bi,z_2=c+di$，那么
 $$z_1+z_2=(a+c)+(b+d)i$$$$z_1{z}_2=(ac-bd)+(ad+bc)i$$
 
复数相加也满足平行四边形法则
 
 
 

 这张是从网上盗的
 
 
即$AB+AD=AC$
 
复数相乘还有一个值得注意的小性质
 $$(a_1,{\theta }_1)\ast (a_2,{\theta }_2)=(a_1{a}_2,{\theta }_1+{\theta }_2)$$
 即模长相乘，极角相加
 
 
DFT（离散傅里叶变换）
 
一定注意从这里开始所有的$n$都默认为$2$的整数次幂
 
对于任意系数多项式转点值，当然可以随便取任意$n$个$x$值代入计算
 但是暴力计算$x_k^0,x_k^1,...,x_k^{n-1}(k\in [0,n))$当然是$O(n^2)$的时间
 其实可以代入一组神奇的$x$，代入以后不用做那么多的次方运算
 这些$x$当然不是乱取的，而且取这些$x$值应该就是 傅里叶 的主意了
 
考虑一下，如果我们代入一些$x$，使每个$x$的若干次方等于$1$，我们就不用做全部的次方运算了
 $\pm 1$是可以的，考虑虚数的话$\pm i$也可以，但只有这四个数远远不够
 
傅里叶说：这个圆圈上面的点都可以做到
 
 
 
 
 
以原点为圆心，画一个半径为$1$的单位圆
 那么单位圆上所有的点都可以经过若干次次方得到$1$
 傅里叶说还要把它给$n$等分了，比如此时$n=8$
 
 
 
 
 
橙色点即为$n=8$时要取的点，从$(1,0)$点开始，逆时针从$0$号开始标号，标到$7$号
 记编号为$k$的点代表的复数值为${\omega }_n^k$，那么由模长相乘，极角相加可知$({\omega }_n^1{)}^k={\omega }_n^k$
 其中${\omega }_n^1$称为$n$次单位根，而且每一个$\omega$都可以求出 （我三角函数不好）
 $${\omega }_n^k=\cos \frac{k}{n}2\pi +i\sin \frac{k}{n}2\pi$$
 
或者说也可以这样解释这条式子
 
 
 

 注意$si{n}^2\theta +co{s}^2\theta =1$什么的，就容易理解了
 
 
那么${\omega }_n^0,{\omega }_n^1,...,{\omega }_n^{n-1}$即为我们要代入的$x_0,x_1,...,x_{n-1}$
 
 
单位根的一些性质
 
推$FFT$的过程中需要用到$\omega$的一些性质
 
 
 
${\omega }_n^k={\omega }_{2n}^{2k}$
 
 
 
它们表示的点（或向量）表示的复数是相同的
 
 
证明
 
 
${\omega }_n^k=cos\frac{k}{n}2\pi +isin\frac{k}{n}2\pi =cos\frac{2k}{2n}2\pi +isin\frac{2k}{2n}2\pi ={\omega }_{2n}^{2k}$
 
 
 
 
${\omega }_n^{k+\frac{n}{2}}=-{\omega }_n^k$
 
 
 
它们表示的点关于原点对称，所表示的复数实部相反，所表示的向量等大反向
 
 
证明
 
 
${\omega }_n^{\frac{n}{2}}=cos\frac{\frac{n}{2}}{n}2\pi +isin\frac{\frac{n}{2}}{n}2\pi =cos\pi +isin\pi =-1$
 
 
（这个东西和$e^{ix}=cosx+isinx$与$e^{i\pi }+1=0$有点关系，我不会就不讲了）
 
 
 
 
${\omega }_n^0={\omega }_n^n$
 
 
都等于$1$，或$1+0i$
 
 
FFT（快速傅里叶变换）
 
虽然$DFT$搞出来一堆很牛逼的$\omega$作为代入多项式的$x$值
 但只是代入这类特殊$x$值法的变换叫做$DFT$而已，还是要代入单位根暴力计算
 
DFT还是暴力$O(n^2)$…
 
但$DFT$可以分治来做，于是 FFT（快速傅里叶变换） 就出来了
 首先设一个多项式$A(x)$
 $$A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i=a_0+a_{1}x+a_2{x}^2+...+a_{n-1}{x}^{n-1}$$
 
按$A(x)$下标的奇偶性把$A(x)$分成两半，右边再提一个$x$
 
$$A(x)=(a_0+a_2{x}^2+...+a_{n-2}{x}^{n-2})+(a_{1}x+a_3{x}^3+...+a_{n-1}{x}^{n-1})$$
 
$$=(a_0+a_2{x}^2+...+a_{n-2}{x}^{n-2})+x(a_1+a_3{x}^2+...+a_{n-1}{x}^{n-2})$$
 
两边好像非常相似，于是再设两个多项式$A_1(x),A_2(x)$，令
 
$$A_1(x)=a_0+a_{2}x+a_4{x}^2+...+a_{n-2}{x}^{\frac{n}{2}-1}$$$$A_2(x)=a_1+a_{3}x+a_5{x}^2+...+a_{n-1}{x}^{\frac{n}{2}-1}$$
 
比较明显得出
 $$A(x)=A_1(x^2)+x{A}_2(x^2)$$
 
再设$k<\frac{n}{2}$，把${\omega }_n^k$作为$x$代入$A(x)$（接下来几步变换要多想想单位根的性质）
 
$$A({\omega }_n^k)=A_1(({\omega }_n^k{)}^2)+{\omega }_n^k{A}_2(({\omega }_n^k{)}^2)$$$$=A_1({\omega }_n^{2k})+{\omega }_n^k{A}_2({\omega }_n^{2k})=A_1({\omega }_{\frac{n}{2}}^k)+{\omega }_n^k{A}_2({\omega }_{\frac{n}{2}}^k)$$
 
那么对于$A({\omega }_n^{k+\frac{n}{2}})$的话，代入${\omega }_n^{k+\frac{n}{2}}$
 $$A({\omega }_n^{k+\frac{n}{2}})=A_1({\omega }_n^{2k+n})+{\omega }_n^{k+\frac{n}{2}}{A}_2({\omega }_n^{2k+n})$$$$=A_1({\omega }_n^{2k}{\omega }_n^n)-{\omega }_n^k{A}_2({\omega }_n^{2k}{\omega }_n^n)$$$$=A_1({\omega }_n^{2k})-{\omega }_n^k{A}_2({\omega }_n^{2k})=A_1({\omega }_{\frac{n}{2}}^k)-{\omega }_n^k{A}_2({\omega }_{\frac{n}{2}}^k)$$
 
发现了什么？
 
$A({\omega }_n^k)$和$A({\omega }_n^{k+\frac{n}{2}})$两个多项式后面一坨东西只有符号不同
 就是说，如果已知$A_1({\omega }_{\frac{n}{2}}^k)$和$A_2({\omega }_{\frac{n}{2}}^k)$的值，我们就可以同时知道$A({\omega }_n^k)$和$A({\omega }_n^{k+\frac{n}{2}})$的值
 现在我们就可以递归分治来搞$FFT$了
 
每一次回溯时只扫当前前面一半的序列，即可得出后面一半序列的答案
 $n==1$时只有一个常数项，直接$return$
 时间复杂度$O(n{\log }_{2}n)$
 
 
IFFT（快速傅里叶逆变换）
 
想一下，我们不仅要会$FFT$，还要会IFFT（快速傅里叶逆变换）
 我们把两个多项式相乘 （也叫求卷积），做完两遍$FFT$也知道了积的多项式的点值表示
 可我们平时用系数表示的多项式，点值表示没有意义
 
 
怎么把点值表示的多项式快速转回系数表示法？
 
 
$IDFT$暴力$O(n^2)$做？其实也可以用$FFT$用$O(n{\log }_{2}n)$的时间搞
 
 
你有没有想过为什么傅里叶是把${\omega }_n^k$作为$x$代入而不是别的什么数？
 原因是有的但是有我也看不懂
 由于我是沙雕所以只用记住一个结论
 
一个多项式在分治的过程中乘上单位根的共轭复数，分治完的每一项除以$n$即为原多项式的每一项系数
 
意思就是说$FFT$和$IFFT$可以一起搞
 
 
朴素版FFT板子
 
$c++$有自带的复数模板$complex$库
 $a.real()$即表示复数$a$的实部
 
#include<complex>
#define cp complex<double>

void fft(cp *a,int n,int inv)//inv是取共轭复数的符号
{
    if (n==1)return;
    int mid=n/2;
    static cp b[MAXN];
    fo(i,0,mid-1)b[i]=a[i*2],b[i+mid]=a[i*2+1];
    fo(i,0,n-1)a[i]=b[i];
    fft(a,mid,inv),fft(a+mid,mid,inv);//分治
    fo(i,0,mid-1)
    {
        cp x(cos(2*pi*i/n),inv*sin(2*pi*i/n));//inv取决是否取共轭复数
        b[i]=a[i]+x*a[i+mid],b[i+mid]=a[i]-x*a[i+mid];
    }
    fo(i,0,n-1)a[i]=b[i];
}
 
两个多项式$a,b$相乘再转系数多项式$c$，通常只用打这么一小段
 
	cp a[MAXN],b[MAXN];
	int c[MAXN];
	fft(a,n,1),fft(b,n,1);//1系数转点值
	fo(i,0,n-1)a[i]*=b[i];
	fft(a,n,-1);//-1点值转系数
	fo(i,0,n-1)c[i]=(int)(a[i].real()/n+0.5);//注意精度
 
很明显，FFT只能处理$n$为$2$的整数次幂的多项式
 所以在$FFT$前一定要把$n$调到$2$的次幂
 
这个板子看着好像很优美，但是
 
 
 
 
 
递归常数太大，要考虑优化…
 
 
FFTの优化——迭代版FFT
 
这个图也是盗的
 
 
 
 
 
这个很容易发现点什么吧？
 
每个位置分治后的最终位置为其二进制翻转后得到的位置
 
这样的话我们可以先把原序列变换好，把每个数放在最终的位置上，再一步一步向上合并
 一句话就可以$O(n)$预处理第$i$位最终的位置$rev[i]$
 
fo(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
 
至于蝴蝶变换它死了其实是我不会
 
 
真·FFT板子
 
void fft(cp *a,int n,int inv)
{
    int bit=0;
    while ((1<<bit)<n)bit++;
    fo(i,0,n-1)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        if (i<rev[i])swap(a[i],a[rev[i]]);//不加这条if会交换两次（就是没交换）
    }
    for (int mid=1;mid<n;mid*=2)//mid是准备合并序列的长度的二分之一
    {
    	cp temp(cos(pi/mid),inv*sin(pi/mid));//单位根，pi的系数2已经约掉了
        for (int i=0;i<n;i+=mid*2)//mid*2是准备合并序列的长度，i是合并到了哪一位
		{
            cp omega(1,0);
            for (int j=0;j<mid;j++,omega*=temp)//只扫左半部分，得到右半部分的答案
            {
                cp x=a[i+j],y=omega*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;//这个就是蝴蝶变换什么的
            }
        }
    }
}
 
这个板子好像不是那么好背
 至少这个板子已经很优美了
 
 
FFT后记
 
本人版权意识薄弱……
 
 
 
 
本博客部分知识学习于
 
 
https://www.cnblogs.com/RabbitHu/p/FFT.html
 
 
https://www.cnblogs.com/zwfymqz/p/8244902.html?mType=Group#_label3
 
 
https://blog.csdn.net/ggn_2015/article/details/68922404
 
 
 
$NTT$我来了

离散二维傅里叶变换
一常用性质：
       可分离性、周期性和共轭对称性、平移性、旋转性质、卷积与相关定理；
（1）可分离性：
   二维离散傅里叶变换DFT可分离性的基本思想是DFT可分离为两次一维DFT。因此可以用通过计算两次一维的FFT来得到二维快速傅里叶FFT算法。根据快速傅里叶变换的计算要求，需要图像的行数、列数均满足2的n次方，如果不满足，在计算FFT之前先要对图像补零以满足2的n次。
   一个M行N列的二维图像f(x,y)，先按行队列变量y做一次长度为N的一维离散傅里叶变换，再将计算结果按列向对变量x做一次长度为M傅里叶变换就可以得到该图像的傅里叶变换结果，如式所示：
                      

将上式分解开来就是如下的两部分，先得到F(x,v),再由F(x,v)得到F(u,v)：
                        



计算过程如下：


每一行由N个点，对每一行的一维N点序列进行离散傅里叶变换得到F(x,u),再对得到F(x,u)按列向对每一列做M点的离散傅里叶变换，就可以得到二维图像f(x,y)的离散傅里叶变换F(u,v).
同样，做傅里叶逆变换时，先对列向做一维傅里叶逆变换，再对行做一维逆傅里叶变换，如下式所示：


（2）周期性和共轭对称性
由傅里叶变换的基本性质可以知道，离散信号的频谱具有周期性。离散傅里叶变换DFT和它的里变换都以傅里叶变换的点数N为周期的。
对于一维傅里叶变换有：
对于二维傅里叶变换有：
类似有：即从DFT角度来看，反变换得到的图像阵列也是二维循环的。
共轭对称性
对于一维信号有：F(u)=F*(-u),如图所示的一维信号的幅度谱：点数为M的傅里叶变换一个周期为M，关于原点对称。原点即为0频率点，从图中可以看出在0频率的值最大，即信号f(x)的直流分量(均值)，远离原点处的即为高频成份，高频成份的幅值较小，说明信号的大部分能量集中在低频部分。


对于二维信号有：F(u,v)=F*(-u,-v)对于二维图像，其结果如图c所示。左上角(0,0)处为二维图像得0频率点，该点得值对应图像的平均灰度值，图中四个角对应低频成分，中间区域为高频成份，低频区域的幅度值打羽高频区域的幅度值，也同样表示该信号的主要能量集中在低频区域。


根据周期性和共轭对称性，在对图像进行频谱分析处理时只需要关注一个周期就可以了，同时利用图像的傅里叶变换和傅里叶变换的共轭可以直接计算图像的幅度谱，因此使得图像的频谱计算和显示得以简化。
（3)平移性：
傅里叶变换对有如下平移性质：


式子表明，
在频域中原点平移到(u0 ,v0)时，其对应的空间域 f(x,y)要乘上一个正的指数项：
                             

在空域中图像原点平移到(x0,y0)时，其对应的F(u,v)要乘上一个负的指数项：
                              

在数字图像处理中，常常需要将F(u,v)的原点移到N*N频域的中心，以便能清楚地分析傅里叶谱的情况，平移前空域、频域原点均在左上方。要做到这点，只需令上面平移公式中的：u0=v0=N/2；


所以
上式表明：如果需要将图像傅里叶谱的原点从左上角(0,0)移到中心点(N/2,N/2),只要f(x,y)乘上因子进行傅里叶变换即可实现。
平移性还体现了：当空域中f(x,y)产生移动时，在频域中只发生相移，并不影响他的傅里叶变换的幅度，因为：
                                        

反之，当频域中F(u,v)产生移动时，相应f(x,y)在空域中也只发生相移，不产生幅值变化。根据平移性质，为了更清楚查看二维图像的频谱，使直流成分出项在图像中央，在把画面分成四分的基础上，进行如图所示的换位(移位)也是可以的，这样，频域原点就回平移到中心。如下所示：



（4）旋转性质

如果 f(x,y)旋转了一个角度，那么 f(x,y)旋转后的图像的傅立叶变换也旋转了相同的角度。平面直角坐标改写成极坐标形式：

替换则有：
如果f(x,y)被旋转W,则F(u,v)被旋转同一角度。即有傅里叶变换对：
                            


如下所示：



同时，我们可以得出结论，对图像进行旋转变换和傅立叶变换的顺序是可交换的。即先旋转再傅里叶变换或者先傅里叶变换再旋转，得到的结果相同。F{R{f(x,y)}} = R{F{f(x,y)}}。
（5）卷积与相关定理
卷积定理包括空间域卷积和频率域卷积，卷积是空间域滤波和频率域滤波之间的纽带：两个空域信号的卷积等价于其频域信号的 乘积f(x,y)*h(x,y) → F(u,v)H(u,v) 或者 F{f(x,y)*h(x,y)} = F(u,v)H(u,v)；
两个信号频域上的卷积等价于空间域的相乘f(x,y) g(x,y) →F(u,v)*H(u,v)；

该性质的好处是将需要经过翻折、平移、相乘、求和等步骤实现的复杂的卷积运算简化为简单的乘法运算，这也是快速傅里叶变换（FFT）的出现使得该性质得到更广泛应用，同时，该性质对于理解信号的频率域处理方法特别重要，使得信号的空间域处理可以转换到频率域进行处理实现。
根据空间域卷积定理，在空间域对应的是原始信号与滤波器的冲击响应的卷积，卷积定义式为信号翻折平移求和的过程，步骤复杂，运算量大，但如果转换到频率域进行处理，则对在将二者的频谱直接相乘就可以得到滤波结果，然后对滤波结果进行傅里叶逆变换就可以得到滤波后的空间域域图像。如下图所示，对信号进行低通和高通滤波处理的过程和效果。


相关定理：
空域中 f(x,y)与 与 g(x,y) 的相关等价于频域中 F(u,v) 的共轭与 G(u,v)  相乘f(x,y) g(x,y) → F*(u,v)G(u,v)
同时有：f*(x,y)g(x,y) → F(u,v) G(u,v)
相关定理与卷积定理类似，也是把积分求和过程转化为了频域相乘，因此，也使得相关分析的计算简化。
相关的重要应用在于匹配：确定是否有感兴趣的物体区域。f(x,y)是原始图像，g(x,y)作为感兴趣的物体或区域（模板），如果匹配，两个函数的相关值会在 f 中找到相应 g 点的位置上达到最大值。如下图所示。图像 f(x,y) 与模板 g(x,y)，通过计算相关函数，在匹配点处达到最大值，如图中红色圆圈标注的区域。




延拓图像 f(x,y)，延拓图像 g(x,y)，相关函数图像，通过相关图像最大值的水平灰度剖面图。

傅里叶变换的实例与应用
首先我们认识几点有关傅里叶变换的特点：
l 傅里叶变换是从将图像从空间域变换到频率域，具有明确的物理意义。图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度，在噪声点和图像边缘处的频率为高频。
l 在频率域中，将信号表示为一系列正弦信号或者复指数函数的叠加，正弦信号的频率、幅值和相位可以描述正弦信号中的所有信息，由此可以得到信号的幅度谱和相位谱。在图像领域就是将图像灰度作为正弦变量。
l 傅里叶变换全局性的，是一个积分求和的过程，对时间、地点位置无法进行准确定义，也就是说傅里叶变换得到的频谱图中的点无法与空间域中的某个空间位置对应，因此，从傅里叶变换图中并不能直接对应某个位置的特点。
l 傅里叶变换是一系列不同频率三角函数的和，每个频率分量的系数不同，这些系数代表了各频率成分的强弱或者所占比重，通过分析这些系数就可以分析图像的特性。

最近结束了一门课，叫《基于波动理论的目标探测》。名字如此高深，实际上还是还是在讲信号处理的一些知识。其中的核心内容是加窗傅里叶变换（或者叫短时傅里叶变换）。这里也想说一说自己的一些理解。
 
从傅里叶变换到加窗傅里叶变换
 
傅里叶变换是我们所熟悉的，它把我们所要分析的信号从时间域变换到了频率域，这样最大的好处是能让我们看的更清楚信号是由哪些些基本的“原子”所组成的。这些“原子”其实就是三角级数，或者说是我们所熟悉的：$e^{j{\omega}t}$，这样的变换能够告诉我们原始信号的频谱，这无疑是非常好的工具。但我们现在来看个例子： 
 在matlab的命令窗口中输入xpsound我们观察其中的任意一个信号都会发现，尽管我们能够从时间上一眼看处声音的频率其实是在一个局部有一个固定的频率而在另外的一个局部又有另外一个固定的频率。然而在其中我们看每一个信号的幅度谱（或者能量谱）都无法看处这一点。 
 我们再来说的更形象一些，如果一个美妙的音乐片段，它是在不同的时间由不同的音符所组成的，我们清楚地知道在不同位置（时间）有不同的音符（频率）。然而我们却不能够通过傅里叶变换的手段来轻松获得这一分析。原因正是因为我们取得的时间片段太长了，以至于这些不同频率的内容都混杂在了一起所以不能够区分开来。那么解决的办法也很简单，就是把原来的片段“切成”每个音符的大小（假定每个音符持续的时间都一样）的小片段，再在每个小片段上做傅里叶变换。这样我们能够直接定位到频率随时间的变化。这种想法和思路实际上就是加窗傅里叶变换。从傅里叶变换到加窗傅里叶变换就是这样过度过来的。
 
如何实现加窗傅里叶变换（WFT）
 
后面为了书写方便，我们暂时都把加窗傅里叶变换叫做是WFT。有了上面的一些基础的加窗傅里叶变化的由来，其实还是很容易想到实现加窗傅里叶变换的方法的。 
 我们还是从傅里叶变换（FT）出发来导出WFT的表达式，在FT中我们熟悉它的表达式是 
 
 $$F(j\omega)  = \int^{\infty}_{-\infty}f(t)e^{-j\omega t}dt$$  

 根据上面所说的WFT的由来，其实我们是不难推出它的表达式的： 

 首先，待分析的信号是

$f(t)\in L^2(R)$它的意思就是说

$f(t)$是一个能量有限的信号，窗函数

$g(t)\in L^2(R)$也是能量有限的信号。我们记

$\bar g(t)$是窗函数

$g(t)$的共轭（这里我们可以先把窗理解成是一个实函数，它的共轭和它本身是一回事儿，写成共轭形式对于一会儿另外一个概念有用）。 

 那么WFT的思路就是，先用窗的不同的时移去截取信号，即 

 

 $$f_t(u) = \bar g(u-t)f(u)$$  

 再对截取的信号取傅里叶变换，我们把变换的结果记为

$\widetilde f(\omega ,t)$,则变换结果为（这里的频率单位是Hz，并且我们还是记为

$\omega$，下同） 

 

 $$\widetilde f(\omega ,t) = \int^{\infty}_{-\infty} \bar g(u-t)f(u)e^{2\pi j \omega u}du$$  

 这样我们可以想象得来此时的

$\widetilde f(\omega ,t)$是一个二维信号，并且它能够从频率和时间两个维度去刻画一个信号。而且一个直观的感受是，我们所说的“窗”如果取得越细密，那么好像可以刻画出信号的刻画的更加完美，但实际上一个极端特例就是“窗”细的不能更细，变成了一个冲击，那么不就变成了连续不断的采样？这么来说在t这个维度上看，每个t都是一个白谱，那么WFT也就失去了意义。这告诉我们，显然不可以把这个时间的“窗”开的很细，否则频率域去看会是很大一片（分辨率极低），这也从另一个角度刻画了时间和频率只能折衷，而不能二者都取得性能极佳！
 
时频局域化与不确定性定理
 
实际上从数学的表达式上，也可以去刻画上面我们所描述的时频分辨率这一特性。 
 我们先定义两个概念：时间的“重心”和频率的“重心”。 
 对于窗函数$g(t)$以及它对应的傅里叶变换$\hat g(\omega)$分别有如下的定义： 
 
 $$t_0 = \frac{1}{{\Vert g(t)\Vert}^2} \int^{\infty}_{-\infty}t{\vert g(t)\vert}^2 dt$$  

 

 $$\omega_0 = \frac{1}{{\Vert {\hat g(\omega)}\Vert}^2} \int^{\infty}_{-\infty}\omega{\vert{\hat g(\omega)}\vert}^2 d\omega$$  

 窗嘛一般来说都是有一个能量聚集中心的，不可能是像噪声那样不规则分布的，所以有一个指标就很重要了，它能够从某种角度说明“分辨率”这个概念，它就是标准差。直观的想如果标准差越大，那么在这个维度上它的能量是分散，所以分辨率自然也不会高，反之亦然。 

 时间和频率的标准差分别如下 

 

 $$T^2 = \frac{\int^{\infty}_{-\infty}{(t-t_0)}^2{\vert g(t)\vert}^2dt}{\int^{\infty}_{-\infty}{\vert g(t)\vert}^2dt}$$  

 

 $$\Omega^2 = \frac{\int^{\infty}_{-\infty}{(\omega-{\omega}_0)}^2{\vert {\hat g(\omega)}\vert}^2d\omega}{\int^{\infty}_{-\infty}{\vert {\hat g(\omega)}\vert}^2d\omega}$$  

 下面这个图叫时频盒子图，它形象地用图像的形式给出了描述了上述的时间和频率分辨率的方法 

 
 

 显然我们都希望在时间和频率的分辨率都能够越高越好，但是瓶颈在于我们已经知道不可能达到两者的分辨率都很好，所以我们试图去折衷。 

 如果能够让

$T\Omega$尽可能的小，那么我们就认为达到了目的。已经证明了，当窗函数

$g(t) = e^{-t^2}$中所谓的高斯窗的形式时，能够让

$T\Omega$尽可能的小，譬如

$g(t) = (2a)^{\frac{1}{4}}e^{-\pi at^2}$他满足能量的归一化，即

$\Vert g\Vert = 1$。在这种情况下

$\hat g(\omega) = (\frac{2}{a})^2e^{-\pi {\omega}^2/a}$，并且

$T\Omega = \frac{1}{4\pi}$对于其他形式的窗函数，

$T\Omega \gt \frac{1}{4\pi}$。这也正是我们窗函数为什么要选择高斯窗的原因。
 
从“原子”的角度来理解WFT
 
在上面我们说道傅里叶变换是要看看一个信号是由哪些基本的“原子”所构成的。这也从另一个角度说明了傅里叶变换的本质——做投影。把信号投影在一个个“相互正交”的原子上，就获得了信号是由每个多大的“原子”所构成的。那么WFT既然是从FT演化而来的，我们能不能以相同的角度来理解呢？答案是肯定的。 
 再回到WFT的表达式： 
 
 $$\widetilde f(\omega ,t) = \int^{\infty}_{-\infty} \bar g(u-t)f(u)e^{2\pi j \omega u}du$$  

 对比傅里叶变换的表达式： 

 

 $$F(j\omega)  = \int^{\infty}_{-\infty}f(t)e^{-j\omega t}dt$$  

 对于FT它的原子是

$e^{j\omega t}$，那么很自然的WFT的原子就是： 

 

 $$g_{\omega,t}(u) = e^{2\pi j\omega u}g(u-t)$$  

 同样的，其实求解WFT的过程也是一个“投影”（内积）的过程，在

$L^2(R)$空间中，内积的表达式为： 

 


 
  
   <f,g>=∫∞−∞f(t)g¯(t)dt
  
<script type="math/tex; mode=display" id="MathJax-Element-7436">

  = \int^{\infty}_{-\infty}f(t)\bar g(t)dt</script> 
 
 他有三个比较重要的性质，分别是三角不等式: 
 
 
 
  $$\vert<f,g>\vert \le \Vert f\Vert\Vert g\Vert$$  
 
 Plancherel定理（其实就是能量守恒定理）： 
 
 
 
  $$\Vert f\Vert = \Vert {\hat f}\Vert$$  
 
 两个域中的能量是一定的。 
 
 以及它的一个推广Parseval恒等式（时域内积等于频域内积）： 
 
 
 
 

  
   
    <f,g>=<f^,g^>
   
 
<script type="math/tex; mode=display" id="MathJax-Element-7439">
 
   = <\hat f,\hat g></script> 
  
 有了以上的数学铺垫，我们可以轻松写出WFT的投影形式： 
  
 
  
   $$\widetilde f(\omega ,t) = <f(u),g_{\omega ,t}(u)>$$  
  
 并且由Parseval定理，我们还可以得到从频率域来计算WFT 
  
 
  
   $$\widetilde f(\omega ,t) = <\widetilde f,\widetilde g_{\omega ,t}>$$  
  
 其中的
  
  $\widetilde f$，
  
  $\widetilde g_{\omega ,t}$分别是
  
  $f(u)$，
  
  $g_{\omega ,t}(u)$对应的傅里叶变换。 
  
 那么，从频率域得到WFT可以表述为： 
  
 
  
  

   
    
     <f˜,g˜ω,t>=∫∞−∞f˜(v)g˜¯ω,t(v)dv
    
  
<script type="math/tex; mode=display" id="MathJax-Element-7446"><\widetilde f,\widetilde g_{\omega ,t}> = \int^{\infty}_{-\infty}\widetilde f(v)\bar{\widetilde g}_{\omega ,t}(v)dv</script> 
  
 
  
   $$= \int^{\infty}_{-\infty}\widetilde f(v)e^{-2\pi jv t}\bar{\widetilde g}_{\omega ,t}(v-\omega)dv$$  
  
 看这个形式是不是非常像有一个频率的窗叫
  
  $\widetilde g_{\omega ,t}$，它在频率域与原始信号相乘（加窗），然后再做一个傅里叶变换呢（此时的积分变量是频率，此处我们用v来表示）？ 
  
 以上内容说明了一个事实，那就是WFT仍然是一个分解原子的过程，只不过原子不再是之前FT中简单的原子了，而变成了窗函数的时移再乘以一个复数调制
  
  $e^{2\pi j \omega t}$。
  
 
  
关于高斯窗
 
  
最后关于WFT，我们再来说说为什么要选用高斯窗。上面已经给过了一个最有力的条件，但是其实他还有几个好处。
 
  
它是一种平滑的函数，这相比于一个我们熟悉的矩形窗就要好很多，它能够避免频率域的震荡。
它是一种从零开始平滑到极值再平滑地衰落到0的函数，这符合一个我们常见信号的特点——平滑到增长到极大值然后再平滑地衰落。
它的FT也是一个高斯函数。
它是偶对称的，有很多非常良好的性质。
 
  
其实高斯窗的应用非常广泛，图像处理中也经常使用到它。我个人认为，它是一种最接近实际真实信号的一个有力模型，它的很多性质比如平滑，以及增加和衰落的过程都能比其他信号更好地描述真实情况。这是它应用广泛的原因。 
 （注：我所说的常见信号，比如像音乐，或者是图像的亮度信号，他们都有一定的持续期，但是由于惯性，它们都不可能立刻跳到极值（或者稳定值），都有一个充能以及在衰减时候释放能量的过程。选择高斯窗应该说会更好地贴合这个特点。）