La máquina de estados algorítmica ( 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, [1] introducido e implementado en Hewlett-Packard en 1968, formalizado y ampliado desde 1967 y escrito por Christopher R. Clare desde 1970. [2] [3] [4] Se utiliza para representar diagramas de circuitos integrados digitales . El diagrama ASM es como un diagrama de estados pero más estructurado y, por lo tanto, más fácil de entender. Un diagrama ASM es un método para describir las operaciones secuenciales de un sistema digital.
El método ASM se compone de los siguientes pasos:
Un diagrama 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 una 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 rombo indica que se debe probar la condición/expresión indicada y que se debe elegir la ruta de salida 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 rombo con una entrada y dos salidas (para verdadero y falso), se utiliza para realizar una transferencia condicional 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 indicada que se debe probar, la expresión contiene una o más entradas de la FSM.
Cuadro de salida condicional : un óvalo indica las señales de salida que son de tipo Mealy . Estas salidas dependen no solo del estado sino también de las entradas al FSM.
Una vez que se ha descrito la operación deseada de un circuito utilizando 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 se puede implementar como un registro simple, un registro de desplazamiento, un contador o un registro precedido por un bloque de lógica 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 de lógica combinacional.
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.
El segundo taller anual IEEE sobre microprocesadores (ahora llamado Taller de microcomputadoras Asilomar o AMW) se llevó a cabo del miércoles 28 al viernes 30 de abril de 1976, cerca de Monterey, California […] Mi charla del miércoles por la noche describía herramientas que permitían una metodología de diseño muy diferente (diseño de máquina de estados algorítmicos [ASM]) utilizando matemáticas de variables de estado
de Lyapunov
y técnicas derivadas iniciadas en
HP
por Chris Clare y Dave Cochran para las
calculadoras científicas
portátiles de espectacular éxito (por ejemplo,
HP 35
) […] Mi punto: el diseño de circuitos ya no era un problema de elemento por elemento, sino una cuestión de "flujo de estados" en muchos nodos (las "palabras" secuenciales de registros en lugar de los voltajes de los pines del dispositivo). En efecto, sostenía que los voltajes electrónicos, ya fueran analógicos o conmutados, "perderían" frente a las instrucciones de software y los "estados de datos". Los sistemas se diseñarían y analizarían para una secuencia de estados adecuada en lugar de una distorsión de señal analógica o tiempos de conmutación digitales. […] Ya había visto el poder de
los libros previos a su publicación
. El perspicaz texto de metodología ASM de Clare,
Designing Logic Systems Using State Machines
, arrasó en la comunidad de diseño de HP […] Sin embargo, el departamento de ingeniería eléctrica de
Stanford
no se mostró tan optimista y canceló el curso de Clare en 1974, diciendo que "es un poco poco convencional" […] Stanford prefirió
las técnicas de minimización de Quine-McCluskey
. Apropiadamente,
el colega
de
Mead
en Caltech,
Ivan Sutherland,
preparó un artículo
en Scientific American
(1977) […] sobre el desafío que planteaba la microelectrónica a la teoría y la práctica de la computación, señalando que, dado que la mayor parte de la superficie de un chip estaba ocupada por "cables" (vías conductoras) en lugar de "componentes" (transistores), décadas de teoría de minimización en el diseño lógico se habían vuelto irrelevantes […]
(4 páginas)
[…] En su número de abril publicó una carta de RL Dineley que describe un método simple para tratar expresiones lógicas de producto de sumas . […] DA Huffman enseña un método aún más simple . Este método se basa en reconocer que la expresión booleana será cero cuando cualquiera de los factores en la forma de producto de sumas sea cero. Trazar ceros de factores en un diagrama de Veitch o un mapa de Karnaugh es tan fácil como localizar unos para una expresión de suma de productos . […] Para ilustrar, utilizando el ejemplo de Dineley (A+BC)(A+C): […] Los ceros resultantes de A+BC se ubicarán donde A y BC sean cero. Por lo tanto, ubicamos en el mapa la expresión A * BC (que es igual a A * B + A * C ). De manera similar, los ceros de A+C se ubican y se grafican en A * C . Con todos los ceros ubicados, el resto del mapa se puede llenar con unos. Uno puede ser un poco más formal y calcular algebraicamente el complemento lógico de la expresión en consideración y luego graficar ceros para esa expresión resultante. Sin embargo, en una representación simple de producto de sumas, los términos complementarios se pueden escribir por inspección; o los ceros se pueden graficar por inspección sin escribir la expresión completa […] "Reducción clásica que involucra variables de uso poco frecuente" 11 de octubre de 1968. Universidad de Santa Clara […] El trabajo del Sr. Osborne presenta una gran similitud con el que presenté en este artículo y, por lo tanto, sin duda será de interés para aquellos lectores que busquen más información. Entiendo que ha trabajado para aplicar la técnica de variables infrecuentes al diseño de redes secuenciales construidas a partir de Read Only Memory . Dado que aún no ha publicado nada sobre esta área, si los lectores desean información adicional, pueden escribir al Sr. Osborne a: […] Thomas E. Osborne […] Edificio 1U […] 1501 Page Mill Road […] Palo Alto, California […] Gracias por la oportunidad de publicar con usted. […] GW Schultz […] Central Data Systems, Inc. […] Sunnyvale, Calif.(1 página) (NB. El método de Osborne fue publicado posteriormente por Clare. [B] )
[…] Schultz [20] hizo una importante contribución a la adaptación de la teoría a la práctica; se basa en la comprensión básica del problema por parte del diseñador y le exige que identifique las " variables infrecuentes ". Definidas de manera vaga, estas variables no se relacionan con todos los estados internos, es decir, no son necesarias para definir cada estado. En esencia, las variables infrecuentes son relevantes solo para unos pocos (quizás uno o dos) estados o transiciones de estado. Schultz sugiere que el diseñador primero traduzca el problema verbal a un gráfico de transición de estado que se reduce. Los estados internos se codifican y luego se agrega información sobre las variables infrecuentes a las transiciones de estado apropiadas. Se realiza una "primera aproximación" a las ecuaciones de entrada de flip-flop , basándose únicamente en las variables frecuentes. Schultz demuestra cómo estas ecuaciones pueden modificarse posteriormente para incorporar transiciones controladas por las variables infrecuentes. En los ejemplos de Schultz, las variables infrecuentes son todas señales de entrada, pero esta idea también se aplica a las señales de las variables de estado internas que pueden considerarse "infrecuentes". En este caso, por ejemplo, una variable de estado interna infrecuente de un flip-flop puede ser establecida por una circunstancia particular y reiniciada en algún momento posterior. La salida del flip-flop puede ahora ser tratada como una variable de entrada infrecuente. […](ix+1+179+3 páginas)