10.3 算法状态机（ASM）的硬件实现

 

10.3  算法状态机（ASM）的硬件实现

用硬件实现ASM图就是按算法要求设计一个控制器的同步时序电路。时序电路的状态可用触发器的输出状态表示。用触发器表示时序电路的状态有两种不同的方法：编码方法和非编码方法。

编码方法就是以不同的二进制码分配给控制器的各个状态，实现对状态的编码。采用编码的方法，用N个触发器可以实现具有2^N个状态的时序电路，所以这种方法可以节省硬件，但是这样因为状态被编码，控制器电路与算法状态机流程图之间没有直接的对应关系，所以采用这种编码方法的控制器电路工作性能的直观性差，而且设计也不方便。

非编码方法就是对每一个状态安排一个触发器，触发器用响应的状态命名。显然，这种方法要用到很多触发器，但是控制算法和控制器电路之间有直接的对应关系，所以逻辑关系非常清楚，设计方便，工作性能的直观性好。

本节介绍3种用硬件实现算法状态机的方法：传统方法、多路选择器法和环形计数型方法。其中前两种是采用状态编码的方法；最后一种采用的是非状态编码的方法。

1．用传统方法实现ASM图

用传统方法设计控制器电路所用到的硬件就是触发器和门电路，实际上就是前面学过的同步时序电路的设计方法，这种设计方法把减少电路成本作为一个重要的设计目标，因此产生了一系列降低电路成本的设计手段。由于数字技术的飞速发展，数字电路的元器件的价格已经降到很低了，所以在设计时，没有必要再用太复杂的手段将电路化到最简，所以在下面的举例中状态分配是随意的，触发器采用D触发器。

【例10-1】 用传统方法实现图10-8所示的ASM流程图。

图10-8  控制器的算法状态机流程图

解：由图10-8可见，该图共有4个状态P、Q、R、S。需要用两个触发器来实现。首先对4个状态P、Q、R、S进行状态分配如下。

P：00    Q：01    R：10     S：11

可以列出状态转换表，如表10-1所示。

表10-1  控制器状态转换表

根据状态转换表10-1，可以写出控制输入的逻辑函数表达式：

D₁=Q₂'Q₁'X+Q₂'Q₁

=Q₂'（Q₁+Q₁'X）

=Q₂'（Q₁+X）

D₂=Q₂'Q₁'X'+Q₂'Q₁

=Q₂'（Q₁+Q₁'X'）

=Q₂'（Q₁+X'）

根据图10-8，在P状态和S状态时，无条件输出CMD₁和CMD₃，在P状态且控制输入X为1时，有条件输出CMD₂，所以有：

CMD₁=Q₂'Q₁'

CMD₂=Q₂'Q₁'X

CMD₃=Q₂Q₁

由此可以画出逻辑电路图，如图10-9所示。

图10-9  控制器逻辑电路图

可见用传统方法设计的控制电路，硬件与算法之间无直接的对应关系，电路的工作性能的直观性差。在本题的具体表现为：在P状态时，如果X=1，则其新态为Q，如果X=0，其新态为R。P状态向其新态的转换关系就很难直观地从逻辑电路图10-9中看出。这种方法还有另外一个缺点：如果控制器电路已经设计好了，那么若要修改算法，哪怕只修改一点点，也要重新设计电路。

2．用多路选择器方法实现ASM图

多路选择器方法与传统方法的不同点在于，采用多路选择器来实现控制器时序电路的组合逻辑部分，而不是用逻辑门，这样不仅简化了电路，而且使电路的工作性能更加直观。下面举例来说明怎样分析用多路选择器法实现的控制器电路以及用多路选择器设计控制器电路的过程。

【例10-2】 分析如图10-10所示的用多路选择器法设计的控制电路。

解：如图10-10，两个多路选择器的输出端接到D触发器的输入端，并以多路选择器所选择的数据作为新态数据。

如果将Q₂Q₁从00→11的4个新态数据分别从图10-10中求出，则可以列出状态转换表，如表10-2所示。

表10-2  状态转换表 现态 新态 Q2 Q1  Q2*  Q1* 0 0 0 1 0 1   X′ 0 1 0 Y 1 1 1 1 X

图10-10  控制器的逻辑电路图

