sumador de anticipación de acarreo

Un sumador con anticipación de acarreo ( CLA ) o sumador rápido es un tipo de sumador electrónico utilizado en lógica digital. Este tipo de sumador mejora la velocidad al reducir el tiempo necesario para determinar los bits de acarreo. Se diferencia del sumador de acarreo en cascada (RCA), más simple pero generalmente más lento, en el que el bit de acarreo se calcula junto con el bit de suma, y ​​cada etapa debe esperar a que se haya calculado el bit de acarreo anterior para comenzar a calcular su propio bit de suma y bit de acarreo. El sumador con anticipación de acarreo 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 del siglo XIX, Charles Babbage reconoció la penalización de rendimiento impuesta por el acarreo en cascada utilizado en su máquina diferencial y, posteriormente, diseñó mecanismos para anticipar el acarreo para su máquina analítica , que nunca llegó a construir . ^{[ 1 ] [ 2 ]} Se cree que Konrad Zuse implementó el primer sumador con anticipación de acarreo en su computadora mecánica binaria de la década de 1930, la Zuse Z1 . ^{[ 3 ]} Gerald B. Rosenberger de IBM solicitó una patente para un sumador binario moderno con anticipación de acarreo en 1957. ^{[ 4 ]}

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

La lógica de anticipación de acarreo utiliza los conceptos de generación y propagación de acarreos. Si bien en el contexto de un sumador de anticipación de acarreo lo más natural es pensar en la generación y propagación en el contexto de la suma binaria, estos conceptos pueden usarse de forma más general. En las descripciones siguientes, la palabra «dígito» puede sustituirse por «bit» al referirse a la suma binaria de 2.

Se dice que la suma de dos entradas de un dígito A y B genera un acarreo si la suma siempre lleva un acarreo, independientemente de si hay un acarreo de entrada (o, equivalentemente, independientemente de si algún dígito menos significativo en la suma lleva un acarreo). Por ejemplo, en la suma decimal 52 + 67, la suma de los dígitos de las decenas 5 y 6 genera un acarreo porque el resultado lleva un acarreo a la cifra de las centenas, independientemente de si la cifra de las unidades lleva un acarreo; en el ejemplo, la cifra de las unidades no lleva un acarreo (2 + 7 = 9). Incluso si los números fueran, digamos, 54 y 69, la suma de los dígitos de las decenas 5 y 6 seguiría generando un acarreo porque el resultado, una vez más, lleva un acarreo a la cifra de las centenas independientemente de que 4 y 9 creen un acarreo.

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

${\displaystyle G(A,B)=A\cdot B}$

dónde${\displaystyle A\cdot B}$es un y .

Se dice que la suma de dos dígitos A y B se propaga si el resultado se propaga siempre que haya un acarreo en la entrada (o, lo que es lo mismo, cuando el dígito menos significativo de la suma se propaga). Por ejemplo, en la suma decimal 37 + 62, la suma de las decenas 3 y 6 se propaga porque el resultado se propagaría hasta las centenas si las unidades se propagaran (lo cual no ocurre en este ejemplo). Cabe destacar que "propagar" y "generar" se definen con respecto a un solo dígito de la suma y no dependen de ningún otro dígito de la misma.

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

${\displaystyle P(A,B)=A+B}$

dónde${\displaystyle A+B}$en el lado derecho de la ecuación hay un o .

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 suma produce un acarreo siempre que haya un acarreo de entrada, pero no lo produce si no lo hay. Debido a la forma en que la lógica de anticipación de acarreo utiliza los bits de generación y propagación, no importa qué definición se utilice. En el caso de la suma binaria, esta definición se expresa mediante

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

dónde${\displaystyle A\oplus B}$es un xor .

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

Para la aritmética binaria, OR es más rápido que XOR y requiere menos transistores para su implementación. Sin embargo, para un sumador de anticipación de acarreo de múltiples niveles, es más sencillo usar${\displaystyle P'(A,B)}$.

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

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

Para cada bit de una secuencia binaria que se va a sumar, la lógica de anticipación de acarreo determinará si ese par de bits generará o propagará un acarreo. Esto permite que el circuito "preprocese" los dos números que se van a sumar para determinar el acarreo con antelación. De esta forma, cuando se realiza la suma, no hay demora por la espera del efecto de propagación del acarreo (o el tiempo que tarda el acarreo del primer sumador completo en pasarse al último).

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

${\displaystyle G_{i}=A_{i}\cdot B_{i}}$

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

${\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${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0}}$. La única diferencia en las tablas de verdad entre (${\displaystyle A\oplus B}$) y (${\displaystyle A+B}$) es cuando ambos${\displaystyle A}$y${\displaystyle B}$son 1. Sin embargo, si ambos${\displaystyle A}$y${\displaystyle B}$son 1, entonces el${\displaystyle G_{0}}$El término es 1 (ya que su ecuación es${\displaystyle A\cdot B}$), y el${\displaystyle P_{0}\cdot C_{0}}$El término se vuelve irrelevante. La compuerta XOR se usa normalmente dentro de un circuito sumador completo básico; la compuerta OR es una opción alternativa (solo para anticipación de acarreo), que es mucho más simple en términos de cantidad de transistores.

Para el ejemplo proporcionado, la lógica para generar (${\displaystyle G}$) y propagar (${\displaystyle P}$Los valores se muestran a continuación. El valor numérico determina la señal del circuito anterior, comenzando desde 0 en el extremo derecho hasta 3 en el extremo izquierdo:

${\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}}$

Sustituyendo${\displaystyle C_{1}}$en${\displaystyle C_{2}}$, entonces${\displaystyle C_{2}}$en${\displaystyle C_{3}}$, entonces${\displaystyle C_{3}}$en${\displaystyle C_{4}}$produce las siguientes ecuaciones expandidas:

${\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}}$

