Chapter 5 – Sequential Circuits

Presentation on theme: "Chapter 5 – Sequential Circuits"— Presentation transcript:

1 Chapter 5 – Sequential Circuits
Logic and Computer Design Fundamentals Chapter 5 – Sequential Circuits Part 1 – Storage Elements and Sequential Circuit Analysis Haifeng Liu 2014 Fall College of Computer Science and Technology, Zhejiang University

2 Overview Part 1 - Storage Elements and Analysis
Introduction to sequential circuits Types of sequential circuits Storage elements Latches Flip-flops Sequential circuit analysis State tables State diagrams Circuit and System Timing Part 2 - Sequential Circuit Design Specification State Assignment Designing

3 Introduction to Sequential Circuit
Inputs Outputs Consist of: Storage elements: Latches or flip-flops Combinational Logic: Implement a function of inputs Inputs are signals from the outside Outputs are signals to the outside Other Signals: Present State, signal from the storage elements Other output, Next state: input of storage element Combinational Logic Storage Elements State Next State

4 Introduction to Sequential Circuit
Combinational Logic Function of next state Next State= f(Inputs, Present State) Output Function(Mealy) Output = g(Inputs, State) Output Function(Moore) Output = h (Present State) The type of output function depends on the functionality, and have a great impact on the design Inputs Outputs Combinational Logic Storage Elements State Next State

5 Types of Sequential Circuits
Depends on the times at which: storage elements observe their inputs, and storage elements change their state Synchronous Behavior defined by knowledge of its signals at discrete instances of time Storage elements observe inputs and can change state only in relation to a timing signal (clock pulses from a clock) Asynchronous Behavior defined by knowledge of inputs an any instant of time and the order in continuous time in which inputs change If clock is regarded as another input, all circuits are asynchronous! Nevertheless, the synchronous abstraction makes complex designs tractable!

6 Discrete Event Simulation
In order to understand the time behavior of a sequential circuit we use discrete event simulation. Rules: Gates modeled by an ideal (instantaneous) function and a fixed gate delay Any change in input values is evaluated to see if it causes a change in output value Changes in output values are scheduled by a fixed gate delay after the input change At the time for a scheduled output change, the output value is changed along with any inputs it drives

7 Simulated NAND Gate Example: A 2-Input NAND gate with a 0.5 ns delay:
Assume A and B have been 1 for a long time At time t=0, A changes to a 0 and at t= 0.8 ns, back to 1. F A B DELAY 0.5 ns. F(I) t (ns) A B F(I) F Comments –  1 A=B=1 for a long time Þ Ü F(I) changes to 1 0.5 F changes to 1 after a 0.5 ns delay 0.8 F(I) changes to 0 1.3 F changes to 0 after a 0.5 ns delay

8 Gate Delay Models Suppose gates with delay n ns are represented for n = 0.2 ns, n = 0.4 ns, n = 0.5 ns, respectively: 0.2 0.5 0.4

9 Gate Delay Models A Y S B A B S Y
Consider a simple of 2-input multiplexer with function: Y = A for S = 0 Y = B for S = 1 “Glitch” is due to delay of inverter 0.4 0.2 0.5 Y S 0.4 B A S B Y

10 Storing State S Y B B S Y What if Y connected to A? Circuit becomes:
With function: Y = B for S = 1, and Y(t) dependent on Y(t – 0.9) for S = 0 The simple combinational circuit now becomes a sequential circuit because its output is a function of a time sequence of input signals! S B Y 0.5 0.4 0.2 B S Y Y is stored value in shaded area

11 Storing State (Continued)
Simulation example as input signals change with time. Changes occur every 100 ns, so that the 1 ns delays are negligible. Y represents the state of the circuit, not only an output.   Time B S Y Comment 1 Y “remembers” 0 Y = B when S = 1 Now Y “remembers” B = 1 for S = 0 No change in Y when B changes Y “remembers” B = 0 for S = 0 Note that the “glitch” is still present. An actual storage circuit would be designed to eliminate this by addition of term BY.

