xor畳み込み
長さ $2^K$ の数列 $X$, $Y$ があるとき， これらのxor畳み込みを，以下を満たす長さ $2^K$ の列 $Z$ として定める． ただし，$x \oplus y$ は $x$ と $y$ の xor とする．
- $ Z_k = \sum \{ X_i Y_j \mid i \oplus j = k \} $
以下では，$Z = X * Y$ と書く．
アダマール変換
長さ $2^K$ の数列に作用するアダマール変換は，以下の行列 $H_K$ で定義される 1次変換である．
$$ H_0 = 1 $$
$$ H_{k + 1} = \begin{bmatrix} H_k & H_k \\ H_k & -H_k \end{bmatrix} $$
本来は，正規化のために定数倍するが， ここでは，結果を整数にするためにそうしていない．
$ H_k H_k = 2^k I $ が成り立つので，$(H_k)^{-1} = 2^{-k} H_k$ である．
畳み込みとアダマール変換
以下が成り立つことが，計算することで容易に分かる．
$$ (H_K X) (H_K Y) = H_K (X * Y) $$
ただし，左辺は，成分ごとの積．したがって，xor 畳み込みは，下のように計算できる．
$$ X * Y = 2^{-K} H_K ((H_K X) (H_K Y)) $$
アダマール変換は，定義に従って $O(n \log n)$ で計算できる．($n = 2^K$)
メモリを賢く使って計算している例が kazuma8128's blog に載っている．