# Computer Architecture I: Digital Design Dr. Robert D. Computer Architecture I: Digital Design Dr. Robert D. Kent Logic Design Sequential Circuits Part I Review We have studied logic design in the contexts of Medium Scale Integration (MSI) of gate devices and programmable logic devices (PLD). We have studied the design of a number of specific, practical functional circuits with a view to re-using those circuits as components in MSI design. Adders Subtractors Comparator Decoders Multiplexers We note the differing design approaches, or emphases, effected by differential

layering of abstraction. (The same design issue arises in the context of software engineering as well.) SSI: MSI: Boolean algebra / Simplification / Logic gates Interconnection networks / Iterative re-use / Components Goals Previously, we studied Combinational circuits, or networks. These are time independent because the inputs, once provided, immediately establish what the outputs will be. Goals Previously, we studied Combinational circuits, or networks. These are time independent because the inputs, once provided, immediately establish what the outputs will be. We now continue to consider Sequential Networks These are time dependent in that the initial values of the circuit outputs are used to provide input to the same circuit. Goals Previously, we studied Combinational circuits, or networks. These are time independent because the inputs, once provided, immediately establish what the outputs will be. We now continue to consider Sequential Networks These are time dependent in that the initial values of the circuit outputs are used to provide input to the same circuit.

This is called feedback. Goals The properties of sequential networks yield the capability to design memory circuits characterized by internal states and secondary states that describe the behaviour and values in a circuit before and after inputs are applied. Goals The properties of sequential networks yield the capability to design memory circuits characterized by internal states and secondary states that describe the behaviour and values in a circuit before and after inputs are applied. There are two kinds of sequential networks Goals The properties of sequential networks yield the capability to design memory circuits characterized by internal states and secondary states that describe the behaviour and values in a circuit before and after inputs are applied. There are two kinds of sequential networks Synchronous - behaviour is governed by the inputs only during specific discrete time intervals Goals The properties of sequential networks yield the capability to design memory circuits characterized by internal states and secondary states that describe the

behaviour and values in a circuit before and after inputs are applied. There are two kinds of sequential networks Synchronous - behaviour is governed by the inputs only during specific discrete time intervals Asynchronous - behaviour is governed by the inputs immediately as they are applied Goals The basic logic element is called the Flip-Flop circuit. Goals The basic logic element is called the Flip-Flop circuit. We will study first a primitive element - the basic bi-stable element. Goals The basic logic element is called the Flip-Flop circuit. We will study first a primitive element - the basic bi-stable element. ... then study Latches. Goals The basic logic element is called the Flip-Flop circuit. We will study first a primitive element - the basic bi-stable element. ... then study Latches. ... then proceed to Flip-Flops and Gated Latches/Flip-Flops. Goals

The basic logic element is called the Flip-Flop circuit. We will study first a primitive element - the basic bi-stable element. ... then study Latches. ... then proceed to Flip-Flops and Gated Latches/Flip-Flops. Finally, we will establish an MSI based model of a register and discuss how to construct load, read, shift and count capabilities into the register designs. Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: X X Q Q Y

Y Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: Trace: Starting from the top gate 1. If X = 0 then Q = X = 1 X X Q Q Y Y Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: X

X Q Q Y Trace: Starting from the top gate 1. If X = 0 then Q = X = 1 2. Thus, Y = X = Q = 1 implies Q = Y = 0 Y Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: X Q Q Y Trace: Starting from the top gate 1. If X = 0 then Q = X = 1 2. Thus, Y = X = Q = 1 implies Q = Y = 0 This is self-consistent, since X = Y = Q.

X Y Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: X X Q Q Y Trace: Starting from the top gate 1. If X = 0 then Q = X = 1 2. Thus, Y = X = Q = 1 implies Q = Y = 0 This is self-consistent, since X = Y = Q. The same self-consistency applies when X = 1 (Y = 0). Therefore, we say the state is stable. Y Basic Bi-stable Element The basic bi-stable element is a simple device characterized by

X no inputs !!! Two outputs. X Q This circuit has the representation: Q Y Y The term bi-stable implies that there are two possible states Q = 0 , Q = 1 and Q = 1 , Q = 0 Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no Q inputs !!! Two outputs. X

