Search

Modern digital systems can be viewed as compositions of combinational and sequential blocks. In the article, we discuss a case when sequential blocks are represented using a model of Mealy finite-state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and power consumption. This article proposes a novel design method which allows diminishing the number of look-up table (LUTs) and increasing the operating frequency of multilevel LUT-based Mealy FSMs. The method is based on simultaneous use of such methods of structural decomposition as the transformation of states into FSM outputs and twofold state encoding. The proposed method results in three-level logic circuits of Mealy FSMs with regular systems of interconnections. Each function for any level of logic is implemented using a single LUT. An example of FSM synthesis with the proposed method is given. The experiments with standard benchmarks were conducted. The results of experiments show that the proposed approach leads to decreasing LUT counts from 11.9% to 62.6%. Also, it leads to increasing the operating frequency from 11.77% to 18.43% on average compared with other investigated approaches (Auto and One-hot of Vivado, JEDI, and replacement of FSM inputs and encoding the collections of outputs). The economy in used LUTs and gain in operating frequency grow with the growth of the FSM complexity. [ABSTRACT FROM AUTHOR]

A method is proposed for optimizing circuits of sequential devices which are used in cyber-physical systems (CPSs) implemented using field programmable gate arrays (FPGAs). The optimizing hardware is a very important problem connected with implementing digital parts of CPSs. In this article, we discuss a case when Mealy finite state machines (FSMs) represent behaviour of sequential devices. The proposed method is aimed at optimization of FSM circuits implemented with look-up table (LUT) elements of FPGA chip. The method aims to reduce the LUT count of Mealy FSMs with extended state codes. The method is based on finding a partition of the set of internal states by classes of compatible states. To reduce LUT count, we propose a special kind of state codes named composite state codes. The composite codes include two parts. The first part includes the binary codes of states as elements of some partition class. The second part consists of the code of corresponding partition class. Using composite state codes allows us to obtain FPGA-based FSM circuits with exactly two levels of logic. If some conditions hold, then any FSM function from the first level is implemented by a single LUT. The second level is represented as a network of multiplexers. Each multiplexer generates either an FSM output or input memory function. An example of synthesis is shown. The experiments prove that the proposed approach allows us to reduce hardware compared with two methods from Vivado, JEDI-based FSMs, and extended state assignment. Depending on the complexity of an FSM, the LUT count is reduced on average from 15.46 to 68.59 percent. The advantages of the proposed approach grow with the growth of FSM complexness. An additional positive effect of the proposed method is a decrease in the latency time. [ABSTRACT FROM AUTHOR]

Very often, a digital system includes sequential blocks which can be represented using a model of the finite state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and consumed energy. The paper proposes a novel technology-dependant design method targeting LUT-based Mealy FSMs. It belongs to the group of structural decomposition methods. The method is based on encoding the product terms of Boolean functions representing the FSM circuit. To diminish the number of LUTs, a partition of the set of internal states is constructed. It leads to three-level logic circuits of Mealy FSMs. Each function from the first level requires only a single LUT to be implemented. The method of constructing the partition with the minimum amount of classes is proposed. There is given an example of FSM synthesis with the proposed method. The experiments with standard benchmarks were conducted. They show that the proposed method can improve such FSM characteristics as the number of used LUTs. This improvement is accompanied by a decrease in performance. A positive side effect of the proposed method is a reduction in power consumption compared with FSMs obtained with other design methods. [ABSTRACT FROM AUTHOR]

A method is proposed targeting the decrease of the number of look-up tables (LUTs) in logic circuits of field programmable gate arrays (FPGA)-based Mealy finite state machines. The method is based on constructing a partition for the set of output variables. It diminishes the number of additional variables encoding the collections of output variables (COVs). A formal method is proposed for finding the partition. An example of synthesis is given, as well as the results of investigations. The investigations were conducted for standard benchmarks. [ABSTRACT FROM AUTHOR]

The complexity of algorithms implemented in digital systems grows. Methods are developed for most effective use of both hardware resources and energy. For engineers the problem of hardware resources optimization in design of control units is still an important issue. The standard way of implementing the control unit as a finite-state machine (FSM) is not satisfactory as it consumes considerable amounts of field-programmable gate arrays (FPGA) resources. This paper is devoted to the design of a Moore FSM in FPGA structure using look-up tables and embedded memory blocks (EMB) elements. The problem background is discussed. The method of the design of Moore FSM logic circuits with EMB based on splitting the set of logical conditions and the encoding of logical conditions is presented. Examples of design and research results are given. [ABSTRACT FROM AUTHOR]

A new two-stage method of finite state machines (FSMs) synthesis for PAL-based complex programmable logic devices (CPLD) is proposed. It is based on both the wide fan-in of PAL cells and existence of the classes of pseudoequivalent states of Moore FSM. The first step targets decreasing for the number of PAL cells used for implementing the block of input memory functions. The second step targets decreasing for the number of PAL cells in the block of microoperations. An example of application of the proposed method is given, as well as results of experiments carried out for standard benchmarks. [ABSTRACT FROM AUTHOR]

The methods are proposed targeting to reduce the numbers of both look-up table elements and embedded memory blocks in the logic circuit of a Moore finite state machine. The proposed methods are based on binary encoding of both classes of pseudoequivalent states and collections of microoperations. Examples of synthesis and results of investigations are given. [ABSTRACT FROM AUTHOR]