随笔 - 略谈 Walsh 变换

发表于 更新于 分类于 ， 本文字数： 817 阅读时长 ≈ 3 分钟

极度简略的科普文，看看就好

Walsh 变换是离散 Fourier 变换的一种替代方案

我们知道离散 Fourier 变换的运算过程需要进行大量浮点复数的运算，导致其不仅效率较低，还存在较高的精度误差。而 Walsh 变换只需要进行整数加法进行运算，这使得其运算复杂度更优

离散 Fourier 变换是把信号拆解成在不同频率的正弦函数与余弦函数的分量，而 Walsh 变换则是把信号拆解成在许多不同震荡频率的方波上，因此，除非所要分析的信号拥有类似方波组合的特性，使用 Walsh 变换作频谱分析的效果会比使用离散 Fourier 变换分析的效果要差

设函数 \(f(n)\) 的定义域为 \(\{0,1,...,N-1\}\), 且 \(N=2^k,k\in\mathbb{N}^+\) 则我们定义 Walsh 变换与 Walsh 逆变换如下

  • Walsh 变换

    \[ \text{WT}(f):=F(m)=\sum_{n=0}^{N-1}f(n)W_N(m,n) \]

  • Walsh 逆变换

    \[ \text{IWT}(F):=F(n)={1\over N}\sum_{m=0}^{N-1}f(m)W_N(n,m) \]

其中 \(W_N\) 为 \(N\) 阶 Walsh 矩阵，\(W_N(m,n)\) 为其第 \(m\) 行第 \(n\) 列，\(W_N\) 的构造方法如下:

  1. 令 \[ W_2=\begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix} \]
  2. 假设我们已经构造出来了 \(W_{2^k}\), 令 \[ \overline{W}_{2^{k+1}}=\begin{bmatrix} W_{2^k}&W_{2^k}\\ W_{2^k}&-W_{2^k} \end{bmatrix} \]

接下来我们只需要对其各行进行重排序即可得到 \(W_{2^{k+1}}\), 排序方式为以各行 \(-1\) 的个数和行坐标进行排列 (Walsh 顺序)

例如

\[ \overline{W}_{4}\begin{bmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{bmatrix}\implies W_{4}\begin{bmatrix} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1 \end{bmatrix} \]

\[ \overline{W}_{8}\begin{bmatrix} 1&1&1&1&1&1&1&1\\ 1&-1&1&-1&1&-1&1&-1\\ 1&1&-1&-1&1&1&-1&-1\\ 1&-1&-1&1&1&-1&-1&1\\ 1&1&1&1&-1&-1&-1&-1\\ 1&-1&1&-1&-1&1&-1&1\\ 1&1&-1&-1&-1&-1&1&1\\ 1&-1&-1&1&-1&1&1&-1 \end{bmatrix}\implies W_{8}\begin{bmatrix} 1&1&1&1&1&1&1&1\\ 1&1&1&1&-1&-1&-1&-1\\ 1&1&-1&-1&-1&-1&1&1\\ 1&1&-1&-1&1&1&-1&-1\\ 1&-1&-1&1&1&-1&-1&1\\ 1&-1&-1&1&-1&1&1&-1\\ 1&-1&1&-1&-1&1&-1&1\\ 1&-1&1&-1&1&-1&1&-1 \end{bmatrix} \]

Walsh 矩阵与 Walsh 变换有如下性质

  1. \[ W_NW_N^T=N \]

    即 \(N^{-{1\over 2}}W_N\) 是正交矩阵

  2. \(W_N\) 的偶数列偶对称，奇数列奇对称 (从 \(0\) 到 \(N-1\))

  3. \[ \text{WT}(af+bg)=a\text{WT}(f)+b\text{WT}(g) \]

    其中 \(a,b\) 为常数

  4. \[ W_N[l,m]W_N[n,m]=W_N[l\oplus n,m] \]

    其中 \(\oplus\) 表示异或

  5. \[ f(n\oplus k)=W_N(k,m)\text{WT}(f)(m) \]

  6. \[ W_N(k,n)f(n)=\text{WT}(f)(m\oplus k) \]

  7. \[ \sum_{n=0}^{N-1}f^2(n)={1\over N}\sum_{m=0}^{N-1}F^2(m) \]

  8. \[ \text{WT}\left(\sum_{l=0}^{N-1}f(l)g(n\otimes_k l)\right)=\text{WT}(f)\text{WT}(g) \]

    其中 \(\otimes_k\) 为 \(k\) 位按位卷积

可以发现，在这些性质的保证下，Walsh 变换可以按使用离散 Fourier 变换的方式去使用，同样的，我们也可以按 FFT 的做法得到 快速 Walsh 变换 (FWT) 的算法