快速沃尔什变换

引入

沃尔什变换的数学定义

沃尔什转换矩阵

沃尔什转换矩阵为一个方阵，其阶数为 $2$ 的幂。$2^k$ 的沃尔什矩阵可用迭代方式产生。
起始点 $k=1$，定义 $2^1$ 阶沃尔什转换矩阵 $W_2=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$。假设已经有 $2^k$ 阶沃尔什转换矩阵 $W_{2^k}$，定义 $V_{2^{k+1}}=\begin{pmatrix}W_{2^k}&W_{2^k}\\W_{2^k}&-W_{2^k}\end{pmatrix}$，再将 $V_{2^{k+1}}$ 的列重新排列得到 $W_{2^{k+1}}$。
在不同的应用领域，对 $V_{2^{k+1}}$ 列的排序时，要按照不同的顺序排序。

Walsh Ordering	Paley Ordering	Hadamard Ordering
常用于信号处理	较常用于控制工程	较常用于数学

正变换与逆变换

沃尔什变换的转换式为 $F_i=\sum\limits_{j=0}^{n-1}f_jW_{ij}$。$W_{ij}$ 是沃尔什变换矩阵的第 $i$ 行第 $j$ 列的元素。其逆变换为 $f_i=\frac{1}{n}\sum\limits_{j=0}^{n-1}F_jW_{ij}$。

沃尔什变换的在通信中的应用

沃尔什变换是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。
在频谱分析上最常用的一种方法是使用傅立叶变换。然而，即使已经有 $\text{FFT}$ 来实现傅立叶变换，仍然具有一些实现上的缺点。
在傅立叶变换中，向量必须乘上复数矩阵加以处理，且复数的实部和虚部大多数情况下都为浮点数，因此计算量和误差会比较大。
在沃尔什变换中，向量需要乘上的矩阵是一个整数的矩阵，而且这些矩阵的元素只可能是 $1$ 或 $–1$，这使得我们不需要作浮点数的乘法运算。更进一步，只需要使用加法来实现沃尔什变换，这使的沃尔什变换在运算复杂度上远小于傅立叶变换。
使用傅立叶变换相当于把信号拆解成在不同频率的正弦函数与余弦函数的分量，而使用沃尔什转换相当于把信号拆解成在许多不同震荡频率的方波上。因此，除非所要分析的信号拥有类似方波组合的特性，使用沃尔什变换作频谱分析的效果会比使用离散傅立叶变换分析的效果要差，这是降低运算复杂度所要付出的代价。
$\text{CDMA}$ 就应用了沃尔什变化做多工。

沃尔什变换在信息学竞赛中的应用

在信息学竞赛中，沃尔什变换用于解决对下标进行位运算卷积的问题。快速沃尔什变换，简称 $\mathrm{FWT}$，能够在 $O(n\log n)$ 的时间内完成沃尔什变换及其逆变换。

一些约定

• $\wedge$ 为与运算符，$\vee$ 为或运算符，$\oplus$ 为异或运算符。
• 一般用大写字母 $A$ 表示一个多项式，$n$ 为多项式的长度。
• 对于所有讨论的多项式，其长度 $n$ 都为 $2$ 的幂次。
• 设 $A$ 为长度为 $n$ 的 $n-1$ 次多项式，其系数表达式为 $(a_0,a_1,\cdots,a_{n-1})$。定义 $A_0$ 为 $A$ 的前 $\frac{n}{2}$ 项，$A_1$ 为 $A$ 的后 $\frac{n}{2}$ 项。
• $A+B$ 表示将多项式 $A,B$ 对应的系数相加，即 $c_i=a_i+b_i$。
• $A-B$ 表示将多项式 $A,B$ 对应的系数相减，即 $c_i=a_i-b_i$。
• $A\times B$ 表示将多项式 $A,B$ 对应的系数相乘，即 $c_i=a_ib_i$。
• $\text{FWT}(A)$ 表示将多项式 $A$ 进行快速沃尔什变换，其结果为一个长度与 $A$ 相同的多项式。
• $\text{IFWT}(A)$ 表示将多项式 $A$ 进行逆快速沃尔什变换，显然有 $\text{IFWT}(\text{FWT}(A))=A$。
• $[A,B]$ 表示多项式的拼接。$A$ 的系数表达式为 $(a_0,a_1,\cdots,a_{n_1})$，$B$ 的系数表达式为 $(b_0,b_1,\cdots,b_{n_2})$，那么 $[A,B]$ 的系数表达式为 $(a_0,\cdots,a_{n_1},b_0,\cdots,b_{n_2})$。
• $C=A\wedge B$ 表示对下标进行与运算卷积，$c_i=\sum\limits_{j\wedge k=i}a_jb_k$。
• $C=A\vee B$ 表示对下标进行或运算卷积，$c_i=\sum\limits_{j\vee k=i}a_jb_k$。
• $C=A\oplus B$ 表示对下标进行异或运算卷积，$c_i=\sum\limits_{j\oplus k=i}a_jb_k$。