12 Storing State (Continued)
Suppose we place an inverter in the “feedback path” The following are behavior results: The circuit is said to be unstable. For S = 0, the circuit becomes what is called an oscillator. Can be used as crude clock. S B Y 0.2 0.5 0.4 B S Y Comment 1 Y = B when S = 1 1 1 1 1 1 Now Y “remembers” 1 1 Y changes after 1.1 ns 1 1 Y changes after 1.1 ns 1 Y changes after 1.1 ns

13 Basic (NAND) S – R Latch “Cross-Coupling” two NAND gates gives the S -R Latch: Which has the time sequence behavior: S = 0, R = 0 is forbidden as input pattern S (set) Q Q R (reset) Time R S Q Comment 1 ? Stored state unknown “Set” Q to 1 Now Q “remembers” 1 “Reset” Q to 0 锁存器三个条件: 可以长时间的保持在稳定状态 稳定状态至少有两个 稳定状态可以转换 当R, S同时从0变成1时, 有3种可能: 1. 0,1震荡; 2, Q=0, Q’=1; 3 Q=1, Q’=0 理想情况震荡, 实际情况会达到一个稳定状态,但是是哪一种稳定状态是竞争的结果, 是随机的. 信号传输时间肯定不一样，两个原因：1是材料上的：与非门是电解质构成，分子运动是统计规律，不可能精确。而是两个门在电路板上的位置不同，造成信号传输速度不同。 上面的一杠说明是低电平有效. 1 1 1 Now Q “remembers” 0 1 1 Both go high 1 1 ? ? Unstable!

14 Basic (NOR) S – R Latch Cross-coupling two NOR gates gives the S – R Latch: Which has the time sequence behavior: S (set) R (reset) Q R S Q Comment ? Stored state unknown 1 “Set” Q to 1 Now Q “remembers” 1 “Reset” Q to 0 Now Q “remembers” 0 Both go low Unstable! Time 能够构成互锁形式的不仅是与非门，或非门也可以，用两个或非门互相耦合也可以构成一个锁存器。 与非门1的时候封锁, 或非门0的时候封锁, 相当于两个反相器对着, 电路封锁, 保持原来状态. 实际应用中,要求R, S不相同, 才能保证电路正常, 不会出现最后两种情况, 后面这种现象叫”一次性采样”,它会把一些外部的干扰记录下来,造成电路出现一些不可预测的情况.

15 Clocked S - R Latch Adding two NAND gates to the basic S - R NAND latch gives the clocked S – R latch: S R Q C Has a time sequence behavior similar to the basic S-R latch except that the S and R inputs are only observed when the line C is high. C means “control” or “clock”. 和或非门的S-R锁存器功能一样.

16 Clocked S - R Latch (continued)
The Clocked S-R Latch can be described by a table: The table describes what happens after the clock [at time (t+1)] based on: current inputs (S, R, C) C S R Q(t + 1) X No change 1 Q=0：Clear Q Q=1：Set Q Undefined S R Q C

17 D Latch Adding an inverter to the S-R Latch, gives the D Latch:
Note that there are no “indeterminate” states! D Q C The graphic symbol for a D Latch is: C D Q(t + 1) X No change 1 Q=0: Clear Q Q=1：Set Q C D Q D就是Data 这样两个输入一定是相反的,不会出现不稳定的情况. D锁存器在计算机中应用非常方便, 因为计算机中数据都是1位的, 要么是0, 要么是1, 不会用一对数据来表示. D锁存器在计算机中是用的最多的，尤其是数据传输，还有用硬件描述语言来实现，D锁存器用的最多。但不是在计算机中使用，比如几个锁存器连起来的时候，D锁存器不方便，SR锁存器更方便些。 SR在控制电路中用的比较多，因为后续链接比较方便。

18 D Latch with Transmission Gates
也可以用三态门实现

19 Flip-Flops The latch timing problem Master-slave flip-flop
Edge-triggered flip-flop Standard symbols for storage elements Direct inputs to flip-flops Flip-flop timing

