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 .
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
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
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
- — 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:
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).
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.
| Adder | Delay grows as | Cost |
|---|---|---|
| Ripple-carry | ( gate delays) | low |
| Carry-lookahead | higher (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.
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).
Exercise – Full Adder with a Decoder
Inputs ; outputs , . Use a 3-to-8 decoder and two 4-input ORs:
Exercises: NAND implementation of the HA; 2-bit adder from three HAs; full adder with a 3-to-8 decoder (§7).