时序逻辑电路的设计方法ppt课件

1、同步时序电路设计根底 同步时序逻辑电路的设计过程就是分析的逆过程，同步时序逻辑电路的设计过程就是分析的逆过程，也就是根据特定的逻辑要求，设计出能实现其逻辑也就是根据特定的逻辑要求，设计出能实现其逻辑功能的时序逻辑电路。设计追求的目的是运用尽能功能的时序逻辑电路。设计追求的目的是运用尽能够少的触发器和逻辑门实现给定的逻辑要求。够少的触发器和逻辑门实现给定的逻辑要求。 同步时序电路设计的普通步骤如下同步时序电路设计的普通步骤如下: (1) 建立原始形状表。建立原始形状表。 根据对时序电路的普通文字描画阐明电路的输根据对时序电路的普通文字描画阐明电路的输入、输出及形状的关系，进而构成形状图和形状表。

2、入、输出及形状的关系，进而构成形状图和形状表。由于开场得到的形状图和形状表是对逻辑问题最原由于开场得到的形状图和形状表是对逻辑问题最原始的笼统，其中能够包含多余的形状，所以称为原始的笼统，其中能够包含多余的形状，所以称为原始形状图和原始形状表。始形状图和原始形状表。(2) 形状化简。形状化简。 对原始形状表进展形状化简，消去多余的形状，对原始形状表进展形状化简，消去多余的形状，求得最小化形状表。求得最小化形状表。(3) 形状分配形状分配(或称形状编码或称形状编码)。 把形状表中用字母或数字标注的每个形状用二把形状表中用字母或数字标注的每个形状用二进制代码表示。进制代码表示。(4) 选择触发器类

3、型选择触发器类型(如如D或或JK触发器触发器)。 通常在开场设计时，曾经初步选择了触发器。通常在开场设计时，曾经初步选择了触发器。这一步是最后确定适宜的触发器的类型。同一形这一步是最后确定适宜的触发器的类型。同一形状表选用不同类型的触发器，得到的电路复杂程状表选用不同类型的触发器，得到的电路复杂程度也不同。度也不同。(5) 确定鼓励函数和输出函数表达式。确定鼓励函数和输出函数表达式。 根据选定的触发器类型，列出鼓励函数表，并根据选定的触发器类型，列出鼓励函数表，并求出鼓励函数和输出函数的最简表达式。求出鼓励函数和输出函数的最简表达式。(6) 画出逻辑电路图。画出逻辑电路图。 上述各步骤中，第一

4、步是最重要的。这一步要完成从文字描画到逻辑符号的转换，一旦完成了这步转换，下面的步骤就可以用较为完善的设计方法进展设计。 以上是普通同步时序电路的设计步骤。对于一些典型的或选用MSI芯片的电路设计，由于形状数、形状编码和触发器类型已给定，设计步骤可以简化。实践设计中可以根据详细问题灵敏掌握。同步时序电路设计步骤建立原始形状表 建立原始形状表是同步时序电路设计中最重要的一建立原始形状表是同步时序电路设计中最重要的一步。普通应思索如下几个方面：步。普通应思索如下几个方面： 1.确定电路模型。确定电路模型。 同步时序电路有同步时序电路有Mealy型和型和Moore型两种模型，型两种模型，不同模型构造

5、对应的电路构造不同。不同模型构造对应的电路构造不同。 2.设立初始形状。设立初始形状。 时序逻辑电路在输入信号开场作用之前的形状时序逻辑电路在输入信号开场作用之前的形状称为初始形状。称为初始形状。 3.根据需求记忆的信息添加新的形状。根据需求记忆的信息添加新的形状。 从初始形状出发，逐个添加和完善，直到每个形从初始形状出发，逐个添加和完善，直到每个形状下各种输入取值均已思索而没有新的形状出现为状下各种输入取值均已思索而没有新的形状出现为止。止。 4.确定各时辰电路的输出。确定各时辰电路的输出。例例1 1 例例1. 1. 某模某模5 5加加1 1和加和加2 2计数器有一个输入计数器有一个输入x

6、x和一个输出和一个输出Z Z。输入。输入x x为加为加1 1、加、加2 2控制信控制信号，当号，当x=0 x=0时，计数器在时钟脉冲作用下时，计数器在时钟脉冲作用下进展加进展加1 1计数；当计数；当x=1x=1时，计数器在时钟时，计数器在时钟脉冲作用下进展加脉冲作用下进展加2 2计数。当电路计满计数。当电路计满5 5个形状后，输出个形状后，输出Z Z产生一个产生一个1 1信号作为进信号作为进位输出，平常位输出，平常Z Z输出为输出为0 0。试建立该计数。试建立该计数器的器的MealyMealy型原始形状图和形状表。型原始形状图和形状表。 解解: : 该问题已指定电路模型为该问题已指定电路模型为

7、MealyMealy型，型，且输入和形状、输出之间的关系也非常且输入和形状、输出之间的关系也非常清楚，所以形状图的建立很容易。清楚，所以形状图的建立很容易。 假设模假设模5 5计数器的计数器的5 5个形状分别用个形状分别用A A、B B、C C、D D、E E表示，其中表示，其中A A为初始形状。根据题意为初始形状。根据题意可作出原始形状图如右图所示，相应的可作出原始形状图如右图所示，相应的原始形状表如右表所示。原始形状表如右表所示。 输入输入状态状态X=0 X=1AB/0C/0BC/0D/0CD/0E/0DE/0A/1EA/1B/0例例2 2例例2. 2. 某序列检测器有一个输入端某序列检测

