第七章 时序电路的设计(1)

第七章时序电路的设计概述

电路分析比较有规律，对于一给定的线路，分析后的结论往往是唯一的。

电路设计：有规律，但不严格，一定程度上依赖于设计者的经验和技巧，对于一个给定命题，最终设计出来的线路不唯一，我们追求的是一个最小化的可靠的电路实现，由此引出了本章要讨论的几个命题。

第七章时序电路的设计时序电路数学模型

用有限状态自动机M=(,Q,Z,,)表示输入量集合：:(

0，1，…n)所有输入的有限非空集合内部状态集合：Q:(S0，S1，…Sr)内部状态的有限非空集合输出量集合：Z:(z0,z1，…zm)外部输出的有限非空集合第七章时序电路的设计次态函数：Q

Q；内部状态转换控制函数，是现态和输入笛卡尔乘积至次态的一个映射。

(Si,j)=SkSi：现态

j：输入Sk：次态输出函数

：Q

Z；内部状态和外部输入笛卡尔乘积到输出的映射。

(Si,j)=Zk第七章时序电路的设计同步时序电路的设计

设计一般步骤

建立原始状态图和状态表

确定输入变量和输出变量构造状态图

产生原始状态表状态化简消除原始状态表中冗余状态，以求取最简状态集Q状态分配对每一个状态赋予一个二进制代码

第七章时序电路的设计产生控制函数和输出函数根据不同触发器的激励表综合出控制函数和输出函数画出逻辑线路图

检验电路是否有自启动能力采取措施重新设计第七章时序电路的设计设计引例（完全定义的同步时序电路设计）例1：“01”序列检测器，即从一输入状态序列中检测出“01”模式的子序列。形成原始状态表和状态图

XSi01S0S1S1/0S1/0S0/0S0/1第七章时序电路的设计状态化简(略)状态分配只有2个状态,只要一个触发器,随意分配。二进制状态表：该电路是Mealy型电路

XQ01011/01/00/00/1第七章时序电路的设计控制函数与输出函数

D触发器控制函数

XQ01011/01/00/00/1输出函数:

第七章时序电路的设计逻辑电路关于D触发器的反相输出的应用

第七章时序电路的设计原始状态图和状态表的构成建立原始状态图

确定状态记忆何种信息四进制加法计数器

初始输入序列识别器（识别X输入序列中第一次出现的X＝111序列）

第七章时序电路的设计每一个状态要考虑所有输入组合下的状态转移状态归纳：在可能的情况下要尽量使用已有的状态作为下一个状态

初始输入X＝000或X＝111子序列识别器（识别X的第一序列是否为X＝000或X＝111）

第七章时序电路的设计串行输入序列中的子序列识别分以下几种情况：上例是初始第一个定长子序列检测，且只检测一次。任意起点，第一个子序列为X＝000或X＝111（一次检测任意起点，所有X＝000或X＝111子序列（循环检测）固定起点（3位一组）所有X＝000或X＝111的子序列（循环检测）第七章时序电路的设计

第七章时序电路的设计建立原始状态表前面讨论了各种输入序列识别器的设计，下面讨论运算类电路的设计。

例：设计一个二进制串行加法器电路

建立原始的状态图与状态表

ABSi00011011S0S1S0/0S0/1S0/1S1/0S0/1S1/0S1/0S1/1第七章时序电路的设计状态化简（略，此表已最简）状态分配：二个状态只要一个触发器就能表示控制函数与输出函数

第七章时序电路的设计逻辑线路

第七章时序电路的设计

设计一个串行的4位字符奇校验电路，在一串行字符输入时，每隔4位（即一字符）输出一奇校验结果1，其余时刻输出为0。

第七章时序电路的设计状态化简

状态表中状态的个数决定着时序电路里所要用的触发器的个数。为了实现最小化的电路设计，需对原始状态表中的状态个数进行压缩或状态化简。状态等价与判定

等价状态（等效状态）定义：若状态p和q对所有的可能的输入序列

（k为任意值）具有相同的输出序列，即则状态p与q等价，记为

第七章时序电路的设计例：给定如下状态表

XS01q1q2q3q3/0q1

/1q3/0q2

/1q2

/0q2/1第七章时序电路的设计等价状态性质自反性pp对称性:若pq则qp传递性若pq,qs则ps等价类:相互等价的状态集合

最大等价类：若一个等价类不包含在任何其它等价之中，则该等价类为最大等价类。等价状态判定定理

若pq

当且仅当

(p,x)=(q,x)且(p,x)(q,x)第七章时序电路的设计等价状态判定方法

判定两个状态是否等价根据判定定理有两个条件：输出相同：要满足现输入X所有取值时都相同次态等价：次态相同次态交错次态循环次态自循环后继次态等效第七章时序电路的设计例1：给定原始状态如下

XSi01ABCDEC/1C/1B/1D/0D/0B/0E/0E/0B/1B/1第七章时序电路的设计例2：给定原始状态如下XSi01ABCDEFGC/0F/0C/0D/1C/0F/0C/1B/1A/1G/0E/0E/1G/0D/0第七章时序电路的设计利用隐含表进行状态化简

画隐含表

顺序比较

关连比较

列出最大等价类并求出最小复盖求取简化状态表

第七章时序电路的设计例2的隐含表最大等价类：(A,B,E),(C,F),(D),(G)abcd简化状态表：XSi01abcdb/0b/0c/1b/1a/1d/0a/0c/0第七章时序电路的设计第七章时序电路的设计状态分配最佳分配的复杂性

