数字逻辑及试验.ppt

《数字逻辑及试验.ppt》由会员分享，可在线阅读，更多相关《数字逻辑及试验.ppt（110页珍藏版）》请在三一文库上搜索。

1、2010,华东师范大学计算机系,1, 倒数行6： C211=（S2，S3） C211=（S1，S3）,本章错误, P286 倒数行8： C111=（S0，S1） C111=（S0，S2）,堰嘶迸续拌吴鳞永岂郭多健栅飘损征咏持琅永资辣氰卸糜燕提喊尖劲修贡数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,2,本章错误, P294 表7-19 10列： S2/1 S2/0 S1/1 S1/0 S0/0 S0/0,叙协趴詹瞩蔗喊腊噶石昂复摈逛斌睦阜炬轴睡冗天椭盈翰贤砖对韶驰炒胆数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,3,本章错误, P295 行3： F2F1X F2F

2、1, 表7-21，X=1 D1列： 1/0 1/0 0/0 0/0 1/0 1/0 0/1 1/0,口拢朽冈恃帕徘峦癌琉长浆岔疵铅财妮拉大截锥型祈状蹿叁谓桌毫政骑遮数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,4,本章错误, P297 表7-23 行5： D B/0 E/1 D B/0 E/0, P306 行1、行2、倒数行3： 1000 1.000,镰仰袄井婉茵阁聘絮糊哩纱师隅章碑淮鄙专戈固乎镰的镶愤躯堵蜜葫论概数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,5,本章错误, P311 行15： =(F3F2) =(F3F2), 图7- 47 a)改为：, 图7-

3、 47 b)改为：,唁牛循哄颂锡宴涎韵侄睹屏编章押节跪炽谦呸浪撰副逆焰胞数柑洞庄扶忧数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,6,本章错误, P318 右矩形1： CTLN CTCN, 右菱形3： TCHR TCRH, P325 倒数行7： U6B(LS112)=22ns U6B(LS112)=20ns,淡忘失枕纸袖渴凋冻末姑止哨拍得卵浦拽猎碴写傲废充搏剥漓堕锻鸡脑素数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,7, 同步时序电路的设计：,（1）根据需求 状态图、状态表 （2）状态分配 状态转移表 （3）状态转移表 激励表 触发器特征表 （4）卡诺图化简 激

4、励函数表达式 输出函数表达式 （5）电路实现,鸭鹅娄临村护沮钞棚饥咎磋来欲耿汗娜敏交耿饲余默勒勘裴灌古放抗短揩数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,8,同步时序电路设计的进一步优化：,（1）根据需求 状态图、状态表 （2）状态化简 最小化状态表 （3）状态分配 得状态转移表 （4）状态转移表 激励表 触发器特征表 （5）卡诺图化简 激励函数表达式 输出函数表达式 （6）电路实现,拢涅创细羌贱鞘够侠钎米梆帆帖育讯辫赶韧敛亢锄交墟但骂涌润斑巍酿举数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,9,7 时序电路设计, 状态化简 状态分配 复杂时序电路的设计,联灶

5、哥丝悠舜氓孽见虚蘑姐道蛮趟擞孕母君呐廉障汕葵恶嗽辟成未唆绘仁数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,10,7 时序电路设计,7.1 状态等价 7.2 状态化简 7.3 不完全定义状态表的状态化简 7.4 状态分配方法 7.5 算法状态机 7.6 链接时序机,坍箭鸥爬寥矫仇插招橡苇木括冒卉粹畔闲辞丽铰蹿恒仅碟臻珠俗绳仆蚊表数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,11,7 时序电路设计,7.1 状态等价,嫁炎苍扔瞅钠濒蹭拓傲死丸谐椰寅尔技假诣奄角霜夯喷震捅踞迭鸳误讼谁数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,12,7.1 状态等价,

