RUS | ENG | Main | DonNTU> Master's portal
Donetsk National Technical University Vypritskaya Polina Alexandrovna

Vypritskaya Polina Alexandrovna

Faculty: Computer Science and Informatics

Speciality: System Programming

Theme of master's work:

Automatisation of Mealy automaton synthesis on FPGA

Leader of work: Krasichkov A. A.

Materials on the theme of master's work: Abstract

Abstract

Introduction

Now there is an automation of processes in all knowledge spheres of the environment world. In some areas of application this automation is reduced to software creation for the personal computer, but in most cases it requires the specialized computers creation. As it is visible from figure 1, the specialized computer consists of two basic parts: the Control Unit (CU) and Operational Automaton (OA). The CU functions forms the control signals on the basis of some algorithm for OA.

Figure 1. The generalize structure of the specialized computer.

The control algorithm of system sets by control code acting in CU from external environment. The control algorithm of OA is called microprogram and is realized by the control unit device. One of the basis problems at creation of the specialized computer is the search of the compromise between speed, cost and universality of CU. Also the time of designing and realization of the CU circuit is important.

Actuality

Now as hardware basis the wide spectrum of the Programmed Logic Integrated Circuit (PLIC) is used for creation of digital systems. This basis finds a use in systems of computer facilities and digital automatics, allowing considerably to increase such characteristics of devices, as reliability, speed, integration scale. The opportunity of programming of internal PLIC structure allows to build reconfigurable systems.

CU with hardware logic is known to win on speed in front of control units with programmable logic, but have hard structure and can not be changed. PLIC allow to replace all configured devices in a microcircuit. Thus, there is in opportunity to create reprogrammable CU with hard logic.

One of CU disadvantages with hardware logic is the labour input of designing. The System of the Automated Designing (SAD) can decrease human expenses at CU creation.

In resent researches 4 architectures of the Mealy CU on the counter for realization in FPGA basis were offered: PC1R1, PC1R2, PC1R3, PC1R4. First at synthesis of such structures of the control unit’s is the flow-chart (example of flow-chart on fig.2) on Linear Sequences of States (LSS). These splittings are various also it is accepted to name them LSS1, LSS2, LSS3, LSS4 accordingly.

Figure 2. Example of flow-chart.

From the theoretical point of view the structure PC1R1 differs by speed and hardware expenses from the Mealy control unit on a register and its further researches are inexpedient. In the SAD the three other architectures of Mealy CU will be implemented.

The purpose and tasks

The purpose of work is the Mealy CU synthesis for the subsequent realization on PLIS wish FPGA architecture and their characteristics research.

Basis research problems. For achievement of an object in view during researches it is necessary:
1. To analyze existing Mealy CU structures and to specify most suitable for the subsequent realization in FPGA basis.
2. To develop the stage algorithms of Mealy CU synthesis.
3. To develop SAD of Mealy CU.
4. To investigate by the developed SAD the time of Mealy CU designing, dependence between optimum structure of the CU and initial flow-chart characteristics.

Methods of researches. During researches were used and will be used further: the vehicle of the theory of finite automata, theory of sets, Boolean algebra and applied combinatory, theory of chances and theory of the graphs.

Prospective scientific novelty

is determined by the following positions:
1. Algorithm of flow-chart splitting on LSS4 for Mealy CU realization on the counter of architecture PC1R1.
2. Algorithm of flow-chart splitting on LSS2 for Mealy CU realization on the counter of architecture PC1R2 with use splitting on LSS4.
3. Proof of algorithm applicability of splitting on LSS2 to transposed flow-chart for the subsequent realization of CU architecture PC1R3.

Prospective practical importance of results

During the Mealy CU SAD creation some researches with its help are supposed. Further SAD usage is possible on several directions: continuation of scientific researches, usage in educational process, usage for real digital device designing, further completion and usage in systems of the decision of adaptive tasks.

Works of masters of the last years

  1. Borovlev Artem Sergeevich
    "Automated design of the Moora FSM in FPGA with objects' codes transformation"
  2. Siluanov Anton
    "Automated designe of the Mealy FSM in FPGA with objects transformation"
  3. Tsololo Sergey Aleksey
    "FPGA control units synthesis methods research"
  4. Berezhok alexey Jurievich
    "Research of structures of managing automatons with simplification of linear sequence of states"
  5. Voytenko Sergiy Arkadiyovich
    "Use UML in designing finite state machines"
  6. Danilov Maxim Vasilievich
    "Development and researches of system of the automated designing of composite microprogram devices of management"
  7. Kostyanok Tat'yana Nikolaevna
    "The development of methods synthesis of microprogram automatic devices Mealy with coding objects"
  8. Maria Krasnokutskaya
    "Research on a data structures in partition problems of large size graphs"
  9. Shepel Alexey Igorevich
    "Algorithms research of graph partition"
  10. Shishko Sergey
    "Development and research of compositional micro-program control devices"
  11. Lavrik Alexandr Srgeevich
    "Syntethys and researching CMCD with modificated system of microcomands on PLD"
  12. Maluk Zhenya Vyacheslavovich
    "Study of four level circuits of Mealy state machines in the basis of standard LSI circuit"
  13. Yakubovskyy Andrey Vjacheslavovich
    "Operating automatic devices with rigid logic on PLIS"
  14. Aniskin Sergey Vadimovich
    "Development of methods for decomposition of algorithm for realization in systems on chip"
  15. Miroshkin Aleksandr Nikolayevich
    "Synthesys and researching of composed microprogram control units with base architecture on PLD"

Sources

  1. Баркалов А. А. Синтез устройств управления на программируемых логических устройствах. – Донецк: ДонНТУ, 2002
  2. Баркалов А. А., Саломатин В.А., Красичков А.А. Синтез микропрограммного устройства управления со статической реконфигурацией. Наукові праці ДонДТУ. Серія "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 29
  3. Баркалов А.А., Зеленева И.Я., Красичков А.А. Оптимизация схем микропрограммных автоматов на счетчиках. Машиностроение и техносфера XXI века // Сборник трудов Международной научно-технической конференции в г. Севастополе 9-15 сентября 2002г. – Донецк: ДонНТУ, 2002
  4. Баркалов А.А., Ковалев С.А., Красичков А.А. Оптимизация логической схемы автомата Мили на программируемых логических устройствах и счетчиках. Тре-тий международный научно-практический семинар «Практика и перспективы развития институционного партнерства» ( 4-5 июня 2002г., Таганрог - на базе ТРТУ) В 2-х кн. Таганрог. Изд-во ТРТУ. Кн.1. 2002, №2
  5. Красичков А.А. Синтез микропрограммных автоматов на FPGA. Наукові праці ДонНТУ. Серія: “Обчислювальна техніка та інформатика”. Випуск 64. – Донецьк: Вид-во ДонНТУ, 2003
  6. Красичков А.А. Методы синтеза управляющих автоматов на конфигурируемых логических блоках. Диссертация … канд. техн. наук: 05.13.13 – Донецк: ДонНТУ, 2004

DonNTU> Master's portal | Abstract