一种可逆有限状态机的电路设计

不同以往通过重构电路行为实现可逆有限状态机方法,本文提出了一种可逆有限状态机的电路结构.该电路主要包括次态与输出计算电路以及状态预置与采样锁存电路两部分,且提出的可逆有限状态机电路中不存在独立的可逆触发器,但可以实现可逆JK,D,T等触发器功能.同时,文中也提出了基于该可逆有限状态机电路的可逆时序电路综合方法,并用实例进行了验证.相比于基于行为重构的可逆有限状态机的综合方法,本文提出的综合方法可以避免原始状态机的逆状态机的求解和增加额外的信号位,从而使得综合过程变得更加简单.     

逆向逻辑综合与功能测试建模

本文在分析时序电路故障检测试法存在难题的基础上,提出一种功能测试建模的新方法。具体内容包括:时序电路功能测试建模的要求;利用逆向逻辑综合方法完成同步时序电路测试的建模;以及异步时序电路功能测试建模的特点。这对时序电路功能测试序列的自动生成有重要意义,因为有了这样的模型,时序电路的自动测试生成可归结为图论算法问题。     

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

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

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

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

时序系统的状态组区别序列测试方法

介绍了采用单变迁故障模型的时序系统状态组区别序列测试方法,通过选择状态组区别序列优化测试序列长度。这种测试生成方法比时序电路门级测试生成快得多,而且能达到很高的故障覆盖率。     

基于Hopfield网络的时序电路测试方法探析

针对时序电路置初态难的问题,提出了利用假想思想把时序电路转化为组合电路的方法,并结合时序电路的特点来实现测试矢量。发现利用EDA工具软件仿真正常电路的波形。可很快得到稳定状态,选择不同的反馈线可得到各稳定状态的次组合电路。结果表明此方法可实现故障的测试矢量,是一种研究时序电路故障测试产生的有效方法。     

BACnet应用层测试状态机自动生成研究

协议状态机测试是通信协议一致性测试的重要内容，状态机的自动测试有利于提高协议测试的效率。本文首先介绍了扩展有限状态机模型，然后采用扩展有限状态机模型对BACnet应用层状态机进行了详细的分析．讨论了BACnet应用层测试状态机自动生成的可能性，最后提出了一个基于规则推理的测试状态机生成方法．该方法能够根据协议一致性声明自动生成测试状态机。     

时序电路的模糊化测试生成算法

文章提出的模糊化的时序电路测试生成算法不明确指定故障点的故障值，它将故障值模糊化，并以符号表示。本算法第一阶段通过计算状态线和原始输出端的故障值来寻找测试矢量，通过计算故障点的正常值来 寻找测试矢量对应的故障类型；第二阶段用故障点的正常值作为约束条件计算故障点的另一个测试矢量。与传统的算法不同，它不需要回退和传播的过程。实验结果表明本算法具有较高的故障覆盖率和较少的测试时间。     

基于有限状态机的错误诊断算法

基于有限状态机的协议的一致性测试问题已经得到了广泛的研究。在检测到错误后,如何诊断错误是一个很重要的问题。该文在有限状态机模型和单个错误的假设下,提出了一种新的错误诊断算法,该算法利用已经确定正确的转换信息以及可疑转换的下一个输入/输出对的头状态集合等信息来高效地诊断单个错误。文中给出了与已有的错误诊断算法的比较结果,并且用一个具体的实例来详细描述本文提出的算法。     

基于状态转换图的测试用例设计方法

本文针对传统设计方法中无法兼顾输入条件的组合与有序状态转移的问题，提出了基于状态转换图的用例设计方法，设计了以有限状态机和决策表形成状态转换的规则，考虑了功能实现时各个状态的执行顺序及状态转换的前提条件和转换路径，并结合实例说明了利用状态转换图进行用例设计的方法。     

Principles and methods of testing finite state machines-a survey

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing     

A test methodology for finite state machines using partial scan design

This paper presents an efficient automatic test pattern generation technique for loop-free circuits. A partial scan technique is used to convert a sequential circuit (finite state machine) with arbitrary feedback paths into a pipelined circuit for testing. Test generation for these modified circuits can be performed with a modified combinational automatic test pattern generator (ATPG), which is much faster than a sequential ATPG. A combinational model is obtained by replacing all flipflops by buffers. It is shown that a test vector for a fault in this model obtained by a combinational test generator can be expanded into a sequence of identical vectors to detect the same fault in the original sequential circuit. This technique may abort a few faults which can then be resolved with a sequential ATPG. Experiments on the ISCAS89 circuits show that only 30% to 70% of flipflops require scanning in larger circuits and 96% to 100% fault coverage for almost all the circuits without resorting to a sequential ATPG.This research was sponsored by the Semiconductor Research Corporation, Contract 90-DP-142.     

Redundancies and don't cares in sequential logic synthesis

The relationships between redundant logic and don't care conditions in combinational circuits are well known. Redundancies in a combinational circuit can be explicitly identified using test generation algorithms or implicitly eliminated by specifying don't cares for each gate in the combinational network and minimizing the gates, subject to the don't care conditions.In this article, we explore the relationships between redundant logic and don't care conditions in sequential circuits. Stuck-at faults in a sequential circuit may be testable in the combinational sense, but may be redundant because they do not alter the terminal behavior of a nonscan sequential machine. These sequential redundancies result in a faulty State Transition Graph (STG) that is equivalent to the STG of the true machine.We present a classification of redundant faults in sequential circuits composed of single or interacting finite state machines. For each of the different classes of redundancies, we define don't care sets which if optimally exploited will result in the implicit elimination of any such redundancies in a given circuit. We present systematic methods for the exploitation of sequential don't cares that correspond to sequences of vectors that never appear in cascaded or interacting sequential circuits. Using these don't care sets in an optimal sequential synthesis procedure of state minimization, state assignment, and combinational logic optimization results in fully testable lumped or interacting finite state machines. We present experimental results which indicate that medium-sized irredundant sequential circuits can be synthesized with no area overhead and within reasonable CPU times by exploiting these don't cares.     

Monitoring machine based synthesis technique for concurrent error detection in finite state machines

This paper discusses a new design methodology for concurrent error detection in synchronous sequential circuits based on the use of monitoring machines. In this approach, an auxiliary sequential circuit, called the monitoring machine, operates in lock-step with the main machine, such that any fault in either of the two machines is immediately detected. This methodology is independent of the fault model. It can be applied to FSMs with pre-encoded states and can also be used for ones being synthesised. It also provides a systematic framework for the combined optimisation of the main and monitoring machines, and for exploring tradeoffs in their implementation. The design of monitored sequential circuits is a two-fold problem; namely one of designing an optimal monitoring machine given the main machine, and the other of encoding the main machine states so that the resulting monitoring machine is minimal. This paper formally discusses the design of both the main and monitoring machines and techniques for their combined optimisation. Tradeoffs in their implementation based on selective fault detection are also examined. Through experimental results, it is shown that the proposed synthesis technique is eminently suitable for the design of low-cost sequential circuits with concurrent error detection. The monitoring machine is less costly than the main machine. It is also not identical to it. As a result, a monitored sequential circuit has significantly lower hardware cost and improved fault coverage than previous implementations. Presently at Texas Instruments (India) Ltd., Bangalore, India.     

CIMT线路码的功率谱分析

本文介绍了一种适于高速光纤数字传输的新型线路码,即ＣＩＭＴ码,并根据有限状态机模型,采用ＣＡＲＩＯＬＡＲＯ算法即状态转移矩阵求解法分析了ＣＩＭＴ码的功率谱,给出了计算示例公式及曲线。ＣＩＭＴ码可有效地抑制信号序列的低频和高频分量,抑制连同的数字,且易于实现     

FsmTest: Functional test generation for sequential circuits

This paper presents a new approach to test pattern generation for sequential circuits modeled as finite state machines. This approach is well suited for controller synthesis, because such devices are usually represented as explicit finite state machines. Based on a functional fault model, only a restricted set of transitions of the finite state machine (FSM) is considered for the purpose of testing. A new state discriminating sequence, referred to as EUIO is proposed. Overlapping is accomplished to reduce the test length. In most cases, test length and CPU time requirements are substantially lower compared with gate-level ATPGs. Techniques are also introduced to preserve a high fault coverage. Evaluation on MCNC benchmarks has shown the effectiveness of the test algorithm both at functional and gate levels, while achieving in most cases 100% coverage of single stuck-at faults.     

Design for Testability Using State Distances

The average distance between states is proposed as a new testabilitymeasure for finite state machines (FSMs). Also proposed is theconcept of center state to reduce distances in FSMs. This testfunction embedding technique has been shown to improve thetestability of sequential circuits with minimal overhead. Anoverview of several design-for-testability (DFT) andsynthesis-for-testability (SFT) methods for sequential circuits willalso be given in this paper. Experimental results have shown thatthe DFT approach is more advantageous than the SFT approach toimplement our test function. The contribution of this paper is toanalyze the trade-offs between several aspects of DFT and SFTtechniques.     

Guaranteed fault detection sequences for single transition faults in finite state machine models using concurrent fault simulation

This paper presents a new algorithm for the generation of test sequences for finite state machines. Test sequence generation is based on the transition fault model, and the generation of state-pair distinguishing sequences. We show that the use of state-pair distinguishing sequences generated from a fault-free finite state machine will remain a distinguishing sequence even in the presence of a single transition fault, thus guaranteeing complete single transition fault coverage. Analysis and experimental results show that the complexity of the test sequence generation algorithm is less than those of the previous algorithms. The utility of the transition fault model, and the generated test sequences is shown by their application to sequential logic circuits. These results show more than a factor of 10 improvement in the test generation time and some reduction in test length while maintaining 100% transition fault coverage.Now with Intel Corporation, FM5-161, 1900 Prairie City Road, Folsom, CA 95630.Now with Chrysalis Symbolic Design, 101 Billerica Ave., North Billerica, MA 01862.