187 lines
6.9 KiB
TeX
187 lines
6.9 KiB
TeX
\documentclass[12pt]{article}
|
|
|
|
\usepackage{karnaugh-map}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[margin=2cm]{geometry}
|
|
|
|
\title{Howework 5 -- Computer Architecture}
|
|
\author{Claudio Maggioni \and Tommaso Rodolfo Masera}
|
|
|
|
\newcommand{\bn}[1]{
|
|
\overline{#1}
|
|
}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
\section{Question 1}
|
|
\subsection{\label{sec:11}Sub-question 1}
|
|
\paragraph{Starting with:}
|
|
$f(A, B, C, D) = \bn{A} \times \bn{B} \times \bn{C} \times \bn{D} +
|
|
\bn{A} \times \bn{B} \times C \times \bn{D} + \bn{A} \times B \times C \times \bn{D} +
|
|
A \times \bn{B} \times \bn{C} \times \bn{D} + A \times \bn{B} \times \bn{C} \times D +
|
|
A \times \bn{B} \times C \times \bn{D} + A \times B \times C \times D +
|
|
\bn{A} \times \bn{B} \times \bn{C} \times D + \bn{A} \times B \times C \times D =$
|
|
|
|
\paragraph{apply the distributive law:}
|
|
$\bn{A} \times (\bn{B} \times \bn{C} \times \bn{D} + \bn{B} \times C \times \bn{D} +
|
|
B \times C \times \bn{D} + \bn{B} \times \bn{C} \times D + B \times C \times D) +
|
|
A \times (\bn{B} \times \bn{C} \times \bn{D} + \bn{B} \times \bn{C} \times D +
|
|
\bn{B} \times C \times \bn{D} + B \times C \times D) =$
|
|
|
|
\paragraph{apply it again:}
|
|
$\bn{A} \times (\bn{B} \times (\bn{C} \times \bn{D} + C \times \bn{D} + \bn{C} \times D)
|
|
+ B \times C \times (\bn{D} + D)) + A \times (\bn{B} \times (\bn{C} \times \bn{D} + \bn{C} \times D +
|
|
C \times \bn{D}) + B \times C \times D) = $
|
|
|
|
|
|
\subsubsection{\label{sec:cd}Solving $\bn{C} \times \bn{D} + C \times \bn{D} + \bn{C} \times D$}
|
|
|
|
\paragraph{Apply the distributive law:}
|
|
$\bn{C} \times (\bn{D} + D) + C \times \bn{D} = $i
|
|
|
|
\paragraph{then apply the inverse law:}
|
|
$\bn{C} \times 1 + C \times \bn{D} =$
|
|
|
|
\paragraph{then apply the identity law:}
|
|
$\bn{C} + C \times \bn{D} =$
|
|
|
|
\paragraph{then apply De Morgan's law:}
|
|
$\bn{C \times \bn{C \times \bn{D}}} =$
|
|
|
|
\paragraph{then apply it again:}
|
|
$\bn{C \times (\bn{C} + D)} =$
|
|
|
|
\paragraph{then apply the distributive law:}
|
|
$\bn{C \times \bn{C} + C \times D} =$
|
|
|
|
\paragraph{then apply the inverse law:}
|
|
$\bn{0 + C \times D} =$
|
|
|
|
\paragraph{then, finally, apply the identity law, obtaining:}
|
|
$\bn{C \times D}$
|
|
|
|
\subsubsection{Back to the main function}
|
|
\paragraph{by \ref{sec:cd} and the inverse law, we continue this way:}
|
|
$\bn{A} \times (\bn{B} \times \bn{C \times D} + B \times C \times 1) +
|
|
A \times (\bn{B} \times \bn{C \times D}) + B \times C \times D) =$
|
|
|
|
\paragraph{then apply the identity law:}
|
|
$\bn{A} \times (\bn{B} \times \bn{C \times D} + B \times C) +
|
|
A \times (\bn{B} \times \bn{C \times D}) + B \times C \times D) =$
|
|
|
|
\paragraph{then apply the distributive law:}
|
|
$\bn{A} \times \bn{B} \times \bn{C \times D}) + \bn{A} \times B \times C +
|
|
A \times \bn{B} \times \bn{C \times D} + A \times B \times C \times D =$
|
|
|
|
\paragraph{then apply it again:}
|
|
$\bn{B} \times \bn{C \times D} \times (\bn{A} + A) + B \times C \times (\bn{A} + A \times D) =$
|
|
|
|
\paragraph{then apply the inverse law:}
|
|
$\bn{B} \times \bn{C \times D} \times 1 + B \times C \times (\bn{A} + A \times D) =$
|
|
|
|
\paragraph{then apply the identity law:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times (\bn{A} + A \times D) =$
|
|
|
|
\paragraph{then apply De Morgan's law:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times \bn{A \times \bn{A \times D}} =$
|
|
|
|
\paragraph{then apply it again:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times \bn{A \times (\bn{A} + \bn{D})} =$
|
|
|
|
\paragraph{then apply the distributive law:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times \bn{A \times \bn{A} + A \times \bn{D}} =$
|
|
|
|
\paragraph{then apply the inverse law:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times \bn{0 + A \times \bn{D}} =$
|
|
|
|
\paragraph{then apply the identity law:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times \bn{A \times \bn{D}} =$
|
|
|
|
\paragraph{then, finally, apply De Morgan's law, we find the result:}
|
|
$\bn{B} \times \bn{C \times D} + B \times C \times (\bn{A} + D)$
|
|
|
|
\subsection{Sub-question 2}
|
|
Using the minterm normal form given in section \ref{sec:11}, we can deduct the truth table of the function. Using that, we can find the following Karnaugh map and the following prime implicants:
|
|
|
|
\begin{figure}[h]
|
|
\centering{
|
|
\begin{karnaugh-map}[4][4][1][AB][CD]
|
|
\maxterms{1,3,5,7,11,12,14}
|
|
\minterms{0,2,4,6,8,9,10,13,15}
|
|
\implicant{1}{7}
|
|
\implicantedge{12}{12}{14}{14}
|
|
\implicantedge{3}{3}{11}{11}
|
|
\end{karnaugh-map}
|
|
}
|
|
\end{figure}
|
|
|
|
Using those prime implicants we find the boolean function $(\bn{B} + C) \times (\bn{A} + \bn{B}
|
|
+ D) \times (B + \bn{C} + \bn{D})$.
|
|
|
|
\section{Question 2}
|
|
\subsection{Sub-question 1}
|
|
We assume $X_3$ is the most significant bit in the binary number. The truth table of the function is:
|
|
|
|
\begin{figure}[h]
|
|
\centering{
|
|
\begin{tabular}{cccc|c}
|
|
\textbf{$X_3$} & \textbf{$X_2$} & \textbf{$X_1$} & \textbf{$X_0$} & \textbf{$Y$} \\ \hline
|
|
0 & 0 & 0 & 0 & 0 \\
|
|
0 & 0 & 0 & 1 & 1 \\
|
|
0 & 0 & 1 & 0 & 0 \\
|
|
0 & 0 & 1 & 1 & 0 \\
|
|
0 & 1 & 0 & 0 & 0 \\
|
|
0 & 1 & 0 & 1 & 0 \\
|
|
0 & 1 & 1 & 0 & 1 \\
|
|
0 & 1 & 1 & 1 & 1 \\
|
|
1 & 0 & 0 & 0 & 1 \\
|
|
1 & 0 & 0 & 1 & 1 \\
|
|
1 & 0 & 1 & 0 & 1 \\
|
|
1 & 0 & 1 & 1 & 1 \\
|
|
1 & 1 & 0 & 0 & 1 \\
|
|
1 & 1 & 0 & 1 & 1 \\
|
|
1 & 1 & 1 & 0 & 1 \\
|
|
1 & 1 & 1 & 1 & 1 \\
|
|
\end{tabular}
|
|
}
|
|
\end{figure}
|
|
|
|
\subsection{Sub-question 2}
|
|
The Conjunctive Normal Form, or the maxterm expansion of the function, is:
|
|
|
|
\begin{figure}[h]
|
|
$(X_3 + X_2 + X_1 + X_0) \times
|
|
(X_3 + X_2 + \bn{X_1} + X_0) \times (X_3 + X_2 + \bn{X_1} + \bn{X_0}) \times
|
|
(X_3 + \bn{X_2} + X_1 + X_0) \times (X_3 + \bn{X_2} + X_1 + \bn{X_0})$
|
|
\end{figure}
|
|
|
|
The Disjunctive Normal Form, or the minterm expansion of the function, is:
|
|
|
|
\begin{figure}[h]
|
|
$(\bn{X_3} \times \bn{X_2} \times \bn{X_1} \times X_0) + (\bn{X_3} \times X_2 \times X_1 \times \bn{X_0}) +
|
|
(\bn{X_3} \times X_2 \times X_1 \times X_0) + (X_3 \times \bn{X_2} \times \bn{X_1} \times \bn{X_0}) +
|
|
(X_3 \times \bn{X_2} \times \bn{X_1} \times X_0) + (X_3 \times \bn{X_2} \times X_1 \times \bn{X_0}) +
|
|
(X_3 \times \bn{X_2} \times X_1 \times X_0) + (X_3 \times X_2 \times \bn{X_1} \times \bn{X_0}) +
|
|
(X_3 \times X_2 \times \bn{X_1} \times X_0) + (X_3 \times X_2 \times X_1 \times \bn{X_0}) +
|
|
(X_3 \times X_2 \times X_1 \times X_0)$
|
|
\end{figure}
|
|
|
|
\subsection{Sub-question 3}
|
|
The maxterm expansion of the function above is clearly the best approach between the two,
|
|
since it contains fewer terms (and thus requires less logic gates).
|
|
|
|
\subsection{Sub-question 4}
|
|
Please find the Logisim file answering this question named \texttt{CA\_2.4\_Homework\_5.circ} in
|
|
the zip file.
|
|
|
|
\subsection{Sub-question 5}
|
|
Please find the Logisim file answering this question named \texttt{CA\_2.5\_Homework\_5.circ} in
|
|
the zip file.
|
|
|
|
\section{Question 3}
|
|
The bomb will not explode if either the first, the second or the fourth cable from the left
|
|
are cut. For the first and the second cable this happens because the NOR inside the circuit will
|
|
get at least a 1 as input, and therefore it will produce a 0 as output, pulling the final AND
|
|
output to 0. When the fourth cable is cut, the NOT will give always 0 as output and therefore
|
|
the final AND output will be always 0.
|
|
\end{document} |