Reducing the Number of Luts for Mealy FSMS with State Transformation
In many digital systems, various sequential blocks are used. This paper is devoted to the case where the model of a Mealy finite state machine (FSM) represents the behaviour of a sequential block. The chip area occupied by an FSM circuit is one of the most important characteristics used in logic syn...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2024-03-01
|
| Series: | International Journal of Applied Mathematics and Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.61822/amcs-2024-0012 |
| _version_ | 1827298355451002880 |
|---|---|
| author | Barkalov Alexander Titarenko Larysa Mielcarek Kamil |
| author_facet | Barkalov Alexander Titarenko Larysa Mielcarek Kamil |
| author_sort | Barkalov Alexander |
| collection | DOAJ |
| description | In many digital systems, various sequential blocks are used. This paper is devoted to the case where the model of a Mealy finite state machine (FSM) represents the behaviour of a sequential block. The chip area occupied by an FSM circuit is one of the most important characteristics used in logic synthesis. In this paper, a method is proposed which aims at reducing LUT counts for FPGA-based Mealy FSMs with transformation of state codes into FSM outputs. This is done using the combined state codes. Such an approach allows excluding a block of transformation of binary state codes into extended state codes. The proposed method leads to LUT-based Mealy FSM circuits having exactly three levels of logic blocks. Under certain conditions, each function for any logic level is represented by a circuit including a single LUT. The proposed approach is illustrated with an example of synthesis. The results of experiments conducted using standard benchmarks show that the proposed method produces LUT-based FSM circuits with significantly smaller LUT counts than is the case for circuits produced by other investigated methods (Auto and One-hot of Vivado, JEDI, and transformation of binary codes into extended state codes). The LUT count is decreased by an average of 17.96 to 91.8%. Moreover, if some conditions are met, the decrease in the LUT count is accompanied with a slight improvement in the operating frequency compared with circuits based on extended state codes. The advantages of the proposed method multiply with increasing the numbers of FSM inputs and states. |
| first_indexed | 2024-04-24T15:13:31Z |
| format | Article |
| id | doaj.art-2154bca1a41b4c008d8b929f5ab6a1d9 |
| institution | Directory Open Access Journal |
| issn | 2083-8492 |
| language | English |
| last_indexed | 2024-04-24T15:13:31Z |
| publishDate | 2024-03-01 |
| publisher | Sciendo |
| record_format | Article |
| series | International Journal of Applied Mathematics and Computer Science |
| spelling | doaj.art-2154bca1a41b4c008d8b929f5ab6a1d92024-04-02T09:29:58ZengSciendoInternational Journal of Applied Mathematics and Computer Science2083-84922024-03-0134116717810.61822/amcs-2024-0012Reducing the Number of Luts for Mealy FSMS with State TransformationBarkalov Alexander0Titarenko Larysa1Mielcarek Kamil2Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516Zielona Góra, PolandInstitute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516Zielona Góra, PolandInstitute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516Zielona Góra, PolandIn many digital systems, various sequential blocks are used. This paper is devoted to the case where the model of a Mealy finite state machine (FSM) represents the behaviour of a sequential block. The chip area occupied by an FSM circuit is one of the most important characteristics used in logic synthesis. In this paper, a method is proposed which aims at reducing LUT counts for FPGA-based Mealy FSMs with transformation of state codes into FSM outputs. This is done using the combined state codes. Such an approach allows excluding a block of transformation of binary state codes into extended state codes. The proposed method leads to LUT-based Mealy FSM circuits having exactly three levels of logic blocks. Under certain conditions, each function for any logic level is represented by a circuit including a single LUT. The proposed approach is illustrated with an example of synthesis. The results of experiments conducted using standard benchmarks show that the proposed method produces LUT-based FSM circuits with significantly smaller LUT counts than is the case for circuits produced by other investigated methods (Auto and One-hot of Vivado, JEDI, and transformation of binary codes into extended state codes). The LUT count is decreased by an average of 17.96 to 91.8%. Moreover, if some conditions are met, the decrease in the LUT count is accompanied with a slight improvement in the operating frequency compared with circuits based on extended state codes. The advantages of the proposed method multiply with increasing the numbers of FSM inputs and states.https://doi.org/10.61822/amcs-2024-0012mealy fsmfpgalutsynthesisextended state codescombined state codes |
| spellingShingle | Barkalov Alexander Titarenko Larysa Mielcarek Kamil Reducing the Number of Luts for Mealy FSMS with State Transformation International Journal of Applied Mathematics and Computer Science mealy fsm fpga lut synthesis extended state codes combined state codes |
| title | Reducing the Number of Luts for Mealy FSMS with State Transformation |
| title_full | Reducing the Number of Luts for Mealy FSMS with State Transformation |
| title_fullStr | Reducing the Number of Luts for Mealy FSMS with State Transformation |
| title_full_unstemmed | Reducing the Number of Luts for Mealy FSMS with State Transformation |
| title_short | Reducing the Number of Luts for Mealy FSMS with State Transformation |
| title_sort | reducing the number of luts for mealy fsms with state transformation |
| topic | mealy fsm fpga lut synthesis extended state codes combined state codes |
| url | https://doi.org/10.61822/amcs-2024-0012 |
| work_keys_str_mv | AT barkalovalexander reducingthenumberoflutsformealyfsmswithstatetransformation AT titarenkolarysa reducingthenumberoflutsformealyfsmswithstatetransformation AT mielcarekkamil reducingthenumberoflutsformealyfsmswithstatetransformation |