20 The Latch Timing Problem
Consider the following circuit: Suppose that initially Y = 0. As long as C = 1, the value of Y continues to change! The changes are based on the delay present on the loop through the connection from Y back to Y. This behavior is clearly unacceptable. Desired behavior: Y changes only once per clock pulse C D Q Y Clock Clock Y Y值变化的宽度由延迟决定, 当控制信号变为低电平时, Y值到底是什么不知道, 变了多少次不知道, Y值不停地变化叫空翻. 要么脉冲做的很窄, 根据延迟时间来决定脉冲, 但是实际电路中, 延迟时间到底是多少很难确定. 这是一个异步电路，不是同步的

21 The Latch Timing Problem (continued)
In a sequential circuit, combinational logic may include the followings paths: From one storage element to another From a storage element back to the same storage element The combinational logic between a latch output and a latch input may be as simple as an interconnect For a clocked D-latch, any change of input D can result in a change of output Q whenever the clock input C has value 1 来了一个控制信号，状态只改变一次，这种电路在脉冲电路中是一个双稳态电路，这里叫触发器，计算机中的静态存储器内部结构就是触发器

22 The Latch Timing Problem (continued)
A solution to the latch timing problem is to break the inner path from input to output within the storage element The commonly-used, path-breaking solutions are: a master-slave flip-flop an edge-triggered flip-flop

23 S-R Master-Slave Flip-Flop
The input is observed by the first latch when C = 1 The output is changed by the second latch when C = 0 The path from input to output is broken by the difference of the clocking values (C = 1 and C = 0). The behavior demonstrated in the previous example can be prevented since a change of Y based on D won’t occur until the clock changes from 1 to 0. Consists of two clocked S-R latches in series with the clock on the second latch inverted C S R Q 这是一个正脉冲的主从触发器。如果把反相器接在前面，就是一个负脉冲的主从触发器。 不过是正的还是负的，都是在脉冲的后沿才能触发。

24 Flip-Flop Problem The change in the flip-flop output is delayed by the pulse width ,which makes the circuit slower S and/or R are permitted to change while C = 1 Suppose Q = 0 and S goes to 1 and then back to 0 with R remaining at 0 The master latch sets to 1 A 1 is transferred to the slave Suppose Q = 0 and S goes to 1 and back to 0 and R goes to 1 and back to 0 The master latch sets and then resets A 0 is transferred to the slave This behavior is called 1s catching

25 S-R Master-Slave Flip-Flop Timing Parameters
C S R Q Y 5 1 3 Keep 0 6 2 4 主从触发器使用时候的要求： 1。控制脉冲越窄越好 2。采样的时候信号尽量不改变 Before the arrival of pulse: Q=0 Before the end of the pulse: RS=00, Q should keep “0” Reason: SR=11, Input state is illegal Disposable sampling

26 Flip-Flop Solution Use edge-triggering instead of master-slave
An edge-triggered flip-flop ignores the pulse while it is at a constant level and triggers only during a transition of the clock signal Edge-triggered flip-flops can be built directly at the electronic circuit level, or A master-slave D flip-flop which also exhibits edge-triggered behavior can be used. 解决一次性采样的问题，需要采用边沿触发方式。主从触发器用在速度比较低的电路中

27 Edge-Triggered D Flip-Flop
It can be formed by: Replacing the first clocked S-R latch with a clocked D latch or Adding a D input and inverter to a master-slave S-R flip-flop The delay of the S-R master-slave flip-flop can be avoided since the 1s-catching behavior is not present with D replacing S and R inputs The change of the D flip-flop output is associated with the negative edge at the end of the pulse It is called a negative-edge triggered flip-flop The edge-triggered D flip-flop is the same as the master-slave D flip-flop C S R Q D

28 Positive-Edge Triggered D Flip-Flop
Formed by adding inverter to clock input C S R Q D Q changes to the value on D applied at the positive clock edge within timing constraints to be specified Our choice as the standard flip-flop for most sequential circuits Q(t) is the current output of flip-flop while D(t) is the current input, and Q(t+1) represent the next output, then we have: Q(t+1) = D(t)

29 Positive-Edge-Triggered D Flip-Flop
D FF Q D ( b ) Logic Symbol S R Cp Circuit for Problem 5-3 5 6 Q 3 1 2 4 D S R ( a ) Logic Circuit Ⅰ Ⅱ Ⅲ 1 X Q D Cp S R Positive-Edge-Triggered Asynchronous 这是维持阻塞型的，还有一些是利用元器件的延迟构造的边沿触发器，是延迟性的触发器，分析起来更复杂。 ( c ) Function Table

