本章学习内容
Base:

• Latches (锁存器) and Flip-Flps (触发器)
• Synchronous Logic Design
• Finite State Machine
  To increse speed of sequential logic:
• Timing of Sequential Logic
• Parallelism

本章重点:
(深蓝色部分为本章介绍的重点，浅蓝色部分为次重点)

3.2 Latches and Flip-Flops

bistable element: 指的是一个 element 有两种稳定的状态。

比如 cross-coupled inverter (即交错配对反向器，两图表示的是同一个东西，只是 (b) 图更加强调来 cross-couple):

bistable element 有: cross-coupled inverters, latches (锁存器), flip-flops (触发器).

cross-coupled inverters 与 latches, flip-flops 的区别:

cross-coupled inverters 没有输入端，无法控制它的状态。 latches 和 flip-flops 提供输入端来控制状态。

cross-coupled: I1 的输入是 I2 的输出，I2 的输入是 I1 的输出。

N 个稳定状态可以传递 比特的信息，比如 2 个状态可以传递 1bit 的信息，因为 1bit 有两个状态。

当电源刚打开时，sequential circuit 的初始状态是未知的。

3.2.1 SR Latch

(SR 锁存器)

SR 中 S 表示 set，即将 Q 设置为 1；R 表示 reset，即将 Q 设置为 0。所以:

3. (所以说 SR latch 有记忆功能)
4. (当输入同时为 1 时，输出都为 0)

3.2.2 D Latch

(也被称为 Transparent Latch, Level-sensitive Latch，Transparent 有透明之意，Level 表示电平)

SR Latch 的缺点:

• 当输入 S，R 同时为 1 时，输出都为 0。这种行为直觉上让人觉得奇怪。
• SR Latch 混淆了 sequential logic 中 when 和 what 的问题，让 when 和 what 是同时发生的，设计 sequential logic 时，我们是希望将 when 和 what 分开的。
  • when 表示 S, R 输入如果改变，什么时候应该改变输出
  • what 表示 S, R 输入如果改变，应该输出什么。

D Latch 就解决了这个问题， D 代表 data input， CLK 代表什么时候改变输出的状态，并且 D Latch 不会出现 SR 中 的情况:

• 当 CLK 为 0 时，
  Q =
• 当 CLK 为 1 时，latch is transparent，此时可以把 D latch 看作是一个 buffer。
  Q = D

3.2.3 D Flip-Flop

(也被称为 master-slave flip-flop, edge-triggered flip-flop)

Flip-Flops 和 Latches 的区别:

1. Latch (锁存器) 指的是不需要 edge-triggered (边沿触发) 的 bistable element.
2. Flip-Flops 指的是 edge-triggered 的 bistable element.
3. 通常来说 Latch 指的是 D latch, flip-flop 指的是 D flip-flop, 因为这两种类型的锁存器和触发器是最常用的。

D Flip-Flop: D 触发器在触发沿将输入数据信号 D 复制到 Q，在其他时间保持状态。

• 符号表示中的三角符号表示边沿触发
• 通常 用不到时可以将 D 触发器到符号写为 (c) 中的形式
  
  
  
  

3.2.4 Register

Register 是计算机中重要组成部分。

Register (寄存器) 的构建方法:
一个 Nbit 的寄存器可以由 N 个 D 触发器共用一个时钟组成，所有触发器中的信号都是同时更新的。

3.2.5 Enabled Flip-Flop

(电平启动触发器)

Enabled flip-flop (电平启动触发器) 增加一个新的输入 EN or ENABLE 来决定输入信号是否在时钟边沿载入触发器。

当 EN=1, Enabled Flip-Flop 和原始的 Flip-Flop 行为一致。
当 EN=0, Enabled Flip-Flop 忽略边沿时钟触发，输出保持原来的状态。

Enabled Flip-Flop 的两种构建方法 (a) 和 (b):
(a) 使用 2:1 的 multiplexer 进行构建
(b) 在 CLK 上添加 Gate 进行构建 (bad idea, 可能会导致 Glitch，在 Section3.5.3 详细说明)

3.2.6 Resettable Flip-Flop