X Q Transition Voltage Smooth Signal Profile Q This circuit has the representation: Q Transition Voltage Y Y The term bi-stable implies that there are two possible states Q = 0 , Q = 1 and Q = 1 , Q = 0 There is a third state that is technically possible, called the metastable state. This applies when the voltage signal values of X and Y (hence, Q and Q) are precisely half way between their HI and LO values; however, these in-between states are typically short lived.

Basic Bi-stable Element The basic bi-stable element is a simple device characterized by X no Q inputs !!! Two outputs. X Q Transition Voltage Noisy Signal Profile Q This circuit has the representation: Q Transition Voltage Y Y The term bi-stable implies that there are two possible states Q = 0 , Q = 1 and

Q = 1 , Q = 0 There is a third state that is technically possible, called the metastable state. This applies when the voltage signal values of X and Y (hence, Q and Q) are precisely half way between their HI and LO values; however, these in-between states are typically short lived. Basic Bi-stable Element The basic bi-stable element is a simple device characterized by no inputs !!! Two outputs. This circuit has the representation: X X Q Q Y Y Although the bi-stable element is worth studying for its simple properties, it is relatively useless as a computer circuit because its value cannot be changed from the outside - once power is applied its value is set (after a brief time period to achieve stability) and does not change henceforth.

Latches Latches A Flip-Flop is a bistable device that permits both probing of its current state (value) and modification of the state. Latches A Flip-Flop is a bistable device that permits both probing of its current state (value) and modification of the state. Set the state - store a value 1 in the circuit; also called pre-setting the state. Latches A Flip-Flop is a bistable device that permits both probing of its current state (value) and modification of the state. Set the state - store a value 1 in the circuit; also called pre-setting the state. Reset the state - store a value 0 in the circuit; also called clearing the state. Latches A Flip-Flop is a bistable device that permits both probing of its current state (value) and modification of the state. Set the state - store a value 1 in the circuit; also called pre-setting the state. Reset the state - store a value 0 in the circuit; also called clearing the state. We will consider next a class of flip-flops called Latches.

Latches A Flip-Flop is a bistable device that permits both probing of its current state (value) and modification of the state. Set the state - store a value 1 in the circuit; also called pre-setting the state. Reset the state - store a value 0 in the circuit; also called clearing the state. We will consider next a class of flip-flops called Latches. Characterized by the fact that the timing of the output changes is not controlled (except possibly by an Enable, or Clock, signal). SR Latch SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q R S Q Q SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q

R Truth table: S R Q0 Q0 Q1 Q1 Q2 Q2 S Q Q SR Latch This circuit consists of two cross-coupled nor gates with Q0 and Q0 are the output signal S set and reset inputs

two inputs,values S and R,when referredthe to as and R inputs are applied they are also applied as twoinputs outputs,to Q and theQ nor gates. R Q0 Truth table: S R Q0 Q0 Q1 Q1 Q2 Q2

Q0 S Q Q SR Latch This circuit consists of two cross-coupled nor gates with Once the nor gates have stabilized two inputs, S and R,the referred to as set and reset inputs outputs, Q1 and Q1 are then fed two outputs, Q and Q back as inputs. R Truth table: S R Q0

Q0 Q1 Q1 Q2 Q2 S Q Q SR Latch This circuit consists of two cross-coupled nor gates with two inputs, The nor mustto as set and reset inputs S andgates R, referred stabilize to a final output , Q2 and Q2. two outputs, Q and Q R

Truth table: S R Q0 Q0 Q1 Q1 Q2 Q2 S Q Q SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0 0

1 Truth table: S R Q0 Q0 0 0 0 1 Q1 Q1 Q2 Q2 0

Q Q 0 1 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0 0 1 Truth table: S R Q0 Q0 Q1 Q1

0 0 0 1 0 1 Q2 Q2 0 Q Q 0 1 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0

0 1 Truth table: S R Q0 Q0 Q1 Q1 0 0 0 1 0 1

Q2 Q2 0 1 0 Q Q 0 1 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 0 0 Truth table:

S R Q0 Q0 Q1 Q1 0 0 0 0 0 1 1 0 0 1 Q2

