Máquina de estados algorítmica

La máquina de estados algorítmicos (ASM) es un método para diseñar máquinas de estados finitos (FSM) desarrollado originalmente por Thomas E. Osborne en la Universidad de California, Berkeley (UCB) desde 1960, introducido e implementado en Hewlett-Packard en 1968, formalizado y ampliado desde 1967 y escrito por Christopher R. Clare desde 1970. Se utiliza para representar diagramas de circuitos integrados digitales. El diagrama ASM es como un diagrama de estado pero más estructurado y, por tanto, más fácil de entender. Un gráfico ASM es un método para describir las operaciones secuenciales de un sistema digital.

Método ASM

El método ASM se compone de los siguientes pasos:

1. Crear un algoritmo, utilizando pseudocódigo, para describir la operación deseada del dispositivo.

2. Convertir el pseudocódigo en un Gráfico ASM.

3. Diseño de datapath basado en el gráfico ASM.

4. Crear un ASM detallado basado en el datapath.

5. Diseño de lógica de control basado en el gráfico ASM detallado.

Gráfico ASM

Un gráfico ASM consta de una interconexión de cuatro tipos de elementos básicos: nombre de estado, cuadro de estado, cuadro de decisión y cuadro de salidas condicionales. Un estado ASM, representado como un rectángulo, corresponde a un estado de un diagrama de estados regular o máquina de estados finitos. Las salidas de tipo Moore se enumeran dentro del cuadro.

Nombre del estado: El nombre del estado se indica dentro del círculo y el círculo se coloca en la esquina superior izquierda o el nombre se coloca sin el círculo.

Cuadro de estado: La salida del estado se indica dentro del cuadro rectangular.

Cuadro de decisión: Un diamante indica que la condición/expresión indicada se debe probar y la ruta de salida se debe elegir en consecuencia. La expresión de condición contiene una o más entradas a la FSM (Máquina de estados finitos). Una verificación de condición de ASM, indicada por un diamante con una entrada y dos salidas (para verdadero y falso), se utiliza para transferir condicionalmente entre dos cuadros de estado, a otro cuadro de decisión o a un cuadro de salida condicional. El cuadro de decisión contiene la expresión de condición establecida que se va a probar, la expresión contiene una o más entradas del FSM.

Cuadro de salida condicional: un óvalo indica las señales de salida que son de tipo Mealy. Estos resultados dependen no sólo del estado sino también de los insumos al FSM.

Ruta de datos

Una vez que se ha descrito la operación deseada de un circuito usando operaciones RTL, se pueden derivar los componentes de la ruta de datos. Cada variable única a la que se le asigna un valor en el programa RTL se puede implementar como un registro. Dependiendo de la operación funcional realizada al asignar un valor a una variable, el registro para esa variable puede implementarse como un registro simple, un registro de desplazamiento, un contador o un registro precedido por un bloque lógico combinacional. El bloque de lógica combinacional asociado con un registro puede implementar un sumador, un restador, un multiplexor o algún otro tipo de función lógica combinacional.

Gráfico ASM detallado

Una vez diseñada la ruta de datos, el gráfico ASM se convierte en un gráfico ASM detallado. La notación RTL se reemplaza por señales definidas en la ruta de datos.