1. Multiple-Bit Rudimentary Functions (Buses)

A bus is a vector signal, drawn as a wide line with a slash and the number of bits.

  • is a 4-bit bus.
  • A bus can be split into individual bits, into a contiguous subset such as , or a non-contiguous one such as .
  • Rudimentary functions (0, 1, transfer, invert) apply bit by bit to buses.

2. Iterative Combinational Circuits

Definition – Cell and Iterative Array

Arithmetic functions operate on binary vectors and use the same sub-function in every bit position.

  • A cell is the functional block implementing that sub-function.
  • An iterative array is an array of interconnected identical cells (1-D or multi-dimensional).

Example – Why Not One Big Truth Table?

A 32-bit adder has inputs → a truth table with rows and equations with up to 66 variables and a huge number of terms — impractical. The iterative array exploits the regularity: design one 1-bit cell and repeat it.

flowchart RL
    C0["C0"] --> F0["cell 0"]
    F0 -->|"C1"| F1["cell 1"]
    F1 -->|"C2"| F2["…"]
    F2 -->|"Cn-1"| Fn["cell n-1"]
    Fn --> Cn["Cn"]

3. Half-Adder (HA)

Definition

A half-adder adds two bits and and produces a 2-bit result: a sum and a carry .

0000
0101
1001
1110

XYS = X ⊕ YC = XY


4. Full-Adder (FA)

Definition

A full-adder adds two bits , plus a carry-in , producing and . It is needed for every column of an -bit addition except (possibly) the first:

Truth Table and K-Maps

00000
00101
01001
01110
10001
10110
11010
11111

XYZ0001111001011321415716S (no groups: odd function)XYZ0001111001013124517161C = XY + XZ + YZ

  • — the checkerboard of the odd function: .
  • (majority function).

Theorem – Carry Rewritten with XOR

if (sum is 2), or if exactly one of is 1 and the carry-in is 1:

Definition – Generate and Propagate

The full adder is therefore two half-adders + one OR:

X=AᵢY=BᵢZ=CᵢPGS = P ⊕ ZC = G + P·Z

In bit- notation ():


5. Ripple-Carry Adder

Definition

full adders in cascade: the carry-out of each stage is the carry-in of the next more significant stage ( for plain addition).

FAA3B3S3C3FAA2B2S2C2FAA1B1S1C1FAA0B0S0C0C4

Carry Propagation Delay

The carry must ripple from the LSB to the MSB, and a stage’s and are not valid until its carry-in has arrived. Each stage adds 2 gate delays on the carry path (AND then OR), so:

Delay grows linearly with → too slow for 32 or 64 bits.


6. Carry-Lookahead Adder (CLA)

Idea

Compute every carry in advance directly from the inputs, instead of waiting for it to ripple.

  • Generate : stage produces a carry whatever the carry-in.
  • Propagate : stage passes an incoming carry on.

, and are local to each cell; the lookahead makes a global function of all lower cells.

Theorem – Flattened Carry Equations

Starting from and substituting repeatedly:

Reading : cell 1 generates a carry, or cell 1 propagates a carry generated by cell 0, or cells 1 and 0 both propagate .

Every carry is now a 2-level SoP of , , : all carries are ready after the same small number of gate delays.

flowchart TB
    AB["A3..A0, B3..B0"] --> PG["PG cells:<br/>Pi = Ai⊕Bi, Gi = AiBi"]
    PG -->|"P0..P3, G0..G3"| CLL["Carry-lookahead logic<br/>(2-level SoP)"]
    C0["C0"] --> CLL
    CLL -->|"C1, C2, C3"| SUM["Sum XORs<br/>Si = Pi ⊕ Ci"]
    PG -->|"Pi"| SUM
    CLL --> C4["C4"]
    SUM --> S["S3..S0"]

Group Carry Lookahead

⚠️ Flattening all the way costs fan-in: already needs a 5-input AND and a 5-input OR. (Fan-in = number of inputs a gate can take.) Use hierarchy instead.

Definition – Group Generate and Propagate (cells 0–3)

The group generates a carry if cell 3 generates one, or cell 2 generates one that cell 3 propagates, or … cell 0 generates one that cells 1–3 propagate. The group propagates if all four cells propagate.

16-bit CLA

Four 4-bit CLA adders each output ; a second-level lookahead unit (same logic, applied to groups) produces .

flowchart RL
    A3["4-bit adder<br/>bits 3–0"] -->|"GG0, PG0"| L["Second-level<br/>carry-lookahead logic"]
    A2["4-bit adder<br/>bits 7–4"] -->|"GG1, PG1"| L
    A1["4-bit adder<br/>bits 11–8"] -->|"GG2, PG2"| L
    A0["4-bit adder<br/>bits 15–12"] -->|"GG3, PG3"| L
    C0["C0"] --> L
    L -->|"C4"| A2
    L -->|"C8"| A1
    L -->|"C12"| A0
    L --> C16["C16"]
  • is available after 2 gate delays, after 3 (one/two more than , ).
  • Delay grows with instead of .

⚠️ The slide writes ""; . The point is that each added lookahead level multiplies the width by 4 while adding only a constant delay.

AdderDelay grows asCost
Ripple-carry ( gate delays)low
Carry-lookaheadhigher (lookahead logic, large fan-in)

7. Exercises (Solved in the Slides)

Exercise – NAND Implementation of the Half-Adder

From the K-maps: , .

Let (one NAND). Then , which is NAND–NAND: . Finally (NAND used as inverter) — 5 NANDs in total.

XYC’SC

Exercise – 2-Bit Adder from Three Half-Adders

  • HA₀ adds → and carry .
  • HA₁ adds ; HA₂ adds that sum to → .
  • = OR of the two carries from HA₁ and HA₂ (they can’t both be 1).

HAXX0YY0SS0CHAXX1YY1SCHASS1CC1C2

Exercise – Full Adder with a Decoder

Inputs ; outputs , . Use a 3-to-8 decoder and two 4-input ORs:

3-to-8decoder2²X2¹Y2⁰Z01234567S = Σm(1,2,4,7)C = Σm(3,5,6,7)


Exercises: NAND implementation of the HA; 2-bit adder from three HAs; full adder with a 3-to-8 decoder (§7).