El método de 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, [1] introducido e implementado en Hewlett-Packard en 1968, formalizado y ampliado desde 1967 y escrito por Christopher R. Clare desde 1970. [2] [3] 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 . Cree un algoritmo, utilizando pseudocódigo , para describir la operación deseada del dispositivo.
- 2 . Convierta el pseudocódigo en un gráfico ASM .
- 3 . Diseñe la ruta de datos según 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 gráfico ASM detallado.
Gráfico ASM
Un diagrama de ASM consta de una interconexión de cuatro tipos de elementos básicos: nombre de estado, cuadro de estado, verificaciones de condición y salidas condicionales. Un estado ASM, representado como un rectángulo, corresponde a un estado de un diagrama de estado regular o máquina de estados finitos. Las salidas de tipo Moore se enumeran dentro de la caja.
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 de rectángulo
Cuadro de decisión: un diamante indica que la condición / expresión declarada debe probarse y la ruta de salida debe elegirse en consecuencia. La expresión de condición contiene una o más entradas al FSM (máquina de estado finito). Una verificación de condición de ASM, indicada por un rombo con una entrada y dos salidas (para verdadero y falso), se usa para transferir condicionalmente entre dos cajas de estado, a otra caja de decisión o a una caja de salida condicional. El cuadro de decisión contiene la expresión de condición establecida para ser probada, la expresión contiene una o más entradas del FSM.
Cuadro de salida condicional: un óvalo denota 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.
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 lógico combinacional asociado con un registro puede implementar un sumador, restador, multiplexor o algún otro tipo de función lógica combinacional.
Gráfico ASM detallado
Una vez que se diseña 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.
Ver también
Referencias
- ^ Osborne, Thomas "Tom" E. (11 de noviembre de 2004) [1994]. "La historia de Tom Osborne en sus propias palabras" . Página HP9825 de Steve Leibson (Carta a Barney Oliver). Archivado desde el original el 24 de febrero de 2021 . Consultado el 24 de febrero de 2021 .
- ^ Clare, Christopher "Chris" R. (febrero de 1971) [noviembre de 1970]. Diseño lógico de máquinas de estados algorítmicos . Laboratorios Hewlett-Packard, EE.UU .: Hewlett-Packard . Número de catálogo de CHM 102650285.(110 páginas) [1] (NB. Varias revisiones internas existieron en 1970 y 1971. Esto fue publicado más tarde por McGraw-Hill. [A] )
- ^ Clare, Christopher "Chris" R. (1973) [noviembre de 1972]. Diseño de sistemas lógicos mediante máquinas de estados (PDF) . Osborne, Thomas "Tom" E. (contribuciones iniciales) (1 ed.). Laboratorio de investigación electrónica, Laboratorios Hewlett-Packard: McGraw-Hill, Inc. ISBN 0-07011120-0. S2CID 60509061 . SBN 07-011120-0. ISBN 978-0-07011120-2 . arca: / 13960 / t9383kw8n. 79876543 . Consultado el 14 de febrero de 2021 .(vii + 114 + 3 páginas) [2] (NB. Este libro se basa en un documento interno de Hewlett-Packard de 1970. [B] )
- Sunggu Lee : Computer Design: An Example of Advanced Digital Logic Design , Prentice-Hall 2000, ISBN 0-13-040267-2 .
- Sunggu Lee : Diseño de lógica digital avanzada: uso de VHDL, máquinas de estado y síntesis para FPGA , Thomson 2006, ISBN 0-534-46602-8 .
- Stephen D. Brown , Zvonko Vranesic : Fundamentos de la lógica digital con diseño VHDL .
- Bjørner, Dines (diciembre de 1970) [4 de mayo de 1970, 7 de abril de 1970, 4 de febrero de 1970]. "Máquinas de diagrama de flujo" . BIT Matemáticas numéricas . Laboratorio de Investigación de IBM, San José, California. 10 : 415–442. doi : 10.1007 / BF01935563 . S2CID 189767592 . RJ-685 (No. 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 de valores múltiples LSI / VLSI (PDF) . Universidad de Oklahoma. Archivado (PDF) desde el original el 17 de agosto de 2016 . Consultado el 17 de febrero de 2021 .
Otras lecturas
- 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" . Diseño informático . Vol. 8 no. 3. Concord, Massachusetts, Estados Unidos: Computer Design Publishing Corporation. págs. 49–55. ISSN 0010-4566 . OCLC 828863003 . CODEN CMPDA . Consultado el 22 de febrero de 2021 .(7 páginas) (NB. Este artículo provocó una serie de cartas al editor en números posteriores de la revista).
- Schultz, GW (1969). Escrito en Central Data Systems, Inc., Sunnyvale, California, EE. UU. "Para el editor" . Cartas al editor. Diseño informático . Vol. 8 no. 5–12 ?. Concord, Massachusetts, Estados Unidos: Computer Design Publishing Corporation. pag. 10. ISSN 0010-4566 . OCLC 828863003 . CODEN CMPDA . pag. 10:
[…] En su número de abril, publicó una carta de RL Dineley que describe un método simple para tratar expresiones lógicas 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 del producto de sumas sea cero. Trazar ceros de factores en un diagrama de Veitch o mapa de Karnaugh es tan fácil como ubicar unos para una expresión de suma de productos . […] Para ilustrar, usando el ejemplo de Dineley (A + BC) (A + C): […] Los ceros resultantes de A + BC estarán ubicados donde tanto A como BC sean cero. Por tanto, ubicamos en el mapa la expresión A * BC (que es igual a A * B + A * C ). Del mismo modo los ceros de A + C se encuentran y se representan en A * C . Con todos los ceros ubicados, el resto del mapa puede llenarse 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 pueden escribirse mediante inspección; o los ceros pueden trazarse por inspección sin escribir la expresión completa […] "Reducción clásica que involucra variables usadas con poca frecuencia" 11 de octubre de 1968. Universidad de Santa Clara […] El trabajo del Sr. Osborne se asemeja mucho al que presenté en este artículo y, por tanto, sin duda sería de interés para aquellos lectores que busquen más información. Tengo entendido que ha trabajado para aplicar la técnica de variables infrecuentes al diseño de redes secuenciales construidas a partir de memoria de solo lectura . 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 contigo. […] GW Schultz […] Central Data Systems, Inc. […] Sunnyvale, Calif.
(1 página) (NB. El método de Osborne fue publicado más tarde por Clare. [B] ) - Langdon, Jr., Glen G. (1974). "Capítulo 4. Interrelaciones, D. Diseño lógico y teoría de la 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 (ed.). Diseño lógico: una revisión de la teoría y la práctica . Serie de monografías ACM (1 ed.). Nueva York, Estados Unidos: Academic Press, Inc. - Subsidiaria de Harcourt Brace Jovanovich, Publishers . pag. 149. ISBN 0-12-436550-7. ISSN 0572-4252 . LCCN 73-18988 . ISBN 978-0-12-436550-6 . Archivado desde el original el 17 de abril de 2021 . Consultado el 17 de abril de 2021 . pag. 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 pide que identifique las " variables poco frecuentes ". Definidas libremente, estas variables no se relacionan con todos los estados internos, es decir, no son necesarias para definir todos los estados. En esencia, las variables poco frecuentes son relevantes solo para unos pocos (quizás uno o dos) estados o transiciones de estados. 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 variables poco frecuentes a las transiciones de estado apropiadas. Se hace una "primera aproximación" a las ecuaciones de entrada flip-flop , basada sólo en las variables frecuentes. Schultz demuestra cómo estas ecuaciones pueden modificarse posteriormente para incorporar transiciones controladas por las variables poco frecuentes. En los ejemplos de Schultz, las variables poco frecuentes son todas señales de entrada, pero esta idea también se aplica a las señales de variables de estado internas que pueden considerarse "poco frecuentes". En este caso, por ejemplo, un flip-flop de variable de estado interno poco frecuente podría establecerse por una circunstancia particular y restablecerse en algún momento posterior. La salida del flip-flop ahora puede tratarse como una variable de entrada poco frecuente. […]
(ix + 1 + 179 + 3 páginas)
enlaces externos
- Breve introducción a los gráficos de MAPE
- ASM ++: una metodología moderna de máquina de estado algorítmica para diseños RTL