8、器有一个输入端x x和一个输出端和一个输出端Z Z。输入端。输入端x x输入一串随机的二进制代码，当输入序列中出现输入一串随机的二进制代码，当输入序列中出现011011时，时，输出输出Z Z产生一个产生一个1 1输出，平常输出，平常Z Z输出输出0 0。典型输入、输出序列。典型输入、输出序列如下。如下。 输入输入x x： l 0 1 0 1 1 1 0 0 1 1 l 0 1 0 1 1 1 0 0 1 1 0 0 输出输出Z Z：0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 01 0 试作出该序列检测器的原始形状图和原始形状表。试作出该序列检测器的原始形

9、状图和原始形状表。 解解 假定用假定用MealyMealy型同步时序逻辑电路实现该序列检测器型同步时序逻辑电路实现该序列检测器的逻辑功能，那么原始形状图的建立过程如下。的逻辑功能，那么原始形状图的建立过程如下。 设电路的初始形状为设电路的初始形状为A A。当处在初始形状下电路输入为。当处在初始形状下电路输入为0 0时，输出时，输出Z Z为为0 0，由于输入，由于输入0 0是序列是序列011011中的第一个信号，中的第一个信号，所以应该用一个形状将它记住，假定用形状所以应该用一个形状将它记住，假定用形状B B记住收到了第记住收到了第一个一个0 0，那么在形状，那么在形状A A输入输入0 0时应转

10、向形状时应转向形状B B；当处在初始形；当处在初始形状状A A电路输入为电路输入为1 1时，输出时，输出Z Z为为0 0，由于输入，由于输入1 1不是序列不是序列011011的第一个信号，故不需求记住，可令其停留在形状的第一个信号，故不需求记住，可令其停留在形状A A。该转。该转换关系如图换关系如图(a)(a)所示。所示。 当电路处于形状当电路处于形状B时，假设输入时，假设输入x为为0，那么它不是序列，那么它不是序列“011的第二的第二个信号，但仍可作为序列中的第一个信号，但仍可作为序列中的第一个信号，故可令电路输出为个信号，故可令电路输出为0，停，停留在形状留在形状B；假设输入；假设输入x为

11、为1，那么，那么意味着收到了序列意味着收到了序列“011的前面两的前面两位位01，可用一个新的形状，可用一个新的形状C将它记将它记住，故此时电路输出为住，故此时电路输出为0，转向形，转向形状状C。部分形状图如图。部分形状图如图(b)所示。所示。 当电路处于形状当电路处于形状C时，假设输入时，假设输入x为为0，那么收到的延续，那么收到的延续3位代码为位代码为010，不是关怀的序列不是关怀的序列011，但此时输入，但此时输入的的0依然可以作为序列的第一个信依然可以作为序列的第一个信号，故此时应输出号，故此时应输出0，转向形状，转向形状B；假设输入假设输入x为为1，那么表示收到了序，那么表示收到了序

12、列列011，可用一个新的形状，可用一个新的形状D记住，记住，此时应输出此时应输出1，转向形状，转向形状D。部分形。部分形状图如图状图如图(c)所示。所示。当电路处于形状当电路处于形状D时，假设输入时，假设输入x为为0，那么应输出那么应输出0，转向形状，转向形状B；假设输入；假设输入x为为l，那么应输出那么应输出0，转向形状，转向形状A。至此，得到。至此，得到了该序列检测器完好的了该序列检测器完好的Mealy型形状图，型形状图，如图如图(d)所示。相应的原始形状表如右所所示。相应的原始形状表如右所示。示。 从上述建立原始形状图的过程可知，实从上述建立原始形状图的过程可知，实现一个序列检测器的功能

13、所需求的形状数现一个序列检测器的功能所需求的形状数与要识别的序列长度相关，序列越长，需与要识别的序列长度相关，序列越长，需求记忆的代码位数越多，形状数也就越多。求记忆的代码位数越多，形状数也就越多。实践上在建立序列检测器的原始形状图时，实践上在建立序列检测器的原始形状图时，可以先根据序列中要记忆的信息设立好每可以先根据序列中要记忆的信息设立好每一个形状，并建立起当输入信号正好按指一个形状，并建立起当输入信号正好按指定序列变化时各形状的相互关系；然后再定序列变化时各形状的相互关系；然后再确定每个形状下输入出现不同取值时的输确定每个形状下输入出现不同取值时的输出和形状转移方向，即可得到一个完好的出

14、和形状转移方向，即可得到一个完好的形状图。形状图。 输入输入状态状态X=0 X=1AB/0 A/0BB/0 C/0CB/0 D/1DB/0 A/0例例3 3例例3.3.假设用假设用MooreMoore型同步时序电路实现上例型同步时序电路实现上例“011011序列检测器，那么电路输出完全取决序列检测器，那么电路输出完全取决于形状，而与输入无直接关系。在作形状图于形状，而与输入无直接关系。在作形状图时，应将输出标志在代表各形状的圆圈内。时，应将输出标志在代表各形状的圆圈内。 假定电路初始形状为假定电路初始形状为A A，并用形状，并用形状B B、C C、D D分别表示收到了输入分别表示收到了输入X

15、X送来的送来的0 0、0101、011011。显然，根据题意，仅当处于形状显然，根据题意，仅当处于形状D D时电路输出时电路输出为为1 1，其他形状下输出均为，其他形状下输出均为0 0。当形状从初始。当形状从初始开场，输入端开场，输入端X X正好依次输入正好依次输入0 0、1 1、1 1时，那时，那么形状从么形状从A A转到转到B B、B B转到转到C C、C C转到转到D D。据此可。据此可得到部分形状图如右图得到部分形状图如右图(a)(a)所示。然后，思索所示。然后，思索到到A A形状下输入为形状下输入为1 1时，它不是指定序列中的时，它不是指定序列中的第一位信号，不用记忆，可令形状停留在

