\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{2}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{9/26/90}

\prob{1}

\subprob{A}

\begin{tabular}{c|c|c|c|c|c}
\multicolumn{3}{r|}{$\overline{A}$} & \multicolumn{3}{l}{A} \\ \cline{2-5}
\mbox{} & 1 & 0 & 1 & 1 & $\overline{D}$ \\ \cline{2-6}
$\overline{C}$ & 0 & 1 & 1 & 1 & D \\ \cline{1-5} 
C & 1 & 1 & 1 & 1 & \mbox{} \\ \cline{2-6}
\mbox{} & 1 & 0 & 0 & 1 & $\overline{D}$ \\ \cline{2-5}
\multicolumn{2}{r|}{$\overline{B}$} & \multicolumn{2}{c|}{B} & 
\multicolumn{2}{l}{$\overline{B}$} 
\end{tabular}

\vspace*{-.5in}
\beq
\hspace*{1.5in} A\cdot B\cdot \overline{C} + A\cdot\overline{B} +
B\cdot D + \overline{B}\cdot\overline{D} + C\cdot D
\eeq

\vspace{.5in}
\begin{tabular}{c|c|c|c|c|c}
\multicolumn{3}{r|}{$\overline{A}$} & \multicolumn{3}{l}{A} \\ \cline{2-5}
\mbox{} & 1 & 0 & 1 & 1 & $\overline{D}$ \\ \cline{2-6}
$\overline{C}$ & 1 & 1 & 1 & 1 & D \\ \cline{1-5} 
C & 0 & 1 & X & 0 & \mbox{} \\ \cline{2-6}
\mbox{} & 1 & 1 & X & 1 & $\overline{D}$ \\ \cline{2-5}
\multicolumn{2}{r|}{$\overline{B}$} & \multicolumn{2}{c|}{B} & 
\multicolumn{2}{l}{$\overline{B}$} 
\end{tabular}

\vspace*{-.5in}
\beq
\hspace*{1.5in} A\cdot\overline{C}\cdot D +
\overline{A}\cdot\overline{C}\cdot D + 
B\cdot C + \overline{B}\cdot\overline{C} + C\cdot D
\eeq

\vspace{.3in}
\subprob{B}

\beq
f(A,B,C,D) & = & A\cdot B\cdot \overline{C} + A\cdot\overline{B} +
B\cdot D + \overline{B}\cdot\overline{D} + C\cdot D
\eeq

\begin{center}
\begin{tabular}{cccc|c||cccc|c} \hline
A & B & C & D & f & A & B & C & D & f \\ \hline
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
\end{tabular}
\end{center}

Multiplexer to implement this function:

\vspace{3.5in}
\special{psfile=mux1.ps}

\mynewpage

\subprob{C}

Truth table for the original diagram:

\begin{center}
\begin{tabular}{ccc|c||ccc|c} \hline
A & B & C & f & A & B & C & f \\ \hline
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \hline
\end{tabular}
\end{center}

Replacing the NANDs with NORs and inverting the inputs:

\vspace{2in}

This yields the intermediate output $f_i$. The truth table shows the
relationship between f (from the original truth table) and $f_i$:

\begin{center}
\begin{tabular}{ccc|c|c||ccc|c|c} \hline
A & B & C & $f_i$ & f & A & B & C & $f_i$ & f \\ \hline
0 & 0 & 0 &   1   & 0 & 1 & 0 & 0 &   1   & 0 \\
0 & 0 & 1 &   0   & 1 & 1 & 0 & 1 &   0   & 1 \\
0 & 1 & 0 &   1   & 0 & 1 & 1 & 0 &   1   & 0 \\
0 & 1 & 1 &   0   & 1 & 1 & 1 & 1 &   1   & 0  \\ \hline
\end{tabular}
\end{center}
 
Therefore, it appears that all that is needed now is to invert the
output $f_i$ to get the original f. So, the final diagram looks like:

\vspace{2in}

