基于Verilog的有限状态机设计与优化

研究了不同的状态机编码(二进制、格雷码、独热码)和不同的状态机描述方式(one always,two always,three always)的优点和缺点,并分析了他们对有限状态机性能的影响.分别使用Xilinx ISE和Design Compiler对一个实例进行了综合,分析了其面积、速度和功耗的信息.结果表明,one always的写法需要被摒弃;two always的编码风格适合Moore型状态机;而three always的编码风格适合Mealy型状态机.同时也给出了适合不同设计的最优状态编码.     

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.     

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.     

Conformance testing of protocols specified as communicating finitestate machines-a guided random walk based approach

We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs     

Circuit Level Concurrent Error Detection in FSMs

Finite state machines (FSMs) are contained in many building blocks of digital electronic circuits. Such electronic circuits are prone to transient errors, caused e.g. by cosmic radiation, and to permanent errors. In this article, the authors give an overview of known error detection methods for FSMs. One method (dependent state encoding for dynamic error detection) is described in detail, as well as the problems arising when the method is applied to a practical example. Additionally, the authors propose a modification of the method above. For several benchmark circuits, this modification shows better results, compared to the state-of-the-art implementation.     

Efficient encoding of facsimile using an adaptive technique

Two binary encoding schemes which lead to bandwidth and power saving are proposed. The binary source is encoded into digrams, which then undergo certain restrictions prior to transmission. Resultant ambiguity at the decoder is avoided by predictive feedback at the encoder. The specific examples proposed belong to a wide class of such adaptive encoding schemes.     

Theoretical bounds for switching activity analysis in finite-statemachines

The objective of this paper is to provide lower and upper bounds for the switching activity on the state lines in finite state machines (FSMs). Using a Markov chain model for the behavior of the FSM states, we derive theoretical bounds for the average Hamming distance on the state lines which are valid irrespective of the state encoding used in the final implementation. Such lower and upper bounds, in addition to providing a target for any state assignment algorithm, can also be used as parameters in a high-level power model and thus provide an early indication about the performance limits of the target FSM     

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.     

Analysis and design of impulse signal generator based on current-mode excitation and transmission line resonator

Hierarchical temporal memory (HTM) is a neuromorphic algorithm that emulates sparsity, hierarchy and modularity resembling the working principles of neocortex. Feature encoding is an important step to create sparse binary patterns. This sparsity is introduced by the binary weights and random weight assignment in the initialization stage of the HTM. We propose the alternative deterministic method for the HTM initialization stage, which connects the HTM weights to the input data and preserves natural sparsity of the input information. Further, we introduce the hardware implementation of the deterministic approach and compare it to the traditional HTM and existing hardware implementation. We test the proposed approach on the face recognition problem and show that it outperforms the conventional HTM approach.     

A Novel Decimal Logarithmic Converter Based on First-Order Polynomial Approximation

This paper presents a decimal logarithmic converter based on the decimal first-order polynomial (linear) approximation algorithm. The proposed approach is mainly based on a look-up table, followed a decimal linear approximation step. Compared with a binary-based decimal linear approximation algorithm (Algorithm 1), the proposed algorithm (Algorithm 2) is error-free in the conversion between the decimal and the binary formats. The proposed architecture is implemented by the combinational logic in the binary coded decimal (BCD) encoding on Virtex5 XC5VLX110T FPGA. The results of the comparison show that the hardware performance of Algorithm 2 can run 2.15 times faster than Algorithm 1, with the expense of 1.14 times more area.     

Peak-to-mean power control and error correction for OFDMtransmission using Golay sequences and Reed-Muller codes

A coding scheme for OFDM transmission is proposed, exploiting a previously unrecognised connection between pairs of Golay complementary sequences and second-order Reed-Muller codes. The scheme solves the notorious problem of power control in OFDM systems by maintaining a peak-to-mean envelope power ratio of at most 3 dB while allowing simple encoding and decoding at high code rates for binary, quaternary or higher-phase signalling together with good error correction     

Optimization based on the minimum maximal k-partial-matching problem of finite states machines with input multiplexing

Design Automation for Embedded Systems - Finite State Machines with Input Multiplexing (FSMIMs) were proposed in previous work as a technique for efficient mapping Finite State Machines (FSMs) into...     

Design,evaluation and fault-tolerance analysis of stochastic FIR filters

