离散傅里叶变换（DFT）要解决两个问题：一是信号离散化后它的频谱情况；二是快速运算算法。第一个问题将涉及周期离散信号的傅里叶级数（DFS），以及由DFS得到非周期信号的离散时间傅里叶变换（DTFT）和有限长序列的离散频谱表示；第二个问题将涉及DFT的快速算法——快速傅里叶变换（FFT）。

与周期模拟信号一样，周期离散信号同样可以展成傅里叶级数形式，并由此得出一新的变换对——离散傅里叶级数（Discrete Fourier Series），简记为DFS。

（一）离散傅里叶级数（DFS）的引入

可以从连续周期信号傅里叶级数的复指数形式导出周期序列的DFS。连续周期信号傅里叶级数的复指数形式为 x ( t ) = ∑ k = − ∞ ∞ X ( k w 0 ) e j k w 0 t (1) x(t)=\sum_{k=-\infty}^{\infty}X(kw_0)e^{jkw_0t} \tag{1} x(t)=k=−∞∑∞​X(kw0​)ejkw0​t(1)

X ( k w 0 ) = 1 T 0 ∫ 0 T 0 x ( t ) e − j k w 0 t d t k = 0 , 1 , 2 , ⋯ (2) X(kw_0)=\frac{1}{T_0}\int_0^{T_0}x(t)e^{-jkw_0t}dt \quad k=0,1,2,\cdots \tag{2} X(kw0​)=T0​1​∫0T0​​x(t)e−jkw0​tdtk=0,1,2,⋯(2)

对连续周期信号 x ( t ) x(t) x(t)的一个周期 T 0 T_0 T0​进行N点采样，即 T 0 = N T , w 0 = 2 π T 0 = 2 π N T T_0=NT,w_0=\frac{2\pi}{T_0}=\frac{2\pi}{NT} T0​=NT,w0​=T0​2π​=NT2π​，T为采样周期，这样采样得到的离散序列 x ( n ) x(n) x(n)是以N为周期的周期序列，即 x ( n ) = x ( n + m N ) ( m 为 任 意 整 数 ) x(n)=x(n+mN) \quad (m为任意整数) x(n)=x(n+mN)(m为任意整数) 设 Ω 0 = w 0 T = 2 π N \Omega_0=w_0T=\frac{2\pi}{N} Ω0​=w0​T=N2π​为离散域的基本频率，单位为弧度， k Ω 0 k\Omega_0 kΩ0​是k次谐波的数字频率。这样，在式（2）中， t = n T , d t = T t=nT,dt=T t=nT,dt=T，在一个周期内的积分变为在一个周期内的累加，即 X ( k Ω 0 T ) = 1 N T ∑ n = 0 N − 1 x ( n T ) e − j k Ω 0 T n T T = 1 N ∑ n = 0 N − 1 x ( n T ) e − j k Ω 0 n X(k\frac{\Omega_0}{T})=\frac{1}{NT}\sum_{n=0}^{N-1}x(nT)e^{-jk\frac{\Omega_0}{T}nT}T=\frac{1}{N}\sum_{n=0}^{N-1}x(nT)e^{-jk\Omega_0n} X(kTΩ0​​)=NT1​n=0∑N−1​x(nT)e−jkTΩ0​​nTT=N1​n=0∑N−1​x(nT)e−jkΩ0​n 在序列表示中，可仅用 n n n表示nT，对应地，用 k Ω 0 k\Omega_0 kΩ0​表示 k Ω 0 T k\frac{\Omega_0}{T} kTΩ0​​，则上式为 X ( k Ω 0 ) = 1 N ∑ n = 0 N − 1 x ( n ) e − j k Ω 0 n = 1 N ∑ n = − N 2 N 2 x ( n ) e − j k Ω 0 n k = 0 , 1 , 2 , ⋯   , N − 1 (3) X(k\Omega_0)=\frac{1}{N}\sum_{n=0}^{N-1}x(n)e^{-jk\Omega_0 n}=\frac{1}{N}\sum_{n=-\frac{N}{2}}^{\frac{N}{2}}x(n)e^{-jk\Omega_0n} \quad k=0,1,2,\cdots,N-1 \tag{3} X(kΩ0​)=N1​n=0∑N−1​x(n)e−jkΩ0​n=N1​n=−2N​∑2N​​x(n)e−jkΩ0​nk=0,1,2,⋯,N−1(3) X ( k Ω 0 ) X(k\Omega_0) X(kΩ0​)是变量k的周期函数，周期为N，因为对任意整数q有 x ( ( k + q N ) Ω 0 ) = X ( k Ω 0 ) x((k+qN)\Omega_0)=X(k\Omega_0) x((k+qN)Ω0​)=X(kΩ0​) 当周期信号从连续域变换到离散域以后，它的频率 w w w从 − ∞ ∼ + ∞ -\infty\sim +\infty −∞∼+∞的无限范围映射到数字频率 Ω \Omega Ω从 0 ∼ 2 π 0\sim 2\pi 0∼2π的有限范围。因此，连续周期信号的傅里叶级数可表示为具有无限多个谐波分量，而离散周期信号只含有有限个谐波分量，其谐波数为 k = 2 π Ω 0 = N k=\frac{2\pi}{\Omega_0}=N k=Ω0​2π​=N。所以对应于式（1）离散化处理后为 x ( n ) = ∑ k = 0 N − 1 X ( k Ω 0 ) e j k Ω 0 T n T = ∑ k = 0 N − 1 X ( k Ω 0 ) e j k Ω 0 n (4) x(n)=\sum_{k=0}^{N-1}X(k\Omega_0)e^{jk\frac{\Omega_0}{T}nT}=\sum_{k=0}^{N-1}X(k\Omega_0)e^{jk\Omega_0 n} \tag{4} x(n)=k=0∑N−1​X(kΩ0​)ejkTΩ0​​nT=k=0∑N−1​X(kΩ0​)ejkΩ0​n(4) 从式（3）和式（4）可以看出， x ( n ) x(n) x(n)以N为周期， x ( n ) x(n) x(n)的频谱就以 Ω 0 = 2 π N \Omega_0=\frac{2\pi}{N} Ω0​=N2π​的基本频率为间距离散化了。由此可以得到一个结论：周期序列的频谱是离散的。在前面的内容，我们看到了信号时域离散化、频域周期化这种现象；在这里，有完全对称的另一种情况，那就是时域周期化，频域离散化。

