Reminder: This post contains 1571 words
· 5 min read
· by Xianbin
This post shows the basic math required to understand the boolean function analysis.
Definitions.
Rademacher Function
The n-th Rademacher function \(r_n(t)\) is defined on the interval [0, 1] as follows.
\(r_n(t) = \operatorname{sign}\left( \sin(2^n \pi t) \right)\)
or equivalently,
\[r_n(t) = (-1)^{\lfloor 2^n t \rfloor}\]
where \(n \in \mathbb{N}\).
Or,
\(r_i(x) = (-1)^{x_i}\)
where \(x_i\) satisfying the following expansion.
\[x = \sum_{i=0}^{+\infty} \frac{x_i}{2^n}\]
\[0\leq x <1/2^n; x_1 = 0;\\
1/2^n \leq x < 2/2^n; x_{1} = 1;\\
....\\\]
It is easy to see that \(x_i\) differs with (odd) even number of bits with \(x_{i+1}\) alternatively.
Walsh Function
The Walsh function is very similar to Rademacher function, but it has more interesting properties. The motivation of creating Walsh function is that to represent a periodic function by simple components like Fourier expansions.
It needs to satisfy some properties, like orthogonality basis.
Let
\(n = a_0 + 2 a_1 + \cdots + 2^k a_k \quad \text{where } a_i \in \{0,1\}\)
Then, we have
\(w_n(x) = \Pi_{i=1}^k r_i(x)^{a_i}\)
where \(a_i\) is the indicator of the \(i\)-th bit of \(n\).
To be more clearly, we have
\[w_n(x) =\Pi_{i=0}^k (-1)^{a_i x_i} = (-1)^{\sum_{i=0}^k a_ix_i}\]
Examples
| n |
Binary |
Walsh Function Expression |
| 0 |
000 |
\(w_0(x) = 1\) |
| 1 |
001 |
\(w_1(x) = r_0(x)\) |
| 2 |
010 |
\(w_2(x) = r_1(x)\) |
| 3 |
011 |
\(w_3(x) = r_0(x) \cdot r_1(x)\) |
\[w_0(x) = 1; \\w_1(x) = (-1)^{x_1};\\ w_2(x) = (-1)^{x_2}; \\w_3(x) = (-1)^{x_1+x_2}\]
where \(0\leq x< 1/4, x_1 = 0, x_2 = 0\);
\(0\leq x < 1/4; x_1 = 0, x_2 = 0;\\
1/4 \leq x < 1/2; x_1 = 0, x_2 = 1;\\
1/2\leq x < 3/4; x_1 = 1, x_2 =0;\\
3/4\leq x < 1; x_1 = 1, x_2 = 1;\)
Then, it is easy to check the following.
-
\[w_a(x) \cdot w_b(x) = w_{a \oplus b}(x)\]
- \(\langle w_i, w_j\rangle =\int_0^1 w_i(x)w_j(x) dx= 0\)
for any \(i\neq j\).
To be continued …