Q2 0 1 0 Q Q 1 0 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 0 0 Truth table: S R

Q0 Q0 Q1 Q1 0 0 0 0 0 1 1 0 0 1 1 0 Q2 Q2

0 1 0 Q Q 1 0 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 0 0 Truth table: S R Q0

Q0 Q1 Q1 0 0 0 0 0 1 1 0 0 1 1 0 Q2 Q2 0 1

1 0 0 Q Q 1 0 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0 > 0 1 1 Truth table: S R

Q0 Q0 Q1 Q1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0

1 Q2 Q2 0 1 0 1 0 1 0 Q Q 0 1 > 1 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1

1 0 Truth table: S R Q0 Q0 Q1 Q1 0 0 0 0 0 0 1 1 0 1

0 1 1 0 1 0 0 1 0 1 0 1 Q2 Q2 0 1 0 1 0 1 0

Q Q 1 0 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 1 > 0 0 > 0 Truth table: S R Q0 Q0 Q1 Q1

0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0

Q2 Q2 0 1 0 1 0 1 1 > 0 0 Q Q 0 > 0 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 > 0 > 0 1 Q

0 > 0 Truth table: S R Q0 Q0 Q1 Q1 0 0 0 0 0 0 1 1 0 1 0 1

1 0 1 0 0 1 0 0 1 0 1 0 Q2 0 1 0 0 Q2 1 0 1 1 * 1 > 0 0

Q 0 > 0 > 1 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0 0 1 Truth table: S R Q0 Q0 Q1 Q1

0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0

1 0 1 0 Q2 0 1 0 0 Q2 1 0 1 1 * 0 1 Q Q 1 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q

0 1 > 0 Truth table: S R Q0 Q0 Q1 Q1 0 0 0 0 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 Q2 0 1 0 0 Q2

1 0 1 1 * 0 > 0 1 0 > 0 Q Q 1 > 0 SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 0 > 0 > 1 0 Q 1 > 0 Truth table: S

R Q0 Q0 Q1 Q1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1

0 1 0 1 0 1 0 0 0 1 0 1 0 0 Q2 0 1 0 0 1 Q2 1 0 1 1 * 0 *

0 > 0 1 Q 1 > 0 > 0 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 > 1 0 Q 0 > 0 Truth table: S R Q0

Q 0 Q1 Q1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1

0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 Q2 0 1 0 0 1 1 Q2 1 0 1

1 * 0 * 0 1 > 1 1 Q 0 > 0 Stable! SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q 1 x > 0 Q x > 0 Truth table: S R

Q0 Q 0 Q1 Q1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0

1 x 1 0 1 0 1 0 x 0 1 0 0 0 1 0 1 0 1 0 0 0 0 Q2 0 1

0 0 1 1 0 Q2 1 0 1 1 * 0 * 0 0 x > 0 1 Q x > 0 Stable! But not complementary! ( Q = Q ) SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs

two outputs, Q and Q R Truth table: (Adapted) S R Q0 Q 0 Q2 Q2 0 0 0 0 1 1 1 0 0 1 1 0

0 1 0 1 0 1 0 1 x 1 0 1 0 1 0 x 0 1 0 0 1 1 0 1 0 1

1 0 0 0 Q+ Q + Q Q Q Q 0 1 0 1 * 1 0 * 1 0 Forbidden S Q+ Q + SR Latch This circuit consists of two cross-coupled nor gates with

two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q R Truth table: (Adapted - Simplified) S R 0 0 1 1 0 1 0 1 Q+ Q 0 1 (0) Forbidden S Q+ Q +

SR Latch This circuit consists of two cross-coupled nor gates with two inputs, S and R, referred to as set and reset inputs two outputs, Q and Q R Q+ Truth table: (Adapted - Simplified) S R 0 0 1 1 0 1 0 1 Q + S Q+

Q Two commonly used MSI 0 symbols. 1 S Q S Q (0) Forbidden R Q R Q SR Latch SR Latch This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs two outputs, Q+ and Q + S R Q+

Q + SR Latch This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs two outputs, Q+ and Q + Truth table: S R 0 0 0 0 Q+ (1) Forbidden Q+ = 1 Q + = 1 SR Latch