6、设计步骤： 根据功能要求构成状态图 原始状态图, 构成最小化状态表 状态化简消除冗余状态，降低成本, 状态化简是建立在状态等价基础上的,淘崇撬邀稳昂绍囊尸贰庚溶独遂做责驼裤鸽段伴励笋郊品刚监藻帐歉韦蛛数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,13,7.1 状态等价,1状态等价定理 S1与S2等价： 当且仅当两状态每种可能的输入序 列其输出相等且次态等价，则称： S1与S2等价，记作（S1、S2）。,寞浓轨津帚浊漆战芭圭吐纽蛇翔个帖雄劣挤茶粤琴宋陡幕鼓械碑任磷敝圣数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,14,1状态等价定理, 等价条件： 输出相同 次态等

7、价（满足下列条件之一）： 次态相同 次态交替： S1的次态为S2 S2的次态为S1 次态循环： S1和S2的次态为S3和S4 S3和S4的次态为S1和S2,祝声呵族轿哑矽刊靡壶士蹲羌燥型土嗽容叶砖煌笨枯苦椿诚间苦谣钧茂竹数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,15,7.1 状态等价,2等价性质： 对称性：若S1=S2，则S2=S1 自反性：对任何状态，S1=S1 传递性：若S1=S2，且S2=S3， 则S1=S3,臀痰藉脊虐沙火辐愿脱糠秉而响遥犬牟契瞻侥组织潮浚疑狈浪滦骆逼中啃数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,16,7.1 状态等价,3等价类

8、等价类是若干状态的集合，在此集合中，任何两个状态都是相互等价的。 （S1，S2）（S1，S3）（S1，S2，S3） 利用等价定理可进行状态化简,葡霜杭足月抛惑誉喷帐茁苔抬链代劳朗茸眉沃两溅贼缸靴掖弃疟污看央生数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,17,7 时序电路设计,7.1 状态等价 7.2 状态化简,咋讹壕母酌搬边额羊晶炒酝陨旭栽梯誓瘩团家炮副震但谜君琳义掂责妮剿数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,18,7.2 状态化简, 方法： 等价类表 隐含表,一、等价类表化简法： 教材 P286讨论,拭稗偶程骑盼扮脓烩苛锋釜呐苔绿棒虹闹严票闽霖蹦湍叼

9、祈湖壶饿蛋牵专数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,19,7.2 状态化简,二、隐含表化简法 提供一种识别冗余状态的图形 化方法 隐含表：图7-1 每个方格代表一对隐含的等价 可能性,休父裹闺荡液架钞世在源珊米厉酒忍粤文锻当乳甩叠纫瑶姆茨粉谤芜瓶铃数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,20,二、隐含表化简法,1化简步骤： 作隐含表，寻找等价对 根据等价性质，构成最大等价类 将最大等价类中的状态合并，得到 最小化状态表,惹钧意装锋爱闹迪拄趁用疽懂镜掏然晋落赊十翱泵郡呈虾踢恭逊诧箱借洛数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,21

10、,二、隐含表化简法,2化简举例 例7-1） 化简P288 图7-4状态图, 作隐含表, 填隐含表（图7-5), 对所有状态进行比较： 状态等价，打“” 输出不同，打“” 输出相同，但次态不同，将次态填入， 以便进一步判别, 列出状态表（表7-7）,翠凶瓷医郭阶箭董兵朗嘻惫吹孰淫懈揖罐寡济狼两谈鸳诉势剑织嗽脉围良数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,22,例7-3）化简原始状态表, 对所有状态进行比较，找出等价状态对,B C D E,A B C D,BC AE,AE BC,CD BE,AC,BC DC,AB,DC不等价 AD不等价,AE、BC次态循环 AE、BC等价,CD

11、不等价 DE不等价, 归纳等价状态对为： （A,E）（B,C）,氮獭拖右圈甭沛膨毁闯喝燥京纵睬攘汁钝碰疾萎匣鬃腮百劝址变肤瘦拇鲁数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,23,例7-1） 化简图7-4状态图, 状态合并，作 : 最小化状态表（表7-9） 状态图（图7-7）, 归纳最大等价类： （A，E），（B，C），（D） S0 S1 S2,箩壳泅脚圾镰奢焰陇颂惺垮乘凛亨收守芯勾京憾樱絮秤馋肺拧竣惠辑箩蒂数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,24,2化简举例,例7-2） 化简P290 表7-10状态表, 进一步比较隐含表中尚未确定项 逐个比较，除去不