(复位触发器)

一个可复位的触发器增加了另一个叫做 RESET 的输入。当 RESET 为 FALSE 时，复位触发器的行为就像一个普通的 D 触发器。当 RESET 为 "TRUE" 时，可复位的触发器忽略输入数据信号 D，并将输出重置为 0。
(用 Resettable Flip-Flop 可以对上电后的状态进行初始化)

Resettable Flip-Flop 可以分为 synchronously and asynchronously flip-flop:
Synchronously resettable flip-flops (同步可复位触发器) 只在触发的时钟边沿进行复位。
Asynchronously resettable flip-flops (异步可复位触发器) 只要复位型号到来即可进行复位。

Settable Flip-Flop:
(置位触发器)
一个置位触发器增加了另一个叫做 SET 的输入。当 SET 为 FALSE 时，置位触发器的行为就像一个普通的 D 触发器。当 SET 为 TRUE 时，置位触发器忽略数据信号输入 D，并将输出设置为 1。

3.2.8 Putting It All Together

D Latch 和 D flip-flop 画波形图 (waveforms) 的方法:
D Latch: 数据输入发生改变 + CLK == 1 ==> 输出发生改变
D flip-flop: edage-triggered ==> 数据输入复制到输出端

3.3 Synchronous Logic Design

3.3.2 Synchronous Sequential Circuits

什么是 Sequential Circuits?
The outputs of sequential logic depend on both current and prior input values.

什么是 Synchronous Sequential Circuits?
A synchronous sequential circuit has a clock input, whose rising edges indicate a sequence of times at which state transitions occur.

什么是 Asynchronous Sequential Circuits?
Asynchronous circuit design in which outputs are directly fed back to inputs.

为什么我们要使用 Synchronous Sequential Circuits 而不是 Asynchronous?
Sequential circuits with cyclic paths can have undesirable races or unstable behavior. Analyzing such circuits for problems is time-consuming, and many bright people have made mistakes.

Synchronous Sequential Circuits 中的 timing specification: 什么是 timing specification?:
stands for the time of propagation from clock to Q, where Q indicates the output of a synchronous sequential circuit.(最大延时)

stands for the time of contamination from clock to Q.
These are analogous to and in combinational logic.(最小延时)

Combinational Logic Circuits 中的 timing specification:
Propagaton delay: The propagation delay is the maximum time from when an input changes until the output or outputs reach their final value.
Contamination Delay: The contamination delay is the minimum time from when an input changes until any output starts to change its value.

The rules of synchronous sequential circuit composition:

1. Every circuit element is either a register or a combinational circuit.
2. At least one circuit element is a register.(一个 D flip-flop 也可以算是一个存储 1bit 信息的 register)
3. All registers receive the same clock signal.(所有寄存器接受的时钟信号来自于一个时钟源)
4. Every cyclic path contains at least one register.(每一个环路上都至少有一个寄存器)

synchronous sequential circuit 主要有三种类型:

1. Flip-flops
2. finite state machines(cover in later chapter)
3. pipelines(cover in later chapter)

3.4 Finite State Machine(FSM)

什么是 Finite State Machine?
如果一个电路中有 k 个寄存器并且假设每个寄存器存储 1bit 的数据，那么这个电路总是在 个状态其中之一。

FSM 的组成结构 (细分，图片描述见下面):

1. 输入: M bits
2. 输出: N bits
3. 状态的 bit 数: k bits
4. 一个时钟
5. 一个复位信号 (可选)

FSM 的组成结构 (泛分):

1. two blocks of combinational logic
   • next state logic
   • output logic
2. a register(store the state)

FSM 有两种类型 (根据 function specification 划分):

1. Moore machines
   输出只取决于当前的状态
   next state = f (current state + input), 其中 f 表示 next state logic
   output = g (current state), 其中 g 表示 current state

2. Mealy machines
   输出不仅取决于当前的状态，还取决于当前的输入。
   next state = f (current state, input), 其中 f 表示 next state logic
   output = g (current state, input), 其中 g 表示 current state

同一个问题即可以使用 Moore machines 解决，也可以使用 Mealy machines 解决，具体区别见 3.4.3

