Optimization of state assignment in a finite state machine

evaluation of a simulated annealing approach

Autores

  • Reinaldo da Silva Ribeiro UFT - Universidade Federal do Tocantins
  • Rafael Lima de Carvalho Universidade Federal do Tocantins
  • Tiago da Silva Almeida Universidade Federal do Tocantins https://orcid.org/0000-0002-0420-4188

DOI:

https://doi.org/10.20873/uft.2675-3588.2022.v3n1.p9-16

Palavras-chave:

Máquinas de Estados FInitos, Resfriamento Simulado, Sistemas Digitais, Meta-heuristica

Resumo

In this research, the application of the Simulated Annealing algorithm to solve the state assignment problem in finite state machines is investigated. The state assignment is a classic NP-Complete problem in digital systems design and impacts directly on both area and power costs as well as on the design time. The solutions found in the literature uses population-based methods that consume additional computer resources. The Simulated Annealing algorithm has been chosen because it does not use populations while seeking a solution. Therefore, the objective of this research is to evaluate the impact on the quality of the solution when using the Simulated Annealing approach. The proposed solution is evaluated using the LGSynth89 benchmark and compared with other approaches in the state-of-the-art. The experimental simulations point out an average loss in solution quality of 11%, while an average processing performance of 86%. The results indicate that it is possible to have few quality losses with a significant increase in processing performance.

Biografia do Autor

Rafael Lima de Carvalho, Universidade Federal do Tocantins

Possui graduação em Ciência da Computação pela Universidade Federal do Tocantins (2006), mestrado em Sistemas e Computação pelo Instituto Militar de Engenharia (2008) e doutorado em Engenharia de Sistemas e Computação pela Universidade Federal do Rio de Janeiro (2016). Atualmente é professor adjunto da Universidade Federal do Tocantins, curso de ciência da computação. Tem experiência na área de Ciência da Computação, com ênfase em Inteligência Computacional, atuando principalmente nos seguintes temas: tracker, weightless neural networks, problema de conectividade dinâmica, aprendizado de máquina.

Tiago da Silva Almeida, Universidade Federal do Tocantins

Possui graduação em Sistemas de Informação pelo Centro Universitário de Jales (2007) e mestrado em Engenharia Elétrica pela Universidade Estadual Paulista Júlio de Mesquita Filho (2009). Atualmente é professor Assistente I da Universidade Federal do Tocantins. Tem experiência na área de Engenharia Elétrica, com ênfase em Circuitos Eletrônicos.

v3 n1

Downloads

Publicado

2021-12-01

Como Citar

[1]
da Silva Ribeiro, R. et al. 2021. Optimization of state assignment in a finite state machine: evaluation of a simulated annealing approach. Academic Journal on Computing, Engineering and Applied Mathematics. 3, 1 (dez. 2021), 9–16. DOI:https://doi.org/10.20873/uft.2675-3588.2022.v3n1.p9-16.

Edição

v. 3 n. 1 (2022)

Seção

Artigos de Pesquisa

Categorias

Licença

Copyright (c) 2021 Reinaldo da Silva Ribeiro, Rafael Lima de Carvalho, Tiago da Silva Almeida

Creative Commons License

Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.

Autores que publicam neste periódico concordam com os seguintes termos:

  1. Autores mantém os direitos autorais e concedem ao periódico o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial neste periódico;
  2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial neste periódico;
  3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto posterior ao processo editorial;
  4. Além disso, o AUTOR é informado e consente com o periódico que, portanto, seu artigo pode ser incorporado pela Academic Journal on Computing, Engineering and Applied Mathematics em bases e sistemas de informação científica existentes (indexadores e bancos de dados atuais) ou a existir no futuro (indexadores e bancos de dados futuros), nas condições definidas por este último em todos os momentos, que envolverá, pelo menos, a possibilidade de que os titulares desses bancos de dados possam executar as seguintes ações sobre o artigo:
    1. Reproduzir, transmitir e distribuir o artigo, no todo ou em parte sob qualquer forma ou meio de transmissão eletrônica existente ou desenvolvida no futuro, incluindo a transmissão eletrônica para fins de pesquisa, visualização e impressão;
    2. Reproduzir e distribuir, no todo ou em parte, o artigo na impressão;
    3. Traduzir certas partes do artigo;
    4. Extrair figuras, tabelas, ilustrações e outros objetos gráficos e capturar metadados, legendas e artigo relacionado para fins de pesquisa, visualização e impressão;
    5. Transmissão, distribuição e reprodução por agentes ou autorizada pelos proprietários de distribuidoras de bases de dados;
    6. A preparação de citações bibliográficas, sumários e índices e referências de captura relacionados de partes selecionadas do artigo;
    7. Digitalizar e / ou armazenar imagens e texto de artigo eletrônico.