设触发器的现态是Q₂Q₁=00，00地址码从两个多路选择器中选择的数据分别是0和1，所以00的新态就是01，于是01又作为地址码输入多路选择器，由它选择的数据是X'和0，于是01的新态要取决于输入X的值，如果X=0，则新态为10；如果X=1，则新态为00。可见如果被选择的数据出现了变量，则说明状态转换出现了分支。按照上面的分析方法，可以列出完整的状态转换表，如表10-3所示。

图10-11  控制器ASM流程图

表10-3  完整的状态转换表

现态		新态		转换条件
Q2	Q1	Q2*	Q1*
0	0	0	1	1
0	1	1	0	X'
		0	0	X
1	0	1	1	Y
		0	1	Y'
1	1	1	1	X
		1	0	X'

将表10-3表示为算法状态机流程图，如图10-11所示。因为在逻辑电路图10-10中，有无条件输出：

CMD=BA

所以将其写在状态码为11的框中。从以上的分析可以看出，用多路选择器的方法设计控制电路，由于状态转换关系表现为以地址码选择相应数据的关系，所以控制器电路与其算法的对应关系就变得比较明显，而且如果需要修改算法，只要修改多路选择器的相应数据端的数据即可，无须重新设计电路。

【例10-3】 用多路选择器的方法实现如图10-12所示的ASM流程图。

解：从图10-12中可以看出，该图有4个状态，所以需要两个D触发器，还要两个4输入的多路选择器。设状态分配如下：

P=00     Q=01     R=10     S=11

根据ASM流程图，可以列出该控制器的状态转换数据表，如表10-4所示。

根据表10-4，可以写出两个多路选择器B和A的各数据输入端的逻辑表达式：

B（0）=0·X'Y+1·X'Y'+1·X

=X'Y'+X

=X+Y'

B（1）=0·W'+1·W

=W

B（2）=0

B（3）=Z'+ZX

=Z'+X

A（0）=X'Y+X

=X+Y

A（1）=0

A（2）=0

A（3）=Z'

该控制器有两个输出CMD₁和CMD₂，它们都是无条件输出，逻辑表达式分别是：

CMD₁=B'A'

CMD₂=BA

由此可以画出该ASM图所对应的逻辑电路图，如图10-13所示。

图10-13  控制器逻辑电路图

从本例可以看出，用多路选择器方法设计控制器电路的主要步骤就是从ASM流程图中读取多路选择器的输入数据，所以这种方法的设计步骤简单方便。

与传统方法相比，用多路选择器法设计控制器电路有两个显著的优点：首先，控制器电路规整化。用传统方法设计的控制电路，其组合逻辑电路是由门电路组成，比较凌乱，是一种不规整的树型逻辑网络，在设计者设计和使用者维护检修时都很麻烦。而用多路选择器实现门电路组合网络的功能，可以使电路的结构规整简单。其次，控制器电路与控制算法之间有着比较明显的对应关系，控制器的工作性能比较直观。

3．用环形计数型方法

环形计数型方法与前面两种方法的不同之处，在于该方法不对状态编码。为了能在控制器电路上区分出不同的状态，每一个状态都要用一个触发器，且每个触发器都用其代表的状态命名。当控制器处于某个给定的状态，那么只有代表这个状态的触发器的输出为1，其他输出为0。

控制器从现状态转换到新状态，电路中所要发生的变化是：表示现态的触发器的输出由1变为0，表示新态的触发器的输出由0变为1，表示其他状态的触发器的状态保持为0。将这种实现ASM流程图的方法叫做环形计数型方法，是因为控制器电路和环形计数器一样，在任何时刻只有一个触发器的输出为1，其余均为0。

采用环形计数型方法设计控制器电路需要注意的问题是，控制器电路的初始化问题和每一个触发器输入逻辑的正确性问题。

控制器电路的初始化问题就是对设计的控制器电路，能通过外部的复位信号，将代表触发器起始状态的触发器置位，而将其余的触发器复位。这是为了保证电路一旦开始工作，就有一个触发器的输出为1，其余触发器的输出为0。用复位信号初始化电路的方法有以下两种：

