跳转至

四、状态机图及应用

状态图的问题

大型电路中的状态图应该如何表示？

  • 数学基础：有限状态机

  • 3个集合

    • I : 输入组合集合

    • O: 输出组合集合

    • S : 状态集合

  • 2个函数

    • f(I, S)：下一个状态函数

    • h(S) [Moore 型]：输出函数

    • g(I, S) [Mealy 型]：输出函数

  • 状态图和状态机是表达有限状态机两种方式

  • 状态图和状态表==需要==：

  • 问题1：表达下一状态函数，需==枚举所有输入组==合

    • 1输入： 2

    • 2输入： 4

    • n输入：\(2^n\)

  • 表达输出函数时：

    • 问题2：Mealy 型：每个状态==枚举所有输入组合==

    • 问题3：Mealy 型：每个(状态-输入)对==写出所有输出==

    • 输出为UVWXYZ，U=1，100000

    • 问题3：Moore型：==写出所有输出==

    • ==Moore比Mealy表达高效==：不用枚举所有输入组合

  • Mealy输出

    • 问题4：只能表示在转移弧上

    • 不能表达在状态上

状态机图模型

  • 怎么办？

  • 一个现象

  • 输入为X, Y, Z

  • 输入为100,101,110,111，状态A从转移到B

  • 即输入为X时（由卡诺图可是此时输入为X），状态从A转移到B （用表达式X来代表一些条件从而使得更简洁）

  • 可解决问题1，问题2

  • 问题3：默认值，不是默认值才显示表达

  • 问题4：划分转移条件和输出条件

状态图 状态机图
image-20230610160416663 image-20230610160500923

条件

  • 输入条件

  • 输入变量的==布尔表达式或方程==，值为0或1

  • 转移条件(Transition condition，TC)

  • 转移弧上==表达状态转移==的输入条件，为1则转移

  • 输出条件(Output condition，OC)

  • ==表达输出==的输入条件（该条件后面紧跟着/输出），为1则发生输出行为

  • 1个输入条件==可同时==为TC和OC （在弧上且后面有/输出）

状态转移

  • 无条件转移

  • 弧上==无转移条件==或转移条件含==常量1==

  • 条件转移

  • 转移弧上有==一或多个转移条==件，任何一个转移条件为1，则转移发生

输出行为

  • Moore输出

  • ==只依赖于状态==，用一条线和相应状态连接

  • 非转移条件依赖(Transition condition-independent, ==TCI==)

  • 输出行为由==输出条件驱动==，和==相应状态连接==

  • 转移条件依赖(Transition condition-dependent, ==TCD==)

  • 输出行为由==转移条件驱动==

  • 转移和输出条件依赖(Transition and output condition-dependent，==TOCD==)

  • 输出行为由==输出条件驱动==，和==转移条件连接==
Moore TCI TCD TCOD
image-20230610161626501 image-20230610161636944 image-20230610161646679
把原来在状态里面的output全部拿了出来 输入A为1时输出Y为1，输入B为1时输出Z为1 满足转移条件时输出，跟传统的Mealy型输出是一样的 输入C=1且转移条件满足时输出Y=1
输出行为无条件（只和状态有关） 输出行为和输出条件有关 输出行为和转移条件有关 输出行为和（输出条件+转移条件）有关

  • 输出行为

  • 单变量Z的==出现==，表示==Z=1==

  • 向量变量==Z=向量值==，指定了Z的值

  • 否则Z为==默认值==

  • ==默认值语句==可指定Z默认值为0或1（默认值语句一般在状态机图左右上角这样子）

image-20230610162850450

选C

状态机图和状态机表

状态机图 状态机表
image-20230610163515351 image-20230610163537445
右表中Output Actions列中的*表示输出还依赖转移条件 image-20230610163640544

image-20230610165225903

请忘记上面的图自己来重新做一遍：

填空1：\(\overline{B}C\)

填空2：\(Z^*\)

填空3：\(A\)

填空4：\(\overline{B} C /Z^*\)

全对，还不错

约束检查

TC 约束

  • 约束 1: 对状态 \(S_i\) , 从\(S_i\) 出发所有TC 对 \((T_{ij}, T_{ik})\) ： \(T_{ij}\times T_{ik} = 0\)

  • 约束 2: 对状态\(S_i\) , 对所有TC, \(T_{ij}\)： \(\sum_j T_{ij} = 1\)

分析状态机图 例 A: 例 B:
image-20230610164854636 \(X \times Y \neq 0\) 且 \(X + Y \neq 1\), 两个约束都违反 \(X \times X’Y = 0\), 但 \(X + X’Y \neq 1\)， 违反约束2

OC 约束

  • 约束 1: 对状态\(S_i\) , 在其上或者其状态转移上==有一致输出变量但不同值==的输出行为，相应的输 出条件对\((O_{ij}, O_{ik})\) 互斥： \(O_{ij}\times O_{ik} = 0\)

  • 约束2：对每个输出变量，在状态 \(S_i\)上或者在 \(S_i\)状态转移上的==输出条件必须覆盖==所有可能的输入变量组合： \(\sum_j O_{ij} = 1\)

分析状态机图 例 C
image-20230610170504292 对 Z = 1 和 Z = 0, \(X\times Y \neq 0\), 因此==违反约束1== ;X + Y + Y’ = 1, 在Y’上输出 默认值Z’ ，因此==约束2满足==

对于输出条件的约束2无论在转移弧上的条件还是直接输出的条件都有关

约束检查

状态机图 转移约束 输出约束
image-20230610171439058 image-20230610171454527 image-20230610171525219
通过状态机表进行约束检测更直观
image-20230610171750082 image-20230610171806338

状态机图设计

例子一：控制滑动门

步骤 具体
① 定义==输入输出==变量，并定义每个变量0和1意义 image-20230610172743575
② 画出电路==状态机图==或者写出状态机表 image-20230610172812713
③ 若使用状态机图，将其转换成==状态机表== image-20230610172828853
④-1 从状态机表，推导出电路==下一状态== image-20230610172949814
④-2 ==和输出方程== image-20230610173228074

例子二：电梯控制

输入 输出 状态
image-20230610174113514 image-20230610174131001 image-20230610174204494
主转移路径 状态机图
image-20230610174256683 image-20230610174348823

  • 约束检查添加其他转移

  • 添加输出

状态机图 状态机表
image-20230610174348823

image-20230610175113957

请先不要看下方答案先独立完成：

image-20230610175851123

完全正确。

下一状态 输出方程
image-20230610174731980 image-20230610174832535