This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs two outputs, Q+ and Q + Truth table: S R 0 0 0 1 Q+ = 1 S = 0 R = 1 Q+ (1) Forbidden 1 Q + = 0 SR Latch This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs

two outputs, Q+ and Q + Truth table: S R 0 0 1 0 1 0 Q+ = 0 S = 1 R = 0 Q+ (1) Forbidden 1 0 Q + = 1 SR Latch This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs

two outputs, Q+ and Q + Truth table: S R 0 0 1 1 0 1 0 1 Q+ = Q S = 1 R = 1 Q+ (1) Forbidden 1 0 Q Q + = Q SR Latch

This circuit consists of two cross-coupled nand gates with two complemented inputs, S and R, referred to as set and reset inputs S two outputs, Q+ and Q + Truth table: S R 0 0 1 1 0 1 0 1 Q+ Q + R Q+ (1**)

1 0 Q Two commonly used MSI symbols. S Q S Q R Q R Q D Flip-Flop D Flip-Flop The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. (Enabl

e) Clk Q Q D D Flip-Flop The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. Note the SR latch sub-circuit element (Enabl e) Clk Q Q D D Flip-Flop The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. Note the SR latch sub-circuit element The control input, Clk, controls a sub-circuit

called a gate. (Enabl e) Clk Q Q D D Flip-Flop The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. Note the SR latch sub-circuit element The control input, Clk, controls a sub-circuit called a gate. Since D is the only input, the forbidden values, S = R = 1, never occur. (Enabl e) Clk Q Q D

D Flip-Flop The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. When Clk = 0, it follows that: Note the SR latch sub-circuit element The control input, Clk, controls a sub-circuit called a gate. S=R=0 Since D is the only input, the forbidden values, S = R = 1, never occur. This implies no change of state: Q+ = Q 0 (Enabl e) Clk D Q 0

0 Q D Flip-Flop When Clk = 1, it follows that: The D flip-flop overcomes the problem of the SR (SR) latch having forbidden states. It features a single input, D, and a control input, Clk, provided by the system clock, and produces outputs Q and Q. Note the SR latch sub-circuit element The control input, Clk, controls a sub-circuit called a gate. S = D and R = D Thus, the behaviour is: Since D is the only input, the forbidden values, S = R = 1, never occur. D=S=1 =1 Q+ D = 0 (R = 1) =0

Q+ D (Enabl e) Clk D Q 1 D Q JK Flip-Flop JK Flip-Flop The basic JK flip-flop provides a solution to the problem of the SR latch with S=R=1 that produces forbidden output states. JK Flip-Flop The basic JK flip-flop provides a solution to the problem of the SR latch with S=R=1 that produces forbidden output states. The JK flip-flop can be constructed from the gated SR latch by coupling additional feedback from the (Q, Q) outputs into the J and K inputs. J Clk

K S C R Q Q Q Q JK Flip-Flop The basic JK flip-flop provides a solution to the problem of the SR latch with S=R=1 that produces forbidden output states. The JK flip-flop can be constructed from the gated SR latch by coupling additional feedback from the (Q, Q) outputs into the J and K inputs. With the clock disabled (C = 0) the SR latch retains the state (Q, Q). J Clk K S 0

C R Q Q Q Q JK Flip-Flop The basic JK flip-flop provides a solution to the problem of the SR latch with S=R=1 that produces forbidden output states. The JK flip-flop can be constructed from the gated SR latch by coupling additional feedback from the (Q, Q) outputs into the J and K inputs. With the clock enabled (C = 1) the SR latch produces outputs that depend on the J and K inputs. J Clk K S 1

C R Q Q Q Q JK Flip-Flop TRACE The JK flip-flop can be constructed from the gated SR latch by coupling additional feedback from the (Q, Q) outputs into the J and K inputs. We denote the final output as Q+. J K Qin Qout META-STABLE ! Actions: J K J=K=0 nothing Do J=1, K=0

Set Q=1 J=0, K=1 Reset Q=0 J=K=1 = Q Complement Q Q Q 0 0 0 0 0 1 0 1 1 0 1 0 0 1

