Structural decomposition as a tool for the optimization of an FPGA-based implementation of a mealy FSM

  • PDF / 126,116 Bytes
  • 10 Pages / 595.276 x 793.701 pts Page_size
  • 86 Downloads / 163 Views

DOWNLOAD

REPORT


STRUCTURAL DECOMPOSITION AS A TOOL FOR THE OPTIMIZATION OF AN FPGA-BASED IMPLEMENTATION OF A MEALY FSM A. A. Barkalov,a† L. A. Titarenko,a and A. A. Barkalov Jr. b

UDC 004.383.3

Abstract. Two models of logic circuits are proposed for the implementation of Mealy FSMs. The models are underlain by FPGAs with embedded memory blocks and are based on a transformation of object codes. To decrease the number of lookup table elements, it is proposed to decrease the number of irregular functions representing FSMs. An example of design and results of experiments are given for the proposed synthesis method based on the transformation of codes of collections of microoperations into state codes of FSMs. Keywords: microprogrammed Mealy FSM, FPGA, structural decomposition, embedded memory blocks. INTRODUCTION A model of a microprogrammed Mealy FSM (MFSM) [1] is frequently used for synthesizing control units [2]. The development of microelectronics has led to the creation of various families of erasable programmable logic devices (integrated schemes) or EPLDs [3, 4]. In synthesizing MFSM circuits on the basis of EPLDs, a number of optimization problems arise, and one of them lies in decreasing the number of EPLD macrocells in a logic circuit [5]. Methods for solving this problem depend on distinctive features of an FSM model, a control algorithm, and an element basis [6]. This article considers the problem of implementation of an MFSM on EPLDs of type FPGA (field-programmable gate array) [7, 8]. Such EPLDs consist of look-up table (LUT) elements and embedded memory blocks (EMBs). In what follows, by EPLDs we will understand FPGAs. We also will denote by LE (logical element) a LUT element and by EMB an embedded memory block. As a rule, LEs implement the truth table of an arbitrary Boolean function of 4–6 arguments [4]. This constraint leads to the necessity of functional decomposition [5] of systems of Boolean functions (SBFs) being implemented. In this case, a circuit assumes a multilevel character, which increases the duration of its clock cycle in the case of implementation of MFSMs on EPLDs. To decrease hardware expenditures, it is expedient to use the structural decomposition method [6] based on the increase in the number of structural levels of an MFSM circuit. In this work, a method is considered that consists of encoding some MFSM objects (for example, collections of microoperations) and their subsequent decoding using EMBs. This leads to a balanced use of EPLD resources (LEs and EMBs) and also to a decrease in the crystal portion occupied by an MFSM circuit [9]. This article considers methods for structural decomposition of MFSM circuits that is based on the method for transformation of objects [10]. These methods are adapted to distinctive features of EPLDs with embedded memory blocks. 1. FUNDAMENTALS A microprogrammed Mealy FSM is represented by the following vector [1]: S = á X , Y , A , d, l , a1 ñ ,

(1)

a

University of Zielona GËra, Zielona GËra, Poland, †[email protected]. b“Nokia-Siemens Networks” compa