16、第一位信号，不用记忆，可令形状停留在A A；B B形状下输入为形状下输入为0 0时，它不是指定序列的第二时，它不是指定序列的第二位，但可作为指定序列的第一位，故可令其位，但可作为指定序列的第一位，故可令其停留在停留在B B；C C形状下输入为形状下输入为0 0时，不是指定序列时，不是指定序列的第三位的第三位, ,但同样可作为第一位但同样可作为第一位, ,故令其转向故令其转向形状形状B B；D D形状下输入形状下输入0 0时，同样应转向时，同样应转向B B，而，而输入为输入为1 1时，那么应令其进入形状时，那么应令其进入形状A A。得到完。得到完好的好的MooreMoore型原始形状图如右图型原

17、始形状图如右图(b)(b)所示。所示。1000Z输出输出ABDDBCCBBABAX=1X=0现态现态次态次态例例4 例例4. 某同步时序电路用于检测串行输入的某同步时序电路用于检测串行输入的8421码，其输入的码，其输入的顺序是先低位后高位，当出现非法数字顺序是先低位后高位，当出现非法数字(即输入即输入1010，1011，1100，1101，1110，1111)时，电路的输出为时，电路的输出为1。试作出该时序。试作出该时序电路的电路的Mealy型模型形状图和形状表。型模型形状图和形状表。 解：根据题意，电路有一个输入和一个输出。设输入解：根据题意，电路有一个输入和一个输出。设输入x用来接用来接

18、纳纳8421码，输出码，输出Z用来指示在输入端出现了非法数字。用来指示在输入端出现了非法数字。 假定起始形状为假定起始形状为A，当第一位输入代码到来时，有两，当第一位输入代码到来时，有两种能够的情况，即种能够的情况，即1和和0，故需用两个形状，故需用两个形状B和和C来表示这两种来表示这两种能够；从形状能够；从形状B和和C出发，当出发，当x输入的第二位代码到来时，又输入的第二位代码到来时，又各有两种能够的情况，分别用形状各有两种能够的情况，分别用形状D，E，F，G表示；从形表示；从形状状D，E，F，G出发，当出发，当x输入的第三位代码到来时，同样，输入的第三位代码到来时，同样，各有两种能够，共有

19、各有两种能够，共有8种不同的情况，分别用形状种不同的情况，分别用形状H，I，J，K，L，M，N，P表示。当表示。当x输入的第四位代码到来时，即一输入的第四位代码到来时，即一组组8421码全部被接纳。对输入的码全部被接纳。对输入的8421码进展判别，假设出现码进展判别，假设出现非法数字，电路的输出为非法数字，电路的输出为1，否那么为，否那么为0，并前往到起始形状，并前往到起始形状A。根据以上分析，可以得到如下的形状图：。根据以上分析，可以得到如下的形状图： 从形状图可以看出，由于串行输入是先低位后高位，从形状图可以看出，由于串行输入是先低位后高位，因此，判别输入的因此，判别输入的8421码能否为

20、非法数字时，应从码能否为非法数字时，应从低位到高位查看各位输入值。待低位到高位查看各位输入值。待4位代码检测完后，位代码检测完后，那么应转向初始形状那么应转向初始形状A，以便检查下一组代码。，以便检查下一组代码。ABDCEFGHIJKLMNP0/01/00/00/00/00/00/00/00/00/00/00/00/00/00/00/01/01/01/01/01/01/01/01/01/11/11/11/11/11/1 将形状图转换成形状表，那么如下表所示：将形状图转换成形状表，那么如下表所示：现态现态 次态次态/输出输出 现态现态 次态次态/输出输出 x=0 x=1 x=0 x=1 A B/

21、0 C/0 B D/0 E/0 I A/0 A/1 C F/0 G/0 J A/0 A/1 D H/0 I/0 K A/0 A/1 E J/0 K/0 L A/0 A/0 F L/0 M/0 M A/0 A/1 G N/0 P/0 N A/0 A/1 H A/0 A/0 P A/0 A/1 上述各例所建立的原始形状图和原始形状表上述各例所建立的原始形状图和原始形状表中，对于所设立的每一个形状，在不同输入取值中，对于所设立的每一个形状，在不同输入取值下都有确定的次态和输出。通常将这类形状图和下都有确定的次态和输出。通常将这类形状图和形状表称为完全确定形状图和形状表，由它们所形状表称为完全确定形状

22、图和形状表，由它们所描画的电路称为完全确定电路。实践运用中，根描画的电路称为完全确定电路。实践运用中，根据某些设计要求建立的原始形状图和原始形状表据某些设计要求建立的原始形状图和原始形状表中往往存在不确定的次态或输出，即存在某些形中往往存在不确定的次态或输出，即存在某些形状，它们在某些输入取值下的次态或输出是随意状，它们在某些输入取值下的次态或输出是随意的。这种形状图和形状表被称为不完全确定形状的。这种形状图和形状表被称为不完全确定形状图和形状表，所描画的电路称为不完全确定电路。图和形状表，所描画的电路称为不完全确定电路。例例5 5 例例5. 5. 设计一个用于引爆控制的同步时序电路，该电设计

23、一个用于引爆控制的同步时序电路，该电路有一个输入端路有一个输入端x x和一个输出端和一个输出端Z Z。平常输入。平常输入x x一直为一直为0 0，一旦需求引爆，那么从，一旦需求引爆，那么从x x延续输入延续输入4 4个个1 1信号信号( (不被不被0 0延续延续) )，电路收到第四个，电路收到第四个1 1后在输出端后在输出端Z Z产生一个产生一个1 1信信号点火引爆，该电路连同引爆安装一同被炸毁。试号点火引爆，该电路连同引爆安装一同被炸毁。试建立该电路的建立该电路的MealyMealy型形状图和形状表。型形状图和形状表。 解解: : 该电路实践上是一个用于特殊场所的该电路实践上是一个用于特殊场

