时序逻辑电路的设计技巧

时序逻辑电路的设计是分析的逆过程，即要求设计者根据给出的具体逻辑功能，求出实现这一逻辑功能的逻辑电路。所得到的设计结果应力求最简，即电路所使用的触发器和门电路的数目及输入端数目最少，或集成电路数目、种类最少，且互相之间连线也较少。本节只讨论同步时序电路的设计。

一般时序电路的设计可按下列步骤进行：

1）根据逻辑问题的文字描述，建立原始状态表。进行这一步时，可借助原始状态图构成原始状态表。建立原始状态图的具体做法是：首先分析给定的逻辑功能，确定输入变量和输出变量，确定有多少种输入信息需要“记忆”，并对每一种需“记忆”的输入信息规定一种状态来表示；然后分别以上述状态为现态，考察在每一个可能的输入组合作用下，应转入哪个状态及相应的输出，便可求得符合题意的状态图。这一步得到的状态图和状态表是原始的，其中可能包含多余的状态。

2）采用状态化简方法，将原始状态表化为最简状态表。状态化简的规则是：若两个电路状态在相同输入下有相同的输出，并且转换到同一个次态去，则这两个状态为等价状态，可以将两者合并为一个状态，而不改变输入输出的关系。通过合并等价状态可以达到状态简化的目的。

3）在得到简化的状态图后，要对每一个状态指定1组二进制代码，这称为状态分配（或状态编码）。时序电路的状态是用触发器状态的不同组合来表示的，时序电路的状态分配就是给这些触发器指定状态，每个触发器的状态组合都是一组二进制代码。如果编码方案得当，设计结果可以很简单。一般选用的状态编码都遵循一定的规律，如自然二进制码、移存码、循环码等。编码方案确定后，根据简化的状态图，画出编码形式的状态图及状态表。

4）选定触发器类型。根据编码后的状态表及触发器的特性方程，求得电路的输出方程和各触发器的驱动方程。

5）根据驱动方程和输出方程画出所要求的逻辑图。

6）检查电路能否自启动，如不能自启动，则需采取措施加以解决。

建立原始状态表的方法可以先借助于原始状态图，画出原始状态图以后再列出原始状态表。至今尚没有一个系统的建立原始状态图的方法，目前仍多采用经验法。对于一个时序电路应该考虑包括几个状态，状态间如何进行转换以及怎样产生输出等内容。

画原始状态图的一般过程是：根据文字描述的设计要求，先假定一个初始状态，从初始状态开始，每加入一个输入，就可以确定一个次态（该次态可能是现态本身，也可以是另一个状态，或者是新增加的一个状态）和输出。这个过程一直到每个现态向其次态的转换都已经考虑，并且不再增加新的状态为止。

例3-12 试列出一个5进制的加1和加2计数器的状态表。

解：对于5进制计数器应有5个独立状态，用S₀～S₄分别表示十进制数的0～4。计数器既可加1计数，又可加2计数，故要设置控制信号x。设x=0时，做加1计数；x=1时，做加2计数。y为输出，表示计满5个脉冲。由此，可以直接画出如图3-60所示的状态图及如表3-14所示的状态表。

图3-60 例3-12的状态图

表3-14 例3-12的状态表

例3-13 设计一个串行数据检测器，该电路具有一个输入端x和一个输出端y。输入为一连串随机信号，当出现连续3个或3个以上的1时，输出为1，其它输入情况输出为0。例如：

输入序列：101100111011110

输出序列：000000001000110

解：设电路在没有输入1以前的初始状态为A，当第一次输入1时，电路由状态A转入状态B，输出0；连续输入两个1时，电路由状态B转入C，并输出0；第三个信号继续输入1时，电路由状态C转入D，并输出1；此后若电路继续输入1，电路仍停留在状态D，并输出1。当输入一个0时，不管当前电路处于何种状态，电路都将回到初始状态A，重新记录连续输入1的个数。

根据上面的分析可得检测器的原始状态图如图3-61所示和状态表如表3-15所示。

图3-61 例3-13的状态图

表3-15 例3-13的状态表

根据设计要求建立的原始状态表，可能会引入多余的状态。因此，在得到原始状态表后，下一步工作就是进行状态表的化简。消去原始状态表中的多余状态，尽量减少所需状态的数目，使实现它的电路最简单。状态表可分为两类，一种是完全定义机（或完全描述时序机）状态表；另一种是不完全定义机（或不完全描述时序机）状态表。两种状态表的化简方法有所不同，本节将分别介绍完全定义机和不完全定义机两类状态表化简的具体步骤。

