\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{1}

% 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/19/90}

\prob{1}

\subprob{1.A}

The truth table corresponding to this origami bird-like transfer
curve, using positive logic, is:

\begin{tabular}{cc|c} 
X & Y & Z \\ \hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\ 
\end{tabular}

\noindent This truth table represents the logical AND function.

\subprob{1.B}

Using negative logic for this same transfer curve, the truth table
looks like:

\begin{tabular}{cc|c} 
X & Y & Z \\ \hline
1 & 1 & 1 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
0 & 0 & 0 \\ 
\end{tabular}

\noindent This truth table represents the logical OR function.

\subprob{2.A}
\vspace{2in}

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

\mynewpage

\subprob{2.C}

No, because there's no room for the necessary forbidden zones, nor
does it give valid outputs for valid inputs.

\subprob{2.D}

$\log{}_2 3 = 1.585$ therefore the amount of information is 1 bit.

\subprob{2.E}

Three wires each with three possible values conveys 4 bits of
information. 

\beq
3 \cdot 3 \cdot 3 & = & 27 \\
\log{}_2 27 & = & 4 \; bits
\eeq

Four wires each with two possible values also conveys 4 bits of
information. 

\beq
2 \cdot 2 \cdot 2 \cdot 2 & = & 16 \\
\log{}_2 16 & = & 4 \;bits
\eeq

\subprob{2.F}

\beq
\frac{4 \; bits}{10e-3} \; s & = & 400 \; bits/s
\eeq

\subprob{2.G}

\beq
2 \cdot 2 \cdot 2 & = & 8 \\
\log{}_2 8 & = & 3 \; bits \\
\frac{3 \; bits}{10e-3} & = & 300 \; bits/s
\eeq

\subprob{3.A}
\vspace{2in}

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

\mynewpage

\subprob{3.C}
No, since part of the graph would go through the forbidden zone.
\vspace{1.5in}

\subprob{4}
Logic levels: 4.5 - 5.5 would be logical ``1'', 0 - 1.5 would be
logical ``0''.
\vspace{2in}

\prob{2}

The longest delay is found by tracing the longest path through the
logic circuit. The longest path through the circuit consists of five
gates. Therefore, the longest delay is $5t_{pd}$. 

Since the rise and fall times do not accumulate through cascaded lofic
devices, the maximum rise and fall times are just the rise and fall
times of the last gate of the circuit. Therefore, $t_{r,max} = t_r$
and $t_{f,max} = t_f$.

\prob{3}

\subprob{A} 253 = 011111101 in 2's complement; notice however that
this is {\em not} a 6-bit representation. 253 cannot be represented by
less than 8 bits in binary, or 9 bits in 2's complement.

34 = 0100010 in 2's complement; also not a 6-bit representation.

14 = 001110 in 2's complement

10 = 001010 in 2's complement

-1 = 111111 in 2's complement since 1 = 000001 in 2's complement and
therefore -1 = 111110 + 1 = 111111.

-254 = 100000010 in 2's complement 

-136 = 101111000 in 2's complement

-17 = 101111 in 2's complement

\subprob{B}
\vspace{2.5in}

\mynewpage

\subprob{C}
34 = 0x22

10 = 0xA

243 = 0xF3

17 = 0x11

\subprob{D}

a. $2^N = 2^6 = 64$

b. $2\cdot (2^{N-1}) = 2\cdot 32 = 64$

c. $2\cdot (2^{N-1}) - 1 = 2^6 - 1 = 63$

d. $2\cdot (2^{N-1}) - 1 = 2^6 - 1 = 63$

\subprob{E}

There are $4 \cdot 3 \cdot 3 \cdot 10 = 360$ possible combinations of
values that the scoreboard can have. This amount of information
requires $\log{}_2 360 = 8$ bits.

\prob{4}

\subprob{A}

i. $G = \bar{A}\cdot\bar{B}\cdot\bar{C} + \bar{A}\cdot\bar{B}\cdot C +
\bar{A}\cdot B \cdot C + A \cdot B \cdot \bar{C}$

ii. $G = \bar{A}\cdot\bar{B}\cdot C + \bar{A}\cdot B \cdot\bar{C} + A
\cdot \bar{B} \cdot C + A \cdot B \cdot \bar{C} + A \cdot B \cdot C$

\subprob{B}

i. 

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

\mynewpage

ii.

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

\subprob{C}

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

\vspace{.2in}
\beq 
f & = & \bar{A}\cdot\bar{B}\cdot C\cdot\bar{D} + \bar{A}\cdot\bar{B}\cdot
C \cdot D + A\cdot\bar{B}\cdot\bar{C}\cdot\bar{D} + A\cdot\bar{B}\cdot
\bar{C} \cdot D + \\ 
\mbox{} & \mbox{} & A\cdot\bar{B}\cdot C \bar{D} + A\cdot \bar{B}\cdot C 
\cdot D + A\cdot B\cdot \bar{C}\cdot D + A \cdot B \cdot C \cdot D 
\eeq

\subprob{D}
\vspace{2in}

\mynewpage

\subprob{E}

a.

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

\vspace{.15in}
b. $f = \overline{\overline{(\bar{A}\cdot B)}\cdot (B \cdot\bar{C})}$


\vspace{.15in}
c. Using deMorgan's equivalences:

\beq
f & = & \overline{(A + \bar{B})} + (\bar{B} + C) = \overline{A + \bar{B}} 
+ \bar{B} + C
\eeq

\end{document}