24、所的“11111111序列检测器。它与普通序列检测器有两点不同。序列检测器。它与普通序列检测器有两点不同。一是输入带有约束条件，即一旦输入出现一是输入带有约束条件，即一旦输入出现1 1，那么一，那么一定是不被定是不被0 0延续的延续延续的延续4 4个个l l；二是收到；二是收到4 4个个1 1后产生的后产生的引爆信号，同时使电路自毁，故此时不再存在次态引爆信号，同时使电路自毁，故此时不再存在次态问题。问题。 设形状设形状A表示电路初始形状，形状表示电路初始形状，形状B表示收到了表示收到了第一个第一个1输入，形状输入，形状C表示收到了延续表示收到了延续2个个1输入，形输入，形状状D表示收到了延续

25、表示收到了延续3个个1输入。根据题意，输入。根据题意，A形状下形状下x为为1时，输出为时，输出为0转向形状转向形状B；B形状下形状下x为为1时，输出时，输出为为0转向形状转向形状C；C形状下形状下x为为1时，输出为时，输出为0转向形状转向形状D；而；而D形状下形状下x为为1时，输出为时，输出为1，次态随意，次态随意(实践上实践上已不存在次态已不存在次态)。其次，。其次，A形状下形状下x为为0时，可令输出时，可令输出为为0，停留在形状，停留在形状A，而，而B、C、D这这3个形状下由于个形状下由于x不会为不会为0，故可令输出和次态作为无关处置。据此，故可令输出和次态作为无关处置。据此，可得到该电路

26、的可得到该电路的Mealy型原始形状图如以下图所示，型原始形状图如以下图所示，原始形状表如下表所示。图表中用原始形状表如下表所示。图表中用“d表示不确定表示不确定次态或不确定输出。次态或不确定输出。 在时序电路设计中，利用不完全确定形状表中不在时序电路设计中，利用不完全确定形状表中不确定次态和不确定输出的随意性，通常可使设计确定次态和不确定输出的随意性，通常可使设计方案变得更简单。这一点和组合电路设计中利用方案变得更简单。这一点和组合电路设计中利用函数包含的无关最小项简化电路构造是类似的，函数包含的无关最小项简化电路构造是类似的，只不过在处置上要复杂一些。只不过在处置上要复杂一些。 输入输入状

27、态状态X=0 X=1AA/0B/0Bd/dC/0Cd/dD/0Dd/dd/1形状化简形状化简 在建立原始形状图和原始形状表时，主要思索的是如何明晰、在建立原始形状图和原始形状表时，主要思索的是如何明晰、正确地反映设计要求，而没有刻意追求如何使图、表中包含正确地反映设计要求，而没有刻意追求如何使图、表中包含的形状数目到达最少。因此，在构造的形状图和形状表中往的形状数目到达最少。因此，在构造的形状图和形状表中往往存在多余形状。但在设计详细电路时，形状数目的多少将往存在多余形状。但在设计详细电路时，形状数目的多少将直接决议电路中所需触发器数目的多少。所以，为了降低电直接决议电路中所需触发器数目的多少

28、。所以，为了降低电路的复杂性和电路本钱，应尽能够地使描画设计要求的形状路的复杂性和电路本钱，应尽能够地使描画设计要求的形状表中包含的形状数到达最少。表中包含的形状数到达最少。 所谓形状化简，就是采用某种化简技术从原始形状表中消去所谓形状化简，就是采用某种化简技术从原始形状表中消去多余形状，得到一个既能正确地描画给定的逻辑功能，又能多余形状，得到一个既能正确地描画给定的逻辑功能，又能使所包含的形状数目到达最少的形状表，通常称这种形状表使所包含的形状数目到达最少的形状表，通常称这种形状表为最小化形状表。为最小化形状表。 形状化简的方法很多，最常用的一种方法是隐含表法。在利形状化简的方法很多，最常用

29、的一种方法是隐含表法。在利用隐含表进展化简时，对于完全给定原始形状表和不完全给用隐含表进展化简时，对于完全给定原始形状表和不完全给定原始形状表援用了不同的概念，并且处置过程有所不同。定原始形状表援用了不同的概念，并且处置过程有所不同。下面分别进展讨论。下面分别进展讨论。1完全确定形状表的化简完全确定形状表的化简完全确定形状表的化简是建立在形状等效这个概念的完全确定形状表的化简是建立在形状等效这个概念的根底之上的。为此，在讨论化简方法之前，先引见化根底之上的。为此，在讨论化简方法之前，先引见化简时涉及的几个概念。简时涉及的几个概念。(1)等效形状和等效类等效形状和等效类等效形状：假设形状等效形状

30、：假设形状Si和和Sj是完全确定形状表中的是完全确定形状表中的两个形状，假设对于一切能够的输入序列，分别从两个形状，假设对于一切能够的输入序列，分别从Si和和Sj出发，所得到的输出呼应序列完全一样，那么形出发，所得到的输出呼应序列完全一样，那么形状状Si和和Sj是等效的，记作是等效的，记作(Si，Sj)，或者说，形状，或者说，形状Si和和Sj是等效对。是等效对。 这里所说的一切能够的输入序列，是指输入序列这里所说的一切能够的输入序列，是指输入序列的长度和构造是恣意的，它包含无穷多位，且有无穷的长度和构造是恣意的，它包含无穷多位，且有无穷多种组合。假设企图经过检测一切能够输入序列下的多种组合。假