分配方案数

S：状态数，K：状态编码的位数（触发器数）从2k组二进制编码中，取S组来表示S个状态，可能出现的分配方案数为：第七章时序电路的设计实质方案数

假定S＝4K＝2，4个状态为NA=24

而实质方案数NAe=3第七章时序电路的设计次佳分配规则

相邻—两状态编码中仅有1位不同，有利于触发器控制函数化简和输出函数化简R1：次态相同，现态相邻

R1a不同输入取值下的次态分别相同，则现态相邻。

R1b不论输入取值，若次态已相邻则具有相同次态集合的现态应相邻。

R1c不同输入取值下部分次态相同，则现态相邻。R2：同一现态，次态相邻R3：输出完全相同，现态相邻(有利于输出函数化简)第七章时序电路的设计例1：对下列状态表进行分配XS01S0S1S2S3S4S5S6S1,0S3,0S2,0S5,1S6,0S0,0S0,1S2,0S2,0S3,0S6,0S5,0S1,1S1,0R1a：S5S6R1b：S3S4R1c：S0S1R2：S0

S1，

S1S2，S2

S3，S5S6R3：S0

S1

S2

S4，S3S6第七章时序电路的设计串行4位字符奇校验电路的设计，其状态表如下：

R1a：FGR1b：DE,BCR1c：R2：BC,DE,FGR3：ABCDE第七章时序电路的设计第七章时序电路的设计

例：一个串行输入x,二进制序列3位一组，设计一个时序电路识别能到序列组编码为010或100时输出Z=1，其余情况Z=0状态图、表状态化简状态分配用D触发器和与非门实现输出函数和控制函数逻辑电路第七章时序电路的设计第七章时序电路的设计设计一个以5为模的可逆计数器第七章时序电路的设计串行8421码检测器的设计X为一串行输入序列，每一个子序列以“1”开头，“1”之后4位代表8421码(低位先出现：b0b1b2b3),一个8421码后的“0…0”子序列表示间隔。要求设计一个8421码的检测电路，当发现非8421码时输出Z=1。第七章时序电路的设计不完全定义同步时序电路的设计

不完全定义同步时序电路

完全定义同步时序电路：电路中每一个现态与输入组合所对应的次态和输出都是确定的。

不完全定义同步电路：电路中存在某些现态与输入组合，他们所对应的次态或输出是不确定的或是无关紧要的。产生不确定次态或输出的根源

外部输入存在某些不可能出现的序列

外部输出仅在某些特定时刻才有意义

某确定时刻，外部输入之后必跟随一系统复位信号

第七章时序电路的设计示例：一个“1111”序列检测电路用作一爆炸装置的引爆控制，输入X通常处于“0”状态，一旦接受了连续4个“1”，（其中不会出现“0”），第4个“1”输入时电路将产生Z＝1的输出，引起爆炸，该电路也不复存在。

XSi01ABCDA/0d/dd/dd/dB/0C/0D/0d/1第七章时序电路的设计状态相容

相容关系性质：自反性pp对称性:若pq则qp不传递性 可应用输入序列定义：给处于初态q的不完全定义时序电路加入一输入序列，除最后一个次态外，每一个输入总能导致下一个确定状态，则这一输入序列称为对该电路在q状态时是可应用的输入序列。

第七章时序电路的设计输出相容定义:两个输出序列中各对应输出，在两者均有定义时是一致的，则这二个输出序列是相容的。状态相容定义：在不完全定义同步时序电路中，分别以p和q为初始状态，如果加入任何可应用的输入序列后，得到两个输出序列是相容的，则p和q是相容的，记

pq。状态相容判定定理：若pq当且仅当

(p,x)(q,x)且(p,x)(q,x)第七章时序电路的设计相容类和最大相容类：状态相容判定方法：输出相容

次态相容次态相同次态交错次态循环次态自循环后继次态相容任一次态为无关项d第七章时序电路的设计隐含表化简法

用隐含表找出相容对用合并图找出最大相容类作最小化状态表复盖性：原始状态表中，每个状态至少属于该组中某一个相容类。

闭合性：该组中任一相容类，在任何一种输入取值时的次态属于该组中一个相容类。最小性：满足上述条件的相容类数最少。用复盖闭合表求最小化相容类集。第七章时序电路的设计例：简化状态表XSi01ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d(AB),(AC),(AD),(AE),(BC),(CD),(DE)第七章时序电路的设计

(ABC),(ACD),(ADE)XSi01A’B’B’/0A’/1A’/dA’/d第七章时序电路的设计

XSi01ZABCDEFBBAdFdDDEEdC0d111d第七章时序电路的设计不完全定义同步时序电路设计举例：火车终点站，一辆火车Ti入站和另一辆火车To出站发生在同一时刻，要求设计一个火车出入站调度控制系统信号：X1/X2/X3为了3个监视传感器，当Xi有脉冲时表示有火车通过，S1/S2为道叉控制开关,L1/L2为红绿灯，红灯停，绿灯放行。初态：Ti欲进站，To欲出站；L1/L2=Red；S1连主轨，S2接侧轨。过程：T0通过X3入侧轨，停在L1处；Ti通过X1，入主轨，再经过X2，停在L2处，当Ti经过X2时，L1=Green，S1连侧轨；T0出侧轨，经过X1时，L2=Green，S2连主轨。Ti前进，经过X1后系统恢复初态。约束条件：