基于二叉树的时序电路测试序列设计

为了实现时序电路状态验证和故障检测,需要事先设计一个输入测试序列。基于二叉树节点和树枝的特性,建立时序电路状态二叉树,按照电路二叉树节点(状态)与树枝(输入)的层次逻辑关系,可以直观和便捷地设计出时序电路测试序列。用测试序列激励待测电路,可以验证电路是否具有全部预定状态,是否能够实现预定状态转换。     

时序电路等价验证的触发器匹配

通常的时序电路等价性验证方法是将触发器按时序展开,从而将时序电路转化为组合电路进行验证。而一般在待验证的两个时序电路中,触发器是一一对应的,找到触发器的对应关系,时序电路的验证就会得到很大的简化。该文通过一种新的基于布尔可满足性(SAT)算法的自动测试模式生成(ATPG)匹配模型建立联接电路,使用时序帧展开传递算法比较触发器的帧时序状态输出,同时在SAT解算中加入信息学习继承等启发式算法,将时序电路的触发器一一匹配。在ISCAS89电路上的实验结果表明,该文算法在对触发器的匹配问题上是非常有效的。     

时序电路可及状态的枚举和自动测试生成

复杂时序电路的测试生成被公认为VL-SI电路测试的难题之一。本文在分析已发表文献对此问题研究情况的基础上,提出一种实用的、可靠的测试生成方法。本方法的特点有二。一是以时序电路可及状态的分析为依据,建立同步、异步时序电路测试的统一数学模型,完全地、准确地反映电路的稳态功能。二是以图论算法为工具,从电路强连通状态转换图中找出最优测试向量序列。此法适用于数字系统层次或功能测试,有效地降低计算复杂性,加快测试生成速度,可望发展成为VLSI电路实用化测试生成方法的一条新途径。     

动态时序电路和广义时序机

本文基于用广义输入信号表示的广义时序机，研究动态时序电路，考虑电容负载时得出动态单元电路特征方程，利用电容存储信息和触发器的类似性，建立了时序电路统一理论，将常规时序电路和动态时序电路理论统一起来，证明实现动态时序电路的条件，结合实例论述各型动态时序电路，伪动态时序电路和静态时序电路的开关级结构间的等价转换。     

时序电路的状态验证研究与设计

采用二元判定图（ＢＤＤ）作为工具来描述时序电路是非常有意义和有效的，本文通过对ＢＤＤ的简化达到对状态变换图（ＳＴＧ）输入，路径和状态的压缩，从而提高状态遍历的效率，另外根据电路的特点，提出状态冲突和不相交分解的启发技术以有效地完成验证。     

时序电路的状态验证研究与设计

采用二元判定图(BDD)作为工具来描述时序电路是非常有意义和有效的.本文通过对BDD的简化达到对状态变换图(STG)输入、路径和状态的压缩,从而提高状态遍历的效率,另外根据电路的特点,提出状态冲突和不相交分解的启发技术以有效地完成验证.     

一种设计同步时序电路的新方法

介绍了一种设计同步时序逻辑电路的新方法。该方法之关键在于直接从时序电路的状态转换图（STD）获得J-K、D和T触发器的激励方程式。采用该方法设计了几个实例，并由此验证了其正确性和有效性。     

基于FSM的时序电路测试生成探析

针对时序电路的结构特点,以有限状态机的状态转换和一致性测试分析为依据,通过采用转换故障模型来实现时序电路的功能测试生成.发现使用VHDL语言和EDA工具软件能很快实现由时序电路到有限状态机的转换,同时可得到时序电路的稳定状态及其有效可及状态.结果表明此方法可实现转换故障的测试生成,是一种研究时序电路功能测试生成的有效方法.     

一种新颖的基于层划分的等价验证方法

提出了一种基于SAT问题的组合电路等价验证算法，该算法特别适用于验证有着一定相似部分的两个电路。其主要创新之处为：1)基于层划分的配对点生成方法；2)基于值控制的回溯过程。ISCAS’85的实例很好地证明了该算法的有效性。     

结合关系建模与项重写技术的时序电路等价验证

提出一个新颖的时序电路等价验证的方法框架.该方法有效地结合了关系建模和项重写技术.首先利用带有测试条件的Kleene关系代数建模时序设计,进而通过对关系表达式的项重写来证明时序设计的等价性.与传统的基于状态空间遍历的时序等价验证方法相比,该方法提供了一种全新的思路.     

The hierarchical timing pair model for multirate DSP applications

The problem of representing timing information associated with functions in a dataflow graph is considered. This information is used for constraint analysis during behavioral synthesis of appropriate architectures for implementing the graph. Conventional models for timing suffer from shortcomings that make it difficult to represent timing information in a hierarchical manner for sequential and multirate systems. Some of these shortcomings are identified, and an alternate timing model that does not have these problems for hardware implementations is provided. We introduce the concept of timing pairs to model delay elements in sequential and multirate circuits and show how this allows us to derive hierarchical timing information for complex circuits. The resulting compact representation of the timing information can be used to streamline system performance analysis. In addition, several analytical results that previously applied only to single rate systems can now be extended to multirate systems. We present an algorithm to compute the timing parameters and have used this to compute timing parameters for a number of benchmark circuits. The results obtained on several ISCAS benchmark circuits as well as several multirate dataflow graphs corresponding to useful signal processing applications are presented. These results show that the new representation model can result in large reductions in the amount of information required to represent timing for hierarchical systems.     

Parallel sequence fault simulation for synchronous sequential circuits

A novel parallel sequence fault simulation (PSF) algorithm for synchronous sequential circuits is presented. The algorithm successfully extend the parallel pattern method for combinational circuits to sequential circuits by proposing a multiple-pass mechanism to overcome the state dependency in sequential circuits. The fault simulation is performed in parallel by partitioning the entire sequence into subsequences of equal length. Furthermore, techniques are developed to minimize the number of simulation passes. Notably, two compact counters, C _x and C _d , are proposed to faciliate the early stabilization detection of faulty circuit simulation with minimum space overhead. The experimental results on the benchmark circuits show that the speedup ratio over a serial sequence fault simulator based on ROOFS is 9.16 on average for pseudo random vectors. The parallel sequence algorithm of PSF is especially adaptable to parallel and distributed simulation which exploits sequence partition.     

A novel automatic test pattern generator for asynchronous sequential digital circuits

A novel automatic test pattern generator (ATPG) for stuck-at faults of asynchronous sequential digital circuits is presented. The developed ATPG does not require support by any design-for-testability method nor external software tool. The shortest test sequence generation is guaranteed by breadth-first search. The contribution is unique hazard identification before the test generation process, state justification on the gate level, sequential fault propagation based on breadth-first search and stepwise composition of state graphs for sequential test generation. A new six-valued logic together with a new algorithm was developed for hazardous transition identification. The internal combinational ATPG allows to generate test patterns one by one and only if it is required by sequential test generation. The developed and implemented ATPG was tested with speed-independent and quasi-delay-insensitive benchmark circuits.     

Accurate power estimation of CMOS sequential circuits

The existence of near-closed sets makes the power estimation of sequential circuits more complicated and time consuming. If caution is not taken, the Monte Carlo-based power estimation techniques for sequential circuits can wrongly terminate the simulation with undesired results. In this paper, we have developed a strategy for a statistical power estimation technique to take into account the possible existence of near-closed sets. We propose an algorithm that partitions states into near-closed sets, if they do exist, and a technique that reduces the computation time of the probabilities of states if state transition graph (STG) is available. If STG is not available, we propose a Monte Carlo-based technique with a warm-up period. The results show that the partitioning algorithm also serves as a detector that signifies whether there may exist near-closed sets. The computation time of state probability can be reduced up to 50% in cases when near-closed sets are present. The relative error of the estimated individual node activity by the Monte Carlo-based technique with a warm-up period is within 3% of the result of long run simulation     

Evolutional searching for circuit structures

A new method based on a genetic algorithm is presented to search for graphs representing structures of circuits with a given transfer function. Operational transconductance amplifier-capacitor filters consisting of lossy and lossless integrators have been taken as an example     

Marked graphs and hamiltonian graphs

In this paper we present an algorithm using a sign incidence matrix to enumerate all the subsets of places of a marked graph which are both siphon and trap, whose input transitions equal the output transitions and where both of them equal the set of all transitions. An iterative procedure to find a set of places in a marked graph whose removal ensures the resulting marked graph does not have a subset of places which are both siphon and trap, is given. This iterative procedure employs a siphon-trap matrix. As an application, using the algorithm given earlier, we have obtained all Hamiltonian circuits of a given directed graph. We have also found the minimal feedback edge set of a given directed graph. A characterization for Hamiltonian graphs is obtained in terms of siphons and traps.     

Simplified Analysis of Coupled Transmission-Line Networks

A relatively simple method is presented for analyzing coupled transmission-line networks by using network graphs and graph transformations. The network graph symbolism is easy to draw and to manipulate. All the graphs consist only of inductor, capacitor, and transformer symbols, and straight lines, which represent unit elements. The method of analysis is illustrated by several two-wire-line and multiwire-line examples. Also presented are several new useful transmission-line transformations and a graph equivalent for the general coupled transmission-line network. The graph-transformation method has four principal advantages: 1) explicit open-wire-line equivalent circuits of coupled line networks can be obtained relatively easily and without knowledge of network synthesis techniques; 2) the form of equivalent circuits can often be obtained without using any algebra; 3) at each step of the analysis, a positive-real network in graph form is available; consequently, in many analysis problems several equivalent circuits for the same network are derived; and 4) multiport networks are as easily dealt with as two-port networks.     

Matching images based on consistency graph and region adjacency graphs

The image matching methods based on regions have many advantages over the point matching techniques, and the most charming one is that once region being matched, all pixels are matched in theory. It would benefit many applications, such as object retrieval, stereo corresponding, semantic understanding a scene, object tracking. This paper proposes a new region matching algorithm based on consistency graph and region adjacency graphs. Firstly, the segmented images are transformed into region adjacency graphs, and the potential region pairs and the potential edge segment pairs are packaged in a consistency graph. Since the rightly matched pair always is accompanied by harmonious neighbourhoods, the right correspondences tend to cluster together, and the error corresponding relationship should have few chances to connect to any compatible neighbourhood. Thus, the solution space is greatly reduced and the corresponding relationship can be found in a polynomial computational complexity just by a simple method, such as seed-growth method. To the best of our knowledge, the method is the first one to match two images by region adjacency graphs and find the corresponding relationship in a polynomial computational complexity. Experiments on the existing benchmark show that the proposed method could quickly find the right corresponding relationship between images with illumination, rotation and affine transformation.