CS 4341 — Digital Logic and Computer Design, Homework 2

Download PDF

3.10(a) A JK flip-flop receives a clock and two inputs, J and K. On the rising edge of the clock, it updates the output, Q. If J and K are both 0, Q retains its old value. If only J is 1, Q becomes 1. If only K is 1, Q becomes 0. If both J and K are 1, Q becomes the opposite of its present state. Construct a JK flip-flop using a D flip-flop and some combinational logic.

JKQQ’
0000
0011
0100
0110
1001
1011
1101
1110

3.22 Describe in words what the state machine in Figure 3.69 does. Using binary state encodings, complete a state transition table and output table for the FSM. Write Boolean equations for the next state and output and sketch a schematic of the FSM

If you recieve inputs and then in order, then Q becomes and then becomes 0. Otherwise, Q is 0.

S1S0ABS’1S’0
001X01
000X00
01X110
01X000
10XX00
S1S0Q
000
010
101

3.23 Describe in words what the state machine in Figure 3.70 does. Using binary state encodings, complete a state transition table and output table for the FSM. Write Boolean equations for the next state and output and sketch a schematic of the FSM

S1S0ABS’1S’0Output
001X010
000X000
01X1100
01X0000
1011101
1010000
1001000
1000000

Although this may at first glance seem more complicated (by not taking the don’t cares), it allows for simplification of the circuit by observing that the terms match up with those of the output.

3.24 Accidents are still occurring at the intersection of Academic Avenue and Bravado Boulevard. The football team is rushing into the intersection the moment light B turns green. They are colliding with sleep-deprived CS majors who stagger into the intersection just before light A turns red. Extend the traffic light controller from Section 3.4.1 so that both lights are red for 5 seconds before either light turns green again. Sketch your improved Moore machine state transition diagram, state encodings, state transition table, output table, next state and output equations, and your FSM schematic

S2S1S0TATBS’2S’1S’0LA1LA0LB1LB0
0000x0010010
0001x0000010
001xx0100110
010xx0111010
011x01001000
011x10111000
100xx1011001
101xx0001010

State encodings are same as in textbook. The SX is given by its numerical value and 0 is green, 1 is yellow, and 2 is red.

3.27 Gray codes have a useful property in that consecutive numbers differ in only a single bit position. Table 3.23 lists a 3-bit Gray code representing the numbers 0 to 7. Design a 3-bit modulo 8 Gray code counter FSM with no inputs and three outputs. (A modulo N counter counts from 0 to N − 1, then repeats. For example, a watch uses a modulo 60 counter for the minutes and seconds that counts from 0 to 59.) When reset, the output should be 000. On each clock edge, the output should advance to the next Gray code. After reaching 100, it should repeat with 000.

#S2S1S0S’2S’1S’0
0000001
1001011
2011010
3010110
4110111
5111101
6101100
7100000

3.31 Analyze the FSM shown in Figure 3.72. Write the state transition and output tables and sketch the state transition diagram. Describe in words what the FSM does.

S1S0XS’1S’0Q
000100
001110
010101
011101
100001
101011
110101
111101

This represents a finite state machine where if the current state is (i.e. one of the two current state bits is true), Q is 1. The next state behaviour can best be seen using 2 bits to represent the current state where is the combinational logic circuit in the circuit diagram provided. If is 0, will be 1 in the next state. If is 1, is set to the current value of . For , the next state is 1 if and the input

3.33 Ben Bitdiddle has designed the circuit in Figure 3.74 to compute a registered four-input XOR function. Each two-input XOR gate has a propagation delay of 100 ps and a contamination delay of 55 ps. Each flip-flop has a setup time of 60 ps, a hold time of 20 ps, a clock-to-Q maximum delay of 70 ps, and a clock-to-Q minimum delay of 50 ps.

If there is no clock skew, what is the maximum operating frequency of the circuit?

The maximum operating frequency of the circuit can be computed by first finding the minimum cycle time. In the worst case, the clock to Q delay is (i.e. its minimum, or the clock-to-Q contamination delay). Additionally, each gate must finish evaluating. This means that it can take up to for the XOR gates to finish evaluating. Finally, the setup time is . This implies that .

Taking the reciprocal, the maximum operating frequency of the circuit is

How much clock skew can the circuit tolerate if it must operate at 2 GHz?

If the circuit must operate at , then we may solve the following equation. Setting to , since we know that , we can subtract this to find that the maximum clock skew the circuit can tolerate is

How much clock skew can the circuit tolerate before it might experience a hold time violation?

In order to prevent a hold time violation, this inequality must hold: In other words, the time that the the output may start changing plus the time the output will actually change (based on the specific gates involved) minus how much sooner the output can change (depending on clock skew) must be after the hold time.

Rearranging, we get . Substituting, of clock skew.

Alyssa P. Hacker points out that she can redesign the combinational logic between the registers to be faster and tolerate more clock skew. Her improved circuit also uses three two-input XORs, but they are arranged differently. What is her circuit? What is its maximum frequency if there is no clock skew? How much clock skew can the circuit tolerate before it might experience a hold time violation?

The only thing which changes is the and . This can be used in the same calculations as before , giving a maximum frequency of . The circuit can tolerate of clock skew.

Used https://www.circuit-diagram.org/editorb/ for circuit diagrams.