31、设企图经过检测一切能够输入序列下的输出来确定两个形状能否等效，显然是不现实的。现输出来确定两个形状能否等效，显然是不现实的。现实上，由于在构成原始形状表时，对每个形状均思索实上，由于在构成原始形状表时，对每个形状均思索了在一位输入各种取值下的次态和输出，因此，从整了在一位输入各种取值下的次态和输出，因此，从整体上讲，原始形状表曾经反映了各形状在恣意输入序体上讲，原始形状表曾经反映了各形状在恣意输入序列下的输出。从而，可以根据形状表上所列出的一位列下的输出。从而，可以根据形状表上所列出的一位输入各种组合下的次态和输出来判别某两个形状能否输入各种组合下的次态和输出来判别某两个形状能否等等效。假定效

32、。假定Si和和Sj是完全确定的原始形状表中的两个是完全确定的原始形状表中的两个现态，那么现态，那么Si和和Sj等效的条件可归纳为在一位输入等效的条件可归纳为在一位输入的各种取值组合下满足如下两条。的各种取值组合下满足如下两条。 第一，它们的输出一样。第一，它们的输出一样。 第二，它们的次态属于以下情况之一：第二，它们的次态属于以下情况之一： a次态一样；次态一样； b次态交错或为各自的现态；次态交错或为各自的现态； c次态循环或为等效对。次态循环或为等效对。 这里，情况这里，情况b中所谓的次态交错，是指在某种输中所谓的次态交错，是指在某种输入取值下，入取值下，Si的次态为的次态为Sj，而，而S

33、j的次态为的次态为Si。而所。而所谓次态为各自的现态，即谓次态为各自的现态，即Si的次态仍为的次态仍为Si，Sj的次的次态仍为态仍为Sj。情况。情况c中的次态循环是指确定两个形状中的次态循环是指确定两个形状能否等效的关联形状对之间，其依赖关系构成闭环。能否等效的关联形状对之间，其依赖关系构成闭环。而两个次态为形状对循环体中的一个形状对。而两个次态为形状对循环体中的一个形状对。 例如，例如，S1和和S2在某种输入取值下的次态是在某种输入取值下的次态是S3和和S4，而，而S3和和S4在该种输入取值下的次态又是在该种输入取值下的次态又是S1和和S2，那么称这种情况，那么称这种情况为次态循环。而次态为

34、等效对是指为次态循环。而次态为等效对是指Si和和Sj的次态已被确以的次态已被确以为等效形状。例如，为等效形状。例如，S1的次态是的次态是S3，S2的次态是的次态是S4，虽然，虽然S3和和S4既不一样，也不交错或循环，但假设以既不一样，也不交错或循环，但假设以S3和和S4作为作为现态，在一位输入的各种取值下，其输出一样且次态一样现态，在一位输入的各种取值下，其输出一样且次态一样或交错或循环，即或交错或循环，即S3和和S4等效，那么，等效，那么，S1和和S2是等效的。是等效的。 等效形状具有传送性。即假设等效形状具有传送性。即假设S1和和S2等效，等效，S2和和S3等效，那么，一定有等效，那么，一

35、定有S1和和S3等效。记作等效。记作 (S1，S2)，(S2，S3)(S1，S3) 等效类：所谓等效类是指由假设干彼此等效的形状构成等效类：所谓等效类是指由假设干彼此等效的形状构成的集合。在一个等效类中的恣意两个形状都是等效的。根的集合。在一个等效类中的恣意两个形状都是等效的。根据等效形状的传送性，可以从等效对中寻觅出等效类。例据等效形状的传送性，可以从等效对中寻觅出等效类。例如，由如，由(S1，S2)和和(S2，S3)可以推出可以推出(S1，S3)，进而可知，进而可知S1、S2、S3属于同一等效类，记作属于同一等效类，记作 (S1，S2)，(S2，S3)S1，S2，S3 在等效关系中，等效对

36、是狭义的概念，它是对两个形状而言的，等效类却是广义的概念，两个形状或多个形状均可以组成一个等效类，甚至一个形状也可以称为等效类，由于任何形状和它的本身必然是等效的。最大等效类：所谓最大等效类，是指不被任何别的等效类所包含的等效类。这里所指的最大，并不是指包含的形状最多，而是指它的独立性，即使是一个形状，只需它不被包含在别的等效类中，也是最大等效类。换句话说，假设一个等效类不是任何其他等效类的子集，那么该等效类称为最大等效类。 利用上述判别形状等效的条件及形状等效的性质，就可以进展形状简化。 原始形状表的化简过程，就是寻觅最大等效类，然后将每个最大等效类中的一切形状合并为一个新的形状，从而得到最

37、小化形状表的过程。简化后的形状数等于最大等效类的个数。(2)用隐含表进展形状化简用隐含表进展形状化简 用隐含表法进展形状化简的普通步骤如下。用隐含表法进展形状化简的普通步骤如下。作隐含表。隐含表是一个直角三角形阶梯网格，横向作隐含表。隐含表是一个直角三角形阶梯网格，横向和纵向格数一样，等于原始形状表中的形状数减和纵向格数一样，等于原始形状表中的形状数减1。隐。隐含表中的方格是用形状称号来标注的，即横向从左到含表中的方格是用形状称号来标注的，即横向从左到右按原始形状表中的形状顺序依次标上第一个形状至右按原始形状表中的形状顺序依次标上第一个形状至倒数第二个形状的形状称号，而纵向自上到下依次标倒数第

38、二个形状的形状称号，而纵向自上到下依次标上第二个形状至最后一个形状的称号。表中每个方格上第二个形状至最后一个形状的称号。表中每个方格代表一个形状对。代表一个形状对。寻觅等效对。利用隐含表寻觅形状表中的全部等效对寻觅等效对。利用隐含表寻觅形状表中的全部等效对普通要进展两轮比较，首先进展顺序比较，然后进展普通要进展两轮比较，首先进展顺序比较，然后进展关联比较。关联比较。 所谓顺序比较是按照隐含表中从上至下、从左至右的所谓顺序比较是按照隐含表中从上至下、从左至右的顺序，对照原始形状表依次对一切形状对进展逐一检顺序，对照原始形状表依次对一切形状对进展逐一检查和比较，并将检查结果以简单明了的方式标注在隐

