Lógica Digital

Introducción

La lógica digital, o booleana, es el concepto fundamental en el que se basan todos los sistemas informáticos modernos. En pocas palabras, es el sistema de reglas que nos permite tomar decisiones extremadamente complicadas basadas en preguntas “sí/no” relativamente sencillas.

Circuitos digitales

Los circuitos lógicos digitales pueden dividirse en dos subcategorías: combinacionales y secuenciales. La lógica combinacional cambia “instantáneamente”: la salida del circuito responde tan pronto como cambia la entrada (con cierto retraso, por supuesto, ya que la propagación de la señal a través de los elementos del circuito lleva un poco de tiempo). Los circuitos secuenciales tienen una señal de reloj, y los cambios se propagan a través de las etapas del circuito en los bordes del reloj.

Normalmente, un circuito secuencial está formado por bloques de lógica combinacional separados por elementos de memoria que se activan mediante una señal de reloj.

Programación

La lógica digital también es importante en la programación. La comprensión de la lógica digital hace posible la toma de decisiones complejas en los programas.

También hay algunas sutilezas en la programación que son importantes de entender; entraremos en ello una vez que hayamos cubierto los fundamentos.

Lecturas sugeridas

Antes de comenzar, puede ser una buena idea revisar nuestro tutorial sobre números binarios, si aún no lo has hecho. Hay una pequeña intruducción a la lógica booleana allí, pero profundizaremos mucho más en el tema aquí. Aquí hay algunos otros temas con los que debería estar familiarizado antes de comenzar.

¿Qué es la electricidad?
Binario
Analógico vs Digital
Niveles Lógicos

Lógica combinacional

Los circuitos combinacionales están formados por cinco puertas lógicas básicas:

• Puerta AND – la salida es 1 si AMBAS entradas son 1
• Puerta O – la salida es 1 si AL MENOS una entrada es 1
• Compuerta XOR – la salida es 1 si SOLO una de las entradas es 1
• Puerta NAND – la salida es 1 si AL MENOS una entrada es 0
• Puerta NOR – la salida es 1 si AMBAS entradas son 0

Hay un sexto elemento en la lógica digital, el inversor (a veces llamado puerta NOT). Los inversores no son verdaderas puertas, ya que no toman ninguna decisión. La salida de un inversor es un 1 si la entrada es un 0, y viceversa.

Algunas cosas a tener en cuenta sobre la imagen anterior:

• Por lo general, no se imprime el nombre de la puerta; se supone que el símbolo es suficiente para identificarla.
• La notación de terminales del tipo A-B-Q es estándar, aunque los diagramas lógicos suelen omitirlos para las señales que no son entradas o salidas del sistema en su conjunto.
• Los dispositivos de dos entradas son estándar, pero ocasionalmente se verán dispositivos con más de dos entradas. Sin embargo, sólo tendrán una salida.

Los circuitos lógicos digitales suelen representarse con estos seis símbolos; las entradas están a la izquierda y las salidas a la derecha. Mientras que las entradas pueden conectarse entre sí, las salidas nunca deben conectarse entre sí, sólo a otras entradas. Sin embargo, una salida puede conectarse a varias entradas.

Tablas de verdad

Las descripciones anteriores son adecuadas para describir la funcionalidad de los bloques individuales, pero existe una herramienta más útil: la tabla de verdad. Las tablas de verdad son gráficos sencillos que explican la salida de un circuito en función de las posibles entradas del mismo. A continuación, se presentan las tablas de verdad que describen los seis elementos principales:

Las tablas de verdad pueden ampliarse a una escala arbitraria, con tantas entradas y salidas como puedas manejar antes de que se te derrita el cerebro. Este es el aspecto de un circuito de cuatro entradas y una tabla de verdad:

Lógica booleana escrita

Por supuesto, es útil poder escribir en un formato matemático sencillo una ecuación que represente una operación lógica. Para ello, existen símbolos matemáticos para las operaciones únicas: AND, OR, XOR y NOT.

• A Y B debe escribirse como AB (o a veces A – B)
• A OR B debe escribirse como A + B
• A XOR B debe escribirse como A ⊕ B
• NOT A debe escribirse como A’ o A

Notarás que hay dos elementos que faltan en esa lista: NAND y NOR. Normalmente, se representan simplemente complementando la representación apropiada:

• A NAND B se escribe como (AB)’ , (A – B)’ , o (AB)
• Un NOR B se escribe como (A + B)’ o (A + B) 

Lógica secuencial

La lógica combinacional es genial, pero sin añadir circuitos secuenciales, la informática moderna no sería posible.

Los circuitos secuenciales son los que añaden memoria a nuestros sistemas lógicos. Como ya hemos dicho, la lógica combinacional produce resultados después de un retardo. Ese retraso varía en función de muchísimas cosas: el proceso de fabricación de las piezas implicadas, la temperatura del silicio, la complejidad del circuito. Si la salida de un circuito depende de los resultados de otros dos circuitos combinacionales y los resultados llegan en momentos diferentes (lo que ocurrirá en el mundo real), un circuito combinacional tendrá un breve “fallo”, produciendo un resultado que puede no ser coherente con la operación deseada.

Un circuito secuencial, sin embargo, sólo muestrea y propaga la salida en momentos concretos. Si la entrada cambia entre esos momentos, se ignora. El tiempo de muestreo suele estar sincronizado en todo el circuito y se denomina “reloj”. Cuando se cita la “velocidad” de un ordenador, éste es el valor en cuestión. Es posible diseñar circuitos secuenciales “asíncronos”, que no dependen de un reloj global sincronizado. Sin embargo, esos sistemas plantean grandes dificultades, y no los discutiremos aquí.

Como nota al margen, cualquier sección de lógica digital tendrá dos valores de retardo característicos: el tiempo de retardo mínimo y el tiempo de retardo máximo. Si el circuito falla el tiempo de retardo mínimo (es decir, es más rápido de lo que debería), el circuito fallará, irremediablemente. Si ese circuito forma parte de un dispositivo más grande, como la CPU de un ordenador, todo el dispositivo es basura y no se puede utilizar. Si el tiempo de retardo máximo falla (es decir, el circuito es más lento de lo que debería), la velocidad del reloj puede reducirse para adaptarse al circuito más lento del sistema. Los tiempos máximos de retardo tienden a aumentar a medida que el silicio que forma un circuito se calienta, razón por la cual los ordenadores se vuelven inestables cuando se sobrecalientan o cuando se aumenta la velocidad del reloj (como ocurre con el overclocking).

Elementos de los circuitos secuenciales

Al igual que ocurre con la lógica combinacional, existen varios elementos de circuito básicos que forman los bloques de construcción de los circuitos secuenciales. Estos bloques se construyen a partir de los elementos combinacionales básicos, utilizando la retroalimentación de la salida para estabilizar la entrada. Los hay de dos tipos: latches y flip-flops. Aunque los términos se utilizan con frecuencia indistintamente, los latches son generalmente menos útiles, ya que no están sincronizados; nos centraremos en los flip-flops.

Flip-Flop tipo D

El tipo más simple de flip-flop es el tipo D. Los flip-flops D son sencillos: cuando se produce un flanco de reloj (normalmente ascendente, aunque se pueden encontrar con un inversor incorporado para que el reloj entre en el flanco descendente), la entrada se enclava en la salida.

Normalmente, la entrada de reloj se indica con el pequeño triángulo que incide en el símbolo. La mayoría de los flip-flops proporcionan dos salidas: la salida “normal” y la salida complementada.

Flip-Flop tipo T

Sólo un poco más complejo es el tipo T. La ‘T’ significa “toggle”. Cuando se produce un flanco de reloj, si la entrada T es un 1, la salida cambia de estado. Si la entrada es un 0, la salida permanece igual. Como en el caso del tipo D, se suele proporcionar el complemento de la salida.

Una función útil del flip-flop T es la de circuito de división de reloj. Si T se mantiene alto, la salida será la frecuencia del reloj dividida por dos. Una cadena de flip-flops T puede utilizarse para producir relojes más lentos a partir del reloj maestro de un dispositivo.

Flip-Flop tipo JK

Por último, tenemos el tipo JK. El tipo JK es el único de los tres que realmente requiere una tabla de verdad para explicarlo; tiene dos entradas (J y K), y la salida puede dejarse igual, establecerse, despejarse o conmutarse, dependiendo de la combinación de señales de entrada presentes. Por supuesto, como con todos los flip-flops, la entrada en el momento del reloj es lo único que importa.

Tiempos de establecimiento, retención y propagación

Todos los circuitos secuenciales tienen lo que se llama tiempos de “preparación” y “retención”, así como un retardo de propagación. Entender estas tres cosas es fundamental para diseñar circuitos secuenciales que funcionen como se espera.

El tiempo de preparación es el tiempo mínimo que debe transcurrir antes de que se produzca un flanco de reloj ascendente para que una señal llegue a la entrada de un flip-flop y éste pueda enclavar los datos correctamente. Del mismo modo, el tiempo de retención es el tiempo mínimo que una señal debe permanecer estable después de que se produzca el flanco de subida del reloj antes de que pueda cambiar.

Mientras que los tiempos de establecimiento y retención se dan como valores mínimos, el retardo de propagación se da como máximo. En pocas palabras, el retardo de propagación es la mayor cantidad de tiempo después de un flanco descendente en el reloj antes de que se pueda esperar ver la señal en las salidas. Aquí hay un gráfico que los explica:

Observa que, en la imagen anterior, las transiciones se dibujan como ligeramente angulares. Esto sirve para dos propósitos: nos recuerda que los bordes del reloj y de los datos nunca son realmente ángulos rectos y siempre tendrán algún tiempo de subida o bajada distinto de cero, y hace más fácil ver dónde se cruzan las líneas verticales que marcan los distintos tiempos con las señales.

La combinación de estos tres valores determina la mayor velocidad de reloj que puede utilizar un dispositivo. Si el retardo de propagación de una parte más el tiempo de establecimiento de la siguiente en el circuito supera el tiempo entre el flanco de caída de un pulso de reloj y el flanco de subida del siguiente, los datos no serán estables en la entrada del segundo componente, provocando un comportamiento inesperado.

Metaestabilidad

El incumplimiento de los tiempos de establecimiento y retención puede provocar un problema llamado “metaestabilidad”. Cuando un circuito está en un estado metaestable, la salida de un flip-flop puede oscilar rápidamente entre los dos estados normales, a menudo a una velocidad muy superior a la del reloj del circuito.

Los problemas de metaestabilidad pueden ir desde un funcionamiento espurio hasta el deterioro del chip, ya que pueden aumentar el consumo de corriente. Aunque la metaestabilidad suele resolverse por sí sola, para cuando lo hace, el sistema puede encontrarse en un estado totalmente desconocido y necesitar un reinicio completo para restablecer el funcionamiento correcto.

Una forma común de que surjan problemas de metaestabilidad es cuando una señal cruza dominios de reloj, es decir, cuando una señal pasa entre dispositivos que están siendo sincronizados por diferentes fuentes. Dado que los relojes no están sincronizados (e incluso si los relojes tienen la misma frecuencia nominal, la realidad dicta que serán ligeramente diferentes), en algún momento un flanco de reloj y un flanco de datos estarán demasiado cerca para ser cómodos, dando lugar a una violación del tiempo de establecimiento. Una solución sencilla para este problema es hacer pasar todas las entradas de un sistema por un par de flip-flops D en cascada. Aunque el primer flip-flop entre en metaestabilidad, (con suerte) se habrá estabilizado antes del siguiente pulso de reloj, permitiendo al segundo flip-flop leer los datos correctos. Esto resulta en un retraso de un ciclo en los bordes de datos entrantes, que casi siempre es insignificante comparado con el riesgo de metaestabilidad. 

Lógica booleana en la programación

Todo esto puede aplicarse también en el mundo de la programación. La mayoría de los programas son simplemente árboles de decisión: “si esto es cierto, entonces haz esto”. Para explicar esto, usaremos código C en un contexto de Arduino.

Lógica bit a bit

Cuando hablamos de lógica “bitwise”, lo que realmente queremos decir son operaciones lógicas que devuelven un valor. Tomemos, por ejemplo, este trozo de código:

byte a = b01010101;
byte b = b10101010;
byte c;

Podemos hacer una operación bitwise usando ‘a’ y ‘b’ y poniendo el resultado en ‘c’. Esto es lo que parece:

c = a & b;  // bitwise AND-ing of a and b; the result is b00000000
c = a | b;  // bitwise OR-ing of a and b; the result is b11111111
c = a ^ b; // bitwise XOR-ing of a and b; the result is b11111111
c = ~a;  // bitwise complement of a; the result is b10101010

En otras palabras, cada bit del resultado es igual a la operación aplicada a los dos bits correspondientes de los operandos:

Vale, eso está muy bien, pero ¿qué pasa? Resulta que podemos hacer algunas cosas bastante útiles utilizando operadores a nivel de bit para manipular registros: podemos borrar, establecer o alternar selectivamente bits individuales, comprobar si un bit está establecido o despejado, o si varios bits están establecidos o despejados. Aquí hay algunos ejemplos que utilizan estas operaciones:

c = b00001111 & a; // clear the high nibble of a, but leave the low nibble alone.
                                // the result is b00000101.
c = b11110000 | a; // set the high nibble of a, but leave the low nibble alone.
                                // the result is b11110101.
c = b11110000 ^ a; // toggle all the bits in the high nibble of a.
                                // the result is b10100101.

Cualquier operación a nivel de bits se puede autoaplicar combinándola con el signo de igualdad:

a ^= b11110000; // XOR a with b11110000 and store the result back in a
b |= b00111100; // OR b with b00111100 and store the result back in b

Desplazamiento de bits

Otra operación útil a nivel de bits que puede realizarse sobre un dato es el desplazamiento de bits. Se trata simplemente de un deslizamiento de los datos a la izquierda o a la derecha en un número determinado de posiciones; los datos que se desplazan hacia fuera desaparecen y son sustituidos por un 0 que se desplaza desde el otro extremo.

byte d = b11010110;
byte e = d>>2;  // right-shift d by two positions; e = b00110101
e = e<<3; // left-shift e by three positions; e = b10101000

Más adelante mostraremos algunos usos del desplazamiento de bits. Una aplicación muy útil para los desplazamientos de bits es la multiplicación y la división: cada desplazamiento a la derecha es lo mismo que una división por dos (aunque se pierde la información del resto) y cada desplazamiento a la izquierda es lo mismo que una multiplicación por dos. Esto es útil porque multiplicar y dividir suelen ser operaciones muy costosas en tiempo en procesadores pequeños, como el de Arduino, pero los desplazamientos de bits suelen ser muy eficientes.

Operadores relacionales y de comparación

Querremos alguna forma de comparar dos valores: hay una familia de operadores que hacen precisamente eso y devuelven “TRUE” o “FALSE” dependiendo del resultado de la comparación.

• == “es igual a” (verdadero si los valores son iguales, falso en caso contrario)
• != “no es igual a” (verdadero si los valores son diferentes)
• > “es mayor que” (verdadero si el operando de la izquierda es mayor que el de la derecha)
• < “es menor que” (verdadero si el operando de la izquierda es menor que el de la derecha)
• >= “es mayor que, o igual a” (verdadero si el operando izquierdo es mayor que, o exactamente igual al operando derecho)
• <= “es menor o igual que” (verdadero si el operando izquierdo es menor o exactamente igual que el operando derecho)

En general, es muy importante que los valores comparados sean del mismo tipo de datos; pueden ocurrir cosas inesperadas si se comparan un “byte” y un “int”, por ejemplo.

Operadores lógicos

Los operadores lógicos son operadores que producen un “TRUE” o un “FALSE”, en lugar de un nuevo valor del mismo tipo. Se parecen más a lo que solemos considerar como conjunciones: “Si no llueve y hace viento, ve a volar una cometa”. Traducida a C, esa frase podría ser así:

if ( (raining != true) && (windy == true) ) flyKite();

Fíjate en los paréntesis que rodean a las dos subcláusulas. Aunque no es estrictamente necesario, es una buena práctica mantener el código lo más legible posible agrupando las subcláusulas.

Observa también que el operador lógico AND (&&) produce una respuesta verdadera/falsa basada en si las subcláusulas producen o no respuestas verdaderas/falsas. Podríamos haber tenido fácilmente un valor numérico en una de las subcláusulas:

if ( (raining != true) && ( (windSpeed >= 5) || (reallyBusy != true) ) ) flyKite();

Esta cláusula me enviará a volar una cometa, siempre que no llueva, pero sólo si hay algo de viento o no estoy ocupado (intentaré volar sin viento).

De nuevo, fíjate en los paréntesis. Si eliminamos los paréntesis alrededor de “(windSpeed >= 5) || (reallyBusy != true)” — con || representando el operador OR — creamos una declaración ambigua que puede o no hacer lo que queremos que haga.

Control de flujo

Ahora que podemos crear sentencias lógicas complejas, veamos las cosas que podemos hacer con las respuestas a esas preguntas.

Sentencias if/else if/else

La decisión más simple es “if/else”. Las sentencias “if/else” le permiten establecer una serie de pruebas, de las cuales sólo una puede ser ejecutada en cualquier momento:

if ( reallyBusy == true ) workHarder();
else if ( (raining != true) && (windy == true) ) flyKite();
else work();

Con esas tres afirmaciones, nunca volaré una cometa si estoy muy ocupado, y si no estoy muy ocupado, y no es un buen día para ello, seguiré trabajando. Cambiemos el else if() por el if(), así:

if ( reallyBusy == true ) workHarder();
if ( (raining != true) && (windy == true) ) flyKite();
else work();

Ahora bien, si tenemos un buen día para volar cometas, aunque esté muy ocupado, sólo trabajaré más duro durante un periodo muy, muy corto, básicamente hasta que note que hace buen tiempo. Además, si el día no es agradable, mi condición de trabajar más duro pasará a ser de simple trabajo inmediatamente después de que empiece a trabajar más duro.

Puedes imaginar lo que pasaría si sustituimos “workHarder()” por “turnLEDOn()” y “work()” por “turnLEDOff()”. En el primer caso, el LED puede estar encendido durante algún tiempo, o apagado durante algún tiempo. En el segundo caso, sin embargo, independientemente del estado de la bandera “reallyBusy”, el LED se apagará casi instantáneamente después de que la primera sentencia if() lo encendiera, ¡y te encontrarías sentado preguntándote por qué la luz “reallyBusy” nunca se enciende!

Sentencias switch/case/default

Menos potente pero más legible que una larga cadena de sentencias if/else, switch/case/default le permite tomar una decisión basada en el valor de una variable:

switch(menuSelection) {
  case '1':
    doMenuOne();
    break;
  case '2':
    doMenuTwo();
    break;
  case '3':
    doMenuThree();
    break;
  default:
    flyKite();
    break;
}

La sentencia switch() sólo nos permite comprobar la equivalencia, pero como eso es algo bastante común de querer hacer, resulta bastante útil. Hay dos cosas realmente importantes a tener en cuenta sobre esto: las declaraciones “break;” y el caso “default:”.

“default:” es lo que se ejecutará si ninguno de los otros coincide. No es estrictamente necesario; si no hay un caso por defecto, entonces no pasa nada si todas las coincidencias fallan. Por supuesto, normalmente se quiere que ocurra algo, y es mejor no asumir que es imposible que todas las coincidencias fallen.

“break;” salta fuera de la condicional actual. Puede usarse dentro de cualquier tipo de condicional (más adelante), y en este caso, si no se incluye un break al final de cada caso, se ejecutará el código después del caso, incluso si las coincidencias de caso posteriores fallan.

Bucles while/do…while

Hasta ahora, hemos visto el código para tomar una decisión una vez. ¿Qué pasa si quieres repetir una acción, una y otra vez, mientras una condición se mantenga? Ahí es donde entran en juego while() y do…while().

while (windy == true) flyKite();

Cuando su código llega a una sentencia while(), el programa evalúa la condicional (“¿Hace viento?”) y, si se evalúa como “TRUE”, ejecuta el código. Una vez que la ejecución del código se ha completado, el condicional se evaluará una vez más. Si el condicional sigue siendo “TRUE”, el código se ejecutará de nuevo. Esto se repite una y otra vez, hasta que la condicional se evalúa a “FALSE” o se encuentra una declaración de ruptura.

Puede anidar una sentencia if() (o un switch(), u otro while(), o de hecho cualquier cosa que desees) dentro del bucle while():

while (windy == true) {
  flyKite();
  if (bossIsMad == true) break;
}

Así que, con ese bucle, volaré mi cometa hasta que el viento ceda o mi jefe se enfade conmigo.

Una variación de los bucles while() es el bucle do…while().

do {
  flyKite();
} while (windy == true);

En este caso, el código dentro de los paréntesis se ejecuta una vez, incluso si el condicional es falso. En otras palabras, independientemente del estado del viento, saldré a arrastrar una cometa, pero si no hay viento, me rendiré.

Por último, poniendo “TRUE” en la condicional, es posible crear un código que se ejecute para siempre:

while(true) {
  flyKite();
}

Con ese trozo de código, seguiré arrastrando mi cometa por el campo para siempre, sin importar el viento, la satisfacción de mi jefe, el hambre, los pumas, etc. Todavía es posible salir de ese código usando la sentencia break, por supuesto; sólo que nunca dejará de ejecutarse por sí mismo

Bucles for()

El último tipo de ejecución condicional que necesitamos considerar es el bucle for(). Los bucles for() nos permiten ejecutar un trozo de código un número específico de veces. La sintaxis de un bucle for es la siguiente

for (byte i = 0; i < 10; i++) {
  Serial.print("Hello, world!");
}

Dentro del paréntesis del bucle for() hay tres sentencias separadas por punto y coma. La primera es el iterador: la variable que estamos cambiando en cada pasada. También es donde se establece el valor inicial del iterador. La central es la comparación que haremos después de cada pasada. Una vez que esa comparación falla, salimos del bucle. La última declaración es lo que queremos hacer después de cada pasada por el bucle. En este caso, queremos incrementar el iterador en uno.

El error más común en un bucle for() es un error de uno en uno: quieres que el código se ejecute 10 veces, pero termina ejecutándose 9 veces, u 11 veces. Esto suele ser el resultado de utilizar un “<=” en lugar de “<” o viceversa.

Sfuptownwaker. Digital Logic. Sparkfun. https://learn.sparkfun.com/tutorials/digital-logic