数字系统的算法描述

数字系统的算法描述2.1数字系统算法流程图描述2.2状态机及算法状态机图描述习题与思考题

2.1数字系统算法流程图描述

2.1.1算法流程图的符号及描述方法算法流程图由若干种描述符号构成，即启动框、工作框、判断框、条件框、结束框及有向线(带有箭头的连线)等。

1．启动框和结束框

与程序流程图一样，启动框和结束框仅仅表示该算法流程图的开始和结束，使读者一目了然。一般这两个框可以省略，而以文字和箭头直接表示，如图2-1所示。

图2-1启动框和结束框

2．工作框

如图2-2所示，工作框用一个矩形框表示，在框内用文字说明该工作框所对应的硬件操作内容及对应的输出信号。

图2-2工作框

(a)工作框；(b)对应的逻辑电路图2-3工作框与硬件之间的对应关系

通常算法流程图与硬件功能有极好的对应关系。也就是说，一个工作框的功能应该很容易地映射成为一个较基本的逻辑电路。图2-3(a)描述两个二进制数a和b相加，其结果为输出c的工作框；图2-3(b)则是实现该工作框功能的逻辑电路。在设计数字系统时，如用算法流程图描述其功能，则总要经历由粗至细逐步细化的过程。所以，在数字系统描述的初期，一个工作框的功能不一定完全能用一个逻辑电路来实现。但是，随着描述的逐步细化，设计者应考虑每一个工作框的可实现性，只有这样，算法流程图最后才能被综合成逻辑电路。

3．判断框

判断框与程序流程图中所采用的符号一样，用菱形框来描述。框内应给出判断量和判断条件。根据不同的判断结果，算法流程图将确定采用什么样的后继操作。判断框必定有两个或两个以上的后续操作，当后续操作超过3个时可以用若干个判断框连接来描述。图2-4是用算法流程图中的判断框描述2-4译码器的示例。图2-4中，输入为a、b，输出为y0、y1、y2、y3，用4个判断框描述该电路的四种不同的后续操作。

图2-4判断框图2-5条件框

2.1.2算法流程图描述数字系统实例

为了熟悉算法流程图描述方法，现举几个例子加以说明。

1．串行加法器

串行加法器是利用一位加法器实现两个多位二进制数据相加的电路。4位串行加法器的算法流程图如图2-6(a)所示，其对应的硬件电路框图如图2-6(b)所示。该4位串行加法器电路由5部分组成：加法控制电路、累加器、加数寄存器、一位全加器和进位位寄存器。

(a)算法流程图；(b)对应的硬件框图图2-64位串行加法器

一位全加器实现2个二进制位的相加，其输入、输出连接如图2-6(b)所示。

需要说明的是，为简化电路，该电路的初始化未包含在上述电路框图中。

如图2-6(a)所标明的一样，如果算法流程图描述适当，则其各工作框和判断框等都会有较好的对应关系，这样会给电路设计带来很大的方便。但是，毕竟算法流程图更贴近数字系统的行为描述，当数字系统较复杂时这种对应关系就不那么紧密了。

2．乘法器

乘法器可实现的算法很多。2个4位数乘法的运算过程如表2-1所示。

表中有一个9位寄存器，低4位存放乘数。如果乘数的最低位(寄存器的最低位)为“1”，则将被乘数加到寄存器的b4～b7位上；如果为“0”，则不作加法，然后向右移一位。再重复上述过程，直至将乘数全部移出9位寄存器为止(此例中要移4位)。将这种算法的运算过程用算法流程图来描述，如图2-7(a)所示，与该算法流程图对应的硬件电路框图如图2-7(b)所示。

(a)算法流程图；(b)硬件电路框图图2-7乘法器

该乘法器由3大部分组成：9位长的累加器ACC、4位加法器和1个乘法控制电路。乘法控制电路有3个输入信号和4个输出控制信号：

(1)

Load——累加器数据装载控制信号；

(2)

