# CMOS反相器
## CMOS反相器的结构

CMOS反相器由一个PMOS和一个NMOS组成



<center>
    <img src="/static/img/5db865fb91f62bd74e1b89394e0677a5.image.webp" width=50%>
</center>

其中NMOS的源极s接地，PMOS的源极s接正高压$V_{DD}$

## CMOS反相器的原理

- 如果输入为高电平，即$v_I=V_{DD}$，对于NMOS而言，$V_{GS}=V_{DD}$自然大于临界电压（正），那么NMOS导通；同时对于PMOS而言$V_{GS}=0$也高于临界电压（负），那么PMOS关断。这样$v_o=0$，输出为低电平
- 如果输入为低电平，即$v_I=0$，对于NMOS而言，$V_{GS}=V_0$自然小于临界电压（正），那么NMOS关断；同时对于PMOS而言$V_{GS}=-V_{DD}$低于于临界电压（负），那么PMOS导通。这样$v_o=V_{DD}$，输出为高电平

由于$v_I$只提供栅极电压，实际上并不导通；而反相器输出低电平时，PMOS关断自然没有电流，NMOS漏极输出电压为$0$，源极接地，其电压也为$0$，流过它的电流为$0$。可见当输出电压为零时反相器的功耗极低

## 反相器的传输特性

反相器的电压传输特性是指输出电压与输出电压的关系，电流传输特性是指漏极电流（即由一个漏极流到另一个漏极之间的电流，并不是输出电流）。可以画图如下

![image.png](/static/img/b7fb2936d1eba3d43195fab1f4eb1ca6.image.webp)

定义CMOS反相器的阈值电压为
$$
V_{TH}=\dfrac{V_{DD}}{2}
$$

输入电压在阈值电压附近时，漏极电流较大，需要避免反相器长时间工作在这种状态

# CMOS与非门和或非门
## CMOS与非门
CMOS与非门可以画出如下
<center>
    <img src="/static/img/a4ecfd0a24eb3a8b6ee776a9cfb7a29f.image.webp" width=50%>
</center>

它的工作原理可以这样描述

- 两个并联$PMOS$决定当AB存在一个是低电平时，其中一个导通，输出$L$为高电平
- 两个串联的$NMOS$决定当$AB$都为高电平时，它们都导通，输出$L$为低电平

需要$n$个输入时，只需要将串联的NMOS数目和并联的PMOS数目都变为$n$即可，不过这样会使得导通时的电阻增大

## CMOS或非门
CMOS或非门可以画出如下
<center>
    <img src="/static/img/e6590fc80a0664f20bc057d43fcd736d.image.webp" width=50%>
</center>

它的工作原理和与非门相近，不过将PMOS改为了串联，NMOS改为了并联，因而只有AB都为低电平时它才输出高电平

需要$n$个输入时，同样只需要将串联的NMOS数目和并联的PMOS数目都变为$n$

# CMOS传输门

CMOS传输门的结构如左图，其符号为右图

![image.png](/static/img/39599125499603d10a643a763cd22497.image.webp)

右图上方的小圆圈代表`0有效`，也就是该脚被置为低电平时激活传输门

传输门的原理应当非常显然，在此不多赘述。之所以用两个MOS管，是因为一管越是导通，另一管就越是阻断，这样两个互补的管子并联在一起使得总的电阻变化较小

# 漏极开路门(OD门)

`OD门`是一种“修饰”，当某个逻辑门被称作OD门时，意味着当它输出高电平时，它实际处于**高阻态**，需要一个上拉电阻接到电源$V_{DD}$上才会正常输出高电平。实现OD门只需要加一个MOS管，一个OD与非门的例子是这样的

![image.png](/static/img/c5bb3f2c5600e272c74508584257e352.image.webp)

由于它输出高电平处于高阻态，可以将很多个这样的门并联在一起，实现**线与**

![image.png](/static/img/bdbdc5086f665e2b656cad56c78decb3.image.webp)

如果是普通的与非门，当它们输出一个高电平和低电平时，功耗会相当大；而对于OD门而言，只要有一个OD门输出低电平，输出电压就会被它拉低至低电平，其他的OD门都在高阻态，并不输出电流，因而功耗小

