Semiconductor & Computer Engineering
m (→Properties) |
|||
| Line 35: | Line 35: | ||
== Properties == | == 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 | + | 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 efficient location. |
== Majority gate == | == Majority gate == | ||
Revision as of 16:56, 24 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 complete 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.