Note

本章核心：定义有限离散傅氏变换（FDFT）及其反变换；阐述循环褶积与普通褶积关系；介绍 FFT 原理与算法；讨论利用 FFT 实现频谱分析、褶积/相关计算；拓展至哈特利变换、余弦变换与广义中值函数。

§1 有限离散傅氏变换、有限离散频谱所引起的假信号

1. 有限离散信号及其频谱

有限离散信号：仅在有限区间 $[N_1, N_2]$ 内非零的离散信号 $x(n\Delta)$，记为

$$x(n\Delta) = [x(N_1\Delta),\, x((N_1+1)\Delta),\, \dots,\, x(N_2\Delta)]$$

其频谱为

$$X(f) = \sum_{n=N_1}^{N_2} x(n\Delta) e^{-i2\pi n\Delta f}$$

2. 有限离散傅氏变换

设长度为 $N$ 的有限离散信号：

$$x(n\Delta) = [x(0),\, x(\Delta),\, \dots,\, x((N-1)\Delta)]$$

取频点 $f_m = \frac{m}{N\Delta}$（$m = 0,1,\dots,N-1$），定义有限离散频谱：

$$X_m = X(f_m)= \sum_{n=0}^{N-1} x(n\Delta) e^{-imn \frac{2\pi}{N}},\quad m = 0,1,\dots,N-1$$

反变换：

$$x_n = \frac{1}{N} \sum_{m=0}^{N-1} X_m e^{imn \frac{2\pi}{N}}, \quad n = 0,1,\dots,N-1$$

上两式合称为有限离散傅氏变换（FDFT）与反变换（IFDFT）。

3. 实信号的有限离散傅氏变换性质

若 $x_n(n = 0,1,\dots,N-1)$ 为实信号，其 FDFT 满足共轭对称性：

$$X_{N-m} = \overline{X}_m$$

反之，若 $X_m$ 满足该对称性，则 $x_n$ 为实信号。

4. 有限离散频谱所引起的假信号问题

有限离散频谱定理 1

设离散信号 $x(n\Delta)(-\infty<n<+\infty)$ 及其频谱 $X(f)$，有限离散频谱 $X(f_m)$，由 $X(f_m)$ 经 IFDFT 所得有限信号为 $x_d(n\Delta)$，则

$$x_d(n\Delta) = \sum_{k=-\infty}^{\infty} x[(n + kN)\Delta], \quad 0 \le n \le N-1$$

该现象称为折叠效应，$N$ 为折叠周期，$x_d(n\Delta)$ 中超出原信号范围的成分称为假信号。

有限离散频谱定理 2

$$X_d(f) = \sum_{n=0}^{N-1} x_d(n\Delta) e^{-i2\pi n\Delta f}$$

在上述条件下，有误差估计：

$$\bigg|x_d(n\Delta) - x(n\Delta)\bigg| \le \sum_{\substack{k=-\infty \\ k\ne 0}}^{\infty} \bigg|x[(n + kN)\Delta]\bigg|$$

$$\sum_{n=0}^{N-1} \bigg|x_d(n\Delta) - x(n\Delta)\bigg| \le \sum_{l=-\infty}^{-1} \bigg|x(l\Delta)\bigg| + \sum_{l=N}^{+\infty} \bigg|x(l\Delta)\bigg|$$

$$\bigg|X_d(f) - X(f)\bigg| \le 2 \sum_{l=-\infty}^{-1} \bigg|x(l\Delta)\bigg| + 2 \sum_{l=N}^{+\infty} \bigg|x(l\Delta)\bigg|$$

§2 快速傅氏变换

1. 时域分解 FFT 算法

设 $N = 2^k$，将序列按下标奇偶分为两组：

$$\begin{cases} g_l = x_{2l} \\\\ h_l = x_{2l+1} \end{cases} \quad l = 0,1,\dots,N/2 -1$$

则 FDFT 可递推计算：

$$\begin{cases} X_m = G_m + W_N^m H_m \\\\ X_{m+N/2} = G_m - W_N^m H_m \end{cases} \quad 0 \le m < N/2$$

