IV. Sequential Circuits

Sequential Circuit Analysis

Introduction to Sequential Circuits

我们将某一时刻存储存储元件(storage element) 中的二进制信息称为该时刻时序电路的状态(state)。

按照输出除了基于当前状态之外是否依赖于输入，可以将视时序电路分为：

• Mealy 型电路(Mealy model circuit)：输出只和前一个状态有关
• Moore 型电路(Moore model circuit)：输出和输入及当前输入有关

根据输入信号的时间和内部状态改变的时间，可以将时序电路分为：

• 同步时序电路(synchronous sequential circuit)：
  • 同步时序电路是通过时钟发生器(clock generator) 产生周期性的时钟脉冲(clock pulse) 来实现的。
  • 把时钟脉冲作为存储元件输入信号的同步时序电路称为钟控时序电路(clocked sequential circuit)。
• 异步时序电路(asynchronous sequential circuit)：
  • Behavior defined by knowledge of inputs at 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!

Discrete-Event Simulation

可以通过离散事件模拟(discrete event simulation) 来更好的理解时序电路的时间行为。离散事件模拟的规则如下：

我们以一个二路选择器为例：

• 毛刺(glitch)：或称瞬态错误。当 $S$ 从 $1$ 变为 $0$ 时，由于非门有 0.2ns 的延迟，由 $A \overline{S}$

如果把选择器的输出 $Y$ 直接连到输入 $A$ 上呢？

• 这里的 Y 不仅是输出，还可以记忆电路的状态(state)。

如果再多加一个反相器(inverter) 呢？

时钟发生器

Latches

S-R and Active-Low S-R Latches

SR 锁存器通过两个或非门实现。

在 SR 锁存器中，$S=1,\ R=1$ 的输入是禁止的(forbidden) 或者说未定义的(undefined)，此时输出端 $Q=0$ 和 $\overline{Q}=0$ 同时成立。一般不使用这种状态。

S’R’ 锁存器通过两个与非门实现。

• S’R’ 锁存器是 $0$ 触发的，即 $\overline{S}=0$ 时将 $Q$ 置 $1$；而 SR 锁存器哈斯 $1$ 触发的，即 $S= 1$ 时将 $Q$ 置 $1$。不过从结果上来说，置为时 $Q$ 的值与 $S$ 的值应相同。

• 如果 $R$ 和 $S$ 同时从 0 变成 1，则输出是不稳定的(unstable)。如果两个与非门的时延完全相同，则输出会在 01 之间震荡，否则会稳定在 $Q=0$ 或 $Q=1$ 中的一个状态，取决于两个与非门的时延。

Clocked S-R Latches

多输入一路信号 $C$ 与 $S,R$ 信号作与或，这里 $C$ 可以理解为 控制(control) 或时钟(clock)。只有 $C=1$ 时输入才被接受；$C=0$ 时无论输入如何改变锁存器都为保持状态。

D Latches

给 Clocked S-R Latch 添加一个反相器可以得到 D 锁存器(D latch)，这样 $S$ 的值和 $R$ 的值一定相反，而我们通过控制信号 $C$ 来控制是否应处于保持状态。当控制输入信号有效（$C=1$）时输出 $Q$ 会根据输入 $D$ 的改变而改变，从这种意义上来讲，锁存器是透明(transparent) 的。

透明的问题——空翻(the latch timing problem)

如果直接把输出 $\overline{Q}$ 接到 $D$ 上时，若 $C=1$，则 D 锁存器的值将不断跳变，这就是空翻问题。这主要是因为 D 锁存器的输入和输出是同时允许变化的（不是同时变化，是指在输出可以变化的时候输出也能变）

空翻的问题不光在 D 锁存器中存在，而是锁存器的普遍问题。

$C$	$D$	$Q_{t+1}$	描述
0	X	$Q_{t}$	输出不改变
1	0	0	复位
1	1	1	置位

The Latch Timing Problem

锁存器存在锁存器的时序问题(the latch timing problem)：在时钟脉冲有效（$C=1$）时，输入信号的改变随时会引起输出的改变，即上文所说的透明性。那么当时钟脉冲保持为 1 时，锁存器的输入信号可能因为其余锁存器的输出信号的改变而改变，从而在一个时钟周期内发多次变化，这是我们要引入触发器的原因。

如考虑这一电路中，$C=1$ 的时间内 $Y$ 的值会反复振荡，且最后结果不确定。而我们期望的功能时，一整段 $C=1$ 只会导致 $Y$ 的值改变一次。

一种可行的解决方案是：$C=1$ 时（输入的时候）先不改变输出，等到 $C=0$ 时在改变，这就是主从触发器的原理。

Standard Symbols for Latches

Flip-Flops

Master-Slave Flip-Flops

主从触发器(master-slave flip-flop) 一般通过将两个 SR 锁存器先后连接起来所得到，其中前者称为主锁存器(master latch)，后者称为从锁存器(slave latch)，两者的控制信号是相反的。

主从触发器的缺憾——一次性采样问题(1s catching problem)：

如果 $C=0$ 时触发器的输入是 $S=0$，$R=0$，但是由于电路问题出现了 $S=1$ 或 $R=1$ 的毛刺(glitch)，就会改变主锁存器的值（而不是像期望的那样处于保持状态），并将这一有问题的修改在下一个时钟上升沿到来时传递给从锁存器。

为了避免发生一次性采样问题，主从触发器要求其的输入信号在半个时钟周期内不能改变（即 $C=0$ 的时间内）。

Edge-Triggered Flip-Flops

边缘触发式(edge-triggered) 触发器忽略了保持阶段的时钟脉冲，只有在时钟信号发生跳变时（正边沿到来时或负边沿到来时）触发。

其逻辑结构可以看作把主从触发器中的主锁存器换成 D 锁存器，

J-K Flip-Flops

$J$	$K$	$Q_{t+1}$	描述
0	0	$Q_t$	保持
0	1	0	复位
1	0	1	设定
1	1	$\overline{Q_t}$	翻转

T Flip-Flops

$T$	$Q_{t+1}$	描述
0	$Q_t$	保持
1	$\overline{Q_t}$	翻转

Flip-Flop Timing Parameters

$t_s$ - 建立时间(setup time)：输入数据在时钟信号的上升沿或下降沿到来之前，需要保持稳定的时间。

• 对于主从触发器，为了避免一次性采样问题，其 setup time 应为半个时钟周期。即对于高电平激活的电路，其在时钟信号维持高电平期间不能改变输出。
• 对于边缘触发器，其所需要的 setup time 比主从触发器小很多，但也并不是 $0$。

$t_h$ - 保持时间(hold time)：输入数据在时钟信号的上升沿或下降沿到来之后，需要保持稳定的时间。

• 经常等于 $0$，即时钟脉冲之后对输入信号是否保持没有要求。

$t_w$ - 时钟脉冲宽度(clock pulse width)：一个时钟周期中，时钟信号为高电平（$t_{wh}$）或低电平（$t_{wl}$）的时间。取决于触发器是在时钟信号的上升沿触发还是在时钟信号的下降沿触发。

$t_{pd}$ - 传播延迟(propagation delay)：从时钟信号的上升沿或下降沿（注意这里和组合电路中的定义略有不同）到触发器输出稳定，所需要的时间。其中

• 输出信号从高到低所需要的传播延迟定义为 $t_{\text{PHL}}$；
• 输出信号从低到高所需要的传播延迟定义为 $t_{\text{PLH}}$。

两者可能不同。对触发器传播延迟的定义可取两者的最大值或平均值，如 $t_{pd} = \max\{t_{\text{PHL}}, t_{\text{PLH}}\}$

Standard Symbols for Flip-Flops

Flip-Flop Description Methods

常用于分析（从当前状态和输入中得到下一状态）：

• 特征表(characteristic table)：定义了下一状态与当前状态和输入的关系。
• 特征方程(characteristic equation)：用布尔函数来表示下一状态与当前状态和输入的关系。

常用于设计（从状态中得到输入）：

• 激励表(excitation table)：列出所有可能的当前状态和下一状态，从而确定输入。

Sequential Circuit Analysis

General Model

对于一个输入为 $X$，输出为 $Y$，状态为 $(A,B)$ 的时序电路可以这样定义其：

• 输出方程(output function)：$y = \overline X (B + A)$。
• 触发器输入方程(flip-flop input equation)：$D_A = AX+BX,\quad D_B=\overline AX$。
• 次态方程(next state function)：$A_{t+1} = D_A,\quad B_{t+1} = D_B$。

State Tables

状态表(state table) 由四部分组成：当前状态(present state)、输入(input)、下一状态(next state) 和输出(output)。

这里我们不妨假设共有 $n$ 个输入和 $m$ 个触发器，则 Mealy 型电路的状态图可表示如下，共 $2^{m+n}$ 行，对应着可能的所有输出。

由于 Moore 型电路的输出只和当前状态有关，所以只需要 $2^m$ 行即可，可以把 $2^n$ 种不同输出所转移到的下一状态写到列上。

Excitation Tables

用当前状态和下一状态来描述输入（展示从当前状态转移到下一状态所需要的输入）。

Excitation Equations

State Diagrams

• 节点表示状态，边表示输入/输出（这一输入下会转移到的状态及对应的输出）

• 节点表示状态/输出，边表示输入（这一输入下会转移到的状态）

我们称呼两个状态是等价(equivalent) 的，当且仅当对于任意的输入序列，其输出序列都是相同的。如下面这个例子，

State Machine Diagrams

对于更复杂的逻辑，我们可能需要用状态机(state-maching diagram) 来表示。

听说考试没有考过？咕了咕了。

Delay Analysis

注意 $t_\text{PLH} = t_\text{PHL}$ 区分的是输出而不是输入。

Sequential Circuit Design

Design Procedure

1. 确定系统的行为；
   1. 描述系统行为过程中，要注意状态的复用（不过并非状态越少成本就越小，这里有触发器数量和组合逻辑电路的 trade-off）；
   2. 确定电路的初始状态（复位状态(reset state)，通过给定复位(reset)信号实现）；
      • 复位一般可以是异步的；
2. 阐述输入和输出之间的逻辑关系，并用真值表或逻辑表达式表达出来；
3. 给设计好的状态编码赋值，得到具体的状态表；
   1. 我们可以使用 按计数顺序、 按格雷码、用独热码 来给状态赋值，更系统的方法比较复杂，不做讨论；
   2. 其中还有一种情况是所需要的状态不能完整填充  2𝑛2n  种情况，需要设计无效状态，这种时候可以不考虑它们；
4. 根据状态表确定使用的触发器及其输入方程；
5. 根据状态表确定输出方程；
6. 优化输入方程和输出方程；
7. 将优化后的逻辑设计工艺映射到硬件实现上；
8. 验证正确性（在仿真环境中）；
   • 主要就是看能不能复现状态图；

State Assignment

用 $n$ 位二进制给 $m$ 种状态各自分配一个不同的编码，需要使用 $n$ 个触发器。剩余 $2^n-m$ 个状态未使用，可视为不定项。

常见的状态赋值方法如下：

赋值方法	特性
按照计数的顺序(counting order) 分配
按照格雷码顺序(Gray code order) 分配	在使用卡诺图作化简时非常方便
单热点(one-hot) 赋值	每个状态对应一个触发器，跳变最少效率最高