Minimization of mealy finite state machines via internal state merging

The problem of minimizing Mealy finite state machines (FSMs) arises when digital devices based on programmable logic integrated circuits are synthesized. A distinctive feature of the approach proposed is that merging of two states is used and an FSM is represented as a transition list. The conditions used to merge states, the functioning identity and the FSM’s behavior determinacy, are presented. Situations leading to wait state formation caused by state merging are discussed. The algorithms for minimizing the internal states, transition paths, and input variable of FSMs are described. The features of application of the method proposed are discussed.     

Binary shape coding using finite automata

Two new binary shape-coding techniques that are based on finite automata methods are proposed. Both contour-based and bitmap-based approaches to shape coding are investigated using one-dimensional weighted finite automata (1D-WFA) and generalised finite automata (GFA) algorithms, respectively. We evaluate the fidelity of shape representation, using 1D-WFA and GFA methods in intraframe mode and compare the performance of the proposed coding techniques against each other and with the benchmark, context-based arithmetic encoding (CAE) of shapes used in MPEG-4. It is found that the GFA method is more suitable for video applications than 1D-WFA and therefore it is adapted to operate in interframe mode. More importantly, GFA is the first shape-coding technique reported to date that has the unique advantage of shape processing in the compressed domain. This is due to the fact that the shape representation in the compressed domain using GFA facilitates processing at the expense of less compression efficiency compared with MPEG-4 CAE. Moreover, shapes encoded using the GFA method can be decoded at any desirable resolution     

Weighted finite automata for video compression

Weighted finite automata (WFA) exploit self-similarities within single pictures and also sequences of pictures to remove spatial and temporal redundancies. Their implementation then combines techniques from hierarchical methods related to quadtrees and from vector quantization to achieve performance results for low bit rates which can be put on a par with state-of-the-art codecs like embedded zero-tree wavelet coding. Due to their simple mathematical structure, WFA provide an ideal platform for efficient hybrid compression methods. Therefore, WFA were chosen as a starting point for a fractal-like video compression integrating a hierarchical motion compensation as well as an option to vary the compression quality between “centers of interest” and “background” in a flexible manner     

Implementation of Turing machines as finite automata

Logical systems are often represented using the Turing-machine concept. A design method is described whereby the normal transition tables for a Turing machine may be translated into a state table defining the control unit as a finite-state machine, and a special shift-register configuration in place of the computing tape. Design equations and circuits are given for a 4-state Turing machine embodying a 2-symbol alphabet.     

Entropy and expected acceptance counts for finite automata

If a sequence of independent unbiased random bits is fed into a finite automaton, it is straightforward to calculate the expected number of acceptances among the first n prefixes of the sequence. This paper deals with the situation in which the random bits are neither independent nor unbiased, but are nearly so. We show that, under suitable assumptions concerning the automaton, if the difference between the entropy of the first n bits and n converges to a constant exponentially fast, then the change in the expected number of acceptances also converges to a constant exponentially fast. We illustrate this result with a variety of examples in which numbers following the reciprocal distribution, which governs the significands of floating-point numbers, are recoded in the execution of various multiplication algorithms.     

基于多维有限自动机的DFA改进算法

多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA, multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1~2个数量级。     

Test for synchronizability of finite automata and variable length codes

A finite automation is called synchronizable ofNth order if the knowledge of the lastNoutputs suffices to determine the state of the automaton at one time during the lastNoutputs (including the initial and the final states). In an analogous manner synchronizability ofNth order is defined for variable length codes. The paper describes a test for synchronizability on a more general model, the coding graphs, and shows that finite automata and variable length codes are special cases of it.     

不完全确定序列机状态化简

本文指出完全确定序列机状态化简是不完全确定序列机状态化简的特殊情况，后者具有更普遍的意义，文中提出了不完全确定序列机状态化简。     

On testing simple hypotheses in finite time with Hellman-Cover automata

Asymptoticallyvarepsilon-optimal automata were developed by Hellman and Cover [4] for testing simple hypotheses concerning the parameter of an independent identically distributed sequence of Bernoulli random variables. These automata permit transitions only between adjacent states and employ artificial randomization only at extreme states. In this paper we study the problem of approximating the optimal Hellman-Cover automaton in fixed-sample-size problems. It is shown that the optimal level of the parameter, which regulates the probability of transitions out of an extreme state, tends to zero at the rateln n/nin symmetric testing problems wherenis the sample size. We develop an approximation for the optimal parameter value valid fornsufficiently large.     

