第5章时序逻辑电路

在组合电路中加入用来存储电路历史信息（称为状态）的存储元件即可构成时序电路。时序电路与组合电路的主要区别是： 组合电路的输出只与当前的输入有关； 而时序电路的输出不仅与当前的输入有关，而且还与当时的状态有关。由于时序电路的特点与组合电路不同，所以对时序电路的研究方法也与组合电路有所不同。在组合电路设计中，使用函数的真值表来描述一个组合逻辑问题； 而在时序电路设计中，则使用时序机的状态表来描述一个时序逻辑问题。

时序电路分为同步时序电路和异步时序电路。同步时序电路的特点是电路有统一的时钟脉冲，在次态函数(又称为激励函数)的控制下，只有当时钟脉冲到达时电路的状态才发生改变； 新的状态一旦建立，又形成新的激励，但直到下一个时钟脉冲到达之前电路的状态不会发生新的变化。同步时序电路工作稳定、可靠，而且分析和设计较为简单，这是同步时序电路被广泛采用的原因所在。但是，在有些场合，如当电路的工作速度较高或者输入是随机变化的场合，或是电路中不同部件的工作速度相差较为悬殊的场合，往往采用异步时序电路。

本章只介绍同步时序电路。

5.1时序电路与时序机
5.1.1时序电路的结构和特点

为了充分理解时序电路的结构和特点，不妨先回顾总结一下组合电路的结构和特点。图5.1展示了组合电路的结构模型，图中，x1，x2，…，xn为某一时刻的输入； Z1，Z2，…，Zm为该时刻的输出。显然，组合电路的逻辑功能可用下列输出函数集来描述： 