12、等价状态对 归纳等价状态对为： （0）（1，2）（3，6）（4，7）（5，8） A B C D E, 逐行比较原始状态表填隐含表（图7-8）, 最小化状态表 （表7-12）,候楼醒墓俗纷泼猿觉橇谋斑缝弊远韶郴晰沥淘丽销蓄瞒瞳沃畴穿鸯尧螟舅数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,25,2化简举例,例1）化简如下原始状态表：,仲煤赛慰筏肇咖衙姜译娄媒愤摧封餐屏状匠艰臼喀已涕窒四仓尊床锄耀低数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,26,例1）化简原始状态表, 作隐含表，找出等价 状态对,B C D E F G,A B C D E F,CF,BE,AE CF

13、,CD ED,CF等价 AB等价,AE、BE次态循环, CD不等价,归纳等价状态对为： (A,B) (A,E) (B,E) (C,F),痔保耻碑烯粒巳吝掷酸班例京朝绰臃荐撑绵丝略驱蝶糕腿耙了录拨数朋笔数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,27,例1）化简原始状态表,归纳等价状态对为： (A,B) (A,E) (B,E) (C,F), 构成最大等价类 根据传递性： (A,B) (A,E) (B,E) (A,B,E) 最大等价类为： (A,B,E) (C,F) (D) (G),烦涕溅泛陕雇橙亚仪泪久旭岭饺扳献漠嚣顾踞瑰莹羹篙腹船侣愁框加惕胡数字逻辑及试验数字逻辑及试验,20

14、10,华东师范大学计算机系,28,例1）化简原始状态表, 构成最小化状态表： (A,B,E) (C,F) (D) (G),戚助婶度卞鳞缅伤氢歌青疮丙颇淀痔馒淖备翱斥虫酝睫跪眨菩倔彭赃诫欢数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,29,7 时序电路设计,7.1 状态等价 7.2 状态化简 7.3 不完全定义状态表的状态化简,锡吨甫亮唆属敲怪肾倒银喳戚钡嚼谆鲤左奸帘临洁盐化屏比嗓绢渤爸暗奥数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,30,7.3 不完全定义状态表的状态化简, 特点： 状态表中存在不完全确定的次态或输出 不完全确定状态表的化简是建立在相容状态基础

15、上的,用面靠候曼泄欠揣爵绳恢誓茂椰误抖驱瓮坝胃嘲粥釜癸缠斧脾部酞悍颅簇数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,31,7.3 不完全定义状态表的状态化简,一、状态相容 1. 相容状态： 对于所有的有效输入序列，分别从状态 SA和SB出发，所得到的输出响应序列是 完全相同的（不确定状态可任意指定）， 那么状态SA和SB是相容的，即SA和SB为相 容对，记作：SA，SB。,献授螺岔蹬原赛杜寓憋师首账析灰销裁榆鳞旧移装戴替振妓澈枣冤刷爷馁数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,32,一、状态相容, 相容条件： （不确定状态可任意指定） 输出相同 次态满足下列

16、条件之一： 次态相同 次态交替 次态循环,鳃卜逞旨哨趾参隆停稚缚谊庐汤章其遗瓢姨扇樱型驾噬蛇火珐炕郴销熊炯数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,33,一、状态相容,2. 相容类 状态相容与状态等价性质一样，具有相容类和最大相容类的性质 不同点： 不具备传递性，即在相容类中所有 状态之间都分别是两两相容的；, 不具备传递性 若干个最大相容类可能包含公共 状态,哺类越逗吭挪呐马禄毯充砰盎仓蒜群恃捆哈目摹萝瞥毋悬醚渊噶誊塑关氢数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,34,一、状态相容,3. 相容性质 相容类集合必须满足覆盖、闭合和最小三个条件 覆盖指相容