因此OD门可以驱动大电流负载（因为电流不是由OD门输出的），或者实现逻辑电平变换（只要接上一个不一样的$V_{DD}$就行了

不过这个上拉电阻的选择也有讲究

- 并联的OD门只有一个导通，输出低电平，电阻上的电流和外来的输入电流全部进入某个OD门内，它不应超过OD门的最大输入电流，由此给出下拉电阻的最小值
- 并联的OD门都关断，输出高电平，每个OD门都有漏电流，它们与输出电流一起使得电阻上出现压降，此时输出电压不应低于高电平的阈值，由此给出上拉电阻的最大值

实际情况下，如果要求电路速度快，则电阻阻值尽量小；若要求电路功耗小，则阻值尽量大

# 三态门
由于上拉电阻的存在，OD门的速度受限。三态门处理输出高低电平，还可以处于高阻态，这由势能控制。下图是高电平使能三态输出缓冲器的结构和符号

![image.png](/static/img/c614c226c1aebb04874721c702be2539.image.webp)

当使能EN被置为低电平时，会使得$B=1,C=0$，两个MOS管都关断，$L$处于高阻态；而EN为高电平时，输出跟随输入变化

# CMOS电路的参数
## 电压限与噪声限
输入输入的高低电平都应有一定的范围
$$
V_{ILmin}\leq V_{IL}\leq V_{ILmax},\quad V_{IHmin}\leq V_{IH}\leq V_{IHmax}
$$
$$
V_{OLmin}\leq V_{OL}\leq V_{OLmax},\quad V_{OHmin}\leq V_{OH}\leq V_{OHmax}
$$
噪声限是门电路中间级之间允许的扰动范围。$V_{NH}$是高电平允许被减小的量，$V_{NL}$是低电平允许被增大的量，如图

<center>
    <img src="/static/img/ae438d657844b9c8bebadf9f7e53324f.image.webp" width=50%>
</center>

## 传输延迟时间
传输延迟时间是指输入电压跳变中点与输出电压跳变中点之间的时间差。输入从低跳高的延迟称为$t_{pLH}$，由高跳低的延迟称为$t_{pHL}$。由于CMOS电路的对称性，它们一般相等

<center>
    <img src="/static/img/90fda041b6ef04a18f58467067b790d5.image.webp" width=70%>
</center>

对于同一电路而言，传输延迟与电源电压$V_{DD}$成负相关，与负载电容正相关。平均延迟是低跳高与高跳低延迟的平均值，记为$t_{pd}$

## 功耗
CMOS电路的静态功耗很小，功耗来源于动态功耗，即电路状态转换时的功耗。动态功耗有两种来源
- 转换瞬间电流流经MOS管产生的功耗，可以计算如下
  $$
  P_\tau=C_{PD}V_{DD}^2f
  $$
  其中$C_{PD}$为**功耗电容**，是由门电路自身计算得到的等效参数，它与电源电压和工作频率也相关；$f$是输出信号的转换频率
- 电容性负载在高低电平转换时充放电产生的功耗，可以类似计算
  $$
  P_L=C_LV_{DD}^2f
  $$
  其中$C_L$是负载电容
  
功耗是这两个功耗的和
$$
P_D=P_\tau+P_L
$$
可见CMOS电路的功耗正比于频率和电源电压的平方

## 延时-功耗积
鉴于功耗与频率也就是延迟的倒数成正比，那么可以定义**延时-功耗积**
$$
DP=t_{pd}P_D
$$
它越小就表明电路越接近理想情况

## 扇入扇出数
可以定义扇入扇出数
- 扇入数是电路输入端的数目
- 扇出数是电路能带同类门电路的最大数目

扇入数是简单的，考虑扇出数的计算。当电路输出高电平时，电流会由**驱动门**输出。输出电流太大会使得输出电压下降，因而它有最大值。由于它的负载是另一些自己，输入为高电平时，电流会流入**负载门**，输入电流应当是固定的。那么输出高电平的扇出数就有公式
$$
N_{OH}=\dfrac{\text{所有驱动门的输出电流和}I_{OH}}{\text{所有负载门的输入电流和}I_{IH}}
$$

同样，当输出低电平时，输出电流太大会使得输出电压上升，由此给出输出低电平时的扇出数
$$
N_{OL}=\dfrac{\text{所有驱动门的输出电流和}I_{OL}}{\text{所有负载门的输入电流和}I_{IL}}
$$

