I am using the method presented in this paper to find the nonlinearity of the function
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
The truth table is $f = [0 \space \space 1]$. Now, I read from the paper by Terry Ritter that
Nonlinearity is the number of bits which must change in the truth table of a Boolean function to reach the closest affine function.
This means the nonlinearity value should be a whole number.
The algorithm to calculate nonlinearity is to first use the Fast Walsh Transform to find the Walsh spectrum, then use the formula
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
where the Walsh spectrum is calculated by multiplying the truth table of the function by the corresponding Hadamard matrix.
So, since $k = 1$, we use the Hadamard matrix of size $2^1$ giving the following Walsh spectrum:
$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1 $$
Therefore
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
What am I missing?
In case the links are dead, the linked papers are:
- Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform by Pedro Miguel Sosa
- Measuring Boolean Function Nonlinearity by Walsh Transform by Terry Ritter