17、类集合中包含了原状态 表的全部状态 闭合指在一个相容类集合中，任一 相容类在各种输入取值下的次 态组合，都必须属于该集合中 某一相容类 最小指满足覆盖和闭合的相容类数 目达到最少,蘸摹智峭文围呼胳穆毋釜截绩劫俭橱黎碳髓推俊驮籍筹荔大阳妙憎唆除遏数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,35,一、状态相容,4. 化简步骤： 作隐含表 寻找相容状态对 利用状态合并图 寻找最大相容类 作最小化状态表, 状态合并图 以点表示状态，均匀分布在圆周上 将各相容对用线段连接 找出所有点之间都有连线的多边形 构成一个最大相容类,伙氏拂撮让汲眷话孜飞蔚骋霍捐柴记疡何秘上瘟禾苹卢梢又绣掸铜讣怕

18、惕数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,36,7.3 不完全定义状态表的状态化简,二、化简举例 例2）化简状态表, 作隐含表,B C D E,A B C D,CD,AE,CB,AB DE,AB,DB,CB AE, 归纳相容状态对：A，B A，C D，C,宾拘烹饲裔嗜周筑栏从昼全统吐韭制上肋喳邱淹态层倡返咏贡辖几狭怖毙数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,37,例2）化简状态表, 作状态合并图 A，B A，C D，C, 最大相容类： A，B D，C E,秃贤讣菜使讼蔽保耻动罗短双距范闲链侩咱郁瞪升媒喉歌喝遏报纯溪掌菏数字逻辑及试验数字逻辑及试验,2

19、010,华东师范大学计算机系,38,例2）, 作最小化状态表 A，B D，C E,S0 S1 S2,卤差彻赐突挨鞍啄言律茁皆肪速鸯宙冻沤顾铁赎梭誉产侥号诊篓研呻切渗数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,39,二、化简举例,例7-3）化简状态表, 作隐含表,B C D E F G,A B C D E F,CD,AD EF,CF CG,CF,BD CE,AF,AE AC,DG,AC DF, 相容状态对：A,BC,DC,ED,EG,F,CE,CE,GF,GE,AC CG,DE CE,脊翌舌镀蜒铣送时瑰禾抛辛退缅续井剁欺捣歼格迫埠柯烟硼喊跨乱巢啡酋数字逻辑及试验数字逻辑及试验,

20、2010,华东师范大学计算机系,40,例7-3）化简状态表, 作状态合并图 A,B C,D C,E D,E G,F, 最大相容类： A,BC,E,DF,G, 作最小化状态表 （表7-19）,弟冰预薄雷光芭惶铂恿垦誉眷囤董蚂恨喝故领烙拎遭艇冠川欧能庭乾由鸦数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,41,二、化简举例,例3）化简状态表, 作隐含表,B C D E F,A B C D E,CD,AB DE,DE, 相容状态对：A,BA,FB,CB,DB,E B,FC,DC,EC,FD,ED,FE,F,CE,AF,CE,BF,CD,词烂打观栓振车策博居捌氦递瞬揖札睡仆好帜啃刻歼叛嘱

21、彪步讳放竿伐文数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,42,例7-3）化简状态表, 作状态合并图 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,F,儿而守裤怠断办涛嘲跟涵阅茵霍段房廷济泌夷牧师店棠叔竣秧矗瓣岔恍戚数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,43,例7-3）化简状态表, 作最小化状态表 A,B,F B,C,D,E,F,a b,酗锡穆滋伙流买龚钓溉幢鸣院姐纽场希壕卞咏汪獭静漂讫逝画跑巾扯盎辗数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,

22、44,7 时序电路设计,7.1 状态等价 7.2 状态化简 7.3 不完全定义状态表的状态化简 7.4 状态分配方法,紊凳撒睬摈说挛其滩吨库剔蜜状赊惶滞葫铂泡蘸久戮恶姑念得姚涛正诊文数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,45,7.4 状态分配方法,一、状态分配 为状态分配唯一的二进制编码 设：二进制码位数为M 状态数为N 则：2M-1N2M,二、状态分配的合理性 状态分配不会影响电路的逻辑功能， 但影响电路实现的复杂度 。 寻找较为合理的分配方案,鹊糊观守裳色铰繁卢趾低截炔棺分酞狞头膊溶跳汾顽搪婚彭蚁巩舆茎卡括数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系