其中 $W_N = e^{-i2\pi / N}$ 。

2. 频域分解 FFT 算法

将频谱 $X_m$ 按奇偶分解，信号按如下组合：

$$\begin{cases} g_n = x_n + x_{n+N/2} \\\\ h_n = (x_n - x_{n+N/2}) W_N^n \end{cases} \quad n = 0,1,\dots,N/2 -1$$

则 FDFT 可递推计算：

$$\begin{cases} X_{2l}=\sum_{n=0}^{N/2-1}g_nW_{N/2}^{nl} \\\\ X_{2l+1}=\sum_{n=0}^{N/2-1}h_nW_{N/2}^{nl} \end{cases} \quad l = 0,1,\dots,N/2 -1$$

其中 $W_N = e^{-i2\pi / N}$ 。

§3 有限离散傅氏变换的循环褶积

1. 有限离散傅氏变换的循环褶积

设 $x_n, y_n$ 是长度为 $N$ 的离散信号，其 FDFT 为 $X_m, Y_m$。定义循环褶积为

$$z_n^{(N)} = x_n * y_n [N] = \sum_{l=0}^{N-1} x_l y_{(n-l) \bmod N}$$

Note

$z_n^{(N)}$ 是以 $N$ 为周期的周期函数。

则

$$Z_m = X_m Y_m \quad \overset{\text{FDFT}}{\longleftrightarrow}\quad z_n^{(N)} = x_n * y_n [N]$$

2. 循环褶积与普通褶积的关系

设 $x_n, y_n$ 是长度分别为 $M,L$ 的离散信号

$$x_n = \begin{cases} x_n, & 0 \le n \le M-1 \\ 0, & \text{其他} \end{cases}\quad y_n = \begin{cases} y_n, & 0 \le n \le L-1 \\ 0, & \text{其他} \end{cases}$$

记循环褶积为 $z_n^{(N)}$，普通褶积为 $z_n = x_n * y_n$，那么当 $0 \le n \le N-1$ 且 $n \ge M + L - 1 - N$ 时

$$z_n = z_n^{(N)}$$

特别地，若 $N \ge M + L -1$，则对 $0 \le n \le N-1$，均有 $z_n=z_n^{(N)}$。

3. 利用快速傅氏变换计算褶积

3.1 一般方法

设离散信号

$$x_n = \begin{cases} x_n, & 0 \le n \le M-1 \\ 0, & \text{其他} \end{cases} \qquad y_n = \begin{cases} y_n, & 0 \le n \le L-1 \\ 0, & \text{其他} \end{cases}$$

现需计算褶积

$$z_n = x_n * y_n$$

1. 选 $N = 2^p \ge M + L -1$
2. 构造补零序列 $x_n^{(N)}, y_n^{(N)}$
3. 用 FFT 计算 $X_m, Y_m$
4. 计算 $Z_m = X_m Y_m$
5. IFFT 得 $z_n^{(N)}$，$z_n=z_n^{(N)}$

3.2 分段求和法

当 $M$ 较大时，若按前述选 $N \ge M+L-1$，则 $N \approx M$ 过大，内存和硬件受限，此时可采用分段求和法。

1. 取 $N = 2^{k} \ge 2L$

2. 定义 $M_0 = N-L+1$

3. 定义长度为 $N$ 的序列 $\tilde{y}_n=(y_0,y_1,\dots,y_{L-1},0,\dots,0)$ ，用 FFT 计算 $\tilde{y}_n$ 的离散频谱 $\tilde{Y}_m$

4. 计算 $[0,M_0-1]$ 范围内的褶积 $z_n$ ：

   1. 取长度为 $N$ 的序列 $\tilde{x}_n^{(1)}=(0,\dots,0,x_0,\dots,x_{M_0-1})$

   2. 用 FFT 计算 $\tilde{x}_n^{(1)}$ 的离散频谱 $\tilde{X}_m^{(1)}$

   3. 计算 $\tilde{Z}_m^{(1)}=\tilde{X}_m^{(1)} \cdot \tilde{Y}_m$

   4. 用 IFFT 计算 $\tilde{z}_n^{(1)}$，有 $z_n=\tilde{z}_{L+n}^{(1)}, 0 \le n \le M_0-1$

      Note

      实际上 $\tilde{z}_n^{(1)}$ 是一个长度为 $L$ 的信号与一个长度为 $N$ 的信号的循环褶积，因此只有 $L-1 \le n \le N-1$ 时等于普通褶积。