1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 0 This leads to the algebraic expression for the final output, labeled Q+, in terms of J, K and initial input Q: Q+ = JQ + KQ JK Flip-Flops edge triggering The previous implementation of a JK flip-flop is considered unstable under certain circumstances. Utilizing an edge-triggered master-slave latch is used to produce a stable circuit.

Below is given a more typical JK using a master-slave approach Q Q WARNING: Tracing the logic may prove confusing as the actual circuits employ both leading-edge and trailing-edge gate elements in order to avoid forbidden states. JK, D and T Flip-Flops JK flip-flops can be used to produce D flip-flops Connect K to J using an inverter so they have different values T flip-flops Sometimes called a complementer Connect J and K so they have the same values If J = K = 0, nothing happens (Q stays the same) If J = K = 1, the complement of Q is outputted This illustrates, once again, the principle that common components can be used to achieve design goals in different ways. Timing Considerations Timing Considerations Real (physical) circuit elements take a finite time to respond to the stimulus of changing state (voltage). The behaviour of a logic device is characterized by the following

times: Timing Considerations Real (physical) circuit elements take a finite time to respond to the stimulus of changing state (voltage). The behaviour of a logic device is characterized by the following times: Propagation Delay S The time it takes to produce a change in an output signal based on the input signals. R Tp,LH Q Q Tp,HL Timing Considerations As the value of S begins to change, it is only when it has

Real (physical) circuit elements takeaacertain finite voltage time tolevel respond to the reached stimulus of changing state (voltage). that the value of Q (Q) begins to change. S must be maintained at a The behaviour of a logic device is characterized by the following certain level for a minimum time period before Q can times: stabilize. Propagation Delay S The time it takes to produce a change in an output signal based on the input signals. R Tp,LH

Q Q Tp,HL Timing Considerations Real (physical) circuit elements take a finite time to respond to the stimulus of changing state (voltage). The behaviour of a logic device is characterized by the following times: Propagation Delay S Minimum Pulse Width The minimum amount of time an input signal must be applied in order to produce a change in the output. R Q Timing Considerations Real (physical) circuit elements take a finite time to respond to the stimulus of changing state (voltage). The behaviour of a logic device is characterized by the following times: Propagation Delay Minimum Pulse Width Setup Time - the minimum time the input signals must be held fixed

before the latching action begins Timing Considerations Real (physical) circuit elements take a finite time to respond to the stimulus of changing state (voltage). The behaviour of a logic device is characterized by the following times: Propagation Delay Minimum Pulse Width Setup Time - the minimum time the input signals must be held fixed before the latching action begins Hold Time - the minimum time the input signals must be held fixed until the latching action is completed State Tables and Diagrams State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State tables are a form of truth tables where current values of flip-flop outputs are used as inputs, along with other specified inputs, to determine outputs after a clock pulse. State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State diagrams are graphical representations of all possible transitions that are described by a state table. Example: JK flip-flop Present

State Inputs Next state Q(t) J K Q(t+1) 0 0 0 0 0 0 1 0

0 1 0 1 0 1 1 1 1 0 0 1 1 0 1

0 1 1 0 1 1 1 1 0 State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State diagrams are graphical representations of all possible transitions that are described by a state table. Example: JK flip-flop 0 Draw possible Q output states in circles (or ellipses)

1 Present State Inputs Next state Q(t) J K Q(t+1) 0 0 0 0 0 0

1 0 0 1 0 1 0 1 1 1 1 0 0 1 1

0 1 0 1 1 0 1 1 1 1 0 State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State diagrams are graphical representations of all possible transitions that are described by a state table. Example: JK flip-flop 00,01 0

1 Present State Inputs Next state Q(t) J K Q(t+1) 0 0 0 0 0 0

1 0 0 1 0 1 0 1 1 1 1 0 0 1 1

0 1 0 1 1 0 1 1 1 1 0 State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State diagrams are graphical representations of all possible transitions that are described by a state table. Example: JK flip-flop 00,01

0 10,11 1 Present State Inputs Next state Q(t) J K Q(t+1) 0 0 0 0 0

0 1 0 0 1 0 1 0 1 1 1 1 0 0 1

