Statistical Delay Fault Coverage Estimation for Synchronous Sequential Circuits

We present a technique to statistically estimate path-delay fault coverage for synchronous sequential circuits. We perform fault-free simulation using a multivalue algebra and accumulate signal transition statistics, from which we calculate controllabilities of all signals and sensitization probabilities for all gates and flip-flops. We use a rated clock testing model where all time frames operate at the rated clock. We obtain path observabilities either by enumerating paths in the all-paths method, or by a nonenumerative method considering only the longest paths. The path-delay fault detectability is the product of observabilities of signals on paths from primary inputs (PIs) or pseudo-primary inputs (PPIs) to primary outputs (POs) or pseudo-primary outputs (PPOs), and the controllability on the corresponding PI or PPI. We use the optimistic update rule of Bose et al. for updating latches during logic simulation. When compared with exact fault simulation, the average absolute deviation in our statistical fault coverage estimation technique is 1.23% and the very worst absolute deviation was 6.59%. On average, our method accelerates delay fault coverage computation four times over an exact path delay fault simulator.     

Cell delay fault testing for iterative logic arrays

C-testable iterative logic arrays for cell-delay faults are proposed. A cell delay fault occurs if and only if an input transition can not be propagated to the cell's output through a path in the cell in a specified clock period. The set of single-path propagation, hazard-free robust tests that completely check all the paths in a cell is first derived, and then necessary conditions for sending this test set to each cell in the array and simultaneously propagating the fault effects to the primary outputs are given. Test set minimization can be solved in a similar way as for the fault cover problem. We use the pipelined array multiplier as an example, and show that it is C-testable with 214 two-pattern tests. With a small number of additional patterns, all the combinational faults can be detected pseudoexhaustive.     

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.     

Probabilistic fault grading based on activation checking and observability analysis

A simplified probabilistic fault grading method is described. The concept of propagation probability is introduced in place of the sensitization probability of STAFAN, and the empirical parameters of STAFAN are eliminated. The division of input vectors into subsets is monitored by the activation or toggle rate. The accuracy of the method is examined for fault coverage estimation and for predicting the undetected faults.     

An efficient built-in self test method for robust path delay fault testing

Single Input Change (SIC) testing has been proposed for robust path delay fault testing. In this letter a new Built-In Self Test (BIST) method for SIC vector generation is presented. The proposed method compares favourably to the previously proposed methods for SIC pattern generation with respect to hardware overhead and time required for completion of the test.     

The optimistic update theorem for path delay testing in sequential circuits

For sequential circuit path delay testing, we propose a new update rule for state variables whereby flipflops are updated with their correct values provided they are destinations of at least one robustly activated path delay fault. Existing algorithms in the literature, for robust fault simulation and test generation, assign unknown values to off-path latches that have non-steady signals at their inputs in the previous vector. Such procedures are pessimistic and predict low fault coverages. They also have an adverse effect on the execution time of fault simulation especially if the circuit has a large number of active paths. The proposed update rule avoids these problems and yet guarantees robustness.     

Efficient multiple path propagating tests for delay faults

This paper presents a test generation procedure for obtainingmaximal multiple-path-propagating robust tests, which detect the largest possible number of path faults simultaneously. Specialized heuristics are used to facilitate the generation of such tests in two-level circuits, and methods are given for extensions to multi-level circuits. Experimental results are presented to demonstrate the efficacy of this approach, which is seen to significantly reduce test-set lengths for path delay faults by generating highlyefficient robust tests. Limitations of the method are discussed, together with suggestions for future research.     

基于网络拓扑的动态时延估算模型的研究

网络时延测量技术是了研究互联网的重要手段。针对网络时延估算问题,首先通过网络仿真分析了不同网络拓扑结构下时延序列与路径长度的关系,引入RTT相似度的概念来刻画这种关系。并以此作为网络时延估算的基础,设计了时延估算架构并提出了基于网络拓扑的时延估算模型。该模型利用线性回归的方法得到时延估算方程及估算精度。结合这些数据给出了动态时延估算方法,该方法可以根据不同的估算精度要求动态地选取测量节点进行时延估算,从而使时延估测系统更加灵活和高效。     

Classification and Test Generation for Path-Delay Faults Using Single Struck-at Fault Tests

We classify all path-delay faults of a combinational circuit intothree categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent} (ST-dependent). The classification uses anyunaltered single stuck-at fault test generation tool. Only two runsof this tool on a model network derived from the original network areperformed. As a by-product of this process, we generate single andmultiple input change delay tests for all testable faults. With thesetests, we expect that most defective circuits are identified. All STfaults are guaranteed detection in the case of a single fault, andsome may be guaranteed detection through robust and validatablenon-robust tests even in the case of multiple faults. An ST-dependentfault can affect the circuit speed only if certain ST faults arepresent. Thus, if all ST faults are tested, the ST-dependent faultsneed not be tested. MT faults cannot be guaranteed detection, butaffect the speed only if delay faults simultaneously exist on a setof paths, none of which is ST. Examples and results on several ISCAS89 benchmarks are presented. The method of classification throughtest generation using a model network is complex and can be appliedto circuits of moderate size. For larger circuits, alternativemethods will have to be explored in the future.     

Dynamic Faults in Random-Access-Memories: Concept, Fault Models and Tests

The ever increasing trend to reduce DPM levels of memories requires tests with very high fault coverage and low cost. This paper describes an important fault class, called dynamic faults, that cannot be ignored anymore. The dynamic fault behavior can take place in the absence of the static fault behavior, for which the conventional memory tests have been constructed. The concept of dynamic fault will be established and validated for both dynamic and static Random-Access-Memories. A systematic way to develop fault models for dynamic faults will be introduced. Further, it will be shown that conventional memory tests do not necessarily detect its dynamic faulty behavior, which has been shown to exist in real designs. The paper therefore also presents new memory tests to target the dynamic fault class.     

Bounded delay timing analysis and power estimation using SAT

This paper presents a satisfiability based approach that can be used for accurate estimation of both the critical delay and dynamic transition power consumption of circuits using an event propagation model. The accuracy of the model depends on the accuracy of the gate delays. The speed and efficiency of modern Boolean SAT solvers permits us to model complicated delay models like the Bounded Delay Model, which is better able to capture realistic variations in gate delays due to process variations and changes in operating conditions. We show that timing analysis with bounded delays yields a more accurate critical delay for a circuit than with fixed gate delays. In spite of the high complexity due to unpredictable gate delays, our SAT based approach gives good performance on benchmark circuits, even with a Bounded Delay Model derived from a real industrial library.     

The Coupling Model for Function and Delay Faults

We propose a high-level fault model, the coupling fault (CF) model, that aims to cover both functional and timing faults in an integrated way. The basic properties of CFs and the corresponding tests are analyzed, focusing on their relationship with other fault models and their test requirements. A test generation program COTEGE for CFs is presented. Experiments with COTEGE are described which show that (reduced) coupling test sets can efficiently cover standard stuck-at-0/1 faults in a variety of different realizations. The corresponding coupling delay tests detect all robust path delay faults in any realization of a logic function. This research was sponsored in part by the U.S. National Science Foundation under Grants No. CCR-9872066 and CCR-0073406. Joonhwan Yi received the B.S degree in electronics engineering from Yonsei University, Seoul, Korea, in 1991, and the M.S. and Ph.D degrees in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 1998 and 2002, respectively. From 1991 to 1995, he was with Samsung Electronics, Semiconductor Business, Korea, where he was involved in developing application specific integrated circuit cell libraries. In 2000, he was a summer intern with Cisco, Santa Clara, CA, where he worked for path delay fault testing. Since 2003, he has been with Samsung Electronics, Telecommunication Network, Suwon, Korea, where he is working on system-on-a-chip design. His current research interests include C-level system modeling for fast hardware and software co-simulation, system-level power analysis and optimization, behavioral synthesis, and high-level testing. John P. Hayes received the B.E. degree from the National University of Ireland, Dublin, and the M.S. and Ph.D. degrees from the University of Illinois, Urbana-Champaign, all in electrical engineering. While at the University of Illinois, he participated in the design of the ILLIAC III computer. In 1970 he joined the Operations Research Group at the Shell Benelux Computing Center in The Hague, where he worked on mathematical programming and software development. From 1972 to 1982 he was a faculty member of the Departments of Electrical Engineering– Systems and Computer Science of the University of Southern California, Los Angeles. Since 1982 he has been with the Electrical Engineering and Computer Science Department of the University of Michigan, Ann Arbor, where he holds the Claude E. Shannon Chair in Engineering Science. Professor Hayes was the Founding Director of the University of Michigan's Advanced Computer Architecture Laboratory (ACAL). He has authored over 225 technical papers, several patents, and five books, including Introduction to Digital Logic Design (Addison-Wesley, 1993), and Computer Architecture and Organization, (3rd edition, McGraw-Hill, 1998). He has served as editor of various technical journals, including the Communications of the ACM, the IEEE Transactions on Parallel and Distributed Systems and the Journal of Electronic Testing. Professor Hayes is a fellow of both IEEE and ACM, and a member of Sigma Xi. He received the University of Michigan's Distinguished Faculty Achievement Award in 1999 and the Humboldt Foundation's Research Award in 2004. His current teaching and research interests are in the areas of computer-aided design, verification, and testing; VLSI circuits; fault-tolerant embedded systems; ad-hoc computer networks; and quantum computing.     

Time delay estimation algorithm of narrow band internet of things based on inter-cell interference cancellation

Aiming at the characteristics of NB-IoT such as low power consumption,low cost and low sampling rate,an NB-IoT delay estimation algorithm based on inter-cell interference cancellation was proposed.To gradually eliminate the interaction between signals in each cell,an inter-cell iterative interference cancellation algorithm was considered.In each iteration,the idea of time-frequency cross-correlation overlapping was introduced on the basis of traditional correlation algorithms to break through the limitations of the sampling rate and further improve the accuracy of time delay estimation.At the same time,a first-arrival-path (FAP) searching algorithm based on noise threshold was used to suppress multipath effects.Through experimental simulation,the results show that the proposed algorithm can significantly improve the time delay estimation accuracy of NB-IoT on the basis of related algorithms.     

故障树最小割集和最小路集在火箭故障诊断中的应用

基于提高火箭故障诊断效率的目的,采用故障树分析原理,结合火箭故障的诊断实际,研究了一种基于故障树最小割集和最小路集的火箭故障快速诊断决策方案。为系统的故障源搜寻提供了具体有效的测试步骤。并给出了应用实例。     

一种对流层散射通信斜延迟估计方法

为实现对流层散射通信的实时性,针对散射通信延迟估计问题,提出了一种不事先进行信道测量的对流层通信延迟计算方法。首先利用全球压力和温度2（GPT2）模型计算气象数据,然后采用射线描迹法对大气层分层并积分求和,最后计算出对流层散射通信延迟。采用与射线描迹法相结合的方法,摆脱了射线描迹法对探空数据的依赖。最后选取我国三个典型测量站数据进行算例分析,计算结果与我国对流层延迟实际分布特征相吻合,为研究在不事先进行信道测量的情况下计算对流层散射通信延迟量提供了一种新思路。     

二阶自适应陷波器频率估计方法统计性能分析

为对如何提高自适应陷波器频率估计精度提供参考,通过评估自适应陷波器频率估计方法性能,对基于均方误差函数的自适应陷波器频率估计方法进行了统计性能分析。首先,根据误差函数的不同,将自适应陷波器划分为自适应FIR陷波器和自适应IIR陷波器。然后,将自适应FIR陷波器看作自适应IIR陷波器的特例,重点分析了自适应陷波器的误差函数及稳态下的频率估计统计性能,讨论了自适应陷波器参数对正弦信号频率估计精度和收敛速度的影响。最后,给出正弦信号的频率估计计算结果。结果表明,实际计算结果同理论计算结果一致,证明了统计性能分析的正确性。      

工艺浮动下数字门电路延时建模研究

作为一种有望解决工艺浮动下数值电路时序问题的技术,基于模块的统计静态时序分析(SSTA)需要特殊形式的门延时模型。虽然多数研究都假设能够获得这些特殊形式的模型,对于一个完整的数字库建立这必不可少的模型却不是一件简单的事。为了在不花费不可承受的代价的前提下,获得一个精度可以接受的库,我们提出利用一些具有更一般形式的数字门延时模型作为电路仿真数据和特殊形式的门延时模型的中介。在本工作中,我们提出了两个工艺浮动下可以同时考虑不同的驱动及负载条件的门电路模型。从实验结果来看,这两个模型,特别是其中那个结合了有效维度降低技术的可理解门延时模型可以以较低的代价提供较高精度的模型,因此适用于SSTA技术。同时,这些模型也可以用在其他形式的SSTA技术中。     

Resynthesis of Combinational Circuits for Path Count Reduction and for Path Delay Fault Testability

Path delay fault model is the most suitable model for detectingdistributed manufacturing defects which can cause delayfaults. However, the number of paths in a modern design can beextremely large and the path delay testability of many practicaldesigns is very low. In this paper we show how to resynthesize acombinational circuit in order to reduce the total number of paths inthe circuit. Our results show that it is possible to obtain circuitswith a significant reduction in the number of paths while notincreasing area and/or delay of the longest sensitizable path in thecircuit.Research on path delay testing shows that in many circuits a largeportion of paths does not have a test that can guarantee detection ofa delay fault. The path delay testability of a circuit would increaseif the number of such paths is reduced. We show that addition of asmall number of test points into the circuit can help reducing thenumber of such paths in the given design.     

基于改进粒子滤波的PSK信号时延和码元联合估计算法

提出了一种基于自适应重采样的粒子滤波算法用于对PSK信号的时间延迟进行估计,可以消除由于状态噪声方差设置过小而产生不准确的后验概率分布和设置过大引起的估计误差增大的问题.同时,考虑已有算法无法实现较小时间延迟准确估计的问题,提出了一种码元正向与反向检测相结合的算法,可实现一个码元周期内任意时间延迟的准确估计.另外,对载频偏差进行精确估计并补偿.仿真结果表明这种新方法与原算法相比能够实现更精确的时间延迟估计与更低码元检测误码率