39、查和比较，并将检查结果以简单明了的方式标注在隐含表中的相应方格内。每个形状对的比较结果有含表中的相应方格内。每个形状对的比较结果有3种情种情况，一是明确是等效的，在相应方格内填上况，一是明确是等效的，在相应方格内填上“；二；二是明确是不等效的，在相应方格内填上是明确是不等效的，在相应方格内填上“；三是与；三是与其他形状对相关，有待于进一步检查的，在相应方格其他形状对相关，有待于进一步检查的，在相应方格内填上相关的形状对。内填上相关的形状对。 所谓关联比较是指对那些在顺序比较时髦未确定能否等效的形状对作进一步检查。 关联比较时，首先要确定隐含表中待检查的那些次态对能否等效，并由此确定原形状对能否

40、等效。假设隐含表中某方格内有一个次态对不等效，那么该方格所对应的两个形状就不等效，于是在相应方格中添加标志“。假设方格内的次态对均为等效形状对，那么与该方格对应的形状为等效形状，该方格不添加任何标志。这种判别有时要反复多次，直到判别出形状对等效或不等效为止。求出最大等效类。在找出原始形状表中的一切等效对之后，可利用等效形状的传送性，求出各最大等效类。确定各最大等效类时应留意两点：一是各最大等效类之间不应出现一样形状，由于假设两个等效类之间有一样形状，那么根据等效的传送性可令其合为一个等效类；二是原始形状表中的每一个形状都必需属于某一个最大等效类，换句话说，各最大等效类所包含的形状之和必需覆盖原

41、始形状表中的全部形状，否那么，化简后的形状表不能描画原始形状表所描画的功能。下面举例阐明化简过程。下面举例阐明化简过程。例例. 化简所示原始形状表。化简所示原始形状表。解解 该表为具有该表为具有7个形状的原始形状个形状的原始形状表。用隐含表法化简如下。表。用隐含表法化简如下。作隐含表。根据画隐含表的规那作隐含表。根据画隐含表的规那么，可得到与给定形状表对应的隐么，可得到与给定形状表对应的隐含表框架如下图。由于原始形状表含表框架如下图。由于原始形状表中有中有A-G共共7个形状，所以隐含表的个形状，所以隐含表的横向和纵向各有横向和纵向各有6个方格。纵向从个方格。纵向从上到下依次为上到下依次为B-G

42、，横向从左到右，横向从左到右依次为依次为AF。表中每个方格代表一。表中每个方格代表一个形状对，如左上角的方格代表形个形状对，如左上角的方格代表形状对状对A和和B，右下角的方格代表形状，右下角的方格代表形状对对F和和G。BCDEFGA B C D E F隐含表格式隐含表格式作出最小化形状表。根据求出的最大等效类，将每作出最小化形状表。根据求出的最大等效类，将每个最大等效类中的全部形状合并为一个形状，即可得个最大等效类中的全部形状合并为一个形状，即可得到和原始形状表等价的最小化形状表。到和原始形状表等价的最小化形状表。寻觅等效对。首先进展顺序比较，根据等效形状的判别规范，寻觅等效对。首先进展顺序比

43、较，根据等效形状的判别规范，依次检查每个形状对，可得到顺序比较结果如以下图所示。依次检查每个形状对，可得到顺序比较结果如以下图所示。例如，形状表中例如，形状表中C和和F满足形状等效条件，所以，在隐含表的相满足形状等效条件，所以，在隐含表的相应方格内填入应方格内填入“；形状；形状A和和C不满足等效条件，故在隐含表的不满足等效条件，故在隐含表的相应方格内填入相应方格内填入“；形状；形状A和和E虽然满足输出一样这个条件，虽然满足输出一样这个条件，但它们的次态在但它们的次态在x=1时为时为B和和E，由于当前尚不能确定，由于当前尚不能确定B和和E能否能否等效，因此，将等效，因此，将BE填人相应方格中。填

44、人相应方格中。 输入输入状态状态X=0 X=1AC/0B/1BF/0A/1CF/0G/0DD/1E/0EC/0E/1FC/0G/0GC/1D/0BCFC D EBEAECFF G CDDEA B C D E F根据输出根据输出,7个个形状分成形状分成3组：组：C，FA，B，ED，G组内形状才有组内形状才有能够等效。能够等效。经过顺序比较后，还有经过顺序比较后，还有A和和B，A和和E，B和和E以及以及D和和C共共4个形状对个形状对尚未确定能否等效。故应接着进展尚未确定能否等效。故应接着进展关联比较，其结果如右图所示。关联比较，其结果如右图所示。 例如，在图中，形状例如，在图中，形状A、B对应对应

45、的方格中次态对为的方格中次态对为CF，而形状，而形状C、F对应的方格标有对应的方格标有“号，阐明形号，阐明形状状C和和F等效，由此可判别出形状等效，由此可判别出形状A和和B等效。等效。 检查形状检查形状A、E的次态对，出的次态对，出现如下循环关系：现如下循环关系： 知形状知形状C和和F是等效的，而形是等效的，而形状状BE又与形状又与形状AB构成循环，所以，构成循环，所以，形状形状A和和E是等效形状对，是等效形状对，B和和E也也是等效形状对。是等效形状对。BCFC D EBEAECFF G CDDEA B C D E FAEBECF BCFC D EBEAECFF G CDDEA B C D E