30 Standard Symbols for Storage Elements
Master-Slave: Postponed output indicators Edge-Triggered: Dynamic indicator (a) Latches S R SR D with 0 Control D C D with 1 Control (b) Master-Slave Flip-Flops Triggered D Triggered SR (c) Edge-Triggered Flip-Flops 延迟输出指示符：表示信号在时钟脉冲的末尾变化，并不是指下降沿。正脉冲控制是下降沿，负脉冲控制是上升沿。

31 Direct Inputs At power up or at reset, all or part of a sequential circuit usually is initialized to a known state before it begins operation This initialization is often done outside of the clocked behavior of the circuit, i.e., asynchronously. D C S R Q Direct R and/or S inputs that control the state of the latches within the flip-flops are used for this initialization. For the example flip-flop shown When R is 0, resets the flip-flop to the 0 state When S is 0, sets the flip-flop to the 1 state When R and S are both 1, flip-flop works normally State undefined when R and S are both set to 0 一般初始化不需要外部时钟，是异步输入，因为开始的时候时钟也没有正常工作。

32 Flip-Flop Timing Parameters
ts - setup time th - hold time tw – clock pulse width tpx - propagation delay tPHL - High-to- Low tPLH - Low-to- High tpd - max (tPHL, tPLH) t ≥ t wH wH,min C t ≥ t wL wL,min t t s h S / R t p-,min t p-,max Q (a) Pulse-triggered (positive pulse) t ≥ t wH wH,min C t ≥ t wL wL,min T_s: setup time T_h: hold time T_w: clock pulse width 在导致输出信号变化的时钟脉冲到达之前之后都需要输入信号保持稳定不变, 之前的时间叫建立时间(t_s),之后是保持时间(t_h). T_w 是最低限度的时钟脉冲宽度, 确保主锁存器有足够的时间获取正确的输入值. 对不同的触发器, 对于这些参数的要求不同. t t s h D t p-,min t p-,max Q (b) Edge-triggered (negative edge)

33 Flip-Flop Timing Parameters (continued)
ts - setup time Master-slave - Equal to the width of the triggering pulse Edge-triggered - Equal to a time interval that is generally much less than the width of the the triggering pulse th - hold time - Often equal to zero tpx - propagation delay Same parameters as for gates except Measured from clock edge that triggers the output change to the output change

34 Sequential Circuit Analysis
General Model Current State at time (t) is stored in an array of flip-flops.  Next State at time (t+1) is a Boolean function of State and Inputs. Outputs at time (t) are a Boolean function of State (t) and (sometimes) Inputs (t). Inputs Outputs Combinational Logic Storage Elements CLK Next State State 两个输入: 现态和信号输入, 两个输出: 次态和输出,对应两个方程.

35 Example 1 (from Fig. 5-15) Input: x(t) Output: y(t)
State: (A(t), B(t)) What is the Output Function? What is the Next State Function? A C D Q y x B CP 三组方程: 输入,激励方程, 输出方程, 次态方程.

36 Example 1 (from Fig. 5-15) (continued)
Boolean equations Input functions: DA= A(t)x(t) + B(t)x(t) DB= A(t)x(t) Next State equations: A(t+1) = DA B(t+1) = DB Output： y(t) = x(t)(B(t) + A(t)) C D Q Q' y x A B CP Next State Output

37 Example 1 (continued) Where in time are inputs, outputs and states defined? 1 DA DB

38 State Table Characteristics
State table – a multiple variable table with the following four sections: Present State – the values of the state variables for each allowed state. Input – the input combinations allowed. Next-state – the value of the state at time (t+1) based on the present state and the input. Output – the value of the output as a function of the present state and (sometimes) the input. From the viewpoint of a truth table: the inputs are Input, Present State and the outputs are Output, Next State 状态表: 全名是状态真值表 现态: 下一个时钟脉冲来到之前的状态取值, 次态是时钟脉冲来到之后的状态

