【深入理解计算机系统】 四:顺序逻辑电路

5.1. The Clock

The circuits implemented only with simple digital gates such as NAND, AND, OR, inverters, etc., are combinational circuits meaning that once a combination of values is set at the inputs, the output is either zero or one depending on it's truth table. The time it takes for the circuit to react to a change in the inputs is almost negligible (although designers care much about reducing it!).

Another way to look at this property of the combinational circuits is that if the value of the inputs changes, they output forgets its value immediately to adapt to the new result. In other words, the circuit does not remember the previous input combinations once it changes. This is an acceptable behaviour for some systems, but totally inappropriate for others.

Consider the following example. You are about to cross a street with a traffic light for the cars, and another one for pedestrians. The light is green for the cars, and you must press a button to request the car light to turn red, and the pedestrian light to turn green. The traffic light will not change until you press the button. Now let us assume that we use a combinational circuit to detect you pressing the button. Suppose it is a circuit that produces a one on its output if the button is pressed, and a zero if it is not pressed. With this functionality, you must keep pressing the button to cross the intersection. Depressing the button is a change in the input of your combinational circuit, and therefore, it will produce a change in the output. The light does not change.

This behaviour is not acceptable for this system. We want the system to remember that we pressed the button. In other words, the digital circuit should detect a change in an input signal, produce an output, and even though the input change again, maintain the value of the output in time. This is precisely the behaviour of the sequential digital circuits

A sequential digital circuit is a system in which, under certain conditions, the value of the outputs change depending on the inputs, or they remain unchanged (they are remembered) over time.

 

The behaviour of these new circuits is clearly more complex than the combinational circuits. The system works in two modes: either ignoring changes in the input values and remembering the last result; or paying attention to these inputs and adjusting the output accordingly. How do these circuits select between these two modes of operation?

The signal that forces a sequential circuit to behave in one of the two modes is generically known as the clock. Thus, every sequential circuit has a signal called the clock that signals when to pay attention to the value of the inputs and change the output, and when to ignore the inputs and maintain the value of the output.

The clock signal used in digital circuits is typically a square signal like the one shown in the following figure.

【深入理解计算机系统】 四:顺序逻辑电路

Clock signal used by sequential circuits


【深入理解计算机系统】 四:顺序逻辑电路 Note

When representing signals that evolve over time, we will assume always that time flows from left to right. So, the evolution of a digital signal over time will be a horizontal line with two levels, high and low. This representation is used frequently with sequential circuits.


The most important properties of this signal are:

  • Over time, the value of this signal oscillates from a high level to a low level.
  • The transitions from high to low levels, and vice versa, occur almost instantaneously and are called falling edge and rising edge respectively.
  • The period of a clock, usually represented by  【深入理解计算机系统】 四:顺序逻辑电路, is the time it takes the signal to make a full transition (that is, from low to high, and back to low). The frequency of a clock, usually represented by 【深入理解计算机系统】 四:顺序逻辑电路f, is the inverse of its period, that is【深入理解计算机系统】 四:顺序逻辑电路The frequency of a clock signal can be seen also as the speed at which it switches between high and low values. If a digital circuit is operating with a 5 Ghz clock, it means the signal is making 【深入理解计算机系统】 四:顺序逻辑电路 full transitions (from low to high and back to low) per second.

The following figure shows a generic representation of a sequential circuit.

【深入理解计算机系统】 四:顺序逻辑电路

Generic sequential circuit with the clock as additional input

The behaviour is this new type of circuits is as follows:

  • At a certain instant marked by the clock, the circuit behaves as a regular combinational circuit and the outputs take the value derived from the inputs. We will call this instance evaluation time.
  • At any other times, the value of the inputs are ignored, and the outputs remain with the values calculated in the previous instant. We will call this instance memory time.

This last step is why we say that sequential circuits are those that have memory, as they can remember the values that occurred at a previous instance. Since the clock is a periodic signal, we then can assume that a sequential circuit is continuously changing from evaluation time to memory time at a pace defined by the clock signal.