46、 F 形状D、G对应的方格中含有CD和DE，而形状C、D对应的方格已标以“X号，这阐明形状C和D不等效。因此，可以判别形状D和G不等效，它所对应的方格应添加记号“。 由隐含表可知，原始形状表中的7个形状共有四个等效对：(A，B)，(A，E)，(B，E)，(C，F)。求出最大等效类。由所得到的四个等效对可知，等效对(A，B)，(A，E)，(B，E)构成一个最大等效类A，B，E。 等效对(C，F)不包含在任何其他等效类中，所以，它也是一个最大等效类。其次，形状D和G不和任何其他形状等效，故它们各自构成一个最大等效类。由此可见，原始形状表中的7个形状共构成四个最大等效类，分别表示如下：A，B，E，C

47、，F，D，G。作出最小化形状表。将最大等效类作出最小化形状表。将最大等效类A，B，E、C，F、D、G分别用新的字母分别用新的字母a、b、c、d表示，并表示，并代入原表形状表中，即可得到化简后的最小化形状代入原表形状表中，即可得到化简后的最小化形状表如下表所示。表如下表所示。 输入输入状态状态X=0X=1ab/0a/1bb/0d/0cc/1a/0db/1c/0不完全确定形状表的化简 在讨论构成原始形状表时曾经看到，根据实践问题所构成的在讨论构成原始形状表时曾经看到，根据实践问题所构成的原始形状表除完全确定形状表之外，还存在另一类不完全确原始形状表除完全确定形状表之外，还存在另一类不完全确定形状表

48、。在这类形状表中存在不确定的次态或输出。无疑，定形状表。在这类形状表中存在不确定的次态或输出。无疑，这些不确定的形状和输出对于形状化简将是有利的，关键是这些不确定的形状和输出对于形状化简将是有利的，关键是必需适当处置，以确保化简前后形状表的逻辑功能不变。为必需适当处置，以确保化简前后形状表的逻辑功能不变。为此，提出了一个新的概念此，提出了一个新的概念相容形状。不完全确定形状表相容形状。不完全确定形状表的化简是建立在相容形状根底上的。的化简是建立在相容形状根底上的。 (1)相容形状和相容类相容形状和相容类 相容形状。假定形状相容形状。假定形状Si和和Sj是不完全确定形状表中的两是不完全确定形状表

49、中的两个形状，假设对于一切的有效输入序列，分别从形状个形状，假设对于一切的有效输入序列，分别从形状Si和和Sj出发，所得到的输出呼应序列出发，所得到的输出呼应序列(除不确定的那些位之外除不确定的那些位之外)是完是完全一样的，那么，形状全一样的，那么，形状Si和和Sj是相容的，或者说形状是相容的，或者说形状Si和和Sj是相容对，记作是相容对，记作(Si，Sj)。 从形状表中的形状从形状表中的形状S出发，假设给定某输入序列所得出发，假设给定某输入序列所得到的形状呼应序列除最后一个次态外，其他次态都是确定的，到的形状呼应序列除最后一个次态外，其他次态都是确定的，那么这个输入序列对形状那么这个输入序列

50、对形状S是有效的。一切的有效输入序列，是有效的。一切的有效输入序列，是指有效输入序列的长度和构造是恣意的。是指有效输入序列的长度和构造是恣意的。在不完全确定形状表中，判别两个形状能否相容的根据是表中在不完全确定形状表中，判别两个形状能否相容的根据是表中给出的次态和输出。假定形状给出的次态和输出。假定形状Si和和Sj是不完全确定形状表中的是不完全确定形状表中的两个现态，那么，形状两个现态，那么，形状Si和和Sj相容的条件，可归纳为在一位输相容的条件，可归纳为在一位输入的各种取值组合下满足如下两条。入的各种取值组合下满足如下两条。 第一，它们的输出完全一样，或者其中的一个第一，它们的输出完全一样，

51、或者其中的一个(或两个或两个)输出输出不不 确定。确定。 第二，它们的次态属于以下情况之一：第二，它们的次态属于以下情况之一： a次态一样；次态一样； b次态交错或为各自的现态；次态交错或为各自的现态； c次态循环或为相容对；次态循环或为相容对； d其中的一个其中的一个(或两个或两个)为不确定形状。为不确定形状。 必需指出，相容形状不具有传送性。即不能由必需指出，相容形状不具有传送性。即不能由S1和和S2相容、相容、S2和和S3相容，推出相容，推出S1和和S3也相容。这是由于判别两个形状能否也相容。这是由于判别两个形状能否相容时，对于不给定的输出和不给定的次态可以随意指定的缘相容时，对于不给定

52、的输出和不给定的次态可以随意指定的缘故。故。 相容类。相容类是由彼此相容的形状构成的集合。处于同一相容类中的一切形状之间都是两两相容的。例如，假设有相容对(S1，S2)、(S2，S3)和(S1，S3)，那么可构成相容类S1，S2，S3。 最大相容类。假设一个相容类不是任何其他相容类的子集，那么该相容类称为最大相容类。由于相容形状无传送性，所以，同一原始形状表的各最大相容类之间能够存在一样形状，即同一形状能够出如今不同的最大相容类中。(2)不完全确定形状表的化简 不完全确定形状表的化简过程与完全确定形状表的化简过程类似，只是在某些环节的详细处置上稍有不同。其普通步骤与方法如下。 作隐含表，寻觅相

53、容形状对。利用隐含表寻觅相容对的过程与化简完全确定形状表时寻觅等效对的过程是一样的，仅仅是形状相容与形状等效的规范有所不同而已。即画好隐含表后，首先依次判别每个形状对的相容关系，并将判别结果标注到隐含表中。假设某个形状对相容，那么在相应方格中填入“；假设某个形状对是不相容的，那么在相应方格中填入“；假设两个形状的输出一样(或者不确定)，而其次态尚不能直接确定能否相容，那么在相应方格中填入与之相关的次态对。 在顺序比较完成后，可利用已建立的隐含表继续追踪待确定的形状，即进展关联比较。假设与之关联的次态对都是相容的，那么原形状对是相容的；只需某方格中填入的次态对中有一对不相容，那么该方格所对应的形

