---

Contents

Introduction
The purpose and problems of work
Prospective scientific novelty
Planned practical value
The review of existing developments on a theme
Current and planned results
Conclusion
The list of sources

---

Introduction

The major part of any digital device is the finite state machine (FSM). In practice FSM often realize in the form of the automatic device with rigid logic. The algorithms of operating device management, being raw data's for syntheses of the scheme FSM, are assigned, as a rule, in the manner of earl-schemes, which differ the big amount of the features. Recently even more often for realization of the schemes FSM are used different programmed logical integral schemes (PLIS), which possess the high cost and difficulty. [1]

At present in practice possible realization of complex digital devices on several, or even to one LSI. It is connected with observable for the last thirty years there was an explosive growth of density of integrations of schemes that allows to release the schemes, which contains on one crystal millions logic gates. LSI possible to divide into two classes: standard LSI and specialized LSI. To the first class refer the microcircuits to memory, alarm processors and etc. Beside second-class select several subclasses: completely custom-mode, semicustom and an programmed by user.

At present are broadly used three classes PLIS: simple PLIS (the foreign term SPLD - simple programmable logic device), complex PLIS (the foreign term CPLD - complex programmable logic device) and programmed by user valve matrixes (the foreign term FPGA - field programmable gate array). Two subclasses select In class SPLD: programmed logical matrixes (PLM, foreign term PLAs - programmable logic arrays) and programmed matrixes of the logic (PML, foreign term PALs - programmable array logics). SPLD consist of two matrixes: matrixes "And" and matrixes "OR". In PLM both matrixes programmed, but in PML - a matrix "OR" fixed. CPLD consist of block of the logical gates, incorporated by a programmed switching matrix. Modern CPLD, as a rule, are electrically reprogrammed and save logic structure after disconnected of a feed. FPGA consist of the big number of configured logic block (the foreign term LUT) and the routemaking resources, providing their interconnections. Leading developers of microcircuits CPLD and FPGA are firms Xilinx, Altera, Atmel, Lattice Semiconductor, Cypress Semiconductor. [2]

Recently two tendencies are observed: simultaneous increase in complexity of developed digital devices and increase of computing capacity, flexibility of hardware decisions. These tendencies have brought about appearance in principal new facilities of the designing - a systems computer aided design (CAD). At first, they simulated manual development of hardware device by the engineer, with appearance of the microcircuits of class FPGA hereinafter and mass release of PLIS appeared the first description languages of the equipment and CAD with their support (in 80 - 90 years of XX century).

---

The purpose and problems of work

• analysis of the modern element base and existing methods of the syntheses FSM on PLD for determination of the ways of the reduction of the cost of the logical schemes FSM;

• development of four level structures FSM and method of the syntheses, oriented on reduction hardware expenseses in logical scheme;

• estimation to difficulties to realization of the under development structure and study for the reason determinations of the areas her efficient using;

• software development, supporting realization of the divined method of the syntheses FSM.

---

Prospective scientific novelty

Scientific novelty given functioning is concluded in:

• study given layered structure of FSM and methods of the syntheses, directed on reduction of hardware expenseses in logical scheme by way of the complex using the change logical variable, maximum coding set microoperations;

• determination to regularities of the change to efficiency to realization of the designed structure depending on features earl-schemes of the algorithm;

• qualification of the area of the efficient using the under development structure;

• development CAD, supporting realization of the divined method of the syntheses FSM.

---

Planned practical value

Planned practical value consists in development and study of the layered structure of FSM with rigid logic in base PLD, in logical scheme which the expenses of hardware are reduced in comparison with traditional structure. Under development software will possible use in educational process for the reason education student on corresponding to course.

---

The review of existing developments on a theme

At our time for the description of logic structure of digital devices, as a rule, are used high-level languages of the description of the equipment (Hardware Description Languages - HDL). The most widespread among them are languages VHDL and Verilog. However in composition many foreign CAD are enclosed special tools, allowing to simplify development of FSM since direct realization of FSM in these languages is labour-intensive process. So module FSM is included in structure CAD Active - HDL firms Aldec. He possesses the multifunctional graphic interface for the description of FSM, however form record of FSM requires the knowledges of the language HDL, also in this module is absence of many optimization of structure of the got automatic devices.

My work is dedicated to actual task of the method study of the syntheses of the structures of FSM with rigid logic, which are oriented on reduction of the cost of the logical scheme device and take into account the typical particularities of the realized algorithm of control and element base. As FSM with rigid logic is chose Mealy machine and as structures of FSM – four level structure MPFY- automaton, which at our time not it is enough explored.

