\documentclass[letter,12pt]{article}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{comment}
%\usepackage{subtable}
\textwidth=14.9cm
\voffset -2.5cm
\hoffset -1.2cm
\textheight=24cm
\topmargin 2cm

%\pagestyle{empty}
\pagenumbering{arabic}
\begin{document}

\noindent
\textbf{\Large CSE140 Homework 2, Due 11:59PM, Mon 4/19/2021}
\newline

\noindent
Homework 2 covers the combinational logic specification, and
implementation.
For the first three problems, we practice more on the specification and design using some popular functions.
For the last two problems, we practice logic design using
Karnaugh maps to derive the minimal sum of products and product of sums expressions. 

\section{Full Subtractor}
A full subtractor reads three binary values $(x, y, b_{in})$ and produces
two binary outputs $(b_{out}, d)$. The relation between all variables can be formulated with an arithmetic equation $-2b_{out}+d= x-y-b_{in}$.

\noindent
A. Write the truth table of the subtractor.

\noindent
B. Express the functions in a minimal sum of products form.

\noindent
C. Use a minimal number of full subtractors (no other
gates) to implement a 4-bit binary subtractor.
Depict your design with a schematic diagram.
Note that a 4-bit binary substractor reads
two 4-bit binary numbers $X=(x_3, x_2, x_1, x_0)$, 
$Y=(y_3, y_2, y_1, y_0)$ and a borrow-in bit $b_0$, 
and produces the subtraction result with a borrow-out bit $b_4$ and 
the difference, i.e. a 4-bit 
binary number $D= (d_3, d_2, d_1, d_0)$.
For example, when $X=(0110), Y=(1011)$
and $b_0= 1$, the result is $b_4=1$ and
$D=(1010)$.

\begin{comment}

\end{comment}

\section{Majority Function}
A majority function produces output $f=1$, when half of all, or more input bits are true, otherwise, the output $f=0$.
For a 4-input majority function example, we have
$f(1, 1, 0, 0)=1$, and
$f(0, 1, 0, 0)=0$.

\noindent
A. Write the truth table of the 4-input majority function.

\noindent
B. Express the 4-input majority function using a minimal sum of product expression. 
Illustrate your design with a logic diagram.

\noindent
C. Construct a 3-input majority function 
using 4-input majority function modules as basic
building blocks (no other gates except 0, 1 constants, and inverters).

\noindent
D. Can we construct a 5-input majority function
using 4-input majority function modules as basic
building blocks (no other gates except 0, 1 constants, and inverters)?
Use one sentence to explain your answer.

\section{Priority Encoder}
A priority encoder reads a vector of four binary bits 
$(a_3, a_2, a_1, a_0)$ and produces a binary
number $(d_1, d_0)$ that presents the highest index of the
input bit which is true.
For example, when
$(a_3, a_2, a_1, a_0)=(1, 1, 1, 0)$,
the output $(d_1, d_0)=(1, 1)$; when
$(a_3, a_2, a_1, a_0)=(0, 1, 0, 1)$,
the output $(d_1, d_0)=(1, 0)$; and 
when $(a_3, a_2, a_1, a_0)=( 0, 0, 0, 1)$,
the output $(d_1, d_0)=(0, 0)$.
However, when none of the input bits asserts a true value, i.e.
$( a_3, a_2, a_1, a_0)=(0, 0, 0, 0)$,
the output remains to be $(d_1, d_0)=(0, 0)$.

\noindent
A. Write the truth table of the priority encoder.

\noindent
B. Express the encoder in a minimal sum of product form. Illustrate your design with a logic
diagram.

\noindent
C. How do we differentiate the 
cases when $(d_1, d_0)= (0, 0)$?
Use one sentence to explain your answer.

\section{Minimal Sum of Products Expression}
Implementation from truth tables to sum of products expressions.

\noindent
1. Use Karnaugh map to simplify function

\indent
%$f(a,b,c) = \sum m(1,6) + \sum d(3,5)$.
$f(a,b,c) = \sum m(1, 2, 4) + \sum d(3, 5, 6)$.

\noindent
List all possible minimal two-level sum of products expressions.
Show the switching functions. No need for the schematic diagram.

\noindent
2. Use Karnaugh map to simplify function

\indent
%$f(a,b,c,d) = \sum m(4,6,8,9,12,14) + \sum d(1,3,7)$.
$f(a,b,c,d) = \sum m(1, 4, 6, 7, 11, 12, 15) + \sum d(3, 5, 9)$.

\noindent
List all possible minimal two-level sum of products expressions.
Show the switching functions. No need for the schematic diagram.

\noindent
3. Use Karnaugh map to simplify function

\indent
%$f(a,b,c,d,e) = \sum m(1,3,4,9,11,12,14,15,17,19,20,22,27,28,30) + \sum d(7,21,23,24,26)$.
$f(a,b,c,d,e) = \sum m(0,2,5,7,8,13,15,16,18,21,24,28,29,31) + \sum d(10,22,27)$.

\noindent
List all minimal two-level sum of products expressions.
Show the switching functions. No need for the schematic diagram.

\section{Minimal Product of Sums Expression}
Implementation from truth table to product of sums expressions.

\noindent
1. Use Karnaugh map to simplify function

\indent
%$f(a,b,c) = \sum m(0,4,5,7) + \sum d(2,3)$.
$f(a,b,c) = \sum m(2, 6, 7) + \sum d(1, 4)$.

\noindent
List {\bf all} possible minimal two-level
product of sums expressions.
Show the switching functions. No need for the schematic diagram.

\noindent
2. Use Karnaugh map to simplify function

\indent
%$f(a,b,c,d) = \sum m(2,5,7,8,10,11,15) + \sum d(0,1,6)$.
$f(a,b,c,d) = \sum m(1, 4, 5, 9, 13, 14) + \sum d(3, 6, 11, 12, 15)$.

\noindent
List all possible minimal two-level
product of sums expressions.
Show the switching functions. No need for the schematic diagram.

\noindent
3. Use Karnaugh map to simplify function

\indent
%$f(a,b,c,d,e) = \sum m(0,2,4,7,9,12,13,17,18,23,26,29,31) + \sum d(1,6,16,20,22,25)$
$f(a,b,c,d,e) = \sum m(3,11,12,13,14,19,22,23,25,28,29,30,31) + \sum d(7,9,15,27)$

\noindent
List all minimal two-level
product of sums expressions.
Show the switching functions. No need for the schematic diagram.

\end{document}