搜索
1第2章数字系统的算法描述2.1数字系统算法流程图描述2.2状态机及算法状态机图描述2在学习高级语言时，通常用程序流程图来描述程序所实现的一种算法。程序流程图实际上就是一种算法描述的方法。在对数字系统进行算法描述时，为了便于最后进行逻辑综合，常用的算法描述有：算法流程图描述、算法状态机描述、硬件描述语言描述等。本章将对算法流程图描述及状态机描述进行详细讨论。3算法流程图实际上是从程序流程图衍生出来的一种描述数字系统硬件操作功能的方法。两者在形式上有许多相似或类同的地方。但是，由于算法流程图描述的是系统的硬件动作，某些操作结果存在并发性，因此在描述时与程序流程图相比会略有不同，这一点在后面还会提及，请读者注意。2.1数字系统算法流程图描述42.1.1算法流程图的符号及其描述方法算法流程图由若干种描述符号构成，即启动框、工作框、判断框、条件框、结束框及有向线(带有箭头的连线)等。1．启动框和结束框与程序流程图一样，启动框和结束框仅仅表示该算法流程图的开始和结束，使读者一目了然。一般这两个框可以省略，而以文字和箭头直接表示，如图2-1所示。5图2-1启动框和结束框62．工作框如图2-2所示，工作框用一个矩形框表示，在框内用文字说明该工作框所对应的硬件操作内容及对应的输出信号。通常算法流程图与硬件功能有极好的对应关系。也就是说，一个工作框的功能应该很容易地映射成为一个较基本的逻辑电路。图2-3(a)描述两个二进制数a和b相加，其结果为输出c的工作框；图2-3(b)则是实现该工作框功能的逻辑电路。在设计数字系统时，如用算法流程图描述其功能，则总要经历由粗至细逐步细化的过程。所以，在数字系统描述的初期，一个工作框的功能不一定完全能用一个逻辑电路来实现。但是，随着描述的逐步细化，设计者应考虑每一个工作框的可实现性，只有这样，算法流程图最后才能被综合成逻辑电路。7图2-2工作框8图2-3工作框与硬件之间的对应关系(a)工作框；(b)对应的逻辑电路93．判断框判断框与程序流程图中所采用的符号一样，用菱形框来描述。框内应给出判断量和判断条件。根据不同的判断结果，算法流程图将确定采用什么样的后继操作。判断框必定有两个或两个以上的后续操作，当后续操作超过3个时可以用若干个判断框连接来描述。图2-4是用算法流程图中的判断框描述2-4译码器的示例。图2-4中，输入为a、b，输出为y0、y1、y2、y3，用4个判断框描述该电路的四种不同的后续操作。104．条件框条件框用椭圆形符号来表示，如图2-5所示。条件框一定与判断框的一个分支相连，且仅当该分支条件满足时，条件框中所表明的操作才被执行。请读者注意，条件框是算法流程图中所特有的，它可描述硬件操作的并发性。与软件程序图中的分支程序不同的是，条件框的操作是与判断结果同时发生的，如图2-5所示，当cnt=7时，发光二极管就发亮(D←1)。在时序上cnt=7和D←1发生在同一个标定时刻。这和程序中先判别cnt是否等于7，如果等于7则再执行下一条指令，点亮发光二极管(D←1)的操作过程是有显著区别的。11图2-4判断框12图2-5条件框132.1.2算法流程图描述数字系统实例为了熟悉算法流程图描述方法，现举几个例子加以说明。1．串行加法器串行加法器是利用一位加法器实现两个多位二进制数据相加的电路。4位串行加法器的算法流程图如图2-6(a)所示，其对应的硬件电路框图如图2-6(b)所示。该4位串行加法器电路由5部分组成：加法控制电路、累加器、加数寄存器、一位全加器和进位位寄存器。14图2-64位串行加法器(a)算法流程图；(b)对应的硬件框图15加法控制电路产生移位控制信号sh和时钟脉冲clock。当启动信号START有效(START=1)时，sh=1，该电路还将输出4个时钟脉冲(clock)，以完成4位二进制数的加法操作。累加器存放被加的4位二进制数。累加器的最高位输入与加法器输出端sumi相连；最低位输出与加法器的一个输入端ai相连。当sh=1时，每个时钟脉冲下降沿到来将使累加器向右移一位。4个时钟脉冲过后，累加器中将存放两数相加之和。加数寄存器存放相加的加数，其最低位输出与加法器的另一个输入端bi相连。另外，还和最高位的移位输入端相连，构成一个循环移位寄存器。sh和clock连接同一累加器。16进位位寄存器存放上一次加法器相加所产生的进位位结果。它实际上是一个D触发器。一位全加器实现2个二进制位的相加，其输入、输出连接如图2-6(b)所示。需要说明的是，为简化电路，该电路的初始化未包含在上述电路框图中。如图2-6(a)所标明的一样，如果算法流程图描述适当，则其各工作框和判断框等都会有较好的对应关系，这样会给电路设计带来很大的方便。但是，毕竟算法流程图更贴近数字系统的行为描述，当数字系统较复杂时这种对应关系就不那么紧密了。172．乘法器乘法器可实现的算法很多。2个4位数乘法的运算过程如表2-1所示。18表2-12个4位二进制数的相乘过程步骤操作内容被乘数乘数备注1初始化9位寄存器，乘数最低位为“1”，故加被乘数0000010010101001011001M=12右移1位，最低位为“0”，不加被乘数000101100M=03右移1位，最低位为“0”，不加被乘数000010110M=04右移1位，最低位为“1”，加被乘数0000010110101001011011M=15右移1位，产生乘法结果00010110119表中有一个9位寄存器，低4位存放乘数。如果乘数的最低位(寄存器的最低位)为“1”，则将被乘数加到寄存器的b4～b7位上；如果为“0”，则不作加法，然后向右移一位。再重复上述过程，直至将乘数全部移出9位寄存器为止(此例中要移4位)。将这种算法的运算过程用算法流程图来描述，如图2-7(a)所示，与该算法流程图对应的硬件电路框图如图2-7(b)所示。该乘法器由3大部分组成：9位长的累加器ACC、4位加法器和一个乘法控制电路。乘法控制电路有3个输入信号和4个输出控制信号：20(1) Load——累加器数据装载控制信号；(2) sh——累加器移位控制信号；(3) Add——累加器输出相加信号；(4) Done——乘法结束标志信号；(5) clk——时钟信号；(6) START——启动控制信号；(7) M——加被乘数控制信号。21图2-7乘法器(a)算法流程图；(b)硬件电路框图22在启动信号有效(START=“1”)以前应先将乘数装入累加器，将被乘数装入被乘数寄存器(该寄存器图中未画出)，即初始化完毕。在启动信号有效以后，经4个时钟脉冲，乘法操作完成，其结果将存于累加器ACC中。如前所述，算法流程图常用于数字系统的行为描述，它仅仅规定了数字系统的一些操作顺序，而并未对操作的时间和操作之间的关系做出严格的规定。因而它常用于验证数字系统数学模型的正确性，对其硬件的可实现性未作更多的关注。23众所周知，数字系统由控制单元和处理单元两大部分组成。控制单元在统一的同步时钟控制下，严格按照一定的时间关系输出控制信号；处理单元一步一步地完成整个数字系统的操作。这种工作过程用算法流程图是无法正确描述的。下面介绍一种用于描述控制器工作过程的方法，即算法状态机图(AlgorithmicStateMachineChart，ASM图)描述方法。2.2状态机及算法状态机图描述242.2.1状态机的分类及特点控制器按一定时序关系产生一系列的时序控制信号，因此它必定包含时序电路。根据时序输出信号产生的机理不同，时序电路可以分成两类：米勒(Mealy)型和摩尔(Moore)型。1．米勒型时序电路米勒型时序电路的典型结构如图2-8所示。25图2-8米勒型时序电路的典型结构26从图2-8中可以看到，该电路由一个组合逻辑电路和一个状态寄存器构成。状态寄存器的输入是下一个状态值，而输出是当前的状态值。组合逻辑电路的输入为电路输入X及当前状态值，输出为电路输出Y及下一个状态值。该电路的特点是：其输出不仅与当前状态有关，还和输入值有关。也就是说，输入X的值不仅决定了电路的下一个状态，而且对当前的输出值也会产生影响。下面以四位串行加法器(见图2-6)的控制电路为例作一说明。参照图2-8所示的米勒型时序电路的典型结构，此时串行加法器控制电路的输入为START，输出信号为sh，状态寄存器的锁存信号为clk，状态寄存器的输出为si，根据前述工作过程，我们不难列出其状态表和状态图，如表2-2和图2-9所示。27表2-2串行加法器的控制状态表下一个状态当前输出(sh)当前状态START=0START=1START=0START=1S0S0S101S1S2S211S2S3S311S3S0S011从表2-2中可以看到，控制器的输入START只有在S0状态下才会对输出sh产生影响，它表明该电路一旦启动，一定要做完4位加法才能使其停止工作。28图2-9串行加法器的控制状态图29在图2-9中，每一个圆代表一个状态，在其中标出了状态名S0、S1、S2、S3。各状态之间用带箭头的线连接起来，表示状态转换的方向。在连接线旁标出了箭头所指状态的输入值和输出值，如0/0，斜杠左边为输入值，右边为输出值，本例中应为START/sh。302．摩尔型时序电路摩尔型时序电路的典型结构如图2-10所示。图2-10中，输入有输入信号X和状态锁存时钟clk，输出只有一个Y，其值仅与当前的状态值有关，而与输入X无关。非归零(NRZ)串行数据信号转换成曼彻斯特(Manchester)串行数据信号的时序电路就是摩尔型时序电路的典型实例。NRZ信号和Manchester信号的时序关系如图2-11所示。从图2-11中可以看出，当非归零信号由“1”变成“0”或由“0”变成“1”时，曼彻斯特信号在一个码元宽度的时间内将维持不变，在其它情况下，在每个码元中间信号将发生一次变化(由“1”变“0”或由“0”变“1”)。据此，我们可以得出该串行码转换电路的状态表和状态转换图分别如表2-3和图2-12所示。31图2-10摩尔型时序电路的典型结构32图2-11NRZ信号和Manchester信号的时序关系33表2-3NRZ信号转换成Manchester码的状态表下一个状态当前状态X=0X=1当前输出YS0S1S30S1S2－0S2S1S31S3－S0134图2-12NRZ信号转换成Manchester码的状态图35clk的时钟周期为码元宽度的二分之一，每个时钟周期为一个状态，也就是半个码元为一个状态。还应注意，Manchester码的输出相对于NRZ信号的输入将滞后一个时钟周期。产生这个滞后的原因是：摩尔时序电路在有效时钟边沿到来以前不能立即响应NRZ信号输入的变化。这是Moore型电路和Mealy型电路的主要区别。在Mealy型电路中，只要在下一个时钟脉冲到来以前，输入的变化立即会引起输出的变化。Mealy型和Moore型时序电路常用于数字系统控制电路的描述，在许多文献和著作中也称它们为Mealy状态机和Moore状态机，以表示它们构造电路时的不同机理。362.2.2算法状态机流程图的符号及描述方法所谓状态机，就是用来控制数字系统，使其根据它的输出，一步一步地进行相应的操作和运算的机器(这里应理解为电路)。实际上，时序电路就是一种状态机。分析状态机的传统方法是利用状态图和状态表。但是，随着计算机技术及电子设计自动化(EDA)技术的发展，为了提高电路的设计效率，人们试图用硬件描述语言(HardwareDescriptionLanguage，HDL)来描述数字系统的硬件电路。硬件描述语言如VHDL、Verilog-HDL等都是高级语言。为了编程方便，人们通常用程序流程图来描述算法和系统的功能。同样，为了方便地利用硬件描述语言来描述数字系统，37在编程前也需要用类似的流程图来描述数字系统的状态机，这就是状态机流程图(StateMachineFlowchart)，也称为算法状态机流程图(AlgorithmicStateMachineFlowchart)。算法状态机流程图也可简称为算法状态机图，其使用的描述符号与算法