引理

引理 1 $[A+B,C+D]=[A,C]+[B,D]$。
略证 将多项式用系数表达式表示得证。
引理 2 $[A\times B,C\times D]=[A,C]\times[B,D]$。
略证 将多项式用系数表达式表示得证。
**引理 3 ** $(A+B)_0=A_0+B_0$，$(A+B)_1=A_1+B_1$。
略证 将多项式化为系数表达式得证。
引理 4 $[(A\wedge B)_0,(A\wedge B)_1]=[A_0\wedge B_0+A_0\wedge B_1+A_1\wedge B_0,A_1\wedge B_1]$。
略证 $A_0$ 的各个下标范围是 $0\sim \frac{n}{2}-1$，而 $A_1$ 的下标范围是 $\frac{n}{2}\sim n-1$，$A_1$ 中下标的最高位是 $1$，而 $A_0$ 中下标的最高位为 $0$。因此卷积结果的前半部分为三项之和：$A_0\wedge B_0+A_0\wedge B_1+A_1\wedge B_0$，每一项的下标范围都在 $0\sim \frac{n}{2}-1$。后半部分为 $A_1\wedge B_1$，下标范围在 $\frac{n}{2}\sim n-1$ 之间。
引理 5 $[(A\vee B)_0,(A\vee B)_1]=[A_0\vee B_0,A_1\vee B_0+A_0\vee B_1+A_1\vee B_1]$。
略证 $A_0$ 的各个下标范围是 $0\sim \frac{n}{2}-1$，而 $A_1$ 的下标范围是 $\frac{n}{2}\sim n-1$，$A_1$ 中下标的最高位是 $1$，而 $A_0$ 中下标的最高位为 $0$。因此卷积结果的前半部分为 $A_0\vee B_0$，下标范围在 $0\sim\frac{n}{2}-1$ 之间。后半部分为三项之和：$A_0\vee B_0+A_0\vee B_1+A_1\vee B_0$，每一项的下标范围都在 $\frac{n}{2}\sim n-1$ 之间。
引理 6 $[(A\oplus B)_0,(A\oplus B)_1]=[A_0\oplus B_0+A_1\oplus B_1,A_1\oplus B_0+A_0\oplus B_1]$。
证明 $A_0$ 的各个下标范围是 $0\sim \frac{n}{2}-1$，而 $A_1$ 的下标范围是 $\frac{n}{2}\sim n-1$，$A_1$ 中下标的最高位是 $1$，而 $A_0$ 中下标的最高位为 $0$。因此卷积结果的前半部分为 $A_0\oplus B_0$ 与 $A_1\oplus B_1$ 之和，两项的下标范围均在 $0\sim\frac{n}{2}-1$ 之间。后半部分为 $A_0\oplus B_1$ 与 $A_1\oplus B_0$ 之和，两项的下标范围都在 $\frac{n}{2}\sim n-1$ 之间。

三种卷积

基于以上的约定，对于两个长度为 $n$ 的 $n-1$ 次多项式 $A,B$，$\text{FWT}$ 可以解决三种对下标进行位运算卷积的问题：$A\wedge B$，$A\vee B$，$A\oplus B$。
类似 $\text{FFT}$，我们需要定义 $\text{FWT}$，先正向得到 $\text{FWT}(A)$ 和 $\text{FWT}(B)$，然后能够在线性的时间内得到 $\text{FWT}(C)$，最后进行逆变换即可得到 $C$。
接下来依次介绍求解三种卷积的方法，对于不同的卷积，$\text{FWT}$ 的定义形式也有些许不同。

与卷积 $C=A\wedge B$

定义

