Una aproximación al diseño óptimo de máquinas de estados finitos

Abstract

En los Capítulos 2 y 3 se aborda el diseño lógico FSMs. En el primero de ellos estudiamos el problema de la reducción del número de estados en máquinas incompletamente especificadas, recogemos el estado del arte del problema, con la redefinición de objetivos y criterios de coste con que se aborda en un entorno automatizado de diseño VLSI, y describimos dos algoritmos heurísticos de minimización de FSMs, que hemos desarrollado siguiendo dos estrategias de optimización diferentes. En el Capítulo 3 describimos un algoritmo de reducción y asignamiento de estados simultáneo, que supone una aproximación conceptualmente novedosa para abordar la síntesis de FSMs. En el Capítulo 4 analizamos en profundidad la relación entre el asignamiento de estados y la testabilidad de la FSM, proponiendo una arquitectura para testabilidad que garantiza el que todos los fallos simples combinacionalmente irredundantes, en el PLA que implementa la componente combinacional, sean testables en el circuito secuencial. Por último, en el Capítulo 5 describimos dos algoritmos de generación de patrones de test para las FSMs que incorporan nuestro esquema de testabilidad.