UIT2201: CS & the IT Revolution
Tutorial Set 9 (Spring 2013)

(D-Problems discussed on Wednesday, 27-Mar-2013)
(Q-Problems due on Monday, 01-Apr-2013 -- before Lecture )


Discussion Problems: -- Prepare (individually) for tutorial discussion.

T9-D1: (Multiplexor Circuits) [2- and 4-input MUXes]
(a) [2-input MUX] Read up "design of multiplexor circuits" in Sec 4.5 of [SG3].
Explain the working of a 2-input multiplexor circuit and the role of the "selector line".
(b) [4-input MUX] (Prob. 23 of Ch.4 of [SG3].)
Design a four-input multiplexor circuit. Use the design of the the two-input MUX as a guide.
(For simplicity, you can make use of 3-input OR/AND gates.)

T9-D2: (Decoder Circuits)
Read up the design of decoder circuits in Ch4.5 of [SG3] and lecture notes.
(a) Explain the working of a 2-to-4 decoder circuit shown in Figure 4.29 of [SG3].
(b) What does a 1-to-2 decoder circuit look like?

T9-D3: (MAR) (Modified from Practice Prob 1 & 2 of Ch-5.2.1 of [SG].)
Assume that our memory unit is organized as a 1,024 x 4,096 two dimensional array.
(a) How big does the MAR register have to be?
(b) How many bits of the MAR is used for row decoder and column decoder?

T9-D4: (ALU and MUX) (Modified from Problem 9 of Ch.4 of [SG].)
Assume that we have an arithmetic/logic unit (ALU) that can carry out 24 distinct operations. Describe exactly what kind of multiplexor circuit would be needed to select exactly one of those 24 operations.
(Note: The ALU in lectures (Figure 5.12, p210 of [SG]) only carries out 4 distinct operations.)

T9-D5: (Eliza and other Chatterboxes)
[First, read lecture notes on AI, the slides on early AI-program Eliza.]
(a) Do a web-search on "Eliza Psychiatrist" for Eliza-like programs on the web. Some are listed in 2013-06-AI-Eliza.txt.
(b) Then, use the same input text sequence as the one given in the lecture notes and see the difference in the responses given by the different Eliza-like programs.
(c) Then, try it out with your own Eliza-like "conversation" using your own sequence of questions.


Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me. Not just soft copy via email.)

T9-Q1: (10 points) [8-input multiplexor circuit]
Extend T9-D1 to design an 8-input MUX. It will have three input lines.
(See helpful pointer above on drawing circuits and for simplicity, you can make use of 3-input OR/AND gates.)
[Helpful Pointer: In these circuit diagrams, it is useful to draw all the input signals (both X and ~X) as vertical lines on the left side of the circuit diagrams -- as shown in Figures 4.29 or 4.26. This makes your circuit neater and easier to "debug" or spot mistakes.]


T9-Q2: (10 points) [3-to-8 Decoder Circuit]
Using T9-D2 as a guide, design and draw the circuit diagram for a 3-to-8 decoder circuit.
(Hint: Label your output lines 0,1,2,...,7 and your input lines (address or decoder) lines s2, s1, s0 so that if the binary number represented by s2,s1,s0 is n, then the n-th line is selected.)

T9-Q3: (5 points) (modified from 2008 Quiz 2)
(a) If the MAR register contains the binary number 0011 1010 1011 0101 1101, what is the size of the memory (how many bytes)?
(b) If the memory is organized in a two-dimensional square, what would its dimensions be? And how many bits for the row selector, column selector?

T9-Q4: (5 points) (FUN -- Annotating your Eliza "conversation")
Using the Eliza Chat bot from http://nlp-addiction.com/eliza/ carry out the second "conversation" as suggested in the notes 2013-06-AI-Eliza.txt. Then annotate the responses from Eliza (like the annotation given in the lecture notes) with your guess of what Eliza "did" to give out those responses.


A-Problems: OPTIONAL Challenging Problems for Further Exploration

A7-2013: (Limits of Floating Point Numbers) For 64-bit computers, if we use 53 bits to represent the mantissa (sign/magnitude) and 11 bits to represent the exponent (also sign/magnitude), we know that we can only represent a small subset of the real numbers. The gap (i.e., difference in absolute value) between two "consecutive" representable real numbers also varies.
(a) What is the largest number (and smallest number) that can be represented.
(b) What is the smallest gap between two consecutive real numbers? What is the largest gap between any two consecutive real numbers?
[For some details on floating points, you can see http://en.wikipedia.org/wiki/Floating_point ]

A8-2013: (Faster ADD circuits)
The n-bit ADD circuit given in Ch-4.4.3 of [SG] is called a ripple carry adder since the carry bit ripples through the individual 1-bit ADD circuits, one step at a time from the 0th bit to the (n-1)st bit. It therefore takes a total of n time steps to complete the addition, and for large n (say n=32 or 64), this makes for a rather slow n-bit ADD circuit.
Design a faster n-bit ADD circuit that takes only lg n time steps.
(Note: You may have to use more gates to achieve this -- trade off area for speed.)


UIT2201: CS & IT Revolution; (Spring 2013); A/P Leong HW