傅里叶变换

\begin{align*} \widehat{f}(w) =& \int_{-\infty}^{+\infty} f(x) e^{-ixw} dx \\ =&\int_{-\infty}^{+\infty} f(x) (\cos wx - i\sin wx) dx \\ =& \int_{-\infty}^{+\infty} f(x) \cos wx dx  - i \int_{-\infty}^{+\infty} f(x) \sin wx dx \qquad (1) \end{align*}

$\widehat{f}$的 Fourier逆变换,

\[f(x) = \frac{1}{2\pi}\int_{-\infty}^{+\infty} \widehat{f}(w)e^{iwx} d w \qquad (2)\]

当频率 w=0 时,  $\widehat{f}(0)=\int_{-\infty}^{\infty} f(x) dx$ 代表了函数 f(x) 在$(-\infty,\infty)$ 上的积分，即该函数围成的面积。

当频率 w=1 时,

\begin{align*} \widehat{f}(1)=& \int_{-\infty}^{\infty} f(x) e^{-i x} dx \\ =& \int_{-\infty}^{\infty} f(x)(\cos  x  - i\sin x) dx \end{align*}

分解成实数轴 $f(x)\cos x$和虚数轴 $f(x)\sin x$ 两个函数，然后分别积分，积分得到的2 个值，构成一个复数赋值给$\widehat{f}(1)$。

更一般地，$w=w_0$ 时，分解成实数轴 $f(x)\cos w_0 x$ 和虚数轴 $f(x)\sin w_0 x$ 两个函数分别积分后构成的复数。

和傅里叶级数进行对比，对于周期为 2T 的实函数 f(x) ， 傅里叶级数($\omega_0=\frac{2\pi}{2T}=\frac{\pi}{T}$)

\[\varphi(x) = a_0 + \sum_{n=1}^{\infty} (a_n\cos n\omega_0 x + b_n\sin n\omega_0 x) ,\]

的系数为：

\begin{align*} a_0 =& \frac{1}{2T} \int_{-T}^{T} f(x) dx \\ a_n =& \frac{1}{T} \int_{-T}^{T} f(x) \cos n\omega_0 x dx \\ b_n =& \frac{1}{T} \int_{-T}^{T} f(x) \sin n\omega_0 x dx \end{align*}

和上面的 (1) 式对比，$a_0$为直流分量，$(a_n, -b_n)$ 类似于傅里叶变换在$nw_0$频率的复数值。

离散傅里叶变换DFT

\[F(u) = \sum_{x=0}^{M-1} f(x) e^{-i2\pi u x/M}, \quad u=0,1,2,\dots,M-1 \quad \qquad (3) \]

和离散傅里叶反变换(IDFT)

\[f(x)=\frac{1}{M}\sum_{u=0}^{M-1} F(u) e^{i2\pi ux/M}, x=0,1,2,\dots,M-1 \qquad (4)\]

这里我们使用x和u来分别表示一维离散空间变量和一维频率变量。给定一个由f(x) 的M 个样本组成的集合$\{f(x)\}$, 式(3) 得出一个与输入样本集合离散傅里叶变换相对应的M 个复数离散值的样本集合$\{F(u)\}$。反之,给定$\{F(u)\}$,我们可以用傅里叶反变换(IDFT) 复原样本集$\{f(x)\}$

证明(3)和(4)组成傅里叶变换对，需要用到指数正交性质：

