18. PLAs and memory organization: NOR–NOR planes, replica clocks and the SRAM array

A processor has three kinds of circuit: the datapath (Chapters 16 and 17), the control logic that steers it, and the memory arrays. Lecture 17 takes the last two. Control logic is “random”: it has no regular structure and keeps changing until the chip is taped out. One way to build it is to synthesize it and place and route the gates. The other, this chapter’s, is to write it as a sum of products and lay it out as a regular two-level array, the programmable logic array (PLA). By De Morgan’s laws both levels can be NOR gates. The static PLA builds them in pseudo-NMOS; the dynamic PLA clocks them, and then needs two clocks whose edges are timed by copies of its own rows, a self-timed trick that SRAMs use too. The last part of the lecture opens the third kind of block: the SRAM array, its word lines and bit lines, and how the address bits are split between the rows and the columns. The PLA example begins at the end of Lecture 16 (54:46), and this chapter starts there.

After this chapter you can:

1. turn a sum of products into a NOR–NOR network and name its AND and OR planes;
2. draw a static PLA’s row as a pseudo-NMOS NOR and say what “ratioed” costs;
3. program a PLA for given functions: one row per product, a device on the complement line for a true literal;
4. read a PLA’s outputs off its transistors, with or without output inverters;
5. write a function as an Espresso table and cut its product terms by hand;
6. read a few lines of a VHDL state machine into table rows;
7. explain the dynamic PLA’s race and the two timing requirements its clocks must meet;
8. trace the replica rows that generate φ_AND and φ_OR, edge by edge, and time them with given delays;
9. split a memory’s address bits between the row decoder and the column multiplexer for any physical organization.

Boxes and equations marked board were written in the lecture. Parts marked added are explanations or examples this guide adds.

Symbols

Symbol	Meaning	Unit	First appears
$x_0, x_1, x_2$x0​,x1​,x2​; $\bar x_0, \bar x_1, \bar x_2$	the inputs and their complements: the literals (the board’s names)	—	§1
$f_0$f0​, $f_1$	the example’s two outputs (board)	—	§1
$\bar f_0$fˉ​0​, $\bar f_1$	an OR-plane column’s own output, before the output inverter (the board’s equations)	—	§1
$P_0 \dots P_3$	product rows, top to bottom (the guide’s names; the board labels each row by its expression) added	—	§1
SOP	sum of products: an OR of AND terms	—	§1
$V_{DD}$	the supply	V	§2
$Y$	a gate’s output node	—	§2
$Q_0$Q0​, $Q_1$Q1​, $z$	the rows and output of §4’s practice PLA added	—	§4
1, 0, –	Espresso’s table codes: literal true, complemented, absent; in the output part, 1 = the output uses the product	—	§5
cs, ns	current state and next state of a state machine (board)	—	§6
hl1, hl0, fl1, fl0, st	the controller’s outputs: highway and farm-road lights (two bits each) and start-timer (board)	—	§6
cars, short, long	the controller’s inputs: the car sensor and the timer’s two flags (board)	—	§6
clk, $\overline{\mathrm{clk}}$	the input clock and its complement	—	§7
$\phi_{\mathrm{AND}}$ϕAND​, $\phi_{\mathrm{OR}}$	the AND plane’s and the OR plane’s clocks (board); each plane precharges while its clock is low	—	§7
$y_0$y0​, $y_1$	outputs of a PLA without output inverters (as FN19 names them)	—	§7
$R_1$R1​, $R_2$	the replica rows’ outputs in the φAND and φOR generators added	—	§9
$t_{inv}$tinv​, $t_{NAND}$	an inverter’s and a NAND’s delay added	ps	§8
$t_{pre}$tpre​, $t_{eval}$	a replica row’s precharge time and its evaluate time through one on device added	ps	§8
PVT	process, voltage and temperature (board)	—	§8
$N_w$Nw​, $W$	a memory’s number of words and bits per word (its logical organization) added	—	§10
$R$R, $C$	its physical rows (word lines) and columns (bit lines) added	—	§10
WL, bit, $\overline{\mathrm{bit}}$	a word line, and the pair of bit lines of one column	—	§10

1. Control logic as a sum of products, built from NORs

You need

Gates and bubbles. A NOR’s output is 1 only when every input is 0. An inverter flips its input. A small circle (a bubble) on a gate’s input or output stands for an inverter there.

De Morgan’s laws added (background from earlier courses):

$$\overline{a + b} = \bar a\,\bar b, \qquad \overline{ab} = \bar a + \bar b .$$

Read the first one backwards with $\bar a$ and $\bar b$ in place of $a$ and $b$b: $ab = \overline{\bar a + \bar b}$aˉ+bˉ​. An AND of $a$ and $b$ is a NOR of their complements.

Sum of products added. A literal is an input or its complement ($x_0$x0​ or $\bar x_0$xˉ0​). A product term is an AND of literals ($x_0x_1$x0​x1​). A sum of products is an OR of product terms, and every logic function can be written as one (one product per input row where it is 1, at worst).

The question. Control logic has no regular structure, and it keeps changing until the chip is taped out. How can any such function be built from one kind of gate, laid out as a regular array that is easy to change?

Two ways to build control logic

The lecture recalls Lecture 16’s split board (L16 43:29–46:44; L17 00:52–02:59). Of a processor’s three kinds of circuit (datapath, control, arrays: Chapter 15’s taxonomy), the control logic is the “random” one. It can be built in two ways:

• Multi-level logic, by the semi-custom flow: a synthesis tool turns the description into gates and a place-and-route tool lays them out. The result has no visible structure; the board brackets it as “random logic”. (Chapter 17 sketches the flow.)
• Structured control logic: write each output as a sum of products and build it as two levels of logic in a regular array, the PLA. Adding a product adds a row; changing a function moves transistors in the grid.

The example

The example that runs through the whole chapter board (L16 55:42; L17 06:40) has three inputs $x_0$x0​, $x_1$x1​, $x_2$x2​, each available true and complemented, and two outputs:

$$\begin{aligned} f_0 &= x_0x_1 + \bar x_2 \\ f_1 &= x_0x_1x_2 + \bar x_2 + \bar x_0x_1 \end{aligned}$$

There are four different product terms, $x_0x_1$x0​x1​, $\bar x_2$xˉ2​, $x_0x_1x_2$ and $\bar x_0x_1$xˉ0​x1​, and one of them, $\bar x_2$xˉ2​, is shared: both outputs use it. The PLA will give each product one row, so this PLA has four rows, not five.

AND–OR to NOR–NOR in three moves, then the planes

Lecture 16’s last board draws the conversion for $f_0$ in four stages board (L16 56:06–57:42; frames 57:25, 58:10).

From AND–OR to NOR–NOR, drawn for $f_0 = x_0x_1 + \bar x_2$ (the board, Lecture16 @ 58:10, draws the same stages for generic AND terms; the middle stage is read at 57:25). (a) The sum of products as an AND feeding an OR. (b) An OR is a NOR followed by an inverter. (c) Invert each AND input twice, by an inverter and a bubble, which changes nothing; an AND with bubbled inputs is a NOR (De Morgan), so the AND becomes a NOR of $\bar x_0$ and $\bar x_1$xˉ1​. (d) The NOR–NOR form: complemented literals into the first column of NORs, the AND plane, whose outputs feed the second column, the OR plane, then an output inverter. The single literal $\bar x_2$ becomes a one-input NOR of $x_2$x2​, which is an inverter.

The board (Lecture16 @ 58:10)

Lecture16 @ 58:10Lecture 16's last board: the example's functions, the product terms, and the four De Morgan stages from AND–OR to NOR–NOR.

Fair copy of the board above (Lecture16 @ 58:10), mark for mark in its own layout. All black: one blue pen wrote the board (it looks violet towards the left edge, where the light shifts its hue). The box round the equations is still being drawn: its left side and top are there, and the pen is on its right end. The arrow after the second stage and the inverters of the third, washed out by the lecturer’s raised hand here, are copied from 57:25. The board draws each inverter as a small D shape with a bubble, and writes the $\bar x_2$ of $f_1$ over a first attempt.

Three moves on the first output, then the planes (board, L16 56:06–57:42; L17 02:59)

1. Write the sum of products as gates. $f_0 = x_0x_1 + \bar x_2$ is an AND of $x_0$ and $x_1$x1​, ORed with the literal $\bar x_2$xˉ2​: two levels, AND then OR (panel a).
2. Make the OR a NOR and an inverter. $a + b = \overline{\overline{a + b}}$a+b​​: a NOR gives $\overline{a + b}$a+b​, and an inverter after it gives $a + b$ back (panel b). The output column now computes $\bar f_0$fˉ​0​, and the inverter turns it into $f_0$f0​.
3. Make each AND a NOR of complements. Put an inverter and a bubble on each AND input: two inversions change nothing. An AND with bubbled inputs is a NOR, by De Morgan, $x_0x_1 = \overline{\bar x_0 + \bar x_1}$xˉ0​+xˉ1​​; so the AND becomes a NOR fed with $\bar x_0$ and $\bar x_1$ (panel c). The literal $\bar x_2$ needs no AND; written as a NOR it is a one-input NOR of $x_2$x2​, an inverter.
4. Read off the two planes. Complemented literals go into a column of NORs; their outputs go into a second column of NORs; an inverter follows (panel d). The first column does the work of the ANDs, so it is called the AND plane; the second does the work of the OR, the OR plane. “They’re still both NORs” (02:36).

All four products as NORs

The same move on each of the example’s four products board (L17 08:15 writes all four at the ends of the rows), giving the rows their names $P_0 \dots P_3$ added:

$$\begin{aligned} P_0 &= x_0x_1 = \overline{\bar x_0 + \bar x_1} \\ P_1 &= \bar x_2 = \overline{x_2} \\ P_2 &= x_0x_1x_2 = \overline{\bar x_0 + \bar x_1 + \bar x_2} \\ P_3 &= \bar x_0x_1 = \overline{x_0 + \bar x_1} \end{aligned}$$

Look at $P_3$P3​: its literal $\bar x_0$ is already a complement, so its NOR takes the complement of the complement, $x_0$x0​. Every literal enters its NOR flipped: a true literal as its complement, a complemented one as the true input. The outputs are then NORs of the rows, followed by inverters:

$$\bar f_0 = \overline{P_0 + P_1}, \qquad \bar f_1 = \overline{P_1 + P_2 + P_3},$$

and each output is its column inverted, $f_k = \overline{\bar f_k}$fˉ​k​​.

A product as a NOR of flipped literalsadded

