离散傅里叶变换

离散傅里叶变换（英语：Discrete Fourier Transform，缩写为DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。

在形式上，变换两端（时域和频域上）的序列都是的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换计算DFT。

离散傅里叶变换，是连续傅里叶变换在离散样本上的类比，目前广泛应用于信号处理、数值分析、数位通信、音讯处理等领域，在快速算法问世，以及硬件设备的提升后，能够更广泛的应用在人们的日常生活当中，也是个非常重要的学问之一。

定义

对于${\displaystyle N}$点序列${\displaystyle \left\{x[n]\right\}_{0\leq n<N}}$，它的离散傅里叶变换（DFT）为

${\displaystyle {\hat {x}}[k]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}nk}x[n]\qquad k=0,1,\ldots ,N-1.}$

其中${\displaystyle e}$是自然对数的底数，${\displaystyle i}$是虚数单位。通常以符号${\displaystyle {\mathcal {F}}}$表示这一变换，即

${\displaystyle {\hat {x}}={\mathcal {F}}x}$

离散傅里叶变换的逆变换（IDFT）为：

${\displaystyle x\left[n\right]={1 \over N}\sum _{k=0}^{N-1}e^{i{\frac {2\pi }{N}}nk}{\hat {x}}[k]\qquad n=0,1,\ldots ,N-1.}$

可以记为：

${\displaystyle x={\mathcal {F}}^{-1}{\hat {x}}}$

实际上，DFT和IDFT变换式中和式前面的归一化系数并不重要。在上面的定义中，DFT和IDFT前的系数分别为${\displaystyle 1}$和${\displaystyle {\frac {1}{N}}}$。有时会将这两个系数都改成${\displaystyle {\frac {1}{\sqrt {N}}}}$。

从连续到离散

连续时间信号${\displaystyle x(t)}$以及对应的连续傅里叶变换${\displaystyle {\hat {x}}(\omega )}$都是连续函数。由于数位系统只能处理有限长的离散信号，因此必须将${\displaystyle x}$和${\displaystyle {\hat {x}}}$都离散化，并且建立对应的傅里叶变换。

假设${\displaystyle x(t)}$时限于${\displaystyle [0,L]}$，再通过时域采样将${\displaystyle x(t)}$离散化，就可以得到有限长离散信号，记为${\displaystyle x_{discrete}(t)}$。设采样周期为${\displaystyle T}$，则时域采样点数${\displaystyle N={\frac {L}{T}}}$。

${\displaystyle x_{discrete}(t)=x(t)\sum _{n=0}^{N-1}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)\delta (t-nT)}$

它的傅里叶变换为

${\displaystyle {\hat {x}}_{discrete}(\omega )=\sum _{n=0}^{N-1}x(nT){\mathcal {F}}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)e^{-in\omega T}}$

这就是${\displaystyle x(t)}$在时域采样后的连续傅里叶变换，也就是离散时间傅里叶变换，它在频域依然是连续的。

下面将频域信号转化为有限长离散信号。与对时域信号的处理类似，假设频域信号是带限的，再经过离散化，即可得到有限长离散信号。依据采样定理，频域采样若要能完全重建原信号，频域信号${\displaystyle {\hat {x}}(\omega )}$应当带限于${\displaystyle (0,{\frac {1}{2T}})}$。由于时域信号时限于${\displaystyle [0,L]}$，由采样定理以及时频对偶的关系，频域的采样间隔应为${\displaystyle 1/L}$。故，频域采样点数为：

${\displaystyle {\frac {1/T}{1/L}}=N}$

即频域采样的点数和时域采样同为${\displaystyle N}$，频域采样点为${\displaystyle \{\omega _{k}={2\pi }k/NT\}_{0\leq k<N}}$。 而DTFT在频域上采样：

${\displaystyle {\hat {x}}[k]={\hat {x}}_{discrete}(\omega _{k})={\frac {1}{T}}\sum _{n=0}^{N-1}x[nT]e^{-i{\frac {2\pi }{N}}nk}}$

