仓库源文，站点原文

title: "随笔 - 略谈 Walsh 变换" date: 2022-08-08 08:08:08 categories:

随笔
数学 tags:
随笔
数学
代数
Walsh变换

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

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$ 的构造方法如下:

令 $$ W_2=\begin{bmatrix} 1&1\ 1&-1 \end{bmatrix} $$
假设我们已经构造出来了 $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 变换有如下性质

$$ W_NW_N^T=N $$

即 $N^{-{1\over 2}}W_N$ 是正交矩阵
$W_N$ 的偶数列偶对称, 奇数列奇对称 (从 $0$ 到 $N-1$)
$$ \text{WT}(af+bg)=a\text{WT}(f)+b\text{WT}(g) $$

其中 $a,b$ 为常数
$$ W_N[l,m]W_N[n,m]=W_N[l\oplus n,m] $$

其中 $\oplus$ 表示异或
$$ f(n\oplus k)=W_N(k,m)\text{WT}(f)(m) $$
$$ W_N(k,n)f(n)=\text{WT}(f)(m\oplus k) $$
$$ \sum{n=0}^{N-1}f^2(n)={1\over N}\sum{m=0}^{N-1}F^2(m) $$
$$ \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) 的算法