式（3）和式（4）描述了 x ( n ) x(n) x(n)和 X ( k Ω 0 ) X(k\Omega_0) X(kΩ0​)相互计算的一对关系式。其中式（4）可以看作周期系列 x ( n ) x(n) x(n)的傅里叶级数展开式，而 X ( k Ω 0 ) X(k\Omega_0) X(kΩ0​)则可以看作是 x ( n ) x(n) x(n)的傅里叶级数展开式的系数。人们称满足这对关系式的周期序列 x ( n ) x(n) x(n)和 X ( k Ω 0 ) X(k\Omega_0) X(kΩ0​)为离散傅里叶级数变换对，简记为 x ( n ) ↔ D F S X ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0) x(n)↔DFSX(kΩ0​) 或者表示为 D F S [ x ( n ) ] = X ( k Ω 0 ) DFS[x(n)]=X(k\Omega_0) DFS[x(n)]=X(kΩ0​)和 I D F S [ X ( k Ω 0 ) ] = x ( n ) IDFS[X(k\Omega_0)]=x(n) IDFS[X(kΩ0​)]=x(n)。即正变换为式（3），反变换为（4）。

（二）DFS的主要性质

若 x ( n ) ↔ D F S X ( k Ω 0 ) , y ( n ) ↔ D F S Y ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0),y(n) \overset{DFS}{\leftrightarrow}Y(k\Omega_0) x(n)↔DFSX(kΩ0​),y(n)↔DFSY(kΩ0​)，则 a x ( n ) + b y ( n ) ↔ D F S a X ( k Ω 0 ) + b Y ( k Ω 0 ) ax(n)+by(n) \overset{DFS}{\leftrightarrow}aX(k\Omega_0)+bY(k\Omega_0) ax(n)+by(n)↔DFSaX(kΩ0​)+bY(kΩ0​)