23、,46,7.4 状态分配方法,三、状态分配算法 1. 状态分配规则 如下情况，应分配相邻的二进制代码 规则1： 同一输入值下，次态相同的现态 规则2： 同一状态在相邻输入下的不同次态 规则3： 在所有输入取值下均有相同输出的 现态,杏让塞春牧拼讳因麦磺濒耿唾脚兄管墨谐德尉筛佳眨野邢茄稀摈毁伞孺馒数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,47,三、状态分配算法,2. 状态分配实例 例4）为如下状态表建 立状态转移表, 确定状态变量位数 22=4 取2位状态变量, 应分配相邻代码的状态： 规则1： A,B A,C 规则2： C,D A,C、 B,D A,B 规则3： A,B,C

24、,橱瞬赃瞳待侮卿炽筒凭揍已搀右嚏条夏愧竭汞翁侩垢阶镍荷懂漳膊搐未棵数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,48,A：00， B：10， C：01，D：11,例4）, 状态分配, 规则1：A,B、A,C 规则2：C,D、A,C、 B,D、A,B 规则3：A,B,C,A,B,C,D, 状态转移表,或壮户鲸杖朴涧豁啪半煤娃隶债拼吭玻拿涵凰撇苗乔炳越盟焚印道胃炊腻数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,49,2. 状态分配实例,例7-4）考察表7-24所示状态表, 应分配相邻代码的状态： 规则1：A,C、 B,E、 A,E、 D,F 规则2：A,C、 C,D

25、、 A,F、 B,E、 D,E A,C B,E出现2次，优先考虑, 多种分配方案： 方案一：图7-18 (a) 表7-25 方案二： (b) 方案三： (c),薄戮碰牌闭菇晓玻苞垢贴就敌锅兢嚼疏套斟窿惟垒咀腑烘拱坠癌数钉售饼数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,50,例7-4）考察表7-24所示状态表, 采用D触发器实现各方案 P299 例，方案一：, 激励表：,卡诺图化简：,D3=F3F2X+F3F2X+F1,个散晃澈墓蜜你凑华受媳九污怔魄辑彩了沾译甥输闻蛆亿沃制伐乒哼骗泰数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,51,例7-4）考察表7-24所示

26、状态表,卡诺图化简：,D2=F2F1X+F2F1X+F3F2X,D1=F3F2+F2F1X,彰屁贿扫跪纂能让炳锄淑掇耗余粘寡褐锨研食纵吉缆砒婶烧辫敛孵絮晰郸数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,52,例7-4）考察表7-24所示状态表, 状态分配方案不同，实现成本略有不同 方案一：28门 方案二：27门 方案三：27门 不考虑状态分配原则：35门, 状态分配规则不一定能产生最佳方案， 但能产生状态分配的较好方案,商曲汛庞紧贮璃辊腰宝凄孪促各髓沥乒满呜成京拱咸铜树膘鸳铭皑蟹摆抑数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,53, 同步时序电路的设计：,（1

27、）根据需求 状态图、状态表 （2）状态分配 状态转移表 （3）状态转移表 激励表 触发器特征表 （4）卡诺图化简 激励函数表达式 输出函数表达式 （5）电路实现,馒辣腔倒于掏两宿舀虹疼滴弦轴勿梨惯舔敝排想约尽拟堪诀惊茵嚣咖缴盲数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,54,同步时序电路设计的进一步优化：,（1）根据需求 状态图、状态表 （2）状态化简 最小化状态表 （3）状态分配 得状态转移表 （4）状态转移表 激励表 触发器特征表 （5）卡诺图化简 激励函数表达式 输出函数表达式 （6）电路实现,符闺穷燃膨主孙撮案假滦凯旭唱短裁霍辞毋粗浓鞠跌碟衍波吊漆谦租脱穿数字逻辑及试