39 Example 1: State Table (from Fig. 5-15)
The state table can be filled in using the next state and output equations: A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) =A (t)x(t) y(t) =x (t)(B(t) + A(t)) Present State Input Next State Output A(t) B(t) x(t) A(t+1) B(t+1) y(t) 1

40 Example 1: Alternative State Table
2-dimensional table that matches well to a K-map. Present state rows and input columns in Gray code order. A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) =A (t)x(t) y(t) =x (t)(B(t) + A(t)) Present State Next State x(t)= x(t)=1 Output x(t)=0 x(t)=1 A(t) B(t) A(t+1)B(t+1) A(t+1)B(t+1) y(t) y(t) 0 0 0 1 1 1 1 0 二维状态表在设计的时候很有用, 左边是当前状态, 上方是输入, 中间是卡诺图.

41 State Diagrams The sequential circuit function can be represented in graphical form as a state diagram with the following components: A circle with the state name in it for each state A directed arc from the Present State to the Next State for each state transition A label on each directed arc with the Input values which causes the state transition, and A label: On each circle with the output value produced, or On each directed arc with the output value produced.

42 Example 1: State Diagram
A B 0 0 0 1 1 1 1 0 x=0/y=1 x=1/y=0 x=0/y=0 Which type? Present State Input Next State Output A(t) B(t) x(t) A(t+1) B(t+1) y(t) 1 Type: Mealy X=0时全部回到同一个状态, 初始化或者复位的功能. X=1的时候把所有状态顺序遍历一遍，就是计数器。一般的计数器遍历的状态是0，1，2，3，。。。 这种叫加1计数器。 广义的计数器就是把所有的状态都遍历一遍。 最后一个状态不动了，就是饱和计数器。

43 Moore and Mealy Models Sequential Circuits or Sequential Machines are also called Finite State Machines (FSMs). Two models exist: In real design, models are sometimes mixed Moore and Mealy Moore Model Named after E.F. Moore. Outputs are a function ONLY of states Usually specified on the states. Mealy Model Named after G. Mealy Outputs are a function of inputs AND states Usually specified on the state transition arcs.

44 Moore and Mealy Example Diagrams
State Diagram of Mealy Model maps inputs and state to outputs State Diagram of Moore Model maps states to outputs 1 x=1/y=1 x=1/y=0 x=0/y=0 01/0 10/1 x=1 x=0 00/0 摩尔型比米利型要多一个状态, 把输入的不同表示出来.

45 Moore and Mealy Example Tables
Mealy Model state table maps inputs and state to outputs Moore Model state table maps state to outputs Present State Next State x=0 x=1 Output 1 Present State Next State x=0 x=1 Output 00 01 10 1

46 Sequential Circuit Analysis
Sequential Circuit Analysis is an procedure of specifying the logic diagram of a given sequential circuit. A state table and state diagram are presented to describe the behavior of the circuit, demonstrate the time sequence of inputs, outputs and states, and illustrate the functionality of the given circuits. 指明电路的功能比较难, 想出设计的原始意义要靠经验的积累.

47 Sequential Circuit Analysis Procedure
1. Derive the output equations，excitation equations and Next state functions 2. Derive the truth table with state: Inputs: inputs of circuit, present state of the circuit Outputs: outputs of circuit, next state of all flip-fops 3. List the next state of the sequential circuit 4. Obtain a state diagram 5. Analyze the external performance of the circuit 6. Verify the correctness of the circuit, check the self-recovery capability and draw the timing parameters 评价: 能不能初始化, 电路工作的时候是不是稳定, 抗干扰情况怎么样等等. 自恢复能力: 有些电路有一些游离状态, 如果外部有干扰, 进入游离状态, 就不具备自恢复功能.

48 Example 2: Sequential Circuit Analysis
Clock Reset D Q C R A B Z Logic Diagram: 这种电路一般就是计数器，不需要有输入

49 Example 2: Flip-Flop Input Equations
Variables Inputs: None Outputs: Z State Variables: A, B, C Initialization: Reset to (0,0,0) Equations A(t+1) = Z = B(t+1) = C(t+1) = A(t+1) = BC B(t+1) = B’C + BC’ C(t+1) = A’C’ Z = A

