（计算机应用技术专业论文）基于lfsr重新播种的soc测试数据压缩方法研究.pdf

基于l f s r 重新播种的s o c 测试数据压缩方法研究 摘要 随着超大规模集成电路( v e r y 1 a r g e s c a l ei n t e g r a t i o n 。v l s i ) 制造工艺的飞 速发展，原有的垂直型芯片设计模式已向水平型设计模式即设计复用转变，通 过复用芯核( c o r e ) ，快速构建复杂的电路系统，也就是系统芯片( s o c 。 s y s t e m o n - a - c h i p ) 。s o c 设计缩短了电路设计周期，降低了设计风险，但同时 s o c 的高集成度迅速提升了测试复杂性，使测试面临巨大的挑战。如何压缩迅 猛增加的测试数据量就是挑战之一对它的研究受到学术研究机构、电子设计 自动化工具厂商和集成电路制造企业的密切关注。 本文围绕s o c 测试数据压缩方法展开研究。测试数据压缩是指对测试激励 和测试响应的测试数据进行压缩。本文研究的是对测试激励数据的压缩，介绍 了三类测试激励压缩方法：编码压缩、应用线性解压结构压缩、基于广播扫描 的压缩，并介绍了它们在工业中的应用鉴于线性反馈移位寄存器( 1 i n e a r f e e d b a c ks h i f tr e g i s t e r s ，l f s r ) 是工业界广泛使用的一种线性解压结构，本文着 重研究基于l f s r 重新播种方法的测试数据压缩问题。 本文分析了各类l f s r 重新播种方法，发现存在硬件开销大或计算复杂等 若干问题，针对这些问题，提出了一种基于部分测试向量切分的l f s r 重新播 种方法。由于l f s r 重新播种方法中编码生成的种子的长度受测试集中测试向 量确定位最大数目s 。的制约。通常地，测试向量含确定位越多，越难以编码。 我们先对测试集进行预处理，按测试向量含确定位数目的大小进行排序，然后 切分一些含确定位较多的且难以编码的测试向量，从而降低了s 。的值，提高 了编码成功率，降低了计算l f s r 种子的复杂度及种子的位数，最终获得了较 好的测试数据压缩效果。对部分标准电路硬故障集的实验结果显示：本方法的 测试数据压缩率略优于国际上同类方法；其硬件解压结构只需在一个l f s r 的 基础上添加简单的时序控制逻辑，硬件开销明显优于同类方法。 关键词：超大规模集成电路、片上系统、测试压缩、线性反馈移位寄存器、重 新播种 r e s e a r c ho nt e s td a t ac o m p r e s s i o no fs o c b a s e do nl f s r r e s e e d i n g 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 ti nm a n u f a c t u r et e c h n o l o g yo fv e r y - l a r g e s c a l e i n t e g r a t i o n ( v l s i ) ，c i r c u i td e s i g nm o d eh a sc h a n g e df r o mv e r t i c a lm o d et o h o r i z o n t a lm o d e t h ec o r er e u s ec a np r o d u c em o r ec o m p l i c a t e dc i r c u i ts y s t e m ，i e s y s t e m o n a c h i p ( s o t ) t h ec y c l eo fc i r c u i td e s i g nh a ss h o r t e da n dt h er i s kh a s r e d u c e d ，b u tt h ei n c r e a s i n gc o m p l e x i t yo fc i r c u i tm a k e st e s t i n gc h a l l e n g e sc o m e o n eo ft h ec h a l l e n g e si st e s td a t ac o m p r e s s i o n t h er e s e a r c ho ni th a sp a i dm o r e a t t e n t i o nb ym a n ya c a d e m i e s ，e l e c t r o n i cd e s i g na u t o m a t i cc o m p a n i e sa n di n t e g r a t e d c i r c u i t sm a n u f a c t u r e r s t e s td a t ac o m p r e s s i o no fs o ci ss t u d i e di nt h ed i s s e r t a t i o n ，w h i c hi n v o l v e s c o m p r e s s i n gt h ea m o u n to ft e s td a t a ( b o t hs t i m u l u sa n dr e s p o n s e ) t e s ts t i m u l u s c o m p r e s s i o ni sd e s c r i b e di nt h r e ec a t e g o r i e so fs c h e m e s ：( 1 ) c o d e - b a s e ds c h e m e s ， ( 2 ) l i n e a r - d e c o m p r e s s i o n - b a s e ds c h e m e s ，( 3 ) b r o a d c a s t - s c a n - b a s e ds c h e m e s d u et o l i n e a rf e e d b a c ks h i f tr e g i s t e r s ( l f s r ) i sw i d e l yu s e db yi n d u s t r ya sal i n e a r d e c o m p r e s s o r ，t h i st h e s i si sf o c u s e do nt h ep r o b l e mo ft e s td a t ac o m p r e s s i o nb a s e d l f s rr e s e e d i n g a f t e r w a r d ss e v e r a lt e c h n i q u e sf o ri m p r o v i n gt h ee n c o d i n ge f f i c i e n c yo ft h e b a s i cl f s rr e s e e d i n gm e t h o da r ea n a l y z e d s o m eh a v eh i g hh a r d w a r eo v e r h e a d ， a n dt h eo t h e r sn e e dc o m p l e xc o m p u t a t i o n t h e r e f o r e ，an e ws c h e m ef o rl f s r r e s e e d i n gb a s e do ns y n c o p a t i o no fs o m et e s tp a t t e r n si sp r e s e n t e di nt h ed i s s e r t a t i o n t h er e s e a r c hs h o w st h a tt h es i z eo fl f s rs e e dd e p e n d so nt h em a x i m a in u m b e ro f s p e c i f i e db i t si nt e s tp a t t e r n s t h em o r es p e c i f i e db i t sat e s tp a t t e r nh a s ，t h em o r e d i f f i c u l t l y i ti se n c o d e da sl f s rs e e d f i r s t l y , t e s tp a t t e r n si nat e s ts e ta r e r e o r d e r e da c c o r d i n gt ot h en u m b e ro fs p e c i f i e db i t st h e yh a v e ；a n dt h e ns o m e p a t t e r n sa r es y n c o p a t e d ，w h i c hh a v eal o to fs p e c i f i e db i t sa n da r ee n c o d e dh a r db y l f s r t h u san e wt e s ts e ti sp r o d u c e da n de n c o d e da sl f s rs e e d s t h ep r o p o s e d m e t h o di n c r e a s e sp r o b a b i l i t yo fs u c c e s s f u le n c o d i n g ，r e d u c e st h es i z eo fs e e d s ，a n d a c h i e v e st h eb e t t e rc o m p r e s s i o nr a t i ot h a ns i m i l a rs c h e m e s i ta l s oh a sv e r ys i m p l e d e c o d i n gc i r c u i tw h i c ho u t p e r f o r m ss i m i l a rs c h e m e s t h ed e c o d i n gc i r c u i to n l y c o n s i s t so fa nl f s ra n das m a l ls e q u e n c em a c h i n e k e y w o r d s ：v l s i ；s o c ；t e s td a t ac o m p r e s s i o n ；l f s r ；r e s e e d i n g 插图清单 图1 1s o c 测试访问结构原理图 图1 2 测试压缩结构原理图 图2 - 1 哈夫曼编码树 图2 2 应用于差分测试集的循环扫描结构1 2 图2 3 高斯约当消元法解线性方程组有解1 4 图2 4 高斯约当消元法解线性方程组无解。1 4 图2 5 一种纯异或网络构成的解码结构 1 5 图2 6 测试向量广播到不同的子待测电路1 6 图2 7i l l i n o i s 扫描结构的操作模式1 7 图3 1 标准的l f s r ( 异或门外接的l f s r ) 图3 2 状态转移矩阵m 图3 3 标准l f s r 的实际数字电路。 图3 4 标准l f s r 的另一种状态转移方程2 l 图3 5m o d u l a rl f s r 和它的状态转移方程。2 l 图3 6 与扫描链相连的度数为3 的l f s r 2 3 图3 7 马尔可夫链的结构 图3 8 多多项式l f s r s 重新播种方法。2 6 图3 9 变长度l f s r s 重新播种方法的数据形式。2 7 图3 1 0 变长度种子l f s r s 重新播种方法的硬件解压结构。2 7 图3 1 l 部分动态l f s r 重新播种的例子2 8 图3 1 2 上例对应的方程组 2 9 图4 1 切分测试向量后的重新播种3 l 图4 2 种子存储在a t e 上的硬件结构框图。3 7 图4 3 种子存储在r o m 中的硬件结构框图3 7 表2 1 表2 2 表2 3 表2 - 4 表2 5 表3 1 表3 2 表4 1 表4 2 表4 3 表格清单 四类编码压缩方法l o 哈夫曼编码表1 0 3 位游程码1 l g o l o m b 码编码表 f d r 码编码表。1 3 最高次数为n 的本原多项式数目2 2 本原多项式的组成项2 3 对切分测试向量个数的探测3 2 本方案的实验结果3 8 本方案与混合码的比较3 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 盒魍兰些太堂或其他教育机构的学位或证书而使 用过的材料与我一同工作的同志对本研究所做的任何贡献均i f , 在论文中作了明确的说 明并表示谢意。 户 靴做储解。乃印辩醐。婶6 月哆日 f 学位论文版权使用授权书 本学位论文作者完全了解 金世王业太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅本人 授权 金胆王些盍堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位躲印导师躲獬 签字日期：7 年6 月 日签字日期：。争。7 年月i , t - e t 学位论文作者毕业后去向： 工作单位； 通讯地址： 电话： 邮编： 致谢 时光荏苒，回首三年的硕士学习经历，我由衷地感谢我的导师粱华国教授， 本论文的研究工作也正是在他的悉心指导下完成的。梁教授将我引入了芯片测 试领域。他的缜密的思维、敏锐的洞察力、渊博的知识，以及极富启发性的建 议，为论文的最后完成起到了关键性的作用。在他的身上我深切体会到严谨的 治学态度和一丝不苟的工作作风。这些必将令我受益终身。同时也真诚感谢导 师平日的谆谆教诲，和蔼可亲的关怀和鼓励。在此，我谨向导师表示最诚挚的 敬意和由衷的感谢! 感谢合肥工业大学系统结构研究室的欧阳一鸣副教授、易茂祥副教授、陈 田、黄正峰、刘军等老师。与他们的讨论使我在研究中受到了很多的启发，也 感谢他们为我提供了许多生活上的关心和帮助。感谢方祥圣、胡志国、于静、 张磊、陶珏辉、詹凯华、叶益群等研究生同学，与他们的合作和讨论，开阔了 我的思路，促使我顺利地完成学业。 此外，我还要感谢合肥工业大学计算机与信息学院的全体领导和老师。 最后，感谢我的父母，谢谢他们给予我的支持和鼓励l 作者；李扬 2 0 0 7 年5 月 第一章绪论 众所周知，数字数据处理的概念对我们的社会已经产生了巨大的影响。早 期的数字电子系统基于磁控开关或继电器，它们主要用来实现非常简单的逻辑 网络。在人们发明真空管后，第一台完整计算机的实现，数字电子计算的时代 由此全面开始。1 9 4 7 年，b e l l 实验室发明了晶体管。1 9 5 6 年出现了第一个双极 型数字逻辑门。1 9 5 8 年，美国德州仪器公司的j a c k k i l b y 提出了集成电路( i c ) 的构想。在2 0 世纪6 0 年代，g o r d o n m o o r e 预见了在一个单片上集成的晶体管 数目将随时间呈指数规律增长。这就是著名的摩尔定律( m o o r e l a w ) 。根据摩 尔定律，芯片的集成度每3 年增加4 倍【1 1 从晶体管晶体管逻辑( t t l ) 到 m o s 数字集成电路，伴随着集成电路制造工艺的提高，集成电路的集成密度、 速度和性能在过去的几十年间，经历了一场翻天覆地的革命，集成电路芯片的 应用早已深入到人们生活、工作的方方面面。 集成电路的发展已成为当代科技最引人注目的焦点之一。人们对集成电路 的可靠性要求越来越高，特另在军事、航天航空、工业控制、金融、通信、医 疗等领域。小小的故障可能会造成无法弥补的巨大损失，因此保证集成电路可 靠性的测试就越来越受到人们的重视。由于集成电路规模的迅速增大，使得对 其进行完全测试变得越来越困难，因此对测试方法的研究有重大的理论意义和 实用价值鲫。 1 i 系统苍片测试概述 集成电路测试是检测集成电路芯片中那些由生产制造过程而引入的缺陷 p 】。集成电路制造工艺的进步使芯片上晶体管的数量按照摩尔定律增长，单个 芯片上已经可以集成上亿个晶体管，并且时钟频率高达千兆赫兹的程度，预计 到2 0 1 0 年芯片上的晶体管可达到百亿数量级。这样的发展趋势对芯片测试的成 本和难度都有深刻的影响。 原有的垂直型芯片设计模式，即一个厂商负责从规格定义到行为级、逻辑 级，门级和版图级的整个芯片设计过程，由于其设计周期长，风险大，已越来 越不能满足市场要求1 4 】2 0 世纪9 0 年代中期，一种新的水平型设计模式一一 设计复用出现了，通过复用一些经过验证的电路模块，可以快速构建一个复杂 的系统。我们称这类可多次重复使用的电路模块为芯核( c o r e ) 。而基于芯核复 用实现系统级功能的芯片称为s o c 。如图1 1 s o c 测试访问结构原理图所示，测 试源( s o u r c e ) 用于产生测试数据，测试池( s i n k ) 用于分析比较测试响应。测试就 是对电路施加输入激励( i n p u ts t i m u l u s ) ，再将响应值与预测数据进行比较，评估 缺陷的过程。测试访问机制t a m ( t e s t a c c e s sm e c h a n i s m ) 用于传输测试数据。 图1 1s o c 测试访问结构原理图 系统芯片( s y s t e m o nac h i p ，s o c ) 可定义为具备完整系统构架与功能的 晶片，其构架包含可执行控制、运算或信号处理功能的处理器、记忆体、周边 电路及系统i p 特定逻辑电路。s o c 是在单片上实现全电子系统的集成，它可将 信号采集、处理和输出等完整的系统集成在一起，成为一个有某种应用目的的 电子系统晶片l5 1 。 s o c 的设计模式一方面缩短了设计周期，另一方面使测试面临巨大的挑 战。 ( 1 ) i p 核供应商和s o c 集成商的分离，使得s o c 集成商对i p 核的测试变 成黑盒测试，难以对测试进行优化； ( 2 ) i p 核的多样性加剧测试的复杂性。i p 核类型多样，有数字逻辑核、存 储器核、模拟、混合核等；设计形式也分为软核、固核、硬核三种。就可测试 性设计( d e s i g n f o r t e s t ，d f t ) 方法而言，又有内建自测试( b u i l t i n s e l f - t e s t ， b i s t ) 、扫描测试、边界扫描测试、测试点插入等1 6 j 。 ( 3 ) 深亚微米工艺的发展，晶圆和芯片尺寸的增加，晶体管密度增大，带 来芯片功耗的增长，增加了测试难度。 ( 4 ) 芯片时钟速度的不断提升，使全速测试( a t s p e e dt e s t ) 显得越来越重 要。自动测试设备( a u t o m a t i ct e s te q u i p m e n t ，a t e ) 不得不面临持续提高时 钟速度的压力。 ( 5 ) 测试资源极其有限。a t e 通常是耗资几百万美元的测试平台。a t e 的 成本因素与i o 通道数量、存储器深度、操作频率以及测试精度有关【7 ，| l 。a t e 只能通过封装引脚，在设计的边界上操作芯片，其成本的主要部分是芯片花在 a t e 插座上的时间。如果测试仪执行的测试程序非常复杂，包含大量的测试向 量，重新加载测试向量增加了“在插座”时间，也就增加了测试成本对测试 向量集合进行压缩可以有效降低测试成本。 2 1 2 测试资源优化方法 s o c 测试对测试资源提出了更高的要求。a t e 的测试成本始终保持迅速增 长。现在用来测试一个复杂的集成电路往往要花费数百万美元。根据1 9 9 9 年的 国际半导体技术报告( h t t p ：p u b l i c i t r s n e t f i l e s 1 9 9 9s i ar o a d m a p h o m e h t m ) ， 到2 0 1 0 年使用一台高速测试仪的花费将超过两亿美元，这样，集成电路的测试 费用将超过制造费用【9 】。随着电路内部节点与外部引脚数量比例的不断增加， 通过系统i o 引脚，很难对电路内部节点状态进行观察和控制，这使得传统的 直接探测测试方法已越来越不能满足实际的需要再加之，a t e 的i o 通道的 容量、速度、精确度和数据存储空间有限，对测试资源进行优化显锝异常重要。 1 2 1 测试集紧缩( t e s ts e tc o m p a c t i o n ) 测试集紧缩方法是通过自动测试向量生成( a u t o m a t i c t e s tp a t t e r n g e n e r a t i o n ， a t p g ) 算法来压缩测试集，得到数据量更小的测试向量。这种方法分为动态和 静态压缩两种 1 0 , 1 1 l ，不需要增加任何的硬件开销。采用这种方法，在s o c 测试 应用时，将施加更少的测试向量。由于任何模型故障都可以通过较少的测试向 量来检测，这种方法会导致降低非模型故障的故障覆盖率 1 2 1 。 1 2 2 测试数据压缩( t e s td a t ac o m p r e s s i o n ) 随着集成电路工艺的发展，i p 核复杂性提高，单个芯片上集成更多的i p 核，s o c 的测试数据量也迅猛增加为了有效测试s o c ，各i p 供应商向s o c 集成商提供i p 核的同时，也提供了测试向量。一个典型的a s i c 芯片就有数百 亿位的测试向量。测试数据压缩作为一种非常有效的资源优化方法，主要用于 减少所需存储的测试向量。测试向量集经过压缩编码后，可以缩小2 0 倍以上。 测试设备随后将压缩编码后的数据传送到芯片的解码电路。解码电路再还原出 原始的测试向量，施加到被测电路完成测试。由于测试向量既包括测试激励又 包括测试响应，下面分开讨论。图1 2 是测试压缩结构原理图。 压缩后的测 解 激励一响应 压缩 压 试q 缩菸潮 压 叫i( c o p e ) b路 专 缩 电 电 路 l 图i 2 测试压缩结构原理图 的涓 应 ( 1 ) 测试激励压缩 测试激励压缩方法可分为三类：基于编码的压缩、基于线性解压结构的压 缩和基于广播扫描的压缩【1 3 d 5 1 。 基于编码的压缩方法首先通过对测试向量进行差分预处理，利用差分向量 上游程比较大的特点，针对差分数据采用特定的编码方法进行压缩。在芯片内 部设置解码电路，将经过压缩后的向量重新解码成原始测试向量，并施加到待 测电路上。编码方法主要有统计码1 1 6 l 、字典编码【1 7 。1 9 1 、哈夫曼编码【2 0 2 2 1 、连续 长度码【2 3 。2 6 1 和g o l o m b 码【2 7 1 、f d r 码【2 8 l 和混合码【2 9 l 等。 基于线性解压结构的编码方法通过特定的解压结构把来自测试仪的数据 展开，来填充扫描链。常用的线性解压结构有l f s r 3 0 l 、细胞自动机、环形计 数器 3 1 , 3 2 】、折叠计数器【3 3 0 7 】等。从l f s r 或者其他有限状态机出发对测试数据 进行压缩是一个研究热点。 基于广播扫描的压缩方法特别适用于多扫描链。常用的有i l l i n o i s 扫描 3 8 , 3 9 】、多输入广播扫描1 4 0 、可重置的广播扫描喇】、虚扫描0 4 外 ( 2 ) 测试响应压缩 测试响应数据压缩研究主要集中于通过设计一个压缩电路对扫描链输出 数据进行压缩。通过这样的电路设计，不仅可以减少测试设备需要提供的测试 通道数目，也可以增加允许设计的扫描链的数目。从而减少单个扫描链的长度， 也就减少了测试时间，达到了减少测试成本的目的。根据响应测试压缩方法所 侧重的方面不同，可以分为空间压缩、时间压缩和空间时间混合压缩。其中， 空间压缩方法有z e r o a l i a s i n g 4 6 1 、x c o m p a c t l 4 外、x b l o c k i n g 4 s , 4 9 1 、 x m a s k i n g 5 0 , 5 1 】、x i m p a c t 4 5 i 。时间压缩方法最典型的是采用m i s r 。空间和时 间混合压缩方法主要有o p m i s r 5 2 i 和q - c o m p a c t o r 5 3 1 。 1 2 3 测试调度 在图1 1 中，s o c 测试结构分为测试激励源、测试响应池和测试访问机制。 测试调度与测试访问机制相关，通过合理地调度各个i p 核实现并发测试，能有 效地缩短s o c 测试时间，降低测试成本。对于基于总线的t a m ( t e s ta c c e s s m e c h a n i s m ) 结构，测试调度问题是指：给定有n 个芯核的s o c 和测试总线宽度 w 。，为每个芯核设计w r a p p e r ，分配适当的测试总线，使总测试时问最短。 测试调度问题可以映射为多处理器任务调度( m u l t i p r o c e s s o ro p e ns h o p s c h e d u l i n g ) 5 4 】问题或二维，三维装箱问题( b i np a c k i n g ) 。对于这些n p 问题，研 究者采用了各种启发式算法，包括线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ，i l p ) 、 混整型线性规划( m i x e di n t e g e rl i n e a rp r o g r a m m i n g ，m i l p ) 、遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 、进化策略( e v o l u t i o n a r y s t r a t e g y , e s ) 、粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ) 和图论( g r a p ht h e o r y ) 4 等。在考虑这些测试调度算法的同时。很可能还要考虑测试功耗、布线、面积 开销、芯核层次结构等约束条件。 1 2 4 低功耗测试 由于芯片集成度及规模的不断增加和工作频率的不断提高，集成电路的功 耗随之呈指数形式增长，并且测试期同的功耗会比芯片正常运行时的功耗高出 许多。低功耗测试技术也是一个研究热点。 功耗分为两类：动态功耗和静态功耗。测试期间的动态功耗主要体现在在 扫描时扫描链中大量的跳变和电路产生的无用跳变上。动态功耗技术瞰l 多围绕 如何降低扫描链或电路的跳变率，而不影响测试覆盖率和测试时间来进行研究 静态功耗由漏电流和来自电源的其它电流引起。在较深亚微米的工艺下，静态 漏电流不断增大，传统的i d d q 技术面l 临很大的挑战，这方面的研究也很多。 另一方面，由于在正常功能状态下，很多测试电路是不需要运行的，时钟门控 和电源门控法是最常用的可以进行功耗控制及管理的有效方法。二者的目的都 是让处于非激活状态的电路消耗尽可能少的功耗。 1 3 研究的意义和现状 随着v l s i 制造工艺的进步，电路的集成度越来越高。原有的垂直型芯片 设计模式已向水平型设计模式设计复用转变，即通过复用芯核( c o r e ) 快速 构建复杂的电路系统，也就是片上系统s o c ( s y s t e m o n a - c h i p ) 。s o c 设计缩 短了设计周期，降低了设计风险，但同时s o c 的高集成度迅速提升了测试复杂 度，使测试面临巨大的挑战。其中，如何压缩迅猛增加的测试数据量就是挑战 之一，对它的研究受到学术研究机构、集成电路设计商、电子设计自动化工具 厂商和集成电路制造企业的密切关注。 先后出现了一系列的编码方法，如：o o l o m b 码【2 7 1 、f d r 码【2 8 和混合码口9 1 。 它们先对测试向量进行编码，再通过解码电路在测试过程中还原测试向量。这 些编码方法都具有很好的压缩效果，尤其是混合码【2 引，作为一种非常有效的改 进方法，它首先使用f d r 码编码交替的连续“o ”和连续“l ”，并对编码以后 的结果重新统计，按照频率由高到低排列建立字典，并再次用s h i f t e d f d r 码1 5 6 j 对字典的索引进行编码。经过这样的两次编码，大电路的压缩率有了明显提高。 另外，线性反馈移位寄存器l i n e a r f e e d b a c k s h i f t r e g i s t e r s ( l f s r ) 重新播种也是 一种非常有效的测试数据压缩方法。 在当前工业界，一些e d a 厂商已经在他们所设计的工具中引入了测试数据 压缩，如：m e n t o rg r a p h i c s 公司的t e s t k o m p r e s s 工具 5 7 1 和c a d e n c e 公司的 s m a r t b i s t 工具【5 3 】。这些商业工具目前都是基于线性反馈移位寄存器重新播种 【3 0 】的。 5 l f s r 重新播种方法的思想核心是将确定测试集编码成l f s r 种子，在测试 过程中，将种子作为l f s r 的初始状态，自动展开成目标测试向量通常在一 个确定测试集中，确定位只占1 - 1 0 1 5 9 】，而其它都为无关位。在求解种子的过 程中，我们只需考虑确定位，也就是说种子的长度极大依赖于确定位的个数。 由此，种子的位数就远小于测试向量的位数，使得测试数据得到有效的压缩。 最初，l f s r 重新播种的机制由k o e n e m a n n 提出。他在分析了l f s r 序列 的线性相关性后指出，要使l f s r 编码种子失败的概率降低到l o ，种子的位 数应为s 。+ 2 0 p ，其中s 。为测试集中所有测试向量含确定位的最大数目 此后，一系列提高l f s r 编码效率的策略随之产生其中，多多项式l f s r 重 新播种 6 0 , 6 1 1 方法使种子的位数降至s 。“，由于它在原有l f s r 的基础上增加 了一个异或网络来实现多个多项式的选择，虽然增加了编码的成功率，但硬件 结构比较复杂。变长度种子l f s r s 6 2 ，6 3 l 方法在多多项式l f s r s 重新播种方法的 基础上，将含确定位数目不同的测试向量编码成长度不等的种子，进一步提高 了编码效率，但仍然存在硬件结构复杂的问题。动态l f s r 重新播种t “舒1 方法 是在生成测试向量的过程中，种子不断增加地变化，并且允许部分重新播种， 硬件实现较上述两种方法简单，但由于需要针对多个测试向量甚至整个测试集 中所有测试向量共同寻找种子，需求解的线性方程组规模很大，这就明显地提 高了计算种子的复杂性本文正是针对l f s r 重新播种方法及其改进方法中存 在的问题，提出一种新颖的基于部分测试向量切分的l f s r 重新播种方法。 1 4 本文的贡献及章节安捧 本文开展的研究受到了国家自然科学基金“系统芯片s o c 外建自测试方法 研究”( 9 0 4 0 7 0 0 8 ) 和安徽省自然科学基金“基于测试源划分的测试方法研究” ( 0 5 0 4 2 0 1 0 3 ) 等科研项目的资助。主要贡献有； 本文以测试数据压缩中对测试激励的压缩作为研究范畴，在全面分析测试 激励压缩方法的基础上，针对最普遍最常用的l f s r 结构，在前人研究的基础 上，提出了一种新颖的l f s r 重新播种方法。在使用l f s k 编码种子前，我们 先对测试集进行预处理，切分一些难以编码的测试向量，其目的是为了降低测 试集s 。的值。这是因为l f s r 编码的成功率与s 。密切相关，测试向量含确 定位越多，越难以编码。切分难以编码的测试向量正是通过降低s 。的值，而 达到提高编码成功率的目的，这样不仅降低了计算种子的复杂度。而且还降低 了种子的位数，获得了较好的压缩效果对部分标准电路硬故障集的实验结果 显示，压缩效果与混合码f 2 9 】相当。而且本方案的硬件实现开销明显优于混合码 | 2 9 1 。本方案只需在一个l f s r 的基础上添加简单的时序控制逻辑，并且，l f s r 种子可以存贮在片外也可以存贮在片上。当种子存贮在片外的测试仪中时，由 于种子具有等长度的特性，为测试仪与测试电路的测试数据通讯提供了方便。 6 本文的章节安排如下： 第2 章测试激励压缩方法。本章在介绍测试激励压缩的概念和评价标准的 基础上，详细分析了各类测试激励压缩方法，并对它们进行了比较和总结。最 后介绍了工业中测试激励压缩方法的应用实例。 第3 章l f s r 重新播种方法。本章首先介绍了l f s r 的基本结构及其相关 的理论知识。再在此基础上，介绍了l f s r 重新播种方法及其各类改进方法。 第4 章基于部分测试向量切分的l f s r 重新播种方法。本章在分析l f s r 重新播种方法及其改进方法的基础上，提出了一种新的l f s r 重新播种方法， 该方法首先切分测试集中含确定位较多的难以编码的测试向量，再和未被切分 的测试向量共同组成新的测试集，并将新测试集编码成种子，从而实现测试数 据压缩。此方法具有测试数据压缩率高且硬件开销小的显著特点 第5 章总结与展望。本章总结了本文的研究工作，并就现实问题，对以后 的研究作出了展望。 7 第二章测试激励压缩方法 伴随着集成电路制造工艺的提升，测试集成电路所需要的数据量迅猛增加。 芯片集成密度的增加使大规模的设计具有更多的扫描单元和故障。为了获得和 以往一样高的测试质量，就需要更多的测试向量用于测试延时故障、固定型故 障等其他类型的故障测试。传统的测试将测试激励和测试响应都存放在a t e 上。但是a t e 的速度、存储容量、i o 通道都是有限的，使得芯片与测试仪之 间测试数据传输的带宽相对很小这就形成了测试的瓶颈。突破瓶颈，实际上 就是要减少测试时间，降低测试成本。很显然，测试时间不会比测试数据传输 时间更短。 测试时间测试仪上的数据量( 测试仪通道数测试时钟频率) ( 2 1 ) 测试压缩能够有效地减少测试数据量，降低对测试仪存储容量和测试数据 传输通道的需求，从而减少测试时间。而且测试压缩与传统的扫描测试的设计 规则和测试生成流程兼容，很容易应用于工业。 测试压缩是一个非常活跃的研究领域。2 0 0 2 年i e e ed e s i g n & t e s t 专门主 办了关于测试数据压缩的圆桌会议，国际上知名的测试专家在会议上讨论了各 种测试数据压缩方法，并试图找出测试压缩的极限 6 6 】 我们先分析一下测试数据。在测试向量自动生成( a u t o m a t i ct e s tp a t t e r n g e n e r a t i o n ，a t p g ) 过程中，由于采用通路敏化，只有那些和敏化通路相关的原 始输入才需要赋确定值，我们称其为确定位( s p e c i f i e d ( c a r e ) b i t s ) ；其他的原 始输入无论赋何值都不影响目标故障覆盖率，我们称其为无关位( d o n tc a r e b i t s ) 。测试数据之所以能被l o 倍甚至1 0 0 倍的压缩，是因为测试数据通常含有 很少的确定位，这些确定位可能只占整个数据量的l 到5 ，剩下的就是大量 的无关位，它们的赋值并不影响测试故障覆盖率。除此以外，由于在a t p g 算 法中，故障模型的结构化又使得测试向量间有很强的相关性，相邻的测试向量 间的差异往往是很小的。这些因素的存在使我们获得高的测试数据压缩率成为 可能。 测试压缩结构主要包含测试激励压缩( 片上表现为解压缩电路) 和测试响 应压缩，如图1 2 测试压缩结构原理图所示整个测试流程如下：首先使用离 线的软件工具对原始测试向量进行压缩，并将压缩后的测试向量存储到测试仪 中。在测试准备阶段，将压缩后的数据装载到测试激励解压缩电路，解压缩电 路再将被压缩的测试数据解码后通过扫描链施加到待测电路( 芯核) 上。在测 试阶段，待测电路处于功能状态，捕捉测试响应，最后再通过扫描链将响应数 据传送给响应压缩电路压缩，压缩后的结果和测试节点上存储的期望结果相比 较，以确定芯片是否存在故障。不难看出，测试压缩结构与内建自测试( b u i l t - i n s e l f t e s t ，b i s t ) 结构很相似。实际上，许多测试压缩技术，都源于b i s t 研究 例如，基于l f s r 的伪随机发生器用于产生测试向量就可以看作是一个测试向 量解压缩电路，存储在片外的种子就是压缩后的测试数据。正是由于测试压缩 研究学者们在b i s t 研究的基础上，展开了新的广泛的研究，创造出多种多样 的测试压缩方法，使得测试压缩逐渐脱离了b i s t 的范畴，发展成一个相对独 立的研究方向。 测试压缩包含测试激励压缩和测试响应压缩两个方面，由此形成了两个主 要的研究领域。一般而言，测试激励压缩为无损压缩( c o m p r e s s i o n ) ，测试响应 压缩为有损压缩( c o m p a c t i o n ) 。 2 1 测试激励压缩方法分类 测试立方或测试集( t e s tc u b e ) 是指测试向量的集合，其中存在大量的a t p g 过程中未被赋值的无关位。测试激励压缩是无损压缩，我们必须保护测试向量 中的确定位，用以确保故障覆盖率。也就是说，解压后移入扫描链的测试向量 中的所有确定位必须与原始测试向量中的确定位匹配。 评价测试激励压缩方法的指标是压缩率( c o m p r e s s i o nr a t i o ，c r ) c r - - ( 1 - 熹) 1 0 0 ( 2 2 ) 测试激励压缩方法可分为三类：编码压缩方法、基于线性解压结构的压缩 方法、广播式扫描压缩方法。 2 1 。1 编码压缩方法 编码压缩方法通过测试压缩码来编码测试向量。这类方法将原始测试集划 分为各种符号块，每种符号块用码字来替换，从而形成压缩数据。解码时，解 码器将码字替换为原来的符号块，还原测试集。举例来说，一些编码压缩方法 是针对向量中的“o 或l 的游程”进行压缩。“游程”是指连续o 或l 组成的串， “游程长度”是连续o 或连续l 的数目。另一些编码压缩方法则是基于对符号 块出现频率的统计。 在测试压缩方法中，符号块含有的位数可以是定长的也可以是变长的。码 字含有的位数可以是定长的也可以是变长的。因而，测试压缩方法又可以分成 四类，如表2 1 所示。 在定长到定长的编码中，测试集被划分为n 位的数据块，即符号块，这些 符号块被编码为b 位的码字( b n ) ，由此形成了符号块与码字一一对应的字典。 不难看出，符号块有2 “种可能，码字有2 6 种可能，在字典中把所有的可能性 都列举出来是不切实际的。设s d i c t i o 。表示字典中的符号块集，s d m 表示出现 在原始数据中的符号块集，如果s d m t z s d i c t i 。a r y ，则称完全字典f 】，否则称部分 字典 1 8 , 1 9 l 。字典编码需要存储的数据量比较大。 9 表2 1 四类编码压缩方法 类别编码压缩方法举倒 定长到定长字典编码 1 7 1 8 , 1 9 l 定长到变长哈夫曼编码f 2 i 】 变长到定长连续长度码1 2 3 l 变长到变长g o l o m b 码1 2 ”、f d r 码【2 。1 表2 2 哈夫曼编码表 符号块频率测试向量段哈夫曼码 s o2 20 0 1 01 0 s 11 30 1 0 00 0 s 270 1 1 01 1 0 s 3 5 o l l l 0 1 0 s 430 0 0 00 1 1 0 s 521 0 0 0o l l l s 62o l o l1 1 1 0 0 s 7l1 0 l l1 1 1 0 l o s 8l0 01 1 1 0 l l s 910 0 0 1l l l l o o s 1 0l1 1 0 11 1 l l o l s l lll l l ll l l l l 0 s 1 210 0 l ll l l l l l s 1 3 o“l o s 1 4o1 0 l o s 1 5o1 0 0 l 统计码是定长到变长编码压缩方法的一种重要形式。其中，哈夫曼编码 ( h u f f m a n ) 1 2