定义 $\text{FWT}(A)=\begin{cases}A&n=1\\\left[\text{FWT}(A_0+A_1),\text{FWT}(A_1)\right]&n>1\end{cases}$。
同时不加证明地给出逆变换 $\mathrm{IFWT}(A)=\begin{cases}A&n=1\\\left[\mathrm{IFWT}(A_0-A_1),\mathrm{IFWT}(A_1)\right]&n>1\end{cases}$。

定理

定理 1.1 $\mathrm{FWT}(A+B)=\mathrm{FWT}(A)+\mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}(A+B)=A+B=\mathrm{FWT}(A)+\mathrm{FWT}(B)$，显然成立。
假设当 $n=\frac{k}{2}$ 时等式成立，其中 $k$ 为 $2$ 的正整数幂。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A+B)\\&=[ \mathrm{FWT}((A+B)_0+(A+B)_1),\mathrm{FWT}((A+B)_1)]\\&=[\mathrm{FWT}(A_0+A_1+B_0+B_1),\mathrm{FWT}(A_1+B_1)]\\&=[\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1)+\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1),\mathrm{FWT}(A_1)+\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1),\mathrm{FWT(A_1)}]+[\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1),\mathrm{FWT}(B_1)]\\&=\mathrm{FWT}(A)+\mathrm{FWT}(B)\end{aligned}$
证毕。
定理 1.2 $\mathrm{FWT}(A\wedge B)=\mathrm{FWT}(A)\times\mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}{A\wedge B}=A\times B=\mathrm{FWT}(A)\times \mathrm{FWT}(B)$，等式成立。
假设当 $n=\frac{k}{2}$ 时等式成立，其中 $k$ 为 $2$ 的正整数次幂。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A\wedge B)\\&=\mathrm{FWT}([(A\wedge B)_0,(A\wedge B)_1])\\&=\mathrm{FWT}([A_0\wedge B_0+A_1\wedge B_0+A_0\wedge B_1,A_1\wedge B_1])\\&=[\mathrm{FWT}(A_0\wedge B_0+A_1\wedge B_0+A_0\wedge B_1+A_1\wedge B_1),\mathrm{FWT}(A_1\wedge B_1)]\\&=[\mathrm{FWT}(A_0\wedge B_0)+\mathrm{FWT}(A_1\wedge B_0)+\mathrm{FWT}(A_0\wedge B_1)+\mathrm{FWT}(A_1\wedge B_1),\mathrm{FWT}(A_1\wedge B_1)]\\&=[\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0)+\mathrm{FWT}(A_1)\times \mathrm{FWT}(B_0)+\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_1)\\&\ \quad+\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1),\mathrm{FWT}(A_1)\times \mathrm{FWT}(B_1)]\\&=[(\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1))\times(\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1)),\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0+A_1)\times\mathrm{FWT}(B_0+B_1),\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0+A_1),\mathrm{FWT}(A_1)]\times[\mathrm{FWT}(B_0+B_1),\mathrm{FWT}(B_1)]\end{aligned}$
证毕。

代码

基于定理1.2，$C=\mathrm{IFWT}(\mathrm{FWT}(A\wedge B))=\mathrm{IFWT}(\mathrm{FWT}(A)\times\mathrm{FWT}(B))$。
正变换：$\text{FWT}(A)=[\text{FWT}(A_0+A_1),\text{FWT}(A_1)]$。
逆变换：$\mathrm{IFWT}(A)=[\mathrm{IFWT}(A_0-A_1),\mathrm{IFWT}(A_1)]$。
可用分治法解决。

void FWT_AND(ll *x,short opt){
	for(register int i=1;i<n;i<<=1){
		int step=i<<1;
		for(register int j=0;j<n;j+=step){
			for(register int k=0;k<i;k++){
				x[j+k]+=x[j+k+i]*opt;
				x[j+k]=(x[j+k]%mod+mod)%mod;
			}
		}
	}
}

或卷积 $C=A\vee B$

定义

定义 $\mathrm{FWT}(A)=\begin{cases}A&n=1\\\left[\mathrm{FWT}(A_0),\mathrm{FWT}(A_0+A_1)\right]&n>1\end{cases}$。
同时不加证明地给出逆变换 $\mathrm{IFWT}(A)=\begin{cases}A&n=1\\\left[\mathrm{IFWT}(A_0),\mathrm{IFWT}(A_1-A_0)\right]&n>1\end{cases}$。

定理

