Caso 01
¿Cómo podemos resolver un sencillo problema de lógica con una placa FPGA?
El primer paso es traducir el problema de "texto humano" a descripciones formales basadas en ceros y unos. Eso significa definir el problema en forma de ecuaciones lógicas.
El segundo paso es representar estas ecuaciones lógicas en un circuito digital mediante puertas lógicas y los periféricos de la placa (botones, LEDs, ...) con los que poder hacer pruebas manualmente.
El último paso es añadir un circuito de pruebas que encuentre la solución, o soluciones, al problema planteado.
Los recursos utilizados son:
- La placa con FPGA IceZUM Alhambra
- El editor de circuitos digitales Icestudio 0.3
En una isla viven dos tipos de habitantes: los escuderos y los caballeros. Los caballeros siempre dicen la verdad, y los escuderos siempre mienten. Un día se encuentran dos habitantes: A y B. Y se produce la siguiente conversación:
A afirma: "¡Eres un escudero!" y B responde: "Eso es mentira".
Veamos cómo se puede definir este sencillo problema mediante lógica binaria. A partir de ahora hay que cambiar el chip y pensar en uno/cero, True/False:
En una isla viven dos tipos de habitantes:
¡Estupendo! Podemos asignar 0 a un tipo de habitante y 1 al otro.
los escuderos y los caballeros.
Vamos a definir que los escuderos se representan con 0 y los caballeros con 1.
Los caballeros siempre dicen la verdad
Definimos que una frase es verdadera con 1 (y falsa con 0). Por lo tanto los caballeros (1) siempre dirán frases verdaderas (1).
y los escuderos siempre mienten.
Por lo tanto los escuderos (0) siempre dirán frases falsas (0).
Un día se encuentran dos habitantes: A y B.
Sabemos que tenemos dos "parámetros de entrada" A y B
Y se produce la siguiente conversación:
¡Ahora vienen las ecuaciones!
A afirma: "¡Eres un escudero!"
Definimos P como la frase "¡Eres un escudero!". Si la frase fuera verdadera P sería 1, si fuera falsa P sería 0.
Analizando la frase vemos que afirma que B es un escudero (0), es decir, que P es cierto (1) cuando B es 0. Y al contrario, P es falso (0) si B es 1. ¡P representa la operación de negación sobre B!. Es decir:
P = ¬B
y B responde "Eso es mentira".
Definimos Q como la frase "Eso es mentira" dentro del contexto de la conversación. Igual que en el caso anterior, si Q es verdadera vale 1 y si es falsa vale 0.
Al analizar la frase se comprueba que está negando lo que dice A, que es P. Es decir:
Q = ¬P
Y ya hemos analizado el problema. Ahora llega el paso de representarlo en un circuito digital.
La puerta XNOR representa el comparador de igualdad. La salida será 1 si las entradas son iguales entre sí (0-0 o 1-1). Esta puerta resulta de utilidad para analizar si es coherente el personaje con su frase, ya que como vimos anteriormente un caballero (1) sólo dirá frases verdaderas (1) y un escudero (0) sólo dirá frases falsas (0).
Como en el problema aparecen dos frases, deberemos introducir dos puertas XNOR. Una para (A,P) y otra para (Q,B)
Para encontrar la solución o soluciones hay que validar que los resultados de las evaluaciones de las puertas XNOR sean correctos (1). Para validar que ambos resultados son 1 utilizamos una puerta AND, que sólo se activa si ambas entradas son 1.
Como en las ecuaciones aparece el operador negación, deberemos utilizar la puerta NOT, que invierte el valor de la entrada, para describir dichas ecuaciones. Al aparecer dos veces, tendremos que incluir dos puertas NOT.
Las entradas del problema, como vimos anteriormente, son los parámetros A y B, que representarán posibles caballeros (1) o escuderos (0). Las conectaremos a los botones de la placa para probar manualmente las posibles combinaciones del problema.
Para visualizar las entradas las conectamos directamente con los LEDs. A en el LED0 y B en el LED1.
La señal de salida queremos que se active cuando la combinación de A y B genere una solución válida. Esta salida la conectamos al LED7.
Finalmente queda representar las ecuaciones mediante conexiones:
P = ¬B
Q = ¬P
NOTA: se podría simplificar Q = ¬¬B = B, pero se deja como está para ser lo más fiel posible a la definición del problema.
Descargar circuito Final en Icestudio
Al sintetizar y descargar el circuito en la FPGA, se puede comprobar manualmente que el LED7 sólo se enciende cuando uno de los dos, pero no los dos botones, están pulsados.
| A (LED0) | B (LED1) | S (LED7) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Este es el comportamiento de una puerta lógica XOR, pero lo hemos deducido probando el circuito previamente sintetizado en la FPGA.
Traduciendo la solución de nuevo al "lenguaje humano", existen dos soluciones posibles y son las siguientes:
- A es un escudero y B un caballero
- A es un caballero y B un escudero
Con la información que tenemos no podemos determinar qué son exactamente A y B, pero sabemos que son distintos. Esta no es una solución muy espectacular pero nos ha servido para visualizar cómo convertir paso a paso un problema lógico en un circuito digital.
Para automatizar el proceso de búsqueda de soluciones se ha implementado el siguiente circuito.
No entraremos en detalle sobre la implementación, pero sí en el comportamiento:
- El circuito comprueba todas las soluciones utilizando un contador binario (00, 01, 10, 11) y se detiene cuando encuentra una solución o termina (llega a 11).
- El contador funciona a la frecuencia de reloj, que en este caso son 12Mhz, es decir, evalua las 4 posibles soluciones en 0.33 micro segundos.
- Si existen múltiples soluciones, al encontrar la 1ª el circuito se detiene. Para continuar la búsqueda de nuevas soluciones hay que pulsar el botón de Next (SW2).
- La búsqueda se puede resetear mediante el Reset asíncrono (SW1).
- Si modificamos el circuito para que no tenga soluciones el circuito finaliza con el LED7 (S) apagado indicando que no se han encontrado soluciones.
En el problema actual, al conectar el circuito se detiene en la primera solución. Al pulsar Next encuentra la siguiente solución. Si volvemos a pulsar Next se detiene al llegar al final del contador.
Descargar circuito de pruebas en Icestudio
Al recordar este tipo de problemas lógicos pensé en crear un programa que encontrara las soluciones, pero vi que era mucho más intuitivo e interesante crear un circuito que encuentre soluciones a problemas lógicos.
Además esta forma es mucho más rápida y eficiente en ejecución que cualquier programa, en igualdad de frecuencia de reloj, ya que no requiere de un procesador que ejecute instrucciones, sino que se trata de un simple circuito secuencial.
Os animo a investigar esta metodología con circuitos más complejos para ver hasta dónde se puede llegar, pero sobre todo para pasar un buen rato pensando en hardware!
GPL 2.0 and Creative Commons Attribution-ShareAlike 4.0 International License.