Activity 2.2.6 — Majority Vote Circuit Design
The Problem: Three judges vote on a competition. A performer advances only if at least 2 of 3 judges say yes. How do you build a circuit that makes this decision automatically?
Learning Objectives
By the end of this lesson, students will be able to:
- Design a combinational logic circuit from a word problem specification
- Create a truth table for a majority vote function (3 inputs, 2+ HIGH = output HIGH)
- Simplify the Boolean expression using K-maps
- Implement the circuit using AOI logic gates
- Convert to NAND-only implementation
Vocabulary
Vocabulary (click to expand)
| Term | Definition |
|---|---|
| Majority Function | A logic function where output is HIGH when more than half the inputs are HIGH |
| M-of-N Logic | Output is HIGH when at least M of N inputs are HIGH |
| Design from Specification | Creating a circuit starting from a written problem description |
| Cascade Design | Building a complex circuit from smaller, simpler sub-circuits |
Part 1: Understanding Majority Vote Logic
The majority vote function is a classic combinational logic problem used in voting systems, error detection, and redundant systems.
Definition
For N inputs, the majority vote output is HIGH when more than N/2 inputs are HIGH.
For our case with 3 inputs (A, B, C):
- Output Y = HIGH when at least 2 of 3 inputs are HIGH
- This covers four cases: (1,1,0), (1,0,1), (0,1,1), and (1,1,1)
Key insight: “At least 2 out of 3” means exactly 2 HIGH or all 3 HIGH. You’re looking for any pair of inputs that are both 1.
Part 2: 3-Input Majority Vote Design
Step 1 — Create the Truth Table
With 3 inputs there are 2³ = 8 possible combinations. For each row, count how many inputs are HIGH:
| Row | A | B | C | # HIGH | Y |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 | 2 | 1 |
| 4 | 1 | 0 | 0 | 1 | 0 |
| 5 | 1 | 0 | 1 | 2 | 1 |
| 6 | 1 | 1 | 0 | 2 | 1 |
| 7 | 1 | 1 | 1 | 3 | 1 |
Check your work: Rows 3, 5, 6, and 7 have 2 or more HIGH inputs. Those are the minterms m3, m5, m6, m7.
Step 2 — Write the Boolean Expression (SOP)
Pull the minterms where Y = 1:
| Minterm | ABC | Product Term |
|---|---|---|
| m3 | 011 | A’BC |
| m5 | 101 | AB’C |
| m6 | 110 | ABC’ |
| m7 | 111 | ABC |
Unsimplified SOP:
Y = A’BC + AB’C + ABC’ + ABC
Step 3 — Simplify with Boolean Algebra
Combine terms that differ by only one variable:
| Pair | Combined |
|---|---|
| m5 + m7: AB’C + ABC | AC(B’ + B) = AC |
| m6 + m7: ABC’ + ABC | AB(C’ + C) = AB |
| m3 + m7: A’BC + ABC | BC(A’ + A) = BC |
Simplified:
Y = AB + BC + AC
Key insight: Each term represents one pair of inputs. The output is HIGH when any pair is both HIGH.
Step 4 — Verify with a K-Map
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
Groups (three overlapping pairs):
| Group | Cells | Term |
|---|---|---|
| Pair 1 | m5, m7 | AC |
| Pair 2 | m6, m7 | AB |
| Pair 3 | m3, m7 | BC |
All three groups share cell m7 (overlapping is allowed). Result matches the algebra: Y = AB + BC + AC
Step 5 — Draw the Circuit
┌──────┐
A ──┬───┤ AND ├──┐
B ──┤ └──────┘ │
│ │ ┌────────┐
│ ┌──────┐ ├───┤ │
├───┤ AND ├──┤ │ 3-in ├── Y
│ └──────┘ ├───┤ OR │
B ──┤ │ │ │
C ──┤ ┌──────┐ │ └────────┘
├───┤ AND ├──┘
A ──┘ └──────┘
C ──────┘Gate count: 3 × 2-input AND gates + 1 × 3-input OR gate
ICs needed:
- 74HC08 (quad 2-input AND) — uses 3 of 4 gates
- 74HC32 (quad 2-input OR) — use 2 gates cascaded for 3-input OR
Step 6 — Verify Each Case
| Condition | AB | BC | AC | Y = AB + BC + AC |
|---|---|---|---|---|
| A=1, B=1, C=0 | 1 | 0 | 0 | 1 ✓ |
| A=1, B=0, C=1 | 0 | 0 | 1 | 1 ✓ |
| A=0, B=1, C=1 | 0 | 1 | 0 | 1 ✓ |
| A=1, B=1, C=1 | 1 | 1 | 1 | 1 ✓ |
All cases match the truth table.
Part 3: NAND-Only Implementation
Since NAND gates are universal (and the 74HC00 IC is cheap and plentiful), converting to NAND-only is a standard skill.
Conversion
Start with: Y = AB + BC + AC
Apply double complement and DeMorgan’s:
Y = ( (AB)’ · (BC)’ · (AC)’ )’
Circuit uses 4 NAND gates:
┌───────┐
A ──┬───┤ NAND ├──┐
B ──┤ └───────┘ │
│ │ ┌────────┐
│ ┌───────┐ ├───┤ │
├───┤ NAND ├──┤ │ NAND ├── Y
│ └───────┘ ├───┤ │
B ──┤ │ └────────┘
C ──┤ ┌───────┐ │
├───┤ NAND ├──┘
A ──┘ └───────┘
C ──────┘ICs needed: Just one 74HC00 (quad 2-input NAND) — uses all 4 gates.
Part 4: Extending to 5-Input Majority Vote
The Challenge
Design a circuit with 5 inputs (A, B, C, D, E) where output Y is HIGH when at least 3 of 5 inputs are HIGH.
With 5 inputs, the truth table has 2⁵ = 32 rows. The minterms where Y = 1:
| Exactly # HIGH | Count | Combinations |
|---|---|---|
| 3 | C(5,3) = | 10 |
| 4 | C(5,4) = | 5 |
| 5 | C(5,5) = | 1 |
| Total | 16 minterms |
That’s a lot. Instead of writing all 32 rows, engineers use cascade design.
Cascade Approach
Build the 5-input majority from smaller 3-input majority blocks:
Stage 1 — Three 3-input majority voters:
- M1 = majority(A, B, C)
- M2 = majority(A, B, D)
- M3 = majority(A, B, E)
Stage 2 — One more majority voter:
- Y = majority(M1, M2, M3)
┌─────────────┐
A ───┤ Maj(A,B,C) ├── M1 ──┐
B ───┤ │ │ ┌─────────────┐
C ───┘ │ ├──┤ Maj(M1,M2,3) ├── Y
┌─────────────┐ │ └─────────────┘
A ───┤ Maj(A,B,D) ├── M2 ──┤
B ───┤ │ │
D ───┘ │ │
┌─────────────┐ │
A ───┤ Maj(A,B,E) ├── M3 ──┘
B ───┤ │
E ───┘ │Key insight: Breaking a complex problem into smaller, tested modules makes design and debugging much easier. Each 3-input block is just Y = AB + BC + AC from Part 2.
Part 5: Real-World Applications
Triple Modular Redundancy (TMR)
Three sensors measure the same value in a safety-critical system. The majority vote determines the accepted reading — one faulty sensor is automatically outvoted.
| Scenario | Sensor A | Sensor B | Sensor C | Majority Output |
|---|---|---|---|---|
| All OK | 1 | 1 | 1 | 1 ✓ |
| One faulty | 1 | 0 | 1 | 1 ✓ (faulty B outvoted) |
| Two faulty | 0 | 0 | 1 | 0 ✗ (majority wrong) |
TMR tolerates 1 sensor failure. This is used in aerospace, nuclear, and medical systems.
Other Applications
- Error correction — Data bits are repeated; majority vote recovers the correct value
- Fault-tolerant computing — Multiple processors vote on results
- Election systems — The literal definition of majority voting
Practice Problems
Problem 1 — 4-Input Majority
For a 4-input majority vote circuit (output HIGH when at least 3 of 4 inputs are HIGH), determine how many minterms produce Y = 1.
Show Answer
| Exactly # HIGH | Combinations |
|---|---|
| 3 | C(4,3) = 4 |
| 4 | C(4,4) = 1 |
| Total | 5 minterms |
Problem 2 — NAND Conversion
Convert Y = AB + BC + AC to NAND-only form. How many NAND gates are needed?
Show Solution
Y = ( (AB)’ · (BC)’ · (AC)’ )’
- NAND(A, B) → (AB)’
- NAND(B, C) → (BC)’
- NAND(A, C) → (AC)’
- NAND(outputs of 1, 2, 3) → Y
4 NAND gates — fits on a single 74HC00 IC.
Problem 3 — Design Challenge
A school cafeteria needs a voting system where 3 student representatives each have a switch. A proposal passes if at least 2 of 3 vote YES. Complete the full design process.
Show Solution
This is the 3-input majority vote from Part 2.
Truth Table: (same as Step 1)
| A | B | C | Y |
|---|---|---|---|
| 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 |
Simplified: Y = AB + BC + AC
Hardware: 3 input switches with pull-down resistors → 74HC08 (AND gates) → 74HC32 (OR gate) → output LED with current-limiting resistor
Or NAND-only: Single 74HC00 IC (4 NAND gates)
Summary
| Concept | Key Takeaway |
|---|---|
| Majority vote | Output HIGH when > half of inputs are HIGH |
| 3-input expression | Y = AB + BC + AC (any pair is both HIGH) |
| K-map grouping | Three overlapping groups of 2 |
| NAND conversion | 4 gates on one 74HC00 IC |
| 5-input extension | Cascade from 3-input blocks |
| Real-world use | TMR, error correction, voting systems |
Custom activity — adapted from PLTW Digital Electronics