The optimization of the scheme Mealy FSM can be executed by reduction both numbers input, and numbers output, as well as together. Such complex approach generates the layered structures of FSM. In MPFY- automaton optimization is executed by change input variable (MP), coding the lines of the direct structured table (the tables transition) (PF) and coding set microoperations (FY). The structure of operation MPFY- automaton is shown in figure 1. M-subcircuit is realized on multiplexer, P-subcircuit - on PLIS (PAL and CPLD), F-subcircuit and Y-subcircuit - on element of the memories PROM.

Figure 1. Structure of operation MPFY-automaton Mealy machine (animation, 5 frames, 1.4 k/s , 6 repetitions, 44 Kbytes)

Are known, however, and other methods of optimization of structure of automatic devices on PLIS. Classification of these methods [1] is resulted in figure 2.

Figure 2. Classification of methods of optimization of automatic devices

However recently appearance new, more high-speed and containing greater amount logical cell on microcircuits FPGA displaces a priority by development of devices with minimization of hardware expenses in the received device or maximizations of speed of the received device on maintenance of reliability and excellent job of the receive device at as much as possible short cycle to development. One of the ways of the decision of this problem is a draft on funds, means based on earlier developed means of designing complex systems for the software such as used of operated by architecture models (MDA - Model - Driven Architecture) and the unified language of modeling (UML - Unified Modeling Language).

---

Current and planned results

On the first stage of the functioning on master job by functioning was an explored method to optimization of four level structures FSM, named in literature MPFY- automaton. In process of the syntheses of automatic devices are used several methods to optimization in complex: structured reduction, algorithmic transformations. [4] Method of the syntheses of Mealy machine with MPFY-structure includes following stages:

• shaping the table of the change variables;

• optimum coding the conditions of the automaton;

• maximum coding of microoperations;

• syntheses of the logical scheme device.

Hereinafter, the estimation was organized to difficulties to realization of the under development structure and study for the reason determinations of the areas her efficient using. The methods of the study is concluded in following:

• output molded for reception analytical estimation area of the divined structure FSM;

• determination and study to relative difficulty to realization of the divined structure.

The studies were conducted on the grounds of molded for given of FSM with use the program EXCEL package MS Office. There were are received ensemble graph, showing dependency of the change the cost and relative difficulty to realization of the divined structure from different parameter earl-schemes of the algorithm (the numbers of the tops in GSA, numbers of microoperations and etc.).

Is it hereinafter expected development of the programmed product, which will allow to synthesize the divined automaton in base standard LSI for realization earl-schemes different deskside. Given CAD on result of its functioning will form VHDL-code of the program, by means of which will possible be a most further study of the divined structure FSM in ambience Active-HDL. Input given for CAD will be a text file with the main feature under investigation earl-schemes of algorithm. Structure of the under development programmed product is resulted in figure 3.

Figure 3. Structure under development CAD

Also within the framework of given master job is expected on base all done studies to do the findings about practicability of the using the givened structure FSM for different earl-schemes algorithm, reveal the defect and value MPFY- automaton in comparison with the other structure Mealy FSM (two-level and etc.).

---

Conclusion

Result of job will be a reception of the layered structure of FSM with rigid logic in base PLD, in logical scheme which hardware of the expenses are reduced in comparison with traditional structure. Designed software will realize the givenned method of the syntheses of FSM and generation of the code on language HDL. The programmed code will is generated with provision for given algorithm to optimization of FSM. Input given for CAD will be a text file with the main feature under investigation earl-scheme algorithm.

---

The list of sources

1. А.А. Баркалов Синтез устройств управления на программируемых логических устройствах. - Донецк. 2002.

2. В.В. Соловьев. Проектирование цифровых систем на основе программируемых логических интегральных схем. - Москва. 2001.

3. В.М. Карпов. Теория автоматов. СПб. Питер. 2002.

4. И.Я. Зеленева - "Методы синтеза многоуровневых структур управляющих автоматов на программируемых логических устройствах" - диссертационная работа.

5. Е.В. Малюк "Исследование четырехуровневой структуры управляющего автомата Мили в базисе стандартных БИС"

---

At a writing of the given author's abstract master job is not completed yet. Final end: January 2008. The full text of job and all materials on a subject can be received at the author or the head after the specified date.