Heuristic procedure for the reduction of finite-state machines

A practical technique for the reduction of large finite-state machines is proposed. The method is based on an empirical evaluation of the machine outputs.     

Simplification of Boolean functions through petri nets

A technique exploiting the modern concepts of Petri nets for simplification of Boolean functions is proposed. The firing concept of Petri nets has been utilized to give a Petri net interpretation to certain properties of switching algebra. These Petri net interpreted properties are then used for the simplification process. Unlike the existing method, the proposed technique does not require the functions to be expressed explicitly in a canonical form. This alleviates the computational efforts. It is simple and amenable for computer programming implementation.     

Relationship between two concepts of equivalence for finite-state machines

In the letter, the relationship between the well-known concept of `equivalence? and the less well known but important concept of `relational equivalence? of finite-state machines is examined, It is shown that, for two strongly connected finite-state machines, the two concepts are the same. Also for two non-degenerate finite-memory finite-state machines it is shown that the two concepts of equivalence are the same. These results, together with some results already known, lead to a table of relationship between equivalence and relational equivalence of finite-state machines.     

A nonlinear fixed-lag smoother for finite-state Markov processes

The fixed-lag smoothing of random telegraph type signals is studied. The smoothers are derived by first obtaining fixed-point smoothing equations and then using a time discretization. Simulation results are described that verify the qualitative carry-over of known results for the linear-Gaussian problem: the greater the lag, the greater the improvement; beyond a certain lag, no further improvement is obtained by the increase of lag; and the higher the signal-to-noise ratio (SNR), the greater is the improvement over filtering obtained through the use of smoothing. Smoothing errors of one-half the corresponding filtering error are demonstrated.     

Scheduling constraint generation for communicating processes

This paper describes a new algorithm for generation of scheduling constraints in networks of communicating processes. Our model of communication intertwines the schedules of the machines in the network: timing constraints of a machine may affect the schedules of machines communicating with it. This model of communication facilitates the modular specification of timing constraints. A feasible solution to the set of constraints generated gives a schedule for each machine in the network such that all internal constraints of each machine are satisfied and communication between machines is statically coordinated whenever possible. Static scheduling of communication saves on the cost of handshake associated with dynamic synchronization. Our algorithm can handle complex, state-dependent and cyclic timing constraints. Experimental results show that our algorithm is both effective and efficient     

基于广义随机Petri网的导弹新型打击流程建模与分析

在导弹打击流程中加入了战术遂行级的效果评估,建立了导弹新型打击流程的广义随机Petri网模型,并在同时考虑随机概率事件与异步并发事件的情况下,利用随机Petri网分析方法对模型进行了分析与求解,得出了导弹打击活动的准确作战周期,对评估系统效能水平具有重要指导意义。     

Enhanced reliability of finite-state machines in FPGA through efficient fault detection and correction

SRAM based FPGA are subjected to ion radiation in many operating environments. Following the current trend of shrinking device feature size & increasing die area, newer FPGA are more susceptible to radiation induced errors. Single event upsets (SEU), (also known as soft-errors) account for a considerable amount of radiation induced errors. SEU are difficult to detect & correct when they affect memory-elements present in the FPGA, which are used for the implementation of finite state machines (FSM). Conventional practice to improve FPGA design reliability in the presence of soft-errors is through configuration memory scrubbing, and through component redundancy. Configuration memory scrubbing, although suitable for combinatorial logic in an FPGA design, does not work for sequential blocks such as FSM. This is because the state-bits stored in flip-flops (FF) are variable, and change their value after each state transition. Component redundancy, which is also used to mitigate soft-errors, comes at the expense of significant area overhead, and increased power consumption compared to nonredundant designs. In this paper, we propose an alternate approach to implement the FSM using synchronous embedded memory blocks to enhance the runtime reliability without significant increase in power consumption. Experiments conducted on various benchmark FSM show that this approach has higher reliability, lower area overhead, and consumes less power compared to a component redundancy technique.     