5. 计算 $[M_0,2M_0-1]$ 范围内的褶积 $z_n$ ：

   1. 取长度为 $N$ 的序列 $\tilde{x}_n^{(2)}=(x_{M_0-L+1},\dots,x_{M_0},\dots,x_{2M_0-1})$

   2. 用 FFT 计算 $\tilde{x}_n^{(2)}$ 的离散频谱 $\tilde{X}_m^{(2)}$

   3. 计算 $\tilde{Z}_m^{(2)}=\tilde{X}_m^{(2)} \cdot \tilde{Y}_m$

   4. 用 IFFT 计算 $\tilde{z}_n^{(2)}$，有 $z_{M_0+n}=\tilde{z}_{L+n}^{(2)}, 0 \le n \le M_0-1$

6. 仿照 5 计算 $[2M_0,3M_0-1]$ 等范围内的褶积 $z_n$，直到 $[(J-1)M_0,JM_0-1]$ 结束，要求

   $$(J-1)M_0 < M+L-1 \le JM_0-1$$

   ​ 因此

   $$J = \left[\frac{M+L}{M_0}+\frac{1}{2}\right]$$

§4 应用快速傅氏变换进行频谱分析

1. 频谱分析步骤

1. 数据准备：取长度为 $N = 2^k$ 的离散信号。

2. FFT 计算频谱：

   $$X_m = \sum_{n=0}^{N-1} x_n e^{-i2\pi mn / N},\quad 0 \le m \le N-1$$

   当 $m=0,1,2,\dots,N/2$ 时，$X_m$ 表示频率为 $m/(N\Delta)$ 的频谱值。

   $$X_m = U_m+iV_m,\quad m=0,1,2,\dots,N/2$$

3. 求振幅谱、相位谱、功率谱：

   $$\begin{cases} A_m = |X_m| \\ \phi_m = \arctan \frac{V_m}{U_m} \\ G_m = |X_m|^2 \end{cases} \quad m=0,1,2,\dots,N/2$$

4. 平滑处理（可选）

5. 求特征频率：

   • 最大值频率点 $f_M = \frac{m_M}{N\Delta}$，其中 $m_M = \arg\max A_m$
   • 中间值频率点 $f_v = \frac{m_v}{N\Delta}$，其中 $m_v$ 满足 $\sum_{m=0}^{m_v} A_m \approx \frac{1}{2} \sum_{m=0}^{N/2} A_m$

2. 频谱分析中参数选取

对截频为 $f_c$，频率分辨间隔为 $f_\delta$ 的信号：

• 抽样间隔：$\Delta < \frac{1}{2f_c}$
• 记录长度：$N\Delta > \frac{1}{f_\delta}$
• 最小记录长度：$T_{min}=\frac{1}{f_\delta}$
• 抽样点数：$N > \frac{2f_c}{f_\delta}$

§5 有限离散哈特利变换、余弦变换和广义中值函数

1. 有限离散哈特利变换（FDHT）

1.1 函数 $\operatorname{cas}\alpha$

$$\operatorname{cas}\alpha = \cos\alpha + \sin\alpha$$

1.2 有限离散哈特利变换

设离散信号 $x_n$（$n = 0,1,\dots,N-1$）：

$$HX_m = \sum_{n=0}^{N-1} x_n \operatorname{cas}\left(\frac{2\pi mn}{N}\right),\quad m = 0,1,\dots,N-1$$

$$x_n = \frac{1}{N} \sum_{m=0}^{N-1} HX_m \operatorname{cas}\left(\frac{2\pi mn}{N}\right)$$

2. 有限离散余弦变换（FDCT）

2.1 Ⅰ型 FDCT

