display | more...

A boolean function is said to be balanced if it outputs 1 (one) half of the time and 0 (zero) the other half, across all possible inputs.

This can be extended to functions over other finite fields (GF(qn) → GF(pm), with qn ≥ pm): a function is said to be balanced if it is surjective and every element of the codomain occurs with equal probability, across all possible inputs.

In the boolean case, if a function f (GF(2n) → GF(2m)) is balanced, then it can be expressed as the concatenation of m balanced boolean functions (GF(2n) → GF(2)).

As an example, let's look at the output of a boolean function (GF(23) → GF(2)):

f(x0,x1,x2) = (x0 AND x1) v (x0 AND x2) v (x1 AND x2)
(where v denotes OR)

x0 = 0, x1 = 0, x2 = 0 → f(x0,x1,x2) = 0
x0 = 1, x1 = 0, x2 = 0 → f(x0,x1,x2) = 0
x0 = 0, x1 = 1, x2 = 0 → f(x0,x1,x2) = 0
x0 = 1, x1 = 1, x2 = 0 → f(x0,x1,x2) = 1
x0 = 0, x1 = 0, x2 = 1 → f(x0,x1,x2) = 0
x0 = 1, x1 = 0, x2 = 1 → f(x0,x1,x2) = 1
x0 = 0, x1 = 1, x2 = 1 → f(x0,x1,x2) = 1
x0 = 1, x1 = 1, x2 = 1 → f(x0,x1,x2) = 1

As we can see, over all 8 possible combinations of inputs you get zero 4 times as output and you get one 4 times as well, which indicates that this boolean function (called "majority function") is balanced.

Log in or register to write something here or to contact authors.