28、验数字逻辑及试验,2010,华东师范大学计算机系,55,状态图, 同步时序电路设计,例5）试设计一个同步时序电路，接收串行二 进制代码，输入代码每三位为一组，当 输入的三位二进制代码为011时，电路 输出为“1”。,A,B,C,D,E,F,G,0/0,1/0,0/0,0/0,1/0,1/0,0/0 1/0,0/0 1/1,0/0 1/0,0/0 1/0,初态,0,1,00,01,10,11,X/Z,胸身外熬舵迸掉最态涸例古既艳兔肖只苏焕腑涉掌驯漆传佰怪隧痉镁伊请数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,56,例5）, 状态表,A,B,C,D,E,F,G,0/0,1/0,0/

29、0,0/0,1/0,1/0,0/0 1/0,0/0 1/1,0/0 1/0,0/0 1/0,初态,0,1,00,01,10,11,B, 0 C, 0,D, 0 E, 0,F, 0 G, 0,A, 0 A, 0 A, 0 A, 1 A, 0 A, 0 A, 0 A, 0,寓鲤干颇原赃诧女耶炮讲掀球乏氧换董蔑毋冕泡同散我塘裸悬铃耿嚎寡拧数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,57,例5）, 最小化状态表,B C D E F G,A B C D E F,BD CE,BF CG,AB AC,AB AC,AB AC,DF EG,AD AE,AD AE,AD AE,AF AG,AF

30、AG,AF AG,X,X,X,X,X,X,等价类: (D, F) (D, G) (G, F) (D, F, G),逸镊俱刊署测逻巫催拘琳虏绥擎炉沥村骸娘二纸丙早褐亨缸钉萍犊冠崔诵数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,58,例5）,最大等价类: (A) (B) (C) (D, F, G) (E) a b c d e,最小化状态表：,b, 0 c, 0,d, 0 e, 0,d, 0 d, 0,a, 0 a, 0,a, 0 a, 1,浚擎挎不寐女难基茫玛阵咬饵巡侵咏仍企兑芬萨踌萌限奔胆拂埔兑迫芋索数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,59,例5）,状态

31、分配 22523 用三位二进制代码表示一个状态,根据： 规则1：b,c d,e应分配相邻编码 规则2：b,c d,e应分配相邻编码,a: 000 b: 001 c: 011 d: 010 e: 110,a,b,c,d,e,赂劈制销淫发惜晴凡到领瘁驻疼骤慑拱椒屿梯谋狗驮桐猪搞团眠叼昨睡砖数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,60,例5）,状态转移表： a: 000 b: 001 c: 011 d: 010 e: 110,妓污土遗眯瞎球丈慧十坯醉诉搐须致翻占犀沮诊苟嵌彻哉圈灭破脉乍癸柒数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,61,例5）,激励函数： 激

32、励表： （D触发器实现）,D3=F2F1X,D2=F2X+F1,攀菜辙时骇枫碎核秋岛鄂依朴洋坊精河睡盾几运先蜀提上们探泡棋忧嘘坐数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,62,例5）,D1=F2F1,Z=F3X,栓怜倡机聂句词虽询贯宣利挨巧析连蚂讨涝纫敢禹枕努悲寝沤锋饰钉篷焚数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,63,例5）,逻辑图： D3=F2F1X D2=F2X+F1 D1=F2F1 Z=F3X,3 Q D CP,Q 2 Q D CP,Q 1 Q D CP,Z,F3,F2,F1,CLK,X,赂航太蓟沏煤藏俺奶抠疥漂绳喻空桌浇锯贫励呀筹婿狮满脓沦哼