sh——累加器移位控制信号；

(3)

Add——累加器输出相加信号；

(4)

Done——乘法结束标志信号；

(5)

clk——时钟信号；

(6)

START——启动控制信号；

(7)

M——加被乘数控制信号。

在启动信号有效(START

=

1)以前应先将乘数装入累加器，将被乘数装入被乘数寄存器(该寄存器图中未画出)，即初始化完毕。在启动信号有效以后，经4个时钟脉冲，乘法操作完成，其结果将存于累加器ACC中。

如前所述，算法流程图常用于数字系统的行为描述，它仅仅规定了数字系统的一些操作顺序，而并未对操作的时间和操作之间的关系做出严格的规定。因而它常用于验证数字系统数学模型的正确性，对其硬件的可实现性未作更多的关注。

2.2状态机及算法状态机图描述

众所周知，数字系统由控制单元和处理单元两大部分组成。控制单元在统一的同步时钟控制下，严格按照一定的时间关系输出控制信号；处理单元一步一步地完成整个数字系统的操作。这种工作过程用算法流程图是无法正确描述的。面介绍一种用于描述控制器工作过程的方法，即算法状态机图(AlgorithmicStateMachineFlowchart，ASM图)描述方法。

2.2.1状态机的分类及特点

控制器按一定时序关系产生一系列的时序控制信号，因此它必定包含时序电路。根据时序输出信号产生的机理不同，时序电路可以分成两类：米勒(Mealy)型和摩尔(Moore)型。

1．米勒型时序电路

米勒型时序电路的典型结构如图2-8所示。

图2-8米勒型时序电路的典型结构．

从图2-8中可以看到，该电路由一个组合逻辑电路和一个状态寄存器构成。状态寄存器的输入是下一个状态值，而输出是当前的状态值。组合逻辑电路的输入为电路输入X及当前状态值，输出为电路输出Y及下一个状态值。该电路的特点是：其输出不仅与当前状态有关，还和输入值有关。也就是说，输入X的值不仅决定了电路的下一个状态，而且对当前的输出值也会产生影响。下面以4位串行加法器(见图2-6)的控制电路为例作一说明。

参照图2-8所示的米勒型时序电路的典型结构，此时串行加法器控制电路的输入为START，输出信号为sh，状态寄存器的锁存信号为clk，状态寄存器的输出为si，根据前述工作过程，我们不难列出其状态表和状态图，如表2-2和图2-9所示。

图2-9串行加法器的控制状态图

2．摩尔型时序电路

摩尔型时序电路的典型结构如图2-10所示。图中，输入有输入信号X和状态锁存时钟clk，输出只有一个Y，其值仅与当前的状态值有关，而与输入X无关。

图2-10摩尔型时序电路的典型结构

非归零(NRZ)串行数据信号转换成曼彻斯特(Manchester)串行数据信号的时序电路就是摩尔型时序电路的典型实例。NRZ信号和Manchester信号的时序关系如图2-11所示。

图2-11NRZ信号和Manchester信号的时序关系

从图2-11中可以看出，当非归零信号由“1”变成“0”或由“0”变成“1”时，曼彻斯特信号在一个码元宽度的时间内将维持不变，在其他情况下，在每个码元中间信号将发生一次变化(由“1”变“0”或由“0”变“1”)。据此，我们可以得出该串行码转换电路的状态表和状态转换图分别如表2-3和图2-12所示。

表2-3NRZ信号转换成Manchester码的状态表

图2-12

NRZ信号转换成Manchester

码的状态图

周期为码元宽度的二分之一，每个时钟周期为一个状态，也就是半个码元为一个状态。还应注意，Manchester码的输出相对于NRZ信号的输入将滞后一个时钟周期。产生这个滞后的原因是：摩尔时序电路在有效时钟边沿到来以前不能立即响应NRZ信号输入的变化。这是Moore型电路和Mealy型电路的主要区别。在Mealy型电路中，只要在下一个时钟脉冲到来以前，输入的变化立即会引起输出的变化。

Mealy型和Moore型时序电路常用于数字系统控制电路的描述，在许多文献和著作中也称它们为Mealy状态机和Moore状态机，以表示它们构造电路时的不同机理。

2.2.2算法状态机流程图的符号及描述方法

所谓状态机，就是用来控制数字系统，使其根据它的输出，一步一步地进行相应的操作和运算的机器(这里应理解为电路)。实际上，时序电路就是一种状态机。

1．状态框

状态框描述符如图2-13(a)所示，它用一个方框表示。状态框描述符中，上方的箭头表示进入该状态；箭头的右方标注该状态在系统中的编码(该编码在系统中是唯一的)；下方箭头表示该状态转离的方向；方框内标注状态名和输出信号清单，斜杠( /

)左边标注状态名，斜杠右边标注输出信号清单。有多个输出信号时，输出信号和输出信号之间用空格分隔。

状态框；(b)判断框；(c)条件输出框图2-13算法状态机图的描述符

3．条件输出框

条件输出框描述符如图2-13(c)所示。条件输出框描述符中，上方箭头表示条件值转入的方向，该带箭头的线一定和判断框的一个分支相连，且继承对应分支的条件值；下方箭头表示转离方向；框内标注条件输出信号清单。有多个输出信号时，输出信号和输出信号之间同样用空格隔开。

在算法状态机图中，无论是什么输出信号，其输出只能是两种值，非“0”即“1”。例如，在条件输出框中表明的输出信号或输出量，在条件满足时输出为“1”。

2.2.3算法状态机图描述实例

算法状态机图与程序流程图一样，在描述过程中有许多不同的方法和技巧。同样一个数字系统可以用多种不同形式的算法状态机图来描述，以达到各种不同的目的。

1．算法状态机图的化简

图2-14(a)和图2-14(b)所示的两个算法流程图是等效的。从结构来看，图2-14(a)是图2-14(b)的简化。

图2-14算法状态机图的化简

2．算法状态机图的反馈通道描述

算法状态机图中可以有内部的反馈通道。与程序流程图画法不同的是，内部反馈通道的箭头应指向某一个状态的输入线，如图2-15所示。

(a)错误画法；(b)正确画法图2-15算法状态机图的反馈通道描述

图2-15(a)中反馈通道箭头指向判断框的输入，这在程序流程图中是允许的，但在算法状态机图中是不允许的，是错误的。如果将图2-15(a)改成图2-15(b)，反馈通道指向S0状态的输入，这样画法就正确了。

3．算法状态机图的串-并结构变换

在进行数字系统设计时，有时为了节省硬件(如运算器)，所有运算工作可分给一个运算器来工作；有时为了加快处理时间，数字系统的运算工作又可以分给多个运算器并行工作。这些硬件结构反映在算法状态机图上就可分为串行方式和并行方式。串-并方式的互相变换是经常要进行的工作。图2-16是这两种结构的等效画法。

(a)并行结构；(b)串行结构图2-16串、并行结构的等效画法

2.2.4算法流程图至状态图的变换方法

对初学者来说，从算法流程图直接变换至算法状态机图是困难的，特别是当数字系统较为复杂时更是如此。

算法流程图至状态图的变换主要有以下几个步骤：

(1)系统状态分配。

(2)确定输入信号及状态转移条件。从算法流程图中，如果抽象出上述三种参数，则可以很容易地画出状态图。

(3)确定各状态的输出。

1．系统状态分配

算法流程图是由事件驱动的流程图，而状态图是一种时钟驱动的流程图，它将系统工作过程分成若干个状态，由时钟驱动，一个状态接着一个状态，按时钟周期节拍完成系统的工作过程。因此，为了将算法流程图转换成状态图，首先要对算法流程图进行抽象，对其工作过程进行划分。每个相对独立的操作状态就可以定义为一个状态，这个过程就称为系统的状态分配。下面以4位乘法算法流程图为例作一说明。

4位乘法器控制算法流程图如图2-7所示。下面根据其工作过程分配各状态。

(1)系统复位状态——S0；

(2)装入乘数和被乘数——S1；

(3)被乘数与累加器ACC相加——S2；

(4)累加器右移1位——S3。

S0～S3包含了4位乘法器控制的4个基本的独立状态。如果图2-7不用循环结构，那么4位乘法器的状态就需10个(S0～S9)，请读者自行画出。

在较为复杂的系统中，状态图可以从粗到细逐步细化，直至最低层。顶层的一个状态细化展开以后可能要用含有若干个子状态的状态图来描述。

2．确定输入信号及状态转移条件

从图2-7中可以看到，当S0是复位状态时，START =

0；当START =

1时，状态由S0转移到S1。下面判断乘数最低位是否为“1”(M =

1)。如果为“1”，则转移至状态S2；如果为“0”(M =

0且K =

0)，则仍在S1状态；若K =

1且M =

0，则转移至S3。在S2状态下，若未移位4次(K =

0)，则转移至S1状态；如果已移够4次(K =

1)，则转移至S3状态。S3状态的下一个状态一定是S0状态。

3．确定各状态的输出

由S0状态转移至S1状态，需要将被乘数和乘数装入累加器ACC，故需要一个装入控制信号Load。S1状态循环或转移至S3状态，需一个累加器移位控制信号sh。由S1状态转移至S2状态需要一个被乘数和累加器相加的信号Add。由S2状态转移至S1状态需加一个累加器移位控制信号sh。由S2状态转移至S3状态需要一个累加器移位控制信号sh。由S3状态转移至S0状态需要输出Done乘法结束状态信号。根据上面的叙述，我们可以画出4位乘法器的控制状态表和状态图如表2-4和图2-17所示，图中K'、M'表示对应取值为“0”。

表2-44位乘法器的控制状态表

图2-174位乘法器的控制状态图

2.2.5状态图至算法状态机图的变换方法

状态图(状态转换图)是传统描述时序电路的方法。为了用硬件描述语言进行编程，通常要将状态图变换成算法状态机图(ASM)。变换大约需经过以下几个步骤。

1．对现有的状态进行编码

从状态图中我们可以确定某数字系统有几个不同的状态，并用二进制数对每一个状态进行赋值。例如，图2-18(a)是某数字系统的状态图。该系统共有3个不同的状态S0、S1、S2，可以用2位二进制数表示：S0——

00；S1——

01；S2——

11。

(a)状态图；(b)算法状态机图图2-18某数字系统的状态图和算法状态机图

2．各输出信号的确定

图2-18(a)所示是米勒型和摩尔型状态机混合的状态图，其输出Za、Zb、Zc仅由状态S0、S1和S2确定(Moore型)，而输出Z1和Z2都由各状态值和输入值共同确定(Mealy型)。

根据算法状态机的画法规则，输出Za、Zb、Zc应标注在状态框中，如S0/Za、S1/Zb、S2/Zc；Z1、Z2除与当前状态值有关外，还与输入值X有关，因此Z1、Z2应用条件输出框来标注。

3．按状态编码顺序画出算法状态机图

根据状态编码及输出标注方法，状态用状态框描述，输入不同的X，状态转移方向是不一样的，据此输入用判断框表示。摩尔输出标注在状态框中，米勒输出用条件输出框标注在判断框的相应分支上。这样就完成了状态图至算法状态机图的变换，如图2-18(b)所示。

【例2-1】串行加法器的控制状态图如图2-19所示。该状态图是米勒型状态图，其输出由输入和当前状态确定。

(1)对现有状态进行编码。

图2-19共有4个状态S0、S1、S2、S3，可用2位二进制数进行编码。

S0——00；

S1——01；

S2——10；

S3——11。

图2-19串行加法器的控制算法状态机图

(2)确定输出值。

图2-19中的输出值为sh，它由输入值START和状态值确定，可用条件输出框描述。在图2-19中，只有在S0状态下，输入值START为“1”，才会发生状态转移，由S0状态转至S1状态，且输出sh =

1。在其他状态下，只要有时钟脉冲，状态就会向下一个转换，直至S0，同时不管此时的输入START为何值，其输出值sh仍继续保持为“1”。

(3)画出串行加法器控制算法状态机图。

根据上面叙述，我们可以画出串行加法器控制算法状态机图如图2-19所示。

【例2-2】4位乘法控制器的状态图如图2-17所示。从状态图中可以看到，它是一个米勒型状态机图，其输出应用条件输出框表示。

(1)对现有状态进行编码。

4位乘法器控制电路共有4个状态S0～S3，这样对应状态编码为00～11，必须用2位二进制数来表示。

对照图2-17可以看到，S0是复位状态。当START为“1”时，系统状态将转移到S1，并输出Load信号，将被乘数和乘数装入ACC。下一个状态有两种选择。如果M

=

1(即乘数低位为“1”)，则输出Add信号，进行累加器和被乘数的加法操作，转移至状态S2；如果M =

0，则输出sh信号，控制ACC右移1位，并对K进行检测。在S1、S2状态下，如果K =

1(表明最后一次移位结束)，则下一个状态为S3；如果K =

0，则转移至S1状态。在S3状态下，Done信号(完成信号)有效输出，在下一个时钟脉冲到来后，状态返回至S0，一个4位数的乘法过程宣布结束。

图2-204位乘法器的控制算法状态机图

(2)确定输出。

图2-20中的输出都是米勒型输出，因此这些输出都应用条件输出框表示。乘法器控制电路的输出有：

sh——移位控制信号；

Add——加法控制信号；

Done——结束标志信号；

Load——加载ACC信号。

(3)画出4位乘法器的控制算法状态机图。

根据图2-17及上面的叙述，我们可以画出4位乘法器的控制算法状态机图如图2-20所示。

2.2.6C语言流程图至算法状态机图的变换方法

在设计数字系统时首先要建立系统的数学模型。最初，通常建立的是行为级的数学模型。为了验证系统数学模型的正确性，设计人员可以根据数学模型的算法，用C语言程序在计算机中进行仿真。如果仿真结果是正确的，那么该C语言程序所描述的系统功能是正确的。如果我们以此C语言程序为依据，将它变换成系统的算法状态机图，那么就可以正确地设计出该数字系统的硬件。这种思路是完全可行的，并且前面几节内容已提供了基本的变换方法和手段。C语言程序很容易变换成算法流程图，那么从算法流程图也就很容易变换成算法状态机图。

【例2-3】一个C语言程序。

#include<stdio.h>

intsample(intfoo)

{intbar

bar=0;

while(bar<foo)

bar=bar+1;

return(bar);

}

众所周知，C语言程序有三种基本结构：顺序结构、分支结构和循环结构。在对程序进行抽象和分配状态时大致可以遵循以下规则：

(1)顺序结构。C语言程序中，顺序结构部分可以归结在一个状态中，因为一般顺序操作中不会改变系统的工作状态。

(2)分支结构。在分支结构中程序将对条件量进行判断，条件不同，程序将转向不同的分支。分支程序的条件量是系统状态的输入，不同条件将转向不同的状态，从而发生状态转移。

(3)循环结构。循环程序以循环变量为条件量，该条件量通常是一个计数值。当计数值达到指定值时，条件满足，状态发生转移，这一点与分支结构相类似。．

【例2-4】C语言程序的流程图如图2-21(a)所示。从该流程图中可以看到，该程序可以分配3个状态：初始状态S0(循环结构之前部分)、循环结构部分状态S1、结果输出状态S2。该C语言程序的状态图如图2-21(b)所示。图中，状态输入信号如下：

fooFlag——foo值刷新标志量；

M——循环计数条件变量；

retFlag——bar值输出标志