Durante mi tiempo libre, mi hijo y yo estudiamos electrónica digital. Recientemente, llegamos al capítulo sobre máquinas de estados finitos. Este tema está lleno de tareas típicas, como un semáforo o una máquina expendedora. Pero todos son aburridos y demasiado simples, y algunos son, en general, francamente exagerados. Después de estudiar ejemplos simples, quería hacer algo más interesante y complejo. El clásico juego "serpiente" me llamó la atención (mi hijo lo jugó por teléfono), y sugerí hacerlo en máquinas de estado. Después de todo, el estado del juego es bastante final (especialmente si te limitas a un campo pequeño), y desde las entradas solo hay 4 botones. Y esto es lo que tenemos.El juego Snake (ella es una serpiente, pitón, boa constrictor, etc.) es ampliamente conocido por todos. Ella viene de los lejanos años 70, pero no repetiré su historia, que puedes leer en Wikipedia o en muchos artículos sobre Habré. El juego tiene reglas bastante simples y al mismo tiempo un juego adictivo)) Gracias a esto, a menudo se usa para tutoriales o muestras de código . En lenguajes de programación de alto nivel, hacer un juego así es bastante fácil. Pero en condiciones más limitadas, lo más interesante comienza, por ejemplo, una implementación en LabVIEW . También hay muchas opciones en FPGA: enlace 1 , enlace 2 , enlace 3, Enlace 4 . Pero no ha habido una sola opción en chips TTL separados de series estándar. Entonces eso es lo que haremos.Parecería que las soluciones FPGA son las más cercanas para nosotros, ¿y usted puede pedir prestado mucho a partir de ahí? Pero en todas las opciones que miré, se dispersan fácilmente en registros de izquierda y derecha. Por ejemplo, muy a menudo se asigna un bit o número separado para cada celda de campo. No podemos hacer esto con polvo suelto, porque cada nuevo registro es un microcircuito separado que debe colocarse en algún lugar y luego conectarse. Por lo tanto, tachamos toda la experiencia acumulada por otros desarrolladores y haremos todo desde cero. Como beneficio adicional, recopilaremos todo en chips domésticos (y mejor - soviéticos) de la serie k555 / kr1533, con la excepción de los ROM, que deberán tomarse de nuevo.Formulación del problema
Tendremos tales restricciones: un campo de tamaño 8 × 8 celdas ( matriz de LED chino ), una longitud de cola de 8 celdas. Una serpiente puede atravesar las paredes, pero al principio no procesaremos la intersección con la cola (para no complicar el diseño, puede agregar esto más adelante). Para describir todo el estado del juego necesitamos:- Posición del cabezal (X = 0..7, Y = 0..7, 6 bits)
- Dirección del movimiento (↑ ↓ ← →, 2 bits)
- Posición de Apple (X, Y, 6 bits)
- Longitud de la cola (0..7, 3 bits)
- La posición de las celdas de la cola (de 0 a 7 piezas de 6 bits cada una)
En total, se obtienen 65 bits, incluso si tomamos registros de 8 bits cada uno, solo se necesitan 8 microcircuitos (y un disparador más) para almacenar el estado, esto es bastante.Pero la cola no puede ubicarse donde quiera, "crece" desde la cabeza. Por lo tanto, no podemos almacenar las coordenadas completas de cada sección de la cola, sino solo la dirección en la que se debe dibujar la dirección de la celda (o cabeza) anterior. Entonces, en lugar de 6 × 8 = 48 bits, necesitamos 4 × 8 = 16 bits, ¡y esto es un ahorro de hasta cuatro casos de registro!Máquinas automáticas
Tratemos de hacer todo en máquinas similares a Moore o Miles. Para implementar dicho autómata, es suficiente tener un poco de memoria de estado (registro) y lógica combinatoria para cambiar entre ellos.
Imagen de WikipediaPor lo general, una máquina de estados se describe como un gráfico de estados y transiciones entre ellos. A veces es más conveniente crear una tabla de transiciones a un nuevo estado, el ejemplo más simple (de Wikipedia):
puede encontrar más información y bellas imágenes, por ejemplo, en este artículo sobre HabréPequeña digresión, , . , ROM , ROM.
( , ).
, , .
, « » .
Una serpiente de varios estados (si no tiene en cuenta la posición de la manzana) puede tener 2 ^ 8 + 2 ^ 10 + ... + 2 ^ 24 ≈ 32 millones. No es posible escribirlos en la tabla, y aún más dibujar un gráfico de transición. Pero la mayoría de las transiciones son bastante iguales (la cabeza se mueve solo una celda adyacente y la cola se mueve una sección por turno). En este caso, no podemos describir cada estado individual, sino formular un nuevo estado en función del anterior. Además, podemos dividir todo el juego en varios autómatas paralelos: 1) una máquina automática de dirección, 2) una máquina automática de posición de la cabeza, 3) una máquina automática para la cola. Y para configurar cada uno de ellos como sea más conveniente:1) , │
────────────────────┼───────────────────
← ←/↓/↑ │ ←
← → │ →
↑ ↑/←/→ │ ↑
↑ ↓ │ ↓
...... │
2) , │
─────────────────────┼──────────────
← (x,y) │ (x-1, y)
→ (x,y) │ (x+1, y)
↑ (x,y) │ (x, y-1)
↓ (x,y) │ (x, y+1)
3) , │
─────────────────────────────────────────┼──────────────────────────
← (t1,t2,t3,t4,t5,t6,t7,t8) │ (←,t1,t2,t3,t4,t5,t6,t7)
...... │
Dirección
Comencemos con la máquina direccional. Si piensa cuidadosamente, puede ensamblarlo en una lógica separada. Pero, dado que la tarea en su conjunto ya es bastante grande, decidí que sería más fácil hacer una tabla de búsqueda desde EEPROM y escribir la tabla de transición manualmente. Tendrá 6 entradas, lo que significa solo 64 valores, que simplemente podemos introducir en el editor hexadecimal.
Cabeza
Para una máquina de posicionamiento de cabeza, escribir tal tabla será mucho más difícil. Pero esencialmente contiene solo 2 operaciones: +1 y -1. Se pueden implementar en un sumador de 4 bits K155IM6. Para +1, agregaremos nuestra coordenada con b'0001 y para -1 con b'1111 (que en realidad es -1 en el código adicional ). Necesitaremos dos sumadores (para x e y), un poco de lógica, y almacenaremos el estado en el registro IR27 de 8 bits (todavía necesitamos muchos de ellos):
Vamos a armarlo en la placa, y para la verificación conectaremos inmediatamente la matriz LED con dos decodificadores. El decodificador con salidas inversas es ID7, y para el directo sería posible tomar K561ID1 (CD4028), pero no lo tenía a la mano. Otra opción es tomar 8 transistores como claves, pero no quería hacer esto, así que tuve que gastar estúpidamente otra EEPROM (escribiendo solo 8 celdas allí). La lógica de la nueva posición de la cabeza en un tablero separado en la parte superior Otra digresión
Tomemos un breve descanso y guardemos la placa de pruebas (y algunas cajas de chips). Nuevamente aprovecharemos el hecho de que cualquier circuito combinado puede ser reemplazado por un LUT escribiendo la tabla en la ROM. Pero, ¿cómo hacer esto para una mesa tan grande? Usaremos otro truco, haremos lo contrario: reemplazar la EEPROM con nuestro circuito lógico y ponerlo en el programador. Las patas no utilizadas están conectadas al suelo a través de resistencias. (Esto no podría hacerse si profundiza en la configuración del programador)
Ahora leeremos nuestro diagrama lógico como ROM y obtendremos una tabla. Lo escribimos con el mismo programador en una EEPROM real, que colocamos en lugar de un circuito de elementos separados.
Cola
La cola tiene una longitud (en nuestras limitaciones) de 2 a 8 celdas. Para almacenar esta longitud, puede usar un contador convencional con una entrada de resolución de cuenta. De hecho, será la misma máquina de estados finitos, en la que el nuevo estado S 'será igual a S + 1 o simplemente S (si la cuenta está prohibida). La cola misma (o más bien, la dirección donde crece) la almacenaremos en dos registros de 8 bits. Teóricamente, uno podría tomar registros de desplazamiento ya preparados (por ejemplo, IR8), pero no estaban disponibles, por lo que se utilizaron los mismos IR27. En cada paso, la dirección actual del movimiento de la cabeza se escribe en el primer bit del registro, y el valor del anterior en el segundo y el siguiente. Para obtener la dirección del crecimiento de la cola, solo necesitamos invertir un bit. Puedes hacer esto de inmediato cuando grabes, pero decidí que era mejor dejar el inverso para el circuito restante.Esquema
En total, nuestra máquina de próximo movimiento adopta esta forma: se puede hacer clic en esta imagen (como todos los demás). Esta es una parte bastante "pura" (desde un punto de vista teórico) del esquema. Ejemplo casi perfecto para la máquina Moore de salida codificada . U1 es responsable de la nueva dirección, U2 de la posición de la cabeza, que se almacenan en U5. U3 y U4 se usan para la cola, y su longitud se almacena (y aumenta) en U6. A continuación, tendremos que mostrar todo lo que tenemos en la pantalla, y también habrá una nave espacial, solo en una forma más sucia. Además de un generador de números aleatorios primitivo, una transición entre circuitos con una señal de reloj diferente y otros hacks.
Total parcial
Espero que este artículo te haya interesado y trataré de terminar rápidamente la segunda parte.Y si ya está entrando en batalla, abastecido con placas de prueba, microchips y pantallas de puntos, se adjunta a este artículo un archivo con el circuito ROM y el firmware. Mini spoiler: para repetir el diseño necesitará unos 6 prototipos, 4 EEPROM 28C16 y un poco más de dos docenas de otros chips.Bueno, como debería ser: como, compartir, retuitear, registrarse, presionar la campana, etc. ...)) Y por hoy todo, ¡gracias por su atención! Continuará…
Archivo con firmware ROM y el esquemaUPD general : la segunda parte está disponible aquí .