From WikiChip
Difference between revisions of "majority gate"

(MAJ5)
 
Line 12: Line 12:
  
 
== MAJ3 ==
 
== MAJ3 ==
<span style="display:inline-block;float: right; margin: 5px;">[[File:MAJ3 gate.svg|250px]]</span>
+
[[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>.
 
A 3-input MAJ gate (MAJ3) can be implemented as <math>(a \land b) \lor (a \land c) \lor (b \land c)</math>.
 
===CMOS===
 
===CMOS===
Line 19: Line 20:
 
we can define MAJ3 as
 
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>
 
:<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 [[AOI|AOI222]] which is defined as
+
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>
 
:<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:
 
note that by substituting ''a, b, and c'' for ''d, e, and f'' we get MAJ:
Line 27: Line 28:
 
then
 
then
 
:<math>\text{MAJ}(a, b, c) = \overline{OAI222(a, b, c, a, b, c)}</math>
 
:<math>\text{MAJ}(a, b, c) = \overline{OAI222(a, b, c, a, b, c)}</math>
[[File:maj gate (cmos).svg|left|200px]]
 
{{clear}}
 
  
 
== MAJ5 ==
 
== 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> This is probably optimal, since the optimal sorting network of 5 terms has 9 comparisons.
+
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) = ( 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 ==
 
== See also ==
 
* [[logic gates]]
 
* [[logic gates]]
 
* [[compound logic gates]]
 
* [[compound logic gates]]

Latest revision as of 00:29, 8 May 2020

MAJ Gate
Typical Symbol
maj gate.svg
Functional
maj gate functional.gif
Truth Table
3-input Majority Gate
Inputs Outputs
A B C 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
Other Gates
Buffer TriBuffer NOT
AND OR XOR
NAND NOR XNOR
Trans AOI OAI
MAJ INH IMPLY
NIMPLY
Other Components
Plexers
MUX DEMUX Encoder
Decoder Pri-Encoder
ALU
Adder Subtractor Multiplier
Divider Shifter Rotator
MAC Comparator Negator
Memory
D latch D flip-flop SR latch
JK flip-flop T flip-flop Register
Register file SRAM Counter
ROM CAM DRAM
I/O
Shift register SIPO PISO
ADC DAC

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[edit]

New text document.svg This section is empty; you can help add the missing info by editing this page.

MAJ3[edit]

MAJ3 gate.svg
Maj gate on CMOS (AOI222)

A 3-input MAJ gate (MAJ3) can be implemented as Equation left-parenthesis a logical-and b right-parenthesis logical-or left-parenthesis a logical-and c right-parenthesis logical-or left-parenthesis b logical-and c right-parenthesis .

CMOS[edit]

However the naive implementation will result in up to 30 transistors. Since

Equation MAJ left-parenthesis a comma b comma c right-parenthesis equals ModifyingAbove Above ModifyingAbove MAJ left-parenthesis a comma b comma c right-parenthesis With bar With bar ,

we can define MAJ3 as

Equation MAJ left-parenthesis a comma b comma c right-parenthesis equals ModifyingAbove Above ModifyingAbove left-parenthesis a logical-and b right-parenthesis logical-or left-parenthesis a logical-and c right-parenthesis logical-or left-parenthesis b logical-and c right-parenthesis With bar With bar

and that can be implemented using a single AOI222 which is defined as

Equation AOI 222 left-parenthesis a comma b comma c comma d comma e comma f right-parenthesis equals ModifyingAbove left-parenthesis a logical-and b right-parenthesis logical-or left-parenthesis c logical-and d right-parenthesis logical-or left-parenthesis e logical-and f right-parenthesis With bar

note that by substituting a, b, and c for d, e, and f we get MAJ:

Equation MAJ left-parenthesis a comma b comma c right-parenthesis equals ModifyingAbove upper A upper O upper I Baseline 222 left-parenthesis a comma b comma c comma a comma b comma c right-parenthesis With bar

It can also be implemented using a OAI222 gate the very same way. Since

Equation OAI 222 left-parenthesis a comma b comma c comma d comma e comma f right-parenthesis equals ModifyingAbove left-parenthesis a logical-or b right-parenthesis logical-and left-parenthesis c logical-or d right-parenthesis logical-and left-parenthesis e logical-or f right-parenthesis With bar ,

then

Equation MAJ left-parenthesis a comma b comma c right-parenthesis equals ModifyingAbove upper O upper A upper I Baseline 222 left-parenthesis a comma b comma c comma a comma b comma c right-parenthesis With bar

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.

See also[edit]

  • Ralph L. DeCarli (2009). The Majority Gate