By the fact that there are non-zero propagation delays through
the NOR gates and by the fact that the path from C to NOR gates 2 and
3 is longer than the path from A to 2 and also from B to 3, there seem
to be potential hazards in this logic circuit. One way to fix this
would be to put an additional gate in A's path to 2 and B's path to 3.

\mynewpage

To pass through the values of A and B using a NOR gate requires that
one of its inputs be a constant 1. So, the new hazard-free logic
circuit looks thusly:

\vspace{2in}

\subprob{D}

One way to implement the ROM for this logic function is like this:

\vspace{3in}
\special{psfile=rom1.ps}

\prob{2}

\subprob{3.17}

Boolean functions involve sums of products, products of sums, and
negations. Sums of products and products of sums can be implemented
using just AND and OR gates. However, to get the negation function, an
inverter is needed. An inverter cannot be built out of simple AND and
OR gates. For example, the simple Boolean function $f(A) =
\overline{A}$ cannot be implemented using ANDs and ORs.

\subprob{3.18}

A hazard can be found in a simple logic circuit consisting of one
input, one output, and only NAND gates. Take this circuit for example:

\mynewpage

\vspace{1in}

It computes the constant 1 function given any input, i.e. $f(A) =
A\cdot \overline{A} = 1$. However, when A goes from 0 to 1, the output
goes through an intermediate value of 0 before returning to its
correct value of 1.

\prob{3}

\subprob{A} $T_{min} = t_{pd} + t_s + t_{pC-Q}$

\subprob{B} At minimum, $t_s$

\subprob{C} At minimum, $t_h$

\subprob{D} $t_{pC-Q} + t_{pd}$

\prob{4}

\subprob{5.8} Implementing a $N$-input Boolean function requires a $2^N$
bit ROM.

\subprob{5.9} The ROM can be broken up into $m$ sub-ROMs, each of which
computes one of the outputs. Each of these sub-roms has $n$ inputs and 1
output and therefore requires $2^n$ bits. Therefore, an $n$-input and
$m$-output ROM requires $m\cdot 2^n$ bits.

\prob{5}

\subprob{A} First of all, it can be noted that if $b_{15} = 0$ all that
has to be done is to carry through $b_{15} \cdot \cdot \cdot b_0$
unchanged to the output. If, however, $b_{15} = 1$ then $b_{15}$ gets
carried through as the sign bit $S_{16}$ and $b_{14} \cdot \cdot \cdot
b_0$ gets converted from a 2's complement number into a magnitude.
This is done by inverting each bit and adding 1. Inverting or not
inverting based on $b_{15}$ can be done using an XOR gate. The adding
of the 1 to the number represented by $b_{14} \cdot \cdot \cdot b_0$
can be done using adders. The whole logic circuit for this {\em
absolute value box} looks like so:

\mynewpage

\subprob{B} Implementing a 16-bit priority encoder using 8-bit
priority encoders and logic gates:

To find $E_0$ for the 16-bit priority encoder:

\vspace{.2in}
\begin{tabular}{cc|c}\hline
$E_H$ & $E_L$ & $E_0$ \\ \hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\ \hline
\end{tabular}

\vspace{.2in}
To find $A_3 \cdot \cdot \cdot A_0$:

\vspace{.2in}
\begin{tabular}{c|c}\hline
$E_h$ & $A_n$ \\ \hline
0 & $A_{n,H}$ \\
1 & $A_{n,L}$ \\ \hline
\end{tabular}

\vspace{4in}

\subprob{C} The 16-bit priority encoder can be used to extract the
base 4 exponent since it will indicate the highest 1 that appears in
the number. However, since we are using base 4, we want which group of
2 bits the highest 1 is in. Thus, we divide the encoder output in half
by dropping the last bit of the output $A_0$. 

\vspace{2in}
\special{psfile=exp.ps}

\mynewpage

\subprob{D} A bit of fiddling with multiplexers turned up this way to
find the mantissa and thus completing the device. {\em Enjoy.}

\vspace{9in}
\special{psfile=mantissa.ps}

\end{document}


