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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}