$$\ell_1\ell_2\cdots\ell_k = \overline{\bar\ell_1 + \bar\ell_2 + \cdots + \bar\ell_k}$$

Holds when: any product of literals ℓ₁ℓ₂…ℓ_k, each literal an input or its complement; De Morgan's law applied to a k-input NOR

A sum as a NOR and an inverteradded

$$f = P_0 + P_1 + \cdots = \overline{\;\overline{P_0 + P_1 + \cdots}\;}$$

Holds when: any sum of products P₀ + P₁ + …; the NOR gives the complement, the inverter restores it

Memorize or derive. Derive both, in one line each from De Morgan; what to memorize is the result in words: a product is the NOR of its literals’ complements, and a column of the OR plane gives the complement of the output until an inverter follows it.

A worked example added. Check the NOR–NOR form of $f_0$ on two input rows, written $x_0x_1x_2$x0​x1​x2​.

f0 through its NORs, two input rows

1. Row 110. $P_0 = \overline{\bar x_0 + \bar x_1} = \overline{0 + 0} = 1$1; $P_1 = \overline{x_2} = \overline{0} = 1$1; $\bar f_0 = \overline{1 + 1} = 0$0; $f_0 = 1$1. Directly: $x_0x_1 + \bar x_2 = 1 + 1 = 1$1. They agree.
2. Row 001. $P_0 = \overline{1 + 1} = 0$0; $P_1 = \overline{1} = 0$0; $\bar f_0 = \overline{0 + 0} = 1$1; $f_0 = 0$0. Directly: $0 + 0 = 0$0. They agree.

Traps.

• Feeding a product’s NOR its true literals. $\overline{x_0 + x_1} = \bar x_0\bar x_1$xˉ0​xˉ1​: the product of the complements, the wrong function. Each literal goes in flipped.
• Forgetting the output inverter. The OR plane’s NOR gives $\bar f$fˉ​, not $f$f. Whether an inverter follows decides every output bit (Section 4).
• Counting a shared product twice. $\bar x_2$ appears in both outputs but is one product: one AND-plane NOR, used by both OR-plane NORs.

Check yourself Write the product x̄₀x₁ as a NOR.

$\bar x_0x_1 = \overline{x_0 + \bar x_1}$x0​+xˉ1​​: each literal enters flipped, so $\bar x_0$ enters as $x_0$ and $x_1$ as $\bar x_1$xˉ1​.

Check yourself Write f₁'s OR-plane column as a NOR of NORs, and say which product it shares with f₀.

$\bar f_1 = \overline{P_1 + P_2 + P_3} = \overline{\overline{x_2} + \overline{\bar x_0 + \bar x_1 + \bar x_2} + \overline{x_0 + \bar x_1}}$x2​​+xˉ0​+xˉ1​+xˉ2​​+x0​+xˉ1​​​, and $f_1$ is its inversion. It shares $P_1 = \bar x_2$ with $f_0$f0​, whose column is $\overline{P_0 + P_1}$P0​+P1​​.

2. The static PLA’s gate: a pseudo-NMOS NOR

You need

Pseudo-NMOS (Chapter 10 §10). A PFET whose gate is tied to ground is always on; it pulls the output up, against a pull-down network of NFETs. With every NFET off the output is $V_{DD}$VDD​. With any NFET on, that NFET overpowers the weak PFET and pulls the output low, but not to ground: the low settles where the two currents balance, so it depends on the ratio of their strengths (ratioed logic). And while the output is low, current flows from $V_{DD}$ to ground all the time (static power).

Pseudo-NMOS (Chapter 10, Lecture10 @ 58:57): a grounded-gate PFET over parallel NFETs, and ratioed logic’s two problems. Original figure ↗

A complementary CMOS NOR (Chapter 7). A $k$-input NOR has $k$ parallel NFETs and $k$ PFETs in series: $2k$ devices, and a pull-up stack $k$ high whose PFETs must each be about $k$ times wider to keep the rise time, so a wide NOR is large and slow.

The question. A PLA’s NORs must be as wide as the function needs: a row may have a device for every input, a column one for every product. What gate makes a NOR of any width cheap?

Arbitrarily wide NORs

The static PLA uses pseudo-NMOS board (03:46, 04:37). One PFET with its gate grounded is the load; one NFET per input hangs in parallel from the output to ground. Adding an input adds one NFET and nothing in series.

The pseudo-NMOS NOR, redrawn from the board (Lecture17 @ 04:37). The PFET’s gate is grounded, so it is always on: a weak load. Any input at 1 turns its NFET on and pulls $Y$ low; with all inputs at 0, $Y$ is high. So $Y = \overline{a + b + c + d + e}$a+b+c+d+e​. The dots: another input is one more NFET in parallel, with nothing added in series.

The board (Lecture17 @ 03:46)

Lecture17 @ 03:46The recap and the static PLA: multi-level against structured control logic, SOP, the AND and OR planes, and pseudo-NMOS.

Fair copy of the board above (Lecture17 @ 03:46), mark for mark in its own layout. All black: a violet pen wrote the recap list, from “Multilevel” to “PLA”, and “random logic”; a pink pen wrote everything from “SOP (sum of products)” on. The pink writes the next topic rather than marking over the first, so it takes no accent. The NFETs have no gates yet, and the PFET is not yet ringed: both come by 04:37. The second and third NFETs, behind the lecturer’s hand here, are copied from 04:37. “AND pla” is the board’s shortened “AND plane”.

“The whole idea of doing these as NORs is that they can be arbitrarily wide … it uses pseudo-NMOS. Okay, so it’s ratioed logic” (03:01–03:25). All of the logic sits in the pull-downs. A static PLA is a pseudo-NMOS NOR plane feeding a pseudo-NMOS NOR plane, laid out as a grid (03:50–04:21); Section 3 builds one.

What pseudo-NMOS costs

The costs are Chapter 10’s added:

• The low is not ground. A low row or column sits at the level where the on NFETs and the always-on PFET balance. The NFETs must be clearly stronger than the PFET, or the next gate does not see a low.
• Static current. A row or column that is low draws current from $V_{DD}$ through its PFET the whole time it is low.
• A slow rise. The rising edge comes through the one weak PFET.

The lecture’s cure is the dynamic PLA (Section 7), which replaces each PFET load with a clocked precharge device. The name stays: “it’s an unfortunate name because it’s not static logic, it’s actually ratioed logic, but it’s still called a static PLA” (36:06–36:24).

A worked example: counting devices

added Count the devices of the example’s static PLA (its NOR forms are in Section 1, repeated here): rows $P_0 = \overline{\bar x_0 + \bar x_1}$xˉ0​+xˉ1​​, $P_1 = \overline{x_2}$x2​​, $P_2 = \overline{\bar x_0 + \bar x_1 + \bar x_2}$xˉ0​+xˉ1​+xˉ2​​, $P_3 = \overline{x_0 + \bar x_1}$x0​+xˉ1​​; columns $\bar f_0 = \overline{P_0 + P_1}$ and $\bar f_1 = \overline{P_1 + P_2 + P_3}$P1​+P2​+P3​​.

The example's static PLA, device by device

1. AND plane. One NFET per literal in each row: $2 + 1 + 3 + 2 = 8$ NFETs, and one PFET load per row, 4.
2. OR plane. One NFET per row a column uses: $2 + 3 = 5$ NFETs, and one PFET per column, 2.
3. Total. $8 + 4 + 5 + 2 = 19$ devices before the inverters; with the two output inverters, of two devices each, 23. (The three input inverters that make $\bar x_0$xˉ0​, $\bar x_1$xˉ1​, $\bar x_2$ add 6 more; they are not counted here.)
4. Against complementary CMOS. The widest row, $P_2$P2​, is a 3-input NOR: in pseudo-NMOS 4 devices, all but the load in parallel; in complementary CMOS 6, with 3 PFETs in series.

Traps.

• Calling the static PLA static logic. It is ratioed: non-rail lows and static current (36:06).
• A strong pull-up. A PFET load as strong as the NFETs lifts the low toward the middle of the swing (Chapter 10), and the next plane may read it as a 1.

Check yourself How many devices does a 6-input pseudo-NMOS NOR need, and a 6-input complementary CMOS NOR?

Pseudo-NMOS: 6 NFETs and 1 PFET, 7. Complementary: 6 NFETs and 6 series PFETs, 12.

Check yourself When does a static PLA row draw static current? On how many of the 8 input rows does the example's row P₀ (= x₀x₁) draw it?

A row draws current whenever it is low, that is, whenever one of its devices is on, which is whenever its product is false. $P_0 = x_0x_1$ is true on 2 of the 8 input rows (110 and 111), so it draws static current on the other 6.

3. Programming a PLA: the worked example

You need

The example in NOR form (Section 1). Rows $P_0 = \overline{\bar x_0 + \bar x_1} = x_0x_1$x0​x1​, $P_1 = \overline{x_2} = \bar x_2$xˉ2​, $P_2 = \overline{\bar x_0 + \bar x_1 + \bar x_2} = x_0x_1x_2$x0​x1​x2​, $P_3 = \overline{x_0 + \bar x_1} = \bar x_0x_1$xˉ0​x1​; columns $\bar f_0 = \overline{P_0 + P_1}$P0​+P1​​, $\bar f_1 = \overline{P_1 + P_2 + P_3}$P1​+P2​+P3​​, each followed by an inverter. A product is the NOR of its literals flipped.

From AND–OR to NOR–NOR (Section 1; Lecture16 @ 58:10, redrawn): panel (d) is the network this section lays out. Original figure ↑

One row is a pseudo-NMOS NOR (Section 2): a grounded-gate PFET load and one NFET per input, in parallel to ground. An NFET whose gate is 1 is on and pulls the row low.

The pseudo-NMOS NOR (Section 2; Lecture17 @ 04:37, redrawn). Original figure ↑

The question. Section 1 gave the network as gates. How is it laid out as a grid, and what does “programming” the grid mean?

The grid: literal lines, ground lines and rows

The lecture builds the grid step by step board (08:15–14:52).

The example’s static PLA, redrawn from the board (Lecture17 @ 14:52; the rows behind the lecturer from 12:08). Dashed lines are ground lines. AND plane (left): each row starts at a pseudo-NMOS pull-up; an NFET sits where a row crosses a literal line it needs, gate on the line, one terminal on the row and the other on the ground line beside it. OR plane (right): each column has a pull-up at the top and an NFET at each row it uses, gate on the row. The board’s columns end at $\bar f_0$fˉ​0​, $\bar f_1$fˉ​1​; the output inverters to $f_0$f0​, $f_1$ are added.