该公式未考虑电容性负载，因此工作频率增大时应减小扇出数

CMOS逻辑电路

# MOS管

MOS管可以由载流子分为**NMOS**和**PMOS**

- NMOS：电子型，电路流入漏极
- PMOS：空穴型，电流流出漏极

按照栅极电压$V_{GS}=0$时导电沟道是否存在，将MOS管分为**耗尽型**和**增强型**

- 增强型：$V_{GS}=0$时不存在导电沟道，MOS管关断
- 耗尽型：$V_{GS}=0$时存在导电沟道，MOS管导通



# N沟道增强型MOS管

N沟道增强型MOS管的实物图如下

<center>
    <img src="/static/img/6776d20a59b06b5d8a0454fe8dceb9ab.image.webp" width=50%>
</center>

将其简化为符号

<center>
    <img src="/static/img/81a901065188cd3760db8ac8fa7a4643.image.webp" width=30%>
</center>

$P$衬底与源极和漏极形成了两个PN结，相当于两个相反的二级管，正常情况下源极和漏极是不导通的

<center>
    <img src="/static/img/8b413e94b52f910077ef17b4a2c84789.image.webp" width=30%>
</center>

当$V_{GA}$大于临界值（正电压）时，出现N型导电沟道，源极s和漏极d导通。$V_{GS}>0$意味着**电流由漏极d流向源极s**

# N沟道耗尽型MOS管

N沟道耗尽型MOS管的实物图如下

<center>
    <img src="/static/img/cb4b0aa6d23d8a111bccd6b58e7d72cd.image.webp" width=50%>
</center>

将其简化为符号

<center>
    <img src="/static/img/7e35fc2f642f4042fa9758b0012e3ebc.image.webp" width=30%>
</center>

$P$衬底也与源极和漏极形成了两个相反的二级管。与增强型不同的是，在$V_{GS}=0$时源极s和漏极d导通，它大于临界值（正电压）时关断

# P沟道增强型MOS管与P沟道耗尽型MOS管

<center>
    <img src="/static/img/7745a4f55f3d37e0e89a061cddf1a96c.image.webp" width=70%>
</center>

PMOS的衬底是N型半导体，源极和漏极是P型半导体，这意味着两个二极管方向不同

此外，PMOS的临**界电压是负的，电流由源极流向漏极**

# 衬底调制效应（体效应）

为了保证导电沟道与衬底的隔离，需要沟道与衬底之间的PN结反偏。这意味着要求NMOS的$V_{BS}\leq0$，PMOS的$V_{BS}\geq 0$，即NMOS衬底应接在最低电位，PMOS的衬底应接在最高电位

不过如果$|V_{BS}|$太大，使得耗尽层加厚，那么就会让开启沟道的临界电压增大

MOS管

# 01背包
有$N$个物品和一个容量为$V$的背包, 物品有两个属性: 价值和体积
$$
\text{第}i\text{个物品的价值为}w_i,\text{体积为}v_i
$$

体积为整数


状态定义为
$$
f(i,j)=\text{只考虑前}i\text{件物品,背包容量为}j\text{时能获取的最大价值}
$$

状态转移方程可以这样考虑:考察状态$f(i,j)$, 对于$i$个物品可以选择拿走或者不拿走, 如果不拿走则
$$
f(i,j)=f(i-1,j)
$$
拿走则需要腾出$v_i$的空间,即上一步只有$j-v_i$的空间可以用
$$
f(i,j)=f(i-1,j-v_i)+w_i
$$
由此得到状态转移方程
$$
f(i,j)=\max\{f(i-1,j), f(i-1,j-v_i)+w_i\}
$$
鉴于$f(i,j)$只依赖于$i-1$的状态, 可以使用滚动数组减小空间开销

# 多重背包
有$N$种物品和一个容量为$V$的背包, 物品有三个属性: 数量,价值和体积
$$
\text{第}i\text{种物品的价值为}w_i,\text{体积为}v_i, \text{数量为}s_i
$$
状态依然定义为
$$
f(i,j)=\text{只考虑前}i\text{件物品,背包容量为}j\text{时能获取的最大价值}
$$
考察状态$f(i,j)$时, 需要遍历拿$0$个,拿$1$个, ... ,拿$s_i$个情况, 那么状态转移方程就是
$$
f(i,j)=\max\{f(i-1,j-k\cdot v_i)+k\cdot w_i\},\quad k=0,1,\cdots,s_i
$$
鉴于$f(i,j)$只依赖于$i-1$的状态, 可以使用滚动数组减小空间开销