As you can see, this type of circuit is the one needed to control the traffic light in the previous example. If a pedestrian pushes the button, the circuit can store and remember that value so that the light will then change to stop the cars and allow the crossing.

5.1.1. Level-Sensitive Sequential Circuits

But when exactly is a sequential circuit paying attention to its inputs or simply remembering the last value of the outputs? Currently there are two types of sequential circuits: those sensitive to a level; and those sensitive to an edge. Those sensitive to a level can be further sub-divided into those sensitive to a high level and those sensitive to a low level.

A high level sensitive sequential circuit is one in which the evaluation time occurs when the clock is at a high level. At any other time, the outputs are fixed to the values of the previous evaluation time.

Conversely, a low level sensitive sequential circuit is one in which the evaluation time occurs when the clock is at a low level. At any other time, the outputs are fixed to the values of the previous evaluation time.

The following figure shows the evaluation and memory periods for level sensitive sequential circuits and the convention to represent their clock signal (the presence or absence of a circle in the clock input).

【深入理解计算机系统】 四:顺序逻辑电路

Stages of the Level Sensitive Clock

Review questions for 5.1.1 Level-Sensitive Sequential Circuits

5.1.2. Edge-Sensitive Sequential Circuits

The second type of sequential circuits are those that have a much shorter evaluation time. Instead of using the time the clock is either high or low, they evaluate the inputs when the clock makes a transition. In other words, the inputs are only considered when the clock is in a raising edge, or in a falling edge. As in the case of the level sensitive circuits, there are two types, those sensitive to a raising edge, and those sensitive to a falling edge.

The following figure show the evolution and memory periods for edge sensitive sequential circuits and the convention to represent the clock signal (see the circle in the clock input for the falling edge sensitive sequential circuit).

【深入理解计算机系统】 四:顺序逻辑电路

Stages of the Edge Sensitive Clock

Review questions for 5.1.2 Edge-Sensitive Sequential Circuits 

5.1.3. Summary of Sensitivity in Sequential Circuits

The following figure shows the behaviour of the four types of sequential circuits depending on their sensitivity. The output value is the same value of the input.

【深入理解计算机系统】 四:顺序逻辑电路

Behaviour of sequential circuits depending on their sensitivity

You may also download this figure as a PDF file【深入理解计算机系统】 四:顺序逻辑电路.

The input sequence makes several transitions between clock edges. The first circuit, circuit A, is high-level sensitive, thus, whenever the clock is high, the changes in the input are reflected in the output. However, when the clock is low, the circuit remembers the last value of the input (before the edge). Analogously, circuit B has similar behaviour but it is sensitive to a low clock value.

Circuits C and D are edge sensitive, thus, the changes in the input are not seen at the output. Circuit C only takes the value of the input at a rising edge, and the rest of the time sustains that value. Circuit D behaves analogously but taking the value whenever a falling edge occurs in the clock.

 

5.2. Flip-Flops

Once we understand the four types of sensitivity of sequential circuits, we will assume, unless otherwise noted that the sequential circuits are edge sensitive. Analogously to the logic gates that were defined as simple circuits implementing basic Boolean expressions, we have the equivalent for sequential circuits. Some of the most commonly used building blocks are called flip-flops.

A flip-flop is a sequential circuit that is edge sensitive and has one or two inputs (aside from the clock, of course) and two outputs. The two outputs, however, always provide one the opposite value of the other.

The behaviour of a combinational circuit (or a Boolean expression) was captured by the truth table. In the case of a sequential circuit the truth table is also used but with a major modification: the output column is not the immediate value of the output, but its value when the following transition is allowed by the clock. In other words, the output column of the truth table contains the future value of the output. The convention that is used to represent this column is by denoting the output with the sub-index 【深入理解计算机系统】 四:顺序逻辑电路. An example of truth table for a one input flip-flop would be:

input 【深入理解计算机系统】 四:顺序逻辑电路
1 1
0 0