The board (Lecture17 @ 14:52)

Lecture17 @ 14:52The finished static PLA: the programmed AND plane, the OR plane (cyan) and the NOR–NOR equations for f̄₀ and f̄₁.

Fair copy of the board above (Lecture17 @ 14:52), mark for mark in its own layout. Black is the violet pen: the AND plane’s pull-ups, rows, literal lines and dashed ground lines, the row expressions, the bottom labels and the equations, with the ring round the right side of $\bar f_0$‘s equation. Orange is the pale cream pen: the AND plane’s eight devices with their dots, and the rows’ extensions into the OR plane. Teal is the cyan pen: the OR plane, its labels and the rings on $\bar f_0$ and $\bar f_1$fˉ​1​. The bars above $f_0$ and $f_1$ at the bottom are the columns’ end bars, so each column gives $\bar f$ (Section 3). The bottom labels, partly behind the papers in the lecturer’s hands here, are read on 14:07. The equation for $\bar f_1$ runs off the frame’s right edge and is copied to the edge.

Laying out the example (board, 08:15–14:52)

1. One row per product (08:15). Four horizontal lines, $P_0 \dots P_3$P0​…P3​, each with a pseudo-NMOS pull-up at its left end: a PFET from $V_{DD}$ with its gate grounded. The board writes each row’s NOR at its right end.
2. The literal lines (08:58–10:17). Vertical lines carry every literal, true and complement: $\bar x_0$xˉ0​, $x_0$x0​, $\bar x_1$xˉ1​, $x_1$x1​, $\bar x_2$xˉ2​, $x_2$ (the complements come from inverters at the bottom). Between each pair runs a ground line (dashed). Every row crosses every literal line, but a crossing does nothing until a transistor is put there.
3. Programming a crossing (10:23). To make a literal line an input of a row’s NOR, drop an NFET at the crossing: its gate on the literal line, one terminal on the row, the other on the neighbouring ground line. When the line is 1, the device is on and pulls the row low (the enlarged crossing, right after these steps).
4. Program each row from its NOR (10:23–12:08). $P_0 = \overline{\bar x_0 + \bar x_1}$xˉ0​+xˉ1​​: devices on the $\bar x_0$ and $\bar x_1$ lines. $P_1 = \overline{x_2}$x2​​: one device, on $x_2$ (a one-input NOR is an inverter, which makes $\bar x_2$xˉ2​; 10:57). $P_2$P2​: devices on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​, $\bar x_2$xˉ2​. $P_3 = \overline{x_0 + \bar x_1}$x0​+xˉ1​​: devices on $x_0$ and $\bar x_1$xˉ1​. The rule: a literal that appears true in the product gets its device on the complement line, and a complemented literal on the true line.
5. The OR plane (12:19–14:24). The rows run on to the right and cross two vertical output columns, each with its own pull-up at the top, and horizontal ground lines between the rows. Column $\bar f_0$ gets devices at $P_0$ and $P_1$P1​; column $\bar f_1$ at $P_1$P1​, $P_2$ and $P_3$P3​. Each device’s gate is on the row. Row $P_1$ feeds both columns: the shared product is built once.
6. The outputs added. Each column computes a NOR of its rows, the complement of its output: the board names them $\bar f_0$ and $\bar f_1$ (12:51). An inverter after each column gives $f_0$ and $f_1$f1​; the board stops at the columns.

One programmed crossing, enlarged added (row $P_3$‘s device on the $\bar x_1$ line, from the board at 14:52). The NFET’s gate sits on the literal line; its terminals connect to the row and to the ground line beside it. When its literal is 1 the device is on and pulls the row low (the arrow). Beside it, at the $x_1$ line, there is no device: the row and the line cross without connecting.

“The way I’ve drawn the schematic is basically going to be reflective of how this is going to be laid out” (11:54–12:19). The schematic is the floor plan: programming the PLA is choosing where transistors go in a fixed grid.

The two formulas, and the whole truth table

A row and a columnadded

$$\begin{aligned} P_k &= \overline{\textstyle\sum (\text{the lines its devices sit on})} \\ \bar f_j &= \overline{\textstyle\sum (\text{the rows column } j \text{ uses})} \end{aligned}$$

Holds when: a PLA whose rows and columns are NORs (pseudo-NMOS or, after both planes have evaluated, dynamic); a device's literal is the line its gate sits on

Memorize or derive. Derive: both are Section 1’s NOR read off the grid. A row’s devices sit on the complements of its literals, so the NOR of those lines is the AND of the literals.

A worked example: the board’s PLA, evaluated. Every row and both outputs for all eight inputs added, rows written $x_0x_1x_2$x0​x1​x2​:

$x_0x_1x_2$	$P_0$	$P_1$	$P_2$	$P_3$	$\bar f_0$	$\bar f_1$	$f_0$	$f_1$
000	0	1	0	0	0	0	1	1
001	0	0	0	0	1	1	0	0
010	0	1	0	1	0	0	1	1
011	0	0	0	1	1	0	0	1
100	0	1	0	0	0	0	1	1
101	0	0	0	0	1	1	0	0
110	1	1	0	0	0	0	1	1
111	1	0	1	0	0	0	1	1

One input row through the grid: x0x1x2 = 011

1. The literal lines. $x_0 = 0$0, $\bar x_0 = 1$1; $x_1 = 1$1, $\bar x_1 = 0$0; $x_2 = 1$1, $\bar x_2 = 0$0.
2. Row $P_0$ has devices on $\bar x_0$ and $\bar x_1$xˉ1​. $\bar x_0 = 1$ turns one on, so the row is pulled low: $P_0 = 0$0.
3. Row $P_1$ has its device on $x_2 = 1$1: on, $P_1 = 0$0. Row $P_2$P2​: its $\bar x_0$ device is on, $P_2 = 0$0.
4. Row $P_3$ has devices on $x_0 = 0$ and $\bar x_1 = 0$0: both off, so the pull-up holds the row high, $P_3 = 1$1.
5. The columns. $\bar f_0$ uses $P_0$ and $P_1$P1​, both 0, so no device is on: $\bar f_0 = 1$ and $f_0 = 0$0. $\bar f_1$ uses $P_1$P1​, $P_2$P2​, $P_3$P3​; $P_3 = 1$ turns its device on: $\bar f_1 = 0$ and $f_1 = 1$1.
6. Check against the functions. $f_0 = x_0x_1 + \bar x_2 = 0 + 0 = 0$ and $f_1 = x_0x_1x_2 + \bar x_2 + \bar x_0x_1 = 0 + 0 + 1 = 1$1. They agree.

Traps.

• The device on the true line for a true literal. A row with devices on $x_0$ and $x_1$ computes $\overline{x_0 + x_1} = \bar x_0\bar x_1$xˉ0​xˉ1​: the product of the complements.

Check yourself Row P₃ computes x̄₀x₁. On which literal lines are its devices?

On $x_0$ and $\bar x_1$xˉ1​: each literal’s device sits on its complement’s line, so the row is $\overline{x_0 + \bar x_1} = \bar x_0x_1$xˉ0​x1​.

Check yourself Add a third output f₂ = x̄₂ + x̄₀x₁. Does the AND plane change? How many devices are added, and where?

No new row: both products already exist ($P_1$P1​ and $P_3$P3​). Add a third OR-plane column with NFETs at rows $P_1$ and $P_3$P3​, a pull-up PFET at its top and an output inverter: $2 + 1 + 2 =$ 5 devices.

4. Reading a PLA back to its functions

You need

A programmed crossing (Section 3). An NFET with its gate on a literal line and its terminals on the row and on a ground line. It is on when its literal is 1, and an on device pulls its row (or column) low. A crossing without a device does nothing.

One programmed crossing (Section 3): the gate’s line is the literal. Original figure ↑

Rows and columns are NORs (Section 3). A row is the NOR of the lines its devices sit on; a column is the NOR of the rows it has devices at:

$$\begin{aligned} P_k &= \overline{\textstyle\sum (\text{its device lines})} \\ \bar f_j &= \overline{\textstyle\sum (\text{its rows})} \end{aligned}$$

A NOR of complemented literals is the AND of the literals (De Morgan), so a row with devices on $\bar x_0$ and $\bar x_1$ is $x_0x_1$x0​x1​.

The question. The lecture only builds PLAs from their functions. Both PLA questions on the past finals run the other way: here are the transistors, what are the outputs? What is the routine for reading a PLA, and where does it go wrong?

The routine

added Three steps, and two decisions that carry the marks: which line each device’s gate sits on, and whether the paper draws output inverters.

Reading a PLA

1. Rows. For each row, list the lines its devices’ gates sit on. Flip each line’s literal, and AND them: devices on $x_0$ and $\bar x_1$ give $\bar x_0x_1$xˉ0​x1​; one device on $x_2$ gives $\bar x_2$xˉ2​. (The row is the NOR of those lines, and De Morgan turns a NOR of lines into the AND of their complements.)
2. Columns. Each column is the NOR of the rows it uses. If an inverter follows, the output is the OR of those rows. If not, it is the complement of that OR: simplify it with De Morgan.
3. Simplify and check. Simplify each output, then check two input rows by tracing them through the grid (Section 3’s walk), not through your formula.

A dynamic PLA (Section 7) is read the same way: once both planes have evaluated, each row and each column holds the NOR of its inputs.

The board’s PLA, read backwards

Take Section 3’s PLA as if it were an exam’s figure, with nothing said about its functions.

The example’s static PLA (Section 3; Lecture17 @ 14:52, redrawn): read its devices, not its labels. Original figure ↑

Reading the example's PLA (added)

