(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.
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.)