Zi=fi(x1，x2，…，xn），i=1，2，…，m

由此可见，组合电路的特点是电路在任何时刻的输出Zi仅与该时刻的输入x1，x2，…，xn有关，而与该时刻以前的输入无关。

时序电路是由组合电路和存储元件两部分构成的，它可以用图5.2所示的结构模型来表示。对图中组合电路而言，它有两组输入和两组输出。其中，输入x1，x2，…，xn称为时序电路的外部输入； 输入y1，y2，…，yk称为时序电路的内部输入，它是存储元件的输出反馈到组合电路的输入； 输出Z1，Z2，…，Zm称为时序电路的外部输出； 而输出Y1，Y2，…，Yp称为时序电路的内部输出。




图5.1组合电路的结构模型




图5.2时序电路的结构模型



时序电路通过存储元件的不同状态来“记忆”以前时刻的输入。状态是时序电路的一个重要概念，它用来表示时序电路的过去属性。通常称y1，y2，…，yk为时序电路的现态，而时序电路的外部输出Zi和内部输出Yj是当前输入x和现态y的函数： 

Zi=fi(x1，x2，…，xn； y1，y2，…，yk），i=1，2，…，m
Yj=gj(x1，x2，…，xn； y1，y2，…，yk)，j=1，2，…，p

一般称Zi为输出函数，Yj为激励函数或次态函数。

因此，时序电路的输出不仅与该时刻的输入有关，还与当时的状态有关。这就是时序电路的主要特点。表5.1概括了组合电路和时序电路的区别。


表5.1组合电路和时序电路的区别



类别组 合 电 路时 序 电 路
电路特性输出只与当前输入有关输出与当前输入和状态有关
电路结构不含存储元件含存储元件
函数描述用输出函数描述用输出函数和次态函数描述

5.1.2时序机的定义

时序机在有的文献中亦称为有限状态机或有限自动机，它是一个从实际中抽象出来的数学模型。任何一个时间离散系统，只要满足下述定义，不管是具体的物理机器（如一个时序电路），还是抽象的虚拟“机器”（如一个算法），都可以称为时序机。

时序机是这样一个系统，它可以用5个参量来表征： 

M=（I，Ｏ，Q，Ｎ，Z）

其中，I为时序机的输入字母有限非空集合； Ｏ为时序机的输出字母有限非空集合： Q为时序机的内部状态有限非空集合； Ｎ为时序机的次态函数，它表示输入及状态到次态的映射，即I×Q→Q； Z为时序机的输出函数，它有以下两种情况。

（1） 若输出函数Z是输入和状态的函数，即Z： I×Q→Ｏ，那么该时序机称米利（Mealy）型时序机。

（2） 若输出函数Z仅是其状态的函数，即Z： Q→Ｏ，那么该时序机称穆尔（Moore）型时序机。

能够用时序机来描述的例子是广泛存在的。如日常生活中的电话系统、自动售票机、号码锁、数字系统中的触发器、时序逻辑电路，甚至数字计算机等都可用时序机来描述。

5.1.3时序机的状态表和状态图

在工程应用中，时序机通常用更直观的形式——状态表和状态图来表示。所谓状态表，就是用表格方式来描述时序机的输入、状态和输出之间的关系，而状态图是用图解方式来描述上述关系，两种方法相辅相成，经常配合使用。由于两种类型时序机的状态表和状态图在表示方法上有所不同，因此下面分别进行讨论。

1. Mealy机的状态表和状态图

Mealy机的状态表和状态图反映了时序机的输出与它的输入以及现态之间的关系。设时序机的输入I为I1，I2，…，In，时序机的内部状态Q为q1，q2，…，qk，则状态表的一般形式如表5.2所示。


表5.2Mealy机状态表的一般形式



Q
I
I1…In

q1N(q1，I1)，Z(q1，I1)…N(q1，In)，Z(q1，In)

︙︙︙︙
qkN(qk，I1)，Z(qk，I1)…N(qk，In)，Z(qk，In)

表中，qi行和Ij列（i=1，…，k； j=1，…，n）相交处的项表示当时序机处于状态qi并在输入Ij时的下一状态和输出，这个项表示成N(qi，Ij)、Z(qi，Ij)，这里N和Z 分别是时序机的次态函数和输出函数。



图5.3Mealy机状态
转换的表示


状态图是这样建立的： 用小圆圈表示状态qi，用有向箭头表示状态转换的方向，并在箭头上标上Ij/Zk，它表示在输入值Ij的情况下，状态由qi转换到下一状态qi+1时，其输出为Zk，如图5.3所示。


应该注意，在状态表和状态图中没有标出时钟脉冲。而实际上，对同步时序电路而言，只有在时钟脉冲作用下才发生状态的转换（这是由同步触发器的特点决定的）。这里规定： 在某时钟脉冲到达以前电路所处的状态称为电路对该时钟脉冲的现态； 而把该时钟脉冲到达之后电路的状态称为电路对该时钟脉冲的次态。还有一点要指出的是，对Mealy型时序电路来说，当输入发生变化时，输出立即跟着变化，而电路状态要等到下一时钟脉冲到达后才发生变化，状态变化后，输出再次随之发生变化。

2. Moore机的状态表和状态图 

由于Moore机的输出仅与现态有关，因此在Moore机的状态表中，每一现态qi的行都应有相同的输出，而与输入无关，因此可以把它们提出来新开一列。Moore机状态表的一般形式如表5.3所示。


表5.3Moore机状态表一般形式



Q
I
I1…InZ



q1N(q1，I1)…N(q1，In)Z(q1)
︙︙︙︙︙
qkN(qk，I1)…N(qk，In)Z(qk)



图5.4Moore机状态
转换的表示


在Moore机的状态图中，输出Zk应与状态qi写在一起，表示Zk只与状态有关，即在圆圈内标以qi/Zk； 输入仍标在箭头上，如图5.4所示。


由于Moore机的输出仅与现态有关，因此新的输出是由转换后的状态决定的，也就是说，先有状态的变化，再形成新的输出。这一点与Mealy型电路有所不同，而这一不同，归根到底是由于两种类型时序电路的输出不同引起的。

5.1.4完全定义机和不完全定义机

在组合电路中，如果一个布尔函数的真值表中所有输出值都是确定的，则此函数称为完全定义函数； 否则，称为不完全定义函数。

在时序电路中，如果一个时序机的状态表中所有的次态/输出都是确定的，则此时序机称为完全定义机； 否则，称为不完全定义机。

不完全定义机在实际中是常常遇到的。例如，当时序机处于状态qi 时，由于不可能（或不允许）出现输入Ik，所以当从状态qi向下一状态转换时，次态/输出是随意的，或没有意义的。如下面将要介绍的基本RS触发器不允许同时输入置1和置0信号就是其中一例。有时，即使是完全定义机，往往在给其状态表的符号状态进行二进制编码时，会使完全定义机变成不完全定义机。例如，一个模6二进制加1、减1计数器，其状态表如表5.4所示。表中，当x=0时，进行加1计数； 当x=1时，进行减1计数。为了表示6个状态q0～q5，至少需要3个存储元件（触发器），设用y1、y2和y3来表示。经过二进制编码后的状态表如表5.5所示。从表中可以看出，由于二进制编码，产生了两行无定义的次态和输出。这说明即使给定一个完全定义机，经过二进制赋值后，也会变成不完全定义机。


表5.4计数器的状态表



Qx
01Z



q0q1q50
q1q2q00
q2q3q10
q3q4q20
q4q5q30
q5q0q41



表5.5经过二进制编码后的状态表



y1y2y3x
01Z

0000011010
0010100000
0100110010
0111000100
1001010110
1010001001
110ddd
111ddd

5.2触发器

触发器是一种具有记忆功能、能存储二进制信息的逻辑电路，是构成时序逻辑电路的基本单元。

触发器具有两个基本特征： 第一，具有两个稳定状态，分别称为“0”状态和“1”状态，触发器的这两个稳定状态可以分别表示一位二进制代码0和1。在没有外界信号作用时，触发器维持原来的稳定状态不变，即触发器具有记忆功能。触发器又称为双稳态触发器； 第二，在一定的外界信号作用下，触发器可以从一个稳定状态转变到另一个稳定状态。这表明触发器可以接收信号，并保存下来。外界信号的作用称为触发，这也是触发器名称的由来。触发器从一个稳态转变到另一个稳态的过程，称为翻转。

触发器按照逻辑功能的不同可分为RS触发器、JK触发器、T触发器和D触发器等几种类型。

5.2.1基本RS触发器

基本的RS触发器是电路结构最简单的一种触发器，也是构成其他触发器的基础。由与非门构成的基本RS触发器的逻辑图和逻辑符号如图5.5所示。



图5.5基本RS触发器


该触发器由两个两输入与非门A和B的输入/输出端交叉连接而成，它有两个输入端和两个输出端。Q为触发器的“1”输出端，简称“1”端，为“0”端。通常将Q端的状态定义为触发器的状态，即当Q=1时称触发器为“1”态； 当Q=0时称触发器为“0”态。在正常情况下，Q与端的输出状态总是彼此互补的。当Q=1时，=0； 反之，当Q=0时，=1。

触发器的两个输入端和分别称为置1端和置0端。字母S(Set)和R(Reset)上的横杠及图5.5逻辑符号中的小圆圈均表示置0、置1信号是低电平有效，即平时这两个端应接高电平，只有在输入端或接低电平（或负脉冲）信号时，触发器的状态才可能改变。

当=0、=1时，不论为何种状态，都有Q=1、=0。可见，不论触发器原来的状态如何，当在端加低电平信号时，触发器都将被置为1状态。而且在端低电平信号消失后，即=1、=1时，触发器的状态保持不变。

当=1、=0时，不论Q状态如何，都有=1、Q=0。可见，不论触发器原来的状态如何，当在端加低电平信号时，触发器都将被置为0状态。同理，在端低电平信号消失后，触发器的状态保持不变。

当=1、=1时，触发器状态保持不变。

当=0、=0时，Q与全为1，使Q与彼此互补的逻辑关系遭到破坏。这是不正常情况，是不允许的。而且，当和低电平信号同时消失后，触发器的状态将无法确定，可能是0，也可能是1。

表5.6为基本RS触发器的真值表。其中，和为触发器的输入信号； Qn为触发器接收信号之前的状态，称为现态； Qn+1为触发器接收信号之后的状态，称为次态。


表5.6基本RS触发器真值表



QnQn+1


000×
0011
0100
0110
100×
1011
1100
1111

从使用触发器的角度出发，通常用简化的真值表，即功能表，表示一个触发器所能完成的功能。基本RS触发器的功能表如表5.7所示。


表5.7基本RS触发器功能表



Qn+1功能
00不正常不允许
011置1
100置0
11Qn保持

根据基本RS触发器的真值表，可以得到次态Qn+1与现态Qn 、输入及的逻辑关系表达式为： 

Qn+1=S+Qn
RS=0(约束条件）(5.1)

式中，RS=0(或+=1)表示不允许同时出现=0、=0的情况，称为约束条件。式(5.1)常称为触发器的特征方程，也称为状态方程或次态方程。

在时序电路设计中，往往已知触发器的现态Qn与次态Qn+1，要求所需的输入信号值，称为输入激励。将不同现态和次态时的输入激励列成表格，称为触发器的激励表。表5.8为基本RS触发器的激励表。


表5.8基本RS触发器激励表



QnQn+1
00d1
0110
1001
111d

5.2.2同步RS触发器

实际的数字系统工作时，要求各部分电路要协调动作，因此系统中用一个同步信号来指挥电路各部分协调动作，该信号又称为时钟脉冲信号，简称时钟，用CP（Clock Pulse）表示。电路中的触发器只有在时钟脉冲到来时，才按照输入信号改变状态。这种受时钟控制的触发器统称为同步触发器或钟控触发器。

同步RS触发器的逻辑图和逻辑符号如图5.6所示。该触发器由4个与非门构成，门A和门B构成基本RS触发器，门C和门D为控制门，CP为控制信号。S和R两个输入端分别是置1端和置0端，高电平有效。在逻辑符号图中，CP输入端有标记“∧”，表示该输入端为脉冲信号。



图5.6同步RS触发器


当CP=0时，门C和门D均输出高电平，门A、B构成的基本RS触发器处于保持状态。

当CP=1时，门C、门D的输出Z1、Z2为： 

Z1= S·CP=(5.2)
Z2= R·CP=(5.3)

同步RS触发器的功能表如表5.9所示，和表5.7完全相同，只是增加了“CP=1时有效”这个条件。因此，同步RS触发器的特征方程与基本RS触发器的完全相同。


表5.9同步RS触发器功能表（CP=1时有效）



SRQn+1功能
00Qn保持
010置0
101置1
11不正常不允许


5.2.3JK触发器

在CP操作下，根据输入信号J、K，具有置0、置1、翻转和保持功能的电路，称为JK触发器，其逻辑符号和时序图如图5.7所示。JK触发器的逻辑功能如表5.10所示。



图5.7JK触发器




表5.10JK触发器的次态真值表



JKQnQn+1
0000
0011
0100
0110
1001
1011
1101
1110

其特性方程为

Qn+1=Jn+Qn（CP下降沿到来后有效）(5.4)

JK触发器的激励表如表5.11所示。


表5.11JK触发器的激励表



QnQn+1JK
000d
011d
10d1
11d0

5.2.4D触发器

在CP操作下，根据输入信号D，具有置0、置1功能的电路，称为D型触发器。根据对维持阻塞D触发器电路分析，D触发器的逻辑功能如表5.12所示。


表5.12D触发器的次态真值表



DQnQn+1
000
010
101
111

其特性方程为

Qn+1=D（CP上升沿到来后有效）(5.5)

表5.13为D触发器的激励表。


表5.13D触发器的激励表



QnQn+1D
000
011
100
111

5.2.5T触发器

在CP操作下，根据输入信号T的不同，具有保持和翻转功能的电路，称为T型触发器，其逻辑符号和时序图如图5.8 所示。T触发器的逻辑功能如表5.14所示。


表5.14T触发器的次态真值表



TQnQn+1
000
011
101
110


图5.8T触发器


T触发器是由JK触发器演变而来，即J、K相连作为信号输入端T。因此其特性方程也可以由JK触发器的特性方程得出

Qn+1=JQn+Qn
=TQn+Qn
=T Qn（CP下降沿到来后有效）(5.6)

T触发器的激励表如表5.15所示。


表5.15T触发器的激励表



QnQn+1T
000
011
101
110

5.3同步时序电路的分析与设计

任何一个数字逻辑电路，总是从一组给定的输入，得到一组确定的输出。在组合电路中，多次重复出现的输入，可得到完全相同的输出。但是在时序电路中，如果一组输入多次重复出现，电路的输出却不尽相同，这是因为在同一输入的情况下，可能有不同的现态。因此，时序电路的分析与设计要比组合电路的分析与设计复杂得多。

设计一个同步时序电路，一般可按如下步骤进行。

（1） 根据逻辑问题的文字描述，建立原始状态表。进行这一步时，可先借助于原始状态图，再构成原始状态表。这一步得到的状态图和状态表是原始的，其中可能包含多余的状态。

（2） 采用状态化简方法，化简原始状态表。这一步得到一个用字符表示状态的简化状态表。

（3） 进行状态分配（或状态赋值），即给予简化状态表中每个符号状态以二进制代码表示，这一步得到一个二进制状态表。

（4） 根据二进制状态表和选用的触发器的激励表，求电路的激励函数和输出函数。

（5） 根据激励函数和输出函数表达式，画出所要求的逻辑图。

同步时序电路的分析过程与设计过程正好相反，其主要步骤如下。

（1） 根据给定的时序电路，写出触发器的输入激励函数表达式以及电路的输出函数表达式，并由此画出激励矩阵和输出矩阵。

（2） 利用触发器的激励表（或状态表），将激励矩阵转换成Y矩阵。并与输出Z矩阵合并，得到YZ矩阵。

（3） 由YZ矩阵列出状态表，并画出状态图。

（4） 根据状态表或状态图，可作出网络的时间图或文字描述。

5.3.1建立原始状态表

状态表是用来描述时序机的输入、状态和输出之间关系的表格。因而，建立状态表需要确定3个问题： 一是电路应该包括几个状态； 二是状态之间如何进行转换； 三是怎样产生输出。解决这3个问题，至今尚没有一个系统的算法，目前所采用的方法仍然是直观的经验方法。

建立原始状态表可以先借助于原始状态图，画出原始状态图以后再列出原始状态表。

画原始状态图的过程是： 首先假定一个初始状态q1； 从这个初始状态q1开始，每加入一个输入，就可确定其次态和输出； 该次态可能是现态本身，也可能是已有的另一个状态，或是新增加的一个状态。继续这个过程，直到每一个现态向其次态的转换都已被考虑到，并且不再构成新的状态。输入也要考虑到各种可能取值。下面通过几个例子来说明上述方法。

【例5.1】列出一个模5加1和加2计数器的状态表。

显然这个计数器应有5个状态，设为q0～q4，以分别记住所输入的脉冲个数。由于这个计数器既可累加1，又可累加2，故需设定一个控制输入x，并假定x=0为加1，x=1为加2。输出Z 为计满5时的进位（即溢出）信号。

经以上分析，可画出该计数器的状态图，如图5.9所示，并由此可列出状态表如表5.16所示。



图5.9模5计数器状态图




表5.16模5计数器状态表



Q
x
01

q0q1,0q2,0
q1q2,0q3,0
q2q3,0q4,0
q3q4,0q0,1
q4q0,1q1,1


【例5.2】设计一个“01”序列检测器。该电路有一个输入x和一个输出Z。输入x 为一串随机信号，当其中出现“01”序列时，检测器能识别出来，并产生输出信号Z=1； 对于其他输入情况，输出均为0。例如

输入序列10011010001

输出序列00010010001


该时序电路应能记住“01”序列中先出现的第一个元素“0”，又能记住后出现的第二个元素“1”，这时产生输出。因此，原始状态图可这样建立，如图5.10（a）所示。假定电路处于初态A，若输入为1，因为“1”不是被识别的输入序列“01”的第一个元素，所以电路停留在状态A并输出0； 若输入为0，这是被识别的输入序列“01”的第一个元素，电路转至状态B 并输出0。当电路处于状态B时，若输入为0，这不是被识别的“01”序列的第二个元素，而仍是第一个元素，所以电路仍停留在状态B并输出0； 若输入为1，这是被识别的“01”序列的第二个元素，这时已检出所要求的序列，电路输出为1，且由于输入序列“01”已检测完毕，因此电路回到初始状态A。由状态图可列出状态表，如图5.10（b）所示。



图5.10 “01”序列检测器


【例5.3】设计一个“111”序列检测器。该电路有一个输入x和一个输出Z。输入x为一连串随机信号，每当其中出现有3个或3个以上连续脉冲时，检测器输出为1； 其他情况，输出均为0。例如

输入序列101100111011110

输出序列000000001000110

可以想象，电路有一个计数器，能记住连续输入1的个数。假定电路处于初态A，当第一次输入1时，电路由状态A 转入状态B，并输出0； 第二个信号继续输入1时，电路由状态B 转入状态C，并输出0； 第三个信号继续输入1时，电路由状态C转至状态D，并输出1； 此后若电路继续输入1时，电路仍停留在状态D，并输出1。这里，状态B、C、D为记录连续输入1 的个数的状态，当接收到一个0之后，都表示序列检测器需要重新记录连续输入1的个数，故电路将回到初始状态A。图5.11为“111”序列检测器的状态图和状态表。



图5.11“111”序列检测器


最后，必须强调指出，建立原始状态表或状态图应着眼于正确性，要尽可能不遗漏一个状态和输入的可能取值。至于所设定的状态是否多余，不必过多注意，多余状态可以通过下面要讲的状态化简来去掉。

5.3.2状态表的化简

 在建立原始状态表的过程中，可能引入多余的状态。显然，网络的状态越多，所需要的存储元件就越多。因此，在得到原始状态表后，设计的下一步工作就是进行状态表的化简，以尽量减少所需状态的数目。本小节将介绍状态表的化简方法。先介绍状态表化简的基本原理，然后分别介绍完全定义机和不完全定义机两类状态表化简的具体步骤。

1. 状态表化简的基本原理

在前面建立原始状态表的过程中可看出，设置电路状态的目的在于利用这些状态记住输入的历史情况，以对其后的输入产生不同的输出。如果所设置的两个状态，对任一输入序列产生的输出序列完全相同，则这两个状态可以合并为一个状态。状态表的化简就是根据这一原理进行的。例如，上一小节的“111”序列检测器的状态表，如图5.11（b）所示。表中，状态C和D 在现输入x 为0或1的情况下，所产生的输出分别相同，即

Z（C，0）=Z（D，0）=0，Z（C，1）=Z（D，1）=1

且所建立的次态也分别相同，即

N（C，0）=N（D，0）=A，N（C,1）=N（D，1）=D 

在现输入下所建立的次态相同，这意味着从现态C和D 开始，对于其后的所有输入序列所产生的输出序列一定都相同，故表中的状态C和D 可以合并为一个状态。这样，原始状态表可化简为3个状态的状态表，如表5.17所示。


表5.17化简后的状态表



yx
01

AA,0B,0
BA,0C,0
CA,0C,1

上面是一个比较简单的例子，用以说明两个状态进行合并的基本原理。但是，两个状态可以合并不限于这一简单情况，还有更复杂的情况。下面通过两个例子进一步说明两个状态进行合并的条件。

【例5.4】化简表5.18所示的原始状态表。


表5.18原始状态表



y
x
01

AC,1B,0
BC,1E,0
CB,1E,0
DD,1B,1
EE,1B,1

考察表中的状态B和C，在现输入x为0或1下，它们所产生的输出分别相同，即

Z（B，0）=Z（C，0）=1，Z( B，1）=Z（C，1）=0

而所建立的次态在x=1时是相同的，即都为E； 在x=0时分别等于对方的现态，即次态为现态的交错，可表示为

N（B，0）=C，N（C，0）=B

在这种情况下，尽管x=0时现态B和C所建立的次态相应为C和B，但由于这两个状态在不同输入下所产生的输出分别相同，故同样满足上述状态合并的条件。

同理，状态表中的状态D和E在现输入x为0或1下，它们所产生的输出分别相同。而所建立的次态在x=1时是相同的，在x=0时分别等于现态本身，即

N（D，0）=D，N（E，0）=E

在这种情况下，同样满足状态合并的条件。

设状态B和C合并为状态q1，D和E合并为状态q2，且令状态A 为状态q0，记为

q0={A}，q1={B，C}，q2={D，E}

代入表5.18，则可以得到简化后的状态表如表5.19所示。


表5.19简化后的状态表



y
x
01

q0q1,1q1,0
q1q1,1q2,0
q2q2,1q1,1

【例5.5】化简表5.20所示的原始状态表。


表5.20原始状态表



y
x
01

AE,0D,0
BA,1F,0
CC,0A,1
DB,0A,0
ED,1C,0
FC,0D,1

先考察状态C和F。由表可知，不论输入x 为0或1，它们所产生的输出分别相同。当x=0时，它们所建立的次态也相同； 但当x=1时，它们所建立的次态却不同。

N（C，1）=A，N（F，1）=D

因此，状态C和F能否合并取决于状态A和D能否合并。为此，需要进一步追踪A和D是否满足合并条件。

由表5.20可知，不论输入x为0或1，由现态A和D所产生的输出分别相同。当x=1时，它们所建立的次态为现态的交错； 但当x=0时，它们所建立的次态却不同： 

N（A，0）=E，N（D，0）=B

因此，状态A和D能否合并取决于状态E和B能否合并。为此，需继续追踪B和E是否满足合并条件。

由表可知，不论输入x 为0或1，由现态B和E产生的输出分别相同。当x=0时，它们所建立的次态不同： 

N（B，0）=A，N（E，0）=D 

当x=1时，它们所建立的次态也不同： 

N（B，1）=F，N（E，1）=C

因此，状态B和E能否合并取决于状态A和D及状态C和F能否合并。

至此，发现状态CF、AD及BE能否各自合并，出现如下循环关系： 





显然，由于这个循环中的各对状态，在不同的现输入下所产生的输出是分别相同的，因而从循环中的某一状态对出发，都能保证在所有的输入序列下所产生的输出序列均相同。因此，循环中的各对状态是可以合并的。令

q1=｛A，D｝，q2={B，E}，q3={C，F}

代入表5.20，则得简化后的状态表如表5.21所示。


表5.21简化的状态表



y
x
01

q1q2,0q1,0
q2q1,1q3,0
q3q3,0q1,1

综上所述，状态表中两个状态可以合并为一个状态的条件，归纳如下。

(1) 在任一现输入下，现输出分别相同。

（2） 在所有不同的现输入下，次态分别为下列情况之一。

① 两个次态完全相同。

② 两个次态为其现态本身或交错。

③ 两个次态的某一后继状态可以合并。

④ 两个次态为状态对循环中的一个状态对。

上述两个条件必须同时满足，而第一个条件是状态合并的必要条件。

显然，从原始状态表可以很容易判断任何两个状态是否满足第一条件，但不太容易判别是否满足第二条件。下面介绍的两种状态表的化简方法，就是为解决这一问题而提出来的。首先介绍完全定义机状态表的化简方法，然后再介绍不完全定义机状态表的化简方法。

2. 完全定义机状态表的化简方法

1) 等价的概念

在介绍具体方法之前，先引入等价的概念。

(1) 等价状态。设qa和qb是时序机状态表的两个状态，如果从qa和qb开始，任何加到时序机上的输入序列均产生相同的输出序列，则称状态qa和qb为等价状态或等价状态对，并记为（qa，qb）或{qb，qa}。显然，满足前面所述合并条件的两个状态是等价状态。

(2) 等价状态的传递性。若状态q1和q2等价，状态q2和q3等价，则状态q1和q3也等价，记为

（q1，q2），（q2，q3）→（q1，q3）

(3) 等价类。彼此等价的状态集合，称为等价类。例如，若有（q1，q2）和（q2，q3），根据等价状态的传递性，则有等价类（q1，q2，q3）。

(4) 最大等价类。若一个等价类不是任何别的等价类的子集，则此等价类称为最大等价类。

显然，状态表化简的根本任务在于从原始状态表中找出最大等价类。

2) 化简方法——隐含表法

它的基本思想是： 先对原始状态表中的各状态进行两两比较，找出等价状态对； 然后利用等价的传递性，得到等价类； 最后确定一组等价类，以建立最简状态表。

隐含表法的具体步骤如下。

(1） 画隐含表。隐含表的格式如图5.12所示。设原始状态表有n 个状态q1～qn，在隐含表的水平方向标以状态q1，q2，…，qn-1，垂直方向标以q2，q3，…，qn。也就是隐含表垂直方向“缺头”，水平方向“少尾”。隐含表中的每一个小方格表示一个状态对（qi，qj)。



图5.12隐含表格式


(2） 顺序比较。顺序比较隐含表中各状态之间的关系，比较结果有以下3种情况。

① qi和qj输出完全相同，次态也相同，或者为现态本身或者交错，表示qi和qj等价，在隐含表对应方格内标以“√”。

② qi和qj输出不相同，表示qi和qj不等价，在对应方格内标以“×”。

③ qi和qj输出完全相同，但其次态既不相同，又不交错，表示qi和qj是否等价，还待进一步考察，在对应方格内标以qi和qj的次态对。

(3） 关联比较。关联比较是要确定上一步待考察的次态对是否等价，并由此来确定原状态对是否等价。这一步应在隐含表上直接进行，以追踪后续状态对的情况。若后续状态对等价或出现循环，则这些状态对都是等价的； 若后续状态对中出现不等价，则在它以前的状态对都是不等价的。

(4） 列最大等价类，作最简状态表。关联比较后，可以确定哪些状态是“等价对”，再由等价对构成“等价类”和“最大等价类”。不与其他任何状态等价的单个状态也是一个最大等价类。每个最大等价类可以合并为一个状态，并以一个新符号表示。这样，由一组新符号构成的状态表，便是所求的最简状态表。


【例5.6】化简图5.13（a）所示的原始状态表。


化简步骤如下。

① 画隐含表，如图5.13(b)所示。

② 顺序比较，结果如图5.13（b）所示。

③ 关联比较，考察状态对AB，若要AB等价，就需要BC等价。从隐含表上可直接看出BC不等价，因此AB也不等价，在相应方格上打“×”号。同理，BD也不等价，如图5.13（c）所示。

④ 列最大等价类。由关联比较结果，可得最大等价类为 

（A，D），（B），（C）

令a=｛A，D｝，b=｛B｝，c={C} 

由此可做出简化状态表，如图5.13(d)所示。

【例5.7】化简图5.14（a）的原始状态表。




图5.13完全定义机状态表的化简方法




图5.14完全定义机状态表的化简方法




化简步骤如下。

① 画隐含表，如图5.14（b）所示。


② 顺序比较。原始状态表中，所有输入（I1、I2和I3）下的输出和次态都要比较，比较结果列于图5.14（b）中。

③ 关联比较。考察状态q1和q2的后继状态，出现如下循环关系： 






由于在循环链中各状态对的输出都是相同的，所以得到下列等价状态对： 

（q1，q2），（q2，q3），（q4，q5）

由隐含表可看出，由于q2 、q3和q4、q5 等价，因而q1、q3也是等价的。

④ 列最大等价类。由关联比较结果可得到最大等价类为： 

（q1，q2，q3），（q4，q5），（q6 ）

令A={q1,q2,q3}，B={q4,q5}，C={q6}

可以作出简化状态表如图5.14（c）所示。

3. 不完全定义机状态表的化简方法

1) 相容的概念

在讨论不完全定义机状态表的化简方法之前，先引入相容的概念。

(1) 相容状态。设qi和qj是不完全定义机状态表中的两个状态，如果它们的输出和次态在两者有定义时满足前面叙述的两个合并条件，则称qi和qj是相容状态，或称相容状态对。 

例如，表5.22为一个不完全定义机状态表。表中，状态A和B为相容状态，B和C也为相容状态，A和C就不是相容状态。


表5.22不完全定义机状态表



y
x
01

AB,0d,0
BA,dB,0
Cd,1B,0
DC,1D,d


(2) 相容状态无传递性。若状态qi和qj相容，状态qj和qk相容，则状态qi和qk不一定相容，如表5.22中，A和B相容，且B和C相容，但A和C却不相容。

(3) 相容类。所有状态之间都是两两相容的状态集合，称为相容类。

(4) 最大相容类。若一个相容类不是任何其他相容类的子集时，则称此相容类为最大相容类。

为了从相容状态方便地找到最大相容类，这里介绍一种状态合并图法。合并图是这样构成的： 先将原始状态表中的每个状态以“点”的形式分布在一个圆周上，然后把各个相容状态的两个“点”用直线连起来，那么所得到的各“点”间都有连线的“多边形”就是一个相容类。如果这个相容类不包含在任何其他相容类之中，它就是一个最大相容类。

例如，设有一个不完全定义机的状态表如图5.15（a）所示。由表可找到相容状态对为

（q1，q2），（q1，q3)，（q3，q4)，（q1，q4），（q2，q4）



图5.15不完全定义机的状态表及合并图


它的状态合并图可以这样构成： 先把状态表的4个状态q1、q2、q3和q4以“点”的形式标在圆周上； 然后，由各相容状态对用直线两两连起来，这样就得到状态合并图如图5.15（b）所示。从图上可以看出，有两个各点间都有连线的“多边形”。因此，求得下列两个相容类： 

（q1，q2，q4），（q1，q3，q4）

由图还可看出，上述两个相容类不包含在其他任何相容类之中。因此，它们是最大相容类。

2) 化简方法——隐含表法

用隐含表法（也称相容法）化简不完全定义机状态表的过程与化简完全定义机状态表的过程大致相同，只是在最后构成最简状态表时有所不同。这点应予以注意。化简的具体步骤如下。

(1） 画隐含表，寻找相容状态对。隐含表的画法与完全定义机相同。画好隐含表后，逐一判别状态表中每对状态qi和qj的相容关系，判别结果有以下3种情况。

① 若qi和qj两个状态对应的输出（除随意项外）不相同，则表示这两个状态不相容，在隐含表的相应方格中标以“×”号。 

② 若qi和qj的输出（除随意项外）相同，且次态相同、交错，或者包含随意项，则表示这两个状态相容，在相应的方格内标以“√”号。

③ 若qi和qj的输出（除随意项外）相同，但次态尚不能直接确定是否相容，则表示这两个状态是否相容还待进一步考察，在对应的方格内填入其对应的不同次态对，这是其相容的条件。此时，利用隐含表继续追踪待定次态对。如果后续状态对相容或出现循环，则这些状态对都是相容的； 如果后续状态对出现不相容，则这些状态对都是不相容的。

(2） 画状态合并图，找最大相容类。

(3） 作最小化状态表。这一步的任务是要从上面求得的最大相容类（或相容类）中选出一组能覆盖原始状态表全部状态且个数最少的相容类，这一组相容类必须满足如下3个条件： 

① 覆盖性，即该组相容类应能覆盖原始状态表的全部状态。

② 最小性，即该组相容类的数目应为最小。 

③ 闭合性，即该组相容类中的任一个相容类，它在原始状态表中任一输入下产生的次态应该属于该组内的某一个相容类。

选出这组满足上述三条件的相容类后，每个相容类用一个状态符号表示。这样，由这组状态就可以构成最小化状态表。

下面举例说明不完全定义机状态表化简的方法。

【例5.8】化简图5.16（a）所示的原始状态表。


化简步骤如下。

① 画隐含表，找相容状态对。隐含表如图5.16(b)所示。由隐含表可得到相容状态对如下： 

（q1,q3 ），（q2，q6 ），（q3，q5），（q1，q5），（q2，q4），（q4，q6 ）

② 画合并图，找最大相容类。状态合并图如图5.16（c）所示。由状态合并图可得到相容类如下： 

(q1，q3，q5)，（q2，q4，q6 ）

③ 作最小化状态表。先作覆盖闭合表，如图5.16（d）所示。选择（q1，q3，q5）和（q2，q4，q6）这两个相容类，它们覆盖了原始状态表的全部状态； 而且每个相容类在任一输入下次态属于这两个相容类中某一个； 此外，这两个相容类不能再少了。因此，它们满足覆盖、闭合和最小3个条件。令q′1={q1，q3，q5}，q′2={q2，q4，q6}，作出最小优化状态表如图5.16(e)所示。

【例5.9】化简图5.17（a）所示的原始状态表。

化简步骤如下。

① 画隐含表，找相容状态对。隐含表如图5.17（b）所示。由隐含表可得相容状态对如下： 

（q1，q2），（q1，q3），（q1，q4），（q1，q5），（q2，q3），（q3，q4），（q4，q5）

② 画状态合并图，找最大相容类。状态合并图如图5.17（c）所示。由状态合并图可得到最大相容类如下： 

（q1，q2，q3），（q1，q3，q4），（q1，q4，q5）



图5.16不完全定义机状态表的化简方法示例1


③ 作最小状态表。先作覆盖闭合表，如图5.17（d）所示。这3个最大相容类满足覆盖闭合条件，但是否最小呢？由于状态q2仅属于（q1，q2，q3），状态q5仅属于（q1，q4，q5），而相容类（q1，q2，q3）和（q1，q4，q5）覆盖了原始状态表的全部状态。因此，可以考虑选择这两个相容类。但在进一步检查闭合性时，发现（q1，q4，q5）在输入x=0时次态为q3q4，它不属于所选的两个相容类中的任何一个。这说明选择相容类（q1，q2，q3）和（q1，q4，q5）不满足闭合性条件。如果选择相容类（q1，q2，q3）和（q4，q5），可以发现它是满足覆盖、闭合和最小这3个条件的，如图5.17（e）所示。这是唯一的一组解。令q′1={q1，q2，q3}，q′2={q4，q5}，作出最小化状态表如图5.17（f）所示。


这个例子说明，有时选用最大相容类不一定能取得最小化。究竟是选用相容类还是最大相容类，应视具体情况而定。





图5.17不完全定义机状态表的化简方法示例2



最后，在结束本小节讨论之前，还需指出两点： 

① 不完全定义机的状态表中，两状态的相容只对可应用输入序列有效，而不是对所有的输入序列都有效。这是由于不完全定义机状态表中状态的随意项引起的。所谓可应用输入序列是指： 以qi为初态，若某一输入序列中的每一个输入所建立的状态都是确定的，则该输入序列为状态qi的可应用输入序列。例如，在表5.22中，对于状态C，输入序列1000是可应用输入序列； 而对于输入序列1010是不可应用输入序列。这是因为

输入序列10001010

次态CB A B AC B A d

确定不确定

② 完全定义机可看作是不完全定义机的特例。换句话说，不完全定义机更具有一般性。因而，不完全定义机状态表的化简方法也适用于完全定义机，两者可统一成一种方法。

5.3.3状态分配

在求得时序电路的最简状态表后，下一个设计步骤就是进行状态分配。所谓状态分配，或称状态编码、状态赋值，就是给最简状态表中的每个符号状态指定一个二进制代码，形成二进制状态表。

状态分配的任务是要解决两个问题： 一是根据简化状态表给定的状态数，确定所需触发器的数目； 二是给每个状态指定二进制代码，以使所设计的电路最简单。

在实际工作中，设计人员主要还是凭经验，依据一定的原则，寻求接近最佳的状态分配方案。下面介绍一种状态分配的经验方法。

这里介绍的经验方法是基于如下思想： 在选择状态编码时，尽可能地使次态和输出函数在卡诺图上“1”的分布为相邻，以便形成较大的圈。这种方法主要根据以下三条相邻原则。

（1） 在相同输入条件下，次态相同，现态应相邻编码。所谓相邻编码，是指两个状态的二进制代码仅有一位不同。

（2） 在不同输入条件下，对于同一现态，次态应相邻编码。

（3） 输出完全相同，两个现态应相邻编码。

在以上三条原则中，第一条最重要，应优先考虑。下面举例说明上述原则的用法。

【例5.10】对表5.23所示的简化状态表进行状态分配。


表5.23简化状态表



y
x
01

q1q3,0q4,0
q2q3,0q1,0
q3q2,0q4,0
q4q1,1q2,1

状态表中共有4个状态q1、q2、q3和q4，其状态编码确定过程如下： 

根据原则（1），q1q2、q1q3应相邻编码； 

根据原则（2），q3q4、q1q3、q2q4、q1q2应相邻编码； 

根据原则（3），q1q2、q1q3、q2q3应相邻编码。

综合上述要求，q1q2、q1q3应给予相邻编码，因为这是三条原则都要求的。可以借用卡诺图，很易得到满足上述相邻要求的状态分配方案，如图5.18所示。其中，y1和y2表示触发器。因此，由图5.18可得状态编码为

q1=00，q2=01，q3=10，q4=11

将上述编码代入表5.23的简化状态表，就得到表5.24所示的二进制状态表，这就完成了状态分配。当然，上述分配方案不是唯一的。



图5.18状态分配方案



表5.24二进制状态表



y1 y2
x
01

0010,011,0
0110,000,0
1001,011,0
1100,101,1



必须指出，状态分配三条原则在大多数情况下是有效的，由它所得到的电路是比较简单的。但是，由于问题的复杂性，有时得到的结果并不令人满意，这是在实际使用中要注意的。还有一点要指出，对于同步时序电路来说，不同的状态分配方案并不影响网络工作的稳定性，仅影响网络的复杂程度。

5.3.4确定激励函数和输出函数

在完成状态分配以后，时序电路设计的下一步工作就是确定激励函数和输出函数，并据此可画出逻辑图。

由状态分配所得到的二进制状态表，反映了次态Y与x、y的关系，也反映了输出Z与x、y的关系。当触发器选定后，由于y和Y在二进制状态表中是已知的，根据触发器的激励表，就可以求出激励函数表达式。输出函数的表达式可直接从二进制状态表求得。

确定激励函数和输出函数的具体步骤如下。

（1） 将二进制状态表变换成YZ矩阵。
为了便于从二进制状态表求得函数的表达式，将这个表的变量取值按Gray码的顺序排列，这样就变换成了卡诺图的形式。把这种能反映函数Yi=fi (x,y)和Zi=gi (x,y)的卡诺图称为YZ矩阵。

例如，表5.24的二进制状态表变换成YZ矩阵如表5.25所示。


表5.25 YZ矩阵



y1 y2
x
01

0010,011,0
0110,000,0
1100,101,1
1001,011,0
（2） 由YZ矩阵变换成激励矩阵和输出矩阵。

YZ矩阵可看成由Y矩阵和Z矩阵两部分构成。Y矩阵给出每一现态yi的次态值Yi，而由现态yi向次态Yi的转换是依靠触发器的输入激励，这个激励可根据所选触发器的激励表来确定。把Y矩阵中的次态值Yi代之以相应触发器的激励值，就得到激励函数的卡诺图形式，这个卡诺图称为激励矩阵。由YZ矩阵的另一部分Z矩阵，直接可得输出矩阵。

例如，假定选RS触发器来实现表5.25的YZ矩阵，则它的激励矩阵和输出矩阵如表5.26和表5.27所示。


表5.26激励矩阵R1S1和R2S2



y1 y2
x
01

0001,d001,01
0101,10d0,10
1110,1010,0d
1010,010d,01


表5.27输出矩阵Z



y1 y2
x
01

0000
0100
1111
1000

（3） 由激励和输出矩阵，求激励函数和输出函数。

激励矩阵可以看成是各个输入激励填在同一个卡诺图上构成的。因此，在求各个激励函数时，只要分别画出各个输入激励的卡诺图，并由此写出各个激励函数的最简表达式。同理，由输出矩阵，可写出输出函数的最简表达式。

例如，由表5.26的激励矩阵R1S1和R2S2，可以分别画出R1、S1、R2、S2 4个卡诺图，并由此写出这4个激励函数的表达式。表中R1和S1是触发器y1的输入，R2和S2是触发器y2的输入。同理，由表5.27的输出矩阵，可写出输出函数的表达式。

将上述求激励函数和输出函数的过程简单表示如下： 

YZ矩阵Y 矩阵→激励矩阵→激励函数
↑
触发器激励表
Z矩阵 → 输出函数

下面举例说明确定激励函数和输出函数的方法。

【例5.11】完成5.3节例5.3“111”序列检测器的设计。

设计过程如下。

① 建立原始状态表。
该序列检测器的原始状态表如图5.11（b）所示。

② 状态化简。
该序列检测器的简化状态表如表5.17所示。

③ 状态分配。
简化状态表共有3个状态，所以需要用两位触发器y1和y2，根据状态分配的原则，一种较好的分配方案如图5.19所示。根据这种状态分配方案，A为00，B为01，C为10。于是，可得二进制状态表（即YZ矩阵），如表5.28所示。


图5.19状态分配方案




表5.28YZ矩阵Y1Y2Z



y1y2
x
01

0000,001,0
0100,010,0
11dd,ddd,d
1000,010,1


④ 求激励函数和输出函数。
若选用JK触发器作为存储元件，则根据JK触发器的激励表，可得到网络的激励矩阵如表5.29所示。


表5.29激励矩阵J1K1，J2K2



y1y2
x
01

000d,0d0d,1d
010d,d11d,d1
11dd,dddd,dd
10d1,0dd0,0d

分别画出各激励函数J1、K1、J2、K2和输出函数Z的卡诺图，如图5.20所示。由此可得激励函数和输出函数为

J1=xy2，K1= x-，J2=xy-1，K2=1，Z=xy1



图5.20卡诺图


⑤ 画逻辑图。
根据所求得的激励函数和输出函数，可画出“111”序列检测器的逻辑电路图，如图5.21所示。



图5.21“111”序列检测器逻辑图


5.3.5分析与设计举例

【例5.12】分析图5.22所示同步时序电路的逻辑功能。



图5.22同步时序电路


根据电路逻辑图，可写出激励函数和输出函数表达式为

J2=K2=xy1=xy-1+x-y1，J1=K1=1，Z=xy-2=x-+y2 

根据这些表达式，分别画出它们的卡诺图如图5.23所示。将J2、K2 、J1、K1的卡诺图合并画在一个卡诺图上，便得到网络的激励矩阵，如表5.30所示。


图5.23J、K、Z的卡诺图





表5.30激励矩阵J2K2、J1K1



y2y1
x
01

0000,1111,11
0111,1100,11
1111,1100,11
1000,1111,11

根据JK触发器的状态表将激励矩阵和输出Z矩阵变换成YZ矩阵，如表5.31所示。

表5.31YZ矩阵



y2y1
x
01

0001,111,0
0110,100,0
1100,110,1
1011,101,1

由YZ矩阵列状态表，画状态图。令编码00、01、10、11分别用状态q1、q2、q3、q4表示，代入YZ矩阵可得状态表，由此可给出状态图，如图5.24所示。



图5.24状态表和状态图


该电路是一个Mealy型时序机。由状态表和状态图可以看出，当输入x=0时，在时钟脉冲CP的作用下，电路的状态按加1顺序变化，即

00→01→10→11→00→…

当x=1时，在时钟脉冲CP的作用下，电路的状态按减1顺序变化，即

11→10→01→00→11→…

因此，该电路既具有加1计数功能，又具有减1计数功能，是一个二进制可逆计数器。

有时还需要用时间图来形象地描述电路的逻辑功能。时间图反映了时序电路在某一给定初态下，对给定输入序列的响应。下面介绍由状态图作时间图的方法。

假定计数器的初态y2y1为00（即q1），输入x的序列为0000011111，计数器在时钟脉冲CP控制下工作。先利用状态图作出时序电路的状态响应序列，而后再作时间图。状态响应序列如下： 

CP12345678910
x0000011111
y（Y）q1q2q3q4q1q2q1q4q3q2
Z1111100110

在CP1到来前，时序电路处于现态q1，当x=0时，由状态图可知，输出Z=1，次态为0（即CP1到来后的状态）。在CP2到来前，电路处于现态q2，当x=0，产生输出1，次态为q3。以此类推，可得到整个状态响应序列。然后，再根据状态响应序列作出时间图。由于状态y由y2y1来表示，所以只要将状态qi按二进制代码表示后，就可画出按电平高低的Y2、Y1时间图。例如，q2的代码为01，则在Y2、Y1的时间图中，Y2为低电平，Y1为高电平。图5.25表示该电路的时间图。



图5.25可逆计数器的时间图



【例5.13】分析图5.26所示同步时序电路。



图5.26同步时序电路


列出激励函数，求激励矩阵。激励函数为

D00=y-3，D01=y2·y-0=y-2+y0，D0=D00·D00
D1=y0，D2=y1，D3=y2

将4个状态变量y0～y3的16种组合代入上式，得激励矩阵如表5.32所示。注意，本例电路没有外部输入，也没有外部输出Z。


表5.32激励矩阵和状态表



y3y2y1y0D3D2D1D01D00Y3Y2Y1Y0
0000000110001
0001001110011
0010010110101
0011011110111
0100100011000
0101101111011
0110110011100
0111111111111
1000000100000
1001001100010
1010010100100
1011011100110
1100100001000
1101101101010
1110110001100
1111111101110

由激励矩阵和D触发器的激励表可得到y矩阵，即状态表，如表5.32右边一栏所示。

根据二进制状态表可作出状态图，如图5.27（a）所示。



图5.27状态图和时间图


由状态图可以看出，这是一个循环移位计数器。在计数时循环移位规则如下： 

y0→y1y1→y2y2→y3y-3→y0


这种计数器的循环长度l=2n，其中n为位数，这里n=4，l=8。

由状态图还可看出，图上半部8个状态形成闭环，称为“有效序列”； 下半部8个状态称为“无效序列”。如果该时序电路在某种偶然因素作用下，使电路处于“无效序列”中的某一状态，则它可以在时钟脉冲CP的作用下，经过若干CP后，将会自动进入有效序列。因此，该计数器称为具有自恢复功能的扭环移位计数器。

这种计数器在数字系统的控制电路中用得较多。图5.27（b）是它的时间图。根据Y0～Y3这4个基本波形，经过简单组合，可以形成各种不同的时序控制波形。

【例5.14】用T触发器设计一位数字的8421BCD码同步加1计数器。

设计步骤如下。

① 建立状态表。
由于计数器的工作状态很有规律，所以可以直接建立二进制状态表。这里，由于计数状态n=10，故需要4个触发器y1～y4，其状态表如表5.33所示。


表5.33激励矩阵和状态表



y1y2y3y4Y1Y2Y3Y4ZT1T2T3T4
0000000100001
0001001000011
0010001100001
0011010000111
0100010100001
0101011000011
0110011100001
0111100001111
1000100100001
1001000011001
1010ddddddddd
1011ddddddddd
1100ddddddddd
1101ddddddddd
1110ddddddddd
1111ddddddddd

② 求激励函数和输出函数。
根据状态表和T触发器的激励表，可得到网络的激励矩阵，如表5.33所示。分别画出激励函数T1～T4和输出函数Z的卡诺图如图5.28所示。由卡诺图化简，可得到网络的激励函数和输出函数为

T1=y1y4+y2y3y4，T2=y3y4，T3=y-1y4，T4=1，Z=y1y4



图5.28卡诺图


③ 画逻辑图。
根据上述激励函数和输出函数，可画出所要求的BCD码十进制计数器的逻辑图如图5.29所示。



图5.29BCD码十进制计数器逻辑图


对于未完全确定的6种状态（即1010～1111），可由上述激励函数表达式和T触发器的激励表，得到它们的状态转换图如图5.30所示。例如，状态“1010”为不完全确定状态，即y1=1，y2=0，y3=1，y4=0，将其代入激励函数表达式得： T1=T2=T3=0，T4=1，则状态“1010”在该激励下将转换到状态“1011”； 再由“1011”，求得T1=T2=T4=1，T3=0，则状态“1011”将转换到状态“0110”，从而进入计数循环中。其余4个不确定状态可按同理分析进入计数循环。



图5.30BCD码十进制计数器的状态转换图


由图5.30所示状态转换图可见，图中没有孤立状态。因而，所设计的图5.28所示的电路是能够自行恢复的。也就是说，不论电路处于何种初始状态，它都可以自动地进入计数循环中，而不会发生“挂起”现象。

5.4常用的同步时序电路

常用的同步时序电路有寄存器、计数器、节拍信号发生器等。其中，寄存器和计数器在计算机及其他数字系统中应用极为广泛，是数字系统的重要组成部分。

5.4.1寄存器

寄存器是由触发器组成的用来寄存二进制数码的逻辑部件，它是计算机中最基本的逻辑部件。通常，寄存器应具有以下4种功能： 

（1） 清除数码。将数码寄存器中所寄存的原始数据清除掉，在逻辑上只要将所有触发器的置“0”端连接在一起，作为置“0”信号的输入端。当需要清除数码时，可在置“0”输入端加一个置0脉冲，寄存器将全部处于“0”状态。

（2） 接收数码。在接收信号的作用下，将外部输入数据接收到寄存器中。

（3） 寄存数码。数码寄存器接收了数据代码后，只要不出现“清除”“接收”等信号，寄存器应保留原寄存数据不变。

（4） 输出数码。在输出控制信号作用下，控制数码寄存器中的数据输出。

有些寄存器还具有移位逻辑功能，称为移位寄存器。实现移位功能，只要将寄存器的每一位触发器输出连到下一位触发器的数码输入端即可。在CP脉冲作用下，寄存器中的数码在移位控制信号控制下左移或右移。

在实际应用中，往往要求寄存器同时具有接收、右移、左移、保持等多种逻辑功能，这种寄存器的逻辑图如图5.31所示。该电路具有4个并行数据输入端允许并行载入外部数据； 两个串行输入端，一个用于左移，一个用于右移； 串行输出可利用4个并行输出中的一个实现。图中，每位触发器的输入激励函数Di表达式为

Di=K右yi+1+K左yi-1+K接Si+K保yi

式中，K保=右·左·接。保持的作用就是将各触发器的数码送到本触发器中，也就是构成自身反馈Di=yi，达到保持原有数据不变的目的。



图5.31具有右移、左移、接收、保持功能的移位寄存器


利用移位寄存器不仅可以方便地实现串行数据到并行数据或并行数据到串行数据的转换，还可用作序列信号发生器。

5.4.2计数器

计数器是用来记录脉冲数目的数字电路，它也是数字设备中的基本逻辑部件。如计算机中用来记录指令执行顺序的指令计数器，用以记录乘除法步数的乘除计数器等。此外，计数器还常用来实现分频、定时等逻辑功能。

计数器的种类很多，按工作方式分，它可分为异步计数器和同步计数器； 按进位制分，可分为二进制计数器和非二进制计数器； 此外，按工作特点又可分为加1计数器、减1计数器、可逆计数器和环形移位计数器。以上各种计数器，有些在前面时序电路的分析和设计举例中已涉及。这里主要介绍一下同步计数器。

同步计数器的计数脉冲（即CP）同时加到各触发器的CP端，当计数脉冲到来时，各触发器同时改变状态。因此，同步计数器又称为并行计数器。同步计数器的总的延迟时间与计数器的位数无关，因而速度可以大大提高。

同步计数器的设计方法，可以按一般同步时序网络的设计方法进行。但由于计数器的状态转换很有规律，故可以直接建立二进制状态表（不必进行状态化简和状态分配）。然后，根据所用触发器的激励表，把二进制状态表（或YZ矩阵）变换成激励矩阵。最后，求出激励函数和输出函数，画出逻辑图。这样的方法前面已做了较充分的论述，下面主要介绍另外的同步计数器设计方法。

【例5.15】用T触发器设计一个模16同步加1计数器。


在一个多位二进制数的末位上加1时，根据二进制加法运算规则可知，若从低位到高位数第i位是第一个“0”位，即以下各位皆为“1”时，则第i位及以下各位应改变状态（由0变成1，由1变成0）； 第i位以上各位不变。而最低位的状态在每次加1时都要改变。例如



图5.32用T触发器构成的模16
同步加1计数器


1 0 1 0 1 1 1+ 11 0 1 1 0 0 0


用T触发器构成同步计数器，则每次CP信号（也就是计数脉冲）到达时应使该翻转的那些触发器输入控制端T=1，不该翻转的T=0。由此可知，当计数器用T触发器构成时，第i位触发器输入端的逻辑式应为

Ti=Qi-1·Qi-2·…·Q1·Q0
=∏i-1j=0Qj(i=1,2,…,n-1)

只有最低位例外，按照计数规则，每次输入计数脉冲时它都要翻转，故T0=1。因而有

T0=1T1=Q0T2=Q0Q1T3=Q0Q1Q2

图5.32所示电路就是按上式构成的4位二进制同步加法计数器。将上式代入T触发器的特性方程式得到电路的状态方程： 

Qn+10=0Qn+11=Q01+0Q1Qn+12=Q0Q12+Q0Q1Q2Qn+13=Q0Q1Q23+Q0Q1Q2Q3

电路的输出为： 

C=Q0Q1Q2Q3


根据上述状态方程和输出方程可求出电路的状态转换表如表5.34所示。利用第16个计数脉冲到达时C端电位的下降沿可作为向高位计数器电路进位的输出信号。


表5.34模16同步加1计数器的状态转换表



计 数 顺 序
电 路 状 态
Q3Q2Q1Q0等效十进制数进位输出C

0000000
1000110
2001020
3001130
4010040
5010150
6011060
7011170
8100080
9100190
101010100
111011110
121100120
131101130
141110140
151111151

图5.33给出了图5.32电路的时序图。由时序图上可以看出，若计数输入脉冲的频率为f0，则Q0、Q1、Q2和Q3端输出脉冲的频率将依次为12f0、14f0、18f0和116f0。针对计数器的这种分频功能，也把它称为分频器。



图5.33模16同步加1计数器的时序图


在同步计数器中，非模2i计数器和模2i计数器的设计方法是相同的，只是非模2i计数器需要检查不确定状态的自恢复性能，参见5.3节例5.14的BCD码十进制计数器。此外，同步计数器也可以设计成不按二进制码顺序计数，而按Gray码顺序计数，即每次计数只有一位触发器改变状态。其设计方法与前面相同，这里不再多述了，读者根据前面方法不难进行设计。

5.4.3节拍信号发生器

计算机在执行一条指令时，总是把一条指令分成若干基本动作，由控制器发出一系列节拍电位，每个节拍电位控制计算机完成一个或几个基本动作。节拍信号发生器就是用来产生节拍电位的逻辑部件。按其结构来分，节拍信号发生器可分为计数型和移位型两种。

1. 计数型节拍信号发生器

计数型节拍信号发生器由计数器和译码器构成。图5.34是一个能产生4个节拍电位的节拍信号发生器。输出电位为W0～W3，输出脉冲是m0～m3，它的工作波形如图5.35所示。



图5.34计数型节拍信号发生器




图5.35节拍信号发生器的波形图



2. 移位型节拍信号发生器

图5.36是一个能产生4个节拍电位的移位型节拍信号发生器。4个D触发器接成环形移位寄存器，输出直接取自触发器的输出端。假设寄存器初态y4y3y2y1=1000，在CP脉冲作用下，其状态转换图如图5.37（a）所示。这种循环状态是我们所希望的，称为“有效时序”。在有效时序下的时间波形图如图5.37（b）所示。



图5.36移位型节拍信号发生器




图5.374位环形移位寄存器的有效时序


但是，图5.36这种简单的环形移位寄存器并不能保证电路一定工作在有效序列。随着移位寄存器中的初始状态不同，将产生不同的状态转换。例如，初始状态为1100、1110、1010时，其状态图如图5.38（a）～（c）所示，它们都可以构成循环。显然，这是我们所不希望的，一般称为“无效时序”。当寄存器的初始状态为0000或1111时，其状态图如图5.38（d）所示，寄存器将始终在该状态“空转”，通常称为“空转时序”。一旦由于某种因素，电路进入无效时序或空转时序，则它就不能再回到有效序列了。



图5.384位环形移位寄存器的其他时序


怎样使环形移位寄存器只工作在一种有效时序下呢？一种办法是预置初值，即通过置0置1输入端，使寄存器预置成所需状态。但这种办法不能保证电路在受到某种干扰时，仍能工作在有效时序。另一种办法是加反馈逻辑，使电路具有自恢复能力，即当电路由于某种因素而进入无效序列时，能自动回到原有效序列。这是一种较好的办法。下面介绍采用反馈逻辑的设计方法。

反馈逻辑的加接方法有好多种，我们采用加在第一级激励输入端的方案，即断开图5.36中y1与D4的连接线，在D4端加一个反馈逻辑电路，这个反馈逻辑电路能使移位寄存器从无效时序或空转时序引导到有效时序中。其设计步骤如下。

（1） 列状态表。
状态表中先列出有效时序，其余状态的转换只要使寄存器的4位状态进入有效时序即可。其状态表如表5.35左边部分所示。


表5.35状态表和激励矩阵


有
效
时
序













y4y3y2y1Y4Y3Y2Y1D4D3D2D1
100001000100
010000100010
001000010001
000110001000
000010001000
001100010001
010100100010
011000110011
011100110011
100101000100
101001010101
101101010101
110001100110
110101100110
111001110111
111101110111


（2） 求激励函数。
由状态表可得激励矩阵，如表5.35右边部分所示。由此可求得激励函数为

D4=y-4y-3y-1，D3=y4，D2=y3，D1=y2


（3） 画逻辑图。
根据激励函数可画出具有“反馈逻辑”的4位移位寄存器逻辑图，如图5.39所示。



图5.39加“反馈逻辑”的4位环形移位寄存器


以上这种环形移位寄存器可以直接用作节拍电位信号发生器，只要从各触发器的输出端直接引出信号即可。但是，这种寄存器的状态利用率很低。一个n位环形移位寄存器可有2n个状态，却只用了其中n个状态，用以产生n个节拍信号。如果采用扭环形移位寄存器，当位数仍为n时，则可产生2n个节拍信号。

3. 序列信号发生器

在数字信号的传输和数字系统的测试中，有时需要用到一组特定的串行数字信号。通常把这种串行数字信号称为序列信号。产生序列信号的电路称为序列信号发生器。

序列信号发生器的构成方法有多种。一种比较简单、直观的方法是用计数器和数据选择器组成。例如，需要产生一个8位的序列信号00010111（时间顺序为自左而右），则可用一个八进制计数器和一个8选1数据选择器组成，如图5.40所示。其中八进制计数器取自74LS161（4位二进制计数器）的低3位。74LS152是8选1数据选择器。 



图5.40用计数器和数据选择器组成的序列信号发生器


在需要修改序列信号时，只要将该序列信号加到D0～D7即可实现，而不需对电路结构作任何更动。因此，使用这种电路既灵活又方便。

习题5

5.1已知时序网络的状态表如题表5.1所示，试作出它的状态图。


题表5.1



Y
Yn+1
x=0x=1Z
ACB0
BCD0
CDB0
DBA1

5.2设有如题表5.2所示的3个完全定义机的状态表，试求每一状态表等价的最简状态表。




题表5.2(a)



y
x
01

14,02,0
23,11,0
32,15,0
41,02,0
54,11,0



题表5.2(b)



y
x
01

18,07,1
23,05,0
32,01,0
45,18,0
58,04,1
65,13,0
71,18,0
84,06,1



题表5.2(c)



y
x1x2
00011110

12,03,02,11,0
25,03,02,14,1
31,02,03,14,1
43,04,01,12,0
53,03,03,15,0

5.3试求题表5.3中不完全定义机的最大相容类。


题表5.3



y
x1x2
00011110

1d,d5,11,d3,1
2d,d2,d5,16,1
36,0d,dd,d2,1
4d,1d,d3,0d,d
51,d5,06,dd,d
64,06,dd,dd,d

5.4试化简题表5.4所示的3个不完全定义机的状态表。


题表5.4(a)



y
x1x2
00011110

13,03,d4,d3,d
24,13,0d,d1,d
31,d1,1d,dd,d
42,dd,d3,d5,d
52,d5,d3,d4,d



题表5.4(b)



y
x
01

1d,04,d
21,15,1
3d,04,d
43,12,1
55,d1,d



题表5.4(c)



y
x
01

13,dd,d
2d,d6,0
34,15,d
46,1d,d
55,d1,d
64,17,1
72,03,0

5.5试用JK触发器设计一个“101”序列检测器。该同步时序网络有一根输入线x，一根输出线Z。对应于每个连续输入序列“101”的最后一个1，输出Z=1，其他情况下Z=0。例如： 

x010101101
Z000101001

5.6设有如题表5.6所示的Moore型时序机状态表，试用T触发器和与非门设计此时序电路。


题表5.6



y
x
01Z

q1q2q30
q2q1q41
q3q2q20
q4q1q41

5.7试分析题图5.7所示同步时序网络，作出它的状态表和状态图，并画出当输入x为0110101序列时网络的时间图。

5.8试分析题图5.8所示同步时序网络，作出它的状态表和状态图，画出当电平输入x为0110110序列时网络的时间图。



题图5.7




题图5.8



5.9试分析题图5.9所示同步时序网络，作出它的状态表和状态图。

5.10试分析题图5.10所示同步时序网络的逻辑功能，作出它的状态表和状态图，并画出当输入x的序列为1011101，初态y2y1=00时网络的时间图。




题图5.9




题图5.10



5.11试用JK触发器设计一个Gray码十进制计数器。

5.12试用T触发器设计一个模8二进制可逆同步计数器。设用外部输入x控制加1或减1，当x=0时减1； 当x=1时加1。


5.13设计一个具有下述特点的计数器。

（1） 计数器有两个控制输入C1和C2，C1用以控制计数器的模数，而C2用以控制计数器的加减。

（2）如C1=0，则计数器为模3计数； 如C1=1，则计数器为模4计数。

（3）如C2=0，则计数器为加1计数； 如C2=1，则计数器为减1计数。

5.14设有如题图5.14所示时序网络，试作出其状态表。



题图5.14


5.15设某一时序网络有一个输入x和一个输出Z。输入由5个符号组成，这些符号或为0或为1。当5个符号中恰有3个符号为1，两个符号为0，且前两个符号为11，则输出Z=1。试建立此网络的状态图和状态表。

5.16采用D触发器，实现题表5.16所示状态表的逻辑电路。


题表5.16



y
x
x1x2x3

AA,0B,0C,1
BB,0C,0D,0
CC,0D,0A,1
DD,0A,0B,1