（计算机应用技术专业论文）基于功能模块的大规模rtl组合电路分层测试产生算法研究.pdf

摘要f 随着数字计算机日益广泛的应用，数字系统的可靠性越来越显得重要。为了提高系、统的可靠性，系统在设计和制造过程中以及运行过程中都需要进行测试l 本文主要是对大规模、超大规模集成电路寄存器传输级( r t l ) 的自动测试产生算法进行研究。一一r 一。一一一一一一一一本文根据超大规模集成电路自动测试产生要求，设计了r t l 电路的数据结构e t b l 。e t b l 能更方便、更有效地访问r t l 电路的结构及功能信息，更有利于进行自动测试产生。并且实现了相应的格式转换器，将v e r i l o gh d l 描述的i s c a s - - 8 5 和i s c a s - - 8 9系列的r t l 电路转换为e t b l 描述的能运用于r t l 电路测试产生的内部数据结构。本文在e t b l 描述的r t l 电路结构的基础上，进行r t l 组合电路自动测试产生算法、的研究，提出了两个基于结构的r t l 组合电路分层测试产生算法。这两个算法主要通t过对电路按结构、功能划分为功能模块，然后利用功能模块的测试集进行r t l 电路测试产生。并且在i s c a s - - 8 5 和i s c a s - - 8 9 系列v e r i l o gh d l 描述的b e n c h m a r k 电路上分别应用这两种算法进行自动测试产生。实验数据表明分层测试产生算法能大大压缩电路测试集( 约为6 6 ) ，而故障覆盖率有略微下降，时间性能也有些许降低。实验结果证明分层测试产生算法能提高测试产生效率、降低测试产生复杂度，并且简化电路结构和功能信息。算法同时也为实现并行测试产生提出了一个基于电路结构而不是基于电路7故障的并行思想。，)a b s t r a c tr e l i a b i l i t yo fd i g i t a ls y s t e m si sm o r ea n dm o r ei m p o r t a n tw i t ht h ew i d eu s eo fd i g i t a lc o m p u t e r s f o ri m p r o v i n gt h er e l i a b i l i t yo fs y s t e m s ，t h e ya l ln e e dt ob et e s t e di nd e s i g n i n g ，m a n u f a c t u r i n g ，a n df u n c t i o n i n gs t a g e s t h i sd i s s e r t a t i o nf o c u s e so na u t o m a t i ct e s tg e n e r a t i o n ( a t p g ) a l g o r i t h m sf o rv e r yl a r g e s c a l ei n t e g r a t e dc i r c u i t sa tr e g i s t e r 。t r a n s f e r l e v e l ( r t l ) t h i sd i s s e r t a t i o nd e s i g n sad a t as t r u c t u r e e t b l f o rr t lc i r c u i t sf o rv l s ia t p ge t b lc a nc o n v e n i e n t l ya n de f f i c i e n t l ya c c e s st h es t r u c t u r ea n df u n c t i o ni n f o r m a t i o no fr t lc i r c u i t sf o ra t p g t h i sd i s s e r t a t i o np r e s e n t saf o r m a t - t r a n s f o r m e r , w h i c hc a nn - a n s f o r r ni s c a s 一8 5a n di s c a s 一8 9b e n c h m a r k sv e r i l o gh d ld e s c r i p t i o n st oi n n e rd a t as t r u c t u r e e t b l a p p l i e di nr t la t p g b a s e do nr t lc i r c u i t ss t r u c t u r ed e s c r i b e di ne t b l - t h i sd i s s e r t a t i o np r e s e n t st w oh i e r a r c h i c a 】a t p ga l g o r i t h m sb a s e do ns t r u c t u r ef o rr t lc o m b i n a t i o n a lc i r c u i t s t h et w oa l g o r i t h m sg e n e r a t et e s t sf o rr t lc i r c u i t sb yt e s ts e t sf o rm o d u l e sw ea p p l yt h et w oa l g o r i t h m st og e n e r a t et e s t sf o ri s c a s 一8 5a n di s c a s - 8 9b e n c h m a r k s t h ee x p e r i m e n t a lr e s u l t si l l u m i n a t et h eh i e r a r c h i c a lt e s tg e n e r a t i o na l g o r i t h mc a ng r e a t l yd e c r e a s et h es c a l eo ft e s ts e t s ( a b o u t6 6 1 ，b u tt h ef a u l tc o v e r a g ea n dt i m ep e r f o r m a n c ea r el o w e rt h a ng a t e l e v e lt e s tg e n e r a t i o n t h ee x p e r i m e n t a lr e s u l t sa l s ot e s t i f yt h a tt h ea l g o r i t h mc a nd e c r e a s et e s tg e n e r a t i o nc o m p l e x i t ya n ds i m p l i f yt h ec i r c u i ts t r u c t u r ea n df u n c t i o ni n f o r m a t i o n i na d d i t i o n ，t h ea l g o r i t h ma l s oe n a b l e st h ep o s s i b i l i t yf o rh i g h l ye f f i c i e n tp a r a l l e la t p g 基于功能模块的大规模r t l 级组合电路分成测试产生算法研究第1 章绪论1 1数字系统测试的发展概况及基本知识随着数字计算机日益广泛的应用，数字系统的可靠性越来越显得重要。近年来，由于超大规模电路的出现，使得早期的人工测试和基丁穷举测试的功能的完全检查方法已难以满足实际需要，因而逐渐被自动测试所取代。所谓自动测试，即自动推导被测电路( c u t ) 的测试码，自动对c u t 的输入加载测试激励并回收其输出的测试响应，自动给出c u t 的故障征兆指示并孤立故障。此过程的难点是自动推导测试，即通常所说的测试生成。对测试的发展历史，可简要追述如下：早在1 9 5 9 年，e l a t e d 首先倡导用计算机自动推导测试，并用一维通路敏化法推导了d 一1 0 0 0 计算机的测试码。1 9 9 6 年，r o t h 1 提出了基于立方体运算的d 算法。它克服了维通路敏化不能处理多维通路敏化的缺陷，形成了第一个完全的测试生成算法。在此后的2 0 多年中，国际上又先后提出了影响较大的基于布尔代数的布尔差分算法 2 ，基于九值逻辑运算的九值算法，面向通路判定的p o d e m 算法 3 和面向扇出的f a n 算法 4 ，使自动推导组合电路测试的理论更加完善、实践结果更加令人满意。无论是元件还是电路和系统，由于制造工艺的限制、使用寿命以及工作条件等影响，故障的产生是不可避免的。早期的数字系统故障诊断是依靠工程技术人员凭借自己的丰富经验和理论知识，并借助一些常规的工具( 如万用表、示波器等) 来完成的。这不仅对技术人员的素质有很高的要求，而且故障诊断速度慢，质量差。尤其是系统日趋复杂，这个矛盾就更加突出，这迫使人们研究新的方法和技术来完成这项工作，而计算机的迅速发展，尤其是微型计算机的普及，为故障检测和诊断提供了物质基础，使测试与诊断的自动化成为可能。个系统或电路在设计和制造过程中以及运行过程中都需要进行测试，以检验它是否符合设计要求或是否能正常工作。对数字系统来说，主要是测试其功能、时序关基于功能模块的大规模r t l 级组合电路分成测试产生算法研究系承i 逻辑关系等。如果仅仅是测试一个电路或系统是否存在故障，则称之为故障检测( f a u l td e t e c t i o n ) ；如果不仅要检查电路或系统中是否存在故障，而且要定位故障点，则称之为故障诊断( f a u l td i a g n o s i s ) 。一般来说，故障检测和故障诊断统称为测试。但在某些场合，测试与故障诊断是有细微差别的：测试是面对产品的检验而言，因此测试的结果可能有故障，也可能没有故障：如果有故障，则有可能需要作故障定位，也可能不需要作故障定位。而故障诊断一般均指在已确定系统或电路有故障的前提下来确定故障的位置，有时还要确定故障的类型和其它问题。因此从某种意义上讲，故障诊断可称为故障定位( f a u l tl o c a t i o n ) 。测试按其工作条件又可分成在线测试( o n l i n et e s t i n g ) 和离线测试( o f f l i n et e s t i n g ) 两种。在线测试是指系统和电路在正常工作时间同时进行的测试，例如数据在存储或传输过程中采用特殊编码，以便随时作故障检测的处理。离线测试是指脱离系统正常工作的条件，放置到专用的测试仪器或测试设备上去进行的测试。1 2 高层测试产生需求及现状高层a t p g 虽在学术上已有许多文章 5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，已提出了许多新的技术，但仍未能在市场上出现成功的高层a t p g 的产品。然而，在工业上仍有要求有效解决此问题的需求。通常出于四个需求需要进行高层a t p g ：一是在综合步骤之前对电路进行一些可测试性分析；二是当缺乏门级网表时，根据电路的高层描述来产生测试向量；三是为了降低之后门级a t p g 的复杂性：四是为了获得能有效应用于设计验证的向量。然而，大量提出的高层a t p g 技术与这些要求背道而驰。首先，技术上采用的故障模型：每种技术的有效性仍是按所获得的测试向量在对应门级描述上的单固定故障的故障覆盖率来衡量：而所有高层技术都应面向其所在层次( 寄存器传输级或行为级) 的要求，而非门级。根据所采用的故障模型，工作的复杂性也随之改变，高层特性与门级故障覆盖率的关系也随着改变。技术所采用的输入描述：某些技术专注于由自动综合工具得出的输入描述形式，某些技术则专门针对一些特殊结构，如专门针对数据结构部分，或控制结构部分。技术所采用的计算模型：计算模型的选择极大影响了可达到的解决方法的完备性：处理更一般描述的能力及可接受输入描述的最大尺寸和复杂性。2 基于功能模块的大规模r t l 级组合电路分成测试产生算法研究解决以上问题的种办法是更加清楚地定义问题所针对的细节，即将高层测试产生分解为几个特定的问题，如“r t l 综合描述的a t p g ”和“行为描述的设计验证序列的自动产生”等。本文则提出了一个针对r t l 级综合描述的a t p g 工具，实现了高层测试产生，特别是分层的测试产生工具。1 3r t l 级测试产生现状及展望随着电路规模的发展、扩大，电路复杂度的不断提升，电路的设计验证及测试的难度也越来越大。一种简单易行的方法即将己有的非常成熟的且在实际应用中己证明了其设计正确性的电路设计作为功能模块的形式嵌入电路的整体设计之中。功能模块具有相对独立的内部实现结构( 一般为门级实现或板图实现) ，具有完整的功能说明及测试集信息。研究针对由功能模块组成的电路的测试产生算法对于含i pc o r e 的电路的测试产生，以及解决大规模、超大规模电路的测试产生均具有重要意义。为了保护知识产权，功能模块的底层实现可能是不透明的。对电路设计者而言，有时仅需了解功能模块的功能及输入、输出端口的含义。另一方面，在进行电路设计时，设计者按自顶向下的设计方法将电路功能划分成子功能，再将子功能又进一步细化，逐层向下，直至用具体的门级或板级实现或用已有的功能模块实现，如四位运算器、十六位乘法器或已非常成熟的芯片。从而在设计时就形成了对电路功能或行为的分层描述形式。由此在进行电路具体实现时，电路设计者可提供电路的具体门级设计或分层设计。电路的分层设计更体现了电路的功能特性，如在电路的测试产生中利用电路分层设计特点，则有助于降低电路测试产生复杂度。虽然门级测试产生算法已十分成熟，但其已不能适应当前电路的规模和复杂度。结合电路的功能特性在更高一层对电路进行基于结构的测试产生可以降低电路测试产生复杂度。r t l 电路既描述了电路的结构特性，又描述了电路的功能行为特性，因此基于r t l 描述的集成电路测试技术研究已受到普遍的关注。r t l 电路测试产生及可测性设计研究已越来越受到测试界的关注。去年在中国湖南长沙，由湖南大学承办了2 0 0 0i n t e r n a t i o n a lw o r k s h o po nr t la t p g & d f t 1 2 ，1 3 ，1 4 ，x s ，会上就r t l 测试技术的研究进行了广泛的交流和探讨。当前大多关于r t la t p g 的研究以r t l 电路的行为描述为基础，如i t a l y 的f c o m o 1 6 1 等提供了新的r t lb e n c h m a r k s 。并给出一个基于功能模块的大规模r t l 级组合电路分成测试产生算法研究a t p g 结果。r t l 电路的行为描述体现了电路的功能和行为特性，更接近于电路的功能描述，因此同时也丧失了电路的结构信息，因此基于r t l 行为描述的测试产生更类似于功能测试或软件测试，未能充分利用r t l 电路描述中的结构信息。u s au n i v e r s i t yo f c a l i f o n i as a nd i e g o 的m a k r i s 1 7 等根据电路中的数据通路及控制通路建立功能模块的连接关系表，根据功能模块的连接关系表进行r t l 电路分层测试产生。但此种算法只能进行两层的测试产生，未实现真正意义上的多层的r t l 分层a t p g 。面向门级单固定故障和基于模拟的确定性门级测试产生方法仍在广泛有效地使用。但随着电路复杂度的提高、规模的扩大，其执行时间通常过长，己不符合时代发展的要求。限制这些方法有效性的关键因素是缺乏电路相关行为的信息。硬件描述语言( h d l ) 用于模型化v l s i 电路。h d l 描述分为三类：结构级，寄存器传输级( r t l ) 和行为级 1 1 。r t l 描述对应于通过逻辑综合工具得到的与门级网表综合一致的设计描述。个r t l 模块代表了电路中的一个微结构，每个模块有其自己的事件调度安排和资源分配信息。r t l 级描述作为一种具有高层信息，又能尽量保持门级结构特性的描述方法，更适合当前测试产生发展的需要，因此r t la t p g 也成了当前测试界的研究热点之一。r t l 测试产生中，电路的行为信息来源于寄存器传输级的结构描述，产生的测试序列仍以检测具有门级描述的模块中的特定固定故障为目标。在许多情况下，r t l 测试产生首先对被测试模块( m u t ) 寻找一个测试环境( 为一个从原始输入和符号化传播路径到原始输出的符号化验证通路集) ，然后根据测试环境及预先计算的模块测试集进行测试产生。如果测试环境为空，则m u t 是符号化不可测的。1 4 本文主要工作本文针对v e r i l o gh d l 描述的r t l 电路结构信息进行r t l 分层测试产生研究，提出了一个将v e r i l o g h d l 描述转换为可用于r t l 测试产生内部描述的格式转换器 1 9 】；并在此格式转换器生成的电路内部描述的基础上提出了两个主要基于电路结构信息的r t l 组合电路分层测试产生算法，一为两层算法 1 2 ，一为多层算法。算法结合了r t l 电路的结构特性与电路中功能模块的行为特性，实现了真正意义上的分层测试基于功能模块的大规模r t l 级组合电路分成测试产生算法研究产生，为解决超大规模集成电路的测试问题提供了一种新的方法。通过实验数据说明该方法降低了电路测试产生的复杂度、提高了电路测试产生的效率，是一种有效可行的方法。本文主要根据组合电路的r t l 级结构描述，对r t l 级分层测试产生进行研究，主要工作为：( 1 )根据r t l 级结构描述，生成用于r t l 级测试产生的内部数据结构的格式转换器。( 2 )r t l 级组合电路两层测试产生算法的研究及实现。( 3 )r t l 级组合电路分层测试产生算法的研究及实现。基于功能模块的大规模r t l 级组合电路分成测试产生算法研究2 1 引言第2 章r t l 描述格式转换器最常见的r t l 级电路描述语言有两类：v h d l 和v e rjl o gh d l 】8 。描述r t l级电路有许多描述语言。其中应用最广的有v h d l 、v e r i l o g 等语言。本文主要针对用v e r i l o g 语言描述的i s c a s 8 5 系列的十个b e n c h m a r k 组合电路 2 0 ，2 1 ，2 2 ，2 3 进行分层测试产生算法的研究。用v e r i l o g 语言描述的r t l 级电路具有良好的结构特性和可读性，但若作为测试产生算法中直接操作的数据对象则不是很方便。它不能有利于对电路结构的遍历，不利于电路组件或功能模块间的联接及事件的驱赶，也不利于简单有效的获得电路的行为特征。因此有必要建立一个有利于进行直接数据操作的r t l 级电路的内部数据结构或数据对象。所采用的数据结构将直接影响r t l 分层测试产生的效率及结果。2 2r t l 级电路的v e r i l o g 描述2 2 1r t l 级电路电子系统按设计层次可划分为系统级、行为级、r t l 级、门级、开关级等五个层次，这种划分是针对描述内容抽象程度不同展开的。r t l 级电路经常用于描述底层硬件行为。r t l 级电路是介于行为级与门级电路之间的一种电路描述方式。r t l级电路一般将电路划分为两大部分：数据通路部分及控制部分。控制部分根据电路中当前控制变量的值对电路中的状态转换进行控制；数据通路部分则根据电路的当前状态、当前输入来实现数据的转换或处理。电路输入也划分为相应的两大类：数据输入及控制输入。数据输入经过数据通路上各数据处理单元至电路的输出。数据处理单元既可是单个门，也可是一个功能模块，如：加法器、多路选择器和乘法器等。每一个功能模块都具有特定的功能或行为，因此也体现了电路中一定的行为特6 基于功能模块的大规模r t l 级组台电路分成测试产生算法研究性。由此，r t l 电路通过数据通路记录电路的结构信息，另一方面通过控制通路和电路中的功能模块记录电路的行为信息。r t l 电路的另一大特色为对具有相同或相似性质的输入线或内部联接线合并成总线形式。如个四位加法器，则将其加数和被加数的对应四位合并成总线；则可将一个四位加法器表示成总线a 与总线b 进行相加的形式：a 十b 。通过总线形式更明确地表示了电路的行为特性。本文仅针对r t l 组合电路进行分层测试产生算法研究。在r t l 组合电路中只有数据处理和运算，无状态转换的变化，不具有时间特性。因此在r t l 组合电路中只包含数据通路部分，而不包括控制通路。因此r t l 组合电路分层测试产生算法研究仅考虑r t l 电路数据通路部分特征。2 2 2v e r i l o gh d l 特性v e r il o gh d l 可以在各个层次上对数字系统进行描述。v e r i1 0 9h d l 是在c 语言的基础上发展起来的，因而保留了c 语言所独有的结构特点。v e r i l o gh ) l 是由类似于c 语言中的函数，称之为m o d u l e 的模块组成的。v e r i l o gh d l 中的模块调用通过模块名相关联，模块之间的联系通过端口之间的连接实现，所不同的是它反映的是硬件之间实际的物理连接。v e r i l o gh d l 具有良好的结构特性，利于设计者从高层对电路进行设计和描述。a baba = _ b图2 - 1 电路7 4 l 8 5r t l 结构图d ba = b7 基于功能模块的大规模r t l 级组合电路分成测试产生算法研究如图2 1 ，为7 4 l 8 5 电路的r t l 结构图。图中m 1 和m 2 是先行进位加法器c l a功能模块，实现对两个四位数进行加法运算时对高位的先行进位。其中g 为两个四位数对应位的本地进位：p 为对应位的传递进位。从此结构图上我们可清晰地得到电路的结构信息：两个四位数a 和b ，将彳 b 送m 1 的g 、爿o b 送m l 的p ，a b 信号送m 2 的c j 。m 1 输出的先行进位c o 送输出信号a b ；( a o 口) a ( 爿= b ) 送输出信号a = b 。另方面，由于此电路结构比较简单，通过功能模块m l 和m 2 的功能或行为可分析出此电路的功能，即对两个四位输入a 和b 进行数值大小的比较。当总线a 的值 总线b 的值，则输出线a b 值为1 ；当总线a 的值 总线b 的值，则输出线a b 、与a b j c k ，对任意的i ，j ，k ：i e 总线a 的优先权最高，总线c 的优先权最低。在每条总线内部，具有高下标的通道的优先权更高，即：a i a j ，i fi j 。如果e l i 3 = 0 ，则屏蔽a i ，b i 和c i 3 的中断请求。功能模块m l 、m 2 和m 3 为九线的中断请求控制器。三个功能模块的结构之间略有区别。功能模块m 5 是一个九线一四线的优先权编码器。各功能模块间的联接关系通过电路描述中的变量体现。v e r i l o g 中的变量形式包括输入变量、输出变量和内部变量。p a 、p b 、p c 和c h a n 为输出变量；x l 、x 2 和i 为内部变量。这些变量对应着电路中的总线。总线在电路中的扇出也在电路描述中得以隐性体现。在此例中，输入变量e 在功能模块p r i o r i t y a 、p r i o r i t y b 、p r i o r i t y c 和e n c o d e c h a n中作为功能模块的输入出现。因此电路的原始输入e 扇出为四个分支分别连接到这四个功能模块。所以可通过分析获得电路的连接信息。从此例中也可看出，基于功能模块的大规模r t l 级组合电路分成测试产生算法研究v e r i l o g 语言与某些门级电路描述不一样，如c d l ，它不描述电路中信号线的扇出信息，而是根据相同的变量名来描述电路中线的连接情况。m o d u l et o p l e v e l 4 3 2 ( e ，a ，b ，c ，p a ，p b ，p c ，t h a n ) ：i n p u t 8 ：0 e ，a ，b ，co u t p u tp a ，p b ，p co u t p u t 3 ：0 c h a n ：w i r e 8 ：0 x i ，x 2 ，i ：p r i o r i t y am i ( e ，a ，p a ，p r i o r i t y bm 2 ( e ，x 1 ，b ，p r i o r i t y cm 3 ( e ，x l ，x 2e n c o d e c h a nm 4 ( e ，a ，b ，b e c o d e c h a nm 5 ( i ，c h a r t )e n d m o d u1e t o p l e v e l 4 3 2 下面简单介绍一下在i s c a s 8 5 和i s c a s 8 9 系列b e n c h m a r k rv e r i i o gh d l 电路描述中所出现的变量类型和关键词：1 ) m o d u l e ：用于标识电路中一个模块说明的开始。m o d u l e 后一般接模块变量名。2 ) e n d m o d u l e ：用于标识电路中一个模块说明的结束。3 ) i n p u t ：输入类型4 ) o u t p u t ：输出类型5 ) w i r e ：内部连线类型6 ) a n d a n d ( n ) ：与门类型n 代表与门的输入个数，下同。7 ) o r o r ( n ) ：或门类型8 ) n a n d n a n d ( n ) ：与非门类型9 ) n o r n o r ( n ) ：或非门类型1 0 ) x o r x o r ( n ) ：异或门类型1 i ) n o t i n v ：非门类型1 2 ) b u f f e r b u f ：缓冲门类型由于i s c a s - - 8 5 和i s c a s - - 8 9 系列的b e n c h m a r k 电路的v e r i l o g 描述是由不同机构提供的，因此造成了电路描述中使用的关键词和方式略有不同。如在i s c a s - - 8 5 系9 叱，阻地k 队n 阳c 巴基于功能模块的大规模r t l 级组合电路分成测试产生算法研究列中，对一个两输入的与1 3 描述) t j ：a n dc p c o ( c v c o ，c o ，p c ) ；但在i s c a s - - 8 9系列中，描述形式为：a n d 2m u x 2 1 ( a ( i n o ) ，b ( n o t _ c o n t i n ) ，y ( 1 i n e l ) ) 。这种差别还存在于同一系列中，给格式转换造成了一定的困难。2 3r t l 电路中的功能模块及层次特性r t l 级组合电路的描述方式体现了电路设计者的设计思想。忽略电路中的某些实现细节，专注于电路的基本特性。将电路的整体功能分解成各子功能；也可将各子功能继续分解成更小、更细的子功能。每个子功能可由功能模块实现，7 1 i , d h 法器、比较器或多路选择器；或由具体的逻辑电路来实现。如此整个电路体现为不同层次的功能模块的组合。各个功能模块的结构、功能相对独立，相当于程序设计语言中的函数。对某一具体的功能模块，其具体的逻辑实现在功能模块内部，不为上层人所见，但不管其具体实现如何，此功能模块的功能及其与功能模块外的连接已基本确定。在r t l级电路中，每个功能模块都具有其自身相对独立的结构描述，既可能是门级描述，也可能是r t l 级描述，如此形成对电路的分层描述。如下为一个r t l 电路的分层描述：m o d u l em u x 9 b i t _ 2 j ( i n o ，i n l ，c o n t l n ，o u t ) ；i n p u t 【8 ：0 l n 0 ，l n l ；i n p u tc o n t l n ；o u t p u t 8 ：0 】o u t ；m u x 4 b i t _ 2 _ lm u x 90 ( i n o 3 ：0 ，i n l 3 ：0 】，c o n t l n ，o u t 3 ：o 】) ，m u x 9 _ l ( i n 0 1 7 ：4 ，l n l 【7 ：4 】，c o n t l n ，o u t 7 ：4 】) ；m u x 2 _ lm u x 92 ( 1 n o 8 ，i n l 8 ，c o n t l n ，o u t 8 】) ；e n d m o d u l e m u x 9 b i t21m o d u l em u x 4 b i t _ 2 一l ( i n o ，i n l ，c o n t l n ，o u t ) ；i n p u t 【3 ：0 】l n o ，i n l ；i n p u tc o n t l n ；o u t p u t 【3 ：0 】o u t ；m u x 2 一lm u x 40 ( 1 n o o ，i n l 【0 1 ，c o n t l n ，o u t o ) ，- 1 0 -一茎主塑! ! 堡垫塑奎塑堡望! 堡堡垒皇堕坌壁塑堕兰生苎鲨婴壅m u x 4 1 ( 1 n o 1 】，i n l 1 】，c o n t i n ，o u t 1j ) ，m u x 42 ( i n 0 2 ，i n l 2 】，c o n t l n ，o u t 2 1 ) ，m u x 4 _ 3 ( i n 0 3 ，i n l 3 】，c o n t l n ，o u t 3 】) ；e n d m o d u l e m u x 4 b i t 2 1m o d u l em u x 2 j ( i n 0 ，l n l ，c o r t t l n ，o u t ) ；i n p u tl n 0 ，i n l ，c o n t l n ；o u t p u to u t ；i n vm u x 2 _ 0 ( a ( c o n t l n ) ，y ( n o r _ c o n t l n ) ) ；a n d 2m u x 2 j ( a ( 1 n o ) ，b ( n o r _ c o n t l n ) ，y ( 1 i n e l ) ) ，m u x 2 2 ( a ( i n l ) ，b ( c o m l n ) ，y ( 1 i n e 2 ) ) ；o r 2m u x 2 _ 3 ( a ( 1 i n e l ) ，b ( 1 i n e 2 ) ，y ( o u t ) ) ；e n d m o d u l e m u x 21从上例中可看出，模块m u x 9 b i t21 由两个模块m u x 4 b i t2l 和一个模块m u x 2l组成。而模块m u x 4 b i u 一1 又由四个模块m u x 2 _ l 组成，模块m u x 2 1 直接由门级描述构成。这样对于直接由门级实现的模块m u x 2 ，我们称之为第一层模块；而对于模块1m u x 4 b i t 一2 一i ，由门级描述及调用第一层模块m u x 2 j 实现，我们称之为第二层模块：模块m u x 9 b i t _ 2 j 的描述中同时包含了第一层模块和第二层模块，其层数取其包含模块的最大层数加1 ，为第三层模块。这样由上至下按逐渐细化的电路功能，分层描述了r t l 电路功能及结构。2 4r t l 组合电路描述的内部数据结构虽然r t l 电路的v e r il o gh d l 描述具有非常好的层次性及可读性，既描述了电路的功能，也描述了电路的结构；但由于这种描述并不适于进行直接的数据操作，因此有必要设计一个能有效表示r t l 电路结构特性和行为特性，且能方便进行电路信息访问的内部数据结构。r t l 组合电路的内部结构是针对测试产生时进行电路结构访问时内部数据结构，因此应有利于电路的结构访问：也不应抛弃r t l 电路v e r i l o gh d l 描述的层次性特色，同时也应体现r t l 级电路中的功能模块特性及层苎至翌丝堡堡堕查塑塑垦! ! 堡垒宣皇堕坌堕型堕主兰苎堕堡壅次性。另一方面，对于电路中信号线的扇出特性，线与线之间、线与功能模块之间以及功能模块之间的连接关系，也应在内部数据结构中有充分地体现。为了体现电路的层次特性，在模块表中从下至上记录电路中的功能模块及其相关信息。为了统一概念，将拯个电路也看成是一个功能模块，记录在模块表的最后一项。模块表中记录的模块的信息包括模块类型、模块层次、模块输入输出端口信息以及模块结构描述在电路结构描述表中的位置。为了有效地体现电路中连线的连接关系及连线间的扇出关系，为了记录电路中出现的各元件信息，建立元素表。元素表记录电路中的门、扇出线、原始输入和输出、模块输入和输出。电路中各元件问的连接关系由元素表和前驱后继表共同记录。当电路中元件的前驱或后继只有个时，由元素表直接记录，否则由前驱后继表间接记录。v e r i l o gh d l 描述中的总线对于电路设计者和使用者而言可读性比较好，但对于测试产生时的电路信息的访问则不太方便，尤其当总线内的位线并不总是以总线的方式进行连接时。在电路中经常会出现对总线进行拆分或合并的形式。因此在内部数据结构当中，将总线中的各线拆分为单个元素记录在元素表中。为了方便记录r t l 电路中模块与门或线的连接关系，在元素表中增加两种类型的元素：m i 类型和m o 类型。m i 为模块输入类型，而m 0 为模块输出类型。这样就可利用元素表和前驱后继表记录模块与元素间的连接关系。从电路测试产生的角度考虑，应记录电路的原始输入和原始输出；从分层测试产生的角度考虑，对模块的d 驱赶与蕴含需记录模块的输入和输出。因此建立输入表和输出表记录电路中所有模块的输入和输出( 包括最高层电路) 。模块的内部说明同样也可利用以上这几个表实现，将电路和模块的说明都同时放在以上各表中，使内部结构简单化。在r t l 电路中，同一类型的功能模块可能在r t l 电路中被多次调用。如在由半加器和全加器组成的乘法器中，如将半加器和全加器作为功能模块考虑，它们在乘法器中均被多次调用。因此，分别建立功能模块表和子模块表。功能模块表记录在r t l 电路中出现的各功能模块的具体信息，具有相同类型的功能模块在功能模块表中仅记录一次。子模块表记录r t l 电路中出现的各层模块，记录各模块的类型，记录模块在电路中的位置，模块的连接关系，模块在电路中的层次。基于以上几点考虑，为r t l 分层测试产生所设计的电路内部结构如下：元素袁e t b l ：基于功能模块的大规模r t l 级组合电路分成测试产生算法研究n a m e 字段：记录元素在v e r i l o g 表中的变量名称：t y p e 字段：记录元素的类型；n f i 字段：记录元素的前驱个数：f il 字段：记录元素前驱在元素表中的位置：1 当元素类型为原始输入类型，n f i 字段值为l ，f i l 字段值为元素在原始输入表中的序号：2当元素类型为扇出类型、原始输出类型和模块输入类型，n f i 字段值为i ，f i l 字段值为元素前驱在元素表中的序号：3 当元素类型为或门类型、与门类型、与非门类型、或非门类型、非门类型和异或门类型，n f i 字段值为各类型门的输入个数；当n f i 字段值为1 时，f i l 字段值为元素唯一前驱在元素表中的序号：当n f i 字段值大于i 时，f i l 字段值为元素各前驱信息连续记录在前驱后继表中的起始序号；4 当元素类型为v c c 类型和g n d 类型，由于元素在电路中无前驱，则n f i 字段值为0 ；f i l 字段值为0 ：5 当元素类型为模块输出类型时，由于元素前驱位于模块内部结构描述的原始输出，则n f i 字段值为元素前驱所属功能模块的序号，f il 字段值为对应输出在模块输出中的序号。n f o 字段：记录元素的后继个数；f o l 字段：记录元素后继在元素表中的位置：1 当元素类型为原始输出类型，由于元素在电路中无后继，则n f o字段值为0 ，f o l 字段值为o ；2 当元素类型为扇出类型，n f o 字段值为1 ，f o l 字段值为元素前驱在元素表中的序号；3 当元素类型为原始输入类型、模块输出类型、v c c 类型、g n o 类型、或门类型、与门类型、与非门类型、或非门类型、非门类型和异或门类型，n f o 字段值为各元素的后继个数；当n f o 字段值为1 时，f o l 字段值为元素唯一后继在元素表中的序号；当n f o基于功能模块的大规模r t l 级组合电路分成测试产生算法研究度字段值大于1 时，f o l 字段值为元素各后继信息连续记录在前驱后继表中的起始序号：4 当元素类型为模块输入类型时，由于元素后继位于模块内部结构描述的原始输入，则n f o 字段值为元素后继所属功能模块的序号，f 0 1 字段值为对应输入在模块输入中的序号。m o d n o 字段：记录元素所在功能模块序号；r t l 电路中各功能模块的结构描述均统一记录在元素表中，同一功能模块的结构描述连续记录在元素表中。因此通过m o d n o 字段记录各元素所属的功能模块。功能模块表e m t b l ：n a m e 字段：记录模块所对应的v e r i l o g 描述中的模块名称：f 1 字段：记录模块内部结构描述的各元素信息在元素表中的起始位置；l e n g t h 字段：记录模块内部结构描述对应的元素信息连续记录在元素表中的长i n p u t n 字段：记录模块的输入个数；o u t p u t n 字段：记录模块的输出个数：i n p t r 字段：记录模块输入说明在输入表中的起始位置；同一模块的输入连续记录在输入表中。o u t p t r 字段：记录模块输出说明在输出表中的起始位置；同一模块的输出连续记录在输出表中。f l o c 字段：记录模块中所有元素对应的前驱后继说明信息连续记录在前驱后继表中的起始位置；f l e n g t h 字段：记录模块相应的前驱后继说明信息在前驱后继表中的长度；1 e v e l 字段：记录模块在电路中的层数；n g a t e 字段：记录模块对应门级说明的门个数；通过此字段控制对此模块进行门级测试产生或r t l 分层测试产生；n v c c 字段：记录模块中包含的v c c 类型元素个数：i v c c 字段：记录模块中v c c 类型元素在元素表中的位置：1 4 基于功能模块的大规模r t l 级组合电路分成测试产生算法研究1 当n v c c 字段值为1 时，i v c c 字段值为模块中唯一v c c 类型元素在元素表中的序号；2当n v c c 字段值大于时，l v c e 字段值为模块中所有v c c 类型元素连续记录在前驱后继表中的起始序号：n g n d 字段：记录模块中包含的g n d 类型元素个数；1 9 n d 字段：记录模块中g n d 类型元素在元素表中的位置。1 当n g n d 字段值为1 时，i g n d 字段值为模块中唯一g n d 类型元素在元素表中的序号：2当n g n d 字段值大于时，i g n d 字段值为模块中所有g n d 类型元素连续记录在前驱后继表中的起始序号：子模块表m l is t ：t y p e 字段：记录模块对应的功能模块类型，即相应类型的功能模块在功能模块表中的序号；f 1 字段：记录模块在调用其的父模块结构描述中的起始序号；f l o c 字段：记录模块内前驱后继说明信息在前驱后继表中的起始序号；m l o c 字段：记录模块调用的各层子模块说明的起始位置；i n p t r 字段：记录模块内的原始输入类型元素在输入表中的序号；o u t p t r 字段：记录模块内的原始输出类型元素在输出表中的序号；1 v c e 字段：记录模块中v c c 类型元素在元素表中的序号：i g n d 字段：记录模块中g n d 类型元素在元素表中的序号：f m o d n 字段：记录调用模块的父模块在子模块表中的序号。输入或输出表p i e t b l ( p o e t b l ) ：n a m e 字段：记录输入或输出类型元素名称；p t r 字段：记录输入或输出类型元素在元素表中的序号；m o d n o 字段：记录输入或输出类型元素所属模块在子模块表中的序号；r l u i l l 字段：记录输入或输出类型元素作为模块端口在调用其的上层模块中的序号。一苎士望墼堡堡塑查塑堡墨! 兰丝望鱼皇堕坌堕塑! 堕主生墨堕竺窒前驱后继表f l i s t ：记录电路中各门的前驱或后继在元素表中的位置。假定每个门的前驱或后继在前驱后继表中连续存放。2 5r t l 电路v e r i l o gh d l 描述转换成内部结构算法r t l 电路描述的格式转换分两步进行。第一步对r t l 电路的v e r il o gh d l 描述进行语法分析，将v e r i l o g 语言中包含的基本电路元素及模块信息记录至预处理表中；第二步根据预处理表建立可以进行r t l 测试产生的内部数据结构，即上节所介绍的几个表。为了区分电路中的信息是元素，还是模块，预处理表包含两个表：预处理元素表和预处理模块表，分别对模块和元素进行处理。算法步骤描述如下：第一步：根据v e r i l o gh d l 层次结构描述文件，进行语法分析，生成预处理元素表：p t b l 和预处理模块表：p m t b l 。将v e r i l o gh d l 语言中记录的模块的基本信息记入预处理模块表中，门、线和输入输出各电路元素的基本信息记入预处理元素表中。v e r i l o gh d l 语言中的类型与p t b l 表中对应类型如下v e r il o g 描述中变v e r i l o g 描述中变内部数据结构类型内部数据结构类型量类型量类型i n p u too u t p u t4a n d2o rln a n d一1n o r一2n o t一3x o r5v c c6g n d7在第一步中，将电路中的总线拆分为单线形式记入元素表中，并建立元素表中各元素间的连接关系。在此过程中，关键是分析电路v e r i l o gh d l 描述中各条语句所记录的电路元件的参数个数及参数之间的连接关系，特别是模块与其它元件之间、模块与模块之间的连接关系。第二步：根据第一步预处理建立的预处理元素表：p t b l ，将电