Sumador de acarreo anticipado - Carry-lookahead adder

Sumador de 4 bits con avance anticipado

Un sumador de acarreo anticipado (CLA) o sumador rápido es un tipo de sumador electrónico utilizado en lógica digital. Un sumador de acarreo anticipado mejora la velocidad al reducir la cantidad de tiempo requerido para determinar los bits de acarreo. Se puede contrastar con el sumador de acarreo de rizado (RCA) más simple, pero generalmente más lento, para el cual el bit de acarreo se calcula junto con el bit de suma, y cada etapa debe esperar hasta que se haya calculado el bit de acarreo anterior para comenzar a calcular el suyo. suma bit y acarreo bit. El sumador de acarreo anticipado calcula uno o más bits de acarreo antes de la suma, lo que reduce el tiempo de espera para calcular el resultado de los bits de mayor valor del sumador.

Ya a mediados de la década de 1800, Charles Babbage reconoció la penalización de rendimiento impuesta por el acarreo de ondas utilizado en su Motor Diferencial , y posteriormente diseñó mecanismos para anticipar el transporte de su Motor Analítico (nunca construido) . Se cree que Konrad Zuse implementó el primer sumador de acarreo anticipado en su computadora mecánica binaria de la década de 1930, la Zuse Z1 . Gerald B. Rosenberger de IBM solicitó una patente sobre un sumador binario moderno de acarreo anticipado en 1957.

Dos implementaciones ampliamente utilizadas del concepto son el sumador de Kogge-Stone (KSA) y el sumador de Brent-Kung (BKA).

Teoría de operación

Adición de ondulación

Un sumador binario de acarreo de ondas funciona de la misma manera que los métodos de adición de lápiz y papel. Comenzando en la posición del dígito más a la derecha ( menos significativo ), se suman los dos dígitos correspondientes y se obtiene un resultado. También es posible que pueda haber un arrastre de esta posición de dígito; por ejemplo, "9 + 5 = 4, lleva 1". La aritmética binaria funciona de la misma manera, con menos dígitos. En este caso, solo hay cuatro operaciones posibles, 0 + 0, 0 + 1, 1 + 0 y 1 + 1. El último de estos casos genera un acarreo. En consecuencia, todas las posiciones de los dígitos que no sean la de la derecha deben tener en cuenta la posibilidad de tener que agregar un 1 adicional de un contingente de dígitos una posición a la derecha.

Esto significa que ninguna posición de dígito puede tener un valor absolutamente final hasta que se haya establecido si un acarreo viene por la derecha o no. Además, si la suma sin un acarreo es 9 (en métodos de lápiz y papel) o 1 (en aritmética binaria), ni siquiera es posible saber si una posición de dígito dada va a transferir un acarreo al posición a su izquierda. En el peor de los casos, cuando una secuencia completa de sumas llega a… 99999999… (en decimal) o… 11111111… (en binario), no se puede deducir nada hasta que se conozca el valor del acarreo que viene de la derecha, y ese acarreo luego se propaga hacia la izquierda, un paso a la vez, ya que cada posición de dígito evalúa "9 + 1 = 0, acarreo 1" o "1 + 1 = 0, acarreo 1". Es la "ondulación" del acarreo de derecha a izquierda lo que le da su nombre y lentitud a un sumador de acarreo ondulado. Al agregar enteros de 32 bits, por ejemplo, se debe tener en cuenta la posibilidad de que un acarreo tenga que ondular a través de cada uno de los 32 sumadores de un bit.

Mirar hacia el futuro

Carry-lookahead depende de dos cosas:

Calculando para cada posición de dígito si esa posición va a propagar un acarreo si uno viene por la derecha.
Combinando estos valores calculados para poder deducir rápidamente si, para cada grupo de dígitos, ese grupo va a propagar un acarreo que viene por la derecha.

Suponiendo que se eligen grupos de cuatro dígitos, la secuencia de eventos es algo como esto:

Todos los sumadores de 1 bit calculan sus resultados. Simultáneamente, las unidades de búsqueda anticipada realizan sus cálculos.
Suponiendo que un acarreo surge en un grupo en particular, ese acarreo emergerá en el extremo izquierdo del grupo dentro de un máximo de cinco retardos de puerta y comenzará a propagarse a través del grupo a su izquierda.
Si ese acarreo se propagará hasta el siguiente grupo, la unidad de búsqueda anticipada ya lo habrá deducido. En consecuencia, antes de que el acarreo emerja del siguiente grupo , la unidad de búsqueda anticipada es inmediatamente (dentro de un retraso de puerta) capaz de decirle al siguiente grupo a la izquierda que va a recibir un acarreo y, al mismo tiempo, decirle al siguiente unidad de anticipación a la izquierda que un carry está en camino.

El efecto neto es que los acarreos comienzan propagándose lentamente a través de cada grupo de 4 bits, como en un sistema de acarreo de ondas, pero luego se mueven cuatro veces más rápido, saltando de una unidad de acarreo de anticipación a la siguiente. Finalmente, dentro de cada grupo que recibe un acarreo, el acarreo se propaga lentamente dentro de los dígitos de ese grupo.

Cuantos más bits haya en un grupo, más compleja se vuelve la lógica de acarreo de anticipación y más tiempo se dedica a las "carreteras lentas" de cada grupo en lugar de a la "ruta rápida" entre los grupos (proporcionada por la lógica de acarreo de anticipación) . Por otro lado, cuantos menos bits haya en un grupo, más grupos deben atravesarse para pasar de un extremo al otro de un número y, como resultado, se obtiene una menor aceleración.

Decidir el tamaño del grupo que se regirá por la lógica de acarreo anticipada requiere un análisis detallado de los retardos de puerta y propagación para la tecnología particular que se está utilizando.

Es posible tener más de un nivel de lógica de acarreo anticipado y, de hecho, esto se suele hacer. Cada unidad de acarreo anticipado ya produce una señal que dice "si un acarreo viene desde la derecha, lo propagaré hacia la izquierda", y esas señales se pueden combinar para que cada grupo de, digamos, cuatro unidades de acarreo anticipado se convierta en parte de un "supergrupo" que gobierna un total de 16 bits de los números que se suman. La lógica de acarreo anticipado del "supergrupo" podrá decir si un acarreo que ingrese al supergrupo se propagará hasta el final y, al usar esta información, podrá propagar acarreos de derecha a izquierda 16 veces más rápido que un ingenuo. llevar ondulación. Con este tipo de implementación de dos niveles, un acarreo puede propagarse primero a través del "camino lento" de sumadores individuales, luego, al llegar al extremo izquierdo de su grupo, propagarse a través del "camino rápido" de búsqueda anticipada de 4 bits. llevar la lógica, luego, al llegar al extremo izquierdo de su supergrupo, propagarse a través del "camino superrápido" de la lógica de búsqueda anticipada de 16 bits.

Nuevamente, los tamaños de grupo que se elegirán dependen de los detalles exactos de la rapidez con la que se propagan las señales dentro de las puertas lógicas y de una puerta lógica a otra.

Para números muy grandes (cientos o incluso miles de bits), la lógica de acarreo anticipado no se vuelve más compleja, porque se pueden agregar más capas de supergrupos y supergrupos según sea necesario. El aumento en el número de puertas también es moderado: si todos los tamaños de grupo son cuatro, uno terminaría con un tercio de unidades de acarreo anticipadas que sumadores. Sin embargo, los "caminos lentos" en el camino hacia los niveles más rápidos comienzan a imponer un freno a todo el sistema (por ejemplo, un sumador de 256 bits podría tener hasta 24 retrasos de puerta en su procesamiento de acarreo), y la mera transmisión física de señales de un extremo de un número largo al otro comienza a ser un problema. En estos tamaños, los sumadores de carry-save son preferibles, ya que no dedican tiempo a la propagación de carry.

Llevar el método de anticipación

Implementación de sumador de 4 bits con avance anticipado

La lógica de acarreo anticipado utiliza los conceptos de generación y propagación de acarreos. Aunque en el contexto de un sumador de acarreo anticipado, es más natural pensar en generar y propagar en el contexto de la suma binaria, los conceptos se pueden usar de manera más general. En las descripciones siguientes, el dígito de la palabra se puede reemplazar por un bit cuando se hace referencia a la suma binaria de 2.

Se dice que la suma de dos entradas A y B de 1 dígito genera si la suma siempre se llevará, independientemente de si hay un acarreo de entrada (de manera equivalente, independientemente de si hay algún dígito menos significativo en la suma). Por ejemplo, en la suma decimal 52 + 67, la suma de los dígitos 5 y 6 de las decenas genera porque el resultado lleva al dígito de las centenas sin importar si el dígito de las unidades lleva; en el ejemplo, el dígito de las unidades no lleva (2 + 7 = 9). Incluso si los números fueran, digamos, 54 y 69, la suma de los dígitos 5 y 6 de las decenas todavía generaría porque el resultado una vez más lleva al dígito de las centenas a pesar de que 4 y 9 crean un acarreo.

En el caso de la suma binaria, genera si y solo si tanto A como B son 1. Si escribimos para representar el predicado binario que es verdadero si y solo si genera, tenemos ${\ Displaystyle A + B}$ ${\ Displaystyle G (A, B)}$ ${\ Displaystyle A + B}$

{\ Displaystyle G (A, B) = A \ cdot B}

donde es una conjunción lógica (es decir, una y ). ${\ Displaystyle A \ cdot B}$

Se dice que la suma de dos entradas A y B de 1 dígito se propaga si la suma se llevará siempre que haya un acarreo de entrada (de manera equivalente, cuando se lleve el siguiente dígito menos significativo de la suma). Por ejemplo, en la suma decimal 37 + 62, la suma de los dígitos 3 y 6 de las decenas se propaga porque el resultado se trasladaría al dígito de las centenas si se llevaran las unidades (que en este ejemplo, no). Tenga en cuenta que propagar y generar se definen con respecto a un solo dígito de suma y no dependen de ningún otro dígito en la suma.

En el caso de la suma binaria, se propaga si y solo si al menos uno de A o B es 1. Si está escrito para representar el predicado binario que es verdadero si y solo si se propaga, uno tiene ${\ Displaystyle A + B}$ ${\ Displaystyle P (A, B)}$ ${\ Displaystyle A + B}$

{\ Displaystyle P (A, B) = A + B}

donde en el lado derecho de la ecuación hay una disyunción lógica (es decir, una o ). ${\ Displaystyle A + B}$

A veces se utiliza una definición ligeramente diferente de propagación . Según esta definición, se dice que A + B se propaga si la adición se llevará siempre que haya un acarreo de entrada, pero no se transmitirá si no hay acarreo de entrada. Debido a la forma en que la lógica de acarreo anticipado usa los bits de generación y propagación, no importa qué definición se use. En el caso de la suma binaria, esta definición se expresa por

{\ Displaystyle P '(A, B) = A \ oplus B}

donde es un exclusivo o (es decir, un xor ). ${\ Displaystyle A \ oplus B}$

${\ Displaystyle A}$	${\ Displaystyle B}$	${\ Displaystyle C_ {i}}$	${\ Displaystyle C_ {o}}$	Tipo de transporte
0	0	0	0	Ninguno
0	0	1	0	Ninguno
0	1	0	0	Ninguno
0	1	1	1	Propagar
1	0	0	0	Ninguno
1	0	1	1	Propagar
1	1	0	1	Generar
1	1	1	1	Generar / Propagar

Tabla que muestra cuándo se propagan o generan los acarreos.

Para aritmética binaria, o es más rápido que xor y requiere menos transistores para implementar. Sin embargo, para un sumador de acarreo anticipado de varios niveles, es más sencillo de usar . ${\ Displaystyle P '(A, B)}$

Dados estos conceptos de generar y propagar, un dígito de suma se lleva precisamente cuando se genera la suma o se lleva el siguiente bit menos significativo y se propaga la suma. Escrito en álgebra booleana, con el bit de acarreo del dígito i , y los bits de propagación y generación del dígito i respectivamente, ${\ Displaystyle C_ {i}}$ ${\ Displaystyle P_ {i}}$ ${\ Displaystyle G_ {i}}$

{\ Displaystyle C_ {i + 1} = G_ {i} + (P_ {i} \ cdot C_ {i}).}

Detalles de implementacion

Para cada bit en una secuencia binaria que se agregue, la lógica de acarreo anticipado determinará si ese par de bits generará un acarreo o propagará un acarreo. Esto permite que el circuito "procese previamente" los dos números que se agregan para determinar el acarreo con anticipación. Luego, cuando se realiza la adición real, no hay demora en esperar el efecto de acarreo de ondulación (o el tiempo que tarda el acarreo del primer sumador completo en pasar al último sumador completo). A continuación se muestra un circuito simple de acarreo anticipado generalizado de 4 bits que se combina con el sumador de acarreo de ondulación de 4 bits que usamos anteriormente con algunos ajustes leves:

Para el ejemplo proporcionado, la lógica para los valores generate ( ) y propagate ( ) se da a continuación. El valor numérico determina la señal del circuito de arriba, comenzando desde 0 en el extremo derecho hasta 3 en el extremo izquierdo: ${\ Displaystyle G}$ ${\ Displaystyle P}$

{\ Displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0},}

{\ Displaystyle C_ {2} = G_ {1} + P_ {1} \ cdot C_ {1},}

{\ Displaystyle C_ {3} = G_ {2} + P_ {2} \ cdot C_ {2},}

{\ Displaystyle C_ {4} = G_ {3} + P_ {3} \ cdot C_ {3}.}

Sustituir en , luego en , luego en produce las siguientes ecuaciones expandidas: ${\ Displaystyle C_ {1}}$ ${\ Displaystyle C_ {2}}$ ${\ Displaystyle C_ {2}}$ ${\ Displaystyle C_ {3}}$ ${\ Displaystyle C_ {3}}$ ${\ Displaystyle C_ {4}}$

{\ Displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0},}

{\ Displaystyle C_ {2} = G_ {1} + G_ {0} \ cdot P_ {1} + C_ {0} \ cdot P_ {0} \ cdot P_ {1},}

{\ Displaystyle C_ {3} = G_ {2} + G_ {1} \ cdot P_ {2} + G_ {0} \ cdot P_ {1} \ cdot P_ {2} + C_ {0} \ cdot P_ {0 } \ cdot P_ {1} \ cdot P_ {2},}

{\ Displaystyle C_ {4} = G_ {3} + G_ {2} \ cdot P_ {3} + G_ {1} \ cdot P_ {2} \ cdot P_ {3} + G_ {0} \ cdot P_ {1 } \ cdot P_ {2} \ cdot P_ {3} + C_ {0} \ cdot P_ {0} \ cdot P_ {1} \ cdot P_ {2} \ cdot P_ {3}.}

Para determinar si un par de bits generará un acarreo, la siguiente lógica funciona:

{\ Displaystyle G_ {i} = A_ {i} \ cdot B_ {i}.}

Para determinar si un par de bits propagará un acarreo, funciona cualquiera de las siguientes declaraciones lógicas:

{\ Displaystyle P_ {i} = A_ {i} \ oplus B_ {i},}

{\ Displaystyle P_ {i} = A_ {i} + B_ {i}.}

La razón por la que esto funciona se basa en la evaluación de . La única diferencia en las tablas de verdad entre ( ) y ( ) es cuando ambos y son 1. Sin embargo, si ambos y son 1, entonces el término es 1 (ya que su ecuación es ) y el término se vuelve irrelevante. El XOR se usa normalmente dentro de un circuito sumador completo básico; el OR es una opción alternativa (solo para una búsqueda anticipada), que es mucho más simple en términos de recuento de transistores. ${\ Displaystyle C_ {1} = G_ {0} + P_ {0} \ cdot C_ {0}}$ ${\ Displaystyle A \ oplus B}$ ${\ Displaystyle A + B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle G_ {0}}$ ${\ Displaystyle A \ cdot B}$ ${\ Displaystyle P_ {0} \ cdot C_ {0}}$

El sumador de 4 bits de acarreo anticipado también se puede utilizar en un circuito de nivel superior haciendo que cada circuito lógico CLA produzca una señal de propagación y generación a un circuito lógico CLA de nivel superior. El grupo propagate ( ) y el grupo generate ( ) para un CLA de 4 bits son: ${\ Displaystyle PG}$ ${\ displaystyle GG}$

{\ Displaystyle PG = P_ {0} \ cdot P_ {1} \ cdot P_ {2} \ cdot P_ {3},}

{\ Displaystyle GG = G_ {3} + G_ {2} \ cdot P_ {3} + G_ {1} \ cdot P_ {3} \ cdot P_ {2} + G_ {0} \ cdot P_ {3} \ cdot P_ {2} \ cdot P_ {1}.}

A continuación, se pueden utilizar para crear una ejecución para ese grupo de 4 bits en particular:

{\ Displaystyle CG = GG + PG \ cdot C_ {in}.}

Se puede ver que esto es equivalente a en ecuaciones anteriores. ${\ Displaystyle C_ {4}}$

Al juntar cuatro CLA de 4 bits se obtienen cuatro grupos de propagación y cuatro grupos de generación. Una unidad de transporte anticipado (LCU) toma estos 8 valores y utiliza una lógica idéntica para calcular en los CLA. Luego, la LCU genera la entrada de acarreo para cada uno de los 4 CLA y un quinto igual a . ${\ Displaystyle C_ {i}}$ ${\ Displaystyle C_ {16}}$

El cálculo del retardo de puerta de un sumador de 16 bits (usando 4 CLA y 1 LCU) no es tan sencillo como el sumador de acarreo de rizado.

Comenzando en el momento de cero:

el cálculo de y se realiza en el momento 1, ${\ Displaystyle P_ {i}}$ ${\ Displaystyle G_ {i}}$
el cálculo de se realiza en el momento 3, ${\ Displaystyle C_ {i}}$
el cálculo del se realiza en el momento 2, ${\ Displaystyle PG}$
el cálculo del se realiza en el momento 3, ${\ displaystyle GG}$
El cálculo de las entradas para los CLA de la LCU se realiza en:
- tiempo 0 para el primer CLA,
- tiempo 5 para el segundo, tercer y cuarto CLA,
el cálculo de los se realiza en: ${\ Displaystyle S_ {i}}$ $Si}$
- tiempo 4 para el primer CLA,
- tiempo 8 para el segundo, tercer y cuarto CLA,
el cálculo del bit de acarreo final ( ) se realiza en el momento 5. ${\ Displaystyle C_ {16}}$

El tiempo máximo es de 8 retardos de puerta (para ). ${\ Displaystyle S _ {[8-15]}}$

Un sumador de acarreo de ondulación estándar de 16 bits tomaría 16 × 3 - 1 = 47 retardos de puerta.

Cadena de transporte Manchester

La cadena de acarreo de Manchester es una variación del sumador de acarreo anticipado que usa lógica compartida para reducir el recuento de transistores. Como se puede ver arriba en la sección de implementación, la lógica para generar cada acarreo contiene toda la lógica utilizada para generar los acarreos anteriores. Una cadena de acarreo de Manchester genera los acarreos intermedios al tocar los nodos en la puerta que calcula el valor de acarreo más significativo. Sin embargo, no todas las familias lógicas tienen estos nodos internos, siendo CMOS un ejemplo importante. La lógica dinámica puede admitir la lógica compartida, al igual que la lógica de la puerta de transmisión . Una de las principales desventajas de la cadena de acarreo de Manchester es que la carga capacitiva de todas estas salidas, junto con la resistencia de los transistores, hace que el retardo de propagación aumente mucho más rápidamente que un avance de acarreo regular. Una sección de cadena de transporte Manchester generalmente no excede los 4 bits.

Ver también

Referencias

Otras lecturas

Algoritmos de hardware para módulos aritméticos , grupo de investigación ARITH, Aoki lab., Universidad de Tohoku
Katz, Randy (1994). Diseño de lógica contemporánea . Revista de microelectrónica . 26 . The Benjamin / Cummings Publishing Company . págs. 249-256 . doi : 10.1016 / 0026-2692 (95) 90052-7 . ISBN 0-8053-2703-7.
Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .

enlaces externos

Simulador de JavaScript Carry Look Ahead Adder

Languages

In other projects