[SoC-02] Digital System Basics: The Foundation of Every Computer

Introduction

#

Before we can design a CPU, build a pipeline, or write firmware for an SoC, we need to speak the language that all digital hardware speaks: binary logic. This post is a comprehensive review of the foundational concepts you will need throughout the rest of this course.

Even if you have seen this material before, I encourage you to read through it carefully — a solid foundation here will make everything else much easier to understand.

1. Number Systems

#

Computers do not think in decimal. They think in binary — because at the physical level, a transistor is either ON or OFF, a voltage is either HIGH or LOW. But humans find binary cumbersome, so we also use hexadecimal and octal as convenient shorthands.

1.1 Decimal (Base-10)

#

The system we use every day. Each digit position represents a power of 10.

1.2 Binary (Base-2)

#

Each digit (called a bit) is either 0 or 1. Each position represents a power of 2.

Common terminology:

1.3 Hexadecimal (Base-16)

#

Uses digits 0–9 and letters A–F. Each hex digit represents exactly 4 binary bits, making it a compact way to write binary values.

Example:

In binary: $2F3_{16} = 0010\ 1111\ 0011_2$

1.4 Octal (Base-8)

#

Uses digits 0–7. Each octal digit represents exactly 3 binary bits. Less common today but still seen in Unix file permissions.

1.5 Conversion Summary

#

Binary ←──────→ Hexadecimal
  │     (group by 4 bits)
  │
  ├──────→ Octal
  │  (group by 3 bits)
  │
  └──────→ Decimal
     (positional weight sum)

Decimal → Binary conversion (repeated division by 2):

Example: Convert 25 to binary

25 ÷ 2 = 12  remainder 1  ← LSB
12 ÷ 2 = 6   remainder 0
 6 ÷ 2 = 3   remainder 0
 3 ÷ 2 = 1   remainder 1
 1 ÷ 2 = 0   remainder 1  ← MSB

Result: (11001)₂  →  Read remainders bottom-to-top

2. Logic Gates: The Building Blocks

#

Every digital circuit — from a simple LED controller to a billion-transistor SoC — is built from a small set of logic gates. Each gate takes one or more binary inputs and produces a binary output according to a fixed rule.

2.1 Basic Gates

#

NOT Gate (Inverter)

#

Flips the input: 0 becomes 1, 1 becomes 0.

A ──►[▷○]──► Y

AND Gate

#

Output is 1 only if all inputs are 1.

A ──┐
    ├──[&]──► Y
B ──┘

OR Gate

#

Output is 1 if at least one input is 1.

A ──┐
    ├──[≥1]──► Y
B ──┘

2.2 Universal Gates

#

NAND Gate

#

AND followed by NOT. This single gate is universal — any logic function can be built using only NAND gates.

NOR Gate

#

OR followed by NOT. Also a universal gate.

Why are NAND and NOR called “universal”? Because you can construct AND, OR, NOT, and any other gate using only NAND gates (or only NOR gates). In real chip manufacturing, CMOS NAND and NOR gates are the most natural structures to build from transistors.

2.3 XOR and XNOR

#

XOR (Exclusive OR)

#

Output is 1 when the inputs differ.

XOR is extremely important for:

• Arithmetic (addition, parity checking)
• Error detection (CRC, parity bits)
• Comparators (checking if two values differ)

XNOR (Exclusive NOR)

#

Output is 1 when the inputs are the same.

2.4 Gate Summary

#

3. Boolean Algebra

#

Boolean algebra provides the mathematical framework for analyzing and simplifying digital logic circuits. Mastering these rules lets you reduce complex circuits to simpler, cheaper, faster equivalents.

3.1 Fundamental Laws

#

3.2 De Morgan’s Theorems

#

These two theorems are arguably the most important rules in digital design:

In words:

• “The complement of AND is OR of complements”
• “The complement of OR is AND of complements”

Practical significance: De Morgan’s theorems let you convert between AND/OR representations, which is essential for implementing logic using only NAND or only NOR gates.

3.3 Simplification Example

#

Let’s simplify the expression $Y = A\overline{B}C + A\overline{B},\overline{C} + AB\overline{C}$:

We reduced a 3-term expression to 2 terms — which means fewer gates, less area, less power, and shorter delay in hardware.

3.4 Karnaugh Maps (K-Maps)

#

