Semiconductor & Computer Engineering
From WikiChip
Difference between revisions of "majority gate"
(Created page with "{{title|Majority (MAJ) Gate}} The '''majority gate''' ('''MAJ gate''') is a logic gate that implements the majority function - a device that outputs a HIGH when th...") |
(→MAJ5: fix parameter list of the function) |
||
| (8 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | {{title|Majority (MAJ) Gate}} | + | {{title|Majority Gate (MAJ)}}{{logic device |
| − | The '''majority gate''' ('''MAJ gate''') is a [[logic gate]] that implements the [[majority function]] - a device that outputs a [[HIGH]] when the majority of its inputs are HIGH, otherwise it outputs a | + | |title = MAJ Gate |
| + | |symbol title = Typical Symbol | ||
| + | |symbol body = [[File:maj gate.svg|150px|center]] | ||
| + | |functional body = [[File:maj gate functional.gif|center]] | ||
| + | |truth table = {{truth table/maj}} | ||
| + | }} | ||
| + | The '''majority gate''' ('''MAJ gate''') is a [[logic gate]] that implements the [[majority function]] - a device that outputs a [[HIGH]] when the majority of its inputs are HIGH, otherwise it outputs a [[LOW]]. | ||
| + | |||
| + | == Applications == | ||
| + | {{empty section}} | ||
| + | |||
| + | == MAJ3 == | ||
| + | [[File:MAJ3 gate.svg|frameless|right|250px]] | ||
| + | [[File:maj gate (cmos).svg|thumb|right|200px|Maj gate on CMOS (AOI222)]] | ||
| + | A 3-input MAJ gate (MAJ3) can be implemented as <math>(a \land b) \lor (a \land c) \lor (b \land c)</math>. | ||
| + | ===CMOS=== | ||
| + | However the naive implementation will result in up to 30 transistors. Since | ||
| + | :<math>\text{MAJ}(a, b, c) = \overline{\overline{\text{MAJ}(a, b, c)}}</math>, | ||
| + | we can define MAJ3 as | ||
| + | :<math>\text{MAJ}(a, b, c) = \overline{\overline{(a \land b) \lor (a \land c) \lor (b \land c)}}</math> | ||
| + | and that can be implemented using a single [[Wikipedia:AND-OR-Invert|AOI222]] which is defined as | ||
| + | :<math>\text{AOI222}(a, b, c, d, e, f) = \overline{(a \land b) \lor (c \land d) \lor (e \land f)}</math> | ||
| + | note that by substituting ''a, b, and c'' for ''d, e, and f'' we get MAJ: | ||
| + | :<math>\text{MAJ}(a, b, c) = \overline{AOI222(a, b, c, a, b, c)}</math> | ||
| + | It can also be implemented using a [[OAI|OAI222]] gate the very same way. Since | ||
| + | :<math>\text{OAI222}(a, b, c, d, e, f) = \overline{(a \lor b) \land (c \lor d) \land (e \lor f)}</math>, | ||
| + | then | ||
| + | :<math>\text{MAJ}(a, b, c) = \overline{OAI222(a, b, c, a, b, c)}</math> | ||
| + | |||
| + | == MAJ5 == | ||
| + | A MAJ5 can be naively described as the OR of 10 MAJ3 gates. It can be simplified down to 10 AND gates and 9 OR gates by rewriting the terms:<ref>Ralph L. DeCarli (2009). [https://www.sysmatrix.net/~omnivore/MajorityGate.html The Majority Gate]</ref> | ||
| + | :<math>\text{MAJ5}(A, B, C, D, E) = ( A \land ( ( B \land (C \lor D \lor E) ) \lor ( C \land (D \lor E) ) \lor (D \land E) ) ) \lor ( B \land ( C \land (D \lor E) ) \lor (D \land E) ) \lor ( C \land D \land E )</math> | ||
| + | |||
| + | This is probably optimal, since the optimal sorting network of 5 terms has 9 comparisons. | ||
| + | |||
| + | == See also == | ||
| + | * [[logic gates]] | ||
| + | * [[compound logic gates]] | ||
Latest revision as of 05:11, 8 August 2022
| MAJ Gate | ||||||||||||||||||||||||||||||||||||||||||||
| Typical Symbol | ||||||||||||||||||||||||||||||||||||||||||||
 | ||||||||||||||||||||||||||||||||||||||||||||
| Functional | ||||||||||||||||||||||||||||||||||||||||||||
 | ||||||||||||||||||||||||||||||||||||||||||||
| Truth Table | ||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||
The majority gate (MAJ gate) is a logic gate that implements the majority function - a device that outputs a HIGH when the majority of its inputs are HIGH, otherwise it outputs a LOW.
Contents
Applications[edit]
 |
This section is empty; you can help add the missing info by editing this page. |
MAJ3[edit]
.svg)
A 3-input MAJ gate (MAJ3) can be implemented as .
CMOS[edit]
However the naive implementation will result in up to 30 transistors. Since
- ,
we can define MAJ3 as
and that can be implemented using a single AOI222 which is defined as
note that by substituting a, b, and c for d, e, and f we get MAJ:
It can also be implemented using a OAI222 gate the very same way. Since
- ,
then
MAJ5[edit]
A MAJ5 can be naively described as the OR of 10 MAJ3 gates. It can be simplified down to 10 AND gates and 9 OR gates by rewriting the terms:[1]
This is probably optimal, since the optimal sorting network of 5 terms has 9 comparisons.