（通信与信息系统专业论文）面向dft的测试数据压缩算法研究.pdf

摘要 摘要 由于集成电路设计趋势正快速朝向所谓系统芯片( s o c ) 设计方法迁移，并且 各种预先设计和验证的芯核集成在一个芯片上，对于外部自动测试设备，这种复杂 的设计正产生严重挑战。虽然这种基于芯核的设计风格大大增加了设计产量，创新 的技术加快了产品投放市场，但与此同时，测试数据量和测试时间也正在快速增 加。为了解决这些问题，目前主要有两种方法：一种是使用内建自测试。为了减少 测试成本，将测试器移到芯片上，直接在芯片上生成测试模式这种方法的优点是 芯片无需额外i o 管脚，克服了测试难以进入问题；除了芯片的生产测试外，同时 也能满足日常的维护测试和在线测试。另一种解决方案是基于测试源的划分，将部 分芯片上的测试模式生成资源移到离线的自动测试设备上，通过数据压缩技术来 减少存储需求和测试时间，芯片上的解压器成为一种无存储数据源，因此，可以进 一步减少测试硬件成本，更好地权衡自动测试设备与片上测试器的成本分配。 本文在f d r 编码和游程编码的基础上，提出了一种改进的压缩编码。该文在 测试序列中直接编码连续的“0 ”和“1 ”以及交替变化位的长度，压缩一个预先计 算的测试集，无需像其它文章中受限制仅仅编码连续的“0 ”。这种交替与连续长 度码由两部分组成，即交替和连续部分。它的解压体系结构是个简单的有限状态 机并且不需要一个分离的循环扫描移位寄存器。试验结果显示，这种编码能够有效 地压缩测试数据，压缩效率优于游程编码和f d r 编码，同时测试时间在大多数情况 下也优于游程编码和f d r 编码算法。 本人在课题研究期间作了很多有效的努力和尝试，主要工作包括以下几个方 面： 阅读了大量关于可测试性设计以及基于芯片测试的数据压缩方面的文献资料。 深入研究了游程编码和f d r 编码算法的理论以及具体实现。在此基础上提出了 改进的f d r 算法。 用e d a 工具完成了代码的编码，调试，仿真。 通过对比论证了改进的算法的优越性。 关键词自动测试设备；可测试技术；测试集；游程编码 兰直兰三查兰堡圭兰些鎏苎 a b s t r a c t as y s t e m - o n - a c h i p ( s o c ) i n t e g r a t e ss e v e r a li n t e l1 e c t u a p r o p e r t y ( i p ) c o r e s t h e s ec o r e sm u s tb et e s t e du s i n gp r e c o m p u t e dt e s ts e t sp r e y i d e db y t h ec o r ev e n d o r h o w e v e r ，i n c r e a s e dd e s i g nc o m p l e x i t yl e a d st oh i g h e rt e s t d a t av o l u m ef o rs o c s ，w h i c hi nt u r n1 e a d st oa ni n c r e a s ei nt e s t i n gt i m e o n e a p p r o a c ht or e d u c et e s tt i m ea sw e l la so v e r c o m em e m o r ya n di ol i m i t a t i o n s o fa u t o m a t i ct e s te q u i p m e n t ( a t e ) ，i sb a s e do nt e s td a t ac o m p r e s s i o na n d o n c h i pd e c o m p r e s s i o n t e s td a t ac o m p r e s s i o ni se s p e c i a l l ya p p e a l i n gf o r s o c sw i t hi pc o r e s 。f o rw h i c hb i s tt e c h n i q u e sb a s e do ng a t e - 1 e v e ls t r u c t u r a l k n o w l e d g ea r en o tf e a s i b l e s t o r e a n d g e n e r a t et e c h n i q u e se n c o d eag i y e nt e s ts e ta n dr e g e n e r a t e t h eo r i g i n a lt e s ts e td u r i n gt e s tw i t ht h eh e l po fad e c o d e r t h e yo f f e r an a t u r a lo p t i o nf o rt e s tr e s o u r c ep a r t i t i o n i n g ，b e c a u s et h ee n c o d e dt e s t d a t ac a nb es t o r e de i t h e ro no fo f fc h i p p r e y i o u sr e s e a r c hh a sf o c u s e do n r u n l e n g t hc o d i n gw h e r et h et e s ts e tisc o n s i d e r e da sas e q u e n c eo fr u n s o fz e r e ，e a c hr u nt e r m i n a t e db yao n e t h i sm a y1 e a dt oa ni n e f f i c i e n t e n c o d i n gf o rr u n so fo n e s i nt h i sp a p e ran e we n c e d i n gs t r a t e g yi sp r o p o s e d t oo v e r c o m et h i sp r o b l e m ：at e s ti sc o n s i d e r e da sas e q u e n c eo fa l t e r n a t i n g r u n so fz e r o sa n dr u n so fo n e s t h isw a y ，i tc a ns i m p l yb ee n c o d e da sa s e q u e n c eo fr u n 一1 e n g t h s t h ee x p e r i m e n t a lr e s u l t ss h o w t h a ti nm o s tc a s e s t h ep r o p o s e ds c h e m ec a np r e y i d eb e t t e rc o m p r e s s i o nr a t i o sa n dl e s st e s t ti m et h a nr u n 一1 e n g t hc o d e sa n df d rc o d e s f u r t h e r m o r e ，t h ea r c h i t e c t u r eo f t h ed e c o d e ris v e r ys i m p l e k e yw o r d sa t e ；d f t ：t e s ts e t ；r u n 一1 e n g t hc o d e 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其它个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名：弦国罕日期：加f 年莎月知日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密西 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 碳圈罕 唆弱字 日期：a 蹋# 月o 曰 日期：叮年f 月易日 第一章绪论 1 1 芯片测试技术介绍 第一章绪论 集成电路在生产中为了保证质量，必须通过测试来保证一定的成品率水平。 在集成电路生产过程中，主要有两次测试。第一次测试是在硅片加工完成后，测 试仪通过探针与管芯的焊盘( b o n d i n gp a d ) 相连，测试程序在输入端加入测试向量， 同时检查输出端的响应。如果响应与预计的相同则为合格，否则判定位测试失败。 第二次测试是在封装完成后，与第一次测试类似，测试仪通过测试程序完成对芯 片的最后测试“1 。 用户得到芯片，通常直接安装在印刷电路板( p c b ) 上，p c b 生产完毕后，直 接对p c b 进行测试。这时如果发现问题，就需要复杂的诊断过程和人工分析，才 能得到问题的原因。如果是集成电路的问题，就需要将坏的集成电路拆卸下来， 将替换的集成电路安装上去。现代工艺，很多大规模集成电路的封装往往是b g a ， 手工拆卸几乎不可能，需要专门的仪器。可见，集成电路如果在p c b 阶段才测试 出问题，对生产的影响大大高于单片的阶段m 。对于复杂的设备，如果在整机阶 段才发现集成电路的问题，其影响更是巨大。因此，集成电路生产时的测试具有 很重要的意义”1 。 测试的主要目的就是找出不合格的芯片w 。这与设计过程中的验证是不同的。 验证的目的在于证明电路设计的正确性。设计者通过验证过程证明芯片设计与设 计要求是一致的，也就是计算机内芯片的模型与设计构想是一致的。而加工厂家 通过测试过程筛选出物理实现与设计模型一致的芯片。通过验证与测试这两个步 骤就可以实现物理芯片与设计构想的一致，从而正确的完成芯片设计。测试的必 要性主要是由于集成电路的制造过程的偏差引起的。如果集成电路的制造过程完 美无缺，则设计正确的电路就没有必要测试。但是，设计验证仍然需要。 目前，大部分测试是通过加入激励。测试响应完成的。一种最直接的测试方 法就是使用功能验证的测试向量。这种方法有很大的局限性。一方面，随着集成 电路规模的增长，完全的功能验证内容太多。例如，对于一个3 2 位的加法器，其 输入共有6 5 个，为了验证这个器件的加法功能对所有的输入组合都是正确的，需 要对2 ”种输入激励全进行测试。即使假定一种输入激励进行测试只需要1 n s ，那 么整个芯片的测试也需要约1 0 0 0 年才能完成。另一方面，测试环境与验证环境完 全不同，功能验证是在计算机上进行的，它可以观察内部节点，使用异步激励。 而测试只能在基本管脚上进行，激励也必须是同步的。例如，一个异步的f i f o 华南理工大学硕士学位论文 写入和读出的时钟是异步的，对于功能验证，这不成问题。然而，对于测试，这 样的功能验证向量是无法实现的”，。 直到几年前，大多数i c 都是用功能测试法来测试的。工程师们开发出各种 测试向量来检验特定i c 的所有功能特性，并在生产过程中利用这些测试来验证 每一个单元。然而，目前的l c 太复杂了，功能测试向量的数量甚至对于最新的 a t e 来说也是太大了。工程师们认识到，一块i c 是由大量独立的或准独立的 功能块构成的，单独测试每一个功能块的效率会更高。这种方法叫做结构测试， 因为它把一个器件分成一个个功能部件，再单独测试每一个结构。为了完成这项 任务，你必须能够给功能块输入适当的向量，并且获得相应的输出。因为功能块 可能没有外部的输入端和输出端，所以你必须把一些新的结构插入到i c 中。 结构测试的目的是试图验证所有结构一一通常是门电路和存储元件，如触发 器和锁存器一一以及它们之间的大多数互连线路都工作正常。利用设计网表的门 电路级表示法，a t p g 可用算法计算出可控节点的激励源，以便你能测试各种内 部设计结构。设计的复杂性和规模日益增大，再加上存储单元数量也很大，已使 “控制”和“观察”每一个结构变得更加困难，从而促使人们开发出两种并行方 法：“扫描”和“随机测试”。 当今的大多数结构逻辑测试方法都是以全扫描方案为基础的。在全扫描方案 中，所有存储元件都连接在一起，成为一个或多个扫描链。以测试模式工作时， a t e 串行扫描输入和输出这些存储元件的数据，为测试工程师提供了充分的可控 性和可观察性。扫描测试包括：扫入图形数据( 对每一个扫描链加载) ，加上一 个或多个功能时钟周期，然后扫出捕获的响应数据。全扫描方法实质上是把任何 一个顺序设计变换成为组合设计。测试工程师把a t p g 图形存储在测试器内存中。 a t e 使用若干并行扫描链，把向量输入到电路中。芯片i o 引脚的可用性、可用 的测试器通道以及片上路由堵塞( 因测试模式中链接各个存储元件而引起的) 等 因素限制了扫描链的数量。 随机测试方法把随机数据值加到“设计输入”节点，目的是运行设计中的每 一个结构( 实际上是对它们进行随机控制和观察) 。对于内存等常规结构，这种 方法很管用。你可以借助定制设计的l f s r ( 线性反馈移位寄存器) 和移相器来 改善伪随机图形的质量。只要l f s r 装有不同的种子程序( 以启动图形生成) ， 你就可以生成可用的全部随机图形空间( l f s r 长度) 的所需分段。测试工程师 利用内部寄存器库，把处于测试模式的庞大设计分解成一个个较小的部分。有些 设计不适合用随机图形来测试。对于这些设计，你需要插入测试点来改进内部结 构的可控制性和可观测性。工程师利用m i s r ( 多输入签名寄存器) 来捕获对随 机图形的响应。当l f s r 和m i s r 成为芯片本身一部分时，用于逻辑电路的b i s t ( 内置自测试) 方法便诞生了。当今市售的逻辑b i s t 又前进了一步，使用一种 第一章绪论 全扫描方法把随机图形数据加到每一个逻辑结构上。这种体系结构考虑到了更多 的并行扫描链，因为你再也不需要为扫描链选择通向芯片引脚的路由。“” 1 2 可测试性设计技术 可测试性设计( d f t ，d e s i g nf o rt e s t ) 是芯片设计中必不可少的技术，它指 在芯片的设计阶段就考虑以后测试的需要，使得芯片容易测试。可测试性设计可 以分为两个发展方向，一是通过对芯片内部进行可控性和可观性设计，使测试更 容易。现在比较成熟的方法有内部扫描( i n t e r n a ls c a n ) 、测试点插入( t e s t p o i n t i n s e r t i o n ) 、边界扫描( b o u n d a r ys c a n ) 等等。另一种是对于测试数据进行分离， 把一些测试资源从a t e 设备中分离出来，主要有以下三种方法“。 a 测试集的压缩。通过测试生成算法( a t p o ) 来压缩测试集。使进入a t e 设备的测试集减少n “。 b 内建自测试设计( b u i l t i ns e l f - t e s t ) 。在集成电路内部增加产生激励和作 测试分析的电路，使芯片不但能完成逻辑功能，还能在外部给定测试方式命令时 进行自我测试分析，并输出结果“。 c 测试数据压缩。采用游程编码。f d r ( f r e q u e n c y d i r e c t e dr u n l e n g t h ) 等 算法来压缩测试数据n ”“。通过对i p 核供应商提供的测试集t d 进行编码，得到 小很多的测试集t e ，把t e 放入a t e 的内存中，同时在芯片上设计一个解码单元， t e 解码后就可得到t d 。如图1 1 。 史n r t a t e c o r eu n d o r t a s t 解 t d t e= = = = 码二 i n t e m a i 器 s c a rc h a l n f a t e f c h i p 图1 - 1 数据压缩的基本结构 f i g 1 1ac o n c e p t u a la r c h i t e c t u r ef o rd a t ed e c o m p r e s s i o n 1 2 1 内部扫描设计 内部扫描是一种成熟的时序电路d f t 技术。其设计思想是把电路中的关键节 华南理工大学硕士学位论文 点连接到一个移位寄存器上，当作为扫描路径的移位寄存器处于串入并出状态 时，可以用来预置电路的状态。当作为扫描路径的移位寄存器处于并入串出状态 时，可以把内部节点的状态依次移出寄存器链。如图1 2 所示，时序电路可以模 型化为一个组合网络和一组带记忆元件( 触发器) 的反馈。这些记忆元件体现了 电路的状态，但由于它们很难观测或控制，所以对时序电路的测试很困难。内部 扫描就是为了方便对这些记忆元件进行控制和观测，通过把它们修改为扫描触发 器，并连接成为扫描链( 可以移位的寄存器，扫描即移位) 。通过扫描输入口， 可以把需要的数据扫描到链中相应的单元，即可以串行地控制它们；同样，通过 扫描输出口，可以串行地观测它们“。这样一来，所有的记忆单元即可以看作为 输入( 伪输入) ，也可以看作为输出( 伪输出) ，所以，进行内部扫描设计后的 时序电路的测试可以参照组合电路测试的方式来进行。 _ 日丑_ i i i i i i i i 专 第一章绪论 测试模式下，把触发器连接成扫描链，则可以在扫描控制信号的有效条件下，把 预定的值移入触发器。接着使电路处于工作模式，整个电路动作起来，组合逻辑 中的数据被采样到触发器中。如果再次使电路处于测试模式，则可以把扫描触发 器中的内容移至输出端，以便观察。 对于实际的电路，扫描设计有“全扫描”和“部分扫描”之分，而部分扫描 的测试控制要比全扫描复杂得多。对于扫描链，可以设计为一条或多条，多条扫 描链可以并行地扫描，用以缩短测试时间”“。 1 2 2 测试点插入设计 从本质上说，测试点的插入是为了对功能数据进行方便地控制或观测。当然， 这种插入逻辑在“非测试状态下”不应该改变系统原有的功能。测试点有观测和 控制之分。观察点的插入可以直接从功能数据线上引出观测线( 或者先存到触发 器再观测) ，这样的观测点在观测时不影响其功能数据线的功能，最坏可能会产 生一定的延迟。控制点的插入通过多路器把原功能数据断开，在测试时，选择控 制的数据( 这个控制数据可以预先存在触发器里，也可以直接输入) 。控制点会 由于在设计中增加了关键路径延迟而影响设计的性能，测试点插入带来的问题是 它与高级设计流程不兼容。用于大规模s o c 的物理综合工具会产生一个完整的网 络表，以简化时序收敛问题。所以，在综合之后的网络表中加入门级测试点，可 能使物理综合过程产生的布局和时序结果无效。还可以使用其它的技术如加权随 机和偏置随机模式发生器，在不插入测试点的情况下在抗随机测试模式电路中增 加故障覆盖率n ”。 1 2 3 边界扫描( j t a g ) 设计 边界扫描是欧美一些大公司联合成立的一个组织一一联合测试行动小组 ( j t a g ) 为了解决p c b 板上芯片与芯片之间互连测试而提出的一种解决方案。 由于该方案的合理性，它于1 9 9 0 年被i e e e 采纳而成为一个标准，即 i e e e l l 4 9 1 。边界扫描是在芯片的每一个输入输出引脚上增加一个存储单元然后， 再将这些存储单元连成一个扫描通路，从而构成一条扫描链。由于这条扫描链分 布在芯片的边缘，故称为边界扫描。边界扫描占用四个芯片引脚，即测试数据输 入( t d i ) 、测试数据输出( t o o ) 、测试模式选择( t m s ) 以及测试时钟( t c k ) 。在正 常的工作模式下，边界扫描单元作为通常的输入输出器件，在测试模式下，测试 向量将扫描输入、输出芯片的引脚。边界扫描与基于扫描设计有明显的区别，前 者是在电路的输入输出端口增加扫描单元，并将这些扫描单元连成扫描通路，后 华南理工大学硕七学位论文 者是将电路中普通时序单元替换为具有扫描能力的时序单元，再将它们连成扫描 通路。 如图1 3 ，j t a g 内部的边界扫描寄存器b s r 可以看作一串实现串并转化的 缓存器。b s r 的并行口接外部引脚或内部逻辑的输入输出，串行口t d i 开始绕行 边界一周t d o 输出。当j t a g 处于t e s t l o g i c r e s e t 状态时( 由t a p 控制，其状 态图如图l 一4 ) ，b s 逻辑是被禁止的，这个时候内部逻辑的输入输出和外部引 脚直接相连，实现逻辑芯片正常功能。当处于边界扫描状态时候，外部引脚和内 部逻辑的输入输出是隔离开来的。如果是内测试i n t e s t ，b s r 的并行数据输入 输出口直接和内部逻辑的输入输出相连接，内部逻辑的输出数据信号被b s r 截 获而被串行的移出t d o 引脚，最后送到外部测试程序。同样，信号从t d i 移进 b s r 后也通过并行口进入内部逻辑的输入口。如果是外测试e x t e s t ，这个时候 b s r 并行口接的换成外部引脚而己。一般说来，边界扫描寄存器的组成单元和外 部引脚( 内部逻辑的输入输出) 一一对应就可以，但是实际上，为了更全面的测 试内部逻辑( “可观性”还是“可控性”) ，往往还增加一些b s r 单元来和内部逻辑 相连”。 图1 3 边界扫描基本结构 f i g 1 _ 3ac o n c e p t u a la r c h i t e c t u r eo fb o u n d a r ys c a n t a p 由信号控制测试逻辑按图卜4 进行状态迁移，从而使状态机产生相应的 控制信号；t c k 提供测试时钟，t m s 在t c k 的边沿转换状态：通过t d i 口将测试数 据移位输入边界扫描寄存器；同时t d o 将原寄存器中的内容移出芯片；t r s t 是可 选的测试端口，作用是将测试逻辑复位。t a p 控制器在加电时自动初始化到测试 逻辑复位状态( 禁止测试逻辑) ，当建立t r s t 或当t m s 在5 个或更多相继时钟内 为高电平时，也进入测试逻辑复位状态，为了实现边界扫描，一个器件的t d 0 以 菊花链形式与下一个器件的t d i 相连，这允许通过一个长移位寄存器对该链上器 6 件的所有i o 进行访问，t m s 和t c k 是为所有器件共用的。 图1 4 t a p 状态转移图 f i g 1 - 4f l o wd i a g r a mo ft a p 1 2 4 测试集压缩( a t p g ) a t p g 称为测试码自动生成( a u t o m e t i ct e s tp a t t e r ng e n e r a t i o n ，简称a t p g ) ， 它根据逻辑电路本身的结构用算法生成测试码，并对测试码进行压缩。一般来说 它提供三种模式“”：基础扫描模式( b a s i c s c a n ) 、快速时序模式( f a s t s e q u e n t i a l ) 、 全时序模式( f u l l s e q u e n t i a l ) 。基础扫描模式基于组合电路的，快速时序模式是 全时序模式的早期版本。实现方法是f u l ls e a f l ，就是按照e h i ps c a nc h a i n 的 规划，把电路中所有的d f f 串在一起，组成流水线的结构。检测两级d f f 之间的 组合逻辑，然后通过s c a n 通道把数据送出与期望值比较。此处的d f f 是综合时 已经经过扫描替代的s c a nd f f 。这种测试的目的是检查c h i p 在f o u n d a r y 制造过 程中的一些错误，简而言之就是检查片子上做出来的电路逻辑是不是正确的，由于 组合逻辑检测算法较时序逻辑检测算法要完善的多，所以一般都是用组合逻辑的 f a u l tm o d e l ( 主要是s t u c ka t 类型) 。 目前半导体制造工艺的迅猛发展，己使得可以生产出含有几百万个门电路的 i c 。随着s o c 尺寸和复杂程度的增加，a t p g 的测试效果越来越差。首先，设计人 员可能没有办法提供a t p g 所需的全部s o c 模型进行测试，而且，a t p g 对c p u 速 华南理工大学硕士学位论文 度和存储器的要求并不与芯片内门电路的数量成线性关系，因此对不同门电路规 模的s o c 比较难确定a t p g 对对c p u 速度和存储器的要求。其次，目前自动测试设 备( a t e ) 的速度和存储能力也不能满足对s o c 作a t p g 模式扫描的要求，这样，就 会导致降低错误查找效率，从而降低产品质量，或因增加测试时间而加大单位成 本。另外，深亚微米i c 中存在的动态失效结构只能用非常快的测试方法才能检测 到，由于a t e 采用早期半导体制造工艺，所以无法跟上最新i c 较高时钟频率的要 求。因此，全芯片a t p g 测试技术已经无法适应现代的s o c 设计。 1 2 5 内建自测试设计( b u i l t i ns e l f - t e s t ) 传统a t p g 技术性能有限，因此人们开发了一种新的d f t 技术，称为内置式自 测( b i s t ) ，它对解决s o c 生产测试中的问题非常有效。它不是在a t e 系统中存储 测试模式，而是将一个激励电路和一个响应电路加在被测电路( c u t ) 中，激励电路 会产生大量激励信号，并将其应用于c u t 中，响应电路就用来对c u t 的响应进行 评测。与a t e 不同，b i s t 的性能不受负载板或测试头电气特性的限制。 内建自测试很大程度上降低了对测试仪带宽的需求，而且适合那些在需要在 使用过程中定期测试的电路。目前，几乎所有的存储器测试都采用b i s t 。从某种 意义上说，b i s t 是把“测试仪”做到了电路内部。如图1 5 所示，它既要对待 测逻辑提供输入的测试向量，又要压缩其输出的响应，还要比较响应压缩的特征， 最终给出测试通过与否的结果。所不同的是，这个“测试仪”是专门为这个待测 逻辑而设计的，功能单一固定。例如，其“测试向量发生器”只能提供预计好的 测试向量序列( 如用伪随机序列发生器产生伪随机的测试向量序列) ，响应压缩 也按照预计好的方式进行，经过规定好的节拍后，其响应压缩的特征要与预计的 特征( 事先模拟得到) 进行比较。 如图1 - 5 所示，测试向量发生器生成电路所需的测试向量。有许多方法可以 生成激励，使用最多的方法是穷举法和随机法。计数器就是穷举法的一个较好的 例子，而线性反馈移位寄存器( l f s r ：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 则属于一种 伪随机模式发生器。响应分析器是将电路所产生的响应与已知正确的响应序列相 比较，以便确定电路的测试结果。一般地，响应分析器先将响应序列进行压缩，得 到响应的特征，然后，将其与期望的特征进行比较，以确定测试的结果。响应分析 器的典型实现是多输入特征寄存器( m i s r ：m u l t i i n p u ts i g n a t u r er e g i s t e r l 。 8 第一章绪论 1 2 6 测试数据压缩 图1 - 5 内建自测试的一般结构 f i g 1 5ac o n c e p t u a la r c h i t e c t u r eo fb i s t 随着设计技术的提高，集成电路的设计规模也在逐渐增大。测试整合在一个 系统中的电路比分别测试他们要难的多。为了减少设计和制造成本，测试这些芯 片一定要快速有效。然而随着测试数据量的增多，a t e ( 自动测试设备) 的工具成 本也越来越高“。对于芯片测试来说，减少测试数据量和测试时间的技术变的非 常重要。测试数据压缩就是将部分芯片上的测试模式生成资源移到离线的自动测 试设备上，通过数据压缩技术来减少存储需求和测试时间，芯片上的解压器成为一 种无存储数据源，因此，可以进一步减少测试硬件成本，更好地权衡自动测试设备与 片上测试器的成本分配。 最近一些有效的压缩和解压方法被提出。这些方法利用芯片上的硬件，解压存 储在a t e 中一个被编码的预先计算的测试集。比如游程编码( r l l r l 1 e n g t hc o d e ) 、 f d r 编码等。 对于s o c 测试，本文采用的是测试数据压缩的办法。对比于可控性、可观性 设计，测试数据压缩技术不需要对芯片增加太大的面积，比采用a t p g 进行测试 集压缩的方式更有效，同时不会降低故障率，比b i s t 方式需要的硬件面积更小， 性价比更高。本文在游程编码算法、f d r 算法基础上提出了一种改进的压缩算法。 通过对预先计算的测试集中的“0 ”和“1 ”的长度进行交替编码的方式来压缩测 试集。实验结果证明，此算法在当前采用的几种压缩算法中，大多数情况下压缩 率是最高的，而且实现的硬件也比较简单e 2 2 , 2 3 , 2 4 ，。 1 3 论文的章节安排 本论文共五章，分五个部分： 第一章绪论简要地讲述了测试的概念，测试技术的发展以及一些可测试性技 9 华南理工大学硕士学位论文 术。并笼统的介绍了本文将要重点讨论的数据压缩测试方法。 第二章游程编码算法、f d r 算法介绍，讲述了当前应用比较多的数据压缩算 法以及他们的硬件实现电路。并对他们的优劣进行讨论。 第三章改进的f d r 算法，详细论述了算法的产生以及它的原理和硬件实现。 并用理论证明它所用的时间比较少。 第四章实验结果分析讨论，在统一的平台上，比较改进的f d r 算法、f d r 算法、游程算法的压缩率，用图表等方法直观表现几种算法的对比情况。 第五章结论是对整个论文主要成果的总结。指出本论文研究内容的成果，及 其意义，并指出今后进一步在本研究方向进行研究工作的展望与设想。 l o 第二章游程编码及f d r 编码算法在s o c 测试中的使用 第二章游程编码及f d r 编码算法在s o g 测试中的使用 2 1 本章概述 在基于数据压缩的测试方法中，采用比较多的是游程编码、f d r 压缩等算法。 而改进的f d r 算法是在游程编码、f d r 算法的基础上得来的。所以这一章首先 对游程编码算法和f d r 算法进行一个详细的讨论和介绍。 2 2 游程编码算法 2 2 1 游程编码算法的基本原理 数据压缩技术主要采用两种方法，一种是“保真率”较高的无损压缩法；另一 种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是 很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用 的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼 ( h u f f m a n ) 编码、算术编码( a c ) 和游程长度编码( r l c ) 。其中，游程长度 编码是一种十分简单的压缩方法，编码解码的速度也非常快，因此得到了广泛的 应用。许多图形和视频文件，如b m p ，t i f 及a v 等，都采用了这种压缩方法， 尤其适用于文本( 文件) 数据压缩。 游程长度编码的主要思想是将一个相同值的连续串用其值和串长( 重复的个 数) 的数对二元组来替代。例如，在图像编码中，可以定义沿特定方向上具有相同 灰度值的相邻像素为一轮，其延续的长度称之为延续的行程即游程。游程终点 位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据。 例如，若沿水平方向有一串m 个像素具有相同的灰度n ，则按游程长度编码后， 只传递两个值( n ，m ) 就可以代替这m 个像素的m 个灰度值n 。简单来说，游 程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相 同字符的个数，恢复原来的数据。 对于只有“0 ”和“1 ”构成的测试数据，因为只有两种情况，因此其游程编 码更是简单。 华南理工大学硕士学位论文 2 2 2 游程编码算法压缩模型 在游程长度编码( r l c ) 中用2 个字节表示一个字符串：第一个字节记录连续 出现的字符；第二个字节记录重复字符出现的次数。可见，只有当rl ( 游程长 度) 2 时进行数据压缩才有意义。因此，编码时首先要判断r l 值，然后再决定是 否进行游程长度编码( r l c ) ；解码时则需读取第一字符表示当前代表的数字，然 后读取下一字符表示当前数字的长度。假如我们采用3 位长度的码字来进行游程 编码，如果游程长度超过7 位( 2 3 - 1 ) ，则再用三位进行编码，编码码表见表2 一l ，举 例如下： 输入数据流：0 0 0 0 0 01 1 1 1 1 l0 0 0 0 0l l l0 0 0 0 0 0 0 0 0 0 1 l 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 4 5 b i t s ) ( 0 ，6 ) ( 1 ，6 )( 0 ，5 )( 1 ，3 )( 0 ，1 0 )( 1 ，2 )( o ，1 3 ) 编码后：01 1 0 11 1 001 0 l10 1 101 1 1 0 1 010 1 001 1 1 1 0 1 ( 3 4 b i t s ) 表2 1 游程编码码表( k = 3 ) 群组 游程长度编码码字 0 0 0 0 lo o l 20 1 0 a l30 1 1 4 1 0 0 51 0 1 6l l o 7 1 1 l 8l l l 0 0 0 91 1 1 0 0 l 1 01 1 l o l 0 1 11 1 1 0 1 1 a 21 21 1 1 1 0 0 1 31 l l l 0 i 1 41 1 1 1 1 0 1 51 1 1 1 1 1 a 3 1 61 1 1 l l l 0 0 0 第二章游程编码及f d r 编码算法在s o c 测试中的使用 2 2 3 游程编码算法编码的实现 用游程长度编码压缩数据时，首先要计算每次连续相同字符的个数，然后将 每次连续相同的字符及个数保存起来。这种压缩数据的方法，连续相同的字符及 出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法 的流程：1 ) 打开源数据文件和压缩后的数据文件；2 ) 从源数据文件中读取字符， 并把它放入一个寄存器中，然后再循环读取后面的字符，并与寄存器中的字符相 比较。如果相等，则计数器加l ，否则，把寄存器中的字符和计数器中数写入压缩 数据文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把计数器置 1 。游程长度编码数据压缩算法流程，如图2 1 所示。 图2 一lr l c 数据压缩算法流程图 f i g 2 - if i o wd i a g r a mo fr l cd a t ac o m p r e s s i o l la l g o t i t h m 华南理工大学硕士学位论文 对于r l c 的编码部分，因为不需要在硬件上实现，所以我们可以用c 语言程序 的实现。 2 2 4 游程编码算法解码器的实现 解压器是放在芯片内部的，因此我们用v e r i l o g 语言实现它。解码器的结构 方框图如图2 - 2 。 图2 2 游程编码算法的解码器结构图 f i g 2 2a r c h i t e c t u r eo fd e c o d e rf o rr u n 一1e n g t ha l g o r i t h m 其原理简单表述如下： ( 1 ) c o u n t e r l 和c o u n t e r 2 初始设置为0 。a t e 通过e n a t e 发出“1 ”给f s m ，表 明a t e 准备好。f s m 通过e n f s m 发出高电平“1 ”给a t e ，然后a t e 开始输 入数据。 ( 2 ) 通过b i t i n 把数据输入f s m ( 有限状态机) ，根据编码规则可知，码字第1 位表示此游程代表是“0 ”还是“l ”。接收完第1 位后，接收下面的3 位 数据。 ( 3 ) 通过b i t i n 把数据输入c o u n t e r 计数器。接收3 个数据后，c o u n t e r 计数 器每时钟减1 ，直到计数器减为o 。同时输出在第二步接收的第l 位数据。 ( 4 ) 如果接收的3 位数据小于7 ，则回到第( 2 ) 步，译码下1 个游程。如果接 收的3 位数据等于7 ，则回到第( 3 ) 步，接收下面3 个数据。 从以上4 步原理出发，每步作为一个状态，可知解码器只需要4 状态的有限 状态机1 个，同时加上1 个3 b i t s 的计数器。实现后综合的面积也非常小。 第二章游程编码及f d r 编码算法在s o c 测试中的使用 2 2 5 游程算法的讨论 游程长度编码的压缩率与测试数据中“0 ”和“1 ”重复出现的长度有关。表 2 2 给出了对长度不同的测试数据，使用游程长度编码( b = 3 ) 进行压缩后的压 缩率( 压缩率= ( t d t e ) z d ) 。根据表2 2 的统计来看，在数据中数据的平 均长度越长，压缩率就越高。因此游程长度编码r l c 比较适合于测试数据的编码， 例如传真图像的编码等。为了达到较好的压缩效果，有时游程长度编码和其它一 些编码方法混合使用。例如在j p e g 中，游程长度编码和离散余弦变换m ，。 表2 2 游程长度编码压缩率统计表 测试数据位长( b i t s )重复数据的平均长度压缩率 1 0 0 0 21 3 2 8 2 0 0 043 9 1 2 8 0 062 7 8 1 3 7 0 083 9 3 4 1 2 0 0 01 02 8 1 1 2 0 0 0 01 23 0 6 6 2 3f d r 编码算法 2 3 1f d r 编码算法的基本原理 为了克服游程编码算法的编码长度限制，出现了一种f d r 编码算法。这种编 码算法重新排列测试向量t 。并且相互异或生成差分序列t 。，。其中t 。，= ( d 。， d 2 d n = t 、，t to t 。，t 。o t 一t 。，。ot 。) 编码t ，获得测试集 t e 译码时使用一个循环扫描寄存器c s r ，再进行差分运算还原测试集t 。在编 码之前因为首先进行了异或运算，所以异或后得到的t 。，数据流中0 的个数相对 比较多，所以可以用数据流中的“0 ”的个数来代表整个数据流，而“1 ”被当作 游程个数为0 。其编码码字主要特征是：每个编码码字有一个前缀码，这个前缀不 仅具有区分码字的作用，而且还能够表示定长度信息，其尾部分配同一前缀相同 长度的二进制码。对应的编码表见表2 3 。这种编码根据连续序列的长度分配不 同长度的编码，没有固定编码长度的约束，因此，能够更有效地压缩测试数据。 华南理工大学硕士学位论文 2 3 2f d r 编码算法压缩模型 在f d r 算法进行数据压缩时，先对数据两两进行相与( 见表2 3 ) ，对于相 与后的数据，根据编码表进行编码。编码时根据0 游程的个数来确定整个数据。 每个1 数据用“0 0 ”来表示： 输入数据流：0 0 0 0 0 0i i ii i 10 0 0 0 01 110 0 0 0 0 0 0 0 0 011 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 4 5 b i t s ) 异或：0 0 0 0 0 01 1 11 10 0 0 0 0 01 10 0 0 0 0 0 0 0 0 0 010 0 0 0 0 0 0 0 0 0 0 0 0 编码后码字：11 0 0 0 00 0 0 0 0 0 0 0 0 011 0 0 0 00 0 0 011 0 1 0 10 0i1 0 1i 1 ( 4 0 b i t s ) 表2 3 相与真值表 t a b l e 2 - 3t h ev a l u eo fa n dg a t e abc 0o o 01 o 10o 11 l 从编码后码字可以看出，由于采用了表2 3 进行编码，因此对比游程编码来 说有效率的多。但是因为全部数据都是用“0 ”游程来表示，因此对于连续的“1 ” 数据来说，是非常不利的。假如有r 个连续“1 ”数据，那么编码后需要2 ( r 一1 ) 个b i t s 进行编码，等于增加了2 r 一2 一r = r 一2 个数据。因此，f d r 码比较适合连“1 ” 较少的情况下。 从表中可以看出它具有以下几个特点： ( 1 ) 码字的前部分和后部分的的编码位数相同。例如：对于a 。都是l 比特。 对于a 。都是2 比特。 ( 2 ) 对于群组a 。前部分编码位数等于i 。例如：对于群组a 。，前部分编码位 数等于2 。 ( 3 ) 对于群组a 。，它包括的游程l 辩月需满足下列关系2 1 3 l * # 2 - 3 。例 如对于群组a 。，它包括的游程需满足2 3 _ 3 lm 。2 3 _ 3 ，也即 6 ，7 ，8 ，9 ，1 0 ，l l ，1 2 ，1 3 。 ( 4 ) 假设p 代表码字前部，t 代表码字后部，( p ，t ) 代表整个码字，它和群组中 游程f 的关系是：r = n ( p ) + n ( t ) ，其中n ( p ) 代表码字前部转化为十进制的数据，n ( t ) 代表后部转化为十进制的数据。例如：对于a 。群组中的游程l o ，它可以表 示：1 0 = n ( 11 0 ) + n ( 1 0 0 ) + l = 6 + 4 。 ( 5 ) 对于群组a 。，码字前部分最后一位为0 ，其余都是1 ，这使硬件实现比较 简单。例如对于群组a 。，它的前部分为11 0 ，晟后一位为o ，其余都为l 。对于群组 第二章游程编码及f d r 编码算法在s o c 测