---

也可以将其转化为01背包问题, 即将第$i$种物品变为$s_i$件物品. 不过这样朴素地转化, 时间复杂度是相同的, 这不好. 可以优化的点在于考虑了多种相同的情况
$$
0,0,1,1\text{与}0,1,0,1\text{拿的数目是相同的}
$$
一种聪明的方式是利用二进制拆分物品, 像这样
$$
1,2,4,\cdots 2^n
$$
任一拿物品的方案都可以用这些物品组的拿与不拿状况唯一表示, 这样就去除了重复的情况, 时间复杂度将为了
$$
V\sum \log s_i
$$

# 完全背包
有$N$种物品和一个容量为$V$的背包, 物品有两个属性: 价值和体积
$$
\text{第}i\text{种物品的价值为}w_i,\text{体积为}v_i
$$
每种物品的数目无限多

一种朴素的做法是如多重背包一般
$$
f(i,j)=\max\{f(i-1,j-k\cdot v_i)+k\cdot w_i\},\quad k=0,1,\cdots
$$
不过这里的$k$选择并没有上限, 唯一约束是不能超过背包容量. 这样做显然复杂度很大, 可以考虑与多重背包相同的二进制优化方案
$$
1, 2, 4, \cdots, 2^k\quad k=\log V/v_i
$$
这样就能将复杂度大大降低

背包问题:01背包,多重背包,完全背包

# 系数表示法与点值表示法
一个$N$次多项式有$N+1$个系数, 它们可以唯一确定这个多项式; 此外可以取$N+1$个点, 计算多项式在这些点的值; 这样$N+1$个不同的键值对也可以唯一确定一个$N$次的多项式

在计算多项式乘法时, 系数表示法需要$O(n^2)$的时间复杂度, 而点值表示法只需要$O(n)$的复杂度. 这是因为两个多项式乘积在一点的值等于它们俩在这点值的乘积

如果能有很快的方法在系数表示法与点值表示法之间转换, 将能极大地加速多项式乘法



# 单位根与FFT

首先将系数表达式转化为点值不能朴素地计算, 这是因为计算一个点值需要$N$次乘法, 这样复杂度仍然是$O(n^2)$, 没有意义. 不过若是取单位根
$$
x_k=e^{2k\pi/N}
$$

它的任意次方都可以以常数复杂度求出, 而不用进行乘法
$$
x_k^m=e^{2mk\pi/N}
$$

如果有多项式
$$
f(x)=a_0+a_1x+\cdots+a_Nx^N=\sum_{n=0}^{N-1} a_kx^n
$$

那么
$$
f(x_k)=\sum_{n=0}^{N-1} a_ke^{i2\pi nk/N}
$$

这个形式容易让人想起一位故人, 因而不妨取单位根是负指数,那么不妨再直接一点
$$
f(x_k)=\sum_{n=0}^{N-1} a_ke^{-i2\pi nk/N}=DFT\{a\}[k]
$$

因而

:::info{title="Note"}
点值表示是系数表示的离散傅里叶变换
:::

而FFT的复杂度是$O(n\log n)$, 这就实现了加速

自然, 将点值表示还原回系数表示, 也只需要进行傅里叶逆变换
$$
a_k=IDFT\{x\}[k]
$$
进行傅里叶逆变换也可以由FFT以$O(n\log n)$的复杂度完成

FFT加速多项式乘法

# 傅里叶变换与离散傅里叶变换DFT
一个时域上的函数 $x(t)$ 其傅里叶变换定义为
$$
\tilde{X}(\omega)=\int_{-\infty}^{+\infty}x(t)e^{-i\omega t}d t
$$
如果用频率表示, 将$\omega=2\pi f$代入可得
$$
\tilde{X}(f)=\int_{-\infty}^{+\infty}x(t)e^{-i2\pi f t}d t
$$



