Máquina de estados algorítmica

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:

1. Cree un algoritmo, utilizando pseudocódigo , para describir el funcionamiento deseado del dispositivo.

2. Convierte el pseudocódigo en un gráfico ASM .

3. Diseñe la ruta de datos basándose en el gráfico ASM.

4. Cree un gráfico ASM detallado basado en la ruta de datos.

5. Diseñe la lógica de control basándose en el diagrama ASM detallado.

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.

• Diagrama de flujo
• Diagrama de Drakon
• Maquina harinosa
• Máquina de Moore
• Variables ingresadas en el mapa (MEV)

• Lee, Sunggu (2000) [1999]. Diseño de computadoras y otros dispositivos digitales complejos (1.ª ed.). Upper Saddle River, Nueva Jersey, EE. UU.: Prentice-Hall, Inc. ISBN 0-13-040267-2. LCCN  99-049967. ISBN 978-0-13040267-7 . (xiv+418 páginas)
• Lee, Sunggu (2000). Diseño de computadoras: un ejemplo de diseño lógico digital avanzado . Prentice-Hall .
• Lee, Sunggu (2006). Diseño lógico digital avanzado: uso de VHDL, máquinas de estado y síntesis para FPGA . Thomson. ISBN 0-534-46602-8.
• Brown, Stephen D.; Vranesic, Zvonko . Fundamentos de lógica digital con diseño VHDL (1.ª ed.).
  • Brown, Stephen D.; Vranesic, Zvonko (2004). Fundamentos de lógica digital con diseño VHDL (2.ª edición). McGraw Hill. ISBN 978-0-07-249938-4.
  • Brown, Stephen D.; Vranesic, Zvonko (2009). Fundamentos de lógica digital con diseño VHDL (3.ª edición). McGraw Hill. ISBN 978-0-07-352953-0.
• Bjørner, Dines (diciembre de 1970) [4 de mayo de 1970, 7 de abril de 1970, 4 de febrero de 1970]. "Máquinas de diagramas de flujo". BIT Numerical Mathematics . 10 (4). IBM Research Laboratory, San José, California: 415–442. doi :10.1007/BF01935563. S2CID  189767592. RJ-685 (n.º 13346).
• Lee, Samuel C. (1976). Circuitos digitales y diseño lógico . Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice-Hall .
• Santrakul, Krayim (1983). Diseño lógico LSI/VLSI de valores múltiples (PDF) (tesis doctoral). Universidad de Oklahoma. Archivado (PDF) desde el original el 2016-08-17 . Consultado el 2021-02-17 .
• Schultz, GW (marzo de 1969). Escrito en Central Data Systems, Inc., Sunnyvale, California, EE. UU. "Un algoritmo para la síntesis de redes secuenciales complejas". Computer Design . Vol. 8, núm. 3. Concord, Massachusetts, EE. UU.: Computer Design Publishing Corporation. págs. 49–55. ISSN  0010-4566. OCLC  828863003 . Consultado el 22 de febrero de 2021 .(7 páginas) (NB: Este artículo provocó numerosas cartas al editor en números posteriores de la revista).
• Schultz, GW (1969). Escrito en Central Data Systems, Inc., Sunnyvale, California, EE. UU. "Al editor". Cartas al editor. Computer Design . Vol. 8, no. 5–12?. Concord, Massachusetts, EE. UU.: Computer Design Publishing Corporation. pág. 10. ISSN  0010-4566. OCLC  828863003. pág. 10: […] 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] )
• Langdon, Jr., Glen G. (1974). "Capítulo 4. Interrelaciones, D. Diseño lógico y teoría de conmutación, 3. La tabla de flujo como punto de partida para el diseño". Escrito en IBM Corporation, San José, California, EE. UU. En Ashenhurst, Robert "Bob" Lovett [en Wikidata] (ed.). Diseño lógico: una revisión de la teoría y la práctica . Serie de monografías de ACM (1.ª ed.). Nueva York, EE. UU.: Academic Press, Inc. - Una subsidiaria de Harcourt Brace Jovanovich, Publishers . pág. 149. ISBN 0-12-436550-7. ISSN  0572-4252. LCCN  73-18988. Archivado desde el original el 2021-04-17 . Consultado el 2021-04-17 . p. 149: […] 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)

• Breve introducción a los gráficos ASM
• ASM++: una metodología moderna de máquina de estados algorítmica para diseños RTL