（1）用复位信号使所有的触发器的输出为低电平。用环形计数型方法设计的控制器电路，所用的触发器一般为中规模集成多位D触发器。常用的4位D触发器如图10-14所示。这样的一类电路有一个公共的异步清零端，通过外部的复位信号RESET的作用，可以使所有触发器的输出为低电平。为了使代表起始状态的触发器的输出为1，其他的触发器的输出为0，对代表起始状态的触发器的原端输出和反端输出重新加以规定，并相应地修改其数据输入电路，如图10-14所示，P状态触发器在复位信号RESET的作用下，输出为1，其余触发器的输出为0，这样就实现了P状态为起始状态的初始化工作。因为对P状态触发器重新规定了原变量和反变量输出，又相应地修改了其数据输入电路，因此从P（D）随时钟输入的数据，仍将出现在其原端输出P。

（2）用复位信号使代表起始状态触发器的输出为高电平，其余触发器的输出为低电平。如果控制器所用的D触发器兼有异步清零和异步置位端，则可以按照图10-15的方式将其连接起来。复位信号RESET作用后，P状态触发器的输出为高电平，P输出为1，其余触发器的输出均为0，实现了初始化工作。

设计中，必须使每一个触发器有正确的输入逻辑，以保证初始化时建立起来的逻辑1能按照ASM流程图的规定，随时钟逐步地由一个触发器移至另一个触发器，要求每个触

           

图10-14  4位D触发器             图10-15  4位D触发器连接方式

发器的输入都包含如下信息：本触发器输出的逻辑1是从哪些触发器转换过来的以及其转换条件。为了解决这一问题，下面通过一道例题来学习用环形计数型方法实现ASM流程图的设计过程。

【例10-4】 用环形计数型方法实现图10-12所示的ASM流程图。

解：因为流程图中有4个状态，所以需要用4个D触发器来实现，这里采用4位D触发器集成电路。由于它的异步控制输入中，仅有公共的复位端，故采用上述第一种实施电路初始化的方法，在P、Q、R、S四个状态中设定P状态为起始状态。为了确定各触发器的输入逻辑，可以列出状态转换表，如表10-5所示。

表10-5  控制器状态转换表

根据表10-5所示，可以列出触发器的输入逻辑的函数表达式和输出命令的逻辑表达式：

P（D）=QW'+R+SZX'

Q（D）=PX'Y

R（D）=PX'Y'+QW+SXZ

S（D）=PX+SZ

CMD₁=P

CMD₂=S

由此可以画出逻辑电路图，如图10-16所示。

图10-16  控制器逻辑电路图

环形计数型方法与前面方法最大区别就是，该方法采用非状态编码。用这种方法设计控制器电路具有如下特点：

（1）设计方便，电路工作性能的直观性好。

用多路选择器方法设计的控制器电路，由于使用了多路选择器，使其工作性能变得直观，也使电路的设计变得方便，但是由于它采用的仍是状态编码，控制器电路与其算法之间的对应关系是间接的，通过二进制编码才能将其联系起来，因此仍然不够直观方便。而用环形计数型方法设计的控制器电路，由于每一个电路状态都对应一个触发器，状态转换关系可以直接表示为触发器的输入逻辑，使电路与算法之间的对应关系变得很直接，所以也使设计变得更加方便。

（2）控制器的无条件输出命令由相应的触发器直接输出，不需要译码电路。

（3）用环形计数型方法实现ASM图，必须有正确的初始化控制电路。

除此以外，对于较大的控制电路，由于每一个状态要安排一个触发器，因此提高了电路的成本。随着数字技术的高速发展，集成电路已经非常廉价，而且所要设计的数字系统通常是很复杂的，要求设计的电路直观性好，且方便设计或改动，因此，环形计数型方法的优势还是很明显的。当然，还是要具体情况具体分析，不同的方法适用于不同的实际设计情况。可以将前面介绍的这3种方法的适用范围大致划分如下：

① 当电路的状态的数目小于或等于4个时，一般采用传统的方法来设计控制器电路。因为这种数字系统较小，不会太强调控制器电路的直观性和设计的方便性。

② 当电路的状态数在5～16个的范围之内时，一般采用多路选择器的方法来设计控制器电路。因为随着状态数目的增多，对电路直观性的要求也越来越高，所以采用多路选择器的方法来设计电路。但是如果状态数目太多，状态编码带来的弊端就会大大影响电路的直观性，而且多路选择器的输入端也不能超过16个，若级联使用也会使电路变得很复杂。

③ 当电路状态数在17～32之间时，一般采用环形计数型方法来设计电路。因为对于较大的数字系统，状态编码使电路直观且设计方便的优势就会表现出来，但是当电路的状态数目更多时，就不采用上述硬件设计的控制器，而采用其他方式设计控制器。