\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{CSE140 Homework 2, Due 11:59PM, Mon 4/22/19}
\newline

\noindent
Homework 2 covers the CMOS design, combinational logic specification, and
implementation.
For the first problem, we construct a gate using CMOS designs.
For the next three problems, we practice more on the specification,
in particular, when the number of input bits is not small, and
the implementation may take multiple levels of logic gates.
For the last two problems, we practice design minimization using
Karnaugh maps in sum of products and product of sums formats. 

\section{CMOS Designs}
Design a CMOS gate with function $y(a,b,c,d)=[a(b+cd)]'$. Draw the schematic diagram
using NMOS and PMOS transistors as the basic elements.

\section{Voting Machine}
A voting machine reads six binary bits $(a_5, a_4, a_3, a_2, a_1, a_0)$ and
outputs a binary number $(y_2, y_1, y_0)$ so that the output represents the
number of input bits which are 1 instead of 0.
For example, when input $(a_5, a_4, a_3, a_2, a_1, a_0) = (1, 1, 1, 1, 1, 0)$,
output $(y_2, y_1, y_0) = (1, 0, 1)$.
When input $(a_5, a_4, a_3, a_2, a_1, a_0) = (0, 1, 1, 0, 0, 1)$,
output $(y_2, y_1, y_0) = (0, 1, 1)$.

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

\noindent
B. Express the function in a minimal Boolean expression.

\noindent
C. Use a minimal number of full adders (no other gates) to implement the
machine. Depict your design with a schematic diagram.

\begin{comment}

\end{comment}

\section{Majority Function}
A majority function $f$ reads five binary bits 
$(a_4, a_3, a_2, a_1, a_0)$ and produces a binary
output $f=1$ when the majority of the input bits are true, otherwise
the output $f=0$.
For example,
$f(1, 1, 1, 0, 0)=1$, and
$f(1, 1, 0, 0, 0)=0$.

\noindent
A. Express the function in a minimal Boolean expression.

\noindent
B. Implement the function using a minimal number of full adders (no other
gates). 
Depict your design with a schematic diagram.

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

\noindent
A. Derive a Boolean expression of the three output bits
(no need to be minimal but try to be concise).

\noindent
B. Implement the encoder with AND, OR, NOT gates (no need to be minimal
but try to be organized).

\section{Minimal Sum of Products Expression}
Implementation from truth table to sum of products 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(0,4,5,7) + \sum d(1,2)$.

\noindent
List {\bf 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(2,5,7,8,10,11,15) + \sum d(0,1,6)$.
$f(a,b,c,d) = \sum m(2,3,5,6,8,11,15) + \sum d(0,9,12)$.

\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(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(6,7,8,10,12,13,15,16,21,22,24,26,31) + \sum d(0,2,9,18,28,29)$

\noindent
Write \textbf{one} minimal two-level
sum of products expression.
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(1,6) + \sum d(3,5)$.
$f(a,b,c) = \sum m(0,7) + \sum d(1,2,5)$.

\noindent
List 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(4,6,8,9,12,14) + \sum d(1,3,7)$.
$f(a,b,c,d) = \sum m(1,2,4,9,12,15) + \sum d(3,11,14)$.

\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(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(1,3,4,11,12,13,14,19,20,22,27,28,30) + \sum d(7,9,23,24,26)$.

\noindent
Write \textbf{one} minimal two-level product of sums expression.
Show the switching functions. No need for the schematic diagram.

\end{document}