对于计算机而言, 记录的下来的函数是对真实函数的**采样**. 如果记采样的时间周期为$T$, 那么采样得到的离散函数自变量应当是采样轮次
$$
x[n]=x(nT)
$$

为了得到离散傅里叶变换, 需要具体地描述采样的过程. 利用$\delta$函数
$$
\delta_s(t)=\sum_{-\infty}^{+\infty}\delta(t-nT)
$$

将它与$x(t)$相乘得到采样后的信号
$$
x_s(t)=\sum_{-\infty}^{+\infty}x(t)\delta(t-nT)
$$
它在除了采样点$nT$之外的点都为零, 虽然在采样点取值正无穷, 但是鉴于
$$
\int_{-\infty}^{+\infty}x(t)\delta(nT)=x(nT)
$$

如果认为采样的过程是对一段段的时间积分,即
$$
x[n]=\int_{nT-T/2}^{nT+T/2}x(t)dt
$$

那么确实有
$$
x[n]=\int_{nT-T/2}^{nT+T/2}x_s(t)dt
$$

当$nT$包含在积分区间内时,积分就为$x(nT)$,否则为零. 因而认为$x_s(t)$是$x[n]$在连续下的形式, 对$x[n]$做傅里叶变换就是在对$x_s(t)$做傅里叶变换. 鉴于$\delta$函数性质优良, 那么
$$
X_s(\omega)=\int_{-\infty}^{+\infty}\left(\sum_{-\infty}^{+\infty}x(t)\delta(t-nT)\right)e^{-i\omega t}dt=\sum_{-\infty}^{+\infty}x(nT)e^{-i\omega nT}
$$

不过显然不可能进行无穷多次采样. 假定在$0\sim t_0$的时间内进行$N$次采样,采样间隔为$T$, 其余未采样的地方视为周期的, 即将$x(t)$视为周期函数

$$
x(t)=\begin{cases}
x(t)&t\in[0,t_0)\\
x(t+kt_0)&\text{其他},k\in \mathbb{N}
\end{cases}
$$

那么它可以进行傅里叶级数展开
$$
x(t)=\sum_{-\infty}^{+\infty}e^{i2\pi n t/t_0}\dfrac{1}{t_0}\int_0^{t_0}x(t)e^{-i2\pi nt/t_0}dt
$$

这说明它的傅里叶变换是离散的
$$
X(\omega)=\sum_{-\infty}^{+\infty}2\pi\delta(\omega-n\omega_0)\dfrac{1}{t_0}\int_0^{t_0}x(t)e^{-in\omega_0 t}dt,\quad \omega_0=\dfrac{2\pi}{t_0}
$$

利用$\omega=2\pi f$将其写为频率
$$
X(f)=\sum_{-\infty}^{+\infty}\delta(f-nf)f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt,\quad f_0=\dfrac{1}{t_0}
$$


将周期的$x_s(t)$代入后式得到
$$
f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt=f_0\sum_{k=0}^{N-1}x(kT)e^{-i2\pi n kTf_0}
$$
鉴于$f_0=1/t_0=1/NT$,那么

$$
f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt=f_0\sum_{k=0}^{N-1}x(kT)e^{-i2\pi n k/N}
$$

记

:::info{title="离散傅里叶变换DFT"}
$$
X[n]=\sum_{k=0}^{N-1}x[k]e^{-i2\pi n k/N}
$$
:::

鉴于$e^{-2\pi nk/N}$的周期性, 只需要计算$0<n<N-1$即可

# FFT的数学基础
根据DFT的表达式不难发现, 如果进行朴素的乘法, 求解一个$X[n]$复杂度为$O(n)$, 求解全部$N$个的复杂度为$O(n^2)$

不过稍加分析,不难发现求解的主要复杂度在于后面的相位项
$$
W[n,k]=\exp\left\{-i\dfrac{2\pi}{N}nk\right\}
$$

由于$k$与$x[k]$相联系, 从$n$处想办法. 注意到
$$
W[n+N/2,k]=\exp\left\{-i\dfrac{2\pi}{N}nk\right\}\exp\left\{-i\pi k\right\}
$$

这意味着当$k$为偶数时有
$$
W[n+N/2,k]=W[n,k]
$$

