Is there any way to check that a nonlinear boolean function is balanced or not?
I can't think any other way except to check all input variables.
2
-
$\begingroup$ An N-variable boolean function$ f(x)$ is said to be balanced if $hw(f) = 2^{N−1}$ $\endgroup$– hardyramaCommented May 15, 2019 at 19:53
-
$\begingroup$ Can you explain why? And is hw meaning hamming weight? $\endgroup$– jyjCommented May 15, 2019 at 23:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If $$w_H(f)=\#\{x \in \{0,1\}^N:f(x)=1\}$$ denotes the Hamming weight of the truth table of the boolean function $f$ in $N$ variables, the function is balanced if and only if $w_H(f)=2^{N-1}.$
Equivalently, if we define the Walsh-Hadamard transform coefficient of $f$ as $$ \widehat{f}(a)=\sum_{x\in \{0,1\}^N} (-1)^{f(x)+a\cdot x}, \quad a\in \{0,1\}^N, $$ then a function $f$ is balanced if and only if $\widehat{f}(0)=0.$
There are some known constructions of nonlinear boolean functions that are balanced, for example you can find some recent constructions in the paper Construction of Balanced Boolean Functions with High Nonlinearity and Good Autocorrelation Properties by Tang, Zhang and Tang, available on the eprint server here.
-
$\begingroup$ @jyj did this answer your question? $\endgroup$– kodluCommented May 16, 2019 at 22:48