\begin{align*} \sum_{x=0}^{M-1} e^{i2\pi rx/M} e^{-i2\pi ux/M} =\left\{\begin{array}{l} M, \quad r=u\\ 0,\quad  \text{其他} \end{array}\right. \qquad (5)\end{align*}

其中 r, u 为 0 到 M-1 的整数。

证明：

\begin{align*} \sum_{x=0}^{M-1} e^{i2\pi rx/M} e^{-i2\pi ux/M} = \sum_{x=0}^{M-1} e^{i2\pi (r-u)x/M} \end{align*}

当 r=u 时, 由 $e^0=1$, 可知左式=M 。

当$r \ne u$ 时, 不妨记$k=r-u$, k 的取值范围为 $-(M-1),\dots,-1, 1, \dots, M-1$, 则

\begin{align*} \sum_{x=0}^{M-1} e^{i2\pi (r-u)x/M} = \sum_{x=0}^{M-1} e^{i2\pi kx/M} . \qquad (6) \end{align*}

记1的M次方根为

\[\omega_k=e^{i2\pi k /M}, k = 0, 1,\dots, M-1\]

(6) 式中，当 k = 1 时，等价于1 的所有M次方根$1,\omega_1, \omega_1^2,\dots,\omega_1^{M-1}$之和零。

如果把所有的向量旋转一个$\omega_1$向量所代表的$\frac{2\pi}{M}$ 角度后，所以它们的向量和也应该旋转相同的角度 $\frac{2\pi}{M}$ 。但是容易看出所有向量旋转$\frac{2\pi}{M}$ 角度后，构成的图形没有变化，旋转后的向量仍然是这些向量,即

\[(1,\omega_1, \omega_1^2,\dots,\omega_1^{M-1})\omega_1 = (\omega_1, \omega_1^2, \dots, \omega_1^{M-1}, 1)\]

因此，旋转前后所有的向量之和不变。只有一种可能: 向量和为零向量！

当 $k = 2, 3,\dots M-1$ 时，参与求和的根向量为

\[1,\omega_k,\omega_k^2,\dots,\omega_k^{M-1},\]

同样把所有的向量旋转一个$\omega_k$向量所代表的$\frac{2\pi k}{M}$ 角度后，它们的向量和也应该旋转相同的角度 $\frac{2\pi k}{M}$ 。由于

\[(1,\omega_k, \omega_k^2,\dots,\omega_k^{M-1})\omega_k = (\omega_k, \omega_k^2, \dots, \omega_k^{M-1}, 1)\]

同样旋转后的向量仍然是这些向量。因此，旋转前后所有的向量之和不变。 所以向量和只能为零向量。

证明(3)和(4)组成傅里叶变换对. 

证明：对于长度为 M 的序列$X = (x_1, x_2, \dots, x_M)^{'}$，假设

\[W=e^{-i\frac{2\pi}{M}} .\]

W 为 1 的M次方根，只不过是反向旋转。那么离散傅里叶变换的矩阵

\begin{align*} A = \begin{pmatrix} W^0 & W^0 & W^0 & \dots & W^0 \\ W^0 & W^1 & W^2 & \dots & W^{M-1} \\ W^0 & W^2 & W^{2\times 2} & \dots & W^{2\times (M-1)} \\ \vdots & \vdots & \vdots & & \vdots \\ W^0 & W^{M-1} & W^{2(M-1)} & \dots & W^{(M-1)(M-1)} \\ \end{pmatrix} . \end{align*}

离散傅里反叶变换的矩阵

\begin{align*} B = \frac{1}{M}\begin{pmatrix} W^0 & W^0 & W^0 & \dots & W^0 \\ W^0 & W^{-1} & W^{-2} & \dots & W^{-(M-1)} \\ W^0 & W^{-2} & W^{-2\times 2} & \dots & W^{-2\times (M-1)} \\ \vdots & \vdots & \vdots & & \vdots \\ W^0 & W^{-(M-1)} & W^{-2(M-1)} & \dots & W^{-(M-1)(M-1)} \\ \end{pmatrix} . \end{align*}

根据指数的正交性，可知 $AB=I$ ，即 A, B 互为逆矩阵，所以

\[B(Ax)=(BA)x=x .\]

例1 假设有一个序列长度N=4，具体的$x(n)=\{1, 2,-1,3\}$，n=0，1，2，3。

首先，由N=4得到 ：

\[W=e^{-i\frac{2\pi}{4}} = -j .\]

于是有

\begin{align*} \begin{pmatrix} X(0) \\ X(1) \\ X(2) \\ X(3) \\ \end{pmatrix} =& \begin{pmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^1 & W^2 & W^3 \\ W^0 & W^2 & W^4 & W^6 \\ W^0 & W^3 & W^6 & W^9 \\ \end{pmatrix} \begin{pmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \\ \end{pmatrix} \\ =&\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \\ \end{pmatrix} \begin{pmatrix} 1 \\ 2 \\ -1 \\ 3 \\ \end{pmatrix} = \begin{pmatrix} 5 \\ 2+j \\ -5 \\ 2-j \\ \end{pmatrix} \end{align*} 反变换 \begin{align*} x(n) =& \frac{1}{4} \begin{pmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^{-1} & W^{-2} & W^{-3} \\ W^0 & W^{-2} & W^{-4} & W^{-6} \\ W^0 & W^{-3} & W^{-6} & W^{-9} \\ \end{pmatrix} \begin{pmatrix} 5 \\ 2+j \\ -5 \\ 2-j \\ \end{pmatrix} \\ =&\frac{1}{4} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \\ \end{pmatrix} \begin{pmatrix} 5 \\ 2+j \\ -5 \\ 2-j \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ -1 \\ 3\\ \end{pmatrix} \end{align*}