Digital Logic Fundamentals
Introduction
Before software runs on a CPU, digital logic defines how bits combine: AND, OR, NOT, and more complex structures built from them. Every register, ALU operation, and GPIO read ultimately rests on logic gates — either as discrete chips (74HC series) or inside an FPGA or MCU silicon.
This article covers combinational logic: gates, truth tables, Boolean algebra, multiplexers, and binary adders. It is essential background for reading schematics, designing glue logic, and understanding how hardware implements arithmetic.
Logic levels
| Level | Typical meaning | Note |
|---|---|---|
| Logic 0 | Low voltage (e.g. 0 V) | Also called LOW, false |
| Logic 1 | High voltage (e.g. 3.3 V, 5 V) | HIGH, true |
Noise margin separates valid 0/1 from undefined zones — critical when mixing 3.3 V and 5 V devices (level shifters may be required).
Basic gates
| Gate | Symbol behaviour | Truth table (A, B → Y) |
|---|---|---|
| NOT | Invert | 0→1, 1→0 |
| AND | Y = 1 only if all inputs 1 | 00→0, 01→0, 10→0, 11→1 |
| OR | Y = 1 if any input 1 | 00→0, others→1 |
| NAND | NOT(AND) | Universal — can build any gate |
| NOR | NOT(OR) | Universal |
| XOR | Y = 1 if inputs differ | 00→0, 01→1, 10→1, 11→0 |
| XNOR | NOT(XOR) | Equality compare |
Example: XOR as parity
Two inputs XOR gives 1 when an odd number of inputs are 1 — used in parity generation:
1 2 | |
Boolean algebra
Simplify logic before building hardware:
| Law | Expression |
|---|---|
| Identity | A + 0 = A, A · 1 = A |
| Null | A + 1 = 1, A · 0 = 0 |
| Idempotent | A + A = A, A · A = A |
| Complement | A + A' = 1, A · A' = 0 |
| De Morgan | (A + B)' = A' · B' ; (A · B)' = A' + B' |
De Morgan is the most useful rule when converting between NAND/NOR implementations and AND/OR forms.
Multiplexer (MUX)
A multiplexer selects one of many inputs based on select lines:
1 2 | |
Use cases:
- Route one of several sensors to a single ADC input
- Implement lookup tables in FPGA
- Build bus arbiters
A demultiplexer (DEMUX) does the reverse: one input to many outputs.
Binary adders
Half adder
Adds two bits A and B:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
- Sum = A XOR B
- Carry = A AND B
Full adder
Adds A, B, and carry-in from previous stage. Chain full adders for multi-bit addition — this is how the ALU adds integers.
Ripple-carry vs carry-lookahead
Ripple-carry: simple, slow for wide words (carry propagates bit by bit).
Carry-lookahead: faster, more gates — used in high-performance CPUs.
Implementations
| Technology | Where you see it |
|---|---|
| Discrete TTL/CMOS | 74HC00, 74HC595 shift registers |
| MCU GPIO + firmware | Bit-banging protocols |
| FPGA/CPLD | Custom parallel logic |
| Inside MCU | Timer PWM, UART, SPI peripherals |
Relevant topics
- Sequential logic design
- Data representation
- Computer architecture
- Logic gate (Wikipedia)
- Adder (electronics)
Starting points
- Build truth tables for NAND and XOR from AND/OR/NOT definitions.
- Simplify
(A + B) · (A + B')using Boolean laws. - Draw a 2-to-1 MUX with AND, OR, NOT — label select line S.
- Simulate a half adder in Logic.ly or Falstad circuit simulator.
Focus points
- NAND/NOR alone can implement any Boolean function — FPGA synthesis uses this.
- Glitch-free design matters when combinational outputs feed critical control — see sequential article.
- Fan-out limits how many inputs one output can drive — use buffers if needed.
- Propagation delay adds up through gate chains — affects maximum clock frequency.
Key points
- Gates implement Boolean functions on logic 0/1 levels.
- MUX/DEMUX route signals; adders implement binary arithmetic in hardware.
- Boolean algebra and De Morgan simplify circuits before building.
- Logic appears as discrete ICs, FPGA fabric, or peripherals inside MCUs.