1 0 1 0 1 1 0 1 1 1 1 0 State Tables and Diagrams Complex circuits are difficult to represent simply in a compact notation. State diagrams are graphical representations of all possible transitions that are described by a state table.

Example: JK flip-flop 00,01 0 10,11 01,11 1 00,10 Present State Inputs Next state Q(t) J K Q(t+1) 0 0

0 0 0 0 1 0 0 1 0 1 0 1 1 1 1

0 0 1 1 0 1 0 1 1 0 1 1 1 1 0

State Tables and Diagrams Draw transitions between output states. Allow no change as well as Complex circuits are difficult to for represent simplyof in value, a compact notation. changes in value. Label each transition State diagrams are graphical representations of JK all possible that by the (list) of all inputs transitions that effect the transition. are described by a state table. are themselves changed in Example: JK flip-flop If the inputs

Present Inputs Next 00,01 transition, list the initial and final input State separated by a slash /. state values Q(t) J K Q(t+1) 0 10,11 01,11 1 00,10 0 0 0 0

0 0 1 0 0 1 0 1 0 1 1 1 1 0 0

1 1 0 1 0 1 1 0 1 1 1 1 0 Characteristic Equations Characteristic Equations Before proceeding, we stop briefly to recapitulate the various basic

flip-flop circuits derived so far. Each circuit has an associated set of expressions that describe the outputs in terms of the inputs and the internal state at the time the circuit is enabled. These expressions are called the characteristic equations. Characteristic Equations SR flip-flop S Q C R Q Q+ = S + RQ : (SR) = 0 Q+ refers to the output value after the next clock interval, or Q(t+1). Characteristic Equations SR flip-flop S

Q C R D flip-flop D Q C Q Q+ = S + RQ : (SR) = 0 Q Q+ = D Characteristic Equations SR flip-flop S Q C R

Q JK flip-flop Q C K D Q C Q+ = S + RQ : (SR) = 0 J D flip-flop Q Q+ = JQ + KQ Q Q+ = D Characteristic Equations SR flip-flop

S Q D flip-flop C R D Q C Q Q Q+ = S + RQ : (SR) = 0 JK flip-flop Q+ = D T flip-flop J Q C

K T Q C Q Q+ = JQ + KQ Q Q+ = TQ + TQ = T xorQ Gated Latches Gated Latches The concept of a gate, or a controlling element, is important in computer circuits. During the execution of a program only specific circuit elements should be active at a given time. These are often controlled using a strobe signal that provides a regular sequence of alternating voltage-HI (1) and voltage-LO (0) signals. Because of the regular nature of the signal sequence the strobe is called a clock. Thus, gate control is often achieved using a clock. Another type of control signal is called an enable signal.

Gated SR Latch Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. S Q (Enable) Clk R Q Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 0 S 0 Q (Enable) Clk R Q

Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 0 S 0 (Enable) Clk R 1 Q Q 1 Q Q Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 0 S 0

(Enable) Clk R 1 Q Q 1 Q Q Q Q Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 0 The outputs (Q, Q) remain unchanged when the circuit is disabled. The (Q,Q) are stored in a stable manner. S

0 (Enable) Clk R 1 Q Q 1 Q Q Q Q Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 1 S 1 Q (Enable) Clk

R Q Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 1 The first stage nand gates are activated by the Clk signal to produce the outputs (S, R). S S Q 1 (Enable) Clk R R Q

Gated SR Latch The SR latch is modified to a gated SR latch by applying a clock signal to the latch input. This gives rise to the behaviour: Clk = 1 The first stage nand gates are activated by the Clk signal to produce the outputs (S, R). S S Q 1 (Enable) Clk The remaining sub-circuit is just an SR latch whose properties were discussed previously. R R Q Gated SR Latch

The effect of the Clk The SR latch is modified to a gatedthe SR latch by applying a clock input is to control signal to the latch circuit. input. latch Changes to (Q,Q) may only Clk=1 This gives riseoccur to the when behaviour: enables the circuit. Clk = 1 The first stage nand gates are activated by the Clk signal to produce the outputs (S, R). S S Q