（1）完全定义机状态表的化简

所谓完全定义机是指其状态表中的次态和输出都能完全确定。不完全定义机是指其状态表中的次态和输出不能完全确定，即存在不确定的次态和输出。不完全定义机在实际中会经常遇到。如基本RS触发器不允许同时输入0就是其中一例。有时，即使是完全定义机，往往在给其状态表的状态进行二进制编码时，也会使完全定义机变成不完全定义机。

在介绍完全定义机状态表化简方法之前，先引入等价的几个概念。

等价状态：设q_a和q_b是时序电路状态表的两个状态，如果从q_a和q_b开始，任何加到时序电路上的输入序列均产生相同的输出序列，则称状态q_a和q_b是等价状态或等价状态对，并记为（q_a，q_b）或｛q_a，q_b｝。等价状态可以合并。

等价状态的传递性：若状态q_a和q_b等价，状态q_b和q_c等价，则状态q_a和q_c也等价，记为（q_a，q_b），（q_b，q_c）→（q_a，q_c）。

等价类：彼此等价状态集合，称为等价类。如若有（q_a，q_b）和（q_b，q_c），则有等价类（q_a，q_b，q_c）。

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

根据上述定义，可以把两个状态合并为一个状态的条件归纳以下为两点：第一，在各种输入取值下，它们的输出完全相同；第二，在满足第一个条件的前提下，它们的次态满足两个次态完全相同、两个次态为其现态本身或交错、两个次态的某一后继状态可以合并、两个次态为状态对循环中的一个状态对的情况之一。

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

原始状态表化简的根本任务在于找出最大等价类，并且把每个最大等价类用一个状态来代替。下面介绍具体化简方法。

隐含表法，又称为表格法，它是一种有规律的方法。其基本思想是先对原始状态表中的所有状态都进行两两比较，找出等价对；然后利用等价状态的传递性，逐步得到等价类及最大等价类；最后建立最小化状态表具体步骤如下：

1）画隐含表。隐含表是一个直角边格数相等的三角形矩阵。设原始状态表中有n个状态q₁～q_n，在隐含表的垂直方向从上而下排列q₂，q₃，…，q_n；水平方向上自左向右排列q₁，q₂，…，q_n-1。简单地说，垂直方向“缺头”，水平方向“少尾”。隐含表中每一个小方格表示一个状态对。隐含表的格式如图3-62所示。

2）顺序比较。顺序比较隐含表中各状态之间的关系，并将比较结果填入小方格内。

如果两个状态的输出完全相同，次态也相同，或者为现态本身或交错，表示两个状态等价，则在隐含表相应小方格内打“√”。

图3-62 隐含表格式

如果两个状态的输出不同，表示这两个状态不等价，则在隐含表相应小方格内打“×”。

如果不能确定两个状态是否等价，需要进一步追踪比较，则在相应的小方格内填上两个状态的次态对。

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

4）找最大等价类，作最简状态表。关联比较后，根据等价状态的传递性，可确定最大等价类。每个最大等价类可以合并为一个状态，并用一个新符号表示。值得注意的是不与其它任何状态等价的单个状态也是一个最大等价类。

例3-14 化简表3-16所给出的原始状态表。

解：化简步骤如下：

1）画隐含表，如图3-63所示。

表3-16 例3-14的原始状态表

图3-63 例3-14的隐含表

2）顺序比较。需要注意，每个状态都要与其他状态比较一次，将每次比较的结果填入隐含表内。如A状态和D状态比较，在x=0和x=1时，它们的输出和次态均相同，因此A和D为等价状态对，在A和D交叉的方格上画“√”。再如，A状态和C状态比较时，发现在x=1时，输出不同，A和C不可能等价，故在方格中打上“×”。再如，比较A状态和B状态，在x=0和x=1时，它们的输出分别相同，且x=0时次态相同，x=1时次态分别为B和C，B和C是否等价还不知道，所以将B和C作为待比较的条件填入，依此类推，比较结果如图3-63所示。

3）关联比较，隐含表中考察状态对AB，若要AB等价，就需要BC等价。但隐含表中BC不等价，因此AB也不等价。同理，BD也不等价。

4）列最大等价类。由关联比较结果，可得最大等价类为（A，D），（B），（C）。

表3-17 例3-14的最简状态表

令Q₁=｛A，D｝，Q₂=｛B｝，Q₃=｛C｝，得最简状态表如表3-17所示。

