本篇文章主要介绍离散傅里叶变换（DFT）的概念、推导、实现及性质以及用DFT实现的线性卷积。

根据数字信号处理知识点总结（二）中的公式（5）可知，一个非周期离散无限长信号进行离散时间傅里叶变换（DTFT）后频谱是连续周期的，以相距 ω = 2 π / N \omega = 2\pi /N ω=2π/N的等分点对该频谱进行采样就会产生一个DFS序列（其是离散周期的，如数字信号处理知识点总结（二）的公式（7）所示），对其进行IDFS（离散傅里叶合成）则会产生周期离散的序列 x ~ ( n ) \tilde x(n) x~(n)。

但是，实际上大多数用于计算机处理的信号都不是周期的，而且计算机也只能处理有限长的信号。理论上，有两种方法可以实现：第一种就是在该有限长序列的两边添上无限的零信号，便能运用DTFT的相关理论进行求解；第二种便是对有限长序列进行周期延拓，运用离散时间傅里叶分解（DFS）进行求解。两种方法都是把有限长信号转变为无限长信号进行求解。第一种方法由于需要存储无限多（或者趋向无限多）的零，对计算机存储性能较大，故不允采用。第二种方法中，周期延拓后的周期信号的主值区间（周期序列延拓的第一个周期）就是原本的有限长信号，然后对这个周期信号应用DFS，DFS后得到结果的主值周期可以定义为离散傅里叶变换（DFT）。

定义一个有限长序列 x ( n ) x(n) x(n)，它在 0 ≤ n ≤ N − 1 0 \le n \le N - 1 0≤n≤N−1上有N个样本，作为一个N点序列。令 x ~ ( n ) \tilde x(n) x~(n)是用这个N点序列 x ( n ) x(n) x(n)创建的一个周期为N的周期信号，如公式（1）所示： x ~ ( n ) = ∑ r = − ∞ ∞ x ( n − r N ) (1) \tilde x(n) = \sum\limits_{r = - \infty }^\infty {x(n - rN)} \tag{1} x~(n)=r=−∞∑∞​x(n−rN)(1) 该式子通过模N运算（modulo-N）可以简化得到公式（2）： x ~ ( n ) = x ( n   m o d   N ) (2) \tilde x(n) = x(n\bmod N)\tag{2} x~(n)=x(nmodN)(2) 模N运算可以简单地说明：如果宗量n是在0和N-1之间，那就是它自己；否则，从n开始加或减N的倍数，直到结果是在0和N-1之间为止。 x ( n ) x(n) x(n)的长度应当是N或小于N时才成立，否则若n取值大于N，则会发生频谱的混叠。公式（2）可以使用公式（3）来表示： x ( ( n ) ) n = Δ x ( n   m o d   N ) (3) x{((n))_n}\mathop = \limits^\Delta x(n\bmod N)\tag{3} x((n))n​=Δx(nmodN)(3) 综上 x ( n ) x(n) x(n)和 x ~ ( n ) \tilde x(n) x~(n)之间的关系是 x ~ ( n ) = x ( ( n ) ) N x ( n ) = x ~ ( n ) R N ( n ) (4) \begin{array}{l} \tilde x(n) = x{((n))_N}\\\tag{4} {\rm{x}}(n) = \tilde x(n){R_N}(n) \end{array} x~(n)=x((n))N​x(n)=x~(n)RN​(n)​(4) 其中，公式（4）的第一个式子是周期延拓，第二个式子是时窗运算， R N ( n ) {R_N}(n) RN​(n)是时窗函数。

由 X ~ ( k ) = Δ D F S [ x ~ ( n ) ] {\tilde X}(k)\mathop = \limits^\Delta DFS[{\tilde x}(n)] X~(k)=ΔDFS[x~(n)],可以推导得到一个N点序列的离散傅里叶变换为： X ( k ) = Δ D F T [ x ( n ) ] = { X ~ ( k ) , 0 ≤ k ≤ N − 1 0 , o t h e r = X ~ ( k ) R N ( k ) (5) {\rm{X}}(k)\mathop = \limits^\Delta DFT[x(n)] = \left\{ \begin{array}{l} {\rm{\tilde X}}(k),0 \le k \le N - 1\\ 0,other \end{array} \right. = {\rm{\tilde X}}(k){R_N}(k)\tag{5} X(k)