2024-04-17

📅 Wednesday, April 17th, 2024

There is not one big cosmic meaning for all, there is only the meaning we each give to our life.

— Anaïs Nin

ECS154A Lecture: K-maps

Problem

Design a “majority rules” circuit with 3 inputs.

We can easily come up with the majority rule truth table. The output $F$ is 1 whenever at least two inputs are 1.

$x$	$y$	$z$	$F$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

$$F=\overline{x}yz+x\overline{y}z+xy\overline{z}+xyz$$

Review: Circuit Design Process

Truth table → Boolean expression (sum-of-products) → schematics

Can we simplify this further?

Yes

$$\begin{array}{rl}F& =\overline{x}yz+x\overline{y}z+xy\overline{z}+xyz\\ & =xyz+x\overline{y}z+xy\overline{z}+xyz+xyz+xyz\\ & =yz\overline{x}+xz\overline{y}+xy\overline{z}+yzx+xzy+xyz\\ & =yz\overline{x}+yzx+xz\overline{y}+xzy+xy\overline{z}+xyz\\ & =yz(\overline{x}+x)+xz(\overline{y}+y)+xy(\overline{z}+z)\\ & =yz(1)+xz(1)+xy(1)\\ & =yz+xz+xy\end{array}$$

Is there a systematic way to reduce boolean expressions?

Yes, via K-maps

• A K-map is a matrix that represents the output values of a Boolean function. Each output value (each element) is derived from the minterm of the function, which is a product with terms that each contains all inputs exactly once.
• K-map minimizes equations graphically.
• $PA+P\overline{A}=P$

Here’s an and gate:

A	B	Y
0	0	0
0	1	0
1	0	0
1	1	1

It’s easy to represent an and gate in a matrix:

B\A	0	1
0	0	0
1	0	1

But what about a three-input function?

A	B	C	Y
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

We can combine multiple variables into a product. Note that we cannot have more than a single one-bit change from one column label to the next one (01 → 11 is okay, but 01 → 10 is not).

C\AB	00	01	11	10
0	1	0	0	0
1	1	0	0	0

We want to circle groups of contigious group of 1’s. This is true for $AB=00$, so we know that $C$ doesn’t matter. Every such group represents a term in our output function.

$$Y=\overline{A}\overline{B}$$

Naturally, we want the least number of terms in this simplified function expression. The longer the group is in a single column, the more simplified the term becomes.

K-map Grouping & Simplification Rules

• We circle 1’s for sum-of-products (and 0’s for product-of-sums, but we don’t do them in this course).
• Each 1 must be in at least 1 circle/group, and the same 1 can be in multiple groups if necessary (e.g., if there’s an odd number of 1’s, or if being in multiple groups give you larger groups).
• Each group must have a power of two number of 1’s ($2^0=1$ one and 2 one’s are okay, but not 3 one’s).
• Try to make each circle as large as possible (it’s okay to overlap them).
• A circle may wrap around/beyond the edges (e.g., four 1’s in the corners form a single group).
• We only circle don’t cares (X’s) if it helps us make larger circles.
• A group of $n$ eliminates $\lg n$ variables from its associated term, e.g., for a ternary function, a group of 4 one’s corresponds to a term with 1 variable.

---

Example: large group

X\YZ	00	01	11	10
0	0	1	1	0
1	0	1	1	0

We have a group of 4 one’s, how can we simplify $F(X,Y,Z)$?

• Does X matter in the group? No, output doesn’t change with X, i.e., from row to row.
• Does Y matter in the group? No, output doesn’t change with Y.
• This leaves us with Z, which is always 1.

$$F(X,Y,Z)=Z$$

---

Example: wrapping around the edge

X\YZ	00	01	11	10
0	1	1	1	1
1	1	0	0	1

We can simplify this to two groupings:

• A square group of 4 one’s that wraps around the edge: $\overline{X}$
• A rectangular group of 4 one’s across the first row: $\overline{Z}$

$$F(X,Y,Z)=\overline{X}+\overline{Z}$$

SOC001 Lecture: interactions & organizations

Blog posts 2-3 due date changed to Sundays. Blog post 1 handed back by Friday with comments. Read the updated instructions for writing blog posts.

• Clarification of terms in 2024-04-15 related to roles (daily note has been updated in-place).
• Dramaturgical analysis is the process of analyzing social interactions under the analogy of a theater (i.e., as if people are performing in a theater).
• systematic categories for analyzing nonfictional dramaturgy based on the dramatistic pentad
  • places: When and where the performance taking place?
    • e.g., Interviewers set up in-person room at a designated time.
  • players: Who is/are performing?
    • e.g., Interviewer & interviewee
  • presentation: How is the performance done?
    • verbal & non-verbal communication
    • e.g., Interview states questions
  • purpose: What is the goal of each performance?
    • e.g., The interview tries to answer questions as best as he could to impress the interviewer.
    • There can be multiple performances taking place sequentially within a single encounter.
  • products: What is the cumulative result of the performances?
    • e.g., The interviewer got a job.

(missed class for second half)