1、华东师范大学计算机系1 倒数行倒数行6：C211=（S2，S3）C211=（S1，S3）本章错误本章错误 P286 倒数行倒数行8：C111=（S0，S1）C111=（S0，S2）华东师范大学计算机系2本章错误本章错误 P294 表表7-19 10列：列：S2/1 S2/0 S1/1 S1/0 S0/0 S0/0华东师范大学计算机系3本章错误本章错误 P295 行行3：F2F1X F2F1 表表7-21，X=1 D1列：列：1/0 1/0 0/0 0/0 1/0 1/0 0/1 1/0华东师范大学计算机系4本章错误本章错误 P297 表表7-23 行行5：D B/0 E/1 D B/0 E/0
2、 P306 行行1、行、行2、倒数行、倒数行3：1000 1.000华东师范大学计算机系5本章错误本章错误 P311 行行15：=(F3F2)=(F3F2)图图7-47 a)改为：改为：000111 10 0 0 1 1 d d000111 10 0 1 1 d d 图图7-47 b)改为：改为：华东师范大学计算机系6本章错误本章错误 P318 右矩形右矩形1：CTLN CTCN 右菱形右菱形3：TCHR TCRH P325 倒数行倒数行7：U6B(LS112)=22ns U6B(LS112)=20ns华东师范大学计算机系7 同步时序电路的设计：同步时序电路的设计：（1）根据需求）根据需求 状
3、态图、状态表状态图、状态表 （2）状态分配）状态分配 状态转移表状态转移表 （3）状态转移表）状态转移表 激励表激励表 触发器特征表触发器特征表 （4）卡诺图化简）卡诺图化简 激励函数表达式激励函数表达式 输出函数表达式输出函数表达式 （5）电路实现）电路实现华东师范大学计算机系8同步时序电路设计的进一步优化：同步时序电路设计的进一步优化：（1）根据需求）根据需求 状态图、状态表状态图、状态表 （2）状态化简最小化状态表状态化简最小化状态表 （3）状态分配状态分配 得状态转移表得状态转移表 （4）状态转移表）状态转移表 激励表激励表 触发器特征表触发器特征表 （5）卡诺图化简）卡诺图化简 激励
4、函数表达式激励函数表达式 输出函数表达式输出函数表达式 （6）电路实现）电路实现华东师范大学计算机系9 7 时序电路设计时序电路设计 状态化简状态化简 状态分配状态分配 复杂时序电路的设计复杂时序电路的设计华东师范大学计算机系10 7 时序电路设计时序电路设计7.1 状态等价状态等价7.2 状态化简状态化简7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简7.4 状态分配方法状态分配方法7.5 算法状态机算法状态机7.6 链接时序机链接时序机华东师范大学计算机系11 7 时序电路设计时序电路设计7.1 状态等价状态等价华东师范大学计算机系12 7.1 状态等价状态等价 设计步骤：设计
5、步骤：根据根据功能要求构成状态图功能要求构成状态图 原始状态图原始状态图 构成最小化状态表构成最小化状态表 状态化简状态化简消除冗余状态，降低成本消除冗余状态，降低成本 状态化简是建立在状态等价基础上的状态化简是建立在状态等价基础上的华东师范大学计算机系13 7.1 状态等价状态等价 1状态等价定理状态等价定理 S1与与S2等价：等价：当且仅当两状态每种可能的输入序当且仅当两状态每种可能的输入序 列其输出相等且次态等价，则称：列其输出相等且次态等价，则称：S1与与S2等价，记作（等价，记作（S1、S2）。）。华东师范大学计算机系14 1状态等价定理状态等价定理 等价条件：等价条件：输出相同输出
6、相同 次态等价（满足下列条件之一）：次态等价（满足下列条件之一）：次态相同次态相同 次态交替：次态交替：S1的次态为的次态为S2 S2的次态为的次态为S1 次态循环：次态循环：S1和和S2的次态为的次态为S3和和S4 S3和和S4的次态为的次态为S1和和S2华东师范大学计算机系15 7.1 状态等价状态等价 2 2等价性质：等价性质：对称性：若对称性：若S S1 1=S=S2 2，则，则S S2 2=S=S1 1 自反性：对任何状态，自反性：对任何状态，S S1 1=S S1 1 传递性：若传递性：若S S1 1=S=S2 2，且，且S S2 2=S=S3 3，则则S S1 1=S=S3 3
7、华东师范大学计算机系16 7.1 状态等价状态等价 3 3等价类等价类 等价类是若干状态的集合，在此集合中，等价类是若干状态的集合，在此集合中，任何两个状态都是相互等价的。任何两个状态都是相互等价的。（S S1 1，S S2 2）（）（S S1 1，S S3 3）（S S1 1，S S2 2，S S3 3）利用等价定理可进行状态化简利用等价定理可进行状态化简华东师范大学计算机系17 7 时序电路设计时序电路设计7.1 状态等价状态等价7.2 状态化简状态化简华东师范大学计算机系18 7.2 状态化简状态化简 方法：方法：等价类表等价类表 隐含表隐含表 一、等价类表化简法：一、等价类表化简法：教
8、材教材 P286P286讨论讨论 华东师范大学计算机系19 7.2 状态化简状态化简二、隐含表化简法二、隐含表化简法 提供一种识别冗余状态的图形提供一种识别冗余状态的图形 化方法化方法 隐含表：图隐含表：图7-17-1 每个方格代表一对隐含的等价每个方格代表一对隐含的等价 可能性可能性 华东师范大学计算机系20二、隐含表化简法二、隐含表化简法 1 1化简步骤：化简步骤：作隐含表，寻找等价对作隐含表，寻找等价对 根据等价性质，构成最大等价类根据等价性质，构成最大等价类 将最大等价类中的状态合并，得到将最大等价类中的状态合并，得到 最小化状态表最小化状态表 华东师范大学计算机系21二、隐含表化简法
9、二、隐含表化简法2 2化简举例化简举例 例例7-1）化简化简P288 图图7-4状态图状态图 作隐含表作隐含表 填隐含表（图填隐含表（图7-5),对所有状态进行比较：对所有状态进行比较：状态等价，打状态等价，打“”输出不同，打输出不同，打“”输出相同，但次态不同，将次态填入，输出相同，但次态不同，将次态填入，以便进一步判别以便进一步判别 列出状态表（表列出状态表（表7-7）华东师范大学计算机系22例例7-3）化简原始状态表）化简原始状态表 对所有状态进行比较，找出等价状态对对所有状态进行比较，找出等价状态对BCDE A B C D BCAEAEBC CDBE,AC BCDC,ABDC不等价不等
10、价AD不不等价等价AE、BC次态循环次态循环 AE、BC等价等价CD不等价不等价DE不等价不等价 归纳等价状态对为：归纳等价状态对为：（A,E）（）（B,C）华东师范大学计算机系23例例7-1）化简图化简图7-4状态图状态图 状态合并，作状态合并，作:最小化状态表（表最小化状态表（表7-9）状态图（图状态图（图7-7）归纳最大等价类：归纳最大等价类：（A，E），（），（B，C），（），（D）S0 S1 S2华东师范大学计算机系242 2化简举例化简举例例例7-2）化简化简P290 表表7-10状态表状态表 进一步比较隐含表中尚未确定项进一步比较隐含表中尚未确定项 逐个比较，除去不等价状态对逐个
11、比较，除去不等价状态对 归纳等价状态对为：归纳等价状态对为：（0）（）（1，2）（）（3，6）（）（4，7）（）（5，8）A B C D E 逐行比较原始状态表逐行比较原始状态表填隐含表（图填隐含表（图7-8）最小化状态表最小化状态表（表（表7-12）华东师范大学计算机系252 2化简举例化简举例例例1）化简如下原始状态表：）化简如下原始状态表：Yt Yt+1/Z X=0X=1ABCDEFG C/0F/0D/0D/1C/0D/0C/0 B/1A/1G/0E/0E/1G/0D/0 华东师范大学计算机系26例例1）化简原始状态表）化简原始状态表 Yt Yt+1/Z X=0X=1ABCDEFG C/
12、0F/0D/0D/1C/0D/0C/1 B/1A/1G/0E/0E/1G/0D/0 作隐含表，找出等价作隐含表，找出等价 状态对状态对BCDEFG A B C D E FCF BEAECFCDEDCF等价等价AB等价等价AE、BE次态循环次态循环 CD CD不等价不等价归纳等价状态对为：归纳等价状态对为：(A,B)(A,E)(B,E)(C,F)华东师范大学计算机系27例例1）化简原始状态表）化简原始状态表 归纳等价状态对为：归纳等价状态对为：(A,B)(A,E)(B,E)(C,F)构成最大等价类构成最大等价类 根据传递性：根据传递性：(A,B)(A,E)(B,E)(A,B,E)最大等价类为：最
13、大等价类为：(A,B,E)(C,F)(D)(G)a b c d华东师范大学计算机系28例例1）化简原始状态表）化简原始状态表 构成最小化状态表：构成最小化状态表：(A,B,E)(C,F)(D)(G)a b c dYt Yt+1/Z X=0X=1ABCDEFG C/0F/0D/0D/1C/0D/0C/1 B/1A/1G/0E/0E/1G/0D/0 Yt Yt+1/Z X=0X=1abcdb/0c/0c/1b/1a/1d/0a/0c/0华东师范大学计算机系29 7 时序电路设计时序电路设计7.1 状态等价状态等价7.2 状态化简状态化简7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简华
14、东师范大学计算机系30 7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简 特点：特点：状态表中存在不完全确定的次态或输出状态表中存在不完全确定的次态或输出 不完全确定不完全确定状态表的化简是建立在相容状态表的化简是建立在相容状态基础上的状态基础上的 华东师范大学计算机系31 7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简一、状态相容一、状态相容 1.1.相容状态：相容状态：对于所有的有效输入序列，分别从状态对于所有的有效输入序列，分别从状态 S SA A和和S SB B出发，所得到的输出响应序列是出发，所得到的输出响应序列是 完全相同的（不确定状态可任意指定），完全相
15、同的（不确定状态可任意指定），那么状态那么状态S SA A和和S SB B是相容的，即是相容的，即S SA A和和S SB B为相为相 容对，记作：容对，记作：SSA A，S SB B。华东师范大学计算机系32一、状态相容一、状态相容 相容条件：相容条件：（不确定状态可任意指定）（不确定状态可任意指定）输出相同输出相同 次态满足下列条件之一：次态满足下列条件之一：次态相同次态相同 次态交替次态交替 次态循环次态循环 华东师范大学计算机系33一、状态相容一、状态相容2.相容类相容类 状态相容与状态等价性质一样，具有相容状态相容与状态等价性质一样，具有相容类和最大相容类的性质类和最大相容类的性质
16、不同点：不同点：不具备传递性，即在相容类中所有不具备传递性，即在相容类中所有 状态之间都分别是两两相容的；状态之间都分别是两两相容的；不具备传递性不具备传递性 若干个最大相容类可能包含公共若干个最大相容类可能包含公共 状态状态华东师范大学计算机系34一、状态相容一、状态相容3.相容性质相容性质 相容类集合必须满足覆盖、闭合和最小三个相容类集合必须满足覆盖、闭合和最小三个条件条件 覆盖覆盖指相容类集合中包含了原状态指相容类集合中包含了原状态 表的全部状态表的全部状态 闭合闭合指在一个相容类集合中，任一指在一个相容类集合中，任一 相容类在各种输入取值下的次相容类在各种输入取值下的次 态组合，都必须
17、属于该集合中态组合，都必须属于该集合中 某一相容类某一相容类 最小最小指满足覆盖和闭合的相容类数指满足覆盖和闭合的相容类数 目达到最少目达到最少华东师范大学计算机系35一、状态相容一、状态相容4.化简步骤：化简步骤：作隐含表作隐含表 寻找相容状态对寻找相容状态对 利用状态合并图利用状态合并图 寻找最大相容类寻找最大相容类 作最小化状态表作最小化状态表 状态合并图状态合并图 以点表示状态，均匀分布在圆周上以点表示状态，均匀分布在圆周上 将各相容对用线段连接将各相容对用线段连接 找出所有点之间都有连线的多边形找出所有点之间都有连线的多边形 构成一个最大相容类构成一个最大相容类华东师范大学计算机系3
18、6 7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简二、化简举例二、化简举例 例例2 2）化简状态表）化简状态表 现现态态次态次态/输出输出00011011ABCDEC，0-，-D，0C，0B，0-，-E，0B，1A，1-，-A，0B，0-，-E，0A，0-，-D，1-，-，-E，1 作隐含表作隐含表BCDE A B C DCDAECBABDEABDBCBAE 归纳相容状态对：归纳相容状态对：AA，B AB A，C DC D，CC华东师范大学计算机系37例例2 2）化简状态表）化简状态表 作状态合并图作状态合并图 A，B A，C D，C ABCDE 最大相容类：最大相容类：AA，B
19、 DB D，C EC E S0 S1 S2华东师范大学计算机系38例例2 2）现现态态次态次态/输出输出00011011ABCDEC，0-，-D，0C，0B，0-，-E，0B，1A，1-，-A，0B，0-，-E，0A，0-，-D，1-，-，-E，1 作最小化状态表作最小化状态表 A，B D，C E S0 S1 S2现现态态次态次态/输出输出00011011S0S1S2S1，0S1，0S0，0S2，0S0，1-，-S0，0S2，0S0，0S1，1-，-S2，1华东师范大学计算机系39二、化简举例二、化简举例例例7-37-3）化简状态表）化简状态表 现现态态次态次态/输出输出00011011ABC
20、DEFG-，-A，0E，0-，-C，0D，1E，1D，0C，0A，0-，-，-B，0-，-F，0-，-E，0C，0-，-，-A，0C，1D，1-，-G，1F，1E，1C，1 作隐含表作隐含表BCDEFG A B C D E FCDADEFCFCGCFBDCEAFAEACDGACDF 相容状态对：相容状态对：A,BC,DC,ED,EG,FA,BC,DC,ED,EG,FCECEGFGEACCGDECE华东师范大学计算机系40例例7-37-3）化简状态表）化简状态表 作状态合并图作状态合并图 A,B C,D C,E D,E G,F 最大相容类：最大相容类：A,BC,E,DF,GA,BC,E,DF,G
21、 S0 S1 S2ABCDEFG 作最小化状态表作最小化状态表 （表（表7-197-19）华东师范大学计算机系41二、化简举例二、化简举例例例3 3）化简状态表）化简状态表 现现态态 次态次态 输出输出X=0X=1ZABCDEFBBA-F-DDEE-C0-111-作隐含表作隐含表BCDEF A B C D E CDABDEDE 相容状态对：相容状态对：A,BA,FB,CB,DB,EA,BA,FB,CB,DB,E B,FC,DC,EC,FD,ED,FE,F B,FC,DC,EC,FD,ED,FE,FCEAFCEBFCD华东师范大学计算机系42例例7-37-3）化简状态表）化简状态表 作状态合并图
22、作状态合并图 A,B A,F B,C B,D B,E B,F C,D C,E C,F D,E D,F E,F 最大相容类：最大相容类：B,C,D,E,FA,B,FB,C,D,E,FA,B,F a bABCDEF华东师范大学计算机系43例例7-37-3）化简状态表）化简状态表现现态态 次态次态 输出输出X=0X=1ZABCDEFBBA-F-DDEE-C0-111-作最小化状态表作最小化状态表 A,B,F B,C,D,E,F a b现现态态 次态次态 输出输出X=0X=1Zab-abb01华东师范大学计算机系44 7 时序电路设计时序电路设计7.1 状态等价状态等价7.2 状态化简状态化简7.3
23、不完全定义状态表的状态化简不完全定义状态表的状态化简7.4 状态分配方法状态分配方法华东师范大学计算机系45 7.4 状态分配方法状态分配方法一、状态分配一、状态分配 为状态分配唯一的二进制编码为状态分配唯一的二进制编码 设：二进制码位数为设：二进制码位数为M M 状态数为状态数为N N 则：则：2 2M-1M-1N2N2M M二、状态分配的合理性二、状态分配的合理性 状态分配不会影响电路的逻辑功能，状态分配不会影响电路的逻辑功能，但影响电路实现的复杂度但影响电路实现的复杂度。寻找较为合理的分配方案寻找较为合理的分配方案华东师范大学计算机系46 7.4 状态分配方法状态分配方法三、状态分配算法
24、三、状态分配算法 1.1.状态分配规则状态分配规则 如下情况，应分配相邻的二进制代码如下情况，应分配相邻的二进制代码 规则规则1 1：同一输入值下，同一输入值下，次态相同次态相同的现态的现态 规则规则2 2：同一状态同一状态在相邻输入下的不同次态在相邻输入下的不同次态 规则规则3 3：在所有输入取值下均有相同输出的在所有输入取值下均有相同输出的 现态现态华东师范大学计算机系47三、状态分配算法三、状态分配算法2.2.状态分配实例状态分配实例 例例4 4）为如下状态表建）为如下状态表建 立状态转移表立状态转移表Y Y+/ZX=0X=1ABCDC/0C/0B/0A/1D/0A/0D/0B/1 确定
25、状态变量位数确定状态变量位数 2 22 2=4=4 取取2 2位状态变量位状态变量 应分配相邻代码的状态：应分配相邻代码的状态：规则规则1 1：A,B A,CA,B A,C 规则规则2 2：C,D A,CC,D A,C、B,D A,BB,D A,B 规则规则3 3：A,B,CA,B,C华东师范大学计算机系48 A：00，B：10，C：01，D：11例例4 4）状态分配状态分配 规则规则1 1：A,BA,B、A,CA,C 规则规则2 2：C,DC,D、A,CA,C、B,DB,D、A,BA,B 规则规则3 3：A,B,CA,B,CY Y+/ZX=0X=1ABCDC/0C/0B/0A/1D/0A/0
26、D/0B/11010Y2Y1ABCD 状态转移表状态转移表Y2Y1 Y2+Y1+/ZX=0X=10 00 11 11 0O1/010/000/101/011/011/010/100/0华东师范大学计算机系492.2.状态分配实例状态分配实例例例7-47-4）考察表）考察表7-247-24所示状态表所示状态表 应分配相邻代码的状态：应分配相邻代码的状态：规则规则1 1：A,CA,C、B,EB,E、A,EA,E、D,FD,F 规则规则2 2：A,CA,C、C,DC,D、A,FA,F、B,EB,E、D,ED,E A,CA,C B,EB,E出现出现2 2次，优先考虑次，优先考虑 多种分配方案：多种分配
27、方案：方案一：图方案一：图7-18(a)7-18(a)表表7-25 方案二：方案二：(b)(b)方案三：方案三：(c)(c)华东师范大学计算机系50例例7-47-4）考察表）考察表7-247-24所示状态表所示状态表 采用采用D D触发器实现各方案触发器实现各方案 P299P299 例，方案一：例，方案一：F3F2F1 D3 D2 D1X=0X=10 0 00 1 11 0 01 1 00 0 10 1 00 0 01 0 00 0 00 1 11 0 01 1 01 0 01 1 00 1 00 0 11 0 00 0 1 激励表：激励表：卡诺图化简：卡诺图化简：01 1 00 10 11
28、01 00F3F2F1X d d 1 10 d d 1 1 1 1 11 D3=F3F2X+F3F2X+F1华东师范大学计算机系51例例7-47-4）考察表）考察表7-247-24所示状态表所示状态表F3F2F1 D3 D2 D1X=0X=10 0 00 1 11 0 01 1 00 0 10 1 00 0 01 0 00 0 00 1 11 0 01 1 01 0 01 1 00 1 00 0 11 0 00 0 1 1 01 1 1 00 10 11 01 00F3F2F1X d d 10 d d 1 11 1 1 01 1 00 10 11 01 00F3F2F1X d d 10 d d
29、 11 卡诺图化简：卡诺图化简：D2=F2F1X+F2F1X+F3F2XD1=F3F2+F2F1X华东师范大学计算机系52例例7-47-4）考察表）考察表7-247-24所示状态表所示状态表 状态分配方案不同，实现成本略有不同状态分配方案不同，实现成本略有不同 方案一：方案一：2828门门 方案二：方案二：2727门门 方案三：方案三：2727门门 不考虑状态分配原则：不考虑状态分配原则：3535门门 状态分配规则不一定能产生最佳方案，状态分配规则不一定能产生最佳方案，但能产生状态分配的较好方案但能产生状态分配的较好方案华东师范大学计算机系53 同步时序电路的设计：同步时序电路的设计：（1）根
30、据需求）根据需求 状态图、状态表状态图、状态表 （2）状态分配）状态分配 状态转移表状态转移表 （3）状态转移表）状态转移表 激励表激励表 触发器特征表触发器特征表 （4）卡诺图化简）卡诺图化简 激励函数表达式激励函数表达式 输出函数表达式输出函数表达式 （5）电路实现）电路实现华东师范大学计算机系54同步时序电路设计的进一步优化：同步时序电路设计的进一步优化：（1）根据需求）根据需求 状态图、状态表状态图、状态表 （2）状态化简最小化状态表状态化简最小化状态表 （3）状态分配状态分配 得状态转移表得状态转移表 （4）状态转移表）状态转移表 激励表激励表 触发器特征表触发器特征表 （5）卡诺图
31、化简）卡诺图化简 激励函数表达式激励函数表达式 输出函数表达式输出函数表达式 （6）电路实现）电路实现华东师范大学计算机系55j 状态图状态图 同步时序电路设计同步时序电路设计例例5 5）试设计一个同步时序电路，接收串行二）试设计一个同步时序电路，接收串行二 进制代码，输入代码每三位为一组，当进制代码，输入代码每三位为一组，当 输入的三位二进制代码为输入的三位二进制代码为011011时，电路时，电路 输出为输出为“1”1”。ABCDEFG0/01/00/00/01/01/00/01/00/01/10/01/00/01/0初态初态0100011011X/Z华东师范大学计算机系56例例5 5）状态
32、表状态表ABCDEFG0/01/00/00/01/01/00/01/00/01/10/01/00/01/0初态初态0100011011YY+/ZX=0X=1ABCDEFGB,0 C,0D,0 E,0F,0 G,0A,0 A,0A,0 A,1A,0 A,0A,0 A,0华东师范大学计算机系57例例5 5）最小化状态表最小化状态表YY+/ZX=0X=1ABCDEFGB,0D,0F,0A,0A,0A,0A,0C,0E,0G,0A,0A,1A,0A,0BCDEFGA B C D E F BDCEBFCGABACABACABACDFEGADAEADAEADAEAFAGAFAGAFAGXXXXXX 等价类
33、等价类:(D,F)(D,G)(G,F)(D,F,G)华东师范大学计算机系58例例5 5）最大等价类最大等价类:(A)(B)(C)(D,F,G)(E)a b c d eYY+/ZX=0X=1ABCDEFGB,0D,0F,0A,0A,0A,0A,0C,0E,0G,0A,0A,1A,0A,0YY+/ZX=0X=1abcde最小化状态表：最小化状态表：b,0 c,0d,0 e,0d,0 d,0a,0 a,0a,0 a,1华东师范大学计算机系59例例5 5）m 状态分配状态分配 22523 用三位二进制代码表示一个状态用三位二进制代码表示一个状态 1 010110100F3F2F1YY+/ZX=0X=1
34、abcdeb,0d,0d,0a,0a,0c,0e,0d,0a,0a,1根据：根据：规则规则1：b,c d,e应分配相邻编码应分配相邻编码 规则规则2：b,c d,e应分配相邻编码应分配相邻编码 a:000 b:001c:011 d:010e:110abcde华东师范大学计算机系60例例5 5）n 状态转移表：状态转移表：a:000 b:001 c:011 d:010 e:110F3F2F1F3+F2+F1+/ZX=0X=1000001011010110001,0010,0010,0000,0000,0011,0110,0010,0000,0000,1YY+/ZX=0X=1abcdeb,0d,0
35、d,0a,0a,0c,0e,0d,0a,0a,1华东师范大学计算机系61例例5 5）o 激励函数：激励函数：激励表：激励表：（D触发器实现）触发器实现）F3F2F1D3 D2 D1/ZX=0X=1000001011010110001,0010,0010,0000,0000,0011,0110,0010,0000,0000,1 d 01 d 00 10 11 01 00F3F2 d d 1 10 d d 1 1 1 1 11 F1X d 01 d 00 10 11 01 00F3F2 d d 10 d d 1 11 F1XD3=F2F1XD2=F2X+F1华东师范大学计算机系62例例5 5）F3
36、F2F1D3 D2 D1/ZX=0X=1000001011010110001,0010,0010,0000,0000,0011,0110,0010,0000,0000,1 d 1 01 d 00 10 11 01 00F3F2 d d 10 d d 11 F1X d 01 d 1 00 10 11 01 00F3F2 d d 10 d d 1 11 F1XD1=F2F1Z=F3X华东师范大学计算机系63例例5 5）p 逻辑图：逻辑图：D3=F2F1X D2=F2X+F1 D1=F2F1 Z=F3X 3 Q D CP Q 2 Q D CP Q 1 Q D CP ZF3F2F1CLKX华东师范大学
37、计算机系64例例5 5）p 分析讨论分析讨论 根据激励函数画出包含所有根据激励函数画出包含所有 状态的状态图状态的状态图0000010101000/00111/01101/00/01/10/00/01/10/01/11/10/01/01011110/0 修改输出函数：修改输出函数：Z=F3F2F1XF3F2F1D3 D2 D1/ZX=0X=1000001011010110001,0010,0010,0000,0000,0011,0110,0010,0000,0000,1D3=F2F1X D2=F2X+F1 D1=F2F1 Z=F3X0/01/0华东师范大学计算机系65例例5 5）修改输出函数：
38、修改输出函数：Z=F3F2F1X 3 Q D CP Q 2 Q D CP Q 1 Q D CP ZF3F2F1CLKX华东师范大学计算机系66例例5 5）0000010111100101000/01/01/00/01/00/00/01/10/01/01/00/01/01011110/0状态图：状态图：0/01/0华东师范大学计算机系67 7 时序电路设计时序电路设计7.1 状态等价状态等价7.2 状态化简状态化简7.3 不完全定义状态表的状态化简不完全定义状态表的状态化简7.4 状态分配方法状态分配方法7.5 算法状态机算法状态机华东师范大学计算机系68 7.5 算法状态机算法状态机 算法状态
39、机（算法状态机（ASMASM）是一种描述时序系统控制过程的算法流图是一种描述时序系统控制过程的算法流图,其结构形式类似于计算机中的程序流程图其结构形式类似于计算机中的程序流程图 特点：特点：可准确地描述控制器的功能和状态变化条可准确地描述控制器的功能和状态变化条件件 jj 描述控制器的控制状态及其转换关系描述控制器的控制状态及其转换关系 精确地表示状态转换的时间关系精确地表示状态转换的时间关系 描述符号：描述符号：ASMASM流程图流程图华东师范大学计算机系697.5 算法状态机算法状态机一、一、ASMASM符号符号 1.1.主要符号主要符号 jj 状态符号状态符号表示系统状态表示系统状态 图
40、图7 72424 OUT1OUT2A00状态状态状态进入状态进入状态退出状态退出无条件输出无条件输出MooreMoore型型华东师范大学计算机系70一、一、ASMASM符号符号 1.1.主要符号主要符号 条件选择符号条件选择符号 图图7 72525 X判定标准判定标准入口入口01退出路径退出路径(A+B)(A+B)华东师范大学计算机系71一、一、ASMASM符号符号 1.1.主要符号主要符号 条件输出符号条件输出符号 图图7 726 26 OUT3输出变量输出变量mealymealy型型AB0/OUT3华东师范大学计算机系72一、一、ASMASM符号符号 2.ASM 2.ASM块块 由一个状态
41、符号（条件选择符号）由一个状态符号（条件选择符号）（条件输出符号）组成（条件输出符号）组成 图图7 72727、图、图7 72828AO1BCXY/O2(XY)O1AXYO2CB10000110华东师范大学计算机系73一、一、ASMASM符号符号3.3.构造构造ASMASM图图 注意避免不确定性注意避免不确定性 图图7-30 7-30 转换条件未确定转换条件未确定 例：构造如下状态图的例：构造如下状态图的ASM图图ABCXY/O1XYXY/O1XYABCXYO10110正确吗？正确吗？华东师范大学计算机系74例例7-67-6ABCXY/O1XYXY/O1XYAXO10BC1Y10华东师范大学计
42、算机系75一、一、ASMASM符号符号 3.3.构造构造ASMASM图图 例：图例：图7-337-33采用并行路径描述采用并行路径描述 不确定描述不确定描述 改串行路径描述：改串行路径描述：图图7-34 7-34 4.简单例子：简单例子：jj 模模4计数器的计数器的ASM图图 图图7-377-37 模模4可逆计数器可逆计数器ASM图图 图图7-387-38 选择块可由选择块可由ASMASM块共享：块共享：图图7-357-35 ASM ASM图的循环描述：图的循环描述：图图7-367-36华东师范大学计算机系767.5 算法状态机算法状态机二、二、ASMASM设计实例设计实例 例例7-77-7）
43、测量超声波发生器发射端到目的地（障碍物）测量超声波发生器发射端到目的地（障碍物）的距离的距离 1.方法：方法：超声波测量超声波测量 计算出从发送（计算出从发送（XMIT）到收到有效回）到收到有效回 波信号（波信号（ECHO）的时间）的时间 图图7-40XMITXMITECHOECHOCENCENt t华东师范大学计算机系77例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离采用类似采用类似P260P260例例6-26-2）“计时器计时器”的方法，获得的方法，获得计数值，送计算机处理。计数值，送计算机处理。计数时钟取计数时钟取1MHz1MHz（1us)1
44、us)计数最大值设为计数最大值设为2 21616 16 16位计数值送计算机处理位计数值送计算机处理 控制时序：控制时序：图图7-417-41ECHOECHOCENCENABSTBAINTRAINTRRDRD计数值送计算机计数值送计算机接口电路接口电路向向CPU发中发中断请求断请求在中断处理程在中断处理程序中序中,CPU读取读取接口的数据接口的数据华东师范大学计算机系78例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离2.2.设计框图设计框图 XMITECHO 时序时序 电路电路定时器定时器ERSTCENCRSTABSTB晶振晶振1016位位计计数数
45、器器16位位并并行行口口10MHz1MHz计算机计算机定时信号（超时复位）。当出现故障，定时信号（超时复位）。当出现故障，无无ECHO信号返回时，利用该信号复信号返回时，利用该信号复位系统。位系统。图图7-43华东师范大学计算机系79例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离3.3.时序电路模块设计时序电路模块设计 （1 1）输入信号：）输入信号：XMITXMIT超声波发送脉冲超声波发送脉冲ECHOECHO回波信号回波信号ERSTERST定时信号定时信号 输出信号：输出信号：CEN CEN 计数使能计数使能 CRST CRST 复位复位 ABS
46、TB ABSTB 数据锁存数据锁存华东师范大学计算机系80例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离（2）ASM图：图：图图7-42 ABC初始态初始态清零态清零态就绪态就绪态XMITCEND10发送超声波发送超声波计数态计数态ERST1超时，系超时，系统复位统复位0ECHO0回波信号未到，回波信号未到，继续计数继续计数1回波信号到回波信号到CRST华东师范大学计算机系81例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离（2）ASM图：图：图图7-42 CENDERST0ECHO01回波信号到回波信号
47、到XMIT1发送信号仍有效发送信号仍有效,继续计数继续计数,避免寄生避免寄生ECHO信号信号0E停止计数停止计数ECHO0ABSTB置数并返回置数并返回等待回波信等待回波信号结束号结束F华东师范大学计算机系82例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离（3）状态表：）状态表：表表7-28（4）状态化简）状态化简 隐含表化简法：隐含表化简法：图图7-44 无等价状态，表无等价状态，表7-28即为最小化状态表即为最小化状态表华东师范大学计算机系83例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离（5 5）
48、状态分配）状态分配 jj 规则规则1 1：B,CB,C 4 D,F4 D,F 4 D,E 4 D,E C,D C,D 2 2 规则规则2 2：C,D A,D E E,FC,D A,D E E,F 规则规则3 3：A,C,E A,C,E 利用卡诺图分配利用卡诺图分配 图图7-457-45（6）状态转移表）状态转移表 表表7-29（7）激励表（用）激励表（用J-K触发器实现）触发器实现）略略华东师范大学计算机系84例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离（8）卡诺图化简）卡诺图化简 激励函数表达式激励函数表达式 输出函数表达式输出函数表达式 分析
49、表分析表7-29：jj J1K1：现态现态011：XMIT F1 F1+0 1 1 1 1 0J1 K1 MEVd 0d 1 XMIT 图图7-46(b)K1卡诺图：卡诺图：011小格填入小格填入XMIT华东师范大学计算机系85例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离 J2K2：现态现态010：ERST F2 F2+J2 K2 MEV 0 1 1 d 0 1 1 0 d 1 ERST 图图7-46(d)K2卡诺图：卡诺图：010小格填入小格填入ERST 现态现态110：ECHO F2 F2+J2 K2 MEV 0 1 0 d 1 1 1 1
50、d 0 ECHO 图图7-46(d)K2卡诺图：卡诺图：110小格填入小格填入ECHO华东师范大学计算机系86例例7-77-7）测量超声波发生器发射端到目的地的距离）测量超声波发生器发射端到目的地的距离 J3K3：现态现态010：F3 F3+J3 K3 XMIT ECHO ERST 0 1 1 d (XMIT ECHO ERST)0 0 0 d 图图7-46(e)J3卡诺图：卡诺图：010小格填入小格填入XMIT ECHO ERST mm 化简，得激励函数和输出函数表达式化简，得激励函数和输出函数表达式 P311（9）电路图）电路图 图图7-48（10）时序图）时序图 图图7-49华东师范大学
