Logic Design of Digital Systems Problem Set #3 SOlution

Description

1 SR latch (8+2 pts)

Consider the non-combinational circuit seen below, known as an SR latch, with inputs S; R and outputs Q; Q0 . Assume both NOR gates have identical contamination and propagation delays tCD; tP D respectively, and note that the two diagonal wires do not connect to each other.

R

S

Q

Q0

Figure 1: SR latch

1.0(a). (4 pts) Assume an initial condition for all t < 0 of S = R = Q = 0; Q0 = 1, and tCD = 1; tP D = 2. Draw a complete timing diagram for the following sequence of levels:

@t = 0: S ! 1

@t = 5: S ! 0

@t = 10: R ! 1

@t = 15: R ! 0

1.0(b). (4 pts) This is called an SR latch because a high value on the S input sets the output Q to 1, while a high value on the R input resets the output Q to 0; Q0 is the inverse of (NOT) Q. (What happens when both S and R are low?) De ne a dynamic discipline for this latch to ensure exactly this behavior.

1.0(c). (EXTRA CREDIT 2 pts) Recall from lecture that the D latch takes two inputs D; G; the output Q follows D when G is high, and holds its value when G is low. Build a D latch from an SR latch and any additional CMOS gates, and draw the resulting gate diagram.

2 Multiplier (15+3 pts)

Consider two 4-bit unsigned inputs A = A3A2A1A0; B = B3B2B1B0. Recall that their product can be written as the sum of partial products:
AB = B3 A 23 + B2 A 22 + B1 A 21 + B0 A 20 = B3 (A 23) + B2 (A 22) + B1 (A 21) + B0 (A 20).

2.0(a). (5 pts) Assume A and B have been loaded into D-registers. Sequentially generate each partial product by generating the lowest order partial product, then shifting A and B appropriately to load into their respective registers for the next clock cycle. Draw this circuit, built with any CMOS gates or muxes, along with the two D-registers. What width do these registers need to be?

2.0(b). (5 pts) Add to the above an accumulator, storing the running sum of the partial products in another D-register. You may use a ripple carry adder block.

2.0(c). (2 pts) Add to the above a one-bit output indicating when the complete product has been generated. You may use any CMOS gates or muxes.

2.0(d). (3 pts) Write out the timing constraints that must be met for this sequential system to be valid, in terms of tCD and tP D of each module in your circuit along with tSETUP and tHOLD of the D-registers.

2.0(e). (EXTRA CREDIT 3 pts) Add to the above a one-bit reset input and two 4-bit inputs for A and B, zeroing out the accumulator as well as loading A and B into their respective registers when the reset input is high. You may use any CMOS gates or muxes.
3 Vowel decoder (15 pts)

The relative frequencies of the vowels in the english language are (approximately) as follows1:

A = 20% E = 32% I = 17% O = 19% U = 7% Y = 5%

3.0(a). (2 pts) Come up with a variable-width Hu man encoding for these vowels, as well as an n-bit xed-width binary encoding (what is n?). Make sure the n-bit label n’b0 is not assigned to any value in the xed-width encoding.

3.0(b). (3 pts) Draw a state diagram for a Moore FSM decoder that has a one-bit input stream of Hu man-encoded vowels, and generates the n-bit binary encoded output when a complete variable-width code has been received, or n’b0 otherwise.

3.0(c). (3 pts) Draw a state diagram for a Mealy FSM decoder that has a one-bit input stream of Hu man-encoded vowels, and generates the n-bit binary encoded output when a complete variable-width code has been received, or n’b0 otherwise.

3.0(d). (2 pts) Draw the state transition table for the Mealy decoder of part 3.0(c), labeling each state with a binary value.

3.0(e). (5 pts) Implement the Mealy decoder of part 3.0(c) using a D-register to hold the current state, a D-register to gate the input, and muxes to generate the next state and output values.

4 Your turn (12 pts)

It’s often said that you don’t truly understand a subject until you can teach it. What was a topic that you struggled with so far in this class? Write and solve a pset problem that sheds light on this particular topic.