For functions with up to 4–5 variables, Karnaugh maps provide a visual method for simplification. The key idea: arrange truth table entries in a grid where adjacent cells differ by exactly one variable, then group adjacent 1s into rectangles of power-of-2 size.

Example: Simplify $F(A, B, C, D) = \sum m(0, 1, 2, 5, 8, 9, 10)$

        CD
AB    00  01  11  10
  ┌────┬────┬────┬────┐
00│ 1  │ 1  │ 0  │ 1  │
  ├────┼────┼────┼────┤
01│ 0  │ 1  │ 0  │ 0  │
  ├────┼────┼────┼────┤
11│ 0  │ 0  │ 0  │ 0  │
  ├────┼────┼────┼────┤
10│ 1  │ 1  │ 0  │ 1  │
  └────┴────┴────┴────┘

Groupings:

• Group 1: cells (0,0), (0,1), (10,0), (10,1) → $\overline{B},\overline{D} + \overline{B},\overline{C}$ → simplifies to $\overline{B},\overline{D}$…

Let me walk through it more carefully:

• Group of 4 — corners: m(0), m(2), m(8), m(10) → $\overline{B},\overline{D}$
• Group of 2 — m(0), m(1) and m(8), m(9): → $\overline{B},\overline{C}$
• Single — m(5): $\overline{A}B\overline{C}D$

The K-map gives us a minimal sum-of-products form. In real designs, EDA (Electronic Design Automation) tools do this optimization automatically for much larger circuits.

4. Combinational Circuits

#

Combinational circuits produce outputs that depend only on the current inputs — they have no memory. They are the “pure functions” of digital hardware.

4.1 Multiplexer (MUX)

#

A multiplexer selects one of several inputs and forwards it to the output, based on a select signal. Think of it as a digitally controlled switch.

2-to-1 MUX:

I0 ──┐
     ├──[MUX]──► Y
I1 ──┘
       ↑
       S (select)

4-to-1 MUX uses 2 select lines ($S_1 S_0$) to choose from 4 inputs.

Where MUXes are used in CPUs:

• Selecting between register data and immediate values for the ALU
• Choosing the next PC value (PC+4 vs. branch target)
• Data forwarding paths in pipelined processors

4.2 Decoder

#

A decoder takes an $n$-bit input and activates exactly one of $2^n$ output lines.

2-to-4 Decoder:

       ┌──────────┐
A ────►│          │──► Y0 = Ā·B̄
B ────►│ 2-to-4   │──► Y1 = Ā·B
       │ Decoder  │──► Y2 = A·B̄
       │          │──► Y3 = A·B
       └──────────┘

Where decoders are used in CPUs:

• Instruction decoding (opcode → control signals)
• Memory address decoding (selecting a memory bank)
• Register file access (selecting which register to read/write)

4.3 Encoder

#

The reverse of a decoder: takes $2^n$ input lines and produces an $n$-bit binary code indicating which input is active.

Priority Encoder: When multiple inputs are active simultaneously, the priority encoder outputs the code for the highest-priority input. This is essential for interrupt handling in SoCs.

4.4 Adder Circuits

#

Adders are the most fundamental arithmetic circuits and form the core of the ALU.

Half Adder

#

Adds two single bits:

Full Adder

#

Adds two bits plus a carry-in from the previous position:

Ripple Carry Adder (RCA)

#

Chain N full adders together to add N-bit numbers:

A3 B3    A2 B2    A1 B1    A0 B0
 │  │     │  │     │  │     │  │
 ▼  ▼     ▼  ▼     ▼  ▼     ▼  ▼
┌────┐   ┌────┐   ┌────┐   ┌────┐
│ FA │◄──│ FA │◄──│ FA │◄──│ FA │◄── Cin=0
└──┬─┘   └──┬─┘   └──┬─┘   └──┬─┘
Cout S3      S2       S1       S0

Problem: The carry must ripple through all N stages. For a 32-bit adder, the worst-case delay is proportional to 32 gate delays — this is slow!

Carry Lookahead Adder (CLA)

#

Solves the ripple delay problem by computing carries in parallel using generate ($G$) and propagate ($P$) signals:

By expanding this recursion, all carries can be computed simultaneously in $O(\log N)$ gate delays instead of $O(N)$.

4.5 Arithmetic Logic Unit (ALU)

#