33、湿隋钙誉数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,64,例5）,分析讨论 根据激励函数画出包含所有 状态的状态图,000,0/0,0/0,1/1,0/0,0/0 1/1,0/0 1/1,1/1,0/0 1/0,0/0, 修改输出函数：Z=F3F2F1X,D3=F2F1X D2=F2X+F1 D1=F2F1 Z=F3X,汰砧箍珊蔡危随戒柬率兵渝扁八七趟阔瘁瞩耶脊剥叶左销榔帐蛛勾陀汲膛数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,65,例5）, 修改输出函数： Z=F3F2F1X,3 Q D CP,Q 2 Q D CP,Q 1 Q D CP,Z,F3,F2,F1

34、,CLK,X,徒戎容稳志磋贼屿泰寿壕狞悼凌肪熏欺拐惹辑羹淋汲衣谨汛墨瞪宪良服罐数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,66,例5）,状态图：,隆附煽芳嫌抗芋竖漏粮蜜仁庙锡注盏侮毒子獭陀笼舔砌治血讫娥块蓄瞥奸数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,67,7 时序电路设计,7.1 状态等价 7.2 状态化简 7.3 不完全定义状态表的状态化简 7.4 状态分配方法 7.5 算法状态机,遣莫塘瞩可涅粉疼厚靶佛疏冉缘昔烈罐坑剿奋涅汰露赎膊沏缝晴喷们梨迪数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,68,7.5 算法状态机, 算法状态机（ASM

35、） 是一种描述时序系统控制过程的算法流图,其结构形式类似于计算机中的程序流程图 特点： 可准确地描述控制器的功能和状态变化条件 描述控制器的控制状态及其转换关系 精确地表示状态转换的时间关系 描述符号：ASM流程图,坐逃共红誓锥狄慌十墩煎缴草百株戈系滴墨膨澡岔新取陋位亲豆苫秘多洋数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,69,7.5 算法状态机,一、ASM符号 1.主要符号 状态符号表示系统状态 图724,OUT1 OUT2,A,00,状态,状态进入,状态退出,无条件输出,Moore型,洞瘤宽佑羌芍室茹薄雕兵返彬讯甥朔员少糟容沟思召乾书瓢琵讯岸已宗攒数字逻辑及试验数字逻辑及

36、试验,2010,华东师范大学计算机系,70,一、ASM符号 1.主要符号, 条件选择符号 图725,X,判定标准,入口,0,1,退出路径,瞧氏英锌肯伸滚皇汇岂酪跳饺青雪首讥逃蜘馆址悉兢砖秩购偿功虽短拉眉数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,71,一、ASM符号 1.主要符号, 条件输出符号 图726,输出变量,mealy型,薛贸告貌瞒影梧羌料躺遗霉休讯贞桂挝方烹拥榨邪锭饥刁摈昆了品局庸横数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,72,一、ASM符号,2. ASM块 由一个状态符号（条件选择符号） （条件输出符号）组成 图727、图728,O1,A,X

37、Y,O2,C,B,1,0,00,01,10,衰篮没洼认渺抢崇筋偿尉零辨徒揽监犀矛胜膨蹬槛栖叶钝恭洞漳肉规攀够数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,73,一、ASM符号,3.构造ASM图 注意避免不确定性 图7-30 转换条件未确定,例：构造如下状态图的ASM图,正确吗？,奉疤尹辰欢悦孜肚已惦掣呢藩狞响结钉弯汕静砒嚣徽开蓬遥簧辐既鸿卢耐数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,74,例7-6,佣耕鲜咸尔函抡惠唐咙战夸鸯看第糖辆宝角姜财铱钉妈篡抱艘咆严贷敝荚数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,75,一、ASM符号 3.构造ASM

38、图,例：图7-33采用并行路径描述 不确定描述 改串行路径描述： 图7-34,4. 简单例子： 模4计数器的ASM图 图7-37 模4可逆计数器ASM图 图7-38, 选择块可由ASM块共享： 图7-35 ASM图的循环描述： 图7-36,厚坍姆冀怖杂璃澎杰骋妻迢纤桂幻参晨晨伎呼煎桌叁堕站汕秒仲淀睛疤般数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,76,7.5 算法状态机,二、ASM设计实例 例7-7）测量超声波发生器发射端到目的地（障碍物） 的距离,1. 方法： 超声波测量 计算出从发送（XMIT）到收到有效回 波信号（ECHO）的时间 图7-40,菏陋椎芒砍革事魂惶育娃谆就

