（计算机应用技术专业论文）vrc变换算法的硬件实现研究.pdf

摘要 本文主要讨论了矢量光栅变换( v e c t o rt or a s t e rc o n v e r s i o n ) 技术硬件实现中的 些问题，包括宽直线、三角形和二次曲线基本生成算法的硬件实现。首先介绍 了现有的基本图形生成算法，包括三角形边相关扫描算法，宽直线的线刷子算法 及其改进和圆形、椭圆的生成算法，同时介绍了加速算法的研究现状；然后，讨 论了高级语言描述到硬件描述语言的映射，提出了算法到状态机抽象的规律；接 着具体讨论了基本图形的硬件实现，给出了各算法的状态机图，接口定义和实现 框架，并且从理论角度给出了二次曲线加速算法的证明：最后采用软件工具进行 测试验证，给出了模拟、综合实现的结果，并在附录中有详细的实验结果数据。 关键词：矢量光栅变换硬件描述语言加速算法 a b s t r a c t i nt h i sp a p e r , w em a i n l yd i s c u s ss o m ei s s u e so ft h ei m p l e m e n t a t i o no f v r c ( v e c t o r r a s t e rc o n v e r t e r ) i nh a r d w a r e ，i n c l u d i n gt h ei m p l e m e n t a t i o no ft h i c k l i n e ，t r i a n g l ea n d c o n i c f i r s t ，t h e b a s i cr a s t e r g r a p h i c sa l g o r i t h m sf o rd r a w i n g2 dp r i m i t i v e sa r e i n t r o d u c e d ，i n c l u d i n ge d g ec o h e r e n c ea n dt h e s c a n - l i n e a l g o r i t h mo ft r i a n g l e ，b r u s h a l g o r i t h mo ft h i c kl i n e ( a n di t si m p r o v e dm e t h o d ) a n dm i d p o i n tc i r c l ea n de l l i p s e a l g o r i t h m ；a n dt h ec u r r e n ts i t u a t i o no f t h ea d v a n c e da l g o r i t h m si sa l s oi n v o l v e d s e c o n d t h em a p p i n go f h i g hl e v e lp r o g r a m m i n gl a n g u a g et oh a r d w a r ed e s c r i p t i o nl a n g u a g ei s d e s c r i b e d ，s o m ep r i n c i p l e so f t h ec o n v e r s i o no f a l g o r i t h mt os t a t em a c h i n ea r ep r o p o s e d a l s o ；t h e n ，t h ei m p l e m e n t a t i o no fb a s i cg r a p h i c si nh a r d w a r ei sd i s c u s s e di nd e t a i l ，t h e s t a t em a c h i n e sa r ed r a w ni nt h e p a p e r , a n dt h ei n t e r f a c e so f h a r d w a r e a r ed e f i n e d ，b l o c k d i a g r a m st o o ，a n dt h ea d v a n c e da l g o r i t h mo fc o n i ci sp r o v e d ；f i n a l l y , s o m ei s s u e sa b o u t t e s ta r ed e s c r i b e d ，t h er e s u l t so fs i m u l a t i o na n ds y n t h e s i sa r eg i v e ni nt h el a s t ，a n d s o m ed e t a i l e dd a t aa r e d i s p l a y e di nt h ea p p e n d i x k e y w o r d ：v e c t o rr a s t e rc o n v e r s i o nh a r d w a r e d e s c r i p t i o nl a n g u a g e a d v a n c e da l g o r i t h m 第一章绪论 第一章绪论 1 1 矢量光栅变换的研究背景 随着人们对计算机速度的要求越来越高，在专用领域采用通用处理器必然会影 响速度，因此可以将一些基本固定不变的算法采用硬件芯片来实现，这就是软件 的硬化。近些年来蓬勃发展的可编程芯片技术( 如c p l d f p g a ) 以及硬件描述语 言的广泛应用使软件的硬化成为可能，例如在数字信号处理、图形图象处理、神 经网络、专家系统以及视频压缩等方面已得到了成功的应用。在计算机图形学领 域中，矢量光栅变换( v e c t o r t or a s t e rc o n v e r s i o n ) 技术主要应用于计算机的显示 输出设备如显示器、打印机、绘图仪等，其特点为核心算法简单固定，数据量大 和要求的处理速度高，因此非常适合将基本的核心算法固化到专用的芯片上，这 样可以在很大程度上提高处理速度，缓解由速度产生的瓶颈问题，更重要的是当 进行批量生产后可以大大地降低成本。可以说，具有了高速的v r c 处理器将成为 产品在市场上具有竞争力的一个重要标志。 采用硬件描述语言( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 设计数字电路已成为设计 人员的首要选择，h d l 和可编程器件的结合使用能在很短的时间内完成原型 ( p r o t o t y p e ) 系统，大大缩短了产品的上市时间( t i m et om a r k e t ) 。借助强大的 e d a ( 电子设计自动化) 工具和先进的半导体工艺可以很容易地将c p l d ( 包括f p g a ) 转换为a s i c ，进而可以成批量地投片生产，达到了缩短设计周期，降低开发费用 、减小投资风险等目的。同时可以获得宝贵的设计l p 库，使得以后数字电路设计 水平极大提高。所以矢量光栅变换的f p g a a s i c 实现是实现高速v r c 算法而同 时又具有快速的产品原型化及相对小的投资的优良选择。 1 2 论文研究的目的和意义 矢量光栅变换是指把向量描述的图形转换成点阵位图的过程，它是任何点阵式 输出设备输出图形所不可缺少的重要环节一j 。 点阵式图形输出设备主要包括有静电式、热敏式、喷墨式、热转印、激光式和 电子照相式等几种方式，其中以静电式绘图速度最快。为了提高出图速度和质量 要求v r c 的处理速度尽可能快且精确，这是影响图形输出设备性能的关键因素之 一，设法提高其速度以便与图形的输出速度相匹配就成为研究的核心。 目前的国外厂商，如h p ，c a l c o m p ，v e r s t a t e c 等，v r c 的实现上大多 采用高速微处理器或a s i c 芯片，取得了良好的效果，达到了较高的处理速度。但 v r c 变换算法的硬件实现研究 是这些技术是严格保密，有的还申请了专利，这就形成了一定的技术垄断，限制 了国内厂商的发展。在国内，我校外设所已在“八五”军事预研项目“高精度彩 色静电绘图机”中，开始了对v r c 的研究，经过不懈的努力，已经形成了多年的 积累并取得了相应的成果。本论文就是在此基础上，进一步将图形学中一些基本 算法硬件实现，并对其进行性能分析，而且在算法级上对加速方法进行了研究。 除了上述的实用价值外，论文还通过对v r c 算法的研究，总结出了一般高级语 言算法抽象与硬件描述语言抽象的映射关系，试图以此对一般算法硬件实现有所 帮助，使得设计更加规范化，提高设计效率。 矢量光栅变换技术具有通用性，研究成果可直接用于高速点阵式输出设备上， 如高速静电绘图机与喷墨绘图。用于绘制高精度的军事电子地图，以及为满足战 场上临时快速输出军事态势图与地形图的需要，而在民用领域，所开发的产品亦 可用于电子设计自动化，机械建筑图纸，超大规模集成电路版图的绘制。总之， v r c 技术具有广阔的市场前景，将在军用和民用绘图打印领域发挥巨大作用。 1 3 论文的主要工作 本论文是在西安电子科技大学外设所申请的“九五”军事预研项目“高速矢 量光栅变换技术研究”和西安电子科技大学计算机学院三零一教研室“高速矢量 光栅变换技术的a s i c 研究”。h 】课题的基础上展开的。 至今为止，论文完成的工作包括： 1 通用高级语言描述的算法抽象到数字系统抽象转换问题的讨论，主要是顺 序结构的c 语苦描述到并行结构的v h d l 语言描述转换问题。 2 基本图形的矢量光栅变换v h d l 实现、模拟和验证。 2 1 宽直线的生成转换 以三角形为线头的宽直线线刷子算法实现，完成了以b r e s e n h a m 算法、中点画 线和d d a 为边线生成方法的线刷子算法的硬件描述实现，并讨论了三种方法的性 能。 2 2 三角形的生成转换 主要提出了一种基于等差数列性质的三角形生成方法，并对此进行了证明，分 析了和传统的扫描线相关算法的差异，指出了在硬件实现方面的优点。 2 3 二次曲线的生成转换 完成了圆的扫描转换算法的硬件实现和椭圆的双步增量生成算法实现，并且从 理论层面上，重点讨论了在直线和园的双步增量方法基础上，提出了一种椭圆的 双步增量生成方法，给出了数学证明和相关实验的结果。 3 采用相应的e d a 软件对上述各算法进行综合、模拟和验证。 第一章绪论 所使用的软件包括有：m a x + p l u s i i9 5 、f p g ae x p r e s s 3 1 、a c t i v e h d l 3 1 以及x i l i n xf o u n d a t i o n l 2 。 接下来，首先给出现有的矢量光栅变换基本算法，这些算法是实现硬件化的基 础，以后的各种实现方法都是在此基础上展开的。 4 v r c 变换算法的硬件实现研究 第二章矢量光栅变换基本算法 本章简要介绍各类常见的矢量光栅变换( v r c ) 算法，包括三角形、宽直线和二 次曲线生成算法，并对各类算法的性能进行简要的分析，最后，讨论针对这些算 法的加速方法的研究情况。 2 1 三角形生成算法 三角形是最简单的多边形，对三角形的处理可以按照多边形填充的方法进行。 现有的方法有扫描线相关算法，边填充算法以及种子填充算法等。这里仅介绍扫 描线相关算法，其它算法可以参见文献 1 ，2 ，3 。 一般三角形的填充过程，对于一条扫描线，可以分为四个步骤： 1 求交：计算扫描线与三角形的交点，一般为两个； 2 排序：把所有交点按x 方向进行排序； 3 交点配对：确定三角形内部区间； 4 三角形生成：输出区间内的点。 扫描线相关算法主要利用了扫描线和三角形边的相关性：第i 条扫描线与多边 形的边相交，则第i + l 条扫描线也很可能与这条边相交，如图2 1 所示。为此算法 采用了两个较为复杂的数据结构实现边相关性，即活性边表( a e t ) 和边表( e t ) 。其 中活性边表是保存当前扫描线与各边交点的链表，边表是保存多边形各边最低点 所处扫描线位置的链表。算法根据活性边表来判断填充多边形，并依据活性边表 和边表信息更新、排序。详细情况请参见文献 1 ，2 】。 图2 1 扫描线相关三角形填充 由于扫描线相关算法是针对一般多边形提出的，所以当应用于三角形时，活性 边表和边表就显得复杂了，其中排序更新不适合硬件实现，并且采用浮点运算使 得效率不高。因此针对三角形有必要提出新的填充方法，以适应硬件化的要求。 第二章矢量光栅变换基本算法 2 2 宽直线生成算法 我们所熟悉的经典直线扫描转换算法都是单象素直线的生成。这些算法已经很 成熟，如数值微分法( d d a ) 、b r e s e n h a m 算法、中点画线法等 1 ，2 】。然而实际应 用中直线的绘制都是有一定宽度的，所以对宽直线生成算法的研究更具有实际价 值。这里指的宽度是宽直线两平行边的垂直距离。 2 2 1 宽直线线宽的处理 宽直线线宽的处理一般采用所谓的“刷子”原理，也就是顺着扫描所生成的单 象素线条轨迹，移动一把具有一定宽度的“刷子”来获得。“刷子”的形状可以是 线段或正方形。根据刷子形状的不同，可分为线刷子、方刷子、圆刷子等| 5 】。 线刷子算法，也称为复制象素法，是将宽线的中心线象素沿着垂直于主轴的方 向复制，复制的个数等于线宽。直线斜率在 _ 1 ，1 之间时，刷子置成垂直方向，刷 子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，完成一次刷的 动作。当斜率不在【1 ，1 之间时，只需把刷子置成水平方向。算法简单、效率高是 线刷子的优点。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，宽 线两端就很不自然了，尤其当两条宽线相交时，汇合处将有缺口出现。而且宽直 线不是旋转不变的，也就是说直线的绘制线宽会随着斜率的变化而改变。水平线 和垂直线最粗，与指定线宽相等，而对角线的宽度仅为指定线宽的1 4 2 ( 约o 7 倍) 。最后，因为将刷子起始点定位在宽线中心会引起在采用线刷子绘制线宽为偶 数个象素时，线条要么多一个象素，要么少一个象素。文献 5 】中的图2 4 和图2 5 给出了利用线刷子绘制宽直线的例子。 方刷子和圆刷子分别采用正方形和园形完成刷子动作的。方刷子同样存在着线 头粗糙，线宽随斜率变化的缺点，而且方刷子的效率比线刷子低。圆刷子的优点 是效果非常突出，线宽不随斜率变化，线接头不用特殊处理，适合曲线的绘制， 但是实现的复杂度要比线刷子和方刷子大得多，对硬件实现不太适合。 当然，除了刷子方法外也可以采用区域填充的算法处理宽线。这时将宽直线看 成为四边形，采用多边形填充算法进行处理。这种方法可以得到效果比较好的宽 线，同样该方法比刷子算法麻烦，而且要有复杂的数据结构( 边表、活性边表) 支持以及复杂的操作，例如一般情况下需进行两次添加边和删除边的操作，判断 当前边是否处理完是必须的，会增加时间开销。 6 v r c 变换算法的硬件实现研究 2 2 2 宽线线头的处理“3 除了线宽和线长的定义外，宽直线还包括直线终端( 线头) 和直线接头两个属 性。一般线头分为四种，平头端、方头端、三角端和圆头端，如图2 2 所示。 口口面 平头端方头端三角端圆头端 图2 2 四种直线终端 当两条直线相交时，如果不进行接头处理，那么在相交处会产生不良效果，只 有圆形线头能很光滑，其它的终端则会有空隙或毛刺。因此在要求高的场合时就 必须进行额外的线间接头处理，图2 3 给出了四种类型的接头。 丝丝丝丝 斜削接头 2 2 3 线刷子的改进 斜切接头三角接头圆形接头 图2 3 四种类型的接头 5 ，9 】给出了线刷子的改进算法，主要的改进包括：调整了线刷子的宽度和重新 定义了新的运动轨迹。下面就以平头线刷子的处理过程来具体说明改进算法。整 个处理过程大体分为主线生成、宽度绘制、线头处理三大步骤。 主线生成 主线生成就是利用基本直线生成算法根据宽线端点生成刷子的主干线。这里存 在如何选择主干线问题，如果以中心线为主干线，那么当线宽为偶数个象素时就 会有一个象素的误差；如果以边线为主干线，那么当线宽为偶数个象素时就会有 1 2 个象素的误差，由此可见应当选择边线为主干线。为了适合硬件实现应当选取 中点线扫描转换或者b r e s e n h a m 算法来生成主干线。 宽度绘制 宽度绘制就是根据线宽沿一定的方向复制主干线上的点完成刷子动作。由于扫 描线是水平的或是垂直的，而线宽方向却是任意的，那么若以实际线宽复制，结 果必然产生误差，当绘制水平或垂直线时误差为零，对角线时误差为最大。解决 第二章矢量光栅变换基本算法 这一问题的方法是进行宽度变换，根据三角关系推导出复制线宽和实际线宽的关 系，采用复制线宽进行实际象素复制。当然这种方法也是一种近似，因为三角函 数的引进必然有误差而且增加计算复杂度，硬件实现会有一定的困难。 线头处理 线头指宽线两端部分，进行线头处理就是一种对宽线相交部分的反走样，减少 锯齿形状的出现。线头可以是三角形、圆形等。同样，三角形简单效果不佳，圆 形复杂效果好。无论哪种线头，处理过程就是一个区域填充过程。但是这些方 法均是采用复杂的数据结构的软件程序解决的，考虑到硬件实现会有一定的复杂 度，比如建立链表v h d l 就无能为力，得采用转换办法。对于三角形线头，经过 分析可以不用专门来处理，如图2 4 所示： d a d a ( a )( b ) 图2 4 宽直线的分割 图2 4 ( a ) 是常用的分割方法，先处理e b f d 进行宽线绘制，然后处理a b e 和d f c 。那么采用扫描线相关算法时就得求扫描线与三角形的交点然后填充。图 2 4 ( b ) 是一种新的分割方法，先计算出落入a b e 和d f c 的判别式，然后对a a c d 进行宽线绘制，但在d d 和e a 段时需利用得到的判别式对象素进行判别，以决 定是否绘制，这样做避免了求交和复杂的数据结构。 2 3 二次曲线生成算法 在矢量光栅变换研究中不能仅有直线( 包括单象素和宽直线) 还应有曲线的生 成。二次曲线是曲线当中最基本的也是最简单的，我们仅研究圆和椭圆的矢量光 栅变换，包括基本算法，加速算法和硬件实现。本节介绍基本生成算法。 2 3 1 圆的生成算法 圆形是对称性最好的图形，不需要对整个圆域进行扫描转换，只要能生成8 分 园，那么圆的其它部分可通过一系列的简单反射变换得到。假设已知一个以原点 为圆心的圆上一点( x ，y ) ，根据对称性可得另外七个8 分园上的对应点( y ，x ) ， v r c 变换算法的硬件实现研究 ( y 一x ) ，( x ，- y ) ，( - x ，- y ) ，( - y - x ) ，( 一y ，x ) ，( - x ，y ) 。因此，只需讨论8 分园的扫描 转换。一般地采用中点画圆法和b r e s e n h a m 画圆法来生成8 分园。下面讨论中点 画圆法，考虑中心在原点，半径为r 的圆第二8 分园，如何从( 0 r ) 到( r 4 2 ，p , ：4 2 ) 顺时针地最佳逼近于该圆弧的象素序列。假设x 坐标为x 。的象素中与该圆弧最近 者已确定，为p ( x p ，y p ) ，那么，下一个象素只能是正右方的p l ( x p + l y p ) 或右下 方的p 2 ( x d + l ，y p - 1 ) 两者之一。如图2 5 所示。 p ( x by p ) p l 、 n 盯 p 2 一| 、 图2 5 圆生成不意 构造函数： f ( x ，y ) = x 2 + y 2 一r 2式( 2 1 ) 对于圆上的点，f ( x ，y ) = 0 ；对于圆外的点，f ( x ，y ) o ；而对于圆内的点，则有 f ( x ，y ) 0 。设m 是p l 和p 2 的中点，那么m = ( x p + 1 ，y p - 0 5 ) 。所以，当f ( m ) o 时，这表 明p 2 距离圆弧更近，取p 2 作为下一象素。当f ( m ) = 0 时，在p 1 与p 2 之中随便取 一个即可，这里约定取p 2 作为下一象素。至此可按照直线的中点线算法，构造判 别式： d = f ( m ) = f ( x p + 1 ，y p 一0 5 ) = ( x p + 1 ) 2 + ( y p - 0 5 ) 。影式( 2 - 2 ) 若d 0 ，则应取p l 为下象素，而且再下一象素的判别式为 d = f ( x 口+ 2 ，y p - 0 5 ) = ( x p + 2 ) 2 + ( y p - 0 5 ) 2 一r 2 = d + 2x p + 3 式( 2 3 ) 所以，沿正右方向，d 的增量为2x 。+ 3 。 如果d 0 ，则p 2 是下象素，判别式为 d = f ( x p + 2 ，y p - 1 5 ) 2 ( x p + 2 ) 2 + ( y p 1 5 ) 2 r 2 = d + 2 ( x p - y p ) + 5 式( 2 4 ) 所以，沿右下方向，d 的增量为2 ( x p - y p ) + 5 。详细实现可参见文献【l ，2 】。 2 3 2 椭圆的生成算法 与圆形的情况类似，椭圆也可以采用中点画算法。注意到椭圆的对称性，我们 也只用生成第一象限的椭圆弧。在处理这段椭圆弧时，进一步以弧上斜率为1 的 点( 即法向量两个分量相等的点) 作为分界将其分为两部分：上部分和下部分， 第二章矢量光栅变换基本算法 然后采用中点线算法分别处理。具体情况可在相应的图形学书【l ，2 ，3 中查到，这里 就不详细叙述。 2 4 已有加速算法的研究 为了提高矢量光栅变换的速度，不少学者针对现有的算法进行研究，提出了许 多加速算法。这些新方法多是在算法级的改进，着眼点是基本图形的性质如对称 性和离散光栅平面的曲线轨迹特性。本论文在前人的工作基础上也提出了一种新 的关于椭圆加速算法的证明，这一方法将放在以后章节作详细论述，这里仅介绍 直线的步距长度片算法和双步增量算法。 2 4 1 直线的步距长度片算法 直线的步距长度片( r u n l e n g t hs l i c e ) 算法实际上是基于b r e s e n h a m 算法的加 速方法，它是根据当直线斜率小于l 时每条扫描线上象素序列的数目是规律性地 改变。在 1 0 ，1 1 中给出了步距长度片的证明和算法，定理如下： 定理2 1 设直线的斜率k 满足1 2 ( n + 1 ) k l 2 n ，n 为正整数，则： a 第一行除端点外输出n 个象素； b 第二行输出的象素数目为2 n ，2 n + l 二者之一。 定理2 2 设直线的斜率k 满足1 2 ( n + 1 ) k s l 2 n ，n 为正整数，则任意中间行 上输出的象素数目为2 n ，2 n + l 二者之一。 因为扫描线每增加一次就可以确定一段直线上的点，所以利用步距长度片可以 在小斜率情况下大大提高直线的生成速度。但采用这种方法来处理线刷子时，就 需要在每一段中选择一个点作为扫描起始点，这种选择直接影响线刷子的绘制效 果。如果对每一段中的任意一点均向右复制w b r u s h - 1 个点，不但会重复写同一个 象素多次，而且会产生毛刺。同时也存在因每一段长度不定，读入帧缓存时位数 不能对齐的问题。 2 4 2 直线的双步增量算法 直线的双步增量( d o u b l e s t e pi n c r e m e n t a l ) 算法【7 】是根据离散光栅平面的曲线 轨迹性质，即当每一次循环的步长为2 且斜率一定时，直线将呈现四种模式。例 如当斜率k ( 0 ，1 ) 时，直线是下列四种模式之一，见图4 1 5 。这样只需在每一循 环内部判断直线所形成的四种模式，每一次操作就可以得到两个未知点，使速度 提高近一倍。利用对称性可以得到直线双步对称( d o u b l e s t e ps y m m e t r y ) 法。双步 v r c 变换算法的硬件实现研究 对称法是在双步增量法的基础上更进一步的改进，利用了直线关于中点对称的原 理来生成整个直线，那么由于直线关于中点对称则只需生成直线的一半就可以完 成整个直线的生成。文献 6 】中的实验结果表明采用双步对称法生成直线速度可以 比传统的b r e s e n h a m 算法有显著提高。 至此，已对基本的矢量光栅变换算法作了介绍，有了高级语言的算法描述对实 现硬件还不够，必须将这种算法描述转换为数字系统能够实现的描述，也就是硬 件描述语言。如果能够找出这两种描述之间的关系，对数字系统的实现将是很有 意义的。那么在下一章将讨论算法抽象到硬件实现的映射问题。 第三章算法抽象与硬件实现的映射 第三章算法抽象与硬件实现的映射 现实中算法多采用高级语言进行描述，这种方法是一种高层次的抽象，可以说 是软件抽象，在进行对算法的硬件实现时就必须考虑高级语言到硬件结构的转换 问题，具体讲就是顺序结构的c 语言到并行结构v h d l 语言的映射。当然，这种 转换不可能是严格意义上对一的映射，但是其中仍有一些规律可以遵循，这就 是本章主要讨论的问题。我们首先论述数字系统设计的基本方法，其中包括硬件 描述语言的介绍，接着对状态机( s t a t em a c h i n e ) 进行描述，最后给出高级语言结 构的状态机抽象。 3 1 数字系统设计的基本方法 我们所论述的设计方法是基于硬件描述语言的，因此有必要对硬件描述语言作 简单介绍。 3 1 1 硬件描述语言简介 硬件描述语言英文全称是h a r d w a r ed e s c r i p t i o nl a n g u a g e ，简写做h d l 。在 h d l s 的发展过程中，标准化起了非常重要的作用。正是由于标准化7 j 。使得有了一 整套的方法理论，从方法论的高度对硬件描述作了理论概括，便于设计人员的交 流。值得一提的是v h d l 语言标准的产生，它是1 9 8 7 年i e e e 正式通过的第一个关 于硬件描述语言的国际标准，并于1 9 9 3 年进行了修订。在此之后，相继公布了几 个标准，如v e r i l o gh d l 。二十世纪九十年代h d l 得到了进一步的发展，许多应用 场合都采用了h d l ，这也推动了它的发展【8 j 。 在硬件设计领域中，硬件描述语言使设计硬件更类似于设计软件，从源程序到 编译然后仿真并下载于可编程逻辑器件，完成设计，这一过程是与传统设计截然 不同的。可以说，传统设计方法是以自下而上为特征的，基于h d l 的设计方法则 是以自顶向下为显著特征的，自顶向下是基于代码生成，仿真和综合等过程的， 这些正是e d a 工具提供的。在各种h d l 的环境中都提供从编译，综合，仿真以至 下载的工具，设计的整个过程与开发软件系统类似。 具体到本文采用的v h d l 语言来说，v h d l 更类似于a d a 语言。基本的v h d l 程序由实体( e n t i t y ) 和构造体( a r c h i t e c t u r e ) 等构成，采纳了a d a 中的包( p a c k a g e ) 和配置( c o n f i g u r e ) 等结构，因此显得结构清楚，语法严格。具有以下特点： v r c 变换算法的硬件实现研究 a v h d l 语言标准、通用且易于共享和复用； b v h d l 支持基于对象的自顶向下设计的描述 c v h d l 支持测试台的描述； d 设计独立于工艺； e 便于f p g a 向a s i c 转换。 3 1 2 数字系统设计层次 数字系统设计通常都是分层次的，不同的设计人员在不同的层面上设计，比如 有的设计人员负责版图设计，有的则负责高级语言的模拟等。这种层次是一种逻 辑地抽象，认识这种层次性有助于全面了解数字系统设计。一般认为设计的表示 包括两个层次即技术层次和规模层次，如表3 1 所示4 表3 1 数字系统设计分层表示 、垫术层次 l 规模层次、行 为结构物理 c p u ，存储器控制芯片，模块，电路 l系统级性能描述器以及总线间的板及系统物理划 互连分 算法级( 子系统级i o 应答算法( 数硬件模块部件之间的物理 或芯片级)据结构操作)数据结构连接如f l o o r p l a n 并行操作，寄存器a l u ，多路器，寄 寄存器传输级传输，状态序列( 状存器，总线，微控芯片，宏单元等 ( r t l )态表)制器及其连接 逻辑级布尔方程门，触发器等标准单元布图 电路级微分方程晶体管，电阻等晶体管布图 行为级描述一个设计的基本功能，或者说该电路，或设计应该做些什么。从概 念上讲，纯行为是输入和输出关系的描述，例如布尔方程就是组合逻辑网络的行 为描述。 结构级描述逻辑结构，或者说描述设计的抽象实现，典型的是抽象模块相互连 接的网表例如在r t l 级，抽象模块是a l u ，多路选择器。 物理级描述设计的物理实现，或者说把结构级的抽象元件代之以真正的物理元 件。在所有级别里，速度，功耗，面积通常是物理领域的一部分。 人们也采用设计空间来表示，这时行为、结构和物理分别是设计空间中的个 维度，可见 2 8 中相应的表示图。 第三章算法抽象与硬件实现的映射 3 1 3 数字系统设计流程 采用硬件描述语言设计数字系统是一种被称作自顶向下的设计方法即 t o p d o w nd e s i g n ，而传统的方法则是相反的，即自下向上的方法。自顶向下的设 计方法的特点之一就是可以快速原型化( r a p i dp r o t o t y p i n g ) ，其中一般涉及如下几 个主要任务： a 系统需求分析( s y s t e mr e q u i r e m e n t ) b 算法描述( a l g o r i t h md e s c r i p t i o n ) c 控制流图和数据流图建模( d f g c f gm o d e l i n g ) d 体系结构建模( s y s t e ma r c h i t e e t u r em o d e li n g ) e 具体设计( d e t a i l e dd e s i g n ) f 系统验证( s y s t e mv e r if y ) g 设计发布( d e s i g nr e l e a s e ) 本文将主要讨论有关算法描述和状态机部分，其它部分可以参见 4 中详细论 述。 3 2 算法的状态机描述 算法描述可以分解为控制部分和功能部分，控制部分可以用有限状态机描述， 而功能部分，也就是数据部分是接受控制信号进行处理的。那么可以将一个算法 的执行视为若干状态的转换过程，当系统处于某一状态时进行特定的操作。本节 首先给出有限状态机的定义，然后讨论两种类型的状态机和其v h d l 实现。 3 2 1 有限状态机( f i n i t es t a t em a c h i n e ) 有限状态机定义了输入序列和输出序列之间的映射，强调时间序列的概念，采 用时序机的数字模型来描述 1 3 , 1 6 1 。其中以时序机的当前状态来表示先前的输入对 输出的影响。如果将所有可能输入的集合记做i ：而将所有可能的输出的集合记做 0 ；所有可能的时序机状态集合为s ，则时序机操作如下：假定初始状态s s ， 输入i j i ，则产生输出z 。0 ，转向状态s 。s 。其中z 。和s 。都唯一地由s 。和 i i 所确定。因此，任一时刻有限状态机的输出，决定于它的当前状态和输入并且当 前状态和输入也确定了有限状态机的后继状态。由此可断言，时序函数能描述状 态数目有限的时序机，并将它表示成一个五元式： m ( s ，i ，0 ，n ，z ) v r c 变换算法的硬件实现研究 其中后继状态函数( 状态转换函数) 为 记作： 而输出函数为 n ：s i _ s n ( s i ，b ) z ：s i _ o 记作：z ( s 。，l ) f s m 有限状态机的分类： ( 1 ) 自主的有限状态机 输入集合i 为空集的有限状态机称为自主的有限状态机，表示如下： n ：s s z ：s 一0 ( 2 ) m o o r e 和m e a l y 型 m o o r e 机具有非空的输入，其输出仅取决于该状态机所处的状态，不管输入如 何变化，只有在状态改变时输出才改变。 m e a l y 机输出不仅取决于状态，而且还取决于其非空的输入集，即 z ：s i o m e a l y 型状态机输出的变化，先于m o o r e 型状态机输出的变化。具体讲，m e a l y 型状念机输出是在输入变化后立即发生变化：而m o o r e 型状态机在输入发生变化 后，还必须等待时钟的到来，时钟使状态发生变化才导致输出变化。因此要多等 待一个时钟周期。 3 2 2m o o r e 型状态机的硬件描述 m o o r e 型状态机的框图见图3 1 ，其输出仅是状态向量的函数。采用硬件描述 语言( v h d l ) 实现时，结构体部分一般包括3 部分：说明部分、时钟同步的进程 和组合进程。下面以一个实例说明具体的描述方法 1 2 , 1 4 1 。 e n t i t yd e m oi s p o r t ( c z k ，i n p u t ，r e s e t ：i ns t d _ l o g i c ； o u t p u t ：o u ts t d _ l o g i c _ v e c t o r ( 3d o w n t o0 ) ) ； e n d d e m o ； a r c h i t e c t u r em o o r e0 fd e m oi s t y p es t a t e t y p ei s ( s o ，s l ，s 2 ，s 3 ) ； s i g n a ls t a t e ：s t a t et y p e ； b e g l n d e m o _ _ p r o e e s s ：p r o c e s s ( c l k ，r e s e t ) 一状态说明 一时钟进程 第三章算法抽象与硬件实现的映射 l n b e g i n 1 fr e s e t = 1 t h e n s t a t e 1 f i n p u t 2 1 t h e n s t a t e i f i n p u t 2 0 t h e n s t a t e o u t p u t o u t p u t o u t p u t o u t p u t - “1 1 1 l ”： e n d c a s e ； e n d p r o c e s s ； e n d “。； 寄存器 1 5 一状态机复位 一组台进程 ( 1 ) 说明部分 图3 1m o o r e 型状态机框图 t s 1 6 v r c 变换算法的硬件实现研究 说明部分中有类型s t a t e _ t y p e 和信号s t a t e 的说明。状态类型一般用枚举类型， 其中每个状态名可任意选取。 ( 2 ) 时钟进程： 时钟进程对状态机的时钟信号敏感，当时钟发生有效跳变时，状态机的状态发 生变化。状态机的下一状态取决于当前状态和当前输入信号值。在检查到时钟发 生了有效跳变之后，使用c a s e 语句检查状态机的当前状态，然后使用i f - t h e n e l s e 语句决定下一状态。 ( 3 ) 组合进程： 组合进程根据当前状态给输出信号赋值。 3 2 3m e a l y 型状态机的硬件描述 m e a l y 型状态机和其等价的m o o r e 型状态机相比，其输出变化要领先一个时钟 周期。m e a l y 型状态机的框图见图3 2 ，其输出既和状态向量有关，又和所有输入 信号有关。构造m e a l y 型状态机的方法和m o o r e 型状态机相同，唯一的区别是： 组合进程中的输出信号是当前状态和当前输入的函数。同样以一个实例说明具体 的描述方法【1 2 1 “。 e n t i t yd e m oi s p o r t ( c l k ，i n p u t ，r e s e t ：i ns t d _ l o g i c ； o u t p u t ：o u ts t d _ l o g i c ( 3d o w n t o 0 ) ) ； e n dd e m o ； a r c h l t e c t u r e m e a l y o fd e m oi s t y p e s t a t e _ t y p ei s ( s 0 ，s 1 ，s 2 ，s 3 ) ； s i g n a ls t a t e ：s t a t e t y p e ； b e g i n d e m oo r o c e s s ：p r o c e s s ( c l k ，r e s e t ) b e g l n i fr e s e t = l t h e n s t a t e i f i n p u t = 1 t h e n o u t p u t 2 “0 0 0 0 ： e l s e o u t p u t i f i n p u t = 1 t h e n o u t p u t 2 “1 0 0 0 ”： e l s e o u t p u t = “1 0 0 1 e n d i f ； e n d c a s e ； e n dp r o c e s s e n d m e a l y ； l n p 图3 2m e a l y 型状态机的状态图 一组合进程 1 7 1 8 v r c 变换算法的硬件实现研究 3 3 高级语言结构的状态机描述 高级语言通常是采用串行结构描述，其主要的结构是顺序、循环、判断三种描 述方式，必须想办法抽象出其并行结构才能进行硬件实现。实际系统中往往是针 对某一特定算法进行抽象得到并行结构，然后画出有限状态图，从而得到控制机 构和数据结构部分。如果采用h d l 来描述有限状态机，那么就可以利用综合器完 成剩余的工作得到最后的数字电路。那么是否能够直接利用h d l 来描述算法昵? 对于一些简单的算法是完全可以直接用h d l 来描述，如计数器等。但对于更多的 算法用h d l 直接描述就不适合了，这是因为h d l 主要是用来描述并行结构的， 它的基本描述单元就是进程这样的并行语句。这样能得到一种将算法抽象出状态 机的一般方法就变得十分有意义。进行这方面的工作将涉及高级综合的知识包括 调度和分配。可以说有限状态机是高级综合的一部分，提供调度和分配的输入。 一般的方法是先得到算法的控制流图和数据流图，然后根据c d f g ( c o n t r o ld a t a f l o w g r a p h ) 得出有限状态机。因此首先应能得出c d f g ，图3 3 给出了一个c d f g 的例子： v o i de x a m p l e ( v o i d ) i n tp c o l d p c ； p p c d c ： p o p c = o l d p c ； o b u s = i b u s + 4 ： i f ( b r a n c h = = 1 、 p c = b r a n c h p c ； v ，h i l e ( i r e2 = 1 ) ； o l d p c = p c ； p c = p c + 4 ； ) 以上是一段v h d l 的顺序执行进程它可以视为某种算法的描述。图3 3 是对 应的c d f g 流图。在得到流图之后就可以根据系统的资源来抽象有限状态机，进 行调度和分配。这方面i b m 的综合系统h i s 2 4 1 、n e c 的综合系统c y b e r 2 卯、s t a n f o r d 的综合系统h e r c u l e s 和h e b e 2 6 1 等已经做到了从算法描述到流图的变换，可是仅能 够得到这些系统介绍性的论文，具体实现细节无法得知。根据现有的分析发现可 以利用算法的特有结构来判断状态，大体规则是顺序结构可以是同一的状态：判 。2 3 4 5 6 7 8 加 9 第三章算法抽象与硬件实现的映射 断结构是状态迁移的条件，条件变量则是控制信号；循环结构是采用计数器作控 制器的一种结构，也可以将循环条件抽象成新的控制信号。这样可以设计程序用 来识别控制信号，进而得出状态迁移条件，然后得到状态图。这一程序主要涉及 编译器的相关知识，如词法分析、语法分析等。如果设计程序，就必须限制算法 语言集，细化状态抽取规则，确定状态产生式。 c f g 4 b r a n c h 汀( 6 n s 川一 、r _ 、 一 、 i r e 、 、一净 釉 1 d f g 图3 3 c d f g 流图 顺序( s e q u e n c e ) 结构是指两条语句的执行有先后次序，在图3 3 的c f g 中表 现为两个结点的一个是另一个的前驱，例如结点8 是结点9 的前驱。顺序语句在 执行时可以认为是立即的，那么构造f s m 时就可以将顺序语句合并构成系统的一 个状态。 t 耋ol v r c 变换算法的硬件实现研究 判断( c o n d i t i o n a le x e c u t i o n ) 结构是指一条语句有不止一个后继，但只有一个 后继被执行，在没有执行时系统的状态是不确定的，那么这将引起系统状态的迁 移，条件则是一个布尔表达式。例如结点4 和结点7 都有两个后继，结点4 的判 别条件是布尔变量b r a n c h ，当b r a n c h 为真时转向结点5 ，否则转向结点6 ；而结点 7 的判别条件则是布尔变量i r e o 因此，在f s m 中就可以用不同的状态来体现这种 程序结构，状态的转换条件就是布尔表达式，不过当有多个条件时就必须考虑各 个转换条件的逻辑关系。 循环( i t e r a t i o n ) 结构是指在程序中包含环路，例如结点7 和结点1 0 。循环结 构在构