（2）不完全定义机状态表的化简

不完全定义机状态表的化简是建立在状态相容的基础上的。为此先讨论相容的几个概念。

相容状态：设A和B是时序电路状态表中的两个状态，如果从A和B开始，任何加到时序电路上的有效输入序列均产生相同的输出序列（除不确定的那些位外），则A状态和B状态是相容的，记作（A，B）。相容状态可合并。值得注意的是，相容没有传递性。例如A状态和B状态相容，B状态和C状态相容，则A状态不一定和C状态相容。

相容类：所有状态之间都是两两相容的状态集合。

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

化简步骤如下：

1）画隐含表，找相容状态对。

2）画合并图，找最大相容类。其中合并图就是在圆周上均匀标上代表状态的点，点与点之间的连线表示两个状态之间的相容关系，而所有点之间都有连线的多边形就构成了一个最大相容类。

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

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

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

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

同时具有覆盖、最小、闭合3个条件的相容类集合，就组成了最简状态表。

例3-15 化简如表3-18所示的原始状态表。

解：化简步骤如下：

①画隐含表，找相容状态对。隐含表如图3-64所示。由隐含表可得相容类有

（q₁，q₂），（q₁，q₃），（q₁，q₄），（q₁，q₅），（q₂，q₃），（q₃，q₄），（q₄，q₅）

②画合并图，找最大相容类。(www.xing528.com)

表3-18 例3-15的原始状态表

图3-64 例3-15的隐含表

图3-65 例3-15的状态合并图

状态合并图如图3-65所示，由合并图可找出最大相容类有

（q₁，q₂，q₃），（q₁，q₃，q₄），（q₁，q₄，q₅）

③作最简状态表。根据所得的最大相容类和原始状态表作覆盖闭合表，如表3-19所示。

表3-19 例3-15的覆盖闭合表一

由覆盖表查得，选取相容类（q₁，q₂，q₃），（q₁，q₄，q₅）可满足覆盖性。再由闭合表查看是否满足闭合关系，在x=0时，相容类（q₁，q₄，q₅）的次态是q₃q₄，它既不是（q₁，q₄，q₅）的部分状态集合，也不属于（q₁，q₂，q₃）。可见选取两个相容类不满足闭合性，需要三个最大相容类，才能满足闭合关系。这样化简后的状态要包括三个状态。

但是，用相容类（q₄，q₅）代替最大相容类重新作出覆盖闭合表，如表3-20所列。从表中可以发现，当x=0时，相容类的次态为q₃，它是相容类（q₁，q₂，q₃）的状态。如果我们选择相容类（q₁，q₂，q₃）和（q₄，q₅），会发现它是满足覆盖、闭合和最小这三个条件的。这是唯一的一组解。重新作覆盖闭合表，如表3-21所示。

令Q₁=｛q₁，q₂，q₃｝，Q₂=｛q₄，q₅｝，作出最简状态表如表3-22所示。

表3-20 例3-15的覆盖闭合表二

表3-21 例3-15的覆盖闭合表三

（3）状态分配

所谓状态分配，就是给最简状态表中的每个符号所表示的状态，指定一个二进制代码，形成二进制状态表。一般情况下，采用不同的状态编码方案，所得到的输出方程和驱动方程不同，从而设计出来的电路复杂程度也不同。因此，状态分配的主要任务是：

表3-22 例3-15的最简状态表

1）据最简状态表给定的状态数，确定所需触发器的数目。

2）寻找一种最佳的或接近最佳的状态分配方案，使所设计的时序电路最简单。

如果最简状态表中的状态数是M，触发器的数目为n，则n和M的关系式应满足

2^n-1＜M≤2ⁿ （3-32）

当M＜2ⁿ时，从2ⁿ个状态中取M个状态的组合可以有多种不同的方案，而每个方案中M个状态的排列顺序又有许多种。

当状态数目较少时，我们可以研究各种可能的状态方案。例如当M=4时，只有三种非等价的状态分配，所以可以对所有分配方案进行比较，从中选取一种最佳方案。但当状态数目稍增大时，分配方案数会急剧增大，以致无法去研究所有可能的状态分配方案。例如，当M=5时，有140种不同的分配方案，而当M=9时，竟有高达一千多万种不同的分配方案。这种情况下，要想对全部状态分配方案进行比较，从中选出最佳方案，是十分困难的，同时也没有必要将所有的分配方案研究一遍。在实际工作中，常采用经验法，按一定的原则进行分配，来获得接近最佳的分配方案。