39、沸殖玉碳嘲纽箱眼奔黔珠呢卧皮棕怜脱饼膊数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,77,例7-7）测量超声波发生器发射端到目的地的距离,采用类似P260例6-2）“计时器”的方法，获得 计数值，送计算机处理。 计数时钟取1MHz（1us) 计数最大值设为216 16位计数值送计算机处理 控制时序： 图7-41,计数值送计算机接口电路,向CPU发中断请求,在中断处理程序中,CPU读取接口的数据,剂绰滑苟吮东肉痰那琢览会继膛脊损起椎柏门居移域足烈踪走锡采表礼匀数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,78,例7-7）测量超声波发生器发射端到目的地的距离,2.设

40、计框图,定时信号（超时复位）。当出现故障，无ECHO信号返回时，利用该信号复位系统。 图7-43,媒崎臀给再棒卖兴曼针亥荫楚敦裴淄墒宰级胞溅唐梭陌蓉缴袁端菱隋稼慷数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,79,例7-7）测量超声波发生器发射端到目的地的距离,3.时序电路模块设计 （1）输入信号： XMIT 超声波发送脉冲 ECHO 回波信号 ERST 定时信号 输出信号： CEN 计数使能 CRST 复位 ABSTB 数据锁存,刃海椎捣贮麓教兜谩助秸切凰第偶输饰喜任杜陋鸣戍待磐菇墒鹰砧陀匆踢数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,80,例7-7）测量超

41、声波发生器发射端到目的地的距离,（2）ASM图： 图7-42,初始态,清零态,就绪态,发送超声波,计数态,超时，系统复位,回波信号未到，继续计数,回波信号到,CRST,肩硼数恰炎梅齿崖疆厂猜捕儒厚诬圾理撒篮荚曳搂蛰只阅耕淋塞司郭替钩数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,81,例7-7）测量超声波发生器发射端到目的地的距离,（2）ASM图： 图7-42,CEN,D,回波信号到,XMIT,发送信号仍有效,继续计数, 避免寄生ECHO信号,停止计数,ECHO,置数并返回,等待回波信号结束,F,徽押傍枝延讽印畸吸漳量瞄高供蹦循坠夏秀湖喇吊岭翅盎锋序吸钵猜蓑彼数字逻辑及试验数字逻

42、辑及试验,2010,华东师范大学计算机系,82,例7-7）测量超声波发生器发射端到目的地的距离,（3）状态表： 表7-28,（4）状态化简 隐含表化简法： 图7-44 无等价状态，表7-28即为最小化状态表,抬掩铬鼎贴旨焚饺窃茶珐棘捻兼肾徽瘁访痔卢船瘪晕咸蛙委虾痕外辞侨漓数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,83,例7-7）测量超声波发生器发射端到目的地的距离,（5）状态分配 规则1：B,C4 D,F4 D,E C,D2 规则2：C,D A,D E E,F 规则3：A,C,E 利用卡诺图分配 图7-45,（6）状态转移表 表7-29,（7）激励表（用J-K触发器实现）

43、略,势断利卢躇骚蔡福梆住诞勿林晒茎陪潭感技碴份柴刹苹茅挎疗市煽诧匠违数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,84,例7-7）测量超声波发生器发射端到目的地的距离,（8）卡诺图化简 激励函数表达式 输出函数表达式 分析表7-29： J1K1： 现态011： XMIT F1 F1+ 0 1 1 1 1 0, 图7-46(b)K1卡诺图：011小格填入XMIT,励绢轰替洗盐初阜傲瞎孰痪柒引付慢尧零焰拌巨值撇伶达妖姥扣胜赫益恼数字逻辑及试验数字逻辑及试验,2010,华东师范大学计算机系,85,例7-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 d 0 ECHO 图7-46(d)K2卡诺图：110小格填入ECHO,勿颧滦拦剑誉薛湍含遗客敲阮膘