若 x ( n ) ↔ D F S X ( k Ω 0 ) , h ( n ) ↔ D F S H ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0),h(n) \overset{DFS}{\leftrightarrow}H(k\Omega_0) x(n)↔DFSX(kΩ0​),h(n)↔DFSH(kΩ0​)，则 x ( n ) ⨀ h ( n ) ↔ D F S X ( k Ω 0 ) H ( k Ω 0 ) x ( n ) h ( n ) ↔ D F S 1 N X ( k Ω 0 ) ⨀ H ( k Ω 0 ) x(n)\bigodot h(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0)H(k\Omega_0)\\ x(n)h(n) \overset{DFS}{\leftrightarrow} \frac{1}{N}X(k\Omega_0)\bigodot H(k\Omega_0) x(n)⨀h(n)↔DFSX(kΩ0​)H(kΩ0​)x(n)h(n)↔DFSN1​X(kΩ0​)⨀H(kΩ0​) ⨀ \bigodot ⨀为周期卷积的符号，两周期序列 x ( n ) x(n) x(n)和 h ( n ) h(n) h(n)的周期卷积定义为 x ( n ) ⨀ h ( n ) = h ( n ) ⨀ x ( n ) = ∑ k = 0 N − 1 x ( k ) h ( n − k ) x(n)\bigodot h(n)=h(n)\bigodot x(n)=\sum_{k=0}^{N-1}x(k)h(n-k) x(n)⨀h(n)=h(n)⨀x(n)=k=0∑N−1​x(k)h(n−k) 周期卷积和线性卷积的惟一区别在于 周期卷积时仅仅在单个周期内求和，而线性卷积则是对所有的k值求和。

若 x ( n ) ↔ D F S X ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0) x(n)↔DFSX(kΩ0​)，则 x ∗ ( − n ) ↔ D F S X ∗ ( k Ω 0 ) x^*(-n) \overset{DFS}{\leftrightarrow}X^*(k\Omega_0) x∗(−n)↔DFSX∗(kΩ0​) *表示复共轭

若 x ( n ) ↔ D F S X ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0) x(n)↔DFSX(kΩ0​)，则 x ( n − m ) ↔ D F S e − j k Ω 0 m X ( k Ω 0 ) x(n-m) \overset{DFS}{\leftrightarrow}e^{-jk\Omega_0m}X(k\Omega_0) x(n−m)↔DFSe−jkΩ0​mX(kΩ0​)

设 x ( n ) ↔ D F S X ( k Ω 0 ) , h ( n ) ↔ D F S H ( k Ω 0 ) x(n) \overset{DFS}{\leftrightarrow}X(k\Omega_0),h(n) \overset{DFS}{\leftrightarrow}H(k\Omega_0) x(n)↔DFSX(kΩ0​),h(n)↔DFSH(kΩ0​)，则 ∑ n = 0 N − 1 x ( n ) h ∗ ( n ) = 1 N ∑ k = 0 N − 1 X ( k Ω 0 ) H ∗ ( k Ω 0 ) \sum_{n=0}^{N-1}x(n)h^*(n)=\frac{1}{N}\sum_{k=0}^{N-1}X(k\Omega_0)H^*(k\Omega_0) n=0∑N−1​x(n)h∗(n)=N1​k=0∑N−1​X(kΩ0​)H∗(kΩ0​) 特别地，当 x ( n ) = h ( n ) x(n)=h(n) x(n)=h(n)时，有 ∑ n = 0 N − 1 ∣ x ( n ) ∣ 2 = 1 N ∑ k = 0 N − 1 ∣ X ( k Ω 0 ) ∣ 2 \sum_{n=0}^{N-1}|x(n)|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X(k\Omega_0)|^2 n=0∑N−1​∣x(n)∣2=N1​k=0∑N−1​∣X(kΩ0​)∣2