令${\displaystyle T=1}$，将其归一化，就得到前面定义的离散傅里叶变换。因此，DFT就是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果。

DFT与CFT

参见：连续傅里叶变换

下面考察离散傅里叶变换与连续傅里叶变换（CFT，Continuous Fourier Transform）的关系。连续傅里叶变换

${\displaystyle {\mathcal {F}}x(t)={\hat {x}}(\omega )={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega t}dt}$

的采样为：

${\displaystyle {\hat {x}}(\omega _{k})={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega _{k}t}dt}$

将这个积分以黎曼和的形式近似，有：

${\displaystyle {\hat {x}}(\omega _{k})\approx {\frac {1}{L}}\sum _{n=0}^{N-1}x[n]e^{-i\omega _{k}nT}T={\frac {1}{N}}{\hat {x}}[k]}$

这一结论指出离散傅里叶变换确实是连续傅里叶变换在某种意义上的近似。不过必须注意以下两点：

• 时域采样必须满足采样定理
• 离散傅里叶变换的处理对象是时限的

为此，通常对连续信号的时域采样再做一次加窗处理（Windowing），这样就得到带限的有限长离散信号。

DFT与DTFT

参见：离散时间傅里叶变换

离散时间傅里叶变换（DTFT）是在时域上对连续傅里叶变换的采样。DFT则是在频域上对DTFT的均匀采样。离散信号${\displaystyle x[n]}$（n=0,...,N-1）的DTFT为：

${\displaystyle {\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }}$

对${\displaystyle {\hat {x}}(e^{i\omega })}$在离散的频点${\displaystyle \{\omega _{k}=k{\frac {2\pi }{N}}\}_{0\leq k<N}}$上采样