The most commonly used flip-flops when designing sequential digital circuits are: SR flip-flop, JK flip-flop, and D flip-flop. It follows a detailed description of each of them.

5.2.1. SR Flip-Flop

An SR flip-flop has two inputs, S and R (plus the clock). The inputs are used to encode three possible transitions when the clock allows them: the output is set to zero, the output is set to one, or the output remains at its current value. Additionally, the circuit has two outputs usually called Q and Q’ to represent the fact that they always produce opposite values. The truth table representing this behaviour is as follows:

Input Output
S R 【深入理解计算机系统】 四:顺序逻辑电路
0 0 【深入理解计算机系统】 四:顺序逻辑电路(no change)
0 1 0
1 0 1
1 1 undefined

【深入理解计算机系统】 四:顺序逻辑电路 Trick

The trick to remember this truth table is to assimilate the signal S with the word set, and R with reset. Whenever S is high, it is trying to set the output, and whenever R is high, it is trying to reset the output to zero. You must remember that when both try to change the output, it is undefined.


This table contains important information about the behaviour over time of this flip-flop:

  • A flip-flop only makes a transition when allowed by an edge in the clock. Thus, the value at the output only occurs at that time. At any other instant, the output remembers the value set in the previous period.
  • If the clock allows a transition and both inputs S and R are set to zero, the circuit maintains its value at the output.
  • If the clock allows a transition and both inputs S and R are set to one, the circuit enters an undefined state. In other words, there is no way to tell if the output will become zero or one.

The symbols used to represent the edge sensitive SR flip-flops are shown in the following figure.

【深入理解计算机系统】 四:顺序逻辑电路

The circle in the output 【深入理解计算机系统】 四:顺序逻辑电路 is to represent that at all times 【深入理解计算机系统】 四:顺序逻辑电路 produces the opposite value than 【深入理解计算机系统】 四:顺序逻辑电路. The reason for these circuits to have two inputs offering the opposite value is related to their implementation. There are a set of logic gates that are used to implement the behaviour of this flip-flop. Two of the internal signals are 【深入理解计算机系统】 四:顺序逻辑电路, and 【深入理解计算机系统】 四:顺序逻辑电路, and both of them are made available as outputs.

Review questions for 5.2.1 SR Flip-Flop

5.2.2. JK Flip-Flop

The SR flip-flop has only three possible behaviour changes depending on the value of its outputs. This translates into one combination of the inputs (both S and R to one) that leaves the circuit in an undefined state. The JK flip-flop is also a 2 input circuit similar to the SR but with the advantage that all four possible values at its inputs have a concrete effect on the circuit. The truth table for this sequential circuit is:

Input Output
J K 【深入理解计算机系统】 四:顺序逻辑电路
0 0 【深入理解计算机系统】 四:顺序逻辑电路(no change)
0 1 0
1 0 1
1 1 【深入理解计算机系统】 四:顺序逻辑电路

【深入理解计算机系统】 四:顺序逻辑电路 Trick

The trick to remember this truth table is to assimilate J to the word jump and K to the word knock-out. If none of them are active, the flip-flop remains in the same state, and if both are active, the input flips its value.


The only difference with the SR flip-flop (other than the name change in the inputs) is when both inputs J and K are set to one. In this case the output of the circuit becomes the opposite value of the output before. In other words, even though the inputs are set to a special value, the future output depends on the output at the current instant.

The other two properties of the SR flip-flop are also preserved in this circuit. A transition only occurs when allowed by the appropriate edge in the clock. If both inputs are zero and the clock allows a transition, the flip-flop maintains the value of its outputs.

The symbols used to represent the edge sensitive JK flip-flops are shown in the following figure.

【深入理解计算机系统】 四:顺序逻辑电路

The only difference with the SR flip-flop is the name of the inputs.

Review questions for 5.2.2 JK Flip-Flop

5.2.3. D Flip-Flop