Stochastic computing utilizes compact arithmetic circuits that can potentially lower the implementation cost in silicon area. In addition, stochastic computing provides inherent fault tolerance at the cost of a less efficient signal encoding. Finite impulse response (FIR) filters are key elements in digital signal processing (DSP) due to their linear phase-frequency response. In this article, we consider the problem of implementing FIR filters using the stochastic approach. Novel stochastic FIR filter designs based on multiplexers are proposed and compared to conventional binary designs implemented using Synopsys tools with a 28-nm cell library. Silicon area, power and maximum clock frequency are obtained to evaluate the throughput per area (TPA) and the energy per operation (EPO). For equivalent filtering performance, the stochastic FIR filters underperform in terms of TPA and EPO compared to the conventional binary design, although the stochastic design shows more graceful degradation in performance with a significant reduction in energy consumption. A detailed analysis is performed to evaluate the accuracy of stochastic FIR filters and to determine the required stochastic sequence length. The fault-tolerance of the stochastic design is compared with that of the binary circuit enhanced with triple modular redundancy (TMR). The stochastic designs are more reliable than the conventional binary design and its TMR implementation with unreliable voters, but they are less reliable than the binary TMR implementation when the voters are fault-free.     

MFLP: a low power encoding for on chip networks

Network on chip (NoC) has been proposed as an appropriate solution for today’s on-chip communication challenges. Power dissipation has become a key factor in the NoCs because of their shrinking sizes. In this paper, we propose a new encoding approach aimed at power reduction by decreasing the number of switching activities on the buses. This approach assigns the symbols to data word in such a way that the more frequent words are sent by less power consumption. This algorithm dedicates the symbols with less ones to high probability data and uses transition signaling to transmit data. The proposed method, unlike the existing low power encoding, does not rely on spatial redundancy and keeps the width of the bus constant. Experimental evaluations show that our approach reduces the power dissipation up to 46 % with 2.70, 0.51, and 15.43 % power, critical path and area overhead in the NoCs, respectively.     

STATE VERIFICATION FOR SYNCHRONOUS CIRCUITS

This paper presents the techniques of implicit traversing and state verification for sequential finite state machines(FSMs) based of on the state collapsing of state transition graph(STG). The problems of state designing are described. In order to achieve high state enumeration coverage, heuristic knowledge is proposed.     

Compaction-based concurrent error detection for digital circuits

We present a non-intrusive concurrent error detection (CED) method for combinational and sequential digital circuits. We analyze the optimal solution model and point out the limitations that prevent logic synthesis from yielding a minimal-cost monolithic CED implementation. We then propose a compaction-based alternative approach for restricted error models. The proposed method alleviates these limitations by decomposing the CED functionality into: compaction of the circuit outputs, prediction of the compacted responses, and comparison. We model the fault-free and erroneous responses as connected vertices in a graph and perform graph coloring in order to derive the compacted responses. The proposed method is first discussed within the context of combinational circuits, with zero detection latency, and subsequently extended to Finite State Machines (FSMs), with a constant detection latency of one clock cycle. Experimental results demonstrate that the proposed method achieves significant hardware reduction over duplication-based CED, while detecting all possible errors.     

Bus encoding for total power reduction using a leakage-aware buffer configuration

Power consumption, particularly runtime leakage, in long on-chip buses has grown to be an unacceptable portion of the total power budget due to heavy buffer insertion used to combat RC delays. In this paper, we propose a new bus encoding algorithm and circuit scheme for on-chip buses that eliminates capacitive crosstalk while simultaneously reducing total power. We utilize a buffer design approach with a selective use of high-threshold voltage transistors and couple this buffer design with a novel bus encoding scheme. The proposed encoding scheme significantly reduces total power by 26% and runtime leakage power by 42% while also eliminating capacitive crosstalk. In addition, the proposed encoding is specifically optimized to reduce the complexity of the encoding logic, allowing for a significant reduction in overhead which has not been considered in previous bus encoding work.     

Reconfigurable finite-state machine based IP lookup engine for high-speed router

Internet protocol (IP) address lookup is one of the major performance bottlenecks in high-end routers. This paper presents an architecture for an IP address lookup engine based on programmable finite-state machines (FSMs). The IP address lookup problem can be translated into the implementation of a large FSM. Our hardware engine is then used to implement this FSM using a structured approach, in which the large FSM is broken down into a set of smaller FSMs which are then mapped into reconfigurable hardware blocks. The design of our hardware engine is based on a regular and well structured architecture, which is easy to scale. Our simulation results demonstrate that the FSM based architecture can easily scale to wire speed performance at OC-192 rates. Unlike previous approaches, the performance of our architecture is not constrained by memory bandwidth and is, therefore, in principle scalable with very large scale integration technology.     

STG-BASED VERIFICATION AND TEST GENERATION

This paper presents the techniques of verification and Test Generation(TG) for sequential machines (Finite State Machines, FSMs) based on state traversing of State Transition Graph(STG). The problems of traversing, redundancy and transition fault model are identified. In order to achieve high fault coverage collapsing testing is proposed. Further, the heuristic knowledge for speeding up verification and TG are described.