EXOR transform of inputs to design efficient two-level AND/EXORadders

An input transformation based on EXOR gates is presented which enables efficient two-level AND/EXOR representations of adders to be constructed. In general, adders only have exponential two-level representations, but by using the input transformation the complexity decreases to O(n²) requiring only a linear hardware overhead. Exclusive sum-of-products (ESOP) and positive polarity Reed-Muller expression (PPRM) circuits are considered     

Testability and test generation for majority voting fault-tolerant circuits

The testability of majority voting based fault-tolerant circuits is investigated and sufficient conditions for constructing circuits that are testable for all single and multiple stuck-at faults are established. The testability conditions apply to both combinational and sequential logic circuits and result in testable majority voting based fault-tolerant circuits without additional testability circuitry. Alternatively, the testability conditions facilitate the application of structured design for testability and Built-In Self-Test techniques to fault-tolerant circuits in a systematic manner. The complexity of the fault-tolerant circuit, when compared to the original circuit can significantly increase test pattern generation time when using traditional automatic test pattern generation software. Therefore, two test pattern generation algorithms are developed for detecting all single and multiple stuck-at faults in majority voting based circuits designed to satisfy the testability conditions. The algorithms are based on hierarchical test pattern generation using test patterns for the original, non-fault-tolerant circuit and structural knowledge of the majority voting based design. Efficiency is demonstrated in terms of test pattern generation time and cardinality of the resulting set of test patterns when compared to traditional automatic test pattern generation software.     

Low power mapping for AND/XOR circuits and its application in searching the best mixed-polarity

A low power mapping algorithm for technology independent AND/XOR circuits is proposed.In this algorithm,the average power of the static mixed-polarity Reed-Muller(MPRM) circuits is minimized by generating a two-input gates circuit to optimize the switching active of nodes,and the power and area of MPRM circuits are estimated by using gates from a given library.On the basis of obtaining an optimal power MPRM circuit,the best mixed-polarity is found by combining an exhaustive searching method with polarity conversion algorithms. Our experiments over 18 benchmark circuits show that compared to the power optimization for fixed-polarity Reed-Muller circuits and AND/OR circuits,power saving is up to 44.22%) and 60.09%,and area saving is up to 14.13%and 32.72%,respectively.     

Efficient test-point selection for scan-based BIST

We propose a test point selection algorithm for scan-based built-in self-test (BIST). Under a pseudorandom BIST scheme, the objectives are (1) achieving a high random pattern fault coverage, (2) reducing the computational complexity, and (3) minimizing the performance as well as the area overheads due to the insertion of test points. The proposed algorithm uses a hybrid approach to accurately estimate the profit of the global random testability of a test point candidate. The timing information is fully integrated into the algorithm to access the performance impact of a test point. In addition, a symbolic procedure is proposed to compute testability measures more efficiently for circuits with feedbacks so that the test point selection algorithm can be applied to partial-scan circuits. The experimental results show the proposed algorithm achieves higher fault coverages than previous approaches,with a significant reduction of computational complexity. By taking timing information into consideration, the performance degradation can he minimized with possibly more test points     

基于三值多样性粒子群算法的MPRM电路综合优化

通过对离散三值粒子群算法的研究,提出一种三值多样性粒子群算法以求解MPRM（Mixed-Polarity Reed-Muller,MPRM）电路综合优化问题.首先根据混合极性XNOR/OR展开式的特点和几率换算法则,推导出三值粒子群算法的运动方程,在此基础上,采用广泛学习策略和三值变异操作进行算法改进;然后建立三值多样性粒子群算法的粒子与MPRM电路极性的参数映射关系,结合估计模型和XNOR/OR电路混合极性转换方法,将所提算法应用于MPRM电路的最佳功耗和面积极性搜索;最后对10个PLA格式MCNC Benchmark电路进行测试.结果表明：与已发表的方法相比,该文的优化算法表现出了总体显著性的性能优势.     

实用BiCMOS电路可测性设计

本文提出了ＢｉＣＭＯＳ电路的实用可测性设计方案，该方案与传统方法相比，可测性高，硬件花费小，仅需额外添加两个ＭＯＳ管和控制端，就可有效地用单个测试码测出ＢｉＣＭＯＳ电路的开路故障和短路故障，减少了测试生成时间，可广泛应用于集成电路设计中。     

基于多数覆盖的二级MPRM函数逻辑优化

利用不相交乘积项之间逻辑"或"和逻辑"异或"可以互换的特性,该文将原逻辑函数转化成由不相交乘积项组成的二级混合极性Reed-Muller(MPRM)函数。然后通过搜索不相交乘积项的多数覆盖和检测乘积项间的位操作结果,实现了二级MPRM函数的优化。另外,该文还提出一种基于逻辑覆盖的功能验证方法也被提出用于验证逻辑函数优化前后逻辑功能的等效性。实验显示,与已发表的方法相比,该文的优化算法在保证优化效果的同时使运算速度获得了明显的改进。     

On local transformations and path delay fault testability

Several synthesis for path delay fault (PDF) testability approaches are based on local transformations of digital circuits. Different methods were used to show that transformations preserve or improve PDF testability. In this paper we present a new unifying approach to show that local transformations preserve or improve PDF testability. This approach can be applied to every local transformation and in contrast to previously published methods only the subcircuits to be transformed have to be considered.Using our new approach we are able to show in a very convenient way that the transformations which are already used in synthesis tools preserve or improve PDF testability. We present further transformations which preserve or improve testability. We show that a transformation, claimed to preserve PDF testability, in fact, does not do so. Moreover, the testability improving factor which is a unit of measurement for the quality of testability improving transformations is introduced.Additionally, we present the capabilities of SALT (system forapplication oflocaltransformations), which is a general tool for application of a predefined set of local transformations. The implementation of SALT is described and it is shown how the isomorphism of a pattern to be searched and a matched subcircuit can be weakened to allow the application of local transformations more frequently.Finally, we confirm the theoretical part of this paper by experimental results obtained by application of the examined local transformations to several benchmark circuits. The effect of these transformations (and combinations of different types of transformations) on PDF testability, size and depth of the transformed circuits is examined and encouraging results are presented. For example, a reduction of up to 90% can be observed for the number of untestable paths.This work was supported in part by DFG grants Be 1176/4-1, Be 1176/4-2 and SFB 124 VLSI Design Methods and Parallelism.     

基于离散三值粒子群算法的MPRM电路面积优化

Having the advantage of simplicity,robustness and low computational costs,the particle swarm optimization (PSO) algorithm is a powerful evolutionary computation tool for synthesis and optimization of ReedMuller logic based circuits.Exploring discrete PSO and probabilistic transition rules,the discrete ternary particle swarm optimization(DTPSO) is proposed for mixed polarity Reed-Muller(MPRM) circuits.According to the characteristics of mixed polarity OR/XNOR expression,a tabular technique is improved,and it is applied in the polarity conversion of MPRM functions.DTPSO is introduced to search the best polarity for an area of MPRM circuits by building parameter mapping relationships between particles and polarities.The computational results show that the proposed DTPSO outperforms the reported method using maxterm conversion starting from POS Boolean functions.The average saving in the number of terms is about 11.5%;the algorithm is quite efficient in terms of CPU time and achieves 12.2%improvement on average.     

TAO: regular expression-based register-transfer level testabilityanalysis and optimization

In this paper, we present testability analysis and optimization (TAO), a novel methodology for register-transfer level (RTL) testability analysis and optimization of RTL controller/data path circuits. Unlike existing high-level testing techniques that cater restrictively to certain classes of circuits or design styles, TAO exploits the algebra of regular expressions to provide a unified framework for handling a wide variety of circuits including application-specific integrated circuits (ASICs), application-specific programmable processors (ASPPs), application-specific instruction processors (ASIPs), digital signal processors (DSPs), and microprocessors. We also augment TAO with a design-for-test (DFT) framework that can provide a low-cost testability solution by examining the tradeoffs in choosing from a diverse array of testability modifications like partial scan or test multiplexer insertion in different parts of the circuit. Test generation is symbolic and, hence, independent of bit width. Experimental results on benchmark circuits show that TAO is very efficient, in addition to being comprehensive. The fault coverage obtained is above 99% in all cases. The average area and delay overheads for incorporating testability into the benchmarks are only 3.2% and 1.0%, respectively. The test generation time is two-to-four orders of magnitude smaller than that associated with gate-level sequential test generators, while the test application times are comparable     

Partial scan flip-flop selection by use of empirical testability

Partial serial scan as a design for testability technique permits automatic generation of high fault coverage tests for sequential circuits with less hardware overhead and less performance degradation than full serial scan. The objective of the partial scan flip-flop selection method proposed here is to obtain maximum fault coverage for the number of scan flip-flops selected. Empirical Testability Difference (ETD), a measure of potential improvement in the testability of the circuit, is used to successively select one or more flip-flops for addition or deletion of scan logic. ETD is calculated by using testability measures based on empirical evaluation of the circuit with the acutal automatic test pattern generation (ATPG) system. In addition, once such faults are known, ETD focuses on the hard-to-detect faults rather than all faults and uses heuristics to permit effective selection of multiple flip-flops without global optimization. Two ETD algorithms have been extensively tested by using FASTEST ATPG [1, 2] on fourteen of the ISCAS89 [3] sequential circuits. The results of these tests indicate that ETD yields, on average, 35% fewer uncovered detectable faults for the same number of scanned flip-flops or 27% fewer scanned flip-flops for comparable fault coverage relative to cycle-breaking methods.This work was performed while the author was with the University of Wisconsin-Madison.     

Partial Reset Methodology and Experiments for Improving Random-Pattern Testability and BIST of Sequential Circuits

Partial reset has been shown to have significant impact on test generation for sequential circuits in a stored-pattern test application environment. In this paper, we explore the use of partial reset in fault-independent testing and built-in self-test (BIST) of non-scan sequential circuits. We select a subset of flip-flops in the circuit to be resetable to logic one or zero during the application of the test vectors. The resetting is performed with random frequency. The selection of the flip-flops and the reset polarity is based on fault-propagation analysis, which determines the impact of a selected flip-flop on fault propagation from the circuits structure. Application of partial reset as described above yields an average improvement of 15% in fault-coverage for sequential circuits resistant to random pattern testing. To further enhance testability, we also present a methodology for selecting observable test points based on propagation of switching activity. Overall, high fault coverages (about 97%) are obtained for many of the ISCAS89 benchmark circuits. Thus, partial reset BIST provides a low cost alternative for testing sequential circuits when scan design is unacceptable due to area and/or delay constraints. The routing overhead for implementing BIST is seen to be about 6%.     

TESTCHIP: a chip for weighted random pattern generation,evaluation, and test control

In self-testable circuits, additional hardware is incorporated for generating test patterns and evaluating test responses. A built-off test strategy is presented which moves the additional hardware to a programmable extra chip. This is a low-cost test strategy in three ways: (1) the use of random patterns eliminates the expensive test-pattern computation; (2) a microcomputer and an ASIC (application-specific IC) replace the expensive automatic test equipment; and (3) the design for testability overhead is minimized. The presented ASIC generates random patterns, applies them to a circuit under test, and evaluates the test responses by signature analysis. It contains a hardware structure that can produce weighted random patterns corresponding to multiple programmable distributions. These patterns give a high fault coverage and allow short test lengths. A wide range of circuits can be tested as the only requirement is a scan path and no other test structures have to be built in     

Integration of partial scan and built-in self-test

Partial-Scan based Built-In Self-Test (PSBIST) is a versatile Design for Testability (DFT) scheme, which employs pseudo-random BIST at all levels of test to achieve fault coverages greater than 98% on average, and supports deterministic partial scan at the IC level to achieve nearly 100% fault coverage. PSBIST builds its BIST capability on top a partial scan structure by adding a test pattern generator, an output data compactor, and a PSBIST controller in a way similar to that of deriving a full scan BIST from a full scan structure. However, to make the scheme effective, there is a minimum requirement regarding which flip-flops in the circuit should be replaced by scan flip-flops and/or initialization flip-flops. In addition, test arents are usually added to boost the fault coverage to the range of 95 to 100 percent. These test points are selected based on a novel probabilistic testability measure, which can be computed extremely fast for a special class of circuits. This ciass of circuits is precisely the type of circuits that we obtain after replacing some of the flip-flops.withscan and/or initilization flip-flops. The testability measure is also used for a very useful quick estimation of the fault coverage right after the selection of sean flip-flops, even before the circuit is modified to incorporate PSBIST capability. While PSBIST provides all the benefits of BIST, it incurs lower area overhead and performance degradation than full scan. The area overhead is further reduced when the boundary scan cells are reconfigured for BIST usage.     

An analytical approach to the partial scan problem

The scan design is the most widely used technique used to ensure the testability of sequential circuits. In this article it is shown that testability is still guaranteed, even if only a small part of the flipflops is integrated into a scan path. An algorithm is presented for selecting a minimal number of flipflops, which must be directly accessible. The direct accessibility ensures that, for each fault, the necessary test sequence is bounded linearly in the circuit size. Since the underlying problem is NP-complete, efficient heuristics are implemented to compute suboptimal solutions. Moreover, a new algorithm is presented to map a sequential circuit into a minimal combinational one, such that test pattern generation for both circuit representations is equivalent and the fast combinational ATPG methods can be applied. For all benchmark circuits investigated, this approach results in a significant reduction of the hardware overhead, and additionally a complete fault coverage is still obtained. Amazingly the overall test application time decreases in comparison with a complete scan path, since the width of the shifted patterns is shorter, and the number of patterns increase only to a small extent.     

基于极零点灵敏度的模拟电路可测性分析

介绍了基于模拟电路极零点灵敏度的分析方法,给出了极零点灵敏度的计算公式。介绍了模拟电路可测性度量的概念,以及基于极零点灵敏度的模拟电路可测性分析方法,给出了求可测性度量的方法。该方法可以用于确定模拟电路的测试点和测试方法。作为例子,对一个3阶电路进行了简要分析。     

Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property

In the optimization of canonical Reed-Muller (RM) circuits, RM polynomials with different polarities are usually derived directly from Boolean expressions. Time efficiency is thus not fully achieved because the information in finding RM expansion of one polarity is not utilized by others. We show in this paper that two fixed-polarity RM expansions that have the same number of variables and whose polarities are dual can be derived from each other without resorting to Boolean expressions. By repeated operations, RM expansions of all polarities can be derived. We consequently apply the result in conjunction with a hypercube traversal strategy to optimize RM expansions (i.e., to find the best polarity RM expansion). A recursive route is found among all possible polarities to derive RM expansion one by one. Simulation results are given to show that our optimization process, which is simpler, can perform exhaustive search as efficiently as other good exhaustive-search methods in the field.     

A New Testability Calculation Method to Guide RTL Test Generation

Current paper presents a unified approach for calculating mixed-level testability measures. In addition, a new method of testability guided RTL Automated Test Pattern Generation (ATPG) for sequential circuits is introduced. The methods and algorithms are based on path tracing procedures on decision diagrams. The previous known methods have been implemented in test synthesis and in guiding gate-level test generation. However, works on application of testability measures to guide high-level test generation are missing. The main aim of this paper is to bridge this gap. Current method is compared to a recent approach known from the test synthesis area. Experiments show that testability measures greatly influence the fault coverage in RT-level test generation with the proposed approach achieving the best results. Similar to earlier works, our research confirms that RT-level fault coverage is in correlation with logic level one.This revised version was published online in March 2005 with corrections to the cover date.     

可测性度量的计算及研究

本文对ＳＣＯＡＰ可测性度量方法作了改进，提出了动态ＳＣＯＡＰ算法。此算法反映测试生成过程中系统和电路各节点可测性的变化，比静态ＳＣＯＡＰ更准确地描述了每个故障的可测性难度，为测试生成过程提供更有效的启发性信息。