54、状对不相容，在该方格中填人标志“。逐个检查，直至判别出一切形状对相容或不相容为止，即可列出原始形状表中的全部相容对。 利用形状合并图，求出最大相容类。为了方便地找到最大相利用形状合并图，求出最大相容类。为了方便地找到最大相容类，可以借助于形状合并图。形状合并图是一种将不完全确容类，可以借助于形状合并图。形状合并图是一种将不完全确定形状表的形状，以定形状表的形状，以“点的方式均匀地绘在圆周上，然后把点的方式均匀地绘在圆周上，然后把一切相容对都用线段衔接起来而得到的图。在这种图中，圆周一切相容对都用线段衔接起来而得到的图。在这种图中，圆周上的点表示形状，点与点之间的连线表示两形状之间的相容关上的点

55、表示形状，点与点之间的连线表示两形状之间的相容关系，一切顶点之间都有连线的多边形就构成一个最大相容类。系，一切顶点之间都有连线的多边形就构成一个最大相容类。2个、个、3个、个、4个和个和5个形状的最大相容类形状合并图如以下图所个形状的最大相容类形状合并图如以下图所示：示：利用闭覆盖表，求最小闭覆盖。这一步与化简完全确定形利用闭覆盖表，求最小闭覆盖。这一步与化简完全确定形状表差别较大。要想求出不完全给定形状表的最小化形状表，状表差别较大。要想求出不完全给定形状表的最小化形状表，必需从最大相容类必需从最大相容类(或相容类或相容类)中选出一个相容类的集合，该相中选出一个相容类的集合，该相容类集合必需

56、满足以下容类集合必需满足以下3个条件。个条件。 S1S2 a覆盖性，即所选相容类集合应包含原始形状表的全部形状。 b. 最小性，即所选相容类集合中相容类个数应最少。 c闭合性，即所选相容类集合中的任一相容类，在原始形状表中任一输入条件下产生的次态应该属于该集合中的某一个相容类。 同时具备最小、闭合和覆盖3个条件的相容类(包括最大相容类)集合，称为最小闭覆盖。不完全确定形状表的最简化，就是寻觅一个最小闭覆盖。 寻觅最小闭覆盖要借助于闭覆盖表。所谓闭覆盖表是指反映闭合和覆盖这两个性质的表，该表包括两部分，一部分反映相容类集合的形状覆盖情况，另一部分反映相容类的闭合关系。闭覆盖表的画法是：在表的左边

57、自上而以下出所选相容类，表的中间覆盖部分从左到右列出全部形状，表的右边闭合部分列出各相容类在输入各种取值组合下的次态组合。必需指出，这里所说的相容类包括最大相容类和它们的子类。 作出最小化形状表。选出一个最小闭覆盖之后，将最小闭覆作出最小化形状表。选出一个最小闭覆盖之后，将最小闭覆盖中的每个相容类用一个新的形状符号表示，再将其代入原始盖中的每个相容类用一个新的形状符号表示，再将其代入原始形状表中，即可得到与原始形状表功能一样的最小化形状表。形状表中，即可得到与原始形状表功能一样的最小化形状表。 下面举例阐明不完全确定形状表的化简方法。下面举例阐明不完全确定形状表的化简方法。 例例1化简右面所示

58、的原始形状表。化简右面所示的原始形状表。 解：解： 这是一个具有这是一个具有5个形状的原个形状的原 始形状表，表中存在不确定的次态始形状表，表中存在不确定的次态 和输出，因此，是一个不完全确定和输出，因此，是一个不完全确定 形状表。用隐含表法化简该形状表形状表。用隐含表法化简该形状表 的过程如下。的过程如下。 作隐含表，寻觅相容形状对。作隐含表，寻觅相容形状对。 作出隐含表，并根据相容形状的判别规范对各形状作出隐含表，并根据相容形状的判别规范对各形状 对进展顺序比较和关联比较后的结果如下。对进展顺序比较和关联比较后的结果如下。 输入输入状态状态X=0 X=1AA/dd/dBC/1B/0CD/0

59、d/1Dd/dB/dEA/0C/1 由隐含表中的标注可知，该形状表中的相容形状对有：(A，B)、(A，C)、(A，D)、(A，E)、(B，D)、(C，D)、(C，E)。作形状合并图，找出最大相容类。 根据相容形状对可作出形状合并图。从形状合并图得到最大相容类为A，B，D、A，C，D、A，C，E。作闭覆盖表，求最小闭覆盖。由得到的3个最大相容类，可作出其闭覆盖表。 BACCADD E AD BCA B C D最大相容类最大相容类覆覆 盖盖闭闭 合合ABCD EX=0X=1ABDABDACBACDACDADBACEACEADC 由闭覆盖表和选择最小闭覆盖的由闭覆盖表和选择最小闭覆盖的3个条件个条件

60、(覆盖、闭合、最小覆盖、闭合、最小)可知，本例的最小闭覆盖可由最大相容类可知，本例的最小闭覆盖可由最大相容类A，B，D和和A，C，E组成。组成。 作出最小化形状表。假定最小闭覆盖中的相容类作出最小化形状表。假定最小闭覆盖中的相容类A，B，D用形状用形状a表示，相容类表示，相容类A，C，E用形状用形状b表示，将其代入原始形状表中，可得到下面所示的最表示，将其代入原始形状表中，可得到下面所示的最小化形状表。小化形状表。在填写最小化形状表中的输出值时，假设原始形状表在填写最小化形状表中的输出值时，假设原始形状表中的相应输出值有确定的和不确定的两种类型，那么中的相应输出值有确定的和不确定的两种类型，那