Walsh-Hadamard Transform of Boolean Functions
The Walsh-Hadamard Transform (WHT) is an orthogonal mathematical operation that decomposes Boolean functions into a linear combination of basic affine functions within the binary domain. By converting binary functions from the standard truth-table representation to the spectral domain, the WHT reveals fundamental structural properties such as balancedness, nonlinearity, and correlation immunity. This spectral analysis is essential in cryptography, error-correcting codes, and digital logic design to assess how closely a Boolean function behaves relative to linear functions.
Mathematical Representation in Binary Systems
A Boolean function \(f(x)\) maps an \(n\)-bit binary vector to a single bit:
\[f: \{0, 1\}^n \to \{0, 1\}\]
To compute the Walsh spectrum, the binary outputs \(\{0, 1\}\) are mapped to real-valued polar characters \(\{-1, 1\}\) using the transformation:
\[\hat{f}(x) = (-1)^{f(x)}\]
Under this representation, binary addition (XOR, denoted as \(\oplus\)) corresponds to real multiplication. A linear Boolean function parameterized by a vector \(\omega \in \{0, 1\}^n\) is defined by the binary inner product:
\[\omega \cdot x = \bigoplus_{i=1}^n \omega_i x_i\]
The Walsh-Hadamard Transform of \(f(x)\) at point \(\omega\), denoted as \(W_f(\omega)\), measures the correlation between \(f(x)\) and the linear function \(\omega \cdot x\):
\[W_f(\omega) = \sum_{x \in \{0, 1\}^n} (-1)^{f(x) \oplus (\omega \cdot x)}\]
Computation via the Fast Walsh-Hadamard Transform
Direct computation of the Walsh spectrum for all \(2^n\) spectral coefficients requires \(O(2^{2n})\) operations. However, the transformation matrix exhibits a recursive Kronecker product structure known as the Hadamard matrix:
\[H_0 = [1]\]
\[H_k = \begin{bmatrix} H_{k-1} & H_{k-1} \\ H_{k-1} & -H_{k-1} \end{bmatrix}\]
The Fast Walsh-Hadamard Transform (FWHT) uses a divide-and-conquer butterfly algorithm based on this structure. It reduces the computational complexity to \(O(n 2^n)\) additions and subtractions, processing the truth table in \(n\) sequential stages without requiring matrix multiplication.
Spectral Properties Derived from the WHT
Computing the Walsh spectrum allows direct extraction of several critical mathematical properties of Boolean functions:
Balancedness: A Boolean function has an equal number of zeros and ones if and only if its Walsh coefficient at the zero vector is zero: \[W_f(0) = 0\]
Parseval’s Theorem: The sum of squared Walsh coefficients is invariant for all Boolean functions of \(n\) variables, establishing an energy conservation law in the spectral domain: \[\sum_{\omega \in \{0, 1\}^n} (W_f(\omega))^2 = 2^{2n}\]
Nonlinearity: Nonlinearity (\(N_f\)) measures the minimum Hamming distance between \(f\) and any affine function. It is computed directly from the maximum absolute Walsh coefficient (the spectral radius): \[N_f = 2^{n-1} - \frac{1}{2} \max_{\omega \in \{0, 1\}^n} |W_f(\omega)|\]
Bent Functions: Functions achieving the maximum possible nonlinearity are called bent functions. For an even number of variables \(n\), a function is bent if and only if its Walsh spectrum is completely flat: \[|W_f(\omega)| = 2^{n/2} \quad \forall \omega \in \{0, 1\}^n\]
Correlation Immunity and Resiliency: A function is correlation-immune of order \(m\) if its output is statistically independent of any subset of \(m\) input variables. In the spectral domain, this corresponds to: \[W_f(\omega) = 0 \quad \text{for all } \omega \text{ where } 1 \le \text{wt}(\omega) \le m\] where \(\text{wt}(\omega)\) denotes the Hamming weight (number of non-zero bits) of \(\omega\). If the function is also balanced (\(W_f(0) = 0\)), it is termed \(m\)-resilient.