状态分配原则如下：

1）在相同输入条件下，次态相同，现态应给于相邻编码。

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

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

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

例3-16 对表3-23所示的最简状态表进行状态分配。

解：状态表中共有4个状态，故选用两个触发器Q₁和Q₀。

根据状态分配原则1）：AB，AC应相邻编码；

根据原则2）：CD，AC，BD，AB应相邻编码；

根据原则3）：AB，AC，BC应相邻编码。

综合上述要求，AB，AC应给予相邻编码，这是3条原则都要求的。用卡诺图表示上述相邻要求的状态分配方案，如图3-66所示。由该图可得状态编码为

A=00，B=01，C=10，D=11

将上述编码代入如表3-23所示的最简状态表，就得到表3-24所示的二进制状态表。当然，上述分配方案不是唯一的。

表3-23 例3-16状态表

图3-66 例3-16的状态分配方案

表3-24 例3-16的二进制状态表

（4）求驱动方程和输出方程

因为不同逻辑功能的触发器驱动方式不同，所以用不同类型触发器设计出的电路也不一样。为此，在设计具体的电路前必须选定触发器的类型。选择触发器类型时应考虑到器件的供应情况，并应力求减少系统中使用的触发器种类。具体步骤如下：

1）根据二进制状态表（或状态图）写出电路的次态方程和输出方程。

2）根据选定的触发器类型，将电路次态方程转换成与选定触发器特性方程相同的形式。

3）将转换后的电路次态方程与触发器特性方程比较，即可得驱动方程。

例3-17 设计一个自动售饮料机的逻辑电路，它的投币口每次只能投入一枚五角或一元的硬币。投入一元五角后机器自动给出一杯饮料；投入两元（两枚一元）后，在给出饮料的同时找回一枚五角的硬币。

解：设投币信号为输入逻辑变量。投入一枚一元硬币用A=1表示，未投入时A=0；投入一枚五角硬币用B=1表示，未投入时B=0。给出饮料和找钱为两个输出变量，分别以Y、Z表示。给出饮料时Y=1，不给时Y=0；找回一枚五角硬币时Z=1，不找时Z=0。

假定通过传感器产生的投币信号（A=1或B=1）在电路转入新状态的同时也随之消失，否则将被误认作又一次投币信号。

图3-67 例3-17的逻辑电路状态图

设未投币前电路的初始状态为S₀，投入五角硬币以后状态为S₁，投入一元硬币（包括投入一枚一元硬币和投入两枚五角硬币的情况）以后状态为S₂。S₂状态下再投入一枚五角硬币后电路返回S₀，同时输出为Y=1，Z=0；如果投入的是一枚一元硬币，则电路也应该返回S₀，同时输出为Y=1，Z=1。因此，电路的状态数M=3已足够。根据以上分析，可得自动售饮料机的逻辑电路的状态如图3-67所示。

根据状态图可得表3-25所列的状态表。因为正常工作中不会出现AB=11的情况，所以此情况下的次态和输出均作无关项处理。又因该状态表已为最简形式，所以不必再进行化简过程。

由于状态表中有3个状态，取触发器的位数n=2，即Q₁和Q₀就满足要求。令Q₁Q₀的00、01、10分别代表S₀、S₁、S₂，Q₁Q₀=11作为无关状态，则从状态图和状态表即可画出表示电路次态/输出（Q^∗₁Q^∗₀/YZ）的卡诺图，如图3-68所示。

表3-25 例3-17的状态表

图3-68 例3-17电路次态/输出的卡诺图

将图3-67中的卡诺图分解，分别画出表示Q^∗₁、Q^∗_0、Y和Z的卡诺图，如图3-69所示。

图3-69 例3-17卡诺图的分解

若电路选用D触发器，则根据如图3-69所示的卡诺图可写出电路的状态方程、驱动方程和输出方程分别为：

根据驱动方程和输出方程可得如图3-70所示的逻辑图，该逻辑图的实际状态图如图3-71所示。

从图3-71可看出，当电路进入无效状态11后，在无输入信号的情况下（即AB=00）不能自行返回有效循环，所以该电路不能自启动。当AB=01或AB=10时，电路在时钟信号作用下虽然能返回到有效循环中去，但收费结果是错误的。因此，在开始工作时，应在异步置零端上加入低电平信号，将电路置为00状态。

图3-70 例3-17逻辑图

图3-71 例3-17的实际状态图