50 Example 2: Flip-Flop Input Equations
Variables Inputs: None Outputs: Z State Variables: A, B, C Initialization: Reset to (0,0,0) Equations A(t+1) = B(t)C(t) Z = A(t) B(t+1) = B(t)C(t) + B(t)C(t) C(t+1) = A(t)C(t) A(t+1) = BC B(t+1) = B’C + BC’ C(t+1) = A’C’ Z = A

51 Example 2: State Table X’ = X(t+1) A B C A’B’C’ Z 0 0 0 0 0 1 0 1 0
A’B’C’: , , , , , , , Z:

52 Example 2: State Table X’ = X(t+1) A B C A’B’C’ Z 0 0 0 0 0 1 0 1 0
1 A’B’C’: , , , , , , , Z:

53 Example 2: State Diagram
Which states are used? What is the function of the circuit? Does it have self-recovery capability? 000/0 011/0 010/0 001/0 100/1 101/1 110/1 111/1 Reset ABC Only states reachable from the reset state 000 are used: 000, 001, 010, 011, and 100. The circuit produces a 1 on Z after four clock periods and every five clock periods thereafter: 000 -> 001 -> 010 -> 011 -> 100 -> 000 -> 001 -> 010 -> 011 -> 100 … 这也是计数器，0，1，2，3。 这个计数器是循环的，会溢出，不像前面一个是饱和的。

54 Circuit and System Level Timing
Consider a system consists of flip-flops connected by logic: If the clock period is too short, data changes may not be able to propagate through the circuit to flip-flop inputs before the setup time interval begins C D Q Q' CLOCK 系统是否能够正常工作，延迟是一个很重要的原因。 用基本与非门实现可以看到信号是通过哪条线传输的；如果用FPGA实现电路，是通过查表的方式，如果通过的门电路比较多，一个查找表不够，有的时候需要通过几个查找表，延迟就会不一样。 调试电路的时候时序问题是最难的，看不见摸不着。

55 Circuit and System Level Timing (continued)
Timing components along a path from flip-flop to flip-flop t p pd,FF pd,COMB slack s C (a) Edge-triggered (positive edge) t p pd,FF pd,COMB slack s C 所以把触发器的时序要求和组合电路结合起来，得到一个系统级的时序要求。要求在一个周期内，除去触发器接受信号的延迟，组合电路的延迟，下一个触发器信号的建立时间之外，还有一定的松弛时间，这个时候电路才是安全的。 (b) Pulse-triggered (negative pulse)

56 Circuit and System Level Timing (continued)
New Timing Components tp - clock period - The interval between occurrences of a specific clock edge in a periodic clock tpd,COMB - total delay of combinational logic along the path from flip-flop output to flip-flop input tslack - extra time in the clock period in addition to the sum of the delays and setup time on a path Can be either positive or negative Must be greater than or equal to zero on all paths for correct operation

57 Circuit and System Level Timing (continued)
Timing Equations tp = tslack + (tpd,FF + tpd,COMB + ts) For tslack greater than or equal to zero, tp ≥ max (tpd,FF + tpd,COMB + ts) for all paths from flip-flop output to flip-flop input Can be calculated more precisely by using tPHL and tPLH instead of tpd , but requires consideration of inversions through paths

58 Calculation of Allowable tpd,COMB
Compare the allowable combinational delay for a specific circuit: a) Using edge-triggered flip-flops b) Using master-slave flip-flops Parameters tpd,FF(max) = 1.0 ns ts(max) = 0.3 ns for edge-triggered flip-flops ts = twH = 2.0 ns for master-slave flip-flops Clock frequency = 250 MHz

59 Calculation of Allowable tpd,COMB (continued)
Calculations: tp = 1/clock frequency = 4.0 ns Edge-triggered: 4.0 ≥ tpd,COMB + 0.3, tpd,COMB ≤ 2.7 ns Master-slave: 4.0 ≥ tpd,COMB + 2.0, tpd,COMB ≤ 1.0 ns Comparison: Suppose that for a gate, average tpd = 0.3 ns Edge-triggered: Approximately 9 gates allowed on a path Master-slave: Approximately 3 gates allowed on a path

60 Assignment Reading: pp. 208-230, 306-310 Problems: 5-2、5-6
5-9、5-12、6-9、6-10