因而计算$X[n]$时考虑将$n$分奇偶
$$
X[n]=\sum_{k=0}^{N-1}x[k]W[n,k]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k+1]
$$

后面的$2k+1$不是偶数, 就把它变成偶数, 利用
$$
W[n,2k+1]=W[n,1]W[n,2k]
$$

那么
$$
X[n]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+W[n,1]\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k]
$$

鉴于$W[n+N/2,k]=W[n,k]$, 那么
$$
X[n+N/2]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+W[n+N/2,1]\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k]
$$

不好处理的是$W[n+N/2,1]$, 不过不难发现
$$
W[n+N/2,1]=\exp\left\{-i\dfrac{2\pi}{N}n-\pi i\right\}=-\exp\left\{-\dfrac{2\pi}{N}n\right\}=-W[n,1]
$$

这就意味着

:::info{title="递推式1"}
$$
X[n+N/2]=X[n]\text{的偶数部分}-W[n,1]\cdot X[n]\text{的奇数部分}
$$
:::


这告诉我们, 知道了$X[n]$的偶数部分就等于知道了$X[n+N/2]$的偶数部分, 奇数也一样;

---

下一步是求解奇数和偶数部分. 先考察偶数部分
$$
\sum_{k=0}^{N/2-1}x[2k]W[n,2k]
$$

记$N'=N/2$, 将偶数位置单独挑出来合成一份$N'$长度的序列, 得到$x'[k],k=0\sim N'$, 那么
$$
W[n,2k]=\exp\left\{-i\dfrac{2\pi}{N}n2k\right\}=\exp\left\{-i\dfrac{2\pi}{N'}nk\right\}=W'[n,k]
$$

那么就可以将偶数部分改写为
$$
X[n]\text{的偶数部分}=\sum_{k=0}^{N'-1}x'[k]W'[n,k]
$$
这不正好是偶数序列$x'[k]$的傅里叶变换. 再考察奇数部分
$$
\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k+1]
$$
如法炮制,令$N'=N/2$, 将奇数位置挑出来合成$x'[k]$, 那么
$$
W[n,2k+1]=W[n,1]W[n,2k]=W[n,1]W'[n,k]
$$
那么就可以将奇数部分改写为
$$
X[n]\text{的奇数部分}=W[n,1]\sum_{k=0}^{N'-1}x'[k]W'[n,k]
$$
进而得到奇数部分和偶数部分的递推式

:::info{title="递推式2"}
$$
X[n]\text{的偶数部分}=DFT\{x的偶数序列\}[n]
$$
$$
X[n]\text{的奇数部分}=W[n,1]DFT\{x的奇数序列\}[n]
$$
:::

# 快速傅里叶变换FFT算法

0. 初始化长度为$N$的序列$x^{(0)}$
1. 对于当前序列$x^{(m)}$, 求解它的FFT只需要求解前半部分的奇数和偶数部分, 后半部分即可由递推式自然得到
   $$
   X[n+N/2]=X[n]\text{的偶数部分}-W[n,1]\cdot X[n]\text{的奇数部分}
   $$
2. 求解前半部分$n=0\sim N/2-1$, 利用递推式
   $$
   X[n]\text{的偶数部分}=DFT\{x的偶数序列\}[n]
   $$
   $$
   X[n]\text{的奇数部分}=W[n,1]DFT\{x的奇数序列\}[n]
   $$
   问题转化为分别求解奇偶序列的FFT

如此, FFT是一种二分法, 其时间复杂度为$O(n\log n)$

# 快速逆傅里叶变换IFFT
注意到
$$
x[n]=\dfrac{1}{N}\sum_{k',k=0}^{N-1}x[k]e^{-i2\pi n(k-k')/N}=\dfrac{1}{N}\sum_{k'=0}^{N-1}X[k']e^{i2\pi nk'/N}
$$

因而定义离散傅里叶逆变换IDFT

:::info{title="离散傅里叶逆变换IDFT"}
$$
x[n]=\dfrac{1}{N}\sum_{k=0}^{N-1}X[k]e^{i2\pi nk/N}
$$
:::

它长得跟DFT一样,只不过将$i$改为了$-i$,并除了个$N$, 那么计算IFFT实际上只需要
$$
IFFT\{X\}=\dfrac{1}{N}FFT\{X;i\to -i\}
$$