From WikiChip
Difference between revisions of "majority gate"

(MAJ5)
Line 31: Line 31:
  
 
== MAJ5 ==
 
== MAJ5 ==
{{empty section}}
+
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.
  
 
== See also ==
 
== See also ==
 
* [[logic gates]]
 
* [[logic gates]]
 
* [[compound logic gates]]
 
* [[compound logic gates]]

Revision as of 00:14, 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

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

MAJ3

MAJ3 gate.svg 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

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
maj gate (cmos).svg

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.[1] This is probably optimal, since the optimal sorting network of 5 terms has 9 comparisons.

See also

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