基于Petri网和有限状态机方法构建工作流引擎

首先指出工作流在系统建设中的重要作用,其次介绍了Petri网理论和基于事件驱动的有限状态机实现工作流引擎,并将该引擎应用到科研管理系统的开发中,在原有的业务逻辑与表现层之间加入流程控制层.该引擎的引入较之传统信息系统,更容易适应科研业务流程的改变,方便实现某些重点项目特事特办的要求,同时调配资源更加方便.之后介绍了基于这个引擎之上的系统整体架构和运行环境,以及最终的开发技术.最后介绍了本系统比较有独创性的异构数据同步技术.     

An iteration algorithm of coding internal states of finite-state machines for minimizing the power consumption

A heuristic iteration algorithm of coding internal states of finite-state machines for reducing the power consumption is considered. The proposed algorithm is universal and can be applied to any results of coding the internal states (including random) to minimize the power consumption of the finite-state machine. In addition, the user can select a trade-off between the problem-solving quality and algorithm-execution time by specifying the maximum number of iterations. The experimental studies showed that the proposed approach is intended to decrease the power consumption of the finite-state machines on average by a factor of 1.73, as compared with the NOVA algorithm (in separate cases, by a factor of 3.29), and by a factor of 1.40, compared to the JEDI algorithm (in separate cases, by a factor of 2.31).     

Implementation of finite-state machines based on programmable logic ICs with the help of the merged model of Mealy and Moore machines

The problem concerning the synthesis of finite-state machines (FSMs) based on programmable logic ICs, in which FSM’s output variables serve as the code (or part of the code) of internal states, has been examined. A solution to the problem is obtained with the help of the merged model of Mealy and Moore machines. A principal distinction between the proposed and well-known techniques is that an initial FSM undergoes no conversions related to an increase in the number of internal states and transitions thereof. The necessary conditions under which output variables can be used as the code of FSM’s internal states are presented. The method for synthesizing the merged model AC of Mealy and Moore machines is described. Basic results of investigations, as well as promising directions of further studies concerned with the development of new structural models of FSMs, are discussed.     

Optimal smoother for discrete time point processes with finite-state Markov rate (Corresp.)

A closed-form optimal nonlinear smoothing algorithm is derived for estimation of signal that is indirectly observed through a discrete time point process (DTPP). A finite-state Markov signal influences the rate of the point process. The smoothers obtained are simple, recursive, and finite dimensional. An illustrative example of the derived estimation scheme is presented.     

Discontinuities in homogeneous markov processes and their use in modelling technical systems under inspection

This paper provides a modelling framework for the use of Markovian techniques for components and systems exhibiting discontinuities for example due to inspection and scheduled maintenance. This approach can be used as a systematic way to build and categorize complex models for components as long as the Markovian assumption holds. The relevant models have been included as examples. In addition, the framework can be applied to systems composed of several components with dependencies among each other, which may cause large conservativities, if Boolean modelling technique is applied. As an example, a failure combination of three events is discussed, one of which is a scheduled maintenance event, which may be postponed, if one of the redundancies is known to be failed. Two strategies of treating scheduled maintenance are compared with the boolean approach assuming independent basic events. The results for the unavailability differ by orders of magnitude, though the Boolean approach is conservative.     

一种改进的通信有限状态机的错误诊断方法

目前对于通信状态机的研究已经很广泛,但对于通信状态机的错误诊断方法的研究不多,已有的问题模型都是输出错误和转换错误。为了更好地将错误诊断与实际相结合,本文在一般的通信有限状态机模型上,新增了一种不可执行的情况,并在传统的问题模型中新增一种转换未执行错误的问题模型。在假设单个错误的情况下,提出了一整套新的错误诊断算法,算法通过分析症状信息进行分步检测,并利用可疑转换下一步输入输出和用例的转换序列等信息来定位出单个错误。最后,文中给出一个实例,详细描述了算法的诊断过程。     