设离散信号 $x_n$（$n = 0,1,\dots,N-1$）：

$$X_m = \sum_{n=0}^{N} k_n x_n \cos\left(\frac{\pi mn}{N}\right)$$

$$x_n = \sum_{m=0}^{N} k_m X_m \cos\left(\frac{\pi mn}{N}\right)$$

其中 $k_0 = k_N = \frac{1}{\sqrt{2}}$，其余 $k_n = 1$。

2.2 Ⅱ型 FDCT

设离散信号 $x_n$（$n = 0,1,\dots,N-1$）：

$$X_m = \sum_{n=0}^{N-1} \beta_n x_n \cos\left[\frac{\pi (n+1/2)m}{N}\right]$$

$$x_n = \sum_{m=0}^{N-1} \beta_m X_m \cos\left[\frac{\pi (n+1/2)m}{N}\right]$$

其中 $\beta_0 = \frac{1}{\sqrt{2}}$，其余 $\beta_n = 1$。

3. 广义中值函数

3.1 定义

函数 $g(\lambda)$ 称为广义中值函数，若存在 $p(\beta)$ 使

$$g[(2k+1)\beta] = \frac{g[(2k+2)\beta] + g(2k\beta)}{p(\beta)},\quad \forall k \in \Z,\beta \in \R$$

典型例子：$\cos\lambda, \sin\lambda, \operatorname{cas}\lambda, e^{i\lambda}$ 均为广义中值函数，对应 $p(\beta) = 2\cos\beta$。

3.2 性质

设 $g(\lambda)$ 为广义中值函数，$x_n$（$n = 0,1,\dots,N-1$）为离散信号：

• 性质1：

  $$\sum_{n=0}^{N-1} x_n g\left[(n + \tfrac{1}{2})\beta\right] = \frac{1}{p(\beta/2)} \left\{ \sum_{n=0}^{N-1} (x_n + x_{n-1}) g(n\beta) + x_{N-1}[g(N\beta) - g(0)] \right\}$$

  其中 $x_{-1} = x_{N-1}$。

• 性质2（$N$ 为正偶数）：

  $$\sum_{n=0}^{N-1} x_n g(n\beta) = \sum_{n=0}^{N/2-1} x_{2n} g(2n\beta) + \frac{1}{p(\beta)} \left\{ \sum_{n=0}^{N/2-1} (x_{2n+1} + x_{2n-1}) g(2n\beta) + x_{N-1}[g(N\beta) - g(0)] \right\}$$

  其中 $x_{-1} = x_{N-1}$。

  Note

  将 $N$ 变换转化为两个 $N/2$ 变换，构成快速算法理论的基础。

3.3 余弦变换的快速算法

考虑一种有限离散余弦变换

$$X_m = \sum_{n=0}^{N-1} x_n \cos n(m+\frac{1}{2})\pi/N,\quad m=0,1,\dots,N-1$$

利用广义中值函数性质可得递推：

$$\begin{cases} X_m = A_m + \left[2\cos\left(\frac{\pi(m+1/2)}{N}\right)\right]^{-1}B_m \\\\ X_{N-m-1} = A_m - \left[2\cos\left(\frac{\pi(m+1/2)}{N}\right)\right]^{-1}B_m \end{cases} \quad 0 \le m \le \frac{N}{2}-1$$

其中

$$\begin{cases} A_m=\sum_{n=0}^{N/2-1}x_{2n} \cos n(m+\frac{1}{2})\frac{\pi}{N/2}\\\\ B_m=\sum_{n=0}^{N/2-1}(x_{2n+1}+x_{2n-1}) \cos n(m+\frac{1}{2})\frac{\pi}{N/2} \end{cases} \quad 0 \le m \le \frac{N}{2}-1$$

Copyright

Copyright Ownership:Staaaaaaaaar

License under:Attribution-NonCommercial-ShareAlike 4.0 International (CC-BY-NC-SA-4.0)

Edit this page

Contributors: Staaaaaaaaar

Previous page第六章：希尔伯特变换与实信号的复数表示

Next page第八章：相关分析