Return to balanced function (thing)

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

This can be extended to functions over other [finite field|finite fields] ([Galois Field|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 function|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 function|balanced].

Existing:


Non-Existing: