二维测试数据压缩的优化

为了减少内建自测试方案中的测试数据,基于输入精简技术(横向压缩)和TRC测试集嵌入技术(竖向压缩)的二维测试数据压缩的BIST方案.采用改进的输入精简算法和基于相容性判断的TRC种子选择算法,同时对横向和纵向压缩进行优化,包括在相同的相容百分数(PC)的条件下,确定位百分数(PSB)对竖向压缩的影响和在相同的PSB条件下竖向压缩算法中的PC对竖向压缩的影响两个方面.针对ISCAS89实验电路的实验结果表明,每一个PSB值都有一个最优的PC值范围[PClow_limit,PChigh_limit]使存储位数最小,并且与最优的 PClow_limit,和PChigh_limit之间满足近似的线性关系.相对现有的测试数据压缩方案,采用该优化的二维测试数据压缩方案实现的测试电路,不仅存储位数可减少20%～75%,而且可以达到ATPG工具所能达到的故障覆盖率.另外,测试控制逻辑电路简单,可重用性好.最后,由于在测试向量生成器和被测电路之间没有引入逻辑门,因此,不会对电路的性能产生影响.     

BIST测试激励的聚类压缩方法

测试激励压缩方案能减少内建自测试(BIST)电路的存储硬件开销,适合超大规模集成电路的测试.将聚类压缩与循环移位压缩和输入精简压缩巧妙结合,提出一种针对BIST的测试激励聚类压缩方法.首先将难测向量进行x方向输入精简;然后以贪心选择的方法进行y方向聚类压缩,即将测试向量集划分成几个子集,每个子集只存储一个种子向量;最后将聚类后的种子向量集进行z方向移位压缩,将最终的种子向量存储到BIST电路中.测试时,解压电路通过对种子向量进行解压得到全部的难测向量.理论分析和实验结果表明,通过增加相对很少的硬件开销构建聚类移位输入精简解压电路能够产生较高的测试数据压缩率,减少测试向量存储单元,且能以芯片频率进行测试,其中对电路s38584的压缩率高达99.87%.     

基于折叠计算的多扫描链BIST方案

为了减少测试数据的存储需求并降低测试应用时间,提出一种以折叠计算为理论的多扫描链BIST方案.首先利用输入精简技术在水平方向上压缩测试集,确定相容扫描链,在测试过程中对相容扫描链中的数据进行广播;然后利用折叠计算理论对测试集进行垂直方向上的压缩,使得同一折叠种子生成的相邻测试向量仅有1位不同,且在测试过程中测试向量并行移人多扫描链,在ISCAS标准电路上的实验结果表明,该方案的平均测试数据压缩率为95.07％,平均测试应用时间为之前方案的13.35％.     

应用向量划分的低功耗确定性BIST方法

提出一种能够与LFSR重播种技术结合的确定性向量生成方法,该方法利用扫描向量中的切片重叠来同时减少确定位数目和跳变数目,可大大降低测试功耗和测试存储.在硬件结构中,用一个译码器来生成控制信号.实验结果表明,对于ISCAS89基准电路,采用文中方法能够减少80%左右的跳变,而只需要原始Mintest测试集25%左右的测试数据存储.     

一种基于双重种子编码确定低功耗BIST方案

本文提出了一种基于双重种子编码的完全确定低功耗BIST方案,它是基于电路完全确定性测试集的特征,结合LFSR和折叠压缩双重编码方案,完成对完全确定性测试集的编码,获取最小的折叠种子集。当对折叠种子进行解压时,调整生成测试向量之间的顺序,确保相邻向量之间的高相关性,从而避免了电路在测试过程中产生过多的开关活动,因此保证了测试是在低功耗下完成的。实验数据表明,本方案的功耗约为门控时钟方案的1%左右;同时,本方案的编码效率比连续长度码好,且解压过程简单易实现。     

一种新型内建自测试重播种技术

测试数据压缩是SoC(System on a Chip)测试领域研究的一个热点问题.本文提出一种新型的内建自测试重播种技术,这项技术利用一个LFSR(Linear Feedback Shift Register)的种子对多个确定性测试向量进行编码压缩,能够显著提高测试数据的压缩率.在ISCAS89基准电路上进行的实验数据显示,这项技术可以减少约30%的LFSR种子数量,进而降低了测试成本.     

嵌入广义折叠技术的集成电路测试数据压缩方案

针对芯片测试过程中自动测试设备需要传输大量测试数据到被测芯片,浪费了大量的测试数据传输时间的问题,提出一种广义折叠技术的集成电路测试数据压缩方案.首先构建有向图,将完全测试集映射到有向图中;其次查找有向图中最长路径,将完全测试集分割成若干个广义折叠集;最后存储广义折叠集的种子和广义折叠距离.另外,提出了广义折叠集的解压结构.理论上可以将整个测试集的存储转化成若干个广义折叠种子和广义折叠距离的存储.对部分ISCAS89标准电路中规模较大的时序电路进行实验的结果表明,在同样实验环境下,该方案在压缩效果方面优于Golomb码、FDR码、EFDR码和折叠集等成熟的压缩方法.     

一种将测试集嵌入到Test-per-Clock位流中的方法

集成电路测试方案的关键在于测试向量产生器的设计.传统的测试方法在测试向量生成、测试应用的过程中,没有充分利用测试数据位流来构建测试向量,从而造成了测试时间和存储开销的增加.为了减少测试成本,提出了一种基于test-per-clock模式的内建自测试方法.通过对线性移位测试结构的分析,提出了一种递进式的反复测试生成方法:顺序求解输入位流,逆向精简,多次求解以获得更优值,最终将测试集以较小的代价嵌入到test-per-clock位流中.在测试应用时,只需存储求解后的最小输入流,通过控制线性移位的首位从而生成所需的测试集.实验结果表明,在达到故障覆盖率要求的前提下,能显著地减少测试应用时间和存储面积开销.     

基于三态信号的测试数据相容压缩方法

针对超大规模集成电路（VLSL）的发展过程中测试数据量增加的问题，提出了一种基于三态信号的测试数据压缩方法。首先，对测试集进行优化预处理操作，即对测试集进行部分输入精简和测试向量重排序操作，在提高测试集中无关位X的比例的同时，使各测试向量之间的相容性提高；随后，对预处理后的测试集进行三态信号编码压缩，即利用三态信号的特性将测试集划分为多个扫描切片，并对扫描切片进行相容编码压缩，考虑多种相容规则使得测试集的压缩率得到提高。实验结果表明，与同类压缩方法相比，所提的方法取得了较高的压缩率，平均测试压缩率达到76.17%，同时测试功耗和面积开销也没有明显增加。     

减少多种子内建自测试方法硬件开销的有效途径

提出一个基于重复播种的新颖的BIST方案，该方案使用侦测随机向量难测故障的测试向量作为种子，并利用种子产生过程中剩余的随意位进行存储压缩；通过最小化种子的测试序列以减少测试施加时间．实验表明，该方案需要外加硬件少，测试施加时间较短，故障覆盖率高，近似等于所依赖的ATPG工具的故障覆盖率．在扼要回顾常见的确定性BIST方案的基础上，着重介绍了文中的压缩存储硬件的方法、合成方法和实验结果．     

基于优化编码的LFSR重播种测试压缩方案

大规模高密度集成电路测试中存在测试数据量大、测试功耗高等问题.提出了一种先通过编码优化测试集,再使用线性反馈移位寄存器(linear feedback shift register,LFSR)重播种的内建自测试方案.该方案通过自动测试模式生成工具得到被测电路的确定测试集,再压缩为种子集存储在片上ROM中.压缩测试集的过程中,首先以降低测试功耗为目标,用少量确定位编码测试集中的部分测试立方,来增强解码后测试模式相邻位之间的一致性;然后以提高压缩率同时降低LFSR级数为目标,将测试立方编码为确定位含量更少的分段相容码(CBC),最后将以CBC编码的测试立方集压缩为LFSR种子集.实验证明所提出的方案在不影响故障覆盖率的前提下大量降低了测试功耗,并且具有更高的测试数据压缩率.     

Hardness of optimal spaced seed design

Speeding up approximate pattern matching is a line of research in stringology since the 80s. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are first excluded, and the remaining regions are then compared to the pattern by dynamic programming. Among the conditions used to test similarity between the regions and the pattern, many require a minimum number of common substrings between them. When only substitutions are taken into account for measuring dissimilarity, counting spaced subwords instead of substrings improves the filtration efficiency. However, a preprocessing step is required to design one or more patterns, called spaced seeds (or gapped seeds), for the subwords, depending on the search parameters. Two distinct lines of research appear the literature: one with probabilistic formulations of seed design problems, in which one wishes for instance to compute a seed with the highest probability to detect the desired similarities (lossy filtration), a second line with combinatorial formulations, where the goal is to find a seed that detects all or a maximum number of similarities (both lossless and lossy filtration). We concentrate on combinatorial seed design problems and consider formulations in which the set of sought similarities is either listed explicitly (RSOS), or characterised by their length and maximal number of mismatches (Non-Detection). Several articles exhibit exponential algorithms for these problems. In this work, we provide hardness and inapproximability results for several seed design problems, thereby justifying the complexity of known algorithms. Moreover, we introduce a new formulation of seed design (MWLS), in which the weight of the seed has to be maximised, and show it is as difficult to approximate as Maximum Independent Set.     

Ontology matching benchmarks: Generation,stability, and discriminability

The OAEI Benchmark test set has been used for many years as a main reference to evaluate and compare ontology matching systems. However, this test set has barely varied since 2004 and has become a relatively easy task for matchers. In this paper, we present the design of a flexible test generator based on an extensible set of alterators which may be used programmatically for generating different test sets from different seed ontologies and different alteration modalities. It has been used for reproducing Benchmark both with the original seed ontology and with other ontologies. This highlights the remarkable stability of results over different generations and the preservation of difficulty across seed ontologies, as well as a systematic bias towards the initial Benchmark test set and the inability of such tests to identify an overall winning matcher. These were exactly the properties for which Benchmark had been designed. Furthermore, the generator has been used for providing new test sets aiming at increasing the difficulty and discriminability of Benchmark. Although difficulty may be easily increased with the generator, attempts to increase discriminability proved unfruitful. However, efforts towards this goal raise questions about the very nature of discriminability.     

中医针灸领域术语自动抽取研究

针对中医针灸领域术语的构成特点,该文建立了一种基于规则的领域术语抽取算法模型,该模型首先对中医针灸领域术语种子集进行有限次的迭代,生成中医针灸领域术语构件集;然后,以术语构件集为领域词典,采用最大向前匹配算法对中文针灸医学文献中的句子进行切分,并抽取候选术语;最后,利用语言规则对候选术语进行过滤处理,筛选出中医针灸领域专业术语。分别以关键字集和中医词典为种子集进行实验,开式测试的F值分别达到76.96%和35.59%。
     

基于BootStrapping的中文事件元素抽取系统设计与实现

采用基于BootStrapping的方法实现中文事件元素抽取系统。其中,将事件元素抽取定义为一个模式匹配问题。针对这一问题,首先构建了初始种子集,然后创新性地引入了BootStrapping方法构建模板集,并使用模式匹配的方法进行事件元素抽取。在模板构造过程中,提出了基于BestMatch的模板泛化算法[1]。对任意两个事件实例模板[2]进行匹配,计算其匹配代价并泛化,提高了模板的覆盖能力。所实现的系统在ACE 2005语料测试中取得了不错结果。     

基于扫描森林结构的种子编码方案

扫描森林是一种有效的扫描结构，它能够大幅度地降低测试应用开销、测试功耗以及测试数据容量。该文针对采用扫描森林结构的待测电路提出了一种新的种子编码方案。在该方案中，伪随机测试向量覆盖电路中的易测故障，使用ATPG对剩余故障生成确定性测试向量，将其中某一测试向量对应的种子编码为LFSR扩展成该向量需要运行的时钟周期数。实验结果表明，提出的方案能大幅度地降低种子存储数据量，最大降幅达到了83.3％。     

Provably good pattern generators for a random pattern test

This paper describes a pseudorandom pattern generator for the random pattern test of combinational circuits. Suppose that a fractionp of the possible patterns detects some fault and the generator generates L patterns to test the circuit. Then the probability that the generator generates a pattern that tests the fault is at leastpL/(pL + 1). The only assumption is that all values of the seed of the generator are equally likely. The seed is twice as long as a single pattern. The generator is less than twice as expensive as a linear feedback shift register. Thus, it can be used in practice. More complicated generators that achieve a better bound are also discussed.This research was supported in part by the National Science Foundation under Grants CCR-8810609 and CDA-8805910.     

基于确定模式的伪单跳变测试矢量生成技术

提出了一种基于确定模式的伪单跳变测试矢量生成方法,它是在折叠计数器确定模式的基础上,采用LFSR编码折叠计数器种子,通过选定的存储折叠距离来控制测试模式,使得产生的测试矢量之间实现伪单跳变。由于是在确定模式基础上进行的研究,没有改变原来的测试矢量,所以故障覆盖率不会改变,却大大降低了测试功耗。这样既保证了高故障覆盖率,又解决了不同种子所生成的测试矢量之间的重叠冗余。研究结果不仅表明该方案具有很好的数据压缩率,而且证明了该方案的有效性。     

一种元路径下基于频繁模式的实体集扩展方法

实体集扩展是指,已知某个特定类别的几个种子实体,根据一定的规则得到该类别的更多的实体.作为一种经典的数据挖掘任务,实体集扩展已经有很多的应用,诸如字典建立、查询建议等.现有的实体集扩展主要是基于文本或网页信息,即实体之间的关系从其在文本或者网页中的共现来推断.随着知识图谱研究的兴起,根据知识图谱中知识的共现来研究实体集扩展也成为了一种可能.本文主要研究知识图谱中的实体集扩展问题,即给定几个种子实体,利用知识图谱来得到更多的同类别的实体.我们首先把知识图谱建模成一个异质信息网络,即含有多种实体类型或者关系类型的网络,提出了一种新的元路径下基于频繁模式的实体集扩展方法,称为FPMP_ESE.FPMP_ESE采用异质信息网络中的元路径来捕捉种子实体之间的潜在共同特征.,为了找到种子实体之间的重要的元路径,我们设计了一种新的基于频繁模式的元路径自动产生算法FPMPG.之后,为了更好地给每条元路径分配相应的权重,我们设计了启发式的方法和PU learning的方法.最后,在真实数据集Yago上的实验,验证了提出方法较其他方法在实体集扩展任务上具有更好地性能以及更高地效率.