Changes in the length of internal state codes with the aim at minimizing the power consumption of finite-state machines

Two heuristic techniques intended to encode the finite-state machine (FSM) internal states with the aim at decreasing the power consumption have been discussed. In the first approach, internal state codes are assumed to have the constant length. The second approach is based on code lengths varying from the minimum value to the level not leading to a decrease in power consumption. It is demonstrated that the second technique has a low computational complexity, making it possible to use FSMs with a large number of states. It has been ascertained experimentally that the FSM consumed power inherent to the NOVA algorithm can be decreased by 39% on the average (or by 68% with the use of certain benchmarks) via the first technique. In several cases, the second approach enables us to diminish the consumed power by 34% in comparison with the first one. Practical recommendations for the use of each technique, as well as the promising directions of further investigations, are presented.     

The use of Petri nets to analyze coherent fault trees

The use of Petri nets to represent fault trees is discussed. Using reachability and other analytic properties of Petri nets, a more general and useful method to study the dynamic behavior of the model at various levels of abstraction is examined. The problems of fault-detection and propagation are discussed. For simplicity, only coherent fault trees are considered. However, the representation and analysis techniques are general and can be used for noncoherent fault trees     

Capacity analysis for finite-state Markov mapping of flat-fading channels

In this paper, time-varying flat-fading channels are modeled as first-order finite-state Markov channels (FSMC). The effect of this modeling on the channel information capacity is addressed. The approximation accuracy of the first-order memory assumption in the Markov model is validated by comparing the FSMC capacity with the channel capacity assuming perfect state information at the receiver side. The results indicate that the first-order Markovian assumption is accurate for normalized Doppler frequencies f/sub d/T /spl lsim/ 0.01, in amplitude-only quantization of the channel gain for noncoherent binary signaling. In phase-only and joint phase and amplitude quantization of the channel gain for coherent binary signaling, the first-order Markovian assumption is accurate for f/sub d/T /spl lsim/ 0.001. Furthermore, the effect of channel quantization thresholds on the FSMC capacity is studied. In high signal-to-noise ratio (SNR) conditions, nonuniform two-level amplitude quantization scheme outperforms equiprobable quantization method by 0.8-1.5 dB.     

Dynamic model of communicating hydrocephalus for surgery simulation

We propose a dynamic model of cerebrospinal fluid and intracranial pressure regulation. In this model, we investigate the coupling of biological parameters with a 3-D model, to improve the behavior of the brain in surgical simulators. The model was assessed by comparing the simulated ventricular enlargement with a patient case study of communicating hydrocephalus. In our model, cerebro-spinal fluid production-resorption system is coupled with a 3-D representation of the brain parenchyma. We introduce a new bi-phasic model of the brain (brain tissue and extracellular fluid) allowing for fluid exchange between the brain extracellular space and the venous system. The time evolution of ventricular pressure has been recorded on a symptomatic patient after closing the ventricular shunt. A finite element model has been built based on a computed tomography scan of this patient, and quantitative comparisons between experimental measures and simulated data are proposed.     

Adaptive neural nets for generation of artificial earthquakeprecursors

A novel methodology for generation of artificial earthquake precursors was tested on Southern California earthquake data in reverse and real time modes. When it was tried as a real time generator of earthquake precursors, it successfully predicted the June, 1992, Landers earthquake. The methodology is based on the use of adaptive neural nets (ANN) that process a set of time-dependent attributes calculated in a moving time-window. The most important of them is a danger function. The structure of the neural net is defined by the properties of input data in the moving time window. Thus, the neural net continuously adapts its structure to the time variant properties of the input attributes. The main problem the authors encountered in training the neural net on the earthquake data was the small size of the training set compared to the number of parameters that describe the structure of the ANN. To prevent instability and over-fitting in the training session, the authors used a technique similar to the damping method in least squares approximation