有限状态机的VHDL设计及优化

有限状态机是数字系统中的重要组成部分。本文讨论了有限状态机的分类,给出了状态机各部分的VHDL的描述方法,并介绍了一种新的状态转移的描述风格(arrive-edges),最后讨论了状态机速度优化和容错技术。     

Minimization of the total loss rate for two finite queues in series

Two finite-capacity loss queues in series, with Poisson arrival at the first queue and with Erlang service time distribution at both queues are considered. It is assumed that the service rate at the second queue is held fixed and that a maximum buffer space is globally available. For this model, the problem of optimally choosing the service rate at the first queue and the buffer space distribution over the two queues is considered in order to minimize the steady-state total network loss rate. It is shown that a decrease of the service rate at the first queue can reduce the total network loss rate only if this lower service rate decreases the variability of the process feeding the second queue. Numerical results show that, when optimal values are assigned to the parameters of the model, a significant reduction of the network loss rate can be achieved, especially when the network load is moderate and when the service time distributions have a small variance     

Subband finite state scalar quantization

A new image-coding algorithm that exploits the relationship between various subbands of an image is presented in this correspondence. Using local variance for state selection and uniform threshold quantizers on subbands, we have achieved a reduction in quantization noise compared to other published techniques for Lena at various bit rates.     

基于有限状态机的雷达状态模型建立

现代雷达具有功能多特点.针对雷达系统控制,采用传统程序设计方法存在调试周期长,可移植性和可扩展性差的特点.本文采用有限状态机理论对雷达状态进行模型建立,根据状态机理论,通过仿真建立相应的状态切换模型,工程实践表明有限状态机能较好的进行雷达系统控制设计,系统可扩展性、可移植性较好.     

Compatible-invariant subset analysis of deterministic finite automata via semi-tensor product of matrices approach

The compatible-invariant subset of deterministic finite automata (DFA) is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product (STP) of matrices. The concepts of compatible-invariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA, and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile, by using the STP of matrices, a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset. Based on the concept of compatible feasible event matrix, an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally, an illustrative example is given to validate the results.     

Deadlock detection in communicating finite state machines by even reachability analysis

A network of communicating finite state machines (CFSM) consists of a set of finite state machines which communicate asynchronously with each other over (potentially) unbounded FIFO channels by sending and receiving typed messages. As a concurrency model, CFSMs has been widely used to specify and validate communications protocols. CFSMs is also powerful and suitable for modeling mobile communication systems – a CFSM can naturally model a mobile station in a wireless communication system. The unbounded FIFO channels are ideal for modeling the communication behavior among mobile stations. Fair reachability is a very useful technique in detecting errors of deadlocks and unspecified receptions in networks of (CFSMs) consisting of two machines. The paper extends the classical fair reachability technique, which is only applicable to the class of two-machine CFSMs, to the general class of CFSMs. For bounded CFSMs, the extended fair reachability technique reduces by more than one half the total number of reachable global states that have to be searched in verifying freedom from deadlocks. The usefulness of the new reachability technique, called even reachability, is demonstrated through two examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

小型化牵动下的硬盘技术

逐一分析了硬盘中的磁头、盘片等主要构件以及飞行高度发展至今的小型化过程,从而显示出当今硬盘技术发展的概貌;分析讨论了超顺磁效应,指出硬盘小型化要想继续下去必须另辟新路。     

State assignment of finite state machines for low powerapplications

The authors present an algorithm for the state assignment in finite state machines targeted for minimal switching power dissipation. The adjacent states are assigned codes closer in Hamming distance by our algorithm, which modifies the given state transition graph so that it can be embedded in an n-cube. Experimental results show that the switching activity obtained by the proposed method is better than the previous method     

Low power finite state machine synthesis using power-gating

Power-gating turns off the power supply of a portion of the circuit completely, resulting in total elimination of power consumption for that part. However, it also necessitates that the sub-circuit to be activated should be charged for some time before its activation. This critical issue can influence the decomposition of a finite state machine (FSM) for its power gated implementation. In this paper we have presented a power-gating method that integrates FSM partitioning with state encoding, thus providing a total solution to the problem of power-aware FSM synthesis. It shows better results, in terms of dynamic and leakage power consumption, compared to the existing techniques reported in the literature.