1. Row $P_0$P0​: devices on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​. Flip and AND: $x_0x_1$x0​x1​.
2. Row $P_1$P1​: one device, on $x_2$x2​: $\bar x_2$xˉ2​.
3. Row $P_2$P2​: devices on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​, $\bar x_2$xˉ2​: $x_0x_1x_2$x0​x1​x2​.
4. Row $P_3$P3​: devices on $x_0$x0​, $\bar x_1$xˉ1​: $\bar x_0x_1$xˉ0​x1​.
5. Columns, with the inverters. Column 1 uses $P_0$ and $P_1$P1​: $f_0 = x_0x_1 + \bar x_2$xˉ2​. Column 2 uses $P_1$P1​, $P_2$P2​, $P_3$P3​: $f_1 = x_0x_1x_2 + \bar x_2 + \bar x_0x_1$xˉ0​x1​.
6. Simplify $f_1$ added. Split on $x_2$x2​. If $x_2 = 0$0, $\bar x_2 = 1$ and $f_1 = 1$1. If $x_2 = 1$1, $f_1 = x_0x_1 + \bar x_0x_1 = x_1$x1​. So $f_1 = \bar x_2 + x_1$x1​: it is 1 when $x_2 = 0$ or $x_1 = 1$1. (This takes three products in place of four; Section 5 uses it.)
7. The same grid without inverters. Each output is the column’s own NOR: $y_0 = \overline{x_0x_1 + \bar x_2} = \overline{x_0x_1}\cdot x_2 = x_2(\bar x_0 + \bar x_1)$ and $y_1 = \overline{x_1 + \bar x_2} = \bar x_1x_2$xˉ1​x2​.
8. Check two input rows by tracing. 011: from Section 3’s walk, $\bar f_0 = 1$ and $\bar f_1 = 0$0, so $f_0 = 0$0, $f_1 = 1$1; the formulas give $x_0x_1 + \bar x_2 = 0$ and $x_1 + \bar x_2 = 1$1. 101: every row is pulled low ($P_0$P0​ by $\bar x_1 = 1$1, $P_1$ by $x_2$x2​, $P_2$ by $\bar x_1$xˉ1​, $P_3$ by $x_0$x0​), so both columns are high and $f_0 = f_1 = 0$0; the formulas give $0 + 0 = 0$ and $0 + 0 = 0$0. Without inverters, 101 gives $y_0 = y_1 = 1$1, and $x_2(\bar x_0 + \bar x_1) = 1$1, $\bar x_1x_2 = 1$1.

The truth tables added, rows $x_0x_1x_2 = 000 \dots 111$000…111:

	000	001	010	011	100	101	110	111
$f_0 = x_0x_1 + \bar x_2$	1	0	1	0	1	0	1	1
$f_1 = x_1 + \bar x_2$	1	0	1	1	1	0	1	1
$y_0 = x_2(\bar x_0 + \bar x_1)$ (no inverter)	0	1	0	1	0	1	0	0
$y_1 = \bar x_1x_2$ (no inverter)	0	1	0	0	0	1	0	0

Traps.

• Reading a device by its terminals. The literal is the line its gate sits on. Its terminals touch the row and a ground line, never another literal line.
• Reading through a missing inverter. If the paper’s columns run straight to the outputs, the outputs are complements of the sums. Look for the inverter before writing anything.
• Stopping at an unsimplified form when the question asks for “the function”. An unsimplified sum is correct, but simplify it, and check that the two forms agree on every input row.

A PLA to read added, in the style of the example’s. Dashed lines are ground lines. The rows carry no expressions: find them from the devices. The column ends at $z$ with no output inverter.

Check yourself The PLA in the figure has rows Q₀ (devices on x₀ and x₁) and Q₁ (devices on x̄₀ and x₂), and one column z using both, with no inverter. What is z, and what is its truth table for x₀x₁x₂ = 000 … 111?

$Q_0 = \overline{x_0 + x_1} = \bar x_0\bar x_1$ and $Q_1 = \overline{\bar x_0 + x_2} = x_0\bar x_2$x0​xˉ2​. With no inverter, $z = \overline{Q_0 + Q_1} = \overline{\bar x_0\bar x_1 + x_0\bar x_2}$xˉ0​xˉ1​+x0​xˉ2​​. For $x_0 = 0$ this is $\overline{\bar x_1} = x_1$x1​; for $x_0 = 1$ it is $\overline{\bar x_2} = x_2$x2​. So $z = \bar x_0x_1 + x_0x_2$x0​x2​, with truth table 0, 0, 1, 1, 0, 1, 0, 1.

Check yourself Put an inverter after the same column. What is the output now, and on how many of the eight input rows is it 1?

The inverter undoes the column’s NOR, so the output is the OR of the rows: $\bar x_0\bar x_1 + x_0\bar x_2$x0​xˉ2​. It is the complement of $z$‘s table, 1, 1, 0, 0, 1, 0, 1, 0: 4 rows (000, 001, 100, 110).

Remember. The two past-final PLAs are this chapter’s example. FN12-10a draws its first three rows, static, with output inverters (there $f_1 = \bar x_2 + x_0x_1x_2$ simplifies to $f_0$ itself, a ready case of the simplify trap); FN19-6a draws all four rows, dynamic, without them. The datapath practice page (FD1) solves both.

5. Fewer product terms: Espresso and its table

You need

A PLA’s rows are its products (Section 3). Each distinct product term is one AND-plane row, used by every output column that needs it. So the PLA’s height is its number of distinct products.

The example’s PLA (Section 3; Lecture17 @ 14:52, redrawn): four rows, one per product. Original figure ↑

Implicants added. A product is an implicant of a function if it is 1 only on input rows where the function is 1. A sum of products is the function exactly when its products are implicants and together cover every 1.

The device rule (Section 3): a literal that appears true in a product has its device on the complement line; a complemented literal, on the true line.

The question. Fewer products means fewer rows, a smaller and faster PLA. How do we find a small set of products, shared between the outputs, and how does a tool take the functions in?

Minimizing is hard; Espresso does it well

“The optimization to try to minimize the number of product terms is an NP-complete problem, as most interesting problems are in CAD” (15:24–15:59). The tool used in the course’s problem sets is Espresso board, a heuristic two-level minimizer: its result is “not provably minimum, but in practice minimum” (16:30–17:03). It also maximizes sharing: one product used by several outputs costs one row.

The table format

Espresso reads a table board (17:09–20:25): one line per product, with an AND part and an OR part.

• AND part, one column per input: 1 if the literal appears true, 0 if it appears complemented, – if the input is absent from the product.
• OR part, one column per output: 1 if the output uses the product.

The example’s table, as the board writes it:

$x_0$	$x_1$	$x_2$	$f_0$	$f_1$	product
1	1	–	1	0	$x_0x_1$
–	–	0	1	1	$\bar x_2$
1	1	1	0	1	$x_0x_1x_2$
0	1	–	0	1	$\bar x_0x_1$

The board’s speech says the OR part has “a one if I use that literal” (19:01): a slip for product term; the 1s choose products.

The Espresso table and what it programs. Top left: the example’s table, from the board (Lecture17 @ 20:25). Top right added: the example minimized by hand to three products (this section’s worked example). Bottom added: the first line, 1 1 –, as the PLA row $P_0$P0​: each 1 puts a device on the literal’s complement line, and the – leaves $x_2$‘s pair empty, so the row computes $x_0x_1$x0​x1​.

The board (Lecture17 @ 21:05)

Lecture17 @ 21:05The example as an Espresso table, and the arrow to Espresso.

Fair copy of the board above (Lecture17 @ 21:05), mark for mark in its own layout. Black is the violet pen: the table and its arrows, the equations, and “espresso”, boxed and double-underlined, with the arrow into it. Teal is the cyan pen’s rings on $\bar f_0$ and $\bar f_1$fˉ​1​, left from 14:52: the planes are wiped, and the equations are unchanged and copied as at 14:52. The short strokes under the header, the lone 1 right of the first row, the stroke right of the last row and the corner marks under it are copied as they stand. The lecturer stands in front of the table’s middle; every digit shows through, and 20:25, where he stands clear, has the same ink.

From a table line to a PLA row, and back (added)

1. AND part to devices. A 1 in column $x_i$ means the product contains $x_i$xi​, so its device goes on the $\bar x_i$ line; a 0 means it contains $\bar x_i$xˉi​, device on the $x_i$ line; a – means no device on either. Line 1, 1 1 –: devices on $\bar x_0$ and $\bar x_1$xˉ1​, which is row $P_0$ of Section 3.
2. OR part to columns. Line 2, – – 0 | 1 1: the product $\bar x_2$ (device on the $x_2$ line), used by both outputs, so both columns get a device at that row.
3. Backwards. A row with devices on $x_0$ and $\bar x_1$ is $\bar x_0x_1$xˉ0​x1​: code 0 1 –.

Espresso returns a table with fewer lines that keeps every output the same (19:40–20:11). The lecturer adds a remark about colleagues earlier in his career (at IBM, 35:31) who wanted all logic written in table formats (20:17–20:57). The idea did not catch on, but RTL code reduces to these tables, as Section 6 shows.

A worked example: three products instead of four

added Minimize the example by hand. (The lecture says Espresso would hand this table back unchanged; for this function it can be cut, as follows.)

Cutting the example to three rows

1. $f_0$ alone. $f_0 = x_0x_1 + \bar x_2$xˉ2​: two products, and neither can be dropped. $x_0x_1$ alone misses rows 000, 010, 100, where $\bar x_2 = 1$1; $\bar x_2$ alone misses 111.
2. $f_1$ alone. Section 4 found $f_1 = x_0x_1x_2 + \bar x_2 + \bar x_0x_1 = x_1 + \bar x_2$xˉ2​: two products. The single literal $x_1$x1​, code – 1 –, is an implicant of $f_1$ (every row with $x_1 = 1$ has $f_1 = 1$1) and covers both $x_0x_1x_2$ and $\bar x_0x_1$xˉ0​x1​.
3. Share. $\bar x_2$ serves both outputs. The cover $\{x_0x_1,\ \bar x_2,\ x_1\}$ is three rows: $f_0$ uses the first two, $f_1$ the last two. The table: 1 1 – | 1 0, – – 0 | 1 1, – 1 – | 0 1.
4. Can two rows do it? An exhaustive search over all 27 products of three inputs (in the test) finds no two-product cover and eight different three-product covers. Three is the minimum. One of the eight, $\{x_0x_1x_2,\ \bar x_0x_1,\ \bar x_2\}${x0​x1​x2​, xˉ0​x1​, xˉ2​}, is the board’s own table without its first line ($f_0$f0​ takes $x_0x_1x_2$ in place of $x_0x_1$x0​x1​), so the board’s four rows were never the minimum.
5. Check on all eight inputs. The new table gives $f_0$ = 1, 0, 1, 0, 1, 0, 1, 1 and $f_1$ = 1, 0, 1, 1, 1, 0, 1, 1, the same as the four-row PLA (Section 4’s table).

Rows of the PLA = distinct products in the cover. Memorize this: a product shared by two outputs is one row.

Traps.

• Writing the code as the device’s line. Code 1 means the literal is true, and its device sits on the complement line.
• Minimizing each output alone and stacking the results. $f_0$ and $f_1$ each need two products, four in all; shared, $\bar x_2$ counts once, three in all.
• Calling Espresso’s answer the proven minimum. It is a heuristic; for small functions an exhaustive search (or a Karnaugh map) proves the minimum.

Check yourself Write the table line for the product x̄₀x₂, used by f₁ only.

0 – 1 | 0 1: $x_0$ complemented (0), $x_1$ absent (–), $x_2$ true (1); only $f_1$ uses it.

Check yourself A table has the lines 1 – 0 | 1 0 and 1 – 1 | 1 0. Merge them, and say how many PLA rows you save.

The two products are $x_0\bar x_2$ and $x_0x_2$x0​x2​, used by the same output; their sum is $x_0(\bar x_2 + x_2) = x_0$x0​, the line 1 – – | 1 0. One row instead of two: one row saved.

6. Background for the final: from VHDL to a table

You need

A state machine (Chapter 13 §1 and §9). A flip-flop holds the current state cs. Combinational logic computes the next state ns and the outputs from cs and the inputs. At each rising clock edge the flip-flop loads ns into cs.

Synchronous design (Chapter 13, panel a): logic between flip-flops on one clock. Original figure ↗

Espresso’s table (Section 5): one line per product, 1/0/– in the input part, 1 for each output that uses the product.

The question. No past final asks about VHDL; this section is background. How does the description of a controller in a hardware language turn into a table that Espresso, and then a PLA, can take?

The lecture’s controller is the traffic light of Mead and Conway’s textbook board (22:17–27:19): a highway crossing a farm road, with a sensor on the farm road. Its outputs are two bits for each light, hl1, hl0 (highway) and fl1, fl0 (farm road), and st, which starts a timer. Its inputs are cars (the sensor) and short and long, which the timer raises after a short and a longer wait. A two-bit state register holds the state: HG = 00, HY = 01, FY = 10, FG = 11 (highway green, highway yellow, farm road yellow, farm road green).

The traffic-light controller, redrawn from the board (Lecture17 @ 35:01). Left: the highway (horizontal) and the farm road (vertical), with the car sensors on the farm road (the board draws two dots), and the state codes under it. Right: the combinational logic, which a PLA can implement, computes the lights, st and the next state ns from cars, short, long and the current state cs; the flip-flop loads ns into cs at each clock edge. The state codes are the board’s: highway green, highway yellow, farm road yellow and farm road green.

The board (Lecture17 @ 35:01)

Lecture17 @ 35:01The controller's specification and the first five lines of its table.

Fair copy of the board above (Lecture17 @ 35:01), mark for mark in its own layout. One pen (cyan) wrote the whole board, copied in black. The last header, ns(1), runs off the frame’s right edge and is cut there as the frame shows it. The table’s rows and the text lines are set level (the board’s rows drift down to the right). The board writes the zeros of hl∅ and Fl∅ slashed, and the F of Fl∅ and of the Fl1, Fl0 headers as a capital; both are copied as written.

The VHDL (spoken, 27:27–29:03; the handout itself is not among this guide’s sources). An entity lists the ports. A clocked process, with the test if clk = '1' and not clk'stable (a rising edge), is the state flip-flop. A combinational process first gives every output a default (ns = cs, the lights and st at 0), then a case on the current state with if branches on the inputs.

Into a table board (29:03–35:01). Each if branch becomes a product term: its conditions on the inputs and the state are the AND part, and the outputs it sets (with the defaults for the rest) are the OR part. The board writes the rows for HG and HY, twelve columns in the order short, long, cars, cs(0), cs(1) | hl1, hl0, fl1, fl0, st, ns(0), ns(1). Here they are grouped by signal, each group’s bits in the board’s order:

short long cars	cs(0) cs(1)	hl1 hl0	fl1 fl0	st	ns(0) ns(1)
– 1 1	0 0	0 0	0 1	1	0 1
– 0 –	0 0	0 0	0 1	0	0 0
– – 0	0 0	0 0	0 1	0	0 0
1 – –	0 1	1 0	0 1	1	1 1
0 – –	0 1	1 0	0 1	0	0 1

Read the first three in words. In HG (cs = 00), “if cars and long”: a car waits and the highway has had its minimum green, so start the timer and go to HY (ns = 01). Otherwise stay in HG. That else is “not cars or not long”, a sum of two products, so it takes two lines: long = 0, and cars = 0. The light bits in HG are hl = 00 and fl = 01; in HY the highway’s turns to hl = 10 (codes inferred from these two states). The rest is “an exercise” (35:02): RTL → table → Espresso → PLA, the path CAD tools once followed automatically (35:02–35:31).

Trap. Forgetting the defaults. A branch that does not assign st leaves it at its default, 0 (32:52–33:28), so its line has st = 0, not “don’t care”.

Check yourself Why does the else after “if cars and long” take two table lines, and what are their AND parts?

Its condition is the complement of cars·long, which by De Morgan is $\overline{\text{cars}} + \overline{\text{long}}$long​, a sum of two products. One line per product: long = 0 (– 0 – 0 0) and cars = 0 (– – 0 0 0). They overlap where both are 0, which is harmless: both lines set the same outputs.

7. The dynamic PLA and its race

You need

Precharge and evaluate (Chapter 11 §4). A dynamic gate has a clocked PFET from $V_{DD}$ to its output node (the precharge device), its NFET network below, and a clocked NFET foot to ground. Clock low: the PFET is on and the foot off, so the node charges high. Clock high: the PFET is off and the foot on, so the node falls if the network conducts, and otherwise floats high. A node that has fallen cannot rise again until the next precharge.

The dynamic gate with its precharge device and foot (Chapter 11, Lecture11 @ 20:18). Original figure ↗

The race (Chapter 11 §5). A dynamic gate’s output is high during precharge. A second dynamic gate driven by it therefore sees a 1 at the start of evaluate, whatever the first gate’s answer will be, and may discharge for good before the first gate falls. Domino cures it with an inverter after each dynamic gate, so that every input starts at 0.

The race between two dynamic gates, and domino’s inverter (Chapter 11, Lecture11 @ 30:38). Original figure ↗

The static PLA (Sections 2–3): rows and columns are pseudo-NMOS NORs, each with a grounded-gate PFET load.

The question. The static PLA’s loads burn static current and give lows above ground. Can each plane be made dynamic, and what goes wrong when one dynamic NOR plane drives another?

Clocking the planes

board (37:02–37:47). Take each pseudo-NMOS load and connect its gate to a clock: “make this the clock” (37:37). It becomes a precharge PFET. Add a clocked NFET foot under each row’s devices and under each column’s. Now each plane precharges while its clock is low and evaluates while it is high, draws no static current and pulls its lows all the way to ground.

One row of a dynamic PLA feeding one column, redrawn from the board (Lecture17 @ 43:07; first drawn at 37:47 with one clock, the frame folded in Section 8’s figure). Each plane’s precharge PFET and its foot share that plane’s clock: $\phi_{\mathrm{AND}}$ for the AND row, $\phi_{\mathrm{OR}}$ for the OR column. Clock low: precharge; clock high: evaluate. The row’s output drives an NFET gate in the column.

One clock on both planes: the race

The first drawing clocks both planes with the same clk (37:47). Then: “I’m gonna have the classic race condition … that caused us to actually go to domino logic and put an inverter here” (38:03). At the start of evaluate every row is still at its precharged high. Every OR-plane device is therefore on, so every column that has any device starts to discharge, whatever the inputs. A row whose product is false falls only after its own evaluate delay, and by then its column may have lost its charge for good. A NOR plane after a NOR plane has no inverter between them to cure this, and an inverter would break the NOR–NOR form.

The race with one clock on both planes added (a sketch of the lecture’s words at 37:51–38:29). When clk rises, a row $P$ whose product is false starts to fall, but it is still high for its whole evaluate delay ($t_{eval}$teval​, the bracket). The column $\bar f$ that it drives is evaluating at the same time, sees the row high, and discharges: a wrong 0 (✗) where the right value (dashed, ✓) is 1. The column cannot recover until the next precharge.

A worked example added. Take the example’s PLA, dynamic, with no output inverters (the form FN19-6 prints), so the outputs are the columns: $y_0 = x_2(\bar x_0 + \bar x_1)$ and $y_1 = \bar x_1x_2$ (Section 4).

What one shared clock does to the example

1. At the start of evaluate, rows $P_0 \dots P_3$ are all high, so both columns’ devices are on and both columns start to fall.
2. In the worst case (a column that discharges faster than its false rows fall), then, $y_0 = y_1 = 0$ at the end of evaluate, for every input.
3. Count the errors. The correct $y_0$ is 1 on 3 of the 8 input rows (001, 011, 101) and $y_1$ on 2 (001, 101). Those are exactly the wrong outputs; every correct 0 is right by luck.
4. The error is one-way. A precharged column can only fall during evaluate, so the race can only turn a correct 1 of the column into a 0 (with an output inverter: a correct 0 of the output into a 1).

The cure: two clocks, and the two requirements

The cure the lecture gives keeps the NOR–NOR form and clocks the two planes separately, by φ_AND and φ_OR board (38:29–38:43; labelled on the board’s circuit at 41:41). They must meet two requirements (40:06–41:53):

1. Enough precharge time. φ_AND’s low pulse must last long enough to precharge the slowest AND row, and φ_OR’s low time long enough to precharge the OR plane.
2. The OR plane waits. φ_OR must not rise (start the OR plane’s evaluate) until the slowest AND row has finished evaluating after φ_AND rose.

The dynamic PLA's two clock requirementsadded

$$\begin{aligned} t_{\phi_{\mathrm{AND}}\ \mathrm{low}} &\ge t_{pre} \\ t(\phi_{\mathrm{OR}}\!\uparrow) &\ge t(\phi_{\mathrm{AND}}\!\uparrow) + t_{eval} \end{aligned}$$

and φ_OR’s low time covers the OR plane’s precharge.

Holds when: each plane precharges while its clock is low and evaluates while it is high; t_pre and t_eval are the slowest AND row's precharge and evaluate times (the lecture states the requirements in words, 40:06–41:53; the symbols are the guide's)

Memorize or derive. Memorize the two requirements in words; Section 8 shows why neither can be a fixed time, and Section 9 builds clocks that meet both.

Traps.

• “A slower OR plane cures it.” Any overlap of the OR plane’s evaluate with a row that is still high can discharge a column for good; only waiting cures it.
• The polarity. Precharge is clock low (the PFET on, the foot off); evaluate is clock high.
• Domino’s cure. An inverter between the planes would cure the race, but the planes are then no longer NOR into NOR.

Check yourself Which output values can the race corrupt in a PLA without output inverters: 0s or 1s? Why only those?

Only 1s. A column is precharged high and can only fall during evaluate, so the race can only discharge a column that should have stayed high. A column that should be 0 falls anyway.

Check yourself The slowest AND row takes 200 ps to fall through one device, but φ_OR rises only 150 ps after φ_AND. Which columns can go wrong, for how long is the danger open, and which way?

A column that should stay high (all of its rows false) but uses a row that is still falling: for up to $200 - 150 = 50$ ps that row is still high while the OR plane evaluates, its device is on, and the column can discharge to a wrong 0. Without an output inverter the output is a wrong 0; with one, a wrong 1. Requirement 2 is broken by 50 ps.

8. Two clocks with self-timed edges

You need

The two requirements (Section 7). Each plane precharges while its clock is low and evaluates while it is high. (1) φ_AND’s low pulse must be at least the slowest AND row’s precharge time $t_{pre}$tpre​, and φ_OR’s low time must cover the OR plane’s precharge. (2) φ_OR may rise only after the slowest AND row has evaluated, $t_{eval}$ after φ_AND rose.

Synchronous design (Chapter 13 §1): only clock edges trigger events, and every delay is checked against the clock period.

Synchronous (a) against asynchronous (b) sequencing (Chapter 13). Original figure ↗

The clock chopper (Chapter 14 §5): a NOR (or NAND) of a clock and a delayed, inverted copy of it makes one pulse a cycle, as wide as the delay: after each falling edge for the NOR, a low pulse at each rising edge for the NAND. Only one edge of the pulse is the clock’s; the other waits for the delay.

The NOR clock chopper (Chapter 14): the pulse width is the inverter delay. Original figure ↗

The question. How long is “long enough to precharge” and “after the slowest row has evaluated”? Both depend on the circuit’s own delays, which change from chip to chip and with the supply and the temperature. How can a clock edge follow them?

φ_AND: falls with the clock, rises when the rows are precharged

board (38:56–40:27). φ_AND falls at clk’s rising edge (the board’s curved arrow), which starts the AND plane’s precharge. Its rising edge is self-timed: it comes “just enough” later for the rows to precharge, and then the AND plane evaluates for the rest of the cycle. The delay is made by a replica: “a replica is a copy, just what it says, a replica of the circuit that I’m trying to estimate the delay for, that PVT tracks that circuit” (39:39). Laid out like the real rows, it slows down and speeds up with them at every corner of PVT: process, voltage and temperature.

φ_OR: rises when the rows have evaluated

board (40:44–41:53). φ_OR’s rising edge is timed from φ_AND’s rising edge, again self-timed, by a replica of the slowest row’s evaluate. So the OR plane starts to evaluate only after every AND row has settled: requirement 2.

The two clocks of the dynamic PLA, redrawn from the board (Lecture17 @ 43:07, uncovered at 41:41 and 50:10). φ_AND falls at clk’s rising edge and rises a replica precharge later ($t_{pre}$tpre​, self-timed). φ_OR rises a replica evaluate after φ_AND rises ($t_{eval}$teval​, self-timed). Each plane precharges (pre) while its clock is low and evaluates (eval) while it is high. The board draws φ_OR falling at clk’s rising edge together with φ_AND; the board’s own generator (Section 9) makes it fall a replica precharge after φ_AND falls, and the redraw follows the generator.

The board (Lecture17 @ 43:07)

Lecture17 @ 43:07The dynamic PLA's two clocks: self-timed edges, a replica that tracks PVT, and 'asynchronous'.

Fair copy of the board above (Lecture17 @ 43:07), mark for mark in its own layout. One pale pen drew the whole board (the edge light tints it violet at the left and peach at the right), copied in black. The clock labels marked † are written over the “clk” labels of the first drawing (37:47); they read φ_AND and φ_OR, and the leftover strokes of “clk” are left out. The precharge devices are copied as drawn: the AND row’s without a bubble, the OR column’s with the bubble of its first gate lead. As on the board, φ_OR falls at clk’s rising edge together with φ_AND; the generator of Section 9 makes it fall a replica precharge later, as the redraw above shows. The waveforms are set level (on the board they drift down to the right), and the last clk fall trails off as drawn. The lecturer stands behind the waveforms, which show over him: nothing is restored (41:41 and 44:03 show the same strokes).

Self-timing is asynchronous

board (42:06–43:07; the board writes “asynchronous” and underlines it). The numbers for these edges come in Section 9’s worked example: φ_AND low from 30 to 220 ps and φ_OR from 200 to 440 ps, with example delays. “This is an asynchronous technique, because in synchronous design … the only thing that triggers anything is the clock” (42:10–42:41). Here a signal edge (the replica finishing) triggers a clock edge, and the delays involved “have nothing to do with the clock”. That is what lets the edges track the circuit, and it is also the risk: nothing is checked against a clock period, so the replica must be verified at every PVT corner.

φ_OR’s falling edge added is a replica’s too: a replica precharge after φ_AND falls, as the figure’s caption says (the board draws it at clk↑).

The edges of the self-timed clocksadded

$$\begin{aligned} \phi_{\mathrm{AND}}\!\downarrow &: \ \text{at clk}\!\uparrow + \,t_{NAND} \\ \phi_{\mathrm{AND}}\!\uparrow &: \ \text{a replica precharge later} \\ \phi_{\mathrm{OR}}\!\uparrow &: \ \text{a replica evaluate after } \phi_{\mathrm{AND}}\!\uparrow \\ \phi_{\mathrm{OR}}\!\downarrow &: \ \text{a replica precharge after } \phi_{\mathrm{AND}}\!\downarrow \end{aligned}$$

Holds when: the lecture's generators (Section 9): t_NAND, t_inv are gate delays; t_pre and t_eval are the replica rows' precharge and evaluate; clk rises at 0

Memorize or derive. Derive the edges from the generators, as Section 9 does; what to memorize is which edge belongs to the clock (only φ_AND’s fall) and which to a replica (the other three).

Traps.

• φ_AND as a delayed copy of clk. Only its rising edge waits; it falls at once, the shape of Chapter 14’s chopper.
• A replica of a typical row. It must copy the slowest row, or the real rows fail at some corner.
• A fixed delay instead of a replica. An inverter chain tuned at one corner need not track the rows’ capacitance and devices at another.

Check yourself Which edges of φ_AND and φ_OR are set by the clock, and which by a replica?

Only φ_AND’s falling edge is the clock’s (clk rising, through the NAND). φ_AND’s rise waits for a replica’s precharge, φ_OR’s rise for a replica’s evaluate, and φ_OR’s fall for a replica’s precharge after φ_AND falls.

Check yourself The chip runs hot and every circuit delay grows. What happens to φ_AND's low pulse if it is made by a replica row, and if it is made by a fixed inverter chain that matched the rows at room temperature?

With a replica, the pulse grows with the replica’s precharge, which grows like the real rows’ (same devices, same layout, same capacitance), so the rows still finish precharging. With an inverter chain, the pulse grows with the inverters, whose delay need not scale like a row’s precharge through its PFET and wire; if the rows slow down more, the pulse ends before they are precharged, and requirement 1 fails.

9. Generating φ_AND and φ_OR with replica rows

You need

A NAND is 0 only when both inputs are 1. An inverter, or a bubble at a gate input, flips its signal after a delay $t_{inv}$tinv​.

A dynamic row clocked by a signal $u$ (Section 7). While $u$ is low it precharges, rising after $t_{pre}$tpre​; when $u$ rises it evaluates, falling after $t_{eval}$ if any of its devices is on. The slowest precharge is the row with the most capacitance; the slowest evaluate is a row with only one device on.

The edges to produce (Section 8): φ_AND falls at clk↑ and rises a replica precharge later; φ_OR rises a replica evaluate after φ_AND rises.

The two clocks (Section 8; Lecture17 @ 43:07, redrawn). Original figure ↑

The question. What circuits make these edges? The lecture draws two, and FN19-6b prints the same two and asks for the replica row inside them.

The φ_AND generator

board (43:41–45:31). clk goes straight to one input of a NAND. It also goes through an inverter to a dummy AND row (the board’s name; a replica), clocked by $\overline{\mathrm{clk}}$clk. The dummy row’s output $R_1$ enters the NAND’s other input through a bubble. The NAND’s output is φ_AND.

The φ_AND generator, redrawn from the board (Lecture17 @ 50:10; FN19-6b prints the same circuit). Top: clk into a NAND directly, and through an inverter into the dummy row $R_1$ (clocked by $\overline{\mathrm{clk}}$clk), whose output enters the NAND through a bubble. Bottom added: clk, φ_AND, $R_1$ and $\overline{\mathrm{clk}}$clk, with the worked example’s delays in proportion. When clk rises the NAND falls (φ_AND↓); $R_1$ precharges on $\overline{\mathrm{clk}}$ low, and once it is high the bubbled input drops and φ_AND rises ($t_{pre}$tpre​).

The board (Lecture17 @ 50:10)

Lecture17 @ 50:10The two generators: φ_AND from a NAND and a dummy AND row (slowest precharge); φ_OR from a dummy row and an inverter; the dummy rows' gates 1, 1, 1 and 1, 0, 0.

Fair copy of the board above (Lecture17 @ 50:10), mark for mark in its own layout. Black is the pale pen: the 43:07 board, as in its fair copy, with the ring now drawn round PVT. Teal is the cyan pen: the rings on “replica” and φ_OR, two marks through the waveforms at the first rising edges of φ_AND and φ_OR, and both generators. At the top, the φ_OR generator: φ_AND through an AND row clocked by clk and an inverter, with that row’s dummy (gates 1, 0, 0). Below it, the φ_AND generator, with clk into a NAND directly and through an inverter to “Dummy AND” (“Slowest precharge”), and the dummy row it points to (gates 1, 1, 1). The middle of the “AND row” box and the upper dummy row are under the lecturer’s hand here and are copied from 49:25. That row’s middle gate digit is written over (†); the speech (49:09, “set only one of these to a one”) makes it 0. The small mark under the NAND’s input is copied as drawn; it is not read in the lecture. The board’s inverters, drawn as small D shapes, are set as triangles.

The NAND-and-replica generator, one cycle (board, 44:20–45:31)

1. Before clk rises. clk has been low, so $\overline{\mathrm{clk}}$ is high and the dummy row has evaluated: its inputs are on, so $R_1$ is low and the bubbled NAND input is 1. With clk = 0 the NAND’s output, φ_AND, is 1.
2. clk rises. Both NAND inputs are now 1, so φ_AND falls one NAND delay later: the AND plane starts to precharge.
3. The replica precharges. $\overline{\mathrm{clk}}$ falls one inverter delay after clk rose, and the dummy row starts to precharge. When $R_1$ is high, the bubbled input drops to 0.
4. φ_AND rises. One NAND delay after that, φ_AND rises and the AND plane evaluates. Its low pulse lasted as long as the replica took to precharge, plus the two gate delays around it.
5. clk falls. The NAND sees clk = 0 and stays high. $\overline{\mathrm{clk}}$ rises, and the dummy row evaluates again, back to low, ready for the next rising edge.

The dummy rows

board (45:33–47:36). The dummy row is a real AND row, laid out like the others, with as many NFETs as any row can have: the maximum literal count, 3 in the example, since a product holds at most one of $x_i$ and $\bar x_i$ for each input (46:11). In the φ_AND generator all three gates are tied to 1. With every device on, the node between the devices and the foot is joined to the row and must be charged too: “that’s going to produce the maximum amount of capacitance on this node, which is going to give me the slowest precharge” (46:37).

The two dummy rows, redrawn from the board (Lecture17 @ 49:25; the board writes the generic “clk” on each row’s precharge device and foot, and the labels here are the clocks each generator feeds it). Left, in the φ_AND generator, clocked by $\overline{\mathrm{clk}}$clk: all three gates at 1, so every device is on and the internal node between the devices and the foot is charged with the row: the slowest precharge. Right, in the φ_OR generator, clocked by φ_AND: one gate at 1 and two at 0, so it discharges through a single device: the slowest evaluate.

The φ_OR generator

board (47:38–49:37). φ_AND clocks a second dummy row; its output $R_2$R2​, inverted, is φ_OR.

The φ_OR generator, redrawn from the board (Lecture17 @ 49:25). Top: φ_AND clocks the dummy row $R_2$R2​, and an inverter after it gives φ_OR. Bottom added: its waveforms with the worked example’s delays. φ_AND falling starts $R_2$‘s precharge, so φ_OR falls a precharge later ($t_{pre}$tpre​); φ_AND rising starts $R_2$‘s evaluate through its one on device, so φ_OR rises only after the slowest evaluate ($t_{eval}$teval​).

The replica-and-inverter generator, edge by edge (board, 47:38–49:37)

1. φ_AND falls. $R_2$ precharges; when it is high, φ_OR falls (one inverter later) and the OR plane precharges.
2. φ_AND rises. The real AND rows start to evaluate, and so does $R_2$R2​. Its gates are 1, 0, 0: “I’m gonna set one of these to a one because the slowest evaluation is gonna be when only one of these evaluates” (49:09–49:37). A row discharging through one device is the slowest any real row can be.
3. φ_OR rises one inverter after $R_2$ is low: by then every real row has settled, so the OR plane evaluates on final rows. Requirement 2 holds at every corner, because $R_2$ is a real row.

A replica has the same structure, the same layout, and sits in the same place (a dummy row inside the PLA’s own array, 50:02–50:28). “This is very commonly done in SRAMs … lots of features in SRAMs are also going to be self-timed” (50:28).

A worked example: timing the two clocks

added Example delays, for example: $t_{inv} = 20$ ps, $t_{NAND} = 30$ ps, the replica’s precharge $t_{pre} = 150$ ps, its evaluate through one device $t_{eval} = 200$ ps, the OR plane’s evaluate 150 ps, and an output latch that needs 50 ps of setup. clk rises at 0.

The two clocks timed with the example delays added, computed from $t_{inv} = 20$20, $t_{NAND} = 30$30, $t_{pre} = 150$150, $t_{eval} = 200$ ps, an OR-plane evaluate of 150 ps and a 50 ps setup, clk rising at 0. φ_AND is low from 30 to 220 ps (190 ps), φ_OR from 200 to 440 ps (240 ps), the outputs are valid at 590 ps (after the OR plane’s 150 ps evaluate), and with the 50 ps setup the period must be at least 640 ps. The clock is drawn rising again at 800 ps.

Edge by edge

1. φ_AND falls one NAND delay after clk rises: at 30 ps.
2. φ_AND rises after the inverter, the replica’s precharge, the bubble and the NAND: $20 + 150 + 20 + 30 =$ 220 ps. It was low for $220 - 30 =$ 190 ps, which is $2t_{inv} + t_{pre}$tpre​: more than $t_{pre} = 150$ ps, so requirement 1 holds for the AND plane, with the two inverter delays to spare.
3. φ_OR falls when $R_2$ has precharged after φ_AND fell, then the inverter: $30 + 150 + 20 =$ 200 ps.
4. φ_OR rises when $R_2$ has evaluated after φ_AND rose, then the inverter: $220 + 200 + 20 =$ 440 ps. The slowest real row finished at $220 + 200 = 420$ ps, so requirement 2 holds, by one inverter delay.
5. The OR plane’s precharge window. φ_OR is low from 200 to 440 ps, 240 ps. It must cover the OR plane’s precharge.
6. The outputs are valid after the OR plane’s evaluate, at $440 + 150 =$ 590 ps, and the output latch needs them 50 ps before the next clk edge: the period must be at least $590 + 50 =$ 640 ps.

Check by the closed form: the OR window is $(t_{\phi_{\mathrm{AND}}\ \mathrm{low}}) + t_{eval} - t_{pre} = 190 + 200 - 150 = 240$ ps, the same as step 5. Two conditions on clk itself: its high phase must outlast φ_AND’s low pulse (here 190 ps; at a 640 ps period with a 50 % duty, the high phase is 320 ps), or clk’s fall would end the pulse early; and its low phase must let the dummy row $R_1$ evaluate again before the next rising edge.

The generators' edge timesadded

$$\begin{aligned} t_{\phi_{\mathrm{AND}}\ \mathrm{low}} &= 2t_{inv} + t_{pre} \\ \phi_{\mathrm{OR}}\!\downarrow &= \phi_{\mathrm{AND}}\!\downarrow + \,t_{pre} + t_{inv} \\ \phi_{\mathrm{OR}}\!\uparrow &= \phi_{\mathrm{AND}}\!\uparrow + \,t_{eval} + t_{inv} \\ t_{\phi_{\mathrm{OR}}\ \mathrm{low}} &= t_{\phi_{\mathrm{AND}}\ \mathrm{low}} + t_{eval} - t_{pre} \end{aligned}$$

Holds when: the lecture's two generators; clk rises at 0; the NAND's bubble counted as an inverter; the same replica design (precharge t_pre, evaluate t_eval) in both generators

Memorize or derive. Derive, three lines: (1) clk↑ → φ_AND↓ after $t_{NAND}$tNAND​; (2) clk↑ → $\overline{\mathrm{clk}}$↓ ($t_{inv}$tinv​) → $R_1$ high ($t_{pre}$tpre​) → bubble low ($t_{inv}$tinv​) → φ_AND↑ ($t_{NAND}$tNAND​), so the low time is $2t_{inv} + t_{pre}$tpre​; (3) φ_OR follows φ_AND’s edges through $R_2$ and one inverter, a precharge after the fall and an evaluate after the rise.

After the outputs are taken added. From about $t_{NAND}$ after each clk↑ until φ_OR falls (30 to 200 ps here), the rows precharge high while the OR plane still evaluates, so the previous cycle’s outputs may be lost soon after the edge that captures them. That is harmless if they are captured at that edge with the latch’s hold time met.

One replica design for both generators

FN19-6b asks for “a replica AND row, two instance of which can be used in the circuits below to generate $\phi_{AND}$ and $\phi_{OR}$ϕOR​” (FN19, p14): one design, used twice. The lecture’s two rows differ (all on for φ_AND, one on for φ_OR). A single design that serves both added:

A single replica row (added)

1. Copy a real AND row, laid out like the others in the array, with its own precharge PFET and foot driven by the replica’s clock input.
2. Give it the maximum literal count of NFETs (3 here), so that its row node carries every device’s drain capacitance.
3. Tie one NFET’s gate to $V_{DD}$ and the others to ground. In the φ_OR generator it then evaluates through one device: the slowest evaluate. In the φ_AND generator it still precharges the internal node, through the one on device, so its precharge is at least as slow as the all-on row’s: the slowest precharge.
4. Load its output like a real row’s: the same wire and the same OR-plane gate capacitance, so that its delays are the real rows’.
5. The cost: in the φ_AND generator this row evaluates through one device too, so clk’s low phase must cover $2t_{inv} + t_{eval}$teval​: the inverter to $\overline{\mathrm{clk}}$clk, the row’s evaluate and the NAND’s bubble, before the bubbled input is back at 1 for the next rising edge (240 ps with the example delays; the low phase is 320 ps at a 640 ps period).

The datapath practice page (FD1) solves FN19-6b in full; the lecture’s two rows are an equally valid, more conservative answer.

Traps.

• The typical literal count in the precharge replica. A row with fewer devices precharges faster, so the real rows with three are cut short.
• All inputs on in the evaluate replica. Three parallel devices discharge fastest; the slowest real row has one on.
• A dummy row that is not discharged before clk rises. The bubbled input is then 0 and the NAND never falls.
• Reading the φ_AND generator as a delayed clock. It is a chopper (Chapter 14 §5) whose delay is a replica.

Check yourself The widest product of a PLA has 5 literals. How many NFETs does each of the lecture's dummy rows get, and how many of them are on?

Five each (the maximum literal count). The φ_AND row has all 5 on (the slowest precharge); the φ_OR row has 1 on (the slowest evaluate).

Check yourself With the worked example's delays, only t_pre changes, to 250 ps. When does φ_AND rise, how long is it low, and when does φ_OR rise?

φ_AND still falls at 30 ps and is low for $2t_{inv} + t_{pre} = 40 + 250 = 290$ ps, so it rises at $30 + 290 = 320$ ps. φ_OR rises $t_{eval} + t_{inv} = 220$ ps later, at 540 ps.

10. SRAM organization: rows, columns and address bits

You need

Binary addressing added. $n$ address bits select one of $2^n$ things, so selecting one of $N$ (a power of two) takes $\log_2 N$ bits: 10 bits for 1024.

A multiplexer (Chapter 10 §7): $k$ select bits choose one of $2^k$ inputs and pass it to the output.

The question. The third kind of block is the array. What is inside an SRAM, how is a memory of so many words of so many bits laid out as a grid, and which address bits go where?

SRAM and DRAM

board (51:53–53:51; the board writes “SRAM, static random access memory” and “lower levels of cache”). An SRAM keeps its data as long as the power is on. A DRAM forgets: each cell must be read and written back (refreshed) within its retention time, by a DRAM controller. Level-one caches are almost always SRAM, and level-two caches often.

The array

board (54:08–57:57). Horizontal word lines (rows) come from a row decoder, which raises one of them for each address. Vertical bit lines (columns) cross them, and a memory cell sits at every crossing, attached to both (57:47). At the bottom, a column multiplexer with the read/write circuitry picks out the bits of one word.

The SRAM array, redrawn from the board (Lecture17 @ 57:57; the cells at every crossing as at 59:32, where the board completes them). Ten address bits split: 8 go to the row decoder (left, unlabelled), which raises one of 256 word lines (WL), and 2 to the column multiplexer and read/write circuits (mux / R/W), which pick one of the four 32-bit words on the selected row’s 128 columns (bit-line pairs, BL). The numbers 256 and 128 are this chapter’s example; the board leaves the grid unnumbered.

The board (Lecture17 @ 57:57)

Lecture17 @ 57:57The SRAM array, its address split 10 = 8 + 2, and the logical organization 1024 × 32 with two physical ones.

Fair copy of the board above (Lecture17 @ 57:57), mark for mark in its own layout. Black is the cyan pen; orange is the cream pen with which the lecturer is drawing the memory cells: two cell marks at the top row’s rightmost crossings, the only ones drawn so far (the board has a cell at every crossing by 59:32). The lecturer’s hand washes out the grid’s top right corner here; the lines there are read on 57:35. The three stacked words at the decoder’s left read “address bits”. The text lines are set level; the grid lines, the bus and the multiplexer box keep their drawn slopes.

Logical and physical organization

The board's example (55:45–57:22)

1. Logical organization. A memory of 1024 words of 32 bits, written 1024 × 32, is what the user sees: give an address, get 32 bits. Selecting one of 1024 words takes $\log_2 1024 = 10$ address bits.
2. Built as it reads? added 1024 rows of 32 cells is a strip 32 times taller than wide: long bit lines, a huge decoder.
3. Fold it. added The same 32,768 cells as 512 rows × 64 columns put two words on each row: 9 address bits pick the row and 1 bit picks one of the two words, through a 2:1 column multiplexer.
4. Fold again. 256 × 128 puts four words on a row: 8 bits pick one of 256 rows, and the other 2 bits drive a 4:1 column multiplexer that takes “128 bits down to my 32 bits”. “Because I can do column multiplexing, I can do whatever physical organization makes the most sense” (57:22).

One logical organization, three physical ones added (the values are the board’s, Lecture17 @ 57:57). Each rectangle holds the same 32,768 cells, drawn to scale. 1024 × 32 (the logical shape, 10 row bits, no column multiplexer), 512 × 64 (9 row bits, 1 column bit, 2:1) and 256 × 128 (8 row bits, 2 column bits, 4:1).

Splitting the addressadded

$$\text{address bits} = \log_2 N_w = \underbrace{\log_2 R}_{\text{row decoder}} + \underbrace{\log_2 (C/W)}_{\text{column mux}}$$

Holds when: N_w words of W bits stored as R rows by C columns, with R·C = N_w·W; every count a power of two; each row holds C/W whole words, chosen by a C/W : 1 column multiplexer

Memorize or derive. Memorize address bits $= \log_2 N_w$ (the board’s example). Derive the split: each row holds $C/W$ words, so the column bits choose one of $C/W$C/W, and the row bits one of $R$ rows; since $R \cdot C/W = N_w$Nw​, the two add up to $\log_2 N_w$log2​Nw​.

Worked examples

Two splits

1. The board’s: 1024 × 32 as 256 × 128. $\log_2 1024 = 10$ address bits. Rows: $\log_2 256 = 8$8. Words per row: $128/32 = 4$4, a 4:1 multiplexer, $\log_2 4 = 2$ column bits. Check: $8 + 2 = 10$10.
2. Added: 2k × 8 as 128 × 128. 2k = 2048 words, $\log_2 2048 = 11$ address bits. Rows: $\log_2 128 = 7$7. Words per row: $128/8 = 16$16, a 16:1 multiplexer, 4 column bits. Check: $7 + 4 = 11$11, and $128 \times 128 = 16{,}384 = 2048 \times 8$ cells.

On a past final (FN10-10). The same two moves: a 4k × 16 memory needs $\log_2 4096 = 12$ address bits, and built as 256 × 256 it uses $\log_2 256 = 8$ row bits and a $256/16 = 16$16:1 column multiplexer, 4 column bits ($8 + 4 = 12$8+12). The memory practice page (FM1) solves both parts; Chapter 19 draws the column multiplexer’s circuit.

What sits at each crossing (57:47–58:21). The cell is the 6T SRAM cell, attached to its word line and to a pair of bit lines, bit and $\overline{\mathrm{bit}}$bit. Chapter 19 opens it: two cross-coupled inverters and two access transistors, read stability, writability and the butterfly. The lecture’s boards from 59:32 on are in this chapter’s board gallery, at the end of the page.

One cell at a crossing added (the lecture’s words at 57:47; the bit and $\overline{\mathrm{bit}}$ pair from 59:52). Each cell connects to its row’s word line (WL) and to its column’s pair of bit lines. What is inside the box is Chapter 19’s.

Traps.

• Column bits as $\log_2 C$log2​C. The multiplexer chooses words, not bits: for 256 × 128 with 32-bit words it is $\log_2 (128/32) = 2$2, not $\log_2 128 = 7$7.
• The logical shape as the physical one. 1024 × 32 built as it reads is 32 times taller than wide; designers fold the array toward a square with column multiplexing.

Check yourself A memory is 2k × 32. How many address bits does it need?

2k = 2048 words, $\log_2 2048 =$ 11 bits. The word width does not enter.

Check yourself The same 2k × 32 memory is built as 512 × 128. How many address bits go to the row decoder, how many to the column multiplexer, and what is the multiplexer's ratio?

Rows: $\log_2 512 =$ 9. Words per row: $128/32 = 4$4, a 4:1 multiplexer, 2 column bits. Check: $9 + 2 = 11$11, and $512 \times 128 = 65{,}536 = 2048 \times 32$ cells.

On the exam

The past finals test this chapter in three questions: two PLAs to read, a replica row to design, and a memory’s address bits. 37 points in all.

Part	Points	What it asks	Sections
FN12-10a	9	the functions $f_0$f0​, $f_1$ of a static PLA: the example’s first three rows, output inverters drawn	§2, §3, §4
FN19-6a	10	the functions $y_0$y0​, $y_1$ of a dynamic PLA with correct clocks: the example’s four rows, no output inverters	§3, §4, §7
FN19-6b	8	a replica AND row, used twice, to generate φAND and φOR	§8, §9
FN10-10a	4	the address bits of a 4k × 16 memory	§10
FN10-10b	6	the column-multiplexing bits when it is built as 256 × 256	§10 (Chapter 19 draws the multiplexer)
FN12-10d	9	a ROM: a full decoder into a pseudo-NMOS NOR plane, read without inverters	§2–§4, as context (Chapter 19)

FN12-10a and FN19-6 are solved on the datapath practice page (FD1), FN10-10 on the memory practice page (FM1). At the finals’ pace of 0.7–0.9 minutes a point, FN19-6 is a 13–16 minute question.

Memorize.

• A product is the NOR of its literals’ complements, so a true literal’s device sits on the complement line; a column is the NOR of its rows.
• Look for the output inverters before writing a PLA’s outputs: without them, each output is the complement of its sum.
• Espresso’s codes: 1 = true, 0 = complemented, – = absent; in the output part, 1 = the output uses the product. Rows = distinct products.
• Each plane precharges while its clock is low. The two requirements: φ_AND’s low pulse at least the slowest row’s precharge; φ_OR rises only after the slowest row’s evaluate.
• The replica rows: the maximum literal count; all on for the slowest precharge (φ_AND), one on for the slowest evaluate (φ_OR); one design with one on serves both.
• Address bits $\log_2 N_w$log2​Nw​; row bits $\log_2 R$log2​R; column bits $\log_2 (C/W)$log2​(C/W).

Derive (with the path).

• NOR–NOR from AND–OR: an OR is a NOR and an inverter; an AND is a NOR of complements (De Morgan).
• A row’s function from its devices: flip each device line’s literal, AND them.
• The generators’ edges: clk↑ → φ_AND↓; $\overline{\mathrm{clk}}$↓ → $R_1$ precharged → bubble → φ_AND↑, so $t_{\phi_{\mathrm{AND}}\ \mathrm{low}} = 2t_{inv} + t_{pre}$tpre​; φ_OR↑ a $t_{eval} + t_{inv}$ after φ_AND↑; the OR window $t_{\phi_{\mathrm{AND}}\ \mathrm{low}} + t_{eval} - t_{pre}$tpre​.

Method cards. FN19-6b belongs to the clock-generation card (its move 8, a replica delay, points here). The playbook’s PLA card (recognize a grid with pull-ups at the row ends and the column tops; moves: rows, columns, inverter, simplify, check two rows; traps: the gate’s line, the missing inverter) covers FN12-10a and FN19-6a.

The lecture’s boards

The boards of Lectures 16 and 17 used in this chapter (23 frames)

Lecture16 @ 55:42 the example functions first written

Lecture16 @ 58:10 SOP and the De Morgan stages to NOR–NOR

Lecture17 @ 02:59 the recap: AND–OR and NOR–NOR, the planes named

Lecture17 @ 03:46 static PLA: pseudo-NMOS, ratioed logic

Lecture17 @ 08:15 the four product rows, before the devices

Lecture17 @ 12:08 the AND plane programmed

Lecture17 @ 14:52 the static PLA with its OR plane and equations

Lecture17 @ 19:40 the Espresso table, uncovered

Lecture17 @ 20:25 the Espresso table complete

Lecture17 @ 21:05 the table and the arrow to Espresso

Lecture17 @ 27:19 the controller’s specification

Lecture17 @ 35:01 the controller’s table, first five rows

Lecture17 @ 37:47 the dynamic PLA on one clock: the race

Lecture17 @ 41:41 φ_AND and φ_OR, before the generators

Lecture17 @ 43:07 self-timed edges, replica, PVT, asynchronous

Lecture17 @ 47:50 the φ_AND generator and its dummy row

Lecture17 @ 50:10 both generators and both dummy rows

Lecture17 @ 50:59 replica checked; the top row being erased

Lecture17 @ 53:03 SRAM, static random access memory

Lecture17 @ 57:57 the SRAM array and its organizations

Lecture17 @ 59:32 every cell marked; the 6T cell begun (Chapter 19)

Lecture17 @ 60:47 the 6T SRAM cell (Chapter 19)

Lecture17 @ 64:30 the cell, the butterfly, read and write (Chapter 19)