Semiconductor & Computer Engineering
m (David moved page majority function to boolean algebra/majority function) |
|||
| Line 33: | Line 33: | ||
</math> | </math> | ||
| − | A 3-input majority function | + | == 3-input Majority Function== |
| − | :<math>\text{ | + | A 3-input majority function is defined as: |
| − | :<math>\text{ | + | :<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 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 | + | 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 == | ||
Revision as of 14:19, 9 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.
3-input Majority Function
A 3-input majority function is defined as:
In the field of cryptography, the XOR version is also common.
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, MAJ} is a complete set). Being self-dual means that which could yields various hardware implementation optimization - such as floating the inversion point to a more desired location.
median algebra
- 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. . Median algebra is a generalized idea based on the majority function, algebra with axioms on a set of truth values.
Majority gate
- Main article: majority gate
The majority gate is a logic gate that implements the majority function as a circuit.