The D flip-flop is one of the most common sequential circuit used when building digital systems due to its simplicity. Rather than having two inputs to encode various transitions at the output, this circuit has one single input called D (aside from the clock, of course), and the outputs simply follow the value of the input when the clock allows a transition. The truth table captures this simplicity.

D 【深入理解计算机系统】 四:顺序逻辑电路
0 0
1 1

【深入理解计算机系统】 四:顺序逻辑电路 Trick

The trick to remember this truth table is to think of a D flip-flop as the output making a copy of the input when the clock says so and stick to that value until a new copy is allowed.


The behaviour of this flip-flop simply states that the output will follow or mimic the value of the input when the clock enables it. Otherwise, the output remains to its previous value. As in the case of the other two previous flip-flops, two outputs with opposite value are also available. This circuit does not allow the appearance of any undefined value as it is the case of the SR flip-flop.

The symbols used to represent the edge sensitive D flip-flops are shown in the following figure.

【深入理解计算机系统】 四:顺序逻辑电路

5.2.4. Examples of Circuits with Flip-Flops

As in the case of the basic logic gates, the power of the sequential circuits previously described is when combined with other circuits. One important limitation present when combining logic gates to create a combinational circuit is the need to avoid what is known as a combinational cycle or loop. Sequential circuits may handle this situation in some cases. Some of the examples described in the next sections will rely on those cycles to implement interesting sequential behaviour.


【深入理解计算机系统】 四:顺序逻辑电路 Example

A Register

One of the simplest sequential digital circuits, but also one of the most commonly used is what is known as a register. The purpose of this circuit is simply to store a number of bits given by an equal number of inputs.

Unless otherwise noted, register are typically implemented as several D flip-flops, one connected to each input and output. The following figure illustrates this construction.

【深入理解计算机系统】 四:顺序逻辑电路

The representation of a register storing 8 bits is drawn simply as a box with a clock signal and with a label in the arrow denoting the number of signals.


【深入理解计算机系统】 四:顺序逻辑电路 Example

Boolean function as input

Consider the circuit in the following figure:

【深入理解计算机系统】 四:顺序逻辑电路

The input of the D flip-flop can be an arbitrary Boolean function. The behaviour of this circuit is similar to its combinational part except for the fact that the D flip-flop copies the value of the function when a raising edge occurs and maintains that value in the output of the flip-flop even if the inputs of the circuit change.

Another way to look at this type of construction is to consider the circuit as a more stable version of its combinational part. The function at the input can change its value at various times, whereas the output of the D flip-flop will only change its value at the raising edge of the clock signal.

 

Question 1 Given the previous circuit, which of the following combination of inputs will produce a 1 in 【深入理解计算机系统】 四:顺序逻辑电路 after the raising edge of the clock?

  1. X = 1, Y = 0, Z = 1
  2. X = 0, Y = 0, Z = 1
  3. X = 1, Y = 1, Z = 0
  4. X = 1, Y = 1, Z = 1

【深入理解计算机系统】 四:顺序逻辑电路 Example

Stable Circuit

Consider the following simple sequential circuit.

【深入理解计算机系统】 四:顺序逻辑电路

The wire connecting 【深入理解计算机系统】 四:顺序逻辑电路 with D must be interpreted as the signal following the path shown by the arrow, because 【深入理解计算机系统】 四:顺序逻辑电路 is an output and D is an input. This is a totally valid circuit with a normal behaviour. The connection from 【深入理解计算机系统】 四:顺序逻辑电路 to D is what would be called a cycle or a loop in a combinational circuit, but not in this one. The value of the output is still evaluated following the value of the input whenever the clock has a rising edge (as noted by the triangle in the clock input).

But in order to know the exact evolution of this circuit we have a problem. The output 【深入理解计算机系统】 四:顺序逻辑电路will take the value of input D whenever the clock says, but D itself has the previous value of 【深入理解计算机系统】 四:顺序逻辑电路. We need to know the initial value of 【深入理解计算机系统】 四:顺序逻辑电路 to know the future evolution of the circuit. However, in either case, if 【深入理解计算机系统】 四:顺序逻辑电路 has initial value one, or zero, the behaviour is similar, the circuit will remain with the output at the same value for ever.

