EECS 31/CSE 31/ICS 151 Homework 5 Questions with Strategies

View Questions Only
View Questions with Solutions

Problem 1

Question

(SR latch) Draw the output and timing diagram of a (a) NOR and (b) NAND implementation of an SR latch for the input signals depicted in Figure P6.2.

Strategy

1. Draw the logic schematic of SR latches with NOR or NAND gates.
2. Propagate the change on inputs S or R to output Q by adding gate delays along the path.
3. Indicate the output delay for each change of input signals on the Q wareform.

Problem 2

Question

(SR latch) Derive an implementation of a clocked SR latch using only:

1. NOR gates
2. NAND gates
3. AND, OR and INVERT gates

Strategy

1. Write out the Boolean expressions for Q and Q' outputs.
2. Implement the Boolean expressions with the required gates.
3. Draw the logic schematic according to the Boolean expressions.

Problem 3

Question

(JK flip-flops) Derive the output waveforms of a master-slave JK flip-flop for the input waveforms depicted in Figure P6.6.

Strategy

1. Draw the characteristic table for JK flip-flops.
2. According to the characteristic table and the J, K and Clk waveform, draw the Q waveform.
3. Indicate delays on the timing diagram.

Problem 4

Question

(Sequential Analysis) Derive a (a) state table and (b) state diagram for the sequential circuit shown in Figure P6.9

Strategy

1. Write out next state equations for the sequential circuit.
2. Draw the state table according to the next state equations.
3. Draw the state diagram according to the state table.

Note: Consider the reset.

Problem 5

Question

(State minimization) Derive the minimal-state FSM from the state/output table shown in Figure P6.12.

PRESENT STATE	NEXT STATE
	x = 0	x = 1
S0	S0/1	S4/0
S1	S0/0	S4/0
S2	S1/0	S5/0
S3	S1/0	S5/0
S4	S2/0	S6/1
S5	S2/0	S6/1
S6	S3/0	S7/1
S7	S3/0	S7/1

Strategy

1. Create the implication table.
2. Cross out all the squares that represent state pairs that have a different output for at least one set of input values.
3. Check for next state euqivalence. If it has the same next states for every set of input values, it is equal, else check the state pairs it depend on. If all of these state pairs are equal, the current state pair is equal, else it is not equal.
4. Group all the equivalent states into equivalence classes, rewrite the state/output table.

Problem 6

Question

(Sequential Synthesis) Design a counter that counts in the sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,..., using natural binary encoding and D-type flip-flops.

Strategy

1. Develop state diagram and next state table.
2. Using natural binary encoding, derive a next-state (input) equations for each D flip-flops.
3. Derive logic schematic.

Problem 7

Question

(Sequential Synthesis) Design a recognizer that recognizes an input sequence that has at least three 1's. The recognizer has a single input X, and a single output Y, in addition to an asynchronous Reset signal. The recognizer sets the output Y to 1 if the input signal X was equal to 1 in at least 3 clock cycles after the Reset was disasserted. For the above recognizer described above:

1. Devise the state diagram.
2. Minimize the number of states.
3. Encode the states to minimize the combinatorial logic.
4. Draw a schematic diagram using D flip-flops.

Strategy

1. Define states and devise the state diagram.
2. Draw the state/output transition table, minimize the states using implication table.
3. Encode the states to minimize the combinatorial logic.
4. Derive next-state table with the encoding states.
5. Write output/state equations.
6. Draw logic schematic.

Problem 8

Question

Sequential Synthesis) Design a simplified traffic-light controller that switches traffic lights on a crossing where a north-south (NS) street intersects an east-west (EW) street. The input to the controller is the WALK button pushed by pedestrians who want to cross the street. The outputs are two signals NS and EW that control the traffic lights in NS and EW directions. When NS or EW are 0, the red light is on and when they are 1, the green light is on. When there are no pedestrians, NS=0 and EW=1 for 1 minute, followed by NS=1 and EW=0 for 1 minute and so on. When a WALK button is pushed, NS and EW both come 1 for a minute when the present minute expires. After that the NS and EW signals continue alternating. For the traffic-light controller:

1. Develop a state diagram and state/output table.
2. Minimize the number of states.
3. Encode the states.
4. Draw a schematic diagram.

Strategy

1. Define states and devise the state diagram.
2. Draw the state/output transition table, minimize the states using implication table.
3. Encode the states.
4. Derive next-state table with the encoding states.
5. Write output/state transition equations.
6. Draw logic schematic.