% \documentclass{article} \documentclass[twocolumn]{article} \setlength{\oddsidemargin}{-0.5in} \setlength{\evensidemargin}{-0.5in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\textwidth}{7.0in} \setlength{\textheight}{9.5in} \setlength{\parindent}{0in} \setlength{\parskip}{0.05in} \setlength{\columnseprule}{0.3pt} \usepackage{fancyvrb} \usepackage{relsize} \begin{document} Name: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \textbf{Directions: Work only on this sheet (on both sides, if needed); do not turn in any supplementary sheets of paper. There is actually plenty of room for your answers, as long as you organize yourself BEFORE starting writing. In order to get full credit, SHOW YOUR WORK.} {\bf 1.} (5) Fill in the blank: The type of component we use to connect/disconnect one part of a circuit from the rest of the circuit is a \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_. {\bf 2.} (5) Show the boolean expression for the (nonminimal) simplification indicated in Fig. 2.19(a) of Dandamudi. {\bf 3.} (5) Use the de Morgan property to derive a sum-of-products expression for $\overline{(\bar{A}+\bar{C}+\bar{D})(\bar{B}+\bar{E})}$. Do not minimize. {\bf 4.} (10) Fill in the blanks: By using a NAND gate instead of an AND together with a NOT, we use fewer \_\_\_\_\_\_\_\_\_\_\_. In fact the count for just an AND gate alone (not even accounting for the NOT) is \_\_\_\_, while for NAND it is \_\_\_\_. {\bf 5.} Consider Example 2 in May's handout on five-variable Karnaugh maps. The minimal boolean expression for F turned out to be $F = \bar{C} \bar{E} + CDE + ADE + \bar{A} B \bar{E}$. \begin{itemize} \item [(a)] (5) Suppose term 1 were to be added to F, so that $F = \sum (0, 1, 2, 7, ..., 31)$. What would be the new minimal boolean expression for F? \item [(b)] (10) Suppose term 24 were to be deleted from F (and term 1 {\bf not} added), so that $F = \sum (0, 2, 7, ..., 23, 26, 27, 31)$. What would be the new minimal boolean expression for F? \end{itemize} {\bf 6.} (15) Suppose we wish to make a three-bit ``counter'' which adds 3 (mod 8), instead of 1, to the count at each clock pulse. Show how the Karnaugh map for $J_B$ on p.129 of Dandamudi would change, and give the minimal boolean expression for $J_B$. {\bf 7.} (10) A bus serves a function similar to that of a combined multiplexer and demultiplexer. Consider the four-register system on p.16 of our PLN unit on digital logic. Assume that R2 and R3 are ordinary registers, not private ones. Ignore the ALU; we are simply interested in register transfer, i.e. copying some Ri to some Rj. Consider the 4-to-1 MUX on p.6, with inputs D3, D2, D1, D0, A1 and A0, and output Z. Think of a corresponding 1-to-4 DEMUX with inputs Y, U1, U0, and outputs V3, V2, V1 and V0. Fill in the blanks: The bus lines \_\_\_\_\_\_\_\_\_ play a role analogous to A1 and A0, and the bus lines \_\_\_\_\_\_\_\_\_ play a role analogous to U1 and U0. {\bf 8.} (15) Show how to use a single 7400 chip to implement the expression E = AB+CD. Express your answer as a set of boolean equations, as follows. We will refer to the pins on the 7400 as $P_i$, so that for example $P_3$ means pin 3. Your equations must use only the $P_i$, A, B, C, D and E. For example, if you wish pin 2 to take input from A, write $P_2 = A$. {\bf 9.} (20) Let's use the term {\it basic gates} to mean AND, OR and NOT, and suppose we are restricted to use only these gates. (Not too different from the situation of a PLA.) The implementation of the SR latch on p.114 of Dandamudi could be done with four basic gates---two ORs and two NOTs. If we do not need a $\bar{Q}$ output, that count of four basic gates can be reduced to two if we allow either S or R to be specified as active-low. Show how to do this, i.e. implement an SR latch using two basic gates. Express your answer in the form of a clear picture. {\bf Solutions:} {\bf 1.} tri-state device {\bf 2.} $BD + \bar{A} B \bar{C} + A \bar{C} D + \bar{A} C D + ABC$ {\bf 3.} ACD + BE {\bf 4.} transistors; 3; 2 {\bf 5.a} add $\bar{A} \bar{B} \bar{C} \bar{D}$ {\bf 5.b} delete $\bar{C} \bar{E}$, and add (for instance) $\bar{C} D \bar{E} +\bar{A} \bar{C} \bar{E}$ {\bf 6.} It is important to look at the table for $J_B$ and $K_B$ together, not just $J_B$ alone, since the don't-cares for $J_B$ depend on $K_B$. Then one obtains: \begin{center} \begin{tabular}{|c||c|c|c|c|} \hline \begin{tabular}{cc} \ & B,C \\ A & \ \end{tabular} & 00 & 01 & 11 & 10 \\ \hline \hline 0 & 1 & 0 & d & d \\ \hline 1 & 1 & 0 & d & d \\ \hline \end{tabular} \end{center} The simplest circuit comes from setting the BC=11 don't-care entries to 0s and the BC=10 entries to 1s: \begin{center} \begin{tabular}{|c||c|c|c|c|} \hline \begin{tabular}{cc} \ & B,C \\ A & \ \end{tabular} & 00 & 01 & 11 & 10 \\ \hline \hline 0 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 0 & 0 & 1 \\ \hline \end{tabular} \end{center} resulting in $J_B = \bar{C}$. {\bf 7.} AS1, AS0; AD1, AD0 {\bf 8.} Actually, this was an example on p.75 of Dandamudi, showing how to implement AB+CD in just three NANDs so that just one 7400 would suffice for the circuit. So, for example, set $$ P_1 = A, ~ P_2 = B, ~ P_{13} = P_3 $$ $$ P_4 = C, ~ P_5 = D, ~ P_{12} = P_6 $$ E is then the output $P_{11}$. {\bf 9.} We want $Q_{new}$, the new Q, to be a function of S, R and $Q_{old}$, the old Q: \begin{center} \begin{tabular}{|r|r|r|r|} \hline S & R & $Q_{old}$ & $Q_{new}$ \\ \hline \hline 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & d \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 \\ \hline 1 & 1 & 1 & d \\ \hline 1 & 0 & 1 & 1 \\ \hline \end{tabular} \end{center} We then get: \begin{center} \begin{tabular}{|c||c|c|c|c|} \hline \begin{tabular}{cc} \ & S,R \\ $Q_{old}$ & \ \end{tabular} & 00 & 01 & 11 & 10 \\ \hline \hline 0 & 0 & 0 & d & 1 \\ \hline 1 & 1 & 0 & d & 1 \\ \hline \end{tabular} \end{center} Taking both don't-cares to be 0s, we get $$ Q_{new} = S \bar{R} + Q \bar{R} = (Q+S) \bar{R} $$ So, by specifying R to active-low, we need just one OR and one AND. Other two-gate solutions are possible, but note that a solution needs to satisfy all rows of the truth table (except the don't-cares). In particular, the circuit must {\it maintain} the values of Q in the case in which neither S nor R is asserted. \end{document}