Although this circuit is not very useful it shows one important property of edge sensitive sequential circuits, they can use their own output to computer the value at the inputs. It works because at the instant in which there is an edge in the clock, the new value is stored in the flip-flop, and even though the input may change, it is passed the edge and the change is not registered.

 

Question 2 Consider the following circuit

【深入理解计算机系统】 四:顺序逻辑电路

【深入理解计算机系统】 四:顺序逻辑电路

You don’t know the initial value of 【深入理解计算机系统】 四:顺序逻辑电路 but you want to set it to 1 and then leave it at that value all the time. What value would you assign to x during first rising edge?

  1. Zero
  2. One
  3. One, and then maintain x to one, otherwise, the flip-flop sets  【深入理解计算机系统】 四:顺序逻辑电路 to zero
  4. Cannot be done with the information given

【深入理解计算机系统】 四:顺序逻辑电路 Example

Switching Circuit

Let us know consider a more interesting circuit like the ones shown in the following figure.

【深入理解计算机系统】 四:顺序逻辑电路

The two circuits in the previous figure have identical behaviour. In this case, the input D of the flip-flop receives the negated value of the output. If the output 【深入理解计算机系统】 四:顺序逻辑电路is one, D will be one, and as stated by the truth table of this flip-flop, at the next raising edge, the output will take the value of the input, thus switching its value. Now, the output has the value zero, and will set the input for the next rising edge to one. Thus, the circuit will switch the value of its input at every rising edge.

But with this circuit we still have the same issue than the previous one. What is the initial value of the output 【深入理解计算机系统】 四:顺序逻辑电路? This value should be defined. However, note that the behaviour is the same independently of this value, the output will switch at every rising edge of the clock.

Question 3 In the circuit shown in the previous figure

  1. The output 【深入理解计算机系统】 四:顺序逻辑电路 changes at exactly the same frequency as the clock following an identical evolution in time.
  2. The output  【深入理解计算机系统】 四:顺序逻辑电路 is always the opposite value of the clock but still with the same frequency.
  3. The output  【深入理解计算机系统】 四:顺序逻辑电路 changes at double the frequency of the clock.
  4. None of the above

【深入理解计算机系统】 四:顺序逻辑电路 Example

Boolean function with state inputs

Consider the circuit in the following figure:

【深入理解计算机系统】 四:顺序逻辑电路

This circuit is a generalization of the previous examples. A flip-flop (in this example a D flip-flop) may have as input a Boolean function itself with inputs coming from the outputs of the flip-flop. The truth table of this circuit is derived by considering the output of the flip-flop as a regular input to compute the value of 【深入理解计算机系统】 四:顺序逻辑电路. The truth table of the circuit shown is:

Inputs Output
x y 【深入理解计算机系统】 四:顺序逻辑电路
【深入理解计算机系统】 四:顺序逻辑电路
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

The third column of the previous table is calculated applying the rules of the digital gates based on the input values. This column, even though it is coming from the flip-flop, it is considered an input. Although in the circuit there are two connections from 【深入理解计算机系统】 四:顺序逻辑电路 and 【深入理解计算机系统】 四:顺序逻辑电路 to the gates, only one column is needed, as they are the same variable, but with a negation.

The fourth column is stating the state of 【深入理解计算机系统】 四:顺序逻辑电路after the next rising edge of the clock.

 

Question 4 Compare the truth table of the previous circuit with the truth table of the SR and JK flip-flops. Do you detect any similarity?

  1. None
  2. This table encodes the same behaviour as the one defined in the truth table of the SR flip-flop.
  3. This table encodes the same behaviour as the one defined in the truth table of the JK flip-flop.
  4. This table encodes the opposite behaviour as the one defined in the truth table of the JK flip-flop.
上一篇:(C语言)clock()函数的基本使用


下一篇:C语言学习笔记--字符串函数