From WikiChip
Difference between revisions of "boolean algebra/majority function"
< boolean algebra

m
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{ba title|Majority Function (Maj)}}
 +
{| class="wikitable" style="float: right; text-align: center;"
 +
! colspan="4" | 3-input Majority
 +
|-
 +
! colspan="3" | Inputs !! Output
 +
|-
 +
! X !! Y !! Z !! Q
 +
|-
 +
| 0 || 0 || 0 || 0
 +
|-
 +
| 0 || 0 || 1 || 0
 +
|-
 +
| 0 || 1 || 0 || 0
 +
|-
 +
| 0 || 1 || 1 || 1
 +
|-
 +
| 1 || 0 || 0 || 0
 +
|-
 +
| 1 || 0 || 1 || 1
 +
|-
 +
| 1 || 1 || 0 || 1
 +
|-
 +
| 1 || 1 || 1 || 1
 +
|}
 
'''Majority function''' (sometimes '''quorum function''') is a [[threshold function]] that produces a 1 if and only if the majority of the inputs are 1. Otherwise, the output is 0. This function is only defined for three or more odd inputs. The majority function can be found in various applications such as [[adder]]s, [[subtractor]]s, [[cryptographic hash function|hash functions]], and [[Muller C-element]].
 
'''Majority function''' (sometimes '''quorum function''') is a [[threshold function]] that produces a 1 if and only if the majority of the inputs are 1. Otherwise, the output is 0. This function is only defined for three or more odd inputs. The majority function can be found in various applications such as [[adder]]s, [[subtractor]]s, [[cryptographic hash function|hash functions]], and [[Muller C-element]].
  
Line 9: Line 33:
 
</math>
 
</math>
  
A 3-input majority function can be implemented using the following Boolean function <math>\text{MAJ}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)</math>.
+
== 3-input Majority Function==
 +
A 3-input majority function is defined as:
 +
:<math>f:\mathbb{B}^3 \to \mathbb{B}, \text{ is } \text{MAJ3}(x,y,z) = (x \land y) \lor (x \land z) \lor (y \land z)</math>
 +
In the field of [[cryptography]], the XOR version is also common.
 +
:<math>\text{MAJ3}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)</math>
 +
 
 +
=== properties ===
 +
The majority function is a [[unate function]], symmetric, monotone increasing, and self-dual. It therefore, with the addition of just an [[inverter]] it can satisfy all the conditions needed to be [[functionally complete]] (i.e. '''{'''[[not gate|NOT]], [[MAJ]]'''}''' is a complete set). Being self-dual means that <math>\text{MAJ}(\bar a, \bar b, \bar c) = \overline{\text{MAJ}(a, b, c)}</math> which could yields various hardware implementation optimization - such as floating the [[inversion bubble|inversion point]] to a more desired location.
 +
 
 +
=== median algebra ===
 +
{{main|median algebra}}
 +
By treating the majority function [[conjunction]] and [[disjunction]] as min and max functions respectively, then it's easy to see how the majority function can serve as the median - i.e. <math>\text{MAJ3}(x,y,z) = y \text{ if } x \le y \le z</math>. '''Median algebra''' is a generalized idea based on the majority function, algebra with axioms on a set of [[truth value]]s.
  
 
== Majority gate ==
 
== Majority gate ==

Latest revision as of 20:04, 15 December 2015

3-input Majority
Inputs Output
X Y Z Q
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Majority function (sometimes quorum function) is a threshold function that produces a 1 if and only if the majority of the inputs are 1. Otherwise, the output is 0. This function is only defined for three or more odd inputs. The majority function can be found in various applications such as adders, subtractors, hash functions, and Muller C-element.

Equation MAJ left-parenthesis x 1 comma x 2 comma period period period comma x Subscript n Baseline right-parenthesis equals StartLayout Enlarged left-brace 1st Row 1st Column 1 comma 2nd Column if sigma-summation Underscript i equals 1 Overscript n Endscripts x Subscript i Baseline greater-than-or-equal-to StartFraction n Over 2 EndFraction 2nd Row 1st Column 0 comma 2nd Column otherwise period EndLayout

3-input Majority Function[edit]

A 3-input majority function is defined as:

Equation f colon double-struck upper B cubed right-arrow double-struck upper B comma is MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals left-parenthesis x logical-and y right-parenthesis logical-or left-parenthesis x logical-and z right-parenthesis logical-or left-parenthesis y logical-and z right-parenthesis

In the field of cryptography, the XOR version is also common.

Equation MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals left-parenthesis x logical-and y right-parenthesis circled-plus left-parenthesis x logical-and z right-parenthesis circled-plus left-parenthesis y logical-and z right-parenthesis

properties[edit]

The majority function is a unate function, symmetric, monotone increasing, and self-dual. It therefore, with the addition of just an inverter it can satisfy all the conditions needed to be functionally complete (i.e. {NOT, MAJ} is a complete set). Being self-dual means that Equation MAJ left-parenthesis a overbar comma b overbar comma c overbar right-parenthesis equals ModifyingAbove MAJ left-parenthesis a comma b comma c right-parenthesis With bar which could yields various hardware implementation optimization - such as floating the inversion point to a more desired location.

median algebra[edit]

Main article: median algebra

By treating the majority function conjunction and disjunction as min and max functions respectively, then it's easy to see how the majority function can serve as the median - i.e. Equation MAJ 3 left-parenthesis x comma y comma z right-parenthesis equals y if x less-than-or-equal-to y less-than-or-equal-to z . Median algebra is a generalized idea based on the majority function, algebra with axioms on a set of truth values.

Majority gate[edit]

Main article: majority gate

The majority gate is a logic gate that implements the majority function as a circuit.

See also[edit]