取 $N = 2^{k} \ge 2L$
定义 $M_0 = N-L+1$
定义长度为 $N$ 的序列 $\tilde{y}_n=(y_0,y_1,\dots,y_{L-1},0,\dots,0)$ ，用 FFT 计算 $\tilde{y}_n$ 的离散频谱 $\tilde{Y}_m$
计算 $[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$
  注
  实际上 $\tilde{z}_n^{(1)}$ 是一个长度为 $L$ 的信号与一个长度为 $N$ 的信号的循环褶积，因此只有 $L-1 \le n \le N-1$ 时等于普通褶积。
计算 $[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$
仿照 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 应用快速傅氏变换进行频谱分析

数据准备：取长度为 $N = 2^k$ 的离散信号。
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$
求振幅谱、相位谱、功率谱：
$\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$
平滑处理（可选）
求特征频率：
- 最大值频率点 $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$

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

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

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

设离散信号 $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)

设离散信号 $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$ 。

设离散信号 $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$ 。

函数 $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$ 。

设 $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}$ 。
注
将 $N$ 变换转化为两个 $N/2$ 变换，构成快速算法理论的基础。

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

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

版权归属：Staaaaaaaaar