定理 2.1 $\mathrm{FWT}(A+B)=\mathrm{FWT}(A)+\mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}(A+B)=A+B=\mathrm{FWT}(A)+\mathrm{FWT}(B)$，等式成立。
假设当 $n=\frac{k}{2}$ 时，等式成立。其中，$k$ 为 $2$ 的正整数幂。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A+B)\\&=[\mathrm{FWT}(A_0+B_0),\mathrm{FWT}(A_0+B_0+A_1+B_1)]\\&=[\mathrm{FWT}(A_0)+\mathrm{FWT}(B_0),\mathrm{FWT}(A_0)+\mathrm{FWT}(B_0)+\mathrm{FWT}(A_1)+\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0),\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1)]+[\mathrm{FWT}(B_0),\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1)]\\&=\mathrm{FWT}(A)+\mathrm{FWT}(B)\end{aligned}$
证毕。
定理 2.2 $\mathrm{FWT}(A\vee B)=\mathrm{FWT}(A)\times \mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}(A\vee B)=A\times B=\mathrm{FWT}(A)\times\mathrm{FWT}(B)$，等式成立。
假设当 $n=\frac{k}{2}$ 时，等式成立。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A\vee B)\\&=\mathrm{FWT}([(A\vee B)_0,(A\vee B)_1])\\&=\mathrm{FWT}([A_0\vee B_0,A_0\vee B_1+A_1\vee B_0+A_1\vee B_1])\\&=[\mathrm{FWT}(A_0\vee B_0),\mathrm{FWT}(A_0\vee B_0+A_0\vee B_1+A_1\vee B_0+A_1\vee B_1)]\\&=[\mathrm{FWT}(A_0\vee B_0),\mathrm{FWT}(A_0\vee B_0)+\mathrm{FWT}(A_0\vee B_1)+\mathrm{FWT}(A_1\vee B_0)+\mathrm{FWT}(A_1\vee B_1)]\\&=[\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0),\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0)+\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_1)\\&\quad\ +\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_0)+\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0),(\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1))\times(\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1))]\\&=[\mathrm{FWT}(A_0),\mathrm{FWT}(A_0+A_1)]\times[\mathrm{FWT}(B_0),\mathrm{FWT}(B_0+B_1)]\\&=\mathrm{FWT}(A)\times\mathrm{FWT}(B)\end{aligned}$

代码

基于定理 2.2，$C=\mathrm{IFWT}(\mathrm{FWT}(A\vee B))=\mathrm{IFWT}(\mathrm{FWT}(A)\times\mathrm{FWT}(B))$。
正变换：$\mathrm{FWT}(A)=[\mathrm{FWT}(A_0),\mathrm{FWT}(A_0+A_1)]$。
逆变换：$\mathrm{IFWT}(A)=[\mathrm{IFWT}(A_0),\mathrm{FWT}(A_1-A_0)]$。
可用分治法解决。

void FWT_OR(ll *x,short opt){
	for(register int i=1;i<n;i<<=1){
		int step=i<<1;
		for(register int j=0;j<n;j+=step){
			for(register int k=0;k<i;k++){
				x[j+k+i]+=x[j+k]*opt;
				x[j+k+i]=(x[j+k+i]%mod+mod)%mod;
			}
		}
	}
}

异或卷积 $C=A\oplus B$

定义

定义 $\mathrm{FWT}(A)=\begin{cases}A&n=1\\\left[\mathrm{FWT}(A_0+A_1),\mathrm{FWT}(A_0-A_1)\right]&n>1\end{cases}$。
同时不加证明地给出逆变换 $\mathrm{IFWT}(A)=\begin{cases}A&n=1\\\left[\frac{\mathrm{IFWT}(A_0+A_1)}{2},\frac{\mathrm{IFWT}(A_0-A_1)}{2}\right]&n>1\end{cases}$。

定理