1 (Enable) Clk The remaining sub-circuit is just an SR latch whose properties were discussed previously. R R Q Gated D Latch Gated D Latch We previously considered this circuit. See earlier notes. (Enabl e) Clk Q Q D Gated D Latch We previously considered this circuit. See earlier notes.

The MSI representation may be given in two forms: (A) (B) D C Q D C Q Q Q (Enabl e) Clk Q Q D

Master-Slave Flip-Flops Master-Slave Flip-Flops We have just considered the category of flip-flops called latches. Changes on the information input lines produce immediate responses on the output lines. This is called transparency. Now we consider the category of Master-Slave (pulse-triggered) flip-flop circuits. These circuits feature a control signal that enables one stage of a circuit while disabling a second stage, then the second stage is enabled while the first stage is disabled. This is called cascading of circuits. Master-Slave SR Flip-Flop Master-Slave SR Flip-Flop The SR flip-flop is adapted to the Master-Slave flip-flop by cascading two SR circuits with sequential enabling of each circuit by a Clk pulse. Master-Slave SR Flip-Flop The SR flip-flop is adapted to the Master-Slave flip-flop by cascading two SR circuits with sequential enabling of each circuit by a Clk pulse. S

S C C R R Q Q QM QM S Q C R Q QS Q

QS Q Master-Slave SR Flip-Flop The SR flip-flop is adapted to the Master-Slave flip-flop by cascading two SR circuits with sequential enabling of each circuit by a Clk pulse. When the clock is set, C = 1, the first stage gated SR latch is enabled, but the second stage is disabled. S C R S 1 Q C R Q QM QM S 0

Q C R Q QS Q QS Q Master-Slave SR Flip-Flop The SR flip-flop is adapted to the Master-Slave flip-flop by cascading two SR circuits with sequential enabling of each circuit by a Clk pulse. When the clock is set, C = 1, the first stage gated SR latch is enabled, but the second stage is disabled. When the clock signal returns to C = 0, the first stage is disabled and the second stage is enabled. S C R S 0 Q

C R Q QM QM S 1 Q C R Q QS Q QS Q Registers Registers A register is a collection of flip-flops taken as a single entity.

Since flip-flops are memory units for single bits, then registers are the equivalent, multi-bit storage units. Since registers are comprised of a finite number, N, of flip-flops, the total number of 0 and 1 combinations is 2N. Each of these combinations is known as the content or state of the register. In addition to storage alone, registers may also have other capabilities associated with them. Clear, Load, Shift, Count Registers A simple storage register based on the Master-Slave D flip-flop is constructed by chaining n of them as shown. The entire memory unit is controlled by the Clock (C) pulse. D0 D Q Q0 C Q D1 D Q

Q 0 . . . Dn-1 Q Q 1 Q0 Q0 Q1 Q1 D1 Q1 C C D0 C Qn-1 Qn-1

Registers In a similar fashion, the Master-Slave T flip-flop is constructed by chaining n of them as shown, controlled by the clock (C) pulse. T0 T Q Q0 C Q T1 T Q Q 0 . . . Tn-1 Q

Q 1 Q0 Q0 Q1 Q1 T1 Q1 C C T0 C Qn-1 Qn-1 Registers Thus, a register is a special multi-bit storage unit that is used to store data in a collective representation (eg. signed binary, BCD, and so on). Input Data N-bit Register I0

D0 I1 D1 In-1 Q0 Q0 Q1 Q1 . . . Dn-1 Enable Clock Enable Q0 Q1 Stored Values (Potential output) Qn-1 Qn-1

Qn-1 Registers We will discuss registers in more detail due to their importance in CPU design and in other places in a computer CPU registers used in the textbook (Mano): PC :: Program counter IR :: Instruction register AR :: Address register DR :: Data register AC :: Accumulator INR :: Input buffer register OUTR :: Output buffer register SCR :: Sequence counter register (or just SC) Summary We considered details and MSI views of: Latches: SR , SR , D Gated Latches: SR , D

Master-Slave: SR , JK, D, T We also discussed the issue of timing and response as important behaviours that characterize and typify logic devices. Including propagation delay, minimum pulse width, set-up and hold times. We concluded by considering registers as conceptual extensions of the basic flip-flops.