Semiconductor & Computer Engineering
| Line 1: | Line 1: | ||
| + | {| 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 10: | Line 33: | ||
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>. | 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>. | ||
| + | |||
| + | == 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 universal 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 efficient location. | ||
== Majority gate == | == Majority gate == | ||
Revision as of 23:48, 23 November 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.
A 3-input majority function can be implemented using the following Boolean function .
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, MAJ} is a universal set). Being self-dual means that which could yields various hardware implementation optimization - such as floating the inversion point to a more efficient location.
Majority gate
- Main article: majority gate
The majority gate is a logic gate that implements the majority function as a circuit.