离散傅里叶变换 （英語：Discrete Fourier Transform ，缩写为DFT 傅里叶变换 在时域 和频域 上都呈离散的形式，将信号的时域采样变换为其DTFT 的频域采样。
在形式上，变换两端（时域和频域上）的序列都是离散的，而实际上这两组序列都应当被认为是离散 周期 信号 的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换 计算DFT。
離散傅里葉變換，是連續傅立葉變換在離散樣本上的類比，目前廣泛應用於信號處理、數值分析、數位通信、音訊處理等領域，在快速演算法問世，以及硬體設備的提升後，能夠更廣泛的應用在人們的日常生活當中，也是個非常重要的學問之一。
对于
N
{\displaystyle N}
{
x
[
n
]
}
0
≤
n
<
N
{\displaystyle \left\{x[n]\right\}_{0\leq n<N}}
x
^
[
k
]
=
∑
n
=
0
N
−
1
e
−
i
2
π
N
n
k
x
[
n
]
k
=
0
,
1
,
…
,
N
−
1.
{\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.}
其中
e
{\displaystyle e}
自然对数 的底数 ，
i
{\displaystyle i}
虚数单位 。通常以符号
F
{\displaystyle {\mathcal {F}}}
x
^
=
F
x
{\displaystyle {\hat {x}}={\mathcal {F}}x}
离散傅里叶变换的逆变换（IDFT）为：
x
[
n
]
=
1
N
∑
k
=
0
N
−
1
e
i
2
π
N
n
k
x
^
[
k
]
n
=
0
,
1
,
…
,
N
−
1.
{\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.}
可以记为：
x
=
F
−
1
x
^
{\displaystyle x={\mathcal {F}}^{-1}{\hat {x}}}
实际上，DFT和IDFT变换式中和式前面的归一化系数并不重要。在上面的定义中，DFT和IDFT前的系数分别为
1
{\displaystyle 1}
1
N
{\displaystyle {\frac {1}{N}}}
1
N
{\displaystyle {\frac {1}{\sqrt {N}}}}
连续时间信号
x
(
t
)
{\displaystyle x(t)}
连续傅里叶变换
x
^
(
ω
)
{\displaystyle {\hat {x}}(\omega )}
离散信号 ，因此必须将
x
{\displaystyle x}
x
^
{\displaystyle {\hat {x}}}
假设
x
(
t
)
{\displaystyle x(t)}
[
0
,
L
]
{\displaystyle [0,L]}
x
(
t
)
{\displaystyle x(t)}
x
d
i
s
c
r
e
t
e
(
t
)
{\displaystyle x_{discrete}(t)}
T
{\displaystyle T}
N
=
L
T
{\displaystyle N={\frac {L}{T}}}
x
d
i
s
c
r
e
t
e
(
t
)
=
x
(
t
)
∑
n
=
0
N
−
1
δ
(
t
−
n
T
)
=
∑
n
=
0
N
−
1
x
(
n
T
)
δ
(
t
−
n
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)}
它的傅里叶变换为
x
^
d
i
s
c
r
e
t
e
(
ω
)
=
∑
n
=
0
N
−
1
x
(
n
T
)
F
δ
(
t
−
n
T
)
=
∑
n
=
0
N
−
1
x
(
n
T
)
e
−
i
n
ω
T
{\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}}
这就是
x
(
t
)
{\displaystyle x(t)}
离散时间傅里叶变换 ，它在频域依然是连续的。
下面将频域信号转化为有限长离散信号。与对时域信号的处理类似，假设频域信号是带限的，再经过离散化，即可得到有限长离散信号。依据采样定理 ，频域采样若要能完全重建原信号，频域信号
x
^
(
ω
)
{\displaystyle {\hat {x}}(\omega )}
(
0
,
1
2
T
)
{\displaystyle (0,{\frac {1}{2T}})}
[
0
,
L
]
{\displaystyle [0,L]}
1
/
L
{\displaystyle 1/L}
1
/
T
1
/
L
=
N
{\displaystyle {\frac {1/T}{1/L}}=N}
即频域采样的点数和时域采样同为
N
{\displaystyle N}
{
ω
k
=
2
π
k
/
N
T
}
0
≤
k
<
N
{\displaystyle \{\omega _{k}={2\pi }k/NT\}_{0\leq k<N}}
x
^
[
k
]
=
x
^
d
i
s
c
r
e
t
e
(
ω
k
)
=
1
T
∑
n
=
0
N
−
1
x
[
n
T
]
e
−
i
2
π
N
n
k
{\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}}
令
T
=
1
{\displaystyle T=1}
下面考察离散傅里叶变换与连续傅里叶变换（CFT，Continuous Fourier Transform）的关系。连续傅里叶变换
F
x
(
t
)
=
x
^
(
ω
)
=
1
L
∫
0
L
x
(
t
)
e
−
i
ω
t
d
t
{\displaystyle {\mathcal {F}}x(t)={\hat {x}}(\omega )={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega t}dt}
的采样为：
x
^
(
ω
k
)
=
1
L
∫
0
L
x
(
t
)
e
−
i
ω
k
t
d
t
{\displaystyle {\hat {x}}(\omega _{k})={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega _{k}t}dt}
将这个积分以黎曼和的形式近似，有：
x
^
(
ω
k
)
≈
1
L
∑
n
=
0
N
−
1
x
[
n
]
e
−
i
ω
k
n
T
T
=
1
N
x
^
[
k
]
{\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），这样就得到带限的有限长离散信号。
离散时间傅里叶变换（DTFT）是在时域上对连续傅里叶变换 的采样。DFT则是在频域上对DTFT的均匀采样。离散信号
x
[
n
]
{\displaystyle x[n]}
x
^
(
e
i
ω
)
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
i
n
ω
{\displaystyle {\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }}
对
x
^
(
e
i
ω
)
{\displaystyle {\hat {x}}(e^{i\omega })}
{
ω
k
=
k
2
π
N
}
0
≤
k
<
N
{\displaystyle \{\omega _{k}=k{\frac {2\pi }{N}}\}_{0\leq k<N}}
x
^
[
k
]
=
x
^
(
e
i
ω
k
)
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
i
2
π
N
k
n
k
=
0
,
…
,
N
−
1
{\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}
即为
x
{\displaystyle x}
x
^
[
k
]
{\displaystyle {\hat {x}}[k]}
N
{\displaystyle N}
N
{\displaystyle N}
栅栏 的缝隙中观察景色，对于了解信号在整个频域上的特性是不够的。为了观察到其他频率的信息，需要对原信号
x
[
n
]
{\displaystyle x[n]}
将原来在DTFT频域上的采样点数增加到
M
{\displaystyle M}
{
ω
k
′
=
e
i
k
2
π
M
}
0
≤
k
<
M
{\displaystyle \{\omega '_{k}=e^{ik{\frac {2\pi }{M}}}\}_{0\leq k<M}}
x
^
′
[
k
]
=
x
^
(
e
i
k
ω
k
′
)
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
i
2
π
M
k
n
{\displaystyle {\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}}
若在序列
x
[
n
]
{\displaystyle x[n]}
x
′
[
n
]
{\displaystyle x'[n]}
x
^
′
[
k
]
=
∑
n
=
0
M
−
1
x
′
[
n
]
e
−
i
2
π
M
k
n
=
F
x
′
{\displaystyle {\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'}
因此将
x
[
n
]
{\displaystyle x[n]}
x
[
n
]
{\displaystyle x[n]}
N
{\displaystyle N}
2
π
/
N
{\displaystyle 2\pi /N}
栅栏效应 一节指出可以通过补零观察到更多的频点，但是这并不意味着补零能够提高真正的频谱分辨率。这是因为
x
[
n
]
{\displaystyle x[n]}
x
(
t
)
{\displaystyle x(t)}
x
[
n
]
{\displaystyle x[n]}
x
′
[
n
]
{\displaystyle x'[n]}
x
(
t
)
{\displaystyle x(t)}
x
^
′
{\displaystyle {\hat {x}}'}
x
^
{\displaystyle {\hat {x}}}
M
{\displaystyle M}
x
′
{\displaystyle x'}
2
π
M
{\displaystyle {\frac {2\pi }{M}}}
x
^
′
{\displaystyle {\hat {x}}'}
周期为N的离散信号构成一个N 维欧几里得空间
C
N
{\displaystyle \mathbb {C} ^{N}}
x 和y 的内积 定义为
⟨
x
,
y
⟩
=
∑
n
=
0
N
−
1
x
[
n
]
y
∗
[
n
]
{\displaystyle \langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]}
下面给出
C
N
{\displaystyle \mathbb {C} ^{N}}
正交基 ：
{
e
k
[
n
]
=
e
i
2
π
N
k
n
}
0
≤
k
<
N
{\displaystyle \{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k<N}}
将信号x 在这组正交基上分解，得
x
=
∑
k
=
0
N
−
1
⟨
x
,
e
k
⟩
‖
e
k
‖
2
e
k
{\displaystyle x=\sum _{k=0}^{N-1}{\frac {\langle x,e_{k}\rangle }{\Vert e_{k}\Vert ^{2}}}e_{k}}
令
x
^
[
k
]
=
⟨
x
,
e
k
⟩
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
i
2
π
N
k
n
{\displaystyle {\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}}
此即为离散傅里叶变换。又
‖
e
k
‖
2
=
N
{\displaystyle \|e_{k}\|^{2}=N}
则有
x
[
n
]
=
1
N
∑
k
=
0
N
−
1
x
^
[
k
]
e
i
2
π
N
k
n
{\displaystyle x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}}
此即为离散傅里叶变换的逆变换。
由此可知，在正交分解的角度上说，离散周期信号
x
{\displaystyle x}
x
^
{\displaystyle {\hat {x}}}
x
{\displaystyle x}
{
e
k
}
{\displaystyle \{e_{k}\}}
线性变换 的角度上说，
{
e
k
}
{\displaystyle \{e_{k}\}}
圆周卷积 的特征向量 ，
x
^
{\displaystyle {\hat {x}}}
特征值 。
根据卷积定理 ，离散信号x与y的圆周卷积 对偶于频域上x与y离散傅里叶变换的乘积。下面揭示DFT与圆周卷积的内在关系。
对长为N的离散信号
x
~
{\displaystyle {\tilde {x}}}
y
~
{\displaystyle {\tilde {y}}}
x
~
[
n
]
{\displaystyle {\tilde {x}}[n]}
y
~
[
n
]
{\displaystyle {\tilde {y}}[n]}
0≤n<N 之外的值。如果将
x
~
{\displaystyle {\tilde {x}}}
y
~
{\displaystyle {\tilde {y}}}
x
[
n
]
=
x
~
[
n
mod
N
]
y
[
n
]
=
y
~
[
n
mod
N
]
{\displaystyle x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]}
如此，周期为N的圆周卷积：
(
x
⊗
y
)
[
n
]
=
∑
m
=
0
N
−
1
x
[
m
]
y
[
n
−
m
]
=
∑
m
=
0
N
−
1
x
[
n
−
m
]
y
[
m
]
{\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为周期的离散信号。
前面指出，
e
k
{\displaystyle e_{k}}
L
x
[
n
]
=
(
x
⊗
y
)
[
n
]
{\displaystyle {L}x[n]=(x\otimes y)[n]}
则
e
k
{\displaystyle e_{k}}
L
e
k
[
n
]
=
e
k
[
n
]
⋅
∑
m
=
0
N
−
1
y
[
m
]
e
k
[
−
m
]
{\displaystyle {L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]}
显然，y的DFT
y
^
[
k
]
=
∑
m
=
0
N
−
1
y
[
m
]
e
k
[
−
m
]
{\displaystyle {\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]}
就是圆周卷积的特征值。
离散傅里叶变换是可逆的线性变换
F
:
C
N
→
C
N
{\displaystyle {\mathcal {F}}:\mathbf {C} ^{N}\to \mathbf {C} ^{N}}
其中C 表示复数集 。即，任意N -维复向量都存在DFT和IDFT，而且其DFT和IDFT也是N -维复向量。
向量组exp（2πi kn/N ）是N -维复数空间上的一组正交基：
∑
n
=
0
N
−
1
(
e
2
π
i
N
k
n
)
(
e
−
2
π
i
N
k
′
n
)
=
N
δ
k
k
′
{\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 。
时域信号序列
x
n
{\displaystyle x_{n}}
exp
(
2
π
i
n
m
/
N
)
{\displaystyle \exp(2\pi inm/N)}
m
{\displaystyle m}
X
k
{\displaystyle X_{k}}
X
(
(
k
−
m
)
)
N
{\displaystyle X_{((k-m))_{N}}}
k-m 对N 取余 。类似的，由对偶性，时域信号序列的循环移位对应于频域信号序列的相移：
若
F
(
{
x
n
}
)
k
=
X
k
{\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}
则
F
(
{
x
n
e
2
π
i
N
n
m
}
)
k
=
X
k
−
m
{\displaystyle {\mathcal {F}}(\{x_{n}e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}}
且有
F
(
{
x
n
−
m
}
)
k
=
X
k
e
−
2
π
i
N
k
m
{\displaystyle {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}e^{-{\frac {2\pi i}{N}}km}}
上文中DFT与DTFT 一节已经证明，离散序列的傅里叶变换是周期的。有限长序列
x
n
{\displaystyle x_{n}}
X
k
{\displaystyle X_{k}}
x
~
n
=
x
n
m
o
d
N
{\displaystyle {\tilde {x}}_{n}=x_{n\ mod\ N}}
X
~
k
{\displaystyle {\tilde {X}}_{k}}
X
k
{\displaystyle X_{k}}
上一节的移位定理隐含着DFT的周期性，因为DFT的幅度
|
X
k
|
{\displaystyle |X_{k}|}
差分方程 时，就假设边界条件是满足周期性的，这是一个很有用的性质（参见应用 ）。
如果X k Y k x n y n 普朗歇尔定理 ：
∑
n
=
0
N
−
1
x
n
y
n
∗
=
1
N
∑
k
=
0
N
−
1
X
k
Y
k
∗
{\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}}
其中星号表示复共扼。帕塞瓦尔定理 是普朗歇尔定理的一个特例：
∑
n
=
0
N
−
1
|
x
n
|
2
=
1
N
∑
k
=
0
N
−
1
|
X
k
|
2
.
{\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計算複雜度較高，約為
O
(
n
2
)
{\displaystyle {\mathcal {O}}(n^{2})}
O
(
n
log
n
)
{\displaystyle {\mathcal {O}}(n\log n)}
[ 编辑 ] 庫利－圖基演算法是一種用於快速計算離散傅立葉轉換的方法，通過分治法策略(Divide-and-conquer)將一個長度為N的DFT分解為多個較小長度的DFT。這使得它特別適合處理長度為2的冪次方的序列，但實際上也適用於其他因數分解形式的序列。庫利和圖基在1965年首次提出這個方法，但類似的概念早在1805年由高斯提出。
[ 编辑 ] 可以視為庫利－圖基演算法的一種推廣，使用不只是以2作為基底，以其他數字做為基底的快速演算法。
[ 编辑 ] 互質因子算法，又稱Good–Thomas算法，是一種用於快速傅立葉變換（FFT）的算法。它將大小為
N
=
N
1
N
2
{\displaystyle N=N_{1}N_{2}}
N
1
×
N
2
{\displaystyle N_{1}\times \ N_{2}}
N
1
{\displaystyle N_{1}}
N
2
{\displaystyle N_{2}}
[ 编辑 ] 此演算法在1958年被傑拉德 · 格策爾 所提出。
此算法，使用數字濾波方法計算離散傅立葉轉換（DFT）係數和信號頻譜。修改後的格策爾演算法可以用來計算信號頻譜，而無需像DFT算法那樣涉及複雜的代數計算。
啁啾-Z轉換（Chirp-Z transform）是一種離散傅立葉轉換（DFT）的擴展算法，適用於當取樣頻率間隔與取樣時間間隔的乘積不等於信號的時頻分佈面積時的情況。它利用卷積來實現任意大小的DFT，從而加快計算速度，是一種基於快速傅立葉轉換（FFT）的高效算法。
此外，啁啾-Z變換也是一種用於評估非單位圓上的Z變換的算法。
[ 编辑 ] 由以色列裔美國計算機科學家Shmuel Winograd於1976年提出的，是一種改進型的快速傅立葉轉換（FFT）算法，旨在進一步提高計算效率和速度。此演算法使用的加法數量與庫利-圖基演算法大致相同，但其所需的乘法數量只有其演算法的約20%。
前面指出，DFT是连续傅里叶变换的近似 。因此可以对连续信号x（t）均匀采样并截断以得到有限长的离散序列
{
x
n
}
{\displaystyle \{x_{n}\}\,}
奈奎斯特频率 ）消减混叠 。选择适当的序列长度并加窗可以抑制频谱泄漏。
由于人类感官的分辨能力存在极限，因此很多有损压缩算法利用这一点将语音、音频、图像、视频等信号的高频部分除去。高频信号对应于信号的细节，滤除高频信号可以在人类感官可以接受的范围内获得很高的压缩比。这一去除高频分量的处理就是通过离散傅里叶变换完成的。将时域或空域的信号转换到频域，仅储存或传输较低频率上的系数，在解压缩端采用逆变换即可重建信号。
离散傅里叶变换及其多维形式在偏微分方程的求解中也有应用。此时DFT被看作傅里叶级数 的近似。傅里叶级数将函数在复指数e inx d /dx e inx in e inx
目前长整数 或多项式 乘法 最快速的算法是基于离散傅里叶变换的。由于整数（或多项式）乘法是逐位（或逐项）乘累加的形式，因此整数（或多项式）乘积的数字（或系数）可以用乘数数字（或乘式系数）的卷积 表示。利用卷积定理 ，只要将数字（或系数）序列通过离散傅里叶变换变到频域，就可以将逐个乘累加的卷积变为对位的乘法，从而减少计算量，再以一次逆变换便可以得到乘法结果。需要注意整数乘法还有进位 的问题。下面以多项式乘法为例说明这一应用：
假设需要计算多项式乘法c (x ) = a (x )·b （x ），这一乘积结果的各项系数的表达式实际上是线性卷积的形式。由于离散傅里叶变换对应于圆周卷积，因此需要将这两个乘式的系数按照次数升序排列，序列后“补零”，使它们的长度d 大于两式最高项次数的和：d > deg(a (x )) + deg(b (x ))。然后作圆周卷积：
c
=
a
⊗
b
{\displaystyle \mathbf {c} =\mathbf {a} \otimes \mathbf {b} }
其中c 就是c (x )系数的向量。由于圆周卷积的DFT是乘积，有：
F
c
=
F
a
⋅
F
b
{\displaystyle {\mathcal {F}}\mathbf {c} ={\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} }
则
c
=
F
−
1
(
F
a
⋅
F
b
)
{\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} )}
利用快速傅里叶变换，这一算法的运算复杂度为
O
(
N
log
N
)
{\displaystyle {\mathcal {O}}(N\log N)}
OFDM（正交频分复用）在宽带无线通信 中有重要的应用。这种技术将带宽分为N 个等间隔的子载波，可以证明这些子载波相互正交。尤其重要的是，OFDM调制可以由IDFT实现，而解调可以由DFT实现。OFDM还利用DFT的移位性质，在每个帧头部加上循环前缀（Cyclic Prefix），使得只要信道延时小于循环前缀的长度，就能消除信道延时对传输的影响。
數論轉換 是一種可以計算摺積 的快速演算法。計算摺積的快速演算法中最常用的一種是使用快速傅里葉變換 ，然而快速傅立葉變換具有一些實現上的缺點，舉例來說，資料向量必須乘上複數 係數的矩陣加以處理，而且每個複數係數的實部和虛部是一個正弦 及餘弦 函數，因此大部分的係數都是浮點數 ，也就是說，必須做複數而且是浮點數的運算，因此計算量會比較大，而且浮點數運算產生的誤差會比較大。
而在數論轉換中，資料向量需要乘上的矩陣是一個整數 的矩陣，因此不需要作浮點數的乘法運算，更進一步，在模數為的情況下，只有種可能的加法與種可能的乘法，這可以使用記憶體把這些有限數目的加法和乘法存起來，利用查表法來計算，使得數論轉換完全不須任何乘法與加法運算，不過需要較大的記憶體與消耗較大的存取記憶體量。
雖然使用數論轉換可以降低計算摺積的複雜度，不過由於只進行整數的運算，所以只能用於對整數 的訊號計算摺積，而利用快速傅立葉變換可以對任何複數的訊號計算摺積，這是降低運算複雜度所要付出的代價，也不一定所有信號都可以找到適合做數論轉換的質數。
F
=
Z
/
p
{\displaystyle F=Z/p}
模運算 而取得的，
p
{\displaystyle p}
質數 ，如此可以建構出有限域 ，並且存在
n
{\displaystyle n}
(
p
−
1
)
{\displaystyle (p-1)}
實數 根。如此可以得到
p
=
k
⋅
n
+
1
{\displaystyle p=k\cdot n+1}
k
{\displaystyle k}
ω
{\displaystyle \omega }
(
p
−
1
)
{\displaystyle (p-1)}
單位根 ，則第
n
{\displaystyle n}
α
{\displaystyle \alpha }
α
=
ω
k
{\displaystyle \alpha =\omega ^{k}}
N
{\displaystyle N}
α
{\displaystyle \alpha }
p
{\displaystyle p}
F
[
k
]
=
∑
n
=
0
N
−
1
f
[
n
]
α
n
k
(
mod
M
)
k
=
0
,
1
,
2
,
…
,
N
−
1
{\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}
f
[
n
]
=
N
−
1
∑
k
=
0
N
−
1
F
[
k
]
α
−
n
k
(
mod
M
)
n
=
0
,
1
,
2
,
…
,
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.
N
−
1
{\displaystyle N^{-1}}
N
−
1
{\displaystyle N^{-1}}
N
{\displaystyle N}
N
−
1
{\displaystyle N^{-1}}
4.
α
{\displaystyle \alpha }
p
=
5
,
α
=
2
{\displaystyle p=5,\alpha =2}
α
1
=
2
(
m
o
d
5
)
{\displaystyle \alpha ^{1}=2\qquad (mod\quad 5)}
α
2
=
4
(
m
o
d
5
)
{\displaystyle \alpha ^{2}=4\qquad (mod\quad 5)}
α
3
=
3
(
m
o
d
5
)
{\displaystyle \alpha ^{3}=3\qquad (mod\quad 5)}
α
4
=
1
(
m
o
d
5
)
{\displaystyle \alpha ^{4}=1\qquad (mod\quad 5)}
因為
α
4
{\displaystyle \alpha ^{4}}
5
{\displaystyle 5}
1
{\displaystyle 1}
4
{\displaystyle 4}
N
=
4
{\displaystyle N=4}
N
{\displaystyle N}
(
p
−
1
)
{\displaystyle (p-1)}
[
F
(
0
)
F
(
1
)
F
(
2
)
F
(
3
)
]
=
[
1
1
1
1
1
2
4
3
1
4
1
4
1
3
4
2
]
[
f
(
0
)
f
(
1
)
f
(
2
)
f
(
3
)
]
{\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}}}
在一些特殊的情況下，令
F
=
Z
/
m
{\displaystyle F=Z/m}
m
{\displaystyle m}
Fermat Number Transform 中
(
m
=
2
k
+
1
)
{\displaystyle (m=2^{k}+1)}
Mersenne Number Transform 中
(
m
=
2
k
−
1
)
{\displaystyle (m=2^{k}-1)}
前面提到數論轉換是一種離散傅立葉轉換的特例，因此數論轉換具有許多離散傅立葉轉換的數學性質。
若F[k]為f[n]的數論轉換結果，即f[n]→F[k](NTT)
矩陣中的每個行或列，彼此正交，即任兩個行或列的內積為0
∑
n
=
0
N
−
1
α
n
l
α
−
n
k
=
∑
n
=
0
N
−
1
α
n
(
k
−
l
)
=
N
δ
k
t
{\displaystyle \sum _{n=0}^{N-1}\alpha ^{nl}\alpha ^{-nk}=\sum _{n=0}^{N-1}\alpha ^{n(k-l)}=N\delta _{kt}}
證明:
當
k
=
l
{\displaystyle k=l}
S
N
=
∑
n
=
0
N
−
1
α
n
(
0
)
=
N
{\displaystyle S_{N}=\sum _{n=0}^{N-1}\alpha ^{n(0)}=N}
當
k
≠
0
{\displaystyle k\neq 0}
(
α
n
(
k
−
l
)
−
1
)
S
N
=
(
α
n
(
k
−
l
)
−
1
)
∑
n
=
0
N
−
1
α
n
(
k
−
l
)
=
α
N
(
k
−
l
)
−
1
=
1
−
1
=
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}
NTT 符合線性轉換，即：
F
[
k
1
+
k
2
]
=
f
[
n
1
]
+
f
[
n
2
]
{\displaystyle F[k_{1}+k_{2}]=f[n_{1}]+f[n_{2}]}
並且對於常數 c 有：
F
[
c
k
]
=
c
F
[
k
]
{\displaystyle F[ck]=cF[k]}
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
−
f
[
n
]
↔
−
F
[
k
]
{\displaystyle -f[n]\leftrightarrow -F[k]}
若
f
[
n
]
↔
F
[
k
]
{\displaystyle f[n]\leftrightarrow F[k]}
f
[
n
+
l
]
↔
α
−
l
k
F
[
k
]
{\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]}
f
[
n
]
α
n
l
↔
F
[
k
+
l
]
{\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}
NTT 變換是可逆的，存在反轉換 INTT 使得：
INTT(NTT(n))=n
若
f
[
n
]
{\displaystyle f[n]}
f
[
n
]
=
f
[
N
−
n
]
{\displaystyle f[n]=f[N-n]}
f
[
n
]
{\displaystyle f[n]}
F
[
k
]
{\displaystyle F[k]}
F
[
k
]
=
F
[
N
−
k
]
{\displaystyle F[k]=F[N-k]}
若
f
[
n
]
=
−
f
[
N
−
n
]
{\displaystyle f[n]=-f[N-n]}
f
[
n
]
{\displaystyle f[n]}
F
[
k
]
{\displaystyle F[k]}
F
[
k
]
=
−
F
[
N
−
k
]
{\displaystyle F[k]=-F[N-k]}
此性質在線性非時變系統當中非常重要，NTT的主要應用多與此性質有關。
若考慮兩個信號，
f
[
n
1
]
↔
F
[
k
1
]
{\displaystyle f[n_{1}]\leftrightarrow F[k_{1}]}
f
[
n
2
]
↔
F
[
k
2
]
{\displaystyle f[n_{2}]\leftrightarrow F[k_{2}]}
f
[
n
1
]
∗
f
[
n
2
]
↔
F
[
k
1
]
F
[
k
2
]
(
mod
m
)
{\displaystyle f[n_{1}]*f[n_{2}]\leftrightarrow F[k_{1}]F[k_{2}]{\pmod {m}}}
f
[
n
1
]
f
[
n
2
]
↔
F
[
k
1
]
∗
F
[
k
2
]
(
mod
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.相對而言缺乏物理意義。
對於一些符合特殊情形的訊號，可以使用不同的轉換去進行運算，以減少運算量。其中包括使用discrete cosine transform (DCT) , discrete sine transform (DST) 以及 discrete Hartley transform (DHT) 。
給定一訊號
x
[
n
]
{\displaystyle x[n]}
x
[
n
]
=
x
[
N
−
n
]
{\displaystyle x[n]=x[N-n]}
N
−
p
o
i
n
t
{\displaystyle N-point}
D
F
T
{\displaystyle DFT}
(
f
l
o
o
r
(
N
/
2
)
+
1
)
−
p
o
i
n
t
{\displaystyle (floor(N/2)+1)-point}
D
C
T
{\displaystyle DCT}
X
C
[
m
]
=
∑
n
=
0
Q
k
n
x
[
n
]
c
o
s
(
π
m
n
Q
)
{\displaystyle X_{C}[m]=\sum _{n=0}^{Q}{k_{n}x[n]cos({\frac {\pi mn}{Q}})}}
Q
=
f
l
o
o
r
(
N
2
)
{\displaystyle Q=floor({\frac {N}{2}})}
k
n
=
1
{\displaystyle k_{n}=1}
n
=
0
{\displaystyle n=0}
N
2
{\displaystyle {\frac {N}{2}}}
k
n
=
2
{\displaystyle k_{n}=2}
可以證明，當
x
[
n
]
{\displaystyle x[n]}
X
C
[
m
]
=
X
F
[
m
]
{\displaystyle X_{C}[m]=X_{F}[m]}
X
F
[
m
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
2
π
m
n
N
{\displaystyle X_{F}[m]=\sum _{n=0}^{N-1}x[n]e^{-j{\frac {2\pi mn}{N}}}}
When
x
[
n
]
=
x
[
N
−
n
]
{\displaystyle x[n]=x[N-n]}
N
{\displaystyle N}
X
F
[
m
]
=
x
[
0
]
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
e
−
j
2
π
m
n
N
+
x
[
N
2
]
e
−
j
π
m
+
∑
n
=
1
N
/
2
−
1
x
[
N
−
n
]
e
−
j
2
π
m
(
N
−
n
)
N
{\displaystyle X_{F}[m]=x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}]e^{-j\pi m}+\sum _{n=1}^{N/2-1}x[N-n]e^{-j{\frac {2\pi m(N-n)}{N}}}}
=
x
[
0
]
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
e
−
j
2
π
m
n
N
+
x
[
N
2
]
(
−
1
)
m
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
e
j
2
π
m
(
n
)
N
{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}](-1)^{m}+\sum _{n=1}^{N/2-1}x[n]e^{j{\frac {2\pi m(n)}{N}}}}
=
x
[
0
]
+
2
∑
n
=
1
N
/
2
−
1
x
[
n
]
c
o
s
(
2
π
m
n
N
)
+
x
[
N
2
]
(
−
1
)
m
{\displaystyle \qquad \quad =x[0]+2\sum _{n=1}^{N/2-1}x[n]cos({\frac {2\pi mn}{N}})+x[{\frac {N}{2}}](-1)^{m}}
=
∑
n
=
0
N
/
2
k
n
x
[
n
]
c
o
s
(
2
π
m
n
N
)
{\displaystyle \qquad \quad =\sum _{n=0}^{N/2}{k_{n}x[n]cos({\frac {2\pi mn}{N}})}}
k
n
=
1
{\displaystyle k_{n}=1}
n
=
0
{\displaystyle n=0}
N
2
{\displaystyle {\frac {N}{2}}}
k
n
=
2
{\displaystyle k_{n}=2}
=
X
C
[
m
]
{\displaystyle \qquad \quad =X_{C}[m]}
給定一訊號
x
[
n
]
{\displaystyle x[n]}
−
x
[
n
]
=
x
[
N
−
n
]
{\displaystyle -x[n]=x[N-n]}
N
−
p
o
i
n
t
{\displaystyle N-point}
D
F
T
{\displaystyle DFT}
(
(
N
/
2
)
−
1
)
−
p
o
i
n
t
{\displaystyle ((N/2)-1)-point}
D
S
T
{\displaystyle DST}
X
S
[
m
]
=
2
∑
n
=
1
Q
−
1
x
[
n
]
s
i
n
(
π
m
n
Q
)
{\displaystyle X_{S}[m]=2\sum _{n=1}^{Q-1}{x[n]sin({\frac {\pi mn}{Q}})}}
Q
=
N
2
{\displaystyle Q={\frac {N}{2}}}
可以證明，當
x
[
n
]
{\displaystyle x[n]}
X
S
[
m
]
=
j
X
F
[
m
]
{\displaystyle X_{S}[m]=jX_{F}[m]}
X
F
[
m
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
2
π
m
n
N
{\displaystyle X_{F}[m]=\sum _{n=0}^{N-1}x[n]e^{-j{\frac {2\pi mn}{N}}}}
When
x
[
n
]
=
x
[
N
−
n
]
{\displaystyle x[n]=x[N-n]}
x
[
n
]
e
−
j
2
π
m
n
N
=
x
[
N
−
n
]
e
−
j
2
π
m
(
N
−
n
)
N
{\displaystyle x[n]e^{-j{\frac {2\pi mn}{N}}}=x[N-n]e^{-j{\frac {2\pi m(N-n)}{N}}}}
X
F
[
m
]
=
x
[
0
]
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
e
−
j
2
π
m
n
N
+
x
[
N
2
]
e
−
j
π
m
+
∑
n
=
1
N
/
2
−
1
x
[
N
−
n
]
e
−
j
2
π
m
(
N
−
n
)
N
{\displaystyle X_{F}[m]=x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}]e^{-j\pi m}+\sum _{n=1}^{N/2-1}x[N-n]e^{-j{\frac {2\pi m(N-n)}{N}}}}
=
x
[
0
]
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
e
−
j
2
π
m
n
N
+
x
[
N
2
]
(
−
1
)
m
+
∑
n
=
1
N
/
2
−
1
(
−
x
[
n
]
)
e
j
2
π
m
(
n
)
N
{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}](-1)^{m}+\sum _{n=1}^{N/2-1}(-x[n])e^{j{\frac {2\pi m(n)}{N}}}}
=
x
[
0
]
+
∑
n
=
1
N
/
2
−
1
x
[
n
]
(
e
−
j
2
π
m
n
N
−
e
j
2
π
m
n
N
)
+
x
[
N
2
]
(
−
1
)
m
{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n](e^{-j{\frac {2\pi mn}{N}}}-e^{j{\frac {2\pi mn}{N}}})+x[{\frac {N}{2}}](-1)^{m}}
=
−
2
j
∑
n
=
1
N
/
2
−
1
x
[
n
]
s
i
n
(
2
π
m
n
N
)
{\displaystyle \qquad \quad =-2j\sum _{n=1}^{N/2-1}{x[n]sin({\frac {2\pi mn}{N}})}}
=
−
j
X
S
[
m
]
{\displaystyle \qquad \quad =-jX_{S}[m]}
給定一訊號
x
[
n
]
{\displaystyle x[n]}
N
−
p
o
i
n
t
{\displaystyle N-point}
D
F
T
{\displaystyle DFT}
N
−
p
o
i
n
t
{\displaystyle N-point}
D
H
T
{\displaystyle DHT}
X
H
[
m
]
=
∑
n
=
0
N
−
1
x
[
n
]
c
a
s
(
2
π
m
n
N
)
{\displaystyle X_{H}[m]=\sum _{n=0}^{N-1}{x[n]cas({\frac {2\pi mn}{N}})}}
c
a
s
(
k
)
=
c
o
s
(
k
)
+
s
i
n
(
k
)
{\displaystyle cas(k)=cos(k)+sin(k)}
可以證明，當
x
[
n
]
{\displaystyle x[n]}
X
H
[
m
]
=
R
e
{
X
F
[
m
]
}
−
I
m
{
X
F
[
m
]
}
{\displaystyle X_{H}[m]=Re\{X_{F}[m]\}-Im\{X_{F}[m]\}}
X
F
[
m
]
=
∑
n
=
0
N
−
1
x
[
n
]
e
−
j
2
π
m
n
N
{\displaystyle X_{F}[m]=\sum _{n=0}^{N-1}x[n]e^{-j{\frac {2\pi mn}{N}}}}
=
∑
n
=
0
N
−
1
x
[
n
]
(
c
o
s
(
2
π
m
n
N
)
−
j
s
i
n
(
2
π
m
n
N
)
)
{\displaystyle \qquad \quad =\sum _{n=0}^{N-1}x[n](cos({\frac {2\pi mn}{N}})-jsin({\frac {2\pi mn}{N}}))}
R
e
{
X
F
[
m
]
}
=
∑
n
=
0
N
−
1
x
[
n
]
c
o
s
(
2
π
m
n
N
)
{\displaystyle Re\{X_{F}[m]\}=\sum _{n=0}^{N-1}x[n]cos({\frac {2\pi mn}{N}})}
I
m
{
X
F
[
m
]
}
=
−
∑
n
=
0
N
−
1
x
[
n
]
s
i
n
(
2
π
m
n
N
)
{\displaystyle Im\{X_{F}[m]\}=-\sum _{n=0}^{N-1}x[n]sin({\frac {2\pi mn}{N}})}
X
H
[
m
]
=
∑
n
=
0
N
−
1
x
[
n
]
c
a
s
(
2
π
m
n
N
)
=
∑
n
=
0
N
−
1
x
[
n
]
(
c
o
s
(
2
π
m
n
N
)
+
s
i
n
(
2
π
m
n
N
)
)
{\displaystyle X_{H}[m]=\sum _{n=0}^{N-1}{x[n]cas({\frac {2\pi mn}{N}})}=\sum _{n=0}^{N-1}{x[n](cos({\frac {2\pi mn}{N}})+sin({\frac {2\pi mn}{N}}))}}
=
∑
n
=
0
N
−
1
x
[
n
]
c
o
s
(
2
π
m
n
N
)
+
∑
n
=
0
N
−
1
x
[
n
]
s
i
n
(
2
π
m
n
N
)
{\displaystyle \qquad \quad =\sum _{n=0}^{N-1}{x[n]cos({\frac {2\pi mn}{N}})}+\sum _{n=0}^{N-1}{x[n]sin({\frac {2\pi mn}{N}})}}
=
R
e
{
X
F
[
m
]
}
−
I
m
{
X
F
[
m
]
}
{\displaystyle \qquad \quad =Re\{X_{F}[m]\}-Im\{X_{F}[m]\}}
Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., (1999). Discrete-time signal processing , Upper Saddle River, N.J. : Prentice Hall. ISBN 0137549202
Mallat, S., A Wavelet Tour of Signal Processing, Second Edition , Academic Press, ISBN 0-12-466606-x
Gill, J., Fourier Transform and Its Applications （[1] （页面存档备份 ，存于互联网档案馆 ））
Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2024 (2025)
Duhamel, Pierre, and Martin Vetterli. "Fast Fourier transforms: a tutorial review and a state of the art." Signal processing 19.4 (1990): 259-299.
![{\displaystyle \left\{x[n]\right\}_{0\leq n<N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/883dc532309399593abe489d2c982030882b92df)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/526d8c9103309b720516b7ee79e79186b15c81e3)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74d2a9e7f31ef1b808bfbc8d2355aff7703c2064)
![{\displaystyle [0,L]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53e3bfad6c2b8297e8c8d2e84ce8f869d69b0d86)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83eedd5085dd500d5f7d7d2f03b6dfd7e4bdbbd6)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/103c335c7408247ff029a6e4ac8493dc57dc62ad)
![{\displaystyle x[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864cbbefbdcb55af4d9390911de1bf70167c4a3d)
![{\displaystyle {\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d079d9387528481918eb9e2ac9686fc8ffe2f2a2)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/495f6951be5f0273e07cef0bb64e7ee5310ffe76)
![{\displaystyle {\hat {x}}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13a06c5cd662791be7e5195c1ce21418a1a7a56c)
![{\displaystyle {\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34ec3d791f0da32c11d497d7aad5b70fb3163dad)
![{\displaystyle x'[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4c7d9f6b3047f4fccbbc9addd6947c3e0ac3a7e)
![{\displaystyle {\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28bd0debc1aae0f960082ae3e65075f333c42a6c)
![{\displaystyle \langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f13ff7fffea851e9c9109597a0cf4a5e0a2e809c)
![{\displaystyle \{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k<N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbced45f701fbae40d8b8fd9c99d1bd3446f8c41)
![{\displaystyle {\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eff3e84cd3d83f4333434301d3401c57905daad6)
![{\displaystyle x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b3769784fd1b1f283a74910baa632a264c2fc43)
![{\displaystyle {\tilde {x}}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f0b944d1740999c970befbae73c94687b80ee69)
![{\displaystyle {\tilde {y}}[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa564a407730408eec6f4ff38eae230727e1fa8d)
![{\displaystyle x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2f396b14bdc802a2c20c608c365062425239c40)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14cd79279dadc66db4a8b6d0413387726080ae18)
![{\displaystyle {L}x[n]=(x\otimes y)[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6eb0cb170e7a883a32425b17e4bf273eb55ab2cb)
![{\displaystyle {L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51a8d0c0bd4ab397e90060a7998ff030c02561cd)
![{\displaystyle {\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/875bba0bc3622841463d9b5c27b33d08c0e27ca7)
![{\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b5ae80e3c29d7fc911df70abbcd11a02b956e9d)
![{\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}{\pmod {M}}\quad n=0,1,2,\ldots ,N-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc04903b711ec40cd564e396963030274d7f3253)
![{\displaystyle F[k_{1}+k_{2}]=f[n_{1}]+f[n_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8221b5124e0a8c2be9b0788ce18149a7fec9b2a8)
![{\displaystyle F[ck]=cF[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8300a2e0e86abab4fc57e891881af254ce3569ef)
![{\displaystyle f[n]\leftrightarrow F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c270965e7225021b5807cb2a0bc0082c717d1c0)
![{\displaystyle -f[n]\leftrightarrow -F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0dff1cadd3aec0e7ef388de6bc8b2da9326de3f0)
![{\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/556178f16e9f3cdd487e45089246924a19846ea4)
![{\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/740c0342528c72337ccff5ead61d2768509a2d4b)
![{\displaystyle f[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b176b3dbcced447341ad5ab70001ef0e3231062e)
![{\displaystyle f[n]=f[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1be38aeb60f3dc3b84bddbdb1860fe384c49237c)
![{\displaystyle F[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b1a4da8ed199ca114765442e28d409694b6485f)
![{\displaystyle F[k]=F[N-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/012a5775e172f5beee85cdc07097534631c3976f)
![{\displaystyle f[n]=-f[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22bfea3756093c07cb80fa7f8eb015beff5ae936)
![{\displaystyle F[k]=-F[N-k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6808e18eebce96aa50d295e7e399439c3567ed7)
![{\displaystyle f[n_{1}]\leftrightarrow F[k_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd3360f5f1d9d26a35b15b4cf6d67696f42a6842)
![{\displaystyle f[n_{2}]\leftrightarrow F[k_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e9f59704e0e2ddb50e4f07e6468f9e8593eec24)
![{\displaystyle f[n_{1}]*f[n_{2}]\leftrightarrow F[k_{1}]F[k_{2}]{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/975d26daa29cb3cb64f425b6138d027990328bfc)
![{\displaystyle f[n_{1}]f[n_{2}]\leftrightarrow F[k_{1}]*F[k_{2}]{\pmod {m}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0509df49aff3dcbc96c66f89a53091f32725c397)
![{\displaystyle x[n]=x[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc0d54b69515eec68136029c82eee6ba6b9b9390)
![{\displaystyle X_{C}[m]=\sum _{n=0}^{Q}{k_{n}x[n]cos({\frac {\pi mn}{Q}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b899eddcec5a3ae97dab3959c721d52b2a67a0)
![{\displaystyle X_{C}[m]=X_{F}[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fb0fd0dcc7778cfbb3e44971310ff5b2c865f4c)
![{\displaystyle X_{F}[m]=\sum _{n=0}^{N-1}x[n]e^{-j{\frac {2\pi mn}{N}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08017393480775c8f400c12c65fea7eded81fb24)
![{\displaystyle X_{F}[m]=x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}]e^{-j\pi m}+\sum _{n=1}^{N/2-1}x[N-n]e^{-j{\frac {2\pi m(N-n)}{N}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1306c619a1cfca1c763773acf2e3eccae737312b)
![{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}](-1)^{m}+\sum _{n=1}^{N/2-1}x[n]e^{j{\frac {2\pi m(n)}{N}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2effc80a9085aa5f8afd6699c1d44076713152a7)
![{\displaystyle \qquad \quad =x[0]+2\sum _{n=1}^{N/2-1}x[n]cos({\frac {2\pi mn}{N}})+x[{\frac {N}{2}}](-1)^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84fd44da791c85def0c8ba1b0a8f16e50df22ca7)
![{\displaystyle \qquad \quad =\sum _{n=0}^{N/2}{k_{n}x[n]cos({\frac {2\pi mn}{N}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b4a35804e75c8ae620d7d70ed279dfa19869b64)
![{\displaystyle \qquad \quad =X_{C}[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5268f5d7d3b51a23132f40f0aff4a6ad8fe7a8d)
![{\displaystyle -x[n]=x[N-n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c75c5caa7f0e1853e09c39690b1d8eb41388fbc)
![{\displaystyle X_{S}[m]=2\sum _{n=1}^{Q-1}{x[n]sin({\frac {\pi mn}{Q}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c81d0568e6f691aac2588225f22c8f768613f562)
![{\displaystyle X_{S}[m]=jX_{F}[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b35f3425fa8ba914bbf2cdb7d002a53f29661e44)
![{\displaystyle x[n]e^{-j{\frac {2\pi mn}{N}}}=x[N-n]e^{-j{\frac {2\pi m(N-n)}{N}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d85473544b341ed0531d5e7f18345b4bce73517)
![{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n]e^{-j{\frac {2\pi mn}{N}}}+x[{\frac {N}{2}}](-1)^{m}+\sum _{n=1}^{N/2-1}(-x[n])e^{j{\frac {2\pi m(n)}{N}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ceab98e18232acf92bac17493be4d0157bf09ef)
![{\displaystyle \qquad \quad =x[0]+\sum _{n=1}^{N/2-1}x[n](e^{-j{\frac {2\pi mn}{N}}}-e^{j{\frac {2\pi mn}{N}}})+x[{\frac {N}{2}}](-1)^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/344e20a73286236424824ac1702cfad1ab0afa95)
![{\displaystyle \qquad \quad =-2j\sum _{n=1}^{N/2-1}{x[n]sin({\frac {2\pi mn}{N}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b040020b973cdd541c7c3661a66c430a8a981ee2)
![{\displaystyle \qquad \quad =-jX_{S}[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac8d598001a2146c9afad19b87c403e3bc11ea3b)
![{\displaystyle X_{H}[m]=\sum _{n=0}^{N-1}{x[n]cas({\frac {2\pi mn}{N}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31c1c32a968340a9558bd07a6f4a3b0e6c41c318)
![{\displaystyle X_{H}[m]=Re\{X_{F}[m]\}-Im\{X_{F}[m]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f4e9be3d84bfce4a97a13b2e9fdba86b4ed374)
-jsin({\frac {2\pi mn}{N}}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca296c61b03c998d81bef4c3fb74a2fd5d4fff55)
![{\displaystyle Re\{X_{F}[m]\}=\sum _{n=0}^{N-1}x[n]cos({\frac {2\pi mn}{N}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b4c8b90a597f62fabb97652a519f8ba98de55f1)
![{\displaystyle Im\{X_{F}[m]\}=-\sum _{n=0}^{N-1}x[n]sin({\frac {2\pi mn}{N}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dca292561e4b15f4a937da87e78033139429661)
![{\displaystyle X_{H}[m]=\sum _{n=0}^{N-1}{x[n]cas({\frac {2\pi mn}{N}})}=\sum _{n=0}^{N-1}{x[n](cos({\frac {2\pi mn}{N}})+sin({\frac {2\pi mn}{N}}))}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b92930d9cd2877495c23b6a6d10292b949fc927)
![{\displaystyle \qquad \quad =\sum _{n=0}^{N-1}{x[n]cos({\frac {2\pi mn}{N}})}+\sum _{n=0}^{N-1}{x[n]sin({\frac {2\pi mn}{N}})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11b95fb5eecc5f24a19547e4ac01b61f93e12e3b)
![{\displaystyle \qquad \quad =Re\{X_{F}[m]\}-Im\{X_{F}[m]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05d3e140bc9ce84aac27639251eebb147350a2e1)