$k$ 进制 FWT 小记

上文：FWT 快速沃尔什变换

概念

\(k\) 进制的 DWT 本质上是二进制操作的一个扩展操作。

原来的位运算也推广到了 \(k\) 进制上。

\(\text{or}\) 卷积

定义

两个数 \(x_{1...k},y_{1...k}\) 的 \(k\) 进制或运算定义为：\(z_i=\max(x_i,y_i)\)。

换言之，在每个维度上取 \(\max\)。

分析

上文中，我们提到了 FWT 的本质，变换矩阵需要满足 \(w(i,j)w(i,k)=w(i,j\oplus k)\)。

对于或卷积，考虑构造一个矩阵满足 \(w(i,j)w(i,k)=w(i,j\text{or} k)\)。