离散傅里叶变换（DFT）及其快速算法是数字信号处理领域中的核心概念，广泛应用于音频、图像处理以及通信工程。本节将详细讲解DFT的起源、性质及其相关变换，包括DFS（离散傅里叶级数）、Z变换、IDFT（逆离散傅里叶变换）和FFT（快速傅里叶变换）。 DFT是离散时间信号的傅里叶变换，用于将无限长或周期性的离散信号转换到频域进行分析。对于一个有限长的离散序列 \( x[n] \)，其DFT定义为： \[ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi kn/N} \] 其中 \( N \) 是序列的长度，\( k \) 表示频域的离散点，\( j \) 是虚数单位。DFT提供了一种将时域信号转换为离散频率成分的方法，便于分析信号的频谱特性。 DFS是DFT的一个特例，适用于周期性离散信号，它基于傅里叶级数的概念，通过离散频率项来表示周期性信号。DFS与DTFT（离散时间傅里叶变换）的区别在于DFS的频谱是离散的，而DTFT的频谱是连续的。 Z变换是一种将离散序列转换为复频域的数学工具，它与DTFT和DFS有着密切关系。Z变换为： \[ X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n} \] 在某些条件下，Z变换可以转化为DTFT或者DFS，提供了解析信号特性的另一种途径。 IDFT是DFT的逆变换，用于将频域表示的信号还原回时域。它的公式为： \[ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j 2\pi kn/N} \] FFT是DFT的快速算法，极大地提高了计算效率。它利用了DFT的对称性和分治策略，将DFT的复杂度从 \( O(N^2) \) 降低到 \( O(N \log N) \)，使得大规模数据的傅里叶变换变得可行。 在实际应用中，如MATLAB等软件通常内置了FFT函数，方便用户快速计算DFT并进行频谱分析。例如，对于一个信号序列，可以使用MATLAB的`fft`函数计算其DFT，然后通过`ifft`函数进行反变换回到时域。 总结四种傅里叶变换形式： 1. 连续傅里叶变换（FT）：非周期连续时间信号，频域连续。 2. 傅里叶级数（FS）：周期连续时间信号，频域离散。 3. 离散时间傅里叶变换（DTFT）：非周期离散时间信号，频域连续。 4. 离散傅里叶级数（DFS）：周期离散时间信号，频域离散。 每种变换都有其适用的场景，选择合适的变换可以更有效地分析和处理不同类型的信号。在数字信号处理中，DFT和FFT因其高效性和广泛的应用性，成为了不可或缺的工具。

Gabor变换的中文书籍，值得一看！浅显易懂。

2、实数序列的FFT 以上讨论的FFT算法都是复数运算,包括序列x(n)也认为是复数,但大多数场合,信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号x(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散傅里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算,下面介绍两种方法。  （1）用 一个N点FFT同时计算两个N点实序列的DFT 设x (n)、y (n)是彼此独立的两个N点实序列,且 X (k)=DFT[x (n)] ， Y (k)=DFT[y(n)] 则X (k)、Y(k)可通过一次FFT运算同时获得。 首先将x (n)、y(n)分别当作一复序列的实部及虚部,令 g(n)=x (n)+jy(n)

离散傅里叶变换及其快速算法