Este artículo demuestra el diseño, minimización e implementación de un full-adder en Logisim para luego implementar un sumador ripple de 4 bits a partir del mismo.

Además se explican los conceptos de generación y propagación de carry, junto con la técnica de Carry Look-Ahead, que permite computar un carry independientemente del cómputo de posiciones anteriores.

Un full-adder (FA) es un circuito digital que computa la suma de operandos binarios de un bit de ancho. Tiene tres entradas y produce dos salidas. Las primeras dos entradas son los operandos, sendos bits, y la tercera entrada es el carry de entrada. Las salidas son el bit de suma y el carry de salida. Se diferencia del half-adder (HA) en que toma un carry de entrada. Esto es de vital importancia para computar sumas de operandos binarios de más de un bit de ancho conectando los carrys de varios full-adders entre sí en formato ripple (en cascada).



Full-adder

La siguiente figura demuestra el esquema de circuito de un full-adder:

La suma binaria de dos bits (xi e yi) con carry de entrada (ci) produce un bit de suma (si) y un carry de salida (ci+1). Este último será el carry de entrada para la siguiente posición (más significativa). La siguiente tabla de verdad contiene los valores que toma suma y carry de salida para cada combinación de entradas:

Al cargar los valores de si y ci+1 en mapas de Karnaugh, se obtienen las siguientes expresiones para suma y carry:

Implementación en Logisim: FA.circ

Este circuito computa en paralelo la suma de un bit. A partir de el mismo es posible crear sumadores de operandos de varios bits, por ejemplo 4 bits, conectando el carry de salida de cada posición, como carry de entrada de la posición siguiente.

Ripple adder

Suponiendo que se desean sumar dos operandos de 4 bits (cuyas posiciones son numeradas desde la 0 hasta la 3), se obtiene el siguiente circuito:

Este sumador toma dos operandos de 4 bits de ancho cada uno (x0-3 e y0-3), junto con un bit de carry de entrada (c0), y genera una suma de 4 bits de ancho (s0-3), junto con un bit de carry de salida (c4). Esta configuración se denomina ripple dado que los sumadores están conectados en serie y un carry de entrada se puede propagar hasta la salida de forma secuencial. Cada full-adder debe esperar a que el carry de entrada esté disponible de forma estable antes de poder computar el valor de suma correcto para su posición.

Implementación en Logisim: ripple4.circ

Este circuito hace uso de la implementación de full-adder anterior importando el circuito FA.circ. Por otro lado, notar el uso de splitters para separar los bits de una entrada de n bits de ancho (multi-bit).

Tiempo de operación

¿Cuál es el tiempo de suma para este sumador ripple de 4 bits?

Para responder esta pregunta es necesario analizar en qué momento estará disponible el carry de entrada de cada posición. Suponiendo c0,1,2 inicialmente igual a 0, ¿cómo puedo saber de antemano si habrá o no carry de entrada en la posición 3? Es decir c3 = 1.

Para que haya carry de entrada en la posición 3 (c3 = 1) tienen que cumplirse al menos una de las siguientes condiciones:

  • Se genera carry en la posición 2
  • Se genera carry en la posición 1 y la posición 2 lo propaga
  • Se genera carry en la posición 0 y las posiciones 1 y 2 propagan
  • Hay carry de entrada y las posiciones 0, 1 y 2 propagan

Más adelante veremos cómo se expresan generación y propagación para una posición dada.

Claramente si hay o no carry (y por qué razón) dependerá de los operandos de entrada.

Veamos un ejemplo sumando 11+9 en binario:

Omitiendo el carry inicial (c0 = 0), hay carry en la posición 2 (c2 = 1) porque se genera un carry en la posición 0 y la posición 1 lo propaga.

El full-adder deberá esperar que se compute c1 en la posición 0 y luego se compute c2 en la posición 1 para poder computar la suma s2. Esto significa que el tiempo de suma trabajando asincrónicamente dependerá de los operandos.

En un extremo, el menor tiempo de operación del sumador será cuando ninguna posición genere ni propague carry. Asumiendo un retardo de una unidad de tiempo (1t) por cada nivel de compuerta, en solo 2t estará la suma disponible.

En el otro extremo, el peor tiempo de suma será cuando haya carry de salida en la posición 1 (c1 = 1) y se propague a lo largo del ripple hasta la entrada de la última posición (c3).

Trabajando de forma sincrónica, el tiempo de operación de nuestro sumador será el del peor caso, pues no se puede garantizar ningún tiempo de suma sin conocer los operandos de entrada.

Analicemos un ejemplo de propagación a lo largo del ripple sumando 3+13 sin carry de entrada (c0 = 0).

Inicialmente (tiempo = 0), todas las entradas y el carry de entrada están estables:

Luego de 2t, todos los FA generan sus salidas. Sin embargo, solo la salida del primer full-adder es correcta (en color rojo), pues el resto fueron computadas con valores de carry incorrectos:

Con un nuevo valor de carry de entrada en la posición 1, y transcurridos 2t más, se generan los valores correctos de carry de salida y suma en la posición 1:

Recién transcurridos 4t el FA de la posición 2 tiene el valor de carry correcto para computar sus salidas. A los 6t se producen los valores correctos de c3 y s2:

Pasados 8t todas las salidas son estables:

Por esta razón este tipo de configuración se denomina "ripple" o ola en español. La siguiente secuencia demuestra la propagación del carry a lo largo de todos los full-adders:

De esta forma 8t es el tiempo de suma del peor caso, con lo cual el tiempo de operación sincrónico del sumador será de 8t.

Generación y propagación de carry

De la fórmula para computar el carry de salida en una posición determinada se pueden discriminar las componentes responsables de la generación y propagación respectivamente:

Llamemos gi a la generación de carry y pi a la propagación de carry. En nuestro ripple de 4 bits obtenemos las siguientes expresiones:

De la fórmula se extrae que cada carry depende del carry de la posición anterior. Si se descompone recursivamente en cada fórmula, se obtienen las siguientes expresiones:

c1 queda como está, pues ya depende del carry inicial (c0). Para el cálculo de c2, se reemplaza c1 por su ecuación. Lo mismo ocurre con c3 reemplazando c2.

Se observa que c3 expresa en términos lógicos las condiciones par aque haya carry mencionadas al comienzo del análisis del tiempo de operación del sumador ripple, lo cual da la pauta de que son expresiones muy intuitivas, a pesar de su complejidad.

Ahora los carrys intermedios (c1-3) son independientes de las posiciones anteriores ya que todos dependen de c0. Esta técnica se conoce como Carry Look-Ahead y consiste en obtener por adelantado el carry en cada posición. De esta forma se rompe el ripple y selogra adelantar el cómputo de carry al costo de una lógica más compleja y mayor uso de compuertas.

Carry Look-Ahead Adder

Un Carry Look-Ahead Adder (CLAA) es un sumador binario que hace uso de la técnica de Look-Ahead para acelerar la operación de suma. Cada carry se computa a partir del carry inicial en paralelo y de manera independiente al resto.

¿Hasta qué punto se puede "adelantar" el cómputo de carry? Debido a que a medida que se avanzan posiciones se depende de mayor cantidad de posiciones anteriores, empiezan a surgir límites de fan-in (cantidad de entradas que deberá tener una compuerta) y fan-out (cantidad de entradas a la que se deberá conectar una salida).

A partir del cálculo de carry expresado en términos de generación y propagación, es posible realizar una abstracción de la fórmula en bloques de a n cantidad de bits. Veamos nuevamente la expresión de CLA de c3:

Agrupando bits desde la posición 0 a la 2 inclusive podemos expresar c3 de forma genérica:

Donde:

Se observa que tanto pi, gi, Gi,j como Pi,j dependen solo de los operandos de entrada. Por ende pueden ser todos calculados inmediatamente sin depender de resultados de posiciones anteriores.

El siguiente diagrama muestra un CLAA de 4 bits (donde j = i + 3):

Este sumador computa la suma en paralelo de 4 bits empleando la técnica Carry Look-Ahead y retorna (además de suma y carry de salida) los valores de Gi,j y Pi,j para los operandos de entrada. Esto servirá para construir sumadores más grandes (en ancho de bits) a partir de bloques CLAA de 4 bits.

Referencias


Tal vez pueda interesarte


Compartí este artículo