${\displaystyle {\hat {x}}[k]={\hat {x}}(e^{i\omega _{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}\qquad k=0,\ldots ,N-1}$

即为${\displaystyle x}$的DFT。由于DTFT在频域是周期的，所以在DTFT频域上的均匀采样也应是周期的。${\displaystyle {\hat {x}}[k]}$实际上是这个周期序列的主值序列。

栅栏效应

${\displaystyle N}$点序列的DFT只能在有限的${\displaystyle N}$个频点上观察频谱，这相当于从栅栏的缝隙中观察景色，对于了解信号在整个频域上的特性是不够的。为了观察到其他频率的信息，需要对原信号${\displaystyle x[n]}$做一些处理，以便在不同的频点上采样。

将原来在DTFT频域上的采样点数增加到${\displaystyle M}$点，这样采样点位置变为${\displaystyle \{\omega '_{k}=e^{ik{\frac {2\pi }{M}}}\}_{0\leq k<M}}$。则对应的DFT成为

${\displaystyle {\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}}$

若在序列${\displaystyle x[n]}$之后补上M-N个零，设为${\displaystyle x'[n]}$，则上式变为

${\displaystyle {\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'}$

因此将${\displaystyle x[n]}$补零再做DFT就可以得到${\displaystyle x[n]}$的DTFT在其他频率上的值，相当于移动了栅栏，因而能够从其他位置进行观察。

频谱分辨率

${\displaystyle N}$点DFT的频谱分辨率是${\displaystyle 2\pi /N}$。栅栏效应一节指出可以通过补零观察到更多的频点，但是这并不意味着补零能够提高真正的频谱分辨率。这是因为${\displaystyle x[n]}$实际上是${\displaystyle x(t)}$采样的主值序列，而将${\displaystyle x[n]}$补零得到的${\displaystyle x'[n]}$周期延拓之后与原来的序列并不相同，也不是${\displaystyle x(t)}$的采样。因此${\displaystyle {\hat {x}}'}$与${\displaystyle {\hat {x}}}$是不同离散信号的频谱。对于补零至${\displaystyle M}$点的${\displaystyle x'}$的DFT，只能说它的分辨率${\displaystyle {\frac {2\pi }{M}}}$仅具有计算上的意义，${\displaystyle {\hat {x}}'}$并不是真正的、物理意义上的频谱。频谱分辨率的提高只能在满足采样定理的条件下增加时域采样长度来实现。

从空间的角度分析

周期为N的离散信号构成一个N维欧几里得空间${\displaystyle \mathbb {C} ^{N}}$。在这一空间上两个信号x和y的内积定义为

${\displaystyle \langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]}$

下面给出${\displaystyle \mathbb {C} ^{N}}$上的一组正交基：

${\displaystyle \{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k<N}}$

将信号x在这组正交基上分解，得

${\displaystyle x=\sum _{k=0}^{N-1}{\frac {\langle x,e_{k}\rangle }{\Vert e_{k}\Vert ^{2}}}e_{k}}$

令

${\displaystyle {\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}}$

此即为离散傅里叶变换。又

${\displaystyle \|e_{k}\|^{2}=N}$

则有

${\displaystyle x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}}$

此即为离散傅里叶变换的逆变换。

由此可知，在正交分解的角度上说，离散周期信号${\displaystyle x}$的离散傅里叶变换${\displaystyle {\hat {x}}}$实质上是${\displaystyle x}$在正交基${\displaystyle \{e_{k}\}}$上的分量。而从线性变换的角度上说，${\displaystyle \{e_{k}\}}$是圆周卷积的特征向量，${\displaystyle {\hat {x}}}$则是对应的特征值。

DFT与圆周卷积

根据卷积定理，离散信号x与y的圆周卷积对偶于频域上x与y离散傅里叶变换的乘积。下面揭示DFT与圆周卷积的内在关系。

对长为N的离散信号${\displaystyle {\tilde {x}}}$与${\displaystyle {\tilde {y}}}$，如果要计算它们的卷积，就必须定义${\displaystyle {\tilde {x}}[n]}$与${\displaystyle {\tilde {y}}[n]}$在0≤n<N之外的值。如果将${\displaystyle {\tilde {x}}}$与${\displaystyle {\tilde {y}}}$作周期为N的延拓，则有

${\displaystyle x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]}$

如此，周期为N的圆周卷积：

${\displaystyle (x\otimes y)[n]=\sum _{m=0}^{N-1}x[m]y[n-m]=\sum _{m=0}^{N-1}x[n-m]y[m]}$

卷积的结果仍然是以N为周期的离散信号。

前面指出，${\displaystyle e_{k}}$是DFT的特征向量，实际上它也是圆周卷积的特征向量。定义x与y的圆周卷积算子：

${\displaystyle {L}x[n]=(x\otimes y)[n]}$

则${\displaystyle e_{k}}$与y的圆周卷积为

${\displaystyle {L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

显然，y的DFT

${\displaystyle {\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

就是圆周卷积的特征值。

性质

完全性

离散傅里叶变换是可逆的线性变换

${\displaystyle {\mathcal {F}}:\mathbf {C} ^{N}\to \mathbf {C} ^{N}}$

其中C表示复数集。即，任意N-维复向量都存在DFT和IDFT，而且其DFT和IDFT也是N-维复向量。

正交性

向量组exp（2πi kn/N）是N-维复数空间上的一组正交基：

${\displaystyle \sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}}$

其中δ_kn是Kronecker delta。

移位定理

时域信号序列${\displaystyle x_{n}}$的相位移动${\displaystyle \exp(2\pi inm/N)}$（其中${\displaystyle m}$为整数）在频域反映为“循环移位”，即：频域信号序列${\displaystyle X_{k}}$变为${\displaystyle X_{((k-m))_{N}}}$，其中下标是指将k-m对N 取余。类似的，由对偶性，时域信号序列的循环移位对应于频域信号序列的相移：

若${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$

则${\displaystyle {\mathcal {F}}(\{x_{n}e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}}$

且有${\displaystyle {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}e^{-{\frac {2\pi i}{N}}km}}$

周期性

上文中DFT与DTFT一节已经证明，离散序列的傅里叶变换是周期的。有限长序列${\displaystyle x_{n}}$的离散傅里叶变换${\displaystyle X_{k}}$可以被看作是它的周期延拓序列${\displaystyle {\tilde {x}}_{n}=x_{n\ mod\ N}}$的离散时间傅里叶变换${\displaystyle {\tilde {X}}_{k}}$。由时频对偶性可知${\displaystyle X_{k}}$也可以被看作它的周期延拓的主值。

上一节的移位定理隐含着DFT的周期性，因为DFT的幅度${\displaystyle |X_{k}|}$不受输入信号的循环移位的影响，因为时移在频域对偶于相移，循环移位仅仅使DFT的相位产生平移。周期性的边界条件在DFT的许多应用中有重要作用。解差分方程时，就假设边界条件是满足周期性的，这是一个很有用的性质（参见应用）。

普朗歇尔定理与帕塞瓦尔定理

如果X_k和Y_k分别是x_n和y_n的离散傅立叶变换，那么就有普朗歇尔定理：

${\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}}$

其中星号表示复共扼。帕塞瓦尔定理是普朗歇尔定理的一个特例：

${\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.}$

应用

DFT在诸多多领域中有着重要应用，下面仅是颉取的几个例子。需要指出的是，所有DFT的实际应用都依赖于计算离散傅里叶变换及其逆变换的快速算法，即快速傅里叶变换。

快速傅里叶变换

主条目：快速傅里叶变换

简介

快速傅里叶变换（Fast Fourier Transform，简称FFT）是一种用来高效计算离散傅里叶变换（Discrete Fourier Transform，DFT）及其反变换的算法。傅里叶变换是一种数学变换，用来将信号从时间域或空间域变换到频率域。这在信号处理、图像处理、数据分析等领域有着广泛的应用。传统的DFT计算复杂度较高，约为${\displaystyle {\mathcal {O}}(n^{2})}$，而FFT将其降为${\displaystyle {\mathcal {O}}(n\log n)}$，大大提高了计算效率。高效的计算能力使其在各种实际应用中扮演着关键角色。理解和应用FFT不仅能解决具体的技术问题，还能帮助我们更深入地了解信号处理的基本原理和方法。FFT的出现和应用，无疑是数学和工程领域的一大突破。

常见用于执行离散傅里叶变换的算法:

1. 库利-图基算法(Cooley-Tukey algorithm)

库利－图基算法是一种用于快速计算离散傅里叶变换的方法，通过分治法策略(Divide-and-conquer)将一个长度为N的DFT分解为多个较小长度的DFT。这使得它特别适合处理长度为2的幂次方的序列，但实际上也适用于其他约数分解形式的序列。库利和图基在1965年首次提出这个方法，但类似的概念早在1805年由高斯提出。

2.基数-4、8、16、……算法(Radix-4, 8, 16, …. Algorithms)

可以视为库利－图基算法的一种推广，使用不只是以2作为基底，以其他数字做为基底的快速算法。

3.互素因子算法(prime factor algorithm)

互素因子算法，又称Good–Thomas算法，是一种用于快速傅里叶变换（FFT）的算法。它将大小为${\displaystyle N=N_{1}N_{2}}$的DFT变换为${\displaystyle N_{1}\times \ N_{2}}$的二维DFT，前提是${\displaystyle N_{1}}$和${\displaystyle N_{2}}$必须是互素的。这种算法在此特殊情况下比传统的Cooley–Tukey算法更有效。

4.格策尔算法(Goertzel Algorithm)

此算法在1958年被杰拉德 · 格策尔所提出。

此算法，使用数字滤波方法计算离散傅里叶变换（DFT）系数和信号频谱。修改后的格策尔算法可以用来计算信号频谱，而无需像DFT算法那样涉及复杂的代数计算。

5. 啁啾-Z变换(Chirp Z transform (CZT))

啁啾-Z变换（Chirp-Z transform）是一种离散傅里叶变换（DFT）的扩展算法，适用于当取样频率间隔与取样时间间隔的乘积不等于信号的时频分布面积时的情况。它利用卷积来实现任意大小的DFT，从而加快计算速度，是一种基于快速傅里叶变换（FFT）的高效算法。

此外，啁啾-Z变换也是一种用于评估非单位圆上的Z变换的算法。

6.威诺格拉德算法(Winograd algorithm)

由以色列裔美国计算机科学家Shmuel Winograd于1976年提出的，是一种改进型的快速傅里叶变换（FFT）算法，旨在进一步提高计算效率和速度。此算法使用的加法数量与库利-图基算法大致相同，但其所需的乘法数量只有其算法的约20%。

频谱分析

前面指出，DFT是连续傅里叶变换的近似。因此可以对连续信号x（t）均匀采样并截断以得到有限长的离散序列${\displaystyle \{x_{n}\}\,}$，对这一序列作离散傅里叶变换，可以分析连续信号x（t）频谱的性质。前面还提到DFT应用于频谱分析需要注意的两个问题：即采样可能导致信号混叠和截断信号引起的频谱泄漏。可以通过选择适当的采样频率（见奈奎斯特频率）消减混叠。选择适当的序列长度并加窗可以抑制频谱泄漏。

数据压缩

主条目：数据压缩

由于人类感官的分辨能力存在极限，因此很多有损压缩算法利用这一点将语音、音频、图像、视频等信号的高频部分除去。高频信号对应于信号的细节，滤除高频信号可以在人类感官可以接受的范围内获得很高的压缩比。这一去除高频分量的处理就是通过离散傅里叶变换完成的。将时域或空域的信号转换到频域，仅储存或传输较低频率上的系数，在解压缩端采用逆变换即可重建信号。

解偏微分方程

主条目：偏微分方程

离散傅里叶变换及其多维形式在偏微分方程的求解中也有应用。此时DFT被看作傅里叶级数的近似。傅里叶级数将函数在复指数e^inx上展开，这正是微分算子的特征方程：d/dx e^inx = in e^inx。因此，通过傅里叶级数的形式，线性常微分方程被转换为代数方程，而后者是很容易求解的。此时得到的结果是偏微分方程解的级数表示，只要通过DFT逆变换即可得到其一般表示。这种方法被称作谱方法或级数解法。

长整数与多项式乘法

目前长整数或多项式乘法最快速的算法是基于离散傅里叶变换的。由于整数（或多项式）乘法是逐位（或逐项）乘累加的形式，因此整数（或多项式）乘积的数字（或系数）可以用乘数数字（或乘式系数）的卷积表示。利用卷积定理，只要将数字（或系数）序列通过离散傅里叶变换变到频域，就可以将逐个乘累加的卷积变为对位的乘法，从而减少计算量，再以一次逆变换便可以得到乘法结果。需要注意整数乘法还有进位的问题。下面以多项式乘法为例说明这一应用：

假设需要计算多项式乘法c(x) = a(x)·b（x），这一乘积结果的各项系数的表达式实际上是线性卷积的形式。由于离散傅里叶变换对应于圆周卷积，因此需要将这两个乘式的系数按照次数升序排列，序列后“补零”，使它们的长度d大于两式最高项次数的和：d > deg(a(x)) + deg(b(x))。然后作圆周卷积：

${\displaystyle \mathbf {c} =\mathbf {a} \otimes \mathbf {b} }$

其中c就是c(x)系数的向量。由于圆周卷积的DFT是乘积，有：

${\displaystyle {\mathcal {F}}\mathbf {c} ={\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} }$

则

${\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} )}$

利用快速傅里叶变换，这一算法的运算复杂度为${\displaystyle {\mathcal {O}}(N\log N)}$。

OFDM

主条目：OFDM

OFDM（正交频分复用）在宽带无线通信中有重要的应用。这种技术将带宽分为N个等间隔的子载波，可以证明这些子载波相互正交。尤其重要的是，OFDM调制可以由IDFT实现，而解调可以由DFT实现。OFDM还利用DFT的移位性质，在每个帧头部加上循环前缀（Cyclic Prefix），使得只要信道延时小于循环前缀的长度，就能消除信道延时对传输的影响。

特殊例子

数论转换

主条目：数论变换

数论变换是一种可以计算卷积的快速算法。计算卷积的快速算法中最常用的一种是使用快速傅里叶变换，然而快速傅里叶变换具有一些实现上的缺点，举例来说，资料向量必须乘上复数系数的矩阵加以处理，而且每个复数系数的实部和虚部是一个正弦及余弦函数，因此大部分的系数都是浮点数，也就是说，必须做复数而且是浮点数的运算，因此计算量会比较大，而且浮点数运算产生的误差会比较大。

而在数论变换中，资料向量需要乘上的矩阵是一个整数的矩阵，因此不需要作浮点数的乘法运算，更进一步，在模数为的情况下，只有种可能的加法与种可能的乘法，这可以使用记忆体把这些有限数目的加法和乘法存起来，利用查表法来计算，使得数论变换完全不须任何乘法与加法运算，不过需要较大的记忆体与消耗较大的存取记忆体量。

虽然使用数论变换可以降低计算卷积的复杂度，不过由于只进行整数的运算，所以只能用于对整数的讯号计算卷积，而利用快速傅里叶变换可以对任何复数的讯号计算卷积，这是降低运算复杂度所要付出的代价，也不一定所有信号都可以找到适合做数论变换的素数。

${\displaystyle F=Z/p}$，此运算是根据模运算 而取得的，${\displaystyle p}$需要是素数 ，如此可以建构出有限域，并且存在 ${\displaystyle n}$ 个可以整除 ${\displaystyle (p-1)}$ 的实数根。如此可以得到${\displaystyle p=k\cdot n+1}$，${\displaystyle k}$ 为正整数。令 ${\displaystyle \omega }$ 为第 ${\displaystyle (p-1)}$ 个单位根，则第 ${\displaystyle n}$ 个单位根 ${\displaystyle \alpha }$ 可以表示成 ${\displaystyle \alpha =\omega ^{k}}$ 。另外，再令${\displaystyle N}$ 为 ${\displaystyle \alpha }$ 次方 ${\displaystyle p}$ 模运算之循环个数。

数论变换的公式

${\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}$

${\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}{\pmod {M}}\quad n=0,1,2,\ldots ,N-1}$

其中有几点限制以及应该注意的事项:

1.M应是一个素数

2.N应该是M-1的约数

3.${\displaystyle N^{-1}}$是满足 ${\displaystyle N^{-1}}$${\displaystyle N}$ modM=1 的整数（当 N = M−1 时， ${\displaystyle N^{-1}}$ = M−1）。它也被称为 N 的模 M 的逆元

4.${\displaystyle \alpha }$是 N 阶的单位根。

举个例子来说，当 ${\displaystyle p=5,\alpha =2}$ 则

${\displaystyle \alpha ^{1}=2\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{2}=4\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{3}=3\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{4}=1\qquad (mod\quad 5)}$

因为 ${\displaystyle \alpha ^{4}}$ 经 ${\displaystyle 5}$ 的模运算为 ${\displaystyle 1}$ ，因此可以判定此情况为 ${\displaystyle 4}$ 个次方一循环，所以 ${\displaystyle N=4}$，${\displaystyle N}$可以整除 ${\displaystyle (p-1)}$。则数论矩阵可以表示成

${\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}$

在一些特殊的情况下，令 ${\displaystyle F=Z/m}$ ，而 ${\displaystyle m}$ 不是值数也是有意义的。像是 Fermat Number Transform 中${\displaystyle (m=2^{k}+1)}$，以及 Mersenne Number Transform 中 ${\displaystyle (m=2^{k}-1)}$.

数论变换的数学性质

前面提到数论变换是一种离散傅里叶变换的特例，因此数论变换具有许多离散傅里叶变换的数学性质。

若F[k]为f[n]的数论变换结果，即f[n]→F[k](NTT)

1.正交性质:

矩阵中的每个行或列，彼此正交，即任两个行或列的内积为0

${\displaystyle \sum _{n=0}^{N-1}\alpha ^{nl}\alpha ^{-nk}=\sum _{n=0}^{N-1}\alpha ^{n(k-l)}=N\delta _{kt}}$

证明:

当${\displaystyle k=l}$，${\displaystyle S_{N}=\sum _{n=0}^{N-1}\alpha ^{n(0)}=N}$

当${\displaystyle k\neq 0}$，${\displaystyle (\alpha ^{n(k-l)}-1)S_{N}=(\alpha ^{n(k-l)}-1)\sum _{n=0}^{N-1}\alpha ^{n(k-l)}=\alpha ^{N(k-l)}-1=1-1=0}$

2.线性性质:

NTT 符合线性变换，即：

${\displaystyle F[k_{1}+k_{2}]=f[n_{1}]+f[n_{2}]}$

并且对于常数 c 有：

${\displaystyle F[ck]=cF[k]}$

若${\displaystyle f[n]\leftrightarrow F[k]}$，则${\displaystyle -f[n]\leftrightarrow -F[k]}$。

3.平移性质:

若${\displaystyle f[n]\leftrightarrow F[k]}$，则${\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]}$，且${\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}$

4.可逆性质:

NTT 变换是可逆的，存在反变换 INTT 使得：

INTT(NTT(n))=n

5.对称性质:

若${\displaystyle f[n]}$具有对称性质，即${\displaystyle f[n]=f[N-n]}$，则${\displaystyle f[n]}$的数论变换${\displaystyle F[k]}$也会有对称性质，即${\displaystyle F[k]=F[N-k]}$的特性。

若${\displaystyle f[n]=-f[N-n]}$，则${\displaystyle f[n]}$的数论变换${\displaystyle F[k]}$也会有${\displaystyle F[k]=-F[N-k]}$的特性。

6.卷积性质:

此性质在线性非时变系统当中非常重要，NTT的主要应用多与此性质有关。

若考虑两个信号，${\displaystyle f[n_{1}]\leftrightarrow F[k_{1}]}$，${\displaystyle f[n_{2}]\leftrightarrow F[k_{2}]}$

${\displaystyle f[n_{1}]*f[n_{2}]\leftrightarrow F[k_{1}]F[k_{2}]{\pmod {m}}}$

${\displaystyle f[n_{1}]f[n_{2}]\leftrightarrow F[k_{1}]*F[k_{2}]{\pmod {m}}}$

数论变换的优缺点

优点:

1.使用整数进行计算，计算较容易，也可以节省记忆体空间。

2.使用整数不会像浮点数一样产生误差，可以非常精确地计算。

3.很多性质都跟离散傅里叶变换相同。

缺点:

1.只能对整数做计算，若信号为非整数，可能需要事先处理。

2.不容易找到root of unity，即不容易找到合适的对数变换。

3.相对而言缺乏物理意义。

参阅

• 傅里叶级数
• 傅里叶变换
• 快速傅里叶变换
• 数字信号处理
• Chirp-Z变换

参考文献

1. Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., (1999). Discrete-time signal processing, Upper Saddle River, N.J. : Prentice Hall. ISBN 0137549202
2. Mallat, S., A Wavelet Tour of Signal Processing, Second Edition, Academic Press, ISBN 0-12-466606-x
3. Gill, J., Fourier Transform and Its Applications（[1] （页面存档备份，存于互联网档案馆））
4. Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2024
5. Duhamel, Pierre, and Martin Vetterli. "Fast Fourier transforms: a tutorial review and a state of the art." Signal processing 19.4 (1990): 259-299.