Semiconductor & Computer Engineering
m (→Properties) |
m |
||
| Line 32: | Line 32: | ||
</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>. | + | A 3-input majority function can be implemented using the following Boolean function: |
| + | :<math>\text{MAJ}(x,y,z) = (x \land y) \lor (x \land z) \lor (y \land z)</math> | ||
| + | :<math>\text{MAJ}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)</math> | ||
| + | The XOR version is more common in cryptography. | ||
== Properties == | == Properties == | ||
Revision as of 22:45, 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:
The XOR version is more common in cryptography.
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.
