Dyadic (XOR) Convolution theorem

The Dyadic (XOR) convolution of the sequences $a$ and $b$ is the sequence $c=a*b$ defined by

$c_k=\displaystyle\sum_{i\oplus j = k}a_ib_j=\sum_{i}a_ib_{i\oplus k}$

where the symbol $\oplus$ stands for bit-wise XOR operator. All the three sequences must of the same length that is a power of 2 (we could pad them with zeroes if they are not).

The Dyadic (XOR) convolution theorem states that for two sequences $a$ and $b$,

$c=a*b \implies H_mc=H_ma\cdot H_mb$

where $\cdot$ deontes pointwise multiplication and $H_m$ is the Hadamard matrix. We omit the normalization of the matrix throughout this post.

Though all these are available in Wikipedia and other webpages, nowhere was I able to find a proof of the Dyadic (XOR) convolution theorem. So that is the point of this post. Let's attack the theorem head-on.

Before we proceed to the proof of the convolution theorem, we notice a property of the Hadamard matrices. Indexing the rows and colomns of the Hadamard matrices from 0, we can directly have the $(i,j)$ of entry of the matrix using the following formula.

$(H_m)_{(i,j)}=(-1)^{n(i\&j)}$

where $n(k)$ counts the number of 1s in the binary expansion of the non-negative ineger $k$.This definition plays a crucial role in our proof. We now have all that we need to prove the Dyadic (XOR) convolution theorem. For simplicity, we drop the suffix in the Hadamard matrix, $H_m$. 

Proof of the Convolution Theorem Notice that the $k$th element of the vector $Ha$ is given by

$(Ha)_k=(-1)^{n(0\&k)}a_0+(-1)^{n(1\&k)}a_1+(-1)^{n(2\&k)}a_2+\cdots$

We get this by directly multiplying the $k$th row of the Hadamard matrix with the $a$ vector. Similar expression holds for $Hb$. Therefore, the $k$the entry of the pointwise product is

$\begin{align}
(Ha)_k\cdot(Hb)_k&=\displaystyle\left(\sum_i (-1)^{n(i\&k)}a_i\right)\left(\sum_j (-1)^{n(j\&k)}a_j\right)\\
&=\bigl((-1)^{n(0\&k)}a_0+(-1)^{n(1\&k)}a_1+(-1)^{n(2\&k)}a_2+\cdots\bigl)\bigl((-1)^{n(0\&k)}b_0+(-1)^{n(1\&k)}b_1+(-1)^{n(2\&k)}b_2+\cdots\bigl)
\end{align}$

Therefore,

$[a_ib_j](Ha)_k\cdot(Hb)_k=(-1)^{n(i\&k)+n(j\&k)}$

where $[]$ denotes the Coefficient extracting operator.

Now the $k$th element of $Hc$ is

$(Hc)_k=(-1)^{n(0\&k)}c_0+(-1)^{n(1\&k)}c_1+\cdots$

Therefore, $[c_r](Hc)_k=(-1)^{n(r\&k)}$ from which we get

$[a_ib_{i \oplus r}](Hc)_k=(-1)^{n(r\&k)}$ (Using $c_r=a_0b_{0 \oplus r}+a_1b_{1 \oplus r}+a_2b_{2 \oplus r}+\cdots$)

Plugging in $r=i \oplus j$ gives

$[a_ib_j](Hc)_k=(-1)^{n((i \oplus j)\&k)}=(-1)^{n(i\&k\text{ } \oplus \text{ } j\&k)}$

For the Dyadic Convolution theorem to hold, we have to show that the coefficients are equal. That means, the exponents have the same parity. Take, $i'=i\&k$ and $j'=j\&k$. Using the lemma, we see that this is indeed true. $\blacksquare$