定理 3.1 $\mathrm{FWT}(A+B)=\mathrm{FWT}(A)+\mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}(A+B)=A+B=\mathrm{FWT}(A)+\mathrm{FWT}(B)$，等式成立。
假设当 $n=\frac{k}{2}$ 时，等式成立。其中，$k$ 为 $2$ 的正整数幂。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A+B)\\&=[\mathrm{FWT}((A+B)_0+(A+B)_1),\mathrm{FWT}((A+B)_0-(A+B)_1)]\\&=[\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1)+\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1),\mathrm{FWT}(A_0)-\mathrm{FWT}(A_1)+\mathrm{FWT}(B_0)-\mathrm{FWT}(B_1)]\\&=[\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1),\mathrm{FWT}(A_0)-\mathrm{FWT}(A_1)]+[\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1),\mathrm{FWT}(B_0)-\mathrm{FWT}(B_1)]\\&=\mathrm{FWT}(A)+\mathrm{FWT}(B)\end{aligned}$
证毕。
定理 3.2 $\mathrm{FWT}(A\oplus B)=\mathrm{FWT}(A)\times\mathrm{FWT}(B)$。
证明 用数学归纳法证明。
当 $n=1$ 时，$\mathrm{FWT}(A\oplus B)=A\times B=\mathrm{FWT}(A)\times \mathrm{FWT}(B)$，等式成立。
假设当 $n=\frac{k}{2}$ 时等式成立。其中，$k$ 为 $2$ 的正整数幂。
当 $n=k$ 时，
$\begin{aligned}&\quad\ \mathrm{FWT}(A\oplus B)\\&=\mathrm{FWT}([(A\oplus B)_0,(A\oplus B)_1])\\&=\mathrm{FWT}([A_0\oplus B_0+A_1\oplus B_1,A_0\oplus B_1+A_1\oplus B_0])\\&=[\mathrm{FWT}(A_0\oplus B_0+A_1\oplus B_1+A_0\oplus B_1+A_1\oplus B_0+),\mathrm{FWT}(A_0\oplus B_0+A_1\oplus B_1-A_0\oplus B_1-A_1\oplus B_0)]\\&=[\mathrm{FWT}(A_0\oplus B_0)+\mathrm{FWT}(A_1\oplus B_1)+\mathrm{FWT}(A_0\oplus B_1)+\mathrm{FWT}(A_1\oplus B_0),\\&\ \quad\mathrm{FWT}(A_0\oplus B_0)+\mathrm{FWT}(A_1\oplus B_1)-\mathrm{FWT}(A_0\oplus B_1)-\mathrm{FWT}(A_1\oplus B_0)]\\&=[\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0)+\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1)+\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_1)+\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_0),\\&\ \quad\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_0)+\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_1)-\mathrm{FWT}(A_0)\times\mathrm{FWT}(B_1)-\mathrm{FWT}(A_1)\times\mathrm{FWT}(B_0)]\\&=[(\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1))\times(\mathrm{FWT}(B_0)+\mathrm{FWT}(B_1)),(\mathrm{FWT}(A_0)-\mathrm{FWT}(A_1))\times(\mathrm{FWT}(B_0)-\mathrm{FWT}(B_1))]\\&=[\mathrm{FWT}(A_0+A_1)\times\mathrm{FWT}(B_0+B_1),\mathrm{FWT}(A_0-A_1)\times\mathrm{FWT}(B_0-B_1)]\\&=[\mathrm{FWT}(A_0+A_1)-\mathrm{FWT}(A_0-A_1)]\times[\mathrm{FWT}(B_0+B_1)-\mathrm{FWT}(B_0-B_1)]\\&=\mathrm{FWT}(A)\times\mathrm{FWT}(B)\end{aligned}$
证毕。

代码

基于定理 3.2，$C=\mathrm{IFWT}(\mathrm{FWT}(A\oplus B))=\mathrm{IFWT}(\mathrm{FWT}(A)\times\mathrm{FWT}(B))$。
正变换：$\mathrm{FWT}(A)=[\mathrm{FWT}(A_0)+\mathrm{FWT}(A_1),\mathrm{FWT}(A_0)-\mathrm{FWT}(A_1)]$。
逆变换：$\mathrm{IFWT}(A)=\left[\frac{\mathrm{IFWT}(A_0)+\mathrm{IFWT}(A_1)}{2},\frac{\mathrm{IFWT}(A_0)-\mathrm{IFWT}(A_1)}{2}\right]$。
可用分治法解决。

void FWT_XOR(ll *x,short opt){
	for(register int i=1;i<n;i<<=1){
		int step=i<<1;
		for(register int j=0;j<n;j+=step){
			for(register int k=0;k<i;k++){
				const ll u=x[j+k],v=x[j+k+i];
				x[j+k]=u+v;
				x[j+k+i]=u-v;
				x[j+k]=(x[j+k]%mod+mod)%mod;
				x[j+k+i]=(x[j+k+i]%mod+mod)%mod;
				if(opt==-1){
					x[j+k]=x[j+k]*inv2%mod;
					x[j+k+i]=x[j+k+i]*inv2%mod;
				}
			}
		}
	}
}