The ALU combines multiple functional units (adder, AND, OR, XOR, shift, comparator) with a MUX that selects the desired operation:

       A          B
       │          │
       ▼          ▼
   ┌───────────────────┐
   │       ALU         │
   │  ┌─────┐ ┌─────┐ │
   │  │Adder│ │ AND  │ │
   │  └──┬──┘ └──┬──┘ │
   │  ┌──┴──┐ ┌──┴──┐ │
   │  │ OR  │ │ XOR │ │
   │  └──┬──┘ └──┬──┘ │
   │     └───┬───┘     │
   │      [MUX]        │
   │        ↑           │
   │     ALU_Op         │
   └────────┬───────────┘
            │
         Result
     (+ Zero, Overflow flags)

5. Sequential Circuits

#

Unlike combinational circuits, sequential circuits have memory — their output depends not only on current inputs but also on the history of past inputs. This memory is what allows computers to store data, maintain state, and execute programs step by step.

5.1 Latches

#

SR Latch

#

The simplest memory element, built from two cross-coupled NOR or NAND gates:

S ──┐        ┌──► Q
    ├──[NOR]─┤
  ┌─┘        │
  │  ┌───────┘
  │  │
  └──┤
    ├──[NOR]─┤
R ──┘        └──► Q̄

Problem: The SR latch is level-sensitive — it responds to input changes at any time, which makes it hard to control in synchronous systems.

D Latch

#

Eliminates the forbidden state by using a single data input D and an enable signal:

5.2 Flip-Flops

#

Flip-flops are edge-triggered — they only capture the input at the precise moment of a clock edge (usually the rising edge). This is essential for building reliable synchronous circuits.

D Flip-Flop

#

      ┌─────────┐
D ───►│  D   Q  │───► Q
      │         │
CLK ─►│>        │
      │  D   Q̄  │───► Q̄
      └─────────┘

Timing parameters:

These parameters determine the maximum clock frequency of a synchronous circuit:

Where $t_{comb}$ is the delay of the combinational logic between two flip-flops.

5.3 Registers

#

A register is a group of flip-flops that store a multi-bit value. For example, a 32-bit register consists of 32 D flip-flops sharing the same clock signal.

              32-bit Register
CLK ─────────────────────────────────►
         │     │     │          │
D[31] ─►[FF] [FF] [FF]  ...  [FF]◄─ D[0]
         │     │     │          │
       Q[31] Q[30] Q[29]     Q[0]

In a CPU:

• Program Counter (PC): register holding the address of the current instruction
• Register File: array of 32 registers (in RISC-V), each 32 or 64 bits wide
• Pipeline registers: hold intermediate results between pipeline stages

5.4 Finite State Machines (FSMs)

#

An FSM is the general model for any sequential circuit. It consists of:

                 ┌─────────────────────────┐
                 │                          │
Input ──────────►│   Combinational Logic    │──────► Output
                 │   (Next State + Output)  │
                 └────────┬────────────────┘
                          │
                          ▼
                    ┌───────────┐
                    │  State    │
                    │ Register  │◄─── CLK
                    └─────┬─────┘
                          │
                          └─────────────► (fed back to combinational logic)

Two types:

FSMs are used extensively in CPU control units, communication protocol handlers, and bus arbiters inside SoCs.

6. From Gates to Processors: The Big Picture

#

Now you can see how these building blocks stack up:

Level 0:  Transistors (NMOS, PMOS)
              ↓
Level 1:  Logic Gates (NAND, NOR, XOR, ...)
              ↓
Level 2:  Combinational Blocks (MUX, Decoder, Adder, ALU)
              ↓
Level 3:  Sequential Blocks (Flip-Flops, Registers, FSMs)
              ↓
Level 4:  Functional Units (Register File, Control Unit, Memory)
              ↓
Level 5:  Processor (CPU core with datapath + control)
              ↓
Level 6:  System-on-Chip (CPU + GPU + Accelerators + I/O)

In the upcoming posts, we will climb this ladder step by step — from computer arithmetic (Level 2) all the way up to a complete pipelined processor (Level 5) and embedded SoC software (Level 6).

7. Summary

#

Here is what we covered in this post:

In the next post ([SoC-03]), we will dive deep into computer arithmetic — how binary addition, subtraction, multiplication, and division actually work inside a processor, and how floating-point numbers are represented.

This post is part of the SoC Design Course series. Navigate to the next post to continue your learning journey.