集成电路内建自测试所需测试向量的生成电路及方法

摘要

本发明涉及一种集成电路内建自测试所需测试向量的生成电路，包括地址计数器发送地址数据序列；序列计数器发送数据序列；种子及多项式系数存储单元与地址计数器连接，发送压缩的难测、易测向量的输出值；序列发生器分别与序列计数器和种子及多项式系数存储单元连接，输出2比特数据；权重产生逻辑单元用于输出4路数据值；四选一数据选择器分别连接权重产生逻辑单元、序列发生器输出一路数据；输入寄存器与四选一数据选择器连接，用于寄存数据并装载更新数据；扫描链分别与输入寄存器以及被测电路组合逻辑单元连接，输出更新变化的数据；被测电路与扫描链连接，用于检测被测电路故障。本发明还提供一种集成电路内建自测试所需测试向量生成方法。

说明书

技术领域

本发明涉及集成电路领域，尤其涉及集成电路内建自测试的确定性测 试向量压缩及解压缩技术，以及伪随机测试中的测试向量产生技术。

背景技术

集成电路要在它生命周期的几个不同时间进行测试和诊断。测试和诊 断必须速度快而且有很高的故障覆盖率。内建自测试技术(Build-In  Self-Test，BIST)通过在集成电路内部增加少量的逻辑电路实现对集成 电路的自测试，能降低测试成本和以电路频率进行测试，因此在工业界广 泛使用。日本专利No.2007-240390A中公开了一种内建自测试的示例。该 内建自测试电路通过线性反馈移位寄存器(LFSR)产生测试向量，通过多 输入特征分析器(MISR)对被测电路的测试响应进行压缩，通过内置的比 较器来判断最终的测试结果为“通过”或“不合格”。

图1为传统内建自测试的方框图。参照图1，内建自测试电路包括测 试激励，被测电路和测试响应。其中，测试激励由线性反馈移位寄存器10 和移相器20组成；被测电路由扫描链30和被测电路组合逻辑部分40组 成；测试响应由响应压缩器及与之相连的多输入特征分析器组成。该电路 的测试激励，通过线性反馈移位寄存器10伪随机产生，然后由移相器降 低产生的数据之间的相关性。

伪随机产生测试向量存在的问题是故障覆盖率不高，难以达到电路设 计指标要求的故障覆盖率。同时，用伪随机的方法产生测试向量，线性反 馈移位寄存器10在产生被测电路所需的测试向量的过程中，不可避免地 产生很多对被测电路无用的数据序列。产生大量这些无用的数据序列，占 用了大量的测试时间。

确定性BIST，通常先采用线性反馈移位寄存器10产生伪随机测试向 量，侦测大多数的易测故障。然后对剩下的少量难测故障，用自动测试向 量生成器(ATPG)产生确定性测试向量，并压缩存储在BIST电路的ROM中。 测试过程与设计过程互逆。首先，进行确定性测试向量测试。然后，用LFSR 伪随机产生测试向量对电路剩下的故障进行测试。确定性BIST测试的故 障覆盖率能够达到电路制造并投入市场的要求，但是在伪随机测试产生阶 段，存在测试时间长的问题。同时，由于确定性BIST测试针对每个难测 故障采用ATPG生成相应的难测向量，所以需要存储的难测向量所占用的 存储单元多，使得集成电路内建自测试电路的面积开销增大，集成电路量 产成本增大。集成电路规模越大，晶体管数目越多，表现在门级的固定故 障的数目就越多，相应的难测向量的数目也会随之增大。每个难测向量都 需预先存储在内建自测试电路的存储单元，但是集成电路中存储单元增长 的速度远远慢于晶体管增长的速度，于是迫切需要寻找减少存储单元使用 面积的方法。目前常采用压缩存储的方法以减少对存储单元的需求。

发明内容

(一)本发明要解决的问题：

为了解决现有技术无用的数据序列占用了大量的测试时间的问题，同 时为了解决现有技术中确定性测试向量占用了大量的存储单元的问题，本 发明的目的是提供一种集成电路内建自测试所需测试向量的生成方法及 电路。

(二)本发明的技术方案：

本发明的第一方面提供一种集成电路内建自测试所需测试向量的生 成电路，包括地址计数器、序列计数器、种子及多项式系数存储单元、序 列发生器、权重产生逻辑单元、四选一数据选择器、输入寄存器、扫描链， 其中：

地址计数器，用于发送地址数据序列；

序列计数器，用于发送数据序列；

种子及多项式系数存储单元与地址计数器连接，根据地址值发送预先 存储压缩的难测向量、易测向量的输出值；

序列发生器分别与序列计数器和种子及多项式系数存储单元连接，接 收难测向量和易测向量的输出值并在每个时钟周期生成输出2比特数据；

权重产生逻辑单元，用于在每个时钟周期同时输出4路数据值；

四选一数据选择器分别连接权重产生逻辑单元、序列发生器，利用2 比特数据来选择并输出4路数据值中的一路数据；

输入寄存器与四选一数据选择器连接，用于寄存0或1的数据组合， 并经过n个时钟周期装载更新数据，n的值的大小等于被测电路输入个数；

扫描链分别与输入寄存器以及被测电路组合逻辑单元连接，用于在每 个时钟周期以串行或并行的方式接收更新数据和组合逻辑响应数据并输 出更新变化的数据；

被测电路与扫描链连接，接收更新变化的数据值产生测试响应，当有 效的所有测试响应与预期设定的被测电路测试响应相符，则表明被测电路 没有故障。

本发明的第二方面提供一种集成电路内建自测试所需测试向量的生 成电路，包括序列发生器、权重产生逻辑单元、四选一数据选择器、输入 寄存器以及扫描链，其中：

序列发生器，用于发送多路2比特数据；

权重产生逻辑单元，用于在每个时钟周期同时输出4路数据值；

多个四选一数据选择器分别与序列发生器、权重产生逻辑单元连接， 利用2比特数据选择并输出4路数据值中的一路数据值；

输入寄存器与多个四选一数据选择器连接，用于寄存0或1数据，并 经过1个时钟周期后装载更新的数据；

多个扫描链分别与输入寄存器、被测电路组合逻辑单元连接，用于在 每个时钟周期以串行或并行的方式接收输入寄存器中的更新数据和组合 逻辑响应数据并输出更新变化的数据；

被测电路与扫描链连接，利用更新数据的变化得到测试响应，当有效 的所有测试响应与预期设定的被测电路测试响应相符，则表明被测电路无 故障。

本发明的第三方面提供一种集成电路内建自测试所需测试向量生成 方法，包括步骤如下：

步骤S1：开始预处理，由计算机对集成电路的难测向量和易测向量分 别经过分类加权、二维权重映射集变换为一维权重映射集、比特流压缩及 解线性方程组计算，得到被测电路原始测试向量的压缩数据；

步骤S2：将被测电路原始测试向量的压缩数据存储于种子及多项式系 数存储单元中；

步骤S3：序列发生器将被测电路原始测试向量的压缩数据经过线性反 馈移位，产生新的权重选择数据；在每个时钟周期后输出一组新的2比特 数据；

步骤S4：四选一数据选择器根据一组新的2比特数据控制值，选择并 输出权重产生逻辑4路中的一路输出值；

步骤S5：将权重产生逻辑4路中的一路输出值串行或并行地装载进输 入寄存器；在串行的装载方式下，经过n个时钟周期后，n比特的输入寄 存器中即有一组n比特的数据值，这n比特的数据值即是一个测试向量， 其中n的值的大小等于被测电路输入个数；在并行的装载方式下，经过一 个时钟周期后，n比特的输入寄存器中即有一组n比特的数据值，这n比 特的数据值即是一个测试向量；

步骤S6：被测电路的扫描链与每个测试向量交互，生成并输出实际的 测试响应；将被测电路实际的测试响应与被测电路预期的测试响应相比 较，如果比较结果相同则被测电路无故障，则转步骤S7，如果比较结果不 相同则被测电路有故障，则转步骤S9；

步骤S7：判断序列计数器中的计数值是否与序列计数器中预定的计数 值相同，若序列计数器中的计数值与序列计数器中预定的计数值不同，则 返回步骤S3继续执行；若序列计数器中的计数值与序列计数器中预定的 计数值相同，则将比特流压缩、解线性方程组的压缩数据的解压缩完毕， 转入步骤S8；

步骤S8：判断地址计数器中的计数值是否与地址计数器中预定的计数 值相同，若地址计数器中的计数值与地址计数器中预定的计数值不同，则 返回步骤S2继续执行；若地址计数器中的计数值与地址计数器中预定的 计数值相同，则将被测电路原始测试向量解压缩完毕，也即被测电路的所 有测试向量产生完毕；

步骤S9：结束。

(三)本发明的有益效果：

本发明能产生集成电路自测试时所需的易测向量和难测向量，其以更 短的测试时间、更省的存储空间，达到理想的故障覆盖率。本发明实施例 由于采用了分类加权的测试产生技术，产生易测向量的所有子类测试向量 的概率增大，产生有效的易测向量的概率增大，也即线性反馈移位寄存器 产生的无效的易测向量的个数减少，使得易测向量的测试时间缩短，降低 了时间成本。本发明实施例由于对难测向量采用分类加权、比特流压缩、 解线性方程组压缩，使得原来总共y比特的难测向量集，只需存储z比特 的数据到种子及多项式存储单元，即可由集成电路内建自测试测试向量生 成电路完全解压出来。z的值大小远远小于y。需要存储在内建自测试电 路ROM中的存储单元减少，节省了内建自测试电路的硬件开销，降低了集 成电路制造的成本。

附图说明

图1为现有技术中集成电路内建自测试的测试电路结构图；

图2为本发明的集成电路内建自测试所需测试向量生成电路的结构示 意图；

图3为本发明另一种集成电路内建自测试所需测试向量生成电路的结 构示意图；

图4为本发明实施例中序列发生器的电路示意图；

图5为本发明实施例中加权逻辑的电路示意图；

图6集成电路内建自测试所需测试向量的生成方法的流程图；

图7为本发明实施例中比特流压缩解线性方程组的流程图；

图8为图7中分类加权算法的流程图；

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实 施例，并参照附图，对本发明进一步详细说明。

如图2示出本发明第一种集成电路内建自测试所需测试向量的生成电 路100的结构框图,参照图2示出本发明所述的装置的实施例是采用混合 模式内建自测试测试向量产生电路100的方框图，所述混合模式是既有随 机测试产生，也有确定性测试产生，也即本发明的2个测试阶段。参照图 2，内建自测试测试向量产生电路100包括地址计数器110、序列计数器 120、种子及多项式系数存储单元130、序列发生器140、权重产生逻辑单 元150、四选一数据选择器160、输入寄存器170、扫描链180。

地址计数器110，用于发送地址数据序列；

序列计数器120，用于发送数据序列号；

种子及多项式系数存储单元130与地址计数器110连接，根据地址值 发送预先存储压缩的难测向量、预先存储的被测电路的易测向量的输出 值；

序列发生器140分别与序列计数器120和种子及多项式系数存储单元 130连接，接收难测向量和易测向量的输出值并在每个时钟周期生成输出 2比特数据；

权重产生逻辑单元150，用于在每个时钟周期同时输出4路数据值； 这4路都是0、1数据，这4路数据值可能的组合为{0001,0011,0101,0111}；

四选一数据选择器160分别连接权重产生逻辑单元150、序列发生器 140，利用2比特数据来选择并输出4路数据值中的一路数据；

输入寄存器170与四选一数据选择器160连接，用于寄存0或1数据， 并经过n个时钟周期装载更新数据，n的值的大小等于被测电路输入个数；

扫描链180分别与输入寄存器170以及被测电路组合逻辑单元190连 接，用于在每个时钟周期以串行或并行的方式接收更新数据和组合逻辑响 应数据并输出更新变化的数据；

被测电路190与扫描链180连接，接收更新变化的数据值产生测试响 应，当有效的所有测试响应与预期设定的存储在被测电路ROM中的测试响 应相符，则表明被测电路无故障；当存在有效的测试响应与预期设定的测 试响应不相符，则表明被测电路有故障。

序列发生器140包括两个移位寄存器组，始终由两个移位寄存器组各 自的最后一个寄存器产生输出四选一数据选择器的2比特控制位。

序列发生器140的一个具体实施电路图如图4所示。主要由异或门、 反馈连接和寄存器组成。

内建自测试测试向量产生电路100通过扫描链180对被测电路190的 组合逻辑进行测试时，分成两个阶段进行。第一阶段，进行确定性测试。 预先在工作站或个人电脑中，用自动测试向量产生器(ATPG)产生被测电 路的难测向量。通过对难测向量进行分类加权、比特流压缩以及解线性方 程组，得到压缩后的难测向量集合。将这些经过压缩的难测向量预先存储 在种子及多项式系数存储单元130中。测试时，地址计数器110取出种子 及多项式系数存储单元130中的数据序列，并行装载到序列发生器140中。 序列发生器140在每个时钟周期同时输出2比特数据到四选一数据选择器 160。权重产生逻辑单元150在每个时钟周期同时输出4路值。四选一数 据选择器160根据序列发生器140输出的2比特数据来选择输出权重产生 逻辑4路输出值中的一路。经过n个时钟周期，四选一数据选择器160的 输出将输入寄存器170装载了新的值，时钟周期数等于被测电路输入个数。 扫描链180在每个时钟周期可以串行或并行地接收来自输入寄存器170的 输出值。扫描链180中的值在变化，被测电路190会有测试响应。若有效 的所有测试响应与预期的测试响应相符，则表明ATPG所产生被测电路的 难测向量所能测试的故障没有发生。

难测向量所能测试的故障没有发生，则可以继续进行第二阶段的伪随 机加权测试。若难测向量所能测试的故障被检测出来，则表明电路有故障， 不能进入市场。预先在工作站或个人电脑中，用ATPG伪随机产生被测电 路的测试向量。这些测试向量即被测电路的易测向量。通过对易测向量进 行合理分类，得到预先存储在种子及多项式系数存储单元130中的数据集 合。测试时，地址计数器110取出种子及多项式系数存储单元130中的数 据序列，并行装载到序列发生器140中。序列发生器140在每个时钟周期 同时输出2比特数据到四选一数据选择器160。权重产生逻辑单元150在 每个时钟周期同时输出4路值。四选一数据选择器160根据序列发生器140 输出的2比特数据来选择输出权重产生逻辑4路输出值中的一路。经过n 个时钟周期，四选一数据选择器160的输出将输入寄存器170装载了新的 值，时钟周期数等于被测电路输入个数。扫描链180在每个时钟周期可以 串行或并行地接收来自输入寄存器170的输出值。扫描链180中的值在变 化，被测电路190会有测试响应。若有效的所有测试响应与预期的测试响 应相符，则表明ATPG所产生被测电路的有效易测向量所能测试的故障没 有发生。

在测试的第一阶段即难测向量测试阶段，经过权重产生逻辑单元150 的加权，四选一数据选择器160会输出一些原本预定在第二阶段即易测向 量测试阶段产生的有效易测向量。所以第二阶段，这些已经产生过的有效 易测向量，不用再输入给被测电路190进行测试。实际上，在电脑上通过 编写程序对测试数据进行压缩预处理时，会进行相应的处理，也即对易测 测试向量进行压缩时，摘除掉这些已经产生过的有效易测向量。

在测试的第二阶段，若给测试向量分的类别数过多，则需要的测试时 间会很短，但需要的种子及多项式系数存储单元130占用过多的集成电路 面积开销。因此，需要根据具体的电路，在缩短测试时间和减小集成电路 面积开销这两个需要优化的目标之间进行折中处理。所述折中处理是给出 一个评价函数h(m)＝a*T(m)+b*area(m)。其中，m为分类后的类别数。a 和b为影响因子，计算时针对具体的被测电路以及能接受的测试时间范围 给出估算值，T(m)为测试时间，area(m)为针对被测电路自测试而增加的 面积开销。T(m)时间越长，测试成本越高，集成电路投入市场日期也会越 晚。area(m)越大，集成电路量产成本越高。a和b的值的和等于1，且a ∈[0,1],b∈[0,1]。m的值增大时，T(m)的值会减小，但是area(m)的值 会增大。所以折中处理的做法就是调整m的大小，找出一个min(h(m))， 使得h(m)的值最小。

图3为本发明提供的第二种集成电路内建自测试所需测试向量生成电 路200，本发明示范的实施例采用混合模式内建自测试电路200的方框图。 其与内建自测试电路100的区别是，采用并行的方式装置扫描链，进一步 缩短测试时间。但是进一步增加了集成电路面积开销。因此，也需要根据 具体的电路和要求，在缩短测试时间和减小集成电路面积开销这两个目标 之间，选择合适的策略。

第二种内建自测试测试向量产生装置200包括序列发生器210、权重 产生逻辑单元230、四选一数据选择器220、输入寄存器240以及扫描链 250，其中：

序列发生器210，用于发送多路2比特数据；其由移位寄存器组211 和212组成。移位寄存器组211的最后一个寄存器的输出与移位寄存器组 212的第一个寄存器的输入相连；

权重产生逻辑单元230，用于在每个时钟周期同时输出4路数据值；

多个四选一数据选择器220分别与序列发生器210、权重产生逻辑单 元230连接，利用2比特数据选择并输出4路数据值中的一路数据值；

输入寄存器240与多个四选一数据选择器220连接，用于寄存0或1 数据，并经过1个时钟周期后装载更新的数据；

多个扫描链250分别与输入寄存器240、被测电路组合逻辑单元260 连接，用于在每个时钟周期以串行或并行的方式接收输入寄存器240中的 更新数据和组合逻辑响应数据并输出更新变化的数据；

被测电路260与扫描链250连接，利用更新数据的变化得到测试响应， 当有效的所有测试响应与预期设定的存储在被测电路ROM中的测试响应相 符，则表明被测电路无故障；当存在有效的测试响应与预期设定的测试响 应不相符，则表明被测电路有故障。其中:

序列发生器210包括移位寄存器组211和移位寄存器组212，其中：

由移位寄存器组211和移位寄存器组212的最后一个寄存器产生输出 第一个四选一数据选择器220的2比特控制位；

由移位寄存器组211和移位寄存器组212的右起第二个寄存器产生输 出第二个四选一数据选择器220的2比特控制位；

由移位寄存器组211和移位寄存器组212的左起第一个寄存器产生输 出左起第一个四选一数据选择器220的2比特控制位。

序列发生器210中的寄存器个数是被测电路260的电路输入个数的2 倍。四选一数据选择器220的个数是序列发生器210中的寄存器个数的一 半。权重产生逻辑单元230输出4路数据，这4路数据具有如下特性：在 大样本统计的情况下，为1的概率分别为：0、1、0.25、0.75。这4路数 据同时输出给所有的四选一数据选择器220。内建自测试电路200中的右 边第一个四选一数据选择器220的2比特控制位分别由序列发生器210中 的移位寄存器组211和移位寄存器组212的最后一个寄存器输出产生。内 建自测试电路200中的右起第二个四选一数据选择器220的2比特控制位 分别由序列发生器210中的移位寄存器组211和移位寄存器组212的右起 第二个寄存器输出产生。依次类推，内建自测试电路200中的左起第一个 四选一数据选择器220的2比特控制位分别由序列发生器210中的移位寄 存器组211和移位寄存器组212的左起第一个寄存器输出产生。

四选一数据选择器220根据序列发生器210输出的2比特数据来选择 输出权重产生逻辑4个输出值中的一个。经过1个时钟周期，四选一数据 选择器220的输出将输入寄存器240装载了新的值。扫描链250在每个时 钟周期可以串行或并行地接收来自输入寄存器240的输出值。扫描链250 中的值在变化，被测电路260会有测试响应。若有效的所有测试响应与预 期的测试响应相符，则表明ATPG所产生被测电路的测试向量所能测试的 故障没有发生。若故障覆盖率达到要求，则认为电路通过了测试。

图4为图2中的序列发生器140和图3中的序列发生器210的内部结 构的示意图。序列发生器140包括：异或门141、反馈连接142以及寄存 器143。其中：异或门141与反馈连接142以及寄存器143相连，接收来 自寄存器143的输出值，异或门141经过异或后，将异或得到的值输出给 寄存器143。

序列发生器140由2倍电路输入个数的寄存器143组成，图4中以每 组4个寄存器作为示意，共2组寄存器组。2组寄存器共同组成线性反馈 移位寄存器。线性反馈移位寄存器，也即序列发生器140，由异或门141、 反馈连接142以及寄存器143组成。对于k位的序列发生器140生成的数 据序列X_k，X_k＝c₀x₀+c₁x₁+……c_Kx_K；c_K为序列发生器的反馈连接，x_K为寄存 器中的值,实施时选择k＝8位的序列发生器140，其所生成的数据序列X₈可用多项式来表示：

X₈＝c₀x₀+c₁x₁+c₂x₂+c₃x₃+c₄x₄+c₅x₅+c₆x₆+c₇x₇+c₈x₈，

其中，j属于0-k中的任一值，c_j表示反馈系数有无构成反馈连接142， c_j＝0表示不存在反馈接入，c_j＝1表示有反馈存在。其中，图4中的反馈连 接142只是示意图，不是电路中的真实器件；真实的反馈连接142可由晶 体管或者与非门或者寄存器实现。

设序列发生器140中寄存器的初始值为“11010010”，反馈系数 C＝{c₀,c₁,c₂,c₃,c₄,c₅,c₆,c₇,c₈}＝{1,0,0,0,0,1,0,0,1}；则，根据数据序列 的多项式可知，下一个时钟周期的上升沿到来时，序列发生器140中各个 寄存器输出的值为“01101001”，再下一个时钟周期的上升沿到来时，序 列发生器140中各个寄存器输出的值为“10110100”，接着几个时钟周期 的上升沿到来时，序列发生器140中各个寄存器输出的值为“11011010”， “01101101”，“00110110”，“10011011”，依此类推。

根据上面的例子，序列发生器140中输出到内建自测试电路100中四 选一数据选择器160的2比特数据依次为：(0,1)，(1,0)，(1,0)， (0,1)，(1,0)，(1,1)，后面的数根据此规则类推，每对数都是在 不同的时钟周期产生的。序列发生器210中输出到内建自测试电路200中 四选一数据选择器220的2比特数据依次为：(0,1)，(1,0)，(1,0)， (0,1)，(1,0)，(1,1)。后面的数根据此规则类推，每对数都是在 同一个时钟周期内产生的。

图5为内建自测试电路100中权重产生逻辑150的一个实施例，包括： 异或门154、寄存器组153、与门152、以及或门151，其中：异或门154 的2个输入端与寄存器组153的输出端相连，异或门154的输出端与寄存 器组153的输入端相连；寄存器组153中的寄存器依次首尾相连：前一个 寄存器的输出端连接后一个寄存器的输入端。与门152接收2个寄存器的 输出，并将相与的结果输出给或门151。或门151和与门152以及寄存器 组153中的一个寄存器相连，输出值作为权重产生逻辑的一路输出值，且 这一路输出值对应的权重值为0.75。

5个寄存器153与异或门154组成以本原多项式形式进行反馈连接的 线性反馈移位寄存器。根据本原多项式的性质可知，其中每个寄存器在经 过一定数量的时钟周期后，所产生的0和1的个数，经过统计，近似各 占0和1的个数总和的一半，也即0和1近似随机产生。所以与门152相 连的2个寄存器的输出为1的概率都是50％，经过与门152相与后，与门 152输出为1的概率为0.25，与门152输出为0的概率为0.75。同理，或 门151的输出为1的概率是50％+25％＝0.75；或门151的输出为0的概率是 1-0.75＝0.25。

权重产生逻辑150产生的4路输出分别具有权重，依次为0、0.25、 0.75以及1，表示的是每路输出为1的概率。内建自测试电路200中权重 产生逻辑230输出的值也依次具有权重:0、0.25、0.75以及1。实际电路 中必须避免0.25和0.75这两个权重对应的输出值具有相关性。实际电路 中0权重的产生，可以通过将线直接连到地(GND)来实现；1权重的产生， 可以通过将线直接连到电(VCC)来实现。

如图6集成电路内建自测试所需测试向量的生成方法的流程图，所需 测试向量生成步骤包括如下：

步骤S1：开始预处理，由计算机对集成电路的难测向量和易测向量分 别经过分类加权、二维权重映射集变换为一维权重映射集、比特流压缩及 解线性方程组计算，得到被测电路原始测试向量的压缩数据；

步骤S2：将被测电路原始测试向量的压缩数据存储于种子及多项式系 数存储单元中；

从种子及多项式系数存储单元取出数据输出到序列发生器；种子及多 项式系数存储单元中存储的数据是：集成电路的难测向量和易测向量分别 经过分类加权、二维权重映射集变换为一维权重映射集、比特流压缩、解 线性方程组计算后，生成被测电路原始测试向量的压缩数据；其中，难测 向量和易测向量的分类加权算法流程相同，但算法中的评价函数不同；难 测向量的分类加权算法的评价函数f₁＝min(R(C₁，C₂，……，C_m))。其 中,C_i表示难测向量分类后的第i类向量集。R(C₁，C₂，……，C_m)＝m， 表示难测向量分类后的类别数。m<＝难测向量的个数，i是向量集的序号， i＝1,2,3,…m。；易测向量的分类加权算法的评价函数f₂＝min(t(C₁， C₂，……，C_m))。其中,C_i表示易测向量分类后的第i类向量集。t(C₁， C₂，……，C_m)＝t₁+t₂+……t_m，表示产生所有易测向量所需的总的时钟周期 数。m表示易测向量分类后的类别数,t_i表示产生第i类内的所有易测向量 所需的总的时钟周期数。

在PC机上编写C语言程序，实现分类加权、二维权重映射集变换为 一维权重映射集、比特流压缩、解线性方程组这4步计算，该系列程序的 初始输入是被测电路的难测向量和易测向量。该系列程序的最终输出是该 被测电路的难测向量和易测向量的压缩数据。该压缩数据存在种子及多项 式系数存储单元。对所述一维权重映射集结合比特流压缩、解线性方程组 压缩这两种技术进一步压缩，使得种子及多项式系数存储单元中少量的数 据，经过序列发生器就能产生大量需要的权重映射集。

步骤S3：序列发生器将被测电路原始测试向量的压缩数据经过线性反 馈移位，产生新的权重选择数据；在每个时钟周期后输出一组新的2比特 数据；

步骤S4：四选一数据选择器根据一组新的2比特数据控制值，选择并 输出权重产生逻辑4路中的一路输出值。

步骤S5：将权重产生逻辑4路中的一路输出值串行或并行地装载进输 入寄存器；

在串行的装载方式下，经过n个时钟周期后，n比特的输入寄存器中 即有一组n比特的数据值，这n比特的数据值即是一个测试向量，其中n 的值的大小等于被测电路输入个数；在并行的装载方式下，经过一个时钟 周期后，n比特的输入寄存器中即有一组n比特的数据值，这n比特的数 据值即是一个测试向量。

步骤S6：测试向量输出到被测电路的扫描链中；被测电路的扫描链将 与测试向量进行交互，生成并输出实际的测试响应，将被测电路实际的测 试响应与被测电路预期的测试响应相比较，如果比较结果相同则被测电路 无故障，则转步骤S7，如果比较结果不相同则被测电路有故障，则转步骤 S9；

步骤S7：判断序列计数器中的计数值是否与序列计数器中预定的计数 值相同，若序列计数器中的计数值与序列计数器中预定的计数值不同，则 返回步骤S3继续执行；若序列计数器中的计数值与序列计数器中预定的 计数值相同，则将比特流压缩、解线性方程组压缩向量对应的解压缩完毕， 转入步骤S8；

步骤S8：判断地址计数器中的计数值是否与地址计数器中预定的计数 值相同，若地址计数器中的计数值与地址计数器中预定的计数值不同，则 返回步骤S2继续执行。若地址计数器中的计数值与地址计数器中预定的 计数值相同，则将被测电路原始测试向量解压缩完毕，也即被测电路的所 有测试向量产生完毕；

步骤S9：结束。

采用分类加权算法是使用很少的种子向量，经过序列发生器、权重产 生逻辑单元和四选一数据选择器的加权后，产生出测试向量。

比特流压缩后解方程组的算法流程图2000如图7所示。参照图7，先 将二维权重映射集变换成一维权重映射集(步骤2100)，以便于进行比特流 压缩以及后续的解线性方程组压缩。上例中的2个权重映射集W1、W2可 以表示如下：

W1＝{10111110111111111100000000000000011, 10000001111111111100000000000001100}；

W2＝{11001101101000000000000100011100111, 11011101101000000000000000000000000}.

对上述两个一维权重映射集进行比特流压缩(步骤2200)，压缩后的比 特流为：

{10111110111111111100000000000000011100000011111111111000000000 000011001101101000000000000100011100111110111011010000000000000 00000000000}将压缩后的比特流转化成方程组(步骤2300)，计算出方程 组的解X为(步骤2400)：

X＝{0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1}；

比特流压缩转化成方程组的举例如下：

假设有比特流压缩10010101111，电路输入个数为5，则转化为的方 程组为：

$\left(\begin{array}{c}01111\\ 10111\\ 01011\\ 10101\\ 01010\\ 00101\end{array}\right)\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\\ c_4\\ c_5\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\\ 0\\ 1\end{array}\right)$

该方程组的解：c₁-c₅为序列发生器的反馈连接,X＝{1 0 0 0 1}. 方程组的解即为多项式的系数，对应着序列发生器140的反馈连接。

判断剩下无解的方程个数是否为0(步骤2500)，若剩下无解的方程个 数为0，则算法结束，将第一个权重映射集做为种子存入种子及多项式存 储单元130，同时将多项式的系数也存入种子及多项式存储单元130。如 果存在无解的方程，则转入步骤2300，若剩下无解的方程个数不为0，对 剩下无解的方程组再次解方程(步骤2600)。本例中只需一个种子，即可应 用内建自测试电路100产生出表1中s420的所有测试向量。

表1自动测试向量产生器产生的s420电路的难测向量，如下示出：

1xxxx10xxxxxxxxxxx0000000001000xxx1

1xxxx1xxxxxxxxxxxx0000000000000xxx1

1xxx10xxxxxxxxxxxx0000000000000xx11

1xxx1xxxxxxxxxxxxx0000000000000xx10

1xx10xxxxxxxxxxxxx0000000000000x110

1xx1xxxxxxxxxxxxxx0000000000000x100

1x000001xxxxxxxxxx000000000x000xxxx

1x01xxxxxxxxxxxxxx0000000000000x000

1xx0xxxxxxxxxxxxxx0000000000000x100

1x1xxxxxxxxxxxxxxx00000000000000000

1x0xxxxxxxxxxxxxxx00000000000001000

1x0001xxxxxxxxxxxx0000000000000xxx0

1x00001xxxxxxxxxxx0000000000000xxxx

1x0000001xxxxxxxxx000000000xx00xxxx

1x001xxxxxxxxxxxxx0000000000000xx00

1xxxxxxxxx1xxxxxxx000001000xxxxxxxx

1xxxxxx1xxxxxxxxxx000000000x100xxxx

1x10xxxxxxxxxxxxxx00000000000001100

1x1xxxxxxxxxxxxxxx00000000000001000

1xxxxxxx1xxxxxxxxx000000000xx10xxxx

内建自测试电路100和内建自测试电路200具有优越性的共同核心在 于2个分类加权算法对其的支撑。对被测电路的测试向量采用分类加权算 法进行压缩中的难测向量和易测向量的分类加权算法流程相同，难测向量 分类加权算法应用在测试的第一阶段，其优化目标是：使测试向量分类后 的类别数尽可能地少，以使种子及多项式系数存储单元占用尽可能地少。 该分类加权算法的流程图如图8所示步骤包括；

步骤1100:先在PC机上用ATPG软件产生被测电路的易测测试向量和 难测测试向量。其中ISCAS-89基准电路中的s420电路的难测向量如表1 所示，共有20个难测向量，每个向量为35比特，因为s420电路的输入 个数为35个。

步骤1200:统计难测向量中0和1的个数，如果表1中数据集的某一 列中全是1，也即0的个数为0，则这一列的对应的权重值映射为11；如 果数据集的某一列中全是0，则这一列的对应的权重值映射为00；某一列 中1的个数大于0的个数，则这一列的对应的权重值映射为10；0的个数 大于1的个数，则权重值映射为01；若0的个数等于1的个数，则权重值 映射为01或10；无关位“X”不参与0和1的计数，当一列中0的个数和 1的个数都为0时，权重值映射为00(也可以映射为11)。

步骤1300:得到表1中所示数据集的第一个权重映射集w： {11,00,01,01,01,01,01,10,11,00,10,00,00,00,00,00,00,00,00,00,0 0,00,00,01,00,00,00,00,01,01,00,10,10，01,01}；

其中有10个元素{01}映射权重0.25，4个元素{10}映射权重0.75。 元素{00}映射权重0，元素{11}映射权重1。

在上例所示的权重映射集w下，产生表1中第一个向量的概率为 0.25*0.75*0.25*0.25*0.25＝0.0029296875。1/0.0029296875约等于341， 于是大约经过341*35个时钟周期，内建自测试电路100的输入寄存器170 中会出现一次第一个向量的值：1xxxx10xxxxxxxxxxx0000000001000xxx1。 表1中所有向量集可由一个权重映射集w来产生。假如有一个向量为 10111110100000000000000100001100011，则上述权重映射集w产生该向 量大概需要1/(0.25)14个时钟周期，显然，在设定的测试周期内，该 向量很可能无法产生。

步骤1400：将权重映射集w装载入序列发生器140中，经过设定的时 钟周期后，输入寄存器170中会得到s420的难测向量。

步骤1500：判断s420的所有难测向量是否都已经由内建自测试电路 100或200产生过，若所有难测向量都由内建自测试电路产生过，则寻找 权重映射集的算法结束，说明这一个权重映射集w即可产生出s420的所 有难测向量，将其设置为序列发生器的初值，即可省去内建自测试电路100 或200的种子及多项式系数存储单元130，节省硬件开销；若所有难测向 量都没由内建自测试电路产生过，则将权重映射集存入种子及多项式系数 存储单元130中；

步骤1600：剩下未匹配的难测向量集组成新的数据集，并转入步骤 1200继续。最终的权重映射集w的个数即为难测向量所分的类别数目。

对于小的电路，也即电路输入个数少的电路，如s420，一般一个权重 映射集w即可产生所有难测向量。但是对于大电路，电路输入个数多的电 路，经过设定的时钟周期后，输入寄存器170中不会得到所有的难测向量。 因为设定值通常不可能设得太大，比如不会超过10万个时钟周期，否则 时间开销无法在现实测试中接受。假设某电路的难测向量如下：

其中，有100列，且每列中1的个数都多于0的个数，则产生(0000… 0000)这个难测向量的概率为1/(4100)，显然10万个时钟周期是远远不 够的。因此给(0000…0000)这个难测向量单独分为一类并计算相应的 权重映射集。

该分类算法思想的核心是：在测试时钟周期数可接受的条件下，将数 据集分为N类，并尽量使N比较小。所分得的每一类中的所有测试向量， 可由权重映射集，权重产生逻辑150或230和四选一数据选择器160或220 完全产生。

难测向量分类属性的确定依赖于对测试时间和占用种子及多项式系 数存储单元130的综合评价。类别确定好后，相应的权重映射集便能很容 易计算出。计算出的权重映射集中的每个元素都是2比特的，其在序列发 生器140或210中的装载过程如下：

假设电路的输入个数为4，且其权重映射集w＝{10,10,10,10}；则将 其转换成2个新的权重映射集w1＝{1,1,1,1}，w2＝{0,0,0,0}。对应于内 建自测试电路100，将新的权重映射集w1的值装入序列发生器140的前 半部分寄存器中，将新的权重映射集w2的值装入序列发生器140的后半 部分寄存器中。这样，在每个时钟周期，四选一数据选择器160的2比特 控制值都是{10}。对应于内建自测试电路200，将新的权重映射集w1的 值装入序列发生器210的前半部分寄存器211中，将新的权重映射集w2的 值装入序列发生器210的后半部分寄存器212中。这样，在每个时钟周期， 四选一数据选择器220的2比特控制值从左到右依次是{10}、{10}、{10}、 {10}。

易测向量分类加权算法应用在测试的第二阶段，其优化目标是：使测 试向量分类后，权重产生逻辑尽可能地以最短的时钟周期产生这些测试向 量，以使测试时间尽可能地缩短。该算法的流程图与图6类似，只需将其 中的难测向量换成易测向量，且应用第二阶段的优化目标即可。

为了与难测向量分类加权算法做对比，现假设表1中的难测向量为易 测向量，对该易测向量向量集进行分类加权。如果将向量集分成多类，则 每类中需要以0.25或0.75的概率产生数据的列数减少，也即产生该类内 所有向量的概率会增大，需要的时钟周期数就会减少。假设分为2类后， 对该集成电路的测试时间成本能接受。经过统计可知，表1中的向量集有 14列不能由权重产生逻辑150以100％的概率产生数值。因为目标是分为2 类，于是寻找符合要求的2个权重映射集，使其能在内建自测试电路100 或200中产生所有的向量集。现找到2个权重映射集W1、W2如下：

W1＝{11，00，10，10，10，10，10，01，11，11，11，11，11，11， 11，11，11，11，00，00，00，00，00，00，00，00，00，00，00，00， 00，01，01，10，10}；

W2＝{11，11，00，01，11，11，00，11，11，00，11，00，00， 00，00，00，00，00，00，00，00，00，00，10，00，00，00，10，10， 10，00，00，10，10，10}.

在上例所示的权重映射集W2下，产生表1中第一个向量的概率为 0.25*0.75*0.25*0.25*0.75＝0.0087890625。1/0.0087890625约等于114， 于是大约经过114*35个时钟周期，内建自测试电路100的输入寄存器170 中会出现一次第一个向量的值：1xxxx10xxxxxxxxxxx0000000001000xxx1。 从这里不难推测出，分类后总的测试时间将会有显著地减少。

将向量集分成多类，不可避免地带来种子及多项式系数存储单元130 面积开销增多的问题。为了减少面积开销，序列发生器中反馈系数必须与 比特流压缩后解方程组求得的系数相同。

一般的电路经过比特流压缩后，求解出的方程组需要多个不同的方程 组系数。如果方程组系数的个数过多，则种子及多项式存储单元130的面 积开销会增大。对于面积成本过高的电路，则内建自测试电路100或200 中可以不采用比特流压缩的方法，只应用分类加权的方法，种子及多项式 存储单元130中只存储权重映射集。

本领域普通技术人员可以理解实现上述实施例中的分类加权、比特流 压缩、解线性方程组方法是可以通过不同的次序进行结合的。根据电路的 具体情况，选择这三种压缩方法中的二种或三种进行组合压缩，能节省硬 件开销。

以上所述仅是本发明的优选实施方式，应当指出，本领域的技术人员 可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样， 倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围 之内，则本发明也意图包含这些改动和变型在内。