专利名称：一种利用高码率卷积码实现的压缩电路和方法
技术领域：
本发明涉及卷积码设计和集成电路芯片的可测性技术领域，特别是涉及应用一种高码率的卷积码的单输出测试响应压缩电路和方法。
背景技术：
随着工艺的发展，特别伴随着系统级芯片的发展，单个芯片上集成的逻辑单元(比如微处理器，存储器，DSPs，I/O控制器)越来越多，其功能也越来复杂，给测试带来了很多新的挑战。这些挑战主要包含1)测试设备的测试频率跟不上芯片频率的提高；2)测试时间过长，导致测试成本大幅增加；3)测试设备内存容量不足；4)芯片可用作全扫描设计的测试引脚不足。一个可行的解决测试引脚不足的方案是对测试响应进行压缩，一般是通过采用一个芯片内置的测试响应压缩电路对完成这种响应压缩。
测试响应压缩的主要思想是首先设计一个内置的响应压缩器，该压缩器能够尽可能将测试响应输出压缩到一个或几个输出，这些输出通过引脚输出到测试设备。对于一般的可测性设计，可用作扫描输入和输出的引脚是限定的。这些限定可能是来自于版图设计的需要，也有可能是兼顾测试设备实际测试资源情况。这样，如果输出被压缩变少后，就可以有更多的引脚用于设计更多的测试扫描链，从而缩短了最长扫描链的长度，减少了用于扫描进/扫描出向量的时间。而扫描测试中，主要的时间耗费就是在移动扫描向量上，因此通过测试响应压缩我们可以大大减少扫描测试时间。同时，由于增加了扫描链，单个扫描链上的数据量就会相应减少，因此，测试响应压缩还减少了每个测试通道需要的测试容量。
测试响应输出有几个特征，这些特征是我们设计不同压缩电路需要考虑的问题1)单位时间内，发生故障的数目比较少，一般不会超过4个。2)响应中可能包含很多不确定位。不确定位是指其值在仿真的时候是不能确定的。这些不确定位的来源包含没有传始化的寄存器，总线竞争，时序环路等。3)所设计的压缩电路必须能提供一个简单的能够收集完全诊断信息的方法，而且这种诊断必须是没有假设条件的。适合于解决以上三个问题的压缩电路方案可以分为两大类组合压缩电路和时序压缩电路。组合压缩电路是指通过简单的组合电路来实现压缩电路。这种压缩电路设计方法比较简单，一种最简单的实现就是利用异或树，其理论基础是奇偶校验。通过合理的设计异或树的结构和规划压缩输出的个数，可以有针对性的解决上述三个问题。组合压缩电路的一个不足之处在于压缩率比较低，而且不能提供一个完全的诊断方案，其诊断必须是基于一些假设，而这些假设在实际测试环境中是无法保证的。时序压缩电路是通过移位寄存器链来实现压缩。这种压缩电路压缩比相对较高，且混淆率也比较低。但是，最直接的时序电路压缩比如MISR，在响应压缩的时候，不能有效的处理不确定位。其通常的方法是通过合理的可测性设计去消除这些不确定状态。而不确定位在大规模的SOC设计中又是不可能被完全消除的，因此要想使得时序压缩电路在SOC的测试响应压缩中依然有效，就必须对其加以变革。创造出新的针对上述三个特征的时序压缩电路。
上段中提到的组合压缩电路，一般都是基于某种线性编码的，这方面的相关技术可以参照下列文章“Testing computer hardware through data compression in space and time”，Published by K.K.Saluja and M.Karpovsky，in Proceeding of InternationalTest Conference，pp.83-88，1983。
在这篇文章中，介绍了一种利用线性分组码的压缩电路设计技术。在这篇文章中还同时提供了这种压缩电路一种利用异或门实现的方法。
卷积码是一种被广泛应用于通信系统、无线、卫星系统、移动通信中的一种先进的编码。卷积编码和分组编码不相同。分组码编码时，本组中的校验元仅与本组在该节拍上的输入有关系，而与其他各节拍的输入码元没有关系。在分组码译码时，也仅从本码组中的码元内提取有关译码信息，而与其他各组无关。而卷积码，本组中的校验元还和前段组上的输入有关系。在卷积码译码时，不仅需要从本节拍输入中提取信息，还需要从前段节拍中提取译码信息。卷积码的详细介绍可以参考下列文献“Coding for Noisy Channels”，Published by P.Elias，in IRE InternationalConvention Record，pt.4，pp.37-46，1955。线性分组码能够应用于测试响应压缩电路的构造，同样，卷积码也适用于构造这种压缩电路。但是，由于响应压缩电路属于一种特殊的应用，它不是直接编码的编码器，而是利用编码的校验矩阵来综合实现编码器。也就是说，测试响应压缩电路实际上是校验矩阵的实现。
为了简单的生成所需的卷积码及兼顾到实际的测试响应压缩的需要，本发明将提出一种高码率，距离为3的卷积码的设计规则。这些设计规则可通过一个基于随机选取的方法自动实现。在该编码的基础上，应用映射规则就可以得到需要的测试响应压缩电路。

发明内容
本发明的目的在于提供一种高码率的卷积码，然后提供一种基于该编码基本校验矩阵的测试响应压缩电路。
本发明针对测试响应中错误位比价少的情况，提出了一种高码率、距离为3的卷积码的设计规则，根据该卷积码基本校验矩阵实现的压缩电路可以提供避免1，2，3和任意奇数个错误位引起混淆的能力。该压缩电路具有设计简单、设计过程可以完全自动化、不需要修改待测电路扫描链结构等特点，使得本发明提出的方法特别适合于当前SOC可测性设计中。
本发明目的之一是提供一种高码率、距离为3的卷积码设计规则。所提设计规则针对卷积码的基本校验矩阵，通过对基本校验矩阵进行规则约束，使得所设计的卷积码距离为3。
本发明目的之二是提供一种利用发明目的一提出的卷积码基本校验矩阵实现的压缩电路，由于发明目的一提出的卷积码能够提供距离为3，所以利用该编码基本校验矩阵实现的压缩电路可以避免1、2、3和任意奇数个错误位引起混淆的情况。
发明技术方案本发明首先提出了一个高码率的卷积码。该卷积码的特征是它的距离是3。卷积码可以用一个四元组表示(n，k，m，d)，其中n是并行输出的数目，k是并行输入的数目，m是编码约束长度，d是卷积码码字的最小距离。卷积码的校验矩阵H定义为G∞·H∞T=0.]]>其中，G∞是卷积码生成矩阵。如果使用m-截断矩阵来表征卷积码，那么响应的截断校验矩阵可定义为Gm·HmT=0,]]>在这里，HTm是一个(m×(n-k)，m×n)矩阵。在Hm中，每一个矩阵元素hi是一个(n-k，n)子矩阵。如图1所描述，从图1可以看出，如果矩阵Hm中前n列元素确定，其他列可以看作是这n列元素下移的结果，这样整个截断校验矩阵也就确定了。截断矩阵的前n列可以表示为H＝{hT1，hT2，hT3，...，hTm}T，它被称为基本校验矩阵。有关上面介绍一些概念，详细可参考下列文献“纠错码-原理与方法”王新梅、萧国镇编著，ISBN 7-5606-0163-4/TN.0059，西安电子科技大学出版社出版，2001年4月修订版，2003年5月第5次印刷。
本专利首先将提出一种码率为n/1的卷积码。在卷积码定义中，n为输出码字信息位长度。此时，该码率卷积码的约束长度为n-1。码率为n/1的卷积码用四元组的表达方式可记作(n，n-1，m，d)。在设计该卷积码时，为了使得它能够提供对测试响应压缩时避免2个错误位不发生混淆情况，要求我们设计规则能使得所设计卷积码的距离为3。错误位发生混淆是指当测试响应中有错误位时，由于压缩电路压缩是有损压缩，导致错误位的特征信息丢失，而使得带有错误位的响应经过压缩后的特征输出和正确响应经过压缩后的特征输出完全一致。这种一致性使得测试者对测试结果发生混淆，将带有故障的芯片误认为是正常芯片。
为了便于描述本发明中提出码率为n/1的卷积码的设计规则，需要先定义一个等价的概念对于两个m次多项式R1(x)，和R2(x)，则等价关系R1(x)≅R2(x)]]>当且仅当(I)---∃σ|R1(x)=xσ×R2(x),(0≤σ≤m-1-deg(R2x))]]>或者
(II)---∃σ|R2(x)=xσ×R1(x),(0≤σ≤m-1-deg(R1(x)))]]>这里deg(.)是多项式中最大非零系数对应的次数。
根据等价的概念可以简单的构造一个码率为n/1，距离为3的卷积码。如果满足其他个设计规则，使得根据该卷积码校验矩阵构造的压缩电路能够在面对任意奇数个错误位时，不发生混淆。该卷积码的设计规则如下所述设计规则1对于卷积码(n，n-1，m，d)，在基本校验矩阵中，如果任意两列均不等价，那么该卷积码的距离为3。
设计规则2对于卷积码(n，n-1，m，d)，在基本校验矩阵中，任意两列的重量均为奇数，那么根据该卷积码基本校验矩阵实现的压缩电路可以发现任意奇数个错误位。
设计规则3对于卷积码(n，n-1，m，d)，在基本校验矩阵中，如果任意两列均不等价，且每一列的重量均相等，那么根据该卷积码基本校验矩阵实现的压缩电路可以发现伴随着一个不确定位的单错误位。
其中，列中“重量”是指列中所含1的个数。用字母w来标识重量。
如果三个规则同时使用，那么所设计的卷积码的基本校验矩阵的实现电路可以提供在1，2，3和任意奇数个错误位情况下，不发生混淆。而且还就可以提供一个不确定位的处理能力。
应用随机生成算法可以很方便的去构造各列重量相等的符合规则1、2、3的基本校验矩阵。图2中介绍了一个基于随机选取的基本校验矩阵生成方法。其具体方法流程可参考图2。
根据上述设计规则所设计的卷积码的基本校验矩阵，我们可以用硬件电路设计测试响应压缩电路，这是本发明另一个关键点。上述码率为n/1的卷积码的基本校验矩阵实现的压缩电路可以由异或门树电路构造。该电路的设计可以参考图4。异或门树电路的输入是连接在芯片内扫描链单元的输出上，经过多级级联后，通过唯一一个输出引脚输出。该实现电路是(n，n-1，m，d)卷积码基本校验矩阵的一个映射电路，具体映射规则如下描述(1)各扫描链最后m个扫描单元将可能被连接到异或门树电路上。
(2)每一条扫描链最后m个扫描单元相应对应于基本校验矩阵H的一列中的m个元素。
(3)一条扫描链最后m个扫描单元到异或门树电路的连接关系取决于基本校验矩阵的一列，也就是说基本校验矩阵的每一列对应于一条扫描链最后m个扫描单元到异或门树电路的连接关系。具体对应关系为如果基本校验矩阵中，某一列中某元素对应的值为1，则该元素对应的扫描单元的输出将被连接到异或门树电路上。
本发明中提出的基本校验矩阵生成方法和基本校验矩阵到异或门树电路的映射过程都可以应用程序自动实现。


图1是卷积码截断校验矩阵示例图。
图2是基于随机选取的基本校验矩阵生成方法流程图。
图3是一个符合三条设计规则的基本校验矩阵示例图。
图4是图2基本校验矩阵示例的实现电路示例图。
具体实施例方式
图1中列出了卷积码截断校验矩阵的示例图。对于四元组表达式为(n，k，m，d)的卷积码，其截断校验矩阵为Hm，是一个(m×n，m×(n-k))矩阵。如图1所示，Hm中任一个子矩阵hi均是一个(n，n-k)。也就是说截断校验矩阵有m×n行，m×(n-k)列，任一子矩阵hi有n行，n-k列。图1中阴影的部分均为0。由此可见Hm是一个下三角矩阵。观察截断校验矩阵Hm的构成，截断校验矩阵实际上由其中的矩阵前n列元素确定，也即是由其中的子矩阵h1，h2，h3，...，hm。决定，其他列可以看作是这n列元素下移的结果，这样整个截断校验矩阵也就确定了。截断校验矩阵的前n列可以表示为H＝{hT1，hT2，hT3，...，hTm}T，它被称为基本校验矩阵。
图2是基于随机选取的基本校验矩阵生成方法流程图。下面是基于随机选取的基本校验矩阵生成方法的描述步骤S1开始；步骤S2初始化基本矩阵列向量集合TS，扩展基本校验矩阵列向量集合ETS。初始化TS和ETS就是将TS和ETS首先置为空集合，其集合元素个数为0；步骤S3随机产生一个k位的行向量V，向量V含有w个1，正如上文已经说明，本方法产生的列向量的重量都是相等的；步骤S4判断ETS中是否有向量和V相等，如果没有，则转入步骤S5，否则转入步骤S7，如果是第一次进行这样的判断，TS和ETS应该为空，自然也没有元素和V相等。所以应该转入S5；步骤S5将V加入到TS中；步骤S6将V加入到ETS中，并根据等价概念生成所有与V等价的向量，将这些向量加入到ETS中，根据等价概念产生和V等价的向量，就是将V中的1元素统一左移位或者右移位，在移位的过程中，要保持1的个数和相对位置不变，变化的只是1前面和后面的0的个数的变化；步骤S7判断TS中列向量元素个数是否小于n，如果列向量个数小于或等于n，则转入步骤S3，否则转入步骤S8，如果TS中列向量的个数已经等于n，说明生成的TS中元素组合即可以得到符合规则1，2，3的基本校验矩阵，无需继续产生新的列向量和扩展新的TS和ETS；步骤S8结束。
在图2中，其中，矩阵列向量集合TS为一个一组列向量的集合，如果所构造的卷积码可写作(n，n-1，m，3)，那么集合中向量元素的个数等于扫描链的个数，集合中每个列向量元素含m位，m为约束长度，也就是需要连接到异或门树电路上的扫描链最后扫描单元的最大可能阶数。ETS是一个扩展列向量集合，和TS不同的是该向量集比TS所含元素多，在ETS中，如果存在一个列向量，那么和该列向量等价的所有列向量必在ETS中。ETS的目的在于提供一个所有已选列向量及他们所有等价列向量的完全集合，以后随机产生一个新向量后就只需要判断该向量是否在ETS中，就可以知道它是否和已选择的列向量是否等价。
图3给出了一个列数为6，行数为5的基本校验矩阵示例。该校验矩阵由图2描述的方法生成，下面介绍图3中基本校验矩阵的生成过程，这样也可了解图2中方法的具体实施流程。
首先初始化TS和ETS。首先TS和ETS被置为空集合，且n＝6，w＝3，m＝5。
第一次产生列向量产生第一个列向量。第一个列向量V＝[11001]T，其中上标T表示向量的转置。因为ETS为空，所以ETS中没有元素和V相等，所以V将被插入TS，而ETS中将被插入所有和V等价的列向量。此时，TS和ETS分别为TS＝{[11001]T}；ETS＝{[11001]T}。此时，TS中元素的个数为1，小于n(6)。所以，循环产生新列向量。
第二次产生列向量产生第二个列向量。第二个列向量V＝[10101]T。此时，ETS中只有一个向量，且和V不相等。这样，V就被插入TS中，V和所有与V等价的向量将被插入到ETS中。此时，TS和ETS分别为TS＝{[11001]T，[10101]T}；ETS＝{[11001]T，[10101]T}。此时，TS中元素的个数为2，小于n(6)。所以，循环产生新列向量。
第三次产生列向量产生第三个列向量。第三个列向量V＝
T。此时，ETS中有二个向量，且都和V不相等。这样，V就被插入TS中，V和所有与V等价的向量将被插入到ETS中。此时，TS和ETS分别为TS＝{[11001]T，[10101]T，
T}；ETS＝{[11001]T，[10101]T，[11100]T，
T，
T}。此时，TS中元素的个数为3，小于n(6)。所以，循环产生新列向量。
第四次产生列向量产生第四个列向量。第四个列向量V＝[11010]T。此时，ETS中有5个向量，且都和V不相等。这样，V就被插入TS中，V和所有与V等价的向量将被插入到ETS中。此时，TS和ETS分别为TS＝{[11001]T，[10101]T，
T，[11010]T}；ETS＝{[11001]T，[10101]T，[11100]T，
T，
T，[11010]T，
T}。此时，TS中元素的个数为4，小于n(6)。所以，循环产生新列向量。
第五次产生列向量产生第五个列向量。第五个列向量V＝[10011]T。此时，ETS中有7个向量，且都和V不相等。这样，V就被插入TS中，V和所有与V等价的向量将被插入到ETS中。此时，TS和ETS分别为TS＝{[11001]T，[10101]T，
T，[11010]T，[10011]T}；ETS＝{[11001]T，[10101]T，[11100]T，
T，
T，[11010]T，
T，[10011]T}。此时，TS中元素的个数为5，小于n(6)。所以，循环产生新列向量。
第六次产生列向量产生第六个列向量。第六个列向量V＝[10110]T。此时，ETS中有8个向量，且都和V不相等。这样，V就被插入TS中，V和所有与V等价的向量将被插入到ETS中。此时，TS和ETS分别为TS＝{[11001]T，[10101]T，
T，[11010]T，[10011]T，[10110]T}；ETS＝{[11001]T，[10101]T，[11100]T，
T，
T，[11010]T，
T，[10011]T，[10110]T，
T}。此时，TS中元素的个数为6，等于n(6)。所以，不再产生新的列向量。
结束生成的基本校验矩阵的列向量集合为TS＝{[11001]T，[10101]T，
T，[11010]T，[10011]T，[10110]T}。该示例中，生成的TS写成矩阵的形式即为图3所述的矩阵。
生成了基本校验矩阵，需要根据基本校验矩阵生成测试响应压缩电路。压缩电路是由若干个异或门构成的，这些若干个异或门构成一个异或门树电路，实际上也是一个奇偶校验电路。然而，本发明提出的异或门树电路的创新之处在于对同扫描状态进行多步计算来避免一些错误位的混淆情况。所以，本发明中，异或门树电路的设计的关键在于确定扫描链中那些扫描单元的输出需要连接到异或门树电路上进行压缩。确定的方式参考发明前述文中。图4给出了一个根据图3中的基本校验矩阵生成的异或压缩网络。下面结合图3，介绍图4中异或门树电路的生成过程
第一步确定最大可能连接到异或门树电路上的各扫描链最后扫描单元个数为5。
第二步每一条扫描链最后5个扫描单元响应对应于基本校验矩阵的一列中的5个元素。
第三步第一条扫描链对应于图3矩阵中第一列，第一列为[11001]T，也就是说从第一条扫描链倒数第5个单元开始计数，第1个，第2个和第5个扫描单元需要连接到异或门树电路上。
第二条扫描链对应于图3矩阵中第二列，第二列为[10101]T，也就是说从第二条扫描链倒数第5个单元开始计数，第1个，第3个和第5个扫描单元需要连接到异或门树电路上。
第三条扫描链对应于图3矩阵中第三列，第三列为
T，也就是说从第三条扫描链倒数第5个单元开始计数，第2个，第3个和第4个扫描单元需要连接到异或门树电路上。
第四条扫描链对应于图3矩阵中第四列，第四列为[11010]T，也就是说从第四条扫描链倒数第5个单元开始计数，第1个，第2个和第4个扫描单元需要连接到异或门树电路上。
第五条扫描链对应于图3矩阵中第五列，第五列为[10011]T，也就是说从第五条扫描链倒数第5个单元开始计数，第1个，第4个和第5个扫描单元需要连接到异或门树电路上。
第六条扫描链对应于图3矩阵中第六列，第六列为[10110]T，也就是说从第六条扫描链倒数第5个单元开始计数，第1个，第3个和第4个扫描单元需要连接到异或门树电路上。
所有这些需要连接到异或门树电路上的扫描单元连接到异或门树电路上，经过异或门树电路计算后，产生单输出压缩结果，如图4所述。测试向量压缩电路，该压缩电路由若干个异或门组成，这些异或门组成一个多输入单输出的异或门树电路。
测试压缩电路由m个扫描链和一个异或门树组成，每个扫描链由多个扫描单元串连连接，各个串连扫描链分级连接到多输入异或门上，多输入异或门经过串接后再输出到一个单输出上。
本发明中，由于所设计的是单输出压缩电路，所以具有压缩率高的特点。应用本发明中提出的压缩电路后，全扫描设计能够增加2倍扫描链，这就缩短了扫描链的长度，也就减少了测试时间。同时针对扫描测试中容易出现的故障模型进行特殊的设计，保证没有误判情况。而且该压缩电路还提供处理不确定位的能力。
权利要求
1.一种卷积码编码方法，该编码方法特征在于，所设计的卷积码的码率为n/1，距离为3，其中，n是输出码字的长度，所设计的测试响应压缩电路是基于卷积码基本校验矩阵实现的。
2.根据权利要求1的卷积码编码方法，其特征在于，基本校验矩阵满足下列三个规则1)基本校验矩阵中，任意两列是不等价的；2)基本校验矩阵中，每一列的重量为奇数；3)基本校验矩阵中，每一列的重量均相等。
3.根据权利要求2的卷积码编码方法，其特征在于，三个规则，实现方法可由下列八个步骤组成步骤S1开始；步骤S2初始化基本矩阵列向量集合TS，扩展基本校验矩阵列向量集合ETS；步骤S3随机产生一个k位的行向量V，向量V含有w个1；步骤S4判断是否ETS中有向量和V相等，如果有则转入步骤S5，否则转入步骤S7；步骤S5将V加入到TS中；步骤S6将V加入到ETS中，并根据等价概念生成所有与V等价的向量，将这些向量加入到ETS中；步骤S7判断TS中得列向量元素个数是否小于n，如果列向量个数小于或等于n，则转入步骤S3，否则转入步骤S7；步骤S8结束。
4.一种测试向量压缩电路，其特征在于，该压缩电路由若干个异或门组成，这些异或门组成一个多输入单输出的异或门树电路。
5.根据权利要求4中的测试向量压缩电路，其特征在于，异或门树电路，是符合权利要求2中提出的三个规则的基本校验矩阵的实现，从基本校验矩阵到异或门树电路的规则为(1)每一条扫描链最后m个扫描单元相应对应于基本校验矩阵H的一列中的m个元素；(2)扫描链单元和异或门树电路输入的连接关系如果基本校验矩阵中，某一列中某元素对应的值为1，则该元素对应的扫描单元的输出将被连接到异或门树电路的输入上；其中，m为符合权利要求2中两个设计规则的卷积码的约束长度。
6.根据权利要求4中的测试向量压缩电路，其特征在于，由m个扫描链和一个异或门树组成，每个扫描链由多个扫描单元串连连接，各个串连扫描链分级连接到多输入异或门上，多输入异或门经过串接后再输出到一个单输出上。
全文摘要
本发明涉及卷积编码设计和芯片可测性设计中的测试响应压缩电路。首先提出一种码率为n/l，距离为3的卷积码。根据该卷积码的基本校验矩阵可得到一种单输出时序压缩电路。当卷积码基本校验矩阵符合三个规则时，所设计的卷积码的距离就为3。符合这三个规则的基本校验矩阵可用一个自动方法实现，该方法分为8个步骤。卷积码到测试响应压缩电路的映射有三个规则，这三个规则均可用程序自动实现。本发明实现的是单输出压缩电路，所以具有压缩率高的特点。应用本发明压缩电路的全扫描设计，能够缩短扫描链长度，减少测试时间。
文档编号G01R31/28GK1584617SQ20041004598
公开日2005年2月23日 申请日期2004年5月27日 优先权日2004年5月27日
发明者韩银和, 李晓维 申请人:中国科学院计算技术研究所