Máquinas de estados finitos con multiplexión de entradasuna contribución al diseño e implementación electrónica de máquinas de estados

Resumen

Esta tesis doctoral supone una contribución a la implementación electrónica de máquinas de estados finitos, en particular a la implementación mediante arquitecturas basadas en memoria. En los últimos años se ha observado un creciente interés por este tipo de arquitecturas debido principalmente al elevado número de recursos de memoria disponibles en los nuevos dispositivos FPGA. El estudio realizado tiene como objetivo mejorar las prestaciones de las implementaciones basadas en el modelo de Máquina de Estados Finitos con Multiplexión de Entradas (FSMIM, sigla del inglés Finite State Machine with Input Multiplexing), que permite aprovechar las indeterminaciones en las entradas de una máquina de estados para reducir el tamaño de la memoria requerida. Se ha propuesto una nueva arquitectura para la implementación de FSMIM que complementa a la arquitectura existente, ampliando el abanico de opciones de diseño para la implementación de máquinas de estados, lo que favorece el cumplimiento de las restricciones de diseño impuestas por la aplicación. Se han propuesto nuevos algoritmos para la generación de implementaciones de FSMIM a partir de máquinas de estados convencionales, que mejoran las prestaciones de dichas implementaciones tanto en velocidad como en consumo de recursos respecto a los algoritmos existentes. En este contexto, la contribución más importante ha sido modelar uno de los problemas de optimización que surgen en el diseño de FSMIM, probar su NP-completitud y proporcionar una formulación basada en programación lineal entera para resolverlo. Se ha realizado un estudio experimental en el que se analiza tanto el consumo de recursos como la velocidad de las implementaciones de FSMIM y de las implementaciones convencionales de máquinas de estado en dispositivos FPGA. Este estudio ha probado que las técnicas presentadas consiguen mejorar las prestaciones de las implementaciones de FSMIM. Por otra parte, respecto a las implementaciones convencionales de máquinas de estados, el estudio ha puesto de manifiesto que las implementaciones de FSMIM constituyen una alternativa viable a las implementaciones basadas en celdas lógicas y que presentan mayor velocidad y menor consumo de recursos que las basadas exclusivamente en bloques de memoria empotrados.