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

View Questions Only
View Questions with Strategies

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.

Figure P6.2

Figure P6.2

Solution

Problem 6 Output and Timing Diagram

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

Solution

    1. Write Boolean equations for Q and Q' of clocked SR latch. 
       Q(next)  = (RC + (Q'))'
 Q'(next) = (SC + Q)'
    2. Use NOR to express the above equations. 
       Q(next)  = ((R' + C')' + (Q'))'
 Q'(next) = ((S' + C') + Q)'
    3. Draw the logic schematic.

      NOR gates Schematic

    1. Write Boolean equations for Q and Q' of clocked SR latch. 
       Q(next)  = (RC + (Q'))'
 Q'(next) = (SC + Q)'
    2. Use NAND to express the above equations. 
       Q(next)  = ((RC)'(Q')')''
 Q'(next) = ((SC)'Q')''
    3. Draw the logic schematic.

      NAND gates Schematic

    1. Write Boolean equations for Q and Q' of clocked SR latch. 
       Q(next)  = (RC + (Q'))'
 Q'(next) = (SC + Q)'
    2. Use AND, OR and NOT to express the above equations. 
       Q(next)  = (RC + (Q'))'
 Q'(next) = (SC + Q)'
    3. Draw the logic schematic.

      AND, OR and INVERT gates Schematic

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.

Figure P6.6

Figure P6.6

Solution

  1. Develop characteristic table for JK flip-flop.
    J K Q(next)
    0 0 Q
    0 1 0
    1 0 1
    1 1 Q'
  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 3 Characteristics Table

Problem 4

Question

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

Figure P6.9

Figure P6.9

Solution

  1. Write out next state equations for the sequential circuit. 
     Q0(next) = Q1
 Q1(next) = Q2
 Q2(next) = Q3
 Q3(next) = Q0'
  2. Draw the state table according to the next state equations.
    R Q3 Q2 Q1 Q0 Q3(next) Q2(next) Q1(next) Q0(next)
    0 X X X X 0 0 0 0
    1 0 0 0 0 1 0 0 0
    1 0 0 0 1 0 0 0 0
    1 0 0 1 0 1 0 0 1
    1 0 0 1 1 0 0 0 1
    1 0 1 0 0 1 0 1 0
    1 0 1 0 1 0 0 1 0
    1 0 1 1 0 1 0 1 1
    1 0 1 1 1 0 0 1 1
    1 1 0 0 0 1 1 0 0
    1 1 0 0 1 0 1 0 0
    1 1 0 1 0 1 1 0 1
    1 1 0 1 1 0 1 0 1
    1 1 1 0 0 1 1 1 0
    1 1 1 0 1 0 1 1 0
    1 1 1 1 0 1 1 1 1
    1 1 1 1 1 0 1 1 1
  3. Draw the state diagram according to the state table.

    Problem 4 State Diagram

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

Figure P6.12

Solution

(1), (2), (3) Using implication table, find equivalent states.

Problem 5 Implication Table

(4) Group all the equivalent states into equivalence classes, rewrite the state/output table.

G0 = {s0}, G1 = {s1}, G2 = {s2, s3}, G3{s4, s5, s6, s7}

PRESENT STATE NEXT STATE
x = 0 x = 1
G0 G0/1 G3/0
G1 G0/0 G3/0
G2 G1/0 G3/0
G3 G2/0 G3/1

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.

Solution

  1. In order to implement this modulo-10 counter, we will need four flip-flops labeled: Q3, Q2, Q1, Q0. Using natural binary encoding, we can derive a state trasitions table:

    Problem 6 flip-flop gates

  2. From the transitions tabel, write transitions equations. 
     Q3(next) = Q2Q1Q0 + Q3Q1'Q0'
 Q2(next) = Q2'Q1Q0 + Q2Q1' + Q2Q0'
 Q1(next) = Q3'Q1'Q0 +Q1Q0'
 Q0(next) = Q0'
  3. Derive logic schematic.

    Problem 6 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.

Solution

  1. Define the states as the following:

    • S0: 0 ones received,
    • S1: 1 ones received,
    • S2: 2 ones received,
    • S3: 3 or more ones received.

    The state diagram is:

    Problem 7 state diagram

  2. The state/output table is:
    PRESENT STATE NEXT STATE
    Walk = 0 Walk = 1
    S0 S0/0 S1/0
    S1 S1/0 S2/0
    S2 S2/0 S3/0
    S3 S3/1 S3/1

    From the state/output table, we can minimize the state number by using implication table.

    Problem 7 implication table

  3. The equations defining the implimentation can be describe as: 
     D1 = Q1 + Q0X
 D0 = Q0X' + Q1'X
 Y = Q1Q0'
  4. Draw logic schematic from the eqations using D flip-flops:

    Problem 7 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.

Solution

  1. Define the states as the following:

     S0: ( NS = 0, EW = 1)
 S1: ( NS = 1, EW = 0)
 S2: ( NS = 1, EW = 1)

    The state diagram is:

    Problem 8 state diagram

  2. The state/output table is:

    PRESENT STATE NEXT STATE
    Walk = 0 Walk = 1
    S0 S1/01 S2/01
    S1 S0/10 S2/10
    S2 S0/11 S2/11

    As you can see below, the number of states is minimal.

    Problem 8 number of states

  3. Using minimum-bit-change strategy, get the minimizing state encoding as following: 
     S0 = 00
 S1 = 01
 S2 = 10
  4. After state encoding, the state/output stable will be:
    PRESENT STATE NEXT STATE
    Walk = 0 Walk = 1
    00 01/01 10/01
    01 00/10 10/10
    11 XX/XX XX/XX
    10 00/11 10/11

  5. The equations defining the implimentation can be describe as:

     D0 = Q1'Q0'Walk'
 D1 = Walk
 NS = Q0 + Q1
 EW = Q0'

  6. Draw logic schematic from the eqations using D flip-flops:

    Problem 8 logic schematic