FSM 的作用:
有限状态机提供了一种系统的方法来设计任意功能的 synchronous sequential circuits。

3.4.1 FSM Design Example

本节以一个红绿灯的例子为例，教我们使用 FSM 的方法来设计指定功能要求的 synchronous sequential circuits。

设计方法:

1. 根据题目条件画出 state transition diagram (to indicate all the possible states of the system and the transitions between these states.)
2. 根据 state transition diagram 列出 State transition table (该表用来表示函数 next state = f (current state, input))
3. 编码 state 和 output
4. 将 2 中的状态转移表中 current state 和 next state 修改编码格式
5. 列出 output table (如果是 Moore FSM 输入为当前状态；如果是 Mealy machine 输入为当前状态和 input，即上一节说的函数 g)
6. 根据 current state 和 next state 选择合适的 register 和 CLK
   (通常来说 binary encoding 可以选用一个多位的寄存器，one hot 使用多个 1 位的寄存器，因为 binary encoding 的初始状态可以设计为 00..0，使用 resettable register 即可，但是 one hot 的初始状态有一个 1，所以需要 resettable register 和 settable register，具体见课本 Section 3.4.2)
7. 根据 4 中的表格使用 SOP 列出表达函数 f 的 boolean equation 并画图
8. 根据 5 出的表格使用 SOP 列出表达函数 g 的 boolean equation 并画图

3.4.2 State Encodings

在上一节设计方法的第三个步骤中对 state 和 output 的编码是随意的，不同的编码选择将会产生不同的电路。
所以一个存在的问题是：什么样的编码格式能产生最少 logic gate 和最小 propagation delay 的电路？
没有一个简单直观的方法能找到，但是可以借助 CAD 辅助寻找合适的编码方式。

最常见的两种编码方式:binary encoding and one-hot encoding

1. binary encoding
   Each state/output is represented as a binary number. 比如 2 位二进制数就表示 4 个状态 (00, 01, 10, 11)。
   特点: Because K binary numbers can be represented by bits, a system with K states only needs log2K bits of state.

2. one-hot encoding
   A separate bit of state is used for each state. 比如 4 个状态就需要 0001, 0010, 0100, 1000 来表示。
   特点: Each bit of state is stored in a flip-flop, so one-hot encoding requires more flip-flops than binary encoding. However, with one-hot encoding, the next-state(3.4 中说的函数 f) and output logic(3.4 中说的函数 g) is often simpler, so fewer gates are required.

具体例子看书上。

3.4.3 Moore and Mealy Machines

两种 FSM 的区别还体现在状态转移图中: Moore Machines 的输出在状态的圈中 (因为 output 只依赖于 current state); 而 Mealy Machines 的输出在状态转移的弧线上 (output 依赖于 current state and input)。

书上的例子还说明 Mealy 的输出比 Moore Machine 快上升一个周期，因为 output 对 input 立即做出反应，而不是等待状态变化后再输出。

所以在选择 FSM 时，要考虑需要输出在什么时候做出反应。

• 如果需要输出在输入变化后就立刻做出反应：使用 Mealy Machine
• 如果需要输出在输入变化后到达下一个状态后在做出反应：使用 Moore Machine
  (看书上例子的状态转移也能明显的看出来)

3.4.4 Factoring State Machine

Factoring State Machine: Broke down complex state FSM into multiple interacting simpler state machines

3.4.5 Deriving an FSM from a Schematic

(逆向工程：从电路图得出 FSM 状态转化图)

设计步骤:

1. Examine circuit, stating inputs, outputs, and state bits.(根据 output 是否直接和 input 相连确定是 Moore/Mealy State)
2. Write next state and output equations.
3. Create next state and output tables.
4. Reduce the next state table to eliminate unreachable states.
5. Assign each valid state bit combination a name.
6. Rewrite next state and output tables with state names.
7. Draw state transition diagram.
8. State in words what the FSM does.

3.4.6 FSM Review

(正向过程：从状态转化图到电路图 example)

1. Identify the inputs and outputs.
2. Sketch a state transition diagram.
3. For a Moore machine:
   – Write a state transition table.
   – Write an output table.
4. For a Mealy machine:
   – Write a combined state transition and output table.(因为 output 和 next state 都依赖于 input and current state, 所以可以画在一个表中，参考 3.4.3)
5. Select state encodings—your selection affects the hardware design.3.4.2
6. Write Boolean equations for the next state and output logic.
7. Sketch the circuit schematic.

FSM 给了我们如何设计 sequential circuit 指导及其重要，之后我们也会经常用到 FSM.

3.5 Timing of Sequential Logic

Aperture time: During clock edage (上升沿 / 下降沿触发) the input must be stable for the flip-flop to produce a well-defined output.

Aperture of a sequence element = a stetup time before the clock edage + a hold time after the clock edage

Static discipline(Section 1.6.5):
Given logically valid inputs, every circuit element will produce lodically valid outputs.

Dynamic disciplien (用来保证 flip-flop 在边沿触发采样信号期间，信号不会发生改变)
具体细节见下一节。

3.5.1 The Dynamic Discipline

The dynamic discipline: the inputs of a synchronous sequential circuit must be stable during the setup and hold aperture time around the clock edge.

Sequential Circuits 中的 timing specification:
stands for the time of propagation from clock to Q, where Q indicates the output of a synchronous sequential circuit.(最大延时)
stands for the time of contamination from clock to Q. (最小延时)

Combinational Logic Circuits 中的 timing specification:
Propagaton delay: The propagation delay is the maximum time from when an input changes until the output or outputs reach their final value.
Contamination Delay: The contamination delay is the minimum time from when an input changes until any output starts to change its value.

3.5.2 System Timing

is the time between rising edges of a repetitive clock signal.
is the clock frequency.

其中灰色的箭头分别表示 contamination delay of Q1 () 和 contamination delay of combinational logic ()

蓝色的箭头表示 propagration delay of Q1 () 和 propagation delay of combinational logic ()

Setup Time Constraint

(Setup Time 对 flip-flops 的限制使得逻辑电路中组合逻辑部分的设计也受到了限制)

为了能 flip-flop 的输入能采样成功，在时钟触发边沿到来前的一小段时间内输入应该保持不变。

Combinational Logic 允许达到的最大延时:

该等式也称为 setup time constraint or max-delay constraint, 因为组合逻辑的延时限制取决于 flip flop 的上升沿到来前要求输入保持不变的时间 (即) 和 flip-flop 的最大延时 (). 对应电路图为:

通常来说，时钟周期 是由 market department 根据市场竞争来确定的， 和 是由晶体管制造厂商 (如台积电) 来决定的，唯一芯片设计者能够修改的只有.

Hold Time Constraint

(Filp-flop 对 Hold Time 限制了)

为了 flip-flop (触发器) 的输入能采样成功，在时钟触发边沿到来后的一小段时间内输入应该保持不变。

因此有等式:

从而有:

该等式也称为 hold time constraint or min-delay constraint, 因为组合逻辑的最小延时限制取决于 flip flop 的上升沿到来后要求输入保持不变的时间 (即) 和 flip-flop 的最小延时 (). 对应电路图为:

通常来说 和 都不受芯片设计者的控制，设计者只能通过调整电路的复杂性来降低或者提高组合逻辑电路的最小时延。

注意：这个图比较容易混淆，在第一个上升沿到来时，R1 开始对输入进行采样。但以此同时，R2 也在对 D2 进行采样，在上升沿结束的一小段时间内，D2 应该保持不变，才能使得 R2 的输入采样成功。其中 是 R1 的最小时延， 是组合逻辑的最小时延， 则属于 R2.

当级联两个 flip-flop 时. 因为它们之间没有组合逻辑电路。 可以将上面的等式改为:

所以说，对 flip-flop 有要求 hold time 应该小于其最小延时 (contamination delay), 通常来说 flip-flops 都被设计为, 所以上面的等式总是满足的。

3.6 Parallelism

The latency is the time required for a token to pass from start to end.

The throughput is the number of tokens that the system can process per unit time.

Parallelism improves system throughput.