（电路与系统专业论文）基于蚁群算法的电路测试研究[电路与系统专业优秀论文].pdf

华南师范大学硕士学位论文 摘要 随着集成电路产业的蓬勃发展，对数字电路测试的需求不断增长，因此，对 数字电路测试的研究具有较高的理论和应用价值。 本文首先介绍了数字电路随机性测试的原理，用c + + 程序实现了电路内部模 型，并且完成了电路单固定型故障的仿真，使用计算机实现了数字电路随机性测 试的操作。 其次，本文采用蚁群算法进行二维混合型细胞自动机规则配置的优化，用优 化后的细胞自动机生成伪随机测试矢量，进行电路测试仿真。对细胞自动机的互 连结构以及每个细胞单元的构造进行了设计，调整了最大一最小蚁群算法的运行 规则，用其优化细胞自动机的系统行为与状态变化规则。实验结果表明，蚁群算 法能够找到细胞自动机的较优配置，优化后的细胞自动机能够产生具有较高随机 性的伪随机数序列，将其用于数字电路随机性测试可以提高故障覆盖率并降低测 试长度。 最后，本文研究了基于二维直方图的图像多阈值分割方法。探索了多阈值情 况下二维直方图的多区域划分以及相应二维熵的计算，设计了二维熵的快速计算 方法。文中对蚁群算法的运行规则进行了调整，用其对二维直方图多区域划分点 最优化，实现了图像的多阈值分割。图像多闽值分割实验取得了较好的效果。 关键词：电路测试；蚁群算法；细胞自动机；二维直方图；图像多阈值分割 华南师范大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi ci n d u s t r y , t h er e q u i r e m e n to fc i r c u i tt e s t i n gi s k e e p i n gi n c r e a s i n g 。c o n s e q u e n t l y , t h er e s e a r c ho fd i g i t a lc i r c u i tt e s t i n gi s f u l lo f t h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e f i r s to fa l l ，t h ep r i n c i p l eo fr a n d o mt e s t i n gm e t h o di si n t r o d u c e d 。t h ei n n e rc i r c u i t m o d e li sc o n s t r u c t e du s i n gc + + t h e nt h es i n g l es t u c k a tf a u ki ss i m u l a t e d t h e r a n d o mt e s t i n gm e t h o di sr e a l i z e di nc o m p u t e rp r o g r a m s e c o n d l y , t h ea n ts y s t e mi su s e dt os t u d yt h eb e s tc o l l o c a t i o no f2 - d i m e n s i o n a l h y b r i dc e l l u l a ra u t o m a t at h a tc a l lg e n e r a t et e s tv e c t o r so fg o o dr a n d o m t h et o p o l o g y o fc e l l u l a ra u t o m a t aa n dt h es t r u c t u r er u l eo fe a c hc e l la r ed e s i g n e dt og e n e r a t e r a n d o mv e c t o r sw i t hb e t t e rq u a l i t y a i m i n ga tu s i n gc e l l u l a ra u t o m a t at op r o d u c e t e s t i n gv e c t o r so fb e t t e rq u a l i t y , t h er e g u l a t i o no fm a x m i na n ts y s t e mi sf i n e - t u n e dt o o p t i m i z et h ec o l l o c a t i o no fc e l l u l a ra u t o m a t a 。t h ec i r c u i tt e s t i n ge x p e r i m e n t ss h o w t h a tt h ea n ts y s t e mc a nf i n dt h eb e s tc o l l o c a t i o no fc e l l u l a ra u t o m a t a ，a n dt h ec e l l u l a r a u t o m a t ao p t i m i z e db ym a x m i ua n ts y s t e mc a ng e n e r a t ep s e u d o r a n d o mn u m b e r a r r a y so fg o o dr a n d o m ，a l s ot h ec e l l u l a ra u t o m a t ac a l lb ea p p l i e dt od i g i t a lc i r c u i t t e s t i n gt oi m p r o v et h ef a u l tc o v e r a g ea n dt h et e s tl e n g t h 。 l a s t l y , t h em u l t i l e v e lt h r e s h o l d i n gm e t h o do fg r a p h i c sw h i c hi sb a s e do n2 - d i m e n s i o n a lh i s t o g r a mi sp r e s e n t e d t h em u l t i p i er e g i o n a l i z a t i o no f2 - d i m e n s i o n a l h i s t o g r a ma n dr e l a t e d2 - d i m e n s i o n a le n t r o p ya r es t u d i e d t h ef a s ti t e r a t i v ea l g o r i t h m f o rc a l c u l a t i n g2 - d i m e n s i o n a le n t r o p yi si n d u c e d t h er e g u l a t i o no fa n ts y s t e mi s a d j u s t e dt oo p t i m i z et h em u l t i p l er e g i o n a l i z a t i o no f2 - d i m e n s i o n a lh i s t o g r a m ，i no r d e r t or e a l i z et h em u l t i t h r e s h o l d i n go fg r a p h i c s o n et h ew h o l e ，t h eg r a p h i c ss e g m e n t a t i o n e x p e r i m e n t sa c h i e v e dh i g hp e r f o r m a n c e k e y w o r d s ：r a n d o mt e s t i n gf o rc i r c u i t ；a n ts y s t e m ；c e l l u l a ra u t o m a t a ； 2 - d i m e n s i o n a lh i s t o g r a m ；m u l t i t h r e s h o l d i n gf o r g r a p h i c s 华南师范大学学位论文源创性声瞬 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进杼研究工作所取得的成采。除文中已经注晴弓f 用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成聚。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确的方式标明。 本人完全意识劐本声明的法律结果由本人承担。 论文馋者签名：孪学妒， 日期：冲6 月r 日 学位论文使用授投声明 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，帮：研究生在校攻读学使期间论文工作的知识产权单位属华南筛 范大学。学校有权保黯并向圉家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，哥以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密范围，在后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 论文作者签名：孕雪静， 日期：7 年占月f 日 导师签名： 日期1 筇6 月夕日 华南师范大学硕士学位论文 第一章绪论 本章主要介绍国内外对于电路的伪随机测试和图像分割的研究现状，论述了 基于蚁群算法的电路测试及图像分割研究的理论和实际意义；指出了本文在这两 个方面的研究工作内容。 1 1 国内外研究现状与本文研究工作的意义 当前数字集成电路的发展日新月异，各种类型、各种规格的集成电路不断被 开发出来，应用于多种多样的场合。随着对集成电路性能要求的不断提升，各个 集成电路生产厂家都在积极提升集成电路的制造工艺，开发规模更大，运行速度 更快，体积更小，功率消耗更低的集成电路产品。在集成电路制造业不断发展的 过程中，人们不仅需要功能更强的集成电路产品，而且还要求电路系统中的集成 电路能够可靠地运行，为整个系统的安全、稳定、高效运行提供基本保障。因此 集成电路运行可靠性的命题就被提了出来，并且逐渐形成了对集成电路功能进行 分析、测试的一整套技术、方法和理论。 数字集成电路的测试研究中需要对电路施加测试输入信号，称为测试矢量。 测试矢量的产生是数字电路测试的一项重要任务。因为数字电路测试的关键在于 寻找测试故障所需的测试矢量集，其中测试矢量的数目称为测试矢量的长度。测 试矢量一般可以通过两种方法生成：确定性方法和随机性方法。随机性测试方法 通常是由一个伪随机序列发生器产生被测电路的输入矢量。 到目前为止，国内外已经有一些对于数字电路测试矢量生成的研究。在数字 电路测试的确定性测试方法中，h i t e c 是一个基于确定性算法的测试生成器， 主要用于对难测故障生成测试矢量【。在数字电路测试的随机性测试方法中， g a t e s t l 2 j ，d i g a t e l 3 1 ，s t r a t e g a t e l 4 1 等都是基于遗传算法的随机性测试生 成器，其中g 纯s t 是纯粹基于遗传算法的测试生成器；而d i g a t e 和 s t r a t e g a t e 是结合了确定性算法的测试生成器。另外，蚁群算法也可用于集 成电路测试矢量的生成，文献f 5 l 研究了使用蚁群算法直接优化电路测试的输入测 试矢量的方法。 在数字电路的随机性测试方法中，使用细胞自动机生成伪随机测试矢量是一 j 华南师范大学硕士学位论文 种重要方法。国内外也有一定量的关于细胞自动机用于数字系统随机性测试的研 究。参考文献【6 】所研究的是2 x n 的特殊型二维细胞自动机的构造和在电路测试 方面的应用。而文献【颂是对l e - j 线性反馈移位寄存器和细胞自动机作为电路测 试的伪随机序列发生器的特性。此外，研究者还设计了细胞自动机的各种变化形 式，以使细胞自动机能够适应各种不同条件下的测试需要。比如，基于细胞自动 机的数字集成电路加权随机测试方法1 8 1 ，可以在不降低故障覆盖率的前提下显著 减小测试长度；设计移相器加于细胞自动机【们，减小了细胞自动机并行输出位流 的互相关性，同时也能够降低测试长度。 本文所进行的电路测试的研究主要针对电路的随机性测试方法。电路的伪随 机测试矢量是使用细胞自动机( c e l l u l a r a u t o m a t a 。简称c a ) 产生的。为了生成 随机性高的电路测试矢量，采用了蚁群算法c a n ts y s t e m ，简称a s ) 优化细胞 自动机配置，从而生成随机性能好的电路测试矢量。蚁群算法优化细胞自动机用 于电路的伪随机测试具有其优点：由于蚁群算法的长处在于问题解路径的构造过 程，而且在问题解路径构造中结合了问题解空间的局部启发信息。因此蚁群算法 具有很强的问题解空间搜索能力，能够较好地对细胞自动机的规则配置进行搜索 和优化。 从电路测试的发展趋势来看，集成电路测试总的来说是向着测试效果更好， 而测试成本更低的方向发展。蚁群算法配置细胞自动机用于电路测试的研究能够 较好地达到上面的目标，所以这方面的研究具有一定的理论和实际意义。 采用二维细胞自动机生成电路测试的伪随机测试矢量具有测试矢量随机性 好、测试矢量生成速度快、细胞自动机易于硬件电路实现等特点，但是在实现这 种电路随机性测试方法中仍有一些问题需要解决，比如二维细胞自动机的具体构 造方法，即如何设计二维细胞自动机才能使得蚁群算法能够方便地处理二维细胞 自动机的优化配置；蚁群算法的具体应用方法，即如何调整蚁群算法才能使其处 理细胞自动机优化配置的问题。这些问题在本文中都进行了探讨，并且比较有效 地解决了这些问题。 在图像处理方面，人们往往仅对图像中的某些部分感兴趣。这些部分常称为 目标或前景，其余部分称为背景。目标一般对应图像中特定的、具有独特性质的 区域。为了辨识和分析目标，需要将这些有关区域分离提取出来。图像分割就是 2 华南师范大学硕士学位论文 把图像划分成各具特征的区域并提取出感兴趣目标的技术和过程。 国内外在基于直方图最优化熵函数的图像分割方法方面已经有一些专门的 研究。熵是平均信息量的表征，2 0 世纪8 0 年代初人们开始考虑用信息论中熵的 概念进行阈值选取。1 9 8 5 年k a p u r 等【1 0 l 提出最大熵阈值选取法；1 9 8 9 年 a b u t a l e b 1 1 j 将k a p u t 等提出的一维最大熵法推广至二维，即考虑像素的灰度级及 其邻域平均灰度级构成的二维直方图；在多种基于直方图最优化熵函数的图像分 割方法中，勋p u 提出的一维最大熵法和被a b u t a l e b 推广的二维最大熵法最为简 洁有效，因此应用最广。但是，被推广的二维最大熵法只是简单地将一维寻优推 广为二维寻优，导致运算量按指数增长。为此，国内学者张毅军等人在1 9 9 7 年 提出了二维最大熵法的递推算法，并以加大存储容量为代价将速度提高了近两个 数量级【1 2 1 ；李立源，龚坚等人提出了二维直方图的最佳一维投影分割法和f i s h e r 准则下的一维投影分割法，并将其运用于二维最大熵法，计算量基本上与一维最 大熵法相当【”j 。 对于基于直方图的图像分割已经开始发展到多阙值分割的研究领域，也就是 基于直方图建立适应度函数，研究如何进行多阈值的适应度函数最优化，从而实 现图像的多阈值分割。在这个方面，最早在1 9 8 9 年a b u t a l e b 将最大熵法推广至 二维的情形的时候就有所论及【1 1 】，文章指出基于图像二维直方图的多阈值方法是 将来可以探索的领域。之后，1 9 9 7 年p e n g y e n gy i n 等人基于一维直方图实现了 多阈值方法，并且研究了最优化多阈值分割的迭代算法【1 4 1 ；后来在2 0 0 7 年 p e n g - y e n gy i n 再次研究了基于一维直方图的多阈值方法，提出了一维直方图的 最小交叉熵的快速计算法，并且使用粒子群算法优化搜索最优多阈值分割点【1 5 l 。 基于二维直方图的图像阈值分割方法以前也有所研究，然而基于二维直方图 的多阈值分割方法由于二维直方图多区域划分问题不易处理尚属探索性研究。比 如：在二维直方图中设置的多个阈值分割点如何导出各个阈值分类的适应度；二 维直方图的信息熵的运算量随着图像灰度级数按指数增长，如何进行二维直方图 信息熵的快速计算；二维直方图多区域划分的优化在多阈值情况下是n p 难问题， 需要考虑使用恰当的优化求解方法；最后，在求得二维直方图中多个阙值分割点 后，如何根据二维直方图下的阈值分割点实现图像中各个像素的灰度阈值化。这 些问题的比较有效的解决方法在本文中都进行了探索。 华南舜蓖犬擘疆圭擎擅论文 本文研究的图像分割方法是采用蚁群算法实现基于二维最大嫡的多阈值分 裁。浚谤7 瓣二维壹方图避霞多区域划分豹方法，傻建蚁群算法簸魏铯二维鬟方 图多区域划分，实现图像的多阂值化。该方法盼特点是： ( 1 ) 图像的灰度属憔是图像比较赢观而且易予获得的信息，从而使得对圈像 戆楚理毙较蹇凌、寿效； ( 2 ) 以图像灰度为蒸础建立的二维直方图包括了像素的获度信息和像豢邻 域的局部交化信息。当图像的信噪比降低时，应用一维最大熵法将产生很多分割 错误。二缭爱大薅法瘦羯二维壹方溪，狐莰反蔌了灰度分枣售塞，还反映了邻域 空间相关信息，因此在图像信噪比较小时，二维最犬熵法明显优予一维最大熵法； ( 3 ) 对= 维直方图的多区域划分方法进行设计，从而使得基予二维直方嘲的 錾缘多瘸繁分裁霉鞋实溪； ( 4 ) 采用了适合于= 维空间搜索的变种的蚁群掉法，这种算法能够有效地利 用分布在二维空间上的邋应度函数信息，实现对问题的优化求解。 1 2 本文的研究内容 首先对所测试的电路建立电路模型，接下来使用伪随机数发嫩器产生的测试 矢塞麓入毫鼹模型输入壤遴孳亍毫跨薅撬往溺试。冀审，赞夔瓤鼗发生器捷矮黪是 细胞自动机，而其规则配置用蚁群算法进行优化，目标是使细胞自动机生成的测 试矢量随机性更高，在数字电路随机性测试中找出尽可能多的举固定型故障。 本文圭溪磅究了嚣令方莲：第一，纂子二维游会鳘缨貔自动税豹数字毫籍蕤 机性测试方法。使用了蚁群算法优化二维混合型细胞自动机的配鼹使其能够产生 随机性能好的电路测试矢量，并且将钡8 试矢量加入集成电路模型进行数字电路随 秘毪溅试实验，获褥实骏结采并透劈分辑；第二，凝饶毪二缍袋犬薅魏蓬豫多游 值分割方法。通过在二维直方图中设溉恰当的区域划分点，实现对图像的多阙值 化。 本交鹣研究痣容安撩翔下： 第一章分析基于蚁群算法的电路测试及图像分割研究的实用价值和理论 意义，介缓本研究领域圈内外的研究现状； 第二豢夯绍数字嘏路静溺试琢疆。对于数掌电路静测试实藏方法送移说 4 华南师范大学硬士学位论文 聪，介绍了集成魄路的标准测试模型，劳说明在集成电路标准测试外部模型自动 转换为计算辊内部模型上骰虢置作； 第三章以数字电路伪随机性测试方法为基础，介绍细胞自动机如何用于电 路测试。对于绷艨自动机的绐掏和工作原溅进行介绍，提狲二维混会型细胞自动 梳的结构配置，势对其结构配嚣使用篱臻蠢效静藤黉l 谶行圣羹述。对纲胞自动梳用 于电路测试的构成框架进行了介绍； 第遥章采薅蚊群算法傀化二维混合溅细胞自动机舱结构配嚣。慰子蚁群算 法的基本工作原瑷迸行奔绣；针对细胞自动机配置静优化闯题，对蚁群算法的工 作机制进行了适当调整；对蚁群算法优化细胞自动机配瀑的算法步骤进行设计； 完成蚁群算法酝嚣缨斑鑫动粥子电路测试舱实验，获取实验数据并对结果进行分 析； 第五章蚁群算法用于图像多阂值分割的实现。对旗于二维最大熵的图像分 割方法进行筠分；考虑了二缀嶷方强中区域分割点与各个划分区域的逶应凄豹对 应荚系，设计了撤据二维寅方溜多区域划分快速许算二维爝的方法；采用适合二 缏空间搜索的蚁群算法优化= 维直方图划分区域，实现图像的多阈值分割。 第六章憨缝全文。 5 华南师范大学硕士学位论文 第二章数字电路测试方法 本章介绍数字电路的测试原理。对于数字电路的测试实施方法进行说明，介 绍了集成电路的标准测试模型，并且提出本文在集成电路标准测试模型自动转换 为计算机程序描述上做的工作。 2 1 数字电路测试原理 2 1 1 数字电路测试的必要性 自从集成电路问世以来，它就得到了迅速发展。集成电路经历了小规模、中 规模、大规模、超大规模和甚大规模等发展过程。目前集成电路已进入系统芯片 ( s o c ) 时代，即可以将各种各样的功能模块( 例如存储器、处理器、输入，输 出接口电路、数字信号处理器等) 集成在一个单一的芯片上1 1 6 1 。 由于数字电路测试对于集成电路制造和广泛使用具有至关重要的作用，数字 电路测试的方法与理论的研究具有很高的应用价值和理论意义。它从诞生到现在 已经经历了比较大的发展。尽管如此，目前对于数字电路测试算法速度的改善仍 是以线型速度增长，而集成电路增长的速度则是每隔5 年就增长一个数量级，总 的来说集成电路测试的研究速度还是跟不上集成电路设计、制造和应用的发展速 度。为了解决集成电路测试问题所面i 艋的困难，现在集成电路制造业已经开始在 系统设计时就充分考虑到测试的要求，即用故障诊断的理论去指导集成电路结构 设计；另一方面，还需要进一步地提高已有测试算法的效率并且研制新的测试生 成算法和技术，研究并行处理方法和进化算法在测试生成中的应用，使集成电路 测试更加快捷，更加充分地进行测试。 集成电路元件或由其构成的系统的物理故障是多种多样的。故障的多样性表 现在两个方面：一方面，故障的种类是各种各样的；另一方面，数字电路中出现 故障数目可能是单个故障或者多个故障同时出现，这也使得故障出现的组合更加 多样化。对各种故障进行分类，并选择最接近于实际处理的电路故障的模型，这 个过程叫做故障的模型化。因此，用以代表某一类故障的典型故障称为模型化故 障。一般的故障情况有固定型故障、桥接故障、暂态故障、时滞故障等四种模型 化故障类型。 6 华南师范大学硕士学位论文 对于一般的电路，根据统计得到如下结论【1 7 】：固定型故障在故障总数中占 到9 0 以上，因此必须对固定型故障作充分的研究。对于电路中一根信号线固 定于逻辑1 或0 的缺陷，用单固定型故障( s i n g l es t u c k - a tf a u l t ，简称s s 舢模型 描述。如图2 1 的组合逻辑电路，若线a 固定接地，用s a - 0 故障描述，标志为a s - a - 0 ，记为a 0 ，或一0 。 x t 图2 1 组合逻辑电路s s a 故障示意 s s a 故障即所谓的经典或标准故障模型，这种故障模型最早被提出，研究和应用 也最广泛。虽然单固定型故障模型的合理性和代表性还有待理论论证，但用于检 测电路中存在的“错误”十分有效。单固定型故障的这种有用性具有以下属性【1 s l ： ( 1 ) 它表达了许多不同的失效方式； ( 2 ) 它是与工艺无关的故障模型； ( 3 ) 实践表明，针对这种故障模型的测试矢量可以检测许多非经典故障； ( 4 ) 单固定型故障模型比其他类型的故障模型的测试矢量数目少，通过故障 化简方法此数目还可以减少； ( 5 ) 可以用这种故障模型表达其他类型的故障。 应该指出，有些故障是侦察不出的。例如图2 1 中p o ，y ，0 就是无法侦测的， 因为有故障时的输出y 邮、y 棚与无故障电路的正常输出完全一样，称这类故障为 不可测故障。一般来说，数字电路中冗余部分的电路故障是不可测故障。 为了尽量减少和消除生产、制造集成电路可能出现的故障，测试已成为i c 制造过程中一项非常重要的内容。特别是集成电路进入深亚微米以及超高集成度 的发展阶段以来，通过集成各种口核，系统芯片的功能更加强大，同时也带来 了一系列的设计和测试问题。测试是集成电路设计中费用最高、难度最大的一个 环节。据报道，随着v l s i 集成度的提高，测试费用可占芯片制造成本的5 0 以 上。p r i m e 研究集团报告称，2 0 0 0 年半导体行业在数字集成电路与系统级芯片测 7 肇南师范大学硬士学位论文 试仪器上豹花费憨4 9 亿美觉，测试费用则更高；按照i t r s ( i n t e r n a t i o n a l t e c h n o l o g yr o a d m a pf o rs e m i c o n d u c t o r s ) 戆磺究，瑟2 0 1 4 年螽钵警魄薅酶溅斌 成本鼹大于其制造成本，所以电路测试将在檠成电路的发腰中起到越米越重要的 作用，并且电路测试豹粳关方法秘理论必将鸯着广耀豹发鼹窆田和巨大舱应弼徐 毽i 域。 2 1 2 数字电路测试的方法 一令电路蔑系统在莰诗、秘逶淡及运褥过程孛蘩需要对箕进行溺试，毅捡验 它怒黼符合设计嚣求或者是磷能够正常工作。般地，对乎数字系统的故障检测 和故障诊断通称为数字系统测试。对于数字堪路来说，耄要是测试其功能，时序 关系，逻辑关系等等。舞栗莰仪测试一辛魄鼹或系统是孬存在敖藩，辩称之势敌 障检测；如果不仅要检查电路戏系统是否存在故障，而熙翳定位故障点，则称之 为赦障诊断。数字电路测试的基本过程如图2 2 所示，在数字电路的输入端加入 嚣试德号，霆察输逮溃戆蔷号与预襄静赣怒溶号是否一致。熟巢一致翳说瞬建亳 路礅常，否则表承此电路有故障存在。 琢2 2 羲字毫耩测试方法藤瑷褥 上隔中数字电路的输入端的测试信号是由测试矢量生成器产生的，在数学电路的 输入端龆入豹测试信号通常稔必溅试矢量。 数字电黯溅试方法戳按照瓣试矢量鹃生成穷法务浚兰类：确定毽溅试、隧 机能测试和混合测试【r 丌。确定性测试方法，首先针对被测电路的各个故障产生 测试矢量，熬螽产生一个筢测试电路孛所有敬障熬最小溅试集箨为测试矢量集 合。秃故障毫膝对测试集合牵备个测试翡穗应餐接存锉起来佟秀参考德。溅试实 施时，测试矢量集合中的各个艇量逐个加黧被测电路的输入端，相应的输出值与 g 华南师范大学硕士学位论文 参考值进行比较以确定被测电路是否存在故障。确定性测试分为两个阶段：产生 测试矢量及参考值的阶段为测试生成阶段；进行测试的阶段为测试实施阶段。这 种测试技术中的测试生成是一项非常耗时的工作并要占用大量的存储器空问。 为了克服确定性测试生成耗时大、成本高的缺点，人们提出了另一种测试方 法随机性测试。随机性测试方法通常是由一个伪随机序列发生器 ( p s e u d o r a n d o ms e q u e n c eg e n e r a t o r , 简称p r s g ) 提供被测试系统的输入信号。 在随机性测试中，测试矢量生成一般不采用确定性算法。产生的测试矢量同时施 加至被测电路和无故障电路的输入端，比较被测电路和无故障电路的输出即可判 别被测电路的好坏。随机性测试省去了确定测试所需的测试生成时间和存储测试 数据的成本。在这种技术中，如何设计伪随机测试矢量生成器使其产生的测试矢 量能够达到较高的故障覆盖率就是比较关键的问题。 混合测试是上述两种测试方法的混合使用。一般在开始时使用随机性测试， 若在使用了一定数量的测试矢量后仍未能测试出新故障，则可接着采用确定性测 试。 本文研究的数字电路测试方法采用的是随机性测试方法。数字系统的随机性 测试方法中，伪随机序列发生器的作用十分重要。伪随机序列发生器生成的序列 的随机性高，那么对被测电路施加的输入矢量在可能的输入矢量空间中的分布就 均匀，而且输入矢量不容易发生重复生成的现象。这就保证了对数字系统的随机 性测试方法的普遍性和有效性，从而使得伪随机序列发生器能够测出更多的故 障，并且测试所用的输入矢量数目更少。设计伪随机序列发生器的一个关键问题 是为了得到满足要求的故障覆盖率，测试矢量的个数( 测试长度) 应该尽可能少。 所谓故障覆盖率( f a u hc o v e r a g e ，简称f c ) ，即伪随机测试矢量可检测到故障 的概率，一般取检测到故障数目与电路所有可能的故障数目的比值。一般而言， 随机性方法求取测试矢量的时间与测试矢量长度成正比。 2 2 数字电路模型建立 2 2 1 用于测试的数字电路模型 数字电路模型在电路的设计、制造和测试中具有非常重要的意义，数字电路 模型的表达方式对电路故障模型建立、电路运行模拟、测试矢量生成和电路设计 9 华南师范大学硕士学位论文 验证的影响很大。 数字电路测试可以把电路看成一个黑匣子，实现的功能是处理输入端施加的 信息，产生的信息通过输出端输出。电路黑匣子对于信号的处理功能可以用电路 模型来表达。电路模型就是一个对电路中各个元件之间的结构连接关系和电路中 各个节点电平变化的逻辑函数关系的定义。 电路模型按照建立和使用方式可分为外部模型和内部模型1 8 】。外部模型是 用户使用的模型，而内部模型在计算机内部以数据结构和计算机程序方式表达电 路功能。 外部模型可以是图形方式的( 如原理图) ，也可以是文本方式的。文本方式 常见的形式是h d l 语言描述，用指令级和寄存器级的h d l 语言进行描述。以 标准测试电路描述文件形式出现的电路外部模型可以用于电路功能的仿真和电 路测试方法的研究。标准测试电路的意义在于使用标准测试电路进行电路测试可 以使得不同测试方法的效果能够用同样的标准进行比较，从而促进电路测试研究 的良性发展：此外，标准测试电路一般选取的是实际电子系统中最为常用、最有 价值的集成电路建立模型，因此可以将研究重点集中于这些比较重要的电路上。 常见的标准测试电路包括i s c a s 8 5 国际基准电路、i s c a s 8 9 国际基准电路 和i t c 9 9 国际基准电路。i s c a s 8 5 国际基准电路是在1 9 8 5 年的国际电路与系 统论坛( i n t e r n a t i o n a ls y m p o s i u mo fc i r c u i t sa n ds y s t e m s ，简称i s c a s ) 上由e b r g l e z 和h f u j i w a r a 以网表文件的形式发布的【1 9 1 。i s c a s 8 5 中的电路取自电子 工业使用的集成电路器件。eb r g l e z 和h f u j i w a r a 并没有公布i s c a s 8 5 的高层 次设计文件和它们的实际用途。这样做部分出于商业保密的原因，部分出于他们 希望电路测试研究者不考虑i s c a s 8 5 的高层次设计，并把这些电路看成电子系 统中随机选择的集成电路。自从i s c a s 8 5 出现以来，它就被广泛用于数字电路 测试研究。i s c a s 8 5 中的电路主要是组合逻辑电路，本文对数字电路测试的研 究主要针对组合逻辑电路，因此数字电路测试实验采用的标准测试电路即是 i s c a s 8 5 国际基准电路。 2 2 2 外部模型到内部模型的自动转换 可以利用计算机的快速计算能力和强大的信息分析处理功能来进行数字电 路测试理论和方法的计算机辅助研究。为了达到这个目的，首先要根据标准测试 华南师范大学碗士学位论文 电路的功能描述文件对电路孽元连接结构和逻辑关系的摇述( 夕卜部模型) ，采用 诗算橇程痔语京鑫动完成龟魏模型静谵算税程序表述( 凌部模垄) 。遮燕采用c 年+ 语啬程序实现对电路的外部模型到内部模型自动转换，建立用c + + 语言表达的内 部模型；然后将如图2 2 所豕的电路测试方法用计算机程序实现。这样，就可以 壹接调厝计算辊程序来寝嚣龟鼹毅簿，模按电路运行稳滋和诗算电臻溅试算法戆 故障覆盖率。电路外部模型到内部模型自动转换程序及相应的电路测试程序已经 通过本文的研究实现。 在进行电路溅试算法浆c 每+ 语言实糯辩，需要将豁准测试毫鼹攘述文释震 c + + 语言的逻辑语句和链接必系进行描述。标准测试电路集中的电路少则有十几 个门，多则有上万个门，如粜手工将标准测试电路采用c + 语句进纷表达，那将 耗爝菲常多的时阍和精力，弼蠢在手工转换中容荔崮璃错误。所戬遮攫研究了鲡 何把文本格式的电路描述文件自动由计算机转换为c + + 语言表达形式的方法。 这个转换_ ；窭程的主要需骚考虑下面三个方瑟： 。 ( 1 ) 考虑毫路描述文件审盼逻辑表达奄c p + 语言逻辚运算语句的对应关系。 在电路描述文件中，主要的逻辑关系包括：与( a n d ) 、与非( n a n d ) 、或( o r ) 、 或嚣( n o r ) 、黪或( x o r ) 、- ：1 t i0 n o t ) ，缓滓( b u f f ) 等。丽在e 语言中表达 逻瓣关系静运舞符只有三释；逻辑与( & ) 、逻辑或( 静、逻辑非( ! ) 。对于与 ( a n d ) 、或( o r ) 、非( n 0 田，c + + 语言中有相应的逻辑运算符；对- y c + + 语言 爨没骞匏电路攒述文侉孛的芟她逻辑关系，霹戥组会馒惩逻辑运算籀构成表达式 避行描述，比如：a ( x o r ) b ，可用c 语言表达为( ( ! a ) b ) h ( a & ( ! b ) ) ； ( 2 ) 电路测试模型的c + + 谮言表达还需考虑电路中备个节点之间的互连结构 关系。为了髓够灵活、有效撼翅e + + 语言淡达各个节煮豹连接关系秘电乎壤况， 采用了结梅数据类型和顺序袭数据结构谶行电路结构擞述。对电路中每一个节 点，使用结构数据类型描述这个节点的属性，包括节点编号、电平情况、输入 输爨褒蛙、兹继艚继节点痿惑等。读取宠路接述文零，逶过c + + 羧净熬鑫动处 理，就可以将电路中所有节点的结构信息，逻辑关系存储为c 年+ 语富的顺序表数 据结构描述； ) 最莲，遴雩亍电路测试躲诗算规模叛。在爰e + + 谗言数撂结构液述豹邀路 模溅上设置好输入信号状态和电路中的单阉定型故障，扁动进行电路测试的c 年+ 1 1 华南师范大学硕士学位论文 语言程序，得到电路芷常输出和敬障情况下的输出，将二辫比较就可知巍前的测 试矢爨楚否可溺爨浚萋静擎露寇蓬故障。既终，程序还窦蠛了对溺蹬教簿数蠢诗 数的功能，从而能够统计电路测试的故障覆盏率。由于标准电路测试文件中各个 节点怒按照电路中从输入到输掇逻辑关系和呶平信号的传播顺序进行j 非序的，所 戳在避行电路运行状态静诗算机模拟靖，只需要对( + + 程膨鸯动建立瓣颓序表依 节点编号遍历运算节点状态，即可以正确地产生电路中各个节点的信号电平和电 路豹输出蓿号。 华南师范大学硕士学位论文 第三章细胞自动机生成电路测试矢量 本章主要对细胞自动机的基本结构和工作原理进行介绍，指出了细胞自动机 具有能够产生高性能伪随机数序列的特点。此外，针对数字电路测试问题，本文 选择了性能更优的二维混合型细胞自动机，建立起细胞自动机与电路模型相结合 的数字电路测试结构。 3 1 细胞自动机的结构与工作原理 1 9 8 5 年，s w o l f r a m 提出将细胞自动机的规则加以简化，并且使用细胞自动 机作为伪随机数发生器应用于密码学领域1 2 0 。细胞自动机能够产生高性能的伪 随机数序列，因此有不少研究者开始进行细胞自动机生成伪随机数序列用于电路 测试的研究1 2 。国内对于使用细胞自动机生成伪随机数序列的研究也比较深入。 论文【2 2 1 讨论了可编程细胞自动机伪随机序列发生方法。文献【2 3 1 使用具有梯形结 构的二维垂直邻居受限细胞自动机生成伪随机序列，研究了其生成伪随机数序列 的随机性。论文l 实现了为细胞自动机阵列设计移相器以减小其生成伪随机数 序列的位流互相关性。 细胞自动机的相关理论经过研究和发展，现在已经比较成熟。下面对细胞自 动机的基本原理进行介绍。 3 1 1 细胞自动机原理 细胞自动机也是有限状态自动机的一种。可以把d 维细胞自动机c a 定义为 一个4 元集合 z d ，s ，n ，f 。其中， z 代表细胞自动机c a 中每个细胞取值构成的集合。d 是细胞自动机的维数。 s 是细胞可以取值的状态集合。 n 代表细胞自动机的邻域结构。用r 表示邻域半径。 f 代表细胞自动机的状态转移函数集合，它是由每个细胞的状态转移函数构 成的集合。f c i 是一个细胞c i 的状态转移函数。 细胞自动机就是d 维空间中的一个细胞阵列。其维数用d 表示，比如d = 2 表示是二维细胞自动机。c d r o y 和kc a t t c u 等人的研究表明，在生成伪随机 数序列方面，二维细胞自动机比一维细胞自动机性能更高【6 捌。 华南师范大学硕士学位论文 每个细胞c i 都按照自己的状态转移函数f b 和邻域n 内部细胞的状态进行细 胞g 状态s s t ) 的演化。细胞阵列中每个细胞c i 可以在状态集合s 中取状态值。 细胞自动机的演化就是当前时刻细胞阵列中每个细胞计算状态值，并且在下一个 时刻更新每个细胞的状态。 细胞自动机中每个细胞c i 都按照状态转移函数f b 进行状态的演化。状态转 移函数集合f 对于细胞自动机产生的伪随机数序列的性能具有十分重要的作用。 如果细胞自动机的状态转移函数集合f 中不只包括一种状态转移函数，那么就称 这种细胞自动机为混合型细胞自动机；否则，就是单一型细胞自动机。混合型细 胞自动机相比单一型细胞自动机具有更加灵活的结构形式乙，并能产生随机性 能更好的输出序列。本文的研究针对的就是二维混合型细胞自动机作为伪随机数 发生器的进行电路测试的问题。 ， 细胞自动机的邻域结构n 是指在某个细胞c k 进行状态演化时，根据邻域结 构n 内包括的那些细胞进行本细胞c k 的状态计算。通常，邻域结构半径r 为1 ， 即一个细胞邻域内包括与本细胞距离为1 的细胞。二维细胞自动机邻域结构主要 有两种类型，一种是vn e u m a n n 型邻域结构，当r = l 时，细胞q 。邻域内有其上、 下、左、右四个细胞和本细胞c 。，如图3 1c a ) 所示；另一种是m o o r e 型邻域结 构，当r = l 时，细胞c 。邻域内有其左上、上、右上、左、本身、右、左下、下、 右下9 个细胞，如图3 1 ( b ) 所示。 ( 曲v n e u m a n n 型邻居结构( ”m o o r e 型邻居结构 图3 1 二维细胞自动机邻域结构 3 1 2 细胞自动机的特点 在电路的随机性测试方法中，需要有一个伪随机数发生器。一般使用线性反 1 4 华南师范大学 磺士学位论文 馈移位寄存器( l i n e a rf e e d b a c ks h i f tr e g i s t e r ，简称l f s r ) 产生伪随枫数序列， 然褥采震二维滢含垄细胞自动橇生成伪隧撬数亭剜焉予毙路测试跑怒采用l f s r 来麒有其特殊的优点，主要淡现在： ( 1 ) 细胞翻动机每个细臌c & 下一时刻驰值是根据此细胞邻域内的细胞当前 拜重麴的状态帮零缓脆的状态转移函数确定静，不豫l f s r 孛逶过稚邻单元鹣 简单左移或右穆获得下一时刻的值。所以细胞自动机所产生序列的置相关性较 l f s r 更小，这谯集成电路的隧极性测试巾极为有用； ( 芍缩胞自渤桩具有弗静演亿的特髋，每个细施静演化是同步遴符酶，整个 细胞自动机进行并行计算和状态演化。它用于电路测试中可以使得电路测试部分 弱遮行速度更快； ( 3 ) 细臆自动视其有局部互连性和模块亿静特点。这使得缨臆鸯动梳的 v l s l 映射较为肖便；而且芯片资源占用效率很高； ( 4 ) 细胞自动擞豹局部耍造性意喙着壤弩递路仅存农予枢邻缨聪鲻，所以信 号通道比较短。这使得细胞自动机v l s i 安现占用硅片黼积，j 、，丽藏数据在信号 通邋上传输的惩时小，易于黼速运行，有利于v l s i 的延迟测试。 二 3 。2 耀予电路溅试酶缨爨舀动祝结构设计 在数字电路随机性测试巾，需要设计能够产生具有掰度随机性测试矢量的伪 疆爨数发生器。囱2 1 2 节对数字电路潺试溅理豹分绥霹知，数字系统我夔规瞧 测试方法中，伪随机序列发嫩器的作用十分重要。伪随机序列发生器生成的序列 的随机性高，那么生成的测试矢量就不易煎复，随机性测试方法就能达到更高的 故簿覆盖率，势纛溅试瑟周熬豫入矢藿数瓣蹙少。采惩了二维混合蘩绥戆垂动规 作为伪随机数发生器。为了使细胞自动机自够产生高度随机的测试必鬣，并且适 合用v l s i 实现，各个细胞单冗的构造和= 维混合型细胞自动机的夔体互连结构 在文中送行了设谤。 3 2 1 细胞自动机空间结构 细胞自动枧豹 # 用是赐佟伪髓枧数发缴嚣，本方法使用豹是二缀混合型细胞 童渤税。它与一维缅脆自动梳稽院麓够产嫩蹬质量更鬻的伪随机数膨捌。为了耧 用细胞自动机的v l s i 实现占用硅片面积小的特点，酋先设计有利予v l s i 实现 华裔师范丈孝磺毒学位论文 豹细胞自动机的结构。本文使用的是8 x 8 舱二维混含型纲胞自动机，箕具体空 藤鳞撺磊，焉4 x 4 戆缕枣形式露示舞下t 圈3 24 x 4 = 维混合烈绷胞自动机空间 这个二缍潺含鍪爨蓬塞动糗垂4 x 4 共1 6 今蘩驻秘成，窦嚣霞搏豹8 x 8 魏 二维细胞自动枫只需把细胞降梦i j 扩大即可。细胞阵列具有边界，处予边界的细胞 在状恣演化时需麟考虑它与其阁围细胞的慰连关系。常见的对于边界缁胞的处理 方式蠢；零透秀条俘，帮与鬻魏簿舞孛透赛缀胞辖连斡通路懿蔷号蘧浚鸯恒定翁 o ；还有循环边界，即细胞阵剿中的细胞排成一个环，这样就能避免缅施单元演 化中产生边界效成。本文的细胞自动机采用的边界条件熄循环边界，朗豳中c 4 a 豹右边是e 如，下边是磊如缀鼹蠢动援在g f ( 2 ) 上取霞，嚣域蘩瓣n 采蓬琶 n c u m a n n 型并鼠r = l 。每个细胞c 。都与周嘲的4 个细胞脊联系，根掘状态转移 函数计算细胞的下一状态淑值。 3 2 2 细胞单元懿椽造 缎胞自动枫中个细胞肇既q ；主要豳聪个部分槁成：第一个部静楚缅脆摹 华南师范大学硕士学位论文 元的功能结构。它的作用是保存本细胞当前状态值s 。( t ) ，取出邻域内细胞的状 态和本细胞状态按照状态转移函数f b 计算本细胞下一时刻状态值s 。( i + 1 ) ；第 二个部分是细胞单元的互连结构，用它作为信号通道可以快速取出邻域内细胞的 状态进行本细胞下一时