Quiz 1 Practice Problems | CSCI 343

Topics for Quiz 1

No floating point on this quiz.

Computations

• K-Maps with and without don’t cares
  • 3 var and 4 variable k-maps
• Implementing a function using a $2^2 \times 1$ MUX

Conceptual Understanding: Behavior and use cases

• Integrated circuits
  • Multiplexer
  • Decoder
  • ROM
• Parallel adder/subtractor
• Arithmetic Logic Units
  • 1-bit ALU
  • 32-bit ALU for MIPS
  • Implementation of check-for-zero and slt (as covered in class and appendix B of Patterson & Hennessy)

 

Example 1: Implementing a Function using a MUX

Using a MUX of size $2^2 \times 1$, implement $f(x,y,z) = x'y + y'z'$ using $yz$ as the control lines.

Based on your solution, provide the completed MUX and give the expression of the MUX’s output.

Solution

	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

	$I_0$	$I_1$	$I_2$	$I_3$
$x'$	0	1	2	3
$x$	4	5	6	7
	$1$	$0$	$x'$	$x'$

Inputs:

$$I_0 = 1 \qquad I_1 = 0 \qquad I_2 = x' \qquad I_3 = x'$$

Output Expression:

$$\begin{align*} & I_0 y'z' + I_1 y'z + I_2 yz' + I_3 yz \\ =\; & (1)y'z' + \cancel{(0)y'z} + x'yz' + x'yz \\ =\; & y'z' + x'yz' + x'yz \end{align*}$$

The MUX

Example 2: Implementing a Function using a MUX

Using a MUX of size $2^2 \times 1$, implement $f(x,y,z) = x'y + y'z'$ using $xy$ as the control lines.

Based on your solution, provide the completed MUX and give the expression of the MUX’s output.

Solution

	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

	$I_0$	$I_1$	$I_2$	$I_3$
$z'$	0	2	4	6
$z$	1	3	5	7
	$z'$	$1$	$z'$	$0$

Inputs:

$$I_0 = z' \qquad I_1 = 1 \qquad I_2 = z' \qquad I_3 = 0$$

Output Expression:

$$\begin{align*} & I_0 x'y' + I_1 x'y + I_2 xy' + I_3 xy \\ =\; & z'x'y' + (1)x'y + z'xy' + \cancel{(0)xy} \\ =\; & x'y'z' + x'y + xy'z' \end{align*}$$

The MUX

Example 3: Simplify with K-map

Use a K-map to simplify $F(A,B,C) = \Sigma(0,3,5,6)$ with don’t cares $D = \Sigma(2,4)$

Solution

Example 4: Simplify with K-map

Use a K-map to simplify $F(A,B,C) = \Sigma(0,2,5,6)$ with don’t cares $D = \Sigma(3,4)$

Solution

Example 5: Simplify with K-map

Use a K-map to simplify $F(A,B,C,D) = \Sigma(0,2,3,5,6,7,8,9)$ with don’t cares $D = \Sigma(10,11,12,13,14,15)$.

Solution

Example 6: Simplify with K-map

Use a K-map to simplify $F(A,B,C,D) = \Sigma(0,2,7,12,14)$ with don’t cares $D = \Sigma(3,4,6,9,13)$

Solution