El sumador de 4 bits con anticipación de acarreo 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 propaga (${\displaystyle PG}$) y generar grupo (${\displaystyle GG}$) para un CLA de 4 bits son:

${\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}}$

Luego se pueden usar para crear un acarreo para ese grupo particular de 4 bits:

${\displaystyle CG=GG+PG\cdot C_{in}}$

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

Al juntar cuatro CLA de 4 bits se obtienen cuatro propagaciones de grupo y cuatro generaciones de grupo. Una unidad de acarreo anticipado (LCU) toma estos 8 valores y utiliza una lógica idéntica para calcular${\displaystyle C_{i}}$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_{16}}$.

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

Comenzando en el tiempo cero:

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

El tiempo máximo es de 8 retardos de puerta (para${\displaystyle S_{[4-15]}}$).

Un sumador estándar de 16 bits con acarreo en cascada requeriría 16 × 2 − 1 = 31 retardos de puerta.

Este ejemplo es un sumador de anticipación de acarreo de 4 bits, tiene 5 salidas. A continuación se muestra la expansión:

S0 = ( A0 XOR B0 ) XOR Cin '2dt (dt - tiempo de retardo)S1 = ( A1 XOR B1 ) XOR (( A0 AND B0 ) OR (( A0 XOR B0 ) AND Cin )) '4dt S2 = ( A2 XOR B2 ) XOR (( A1 AND B1 ) OR (( A1 XOR B1 ) AND ( A0 AND B0 )) OR (( A1 XOR B1 ) AND ( A0 XOR B0 ) AND Cin )) '4dtS3 = ( A3 XOR B3 ) XOR (( A2 AND B2 ) OR (( A2 XOR B2 ) AND ( A1 AND B1 )) OR (( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 AND B0 )) OR (( A2 XOR B2 ) AND ( A1 XOR B1 ) AND ( A0 XOR B0 ) AND Cin )) '4dtCout = ( A3 Y B3 ) O (( A3 XOR B3 ) Y ( A2 Y B2 )) O (( A3 XOR B3 ) Y ( A2 XOR B2 ) Y ( A1 Y B1 )) O (( A3 XOR B3 ) Y ( A2 XOR B2 ) Y ( A1 XOR B1 ) Y ( A0 Y B0 )) O (( A3 XOR B3 ) Y ( A2 XOR B2 ) Y ( A1 XOR B1 ) Y ( A0 XOR B0 ) Y Cin ) '3dt

Sumador de anticipación de acarreo de 4 bits más simple:

'Paso 0 Gin = Cin '0dt P00 = A0 XOR B0 '1dt G00 = A0 AND B0 '1dt P10 = A1 XOR B1 '1dt G10 = A1 AND B1 '1dt P20 = A2 XOR B2 '1dt G20 = A2 AND B2 '1dt P30 = A3 XOR B3 '1dt G30 = A3 AND B3 '1dt 'Paso 1 G01 = G00 OR P00 AND Gin '3dt, C0, valencia-2 G11 = G10 OR P10 AND G00 OR P10 AND P00 AND Gin '3dt, C1, valencia-3 G21 = G20 OR P20 AND G10 OR P20 AND P10 AND G00 OR P20 AND P10 AND P00 AND Gin '3dt, C2, valencia-4 G31 = G30 O P30 Y G20 O P30 Y P20 Y G10 O P30 Y P20 Y P10 Y G00 O P30 Y P20 Y P10 Y P00 Y Gin '3dt, C3, valencia-5 'Suma S0 = P00 XOR Gin '2dt S1 = P10 XOR G01 '4dt S2 = P20 XOR G11 '4dt S3 = P30 XOR G21 '4dt S4 = G31 '3dt, Cout

La cadena de acarreo de Manchester es una variación del sumador de anticipación de acarreo ^{[ 5 ]} que utiliza lógica compartida para reducir el número 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 tomando 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 lógica compartida, al igual que la lógica de 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 en una anticipación de acarreo regular. Una sección de cadena de acarreo de Manchester generalmente no supera los 4 bits.

• sumador de salto de acarreo
• Operador de transporte
• Ejecución especulativa

• Algoritmos de hardware para módulos aritméticos. Archivado el 9 de abril de 2007 en Wayback Machine , grupo de investigación ARITH, laboratorio Aoki, Universidad de Tohoku.
• Katz, Randy (1994). «Diseño lógico contemporáneo» . Microelectronics Journal . 26 (5). The Benjamin/Cummings Publishing Company : 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 del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .

• Simulador JavaScript de sumador de anticipación de acarreo