2024-04-19

📅 Friday, April 19th, 2024

Friendship is the marriage of the soul, and this marriage is liable to divorce.

— Voltaire

ECS154A Lecture: K-maps cont’d, bubble pushing, 2-bit multiplier

Maurice Karnaugh came up with K-map. in th 50s.

Here’s an or gate.

Y\X	0	1
0	0	1
1	1	1

There are two groups, but what if we take the zeros instead of ones? We can take the zero, and use De Morgan’s theorem to simplify it.

$$F=\overline{\overline{x}\overline{y}}=x+y$$

Does this process work? Yes, but this defeats the purpose of K-map, since its goal is to arrive at the simplest circuit without having to do much boolean algebra.

We can also use product of sums, which only looks at when things are zero. The only zero we have is when $x=0$ & $y=0$, so we have:

$$F=(x+y)$$

It follows that:

$$\text{sum of products}(F)=\text{product of sums}(\overline{F})$$

Use sum of products or product of sums, whichever is shorter. This course uses sum of products.

---

Here’s an nor gate.

Y\X	0	1
0	1	0
1	0	0
Looking at the zeros, we can derive $F$ and use De Morgan’s law to simplify again.

• The vertical group is 0 when $x=1$, so we invert it: $\overline{x}$
• The horizontal group is 0 when $y=1$, so we invert it: $\overline{y}$

$$F=\overline{x}\overline{y}\equiv \overline{x+y}$$

When applied to digital logic, this simplification technique is aptly called bubble pushing:

And, or, nand, nor, & not all have a unit delay (propagation delay of 1), but they aren’t necessarily the same cost in production (NAND and NOR are preferred over AND and OR in CMOS; @harrisDigitalDesignComputer2016 p. 68).

---

Design and build a circuit that multiplies two 2-bit unsigned numbers, and minimize the curcuit.

Again, don’t worry about “but we haven’t been taught multiplers;” just come up with the truth table first. It’s hard to do binary multiplication in our heads, so we convert $A$ and $B$ to decimal ($A_d,B_d$), do the multiplication $F_d$, and convert the result back to binary.

$A_1{A}_0$	$B_1{B}_0$	$A_d$	$B_d$	$F_d$	$F_3$	$F_2$	$F_1$	$F_0$
00	00	0	0	0	0	0	0	0
00	01	0	1	0	0	0	0	0
00	10	0	2	0	0	0	0	0
00	11	0	3	0	0	0	0	0
01	00	1	0	0	0	0	0	0
01	01	1	1	1	0	0	0	1
01	10	1	2	2	0	0	1	0
01	11	1	3	3	0	0	1	1
10	00	2	0	0	0	0	0	0
10	01	2	1	2	0	0	1	0
10	10	2	2	4	0	1	0	0
10	11	2	3	6	0	1	1	0
11	00	3	0	0	0	0	0	0
11	01	3	1	3	0	0	1	1
11	10	3	2	6	0	1	1	0
11	11	3	3	9	1	0	0	0

Note how product of sums doesn’t work here, because there are too many zeros in the output.

We don’t really need K-maps for this, but here’s one anyways:

$B_1{B}_0$ \ $A_1{A}_0$	00	01	11	10
00	0000	0000	0000	0000
01	0000	0001	0011	0010
11	0000	0011	1000	0110
10	0000	0010	0110	0100

ECS154A Discussion: FISC schematics

• register file
• WE: write-enable, i.e., only use the input if WE is 1. For example, on a bnz instruction, the target address will still be fed into the ALU. Since we don’t want the output of ALU to put garbage into the z register, we set zf’s write-enable bit to false whenever it’s a branch. We also pass this to the register file’s WE under the same reasoning.
• Note the the entire circuit is controlled by the clock in the bottom left corner.

Schematics will also be availble in Logisim on Canvas.

SOC001 Discussion: social construction, performance

• SOC001 2024-04-19 discussion
• Under a social constructionism lens, people form policies / institutions / social constructs on how things are over time (over many social interactions). Such agreements form the truths and reality around us.
• Everyone is an audience member (we watch how others perform as feedback of our performance) and performer (we perform for others, adjusting it according to others’ feedback) at the same time.
• SOC001 2024-04-19 participation assignment

Blog post 2 due Sunday!

MGT011A Discussion: no notes