Sumador de anticipación

Circuito lógico aritmético

Un sumador de anticipación ( CLA ) o sumador rápido es un tipo de sumador electrónico utilizado en lógica digital. Un sumador de anticipación de acarreo mejora la velocidad al reducir la cantidad de tiempo necesario para determinar los bits de acarreo. Se puede contrastar con el sumador de acarreo 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 propio. bit de suma y bit de acarreo. El sumador de 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 en el rendimiento impuesta por el transporte de ondas utilizado en su motor diferencial y posteriormente diseñó mecanismos para anticipar el transporte para su motor analítico, nunca construido . ^{[1] [2] Se cree que} Konrad Zuse implementó el primer sumador de anticipación en su computadora mecánica binaria de la década de 1930, la Zuse Z1 . ^[3] Gerald B. Rosenberger de IBM solicitó una patente sobre un moderno sumador binario de anticipación en 1957. ^[4]

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

Teoría de operación

Adición de ondulación

Un sumador binario de ondulación y acarreo funciona de la misma manera que la mayoría de los métodos de suma de lápiz y papel. Comenzando en la posición del dígito más a la derecha ( menos significativa ), se suman los dos dígitos correspondientes y se obtiene un resultado. Puede ocurrir una "realización" si el resultado requiere un dígito más alto; por ejemplo, "9 + 5 = 4, lleva 1". La aritmética binaria funciona de la misma manera, con menos dígitos. En este caso, sólo hay cuatro operaciones posibles, 0+0, 0+1, 1+0 y 1+1; el caso 1+1 genera un acarreo. En consecuencia, todas las posiciones de los dígitos, excepto la que está más a la derecha, deben esperar la posibilidad de tener que agregar un 1 adicional al llevar los dígitos una posición a la derecha.

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

Mirar hacia el futuro

El carry-lookahead depende de dos cosas:

1. Calcular para cada posición de dígito si esa posición propagará un acarreo si uno entra por la derecha.
2. 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.

Supongamos que se eligen grupos de cuatro dígitos. La secuencia de eventos sería así:

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

El efecto neto es que los acarreos comienzan propagándose lentamente a través de cada grupo de 4 bits, tal como en un sistema de acarreo ondulado, pero luego se mueven cuatro veces más rápido, saltando de una unidad de acarreo anticipado 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 anticipado y más tiempo se dedica a las "vías lentas" de cada grupo en lugar de a la "vía rápida" entre los grupos (proporcionada por la lógica de acarreo anticipado). . Por otro lado, cuantos menos bits haya en un grupo, más grupos habrá que atravesar para llegar de un extremo al otro de un número y, como resultado, se obtendrá menos aceleración.

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

Es posible tener más de un nivel de lógica de anticipación y acarreo y, de hecho, esto suele hacerse. Cada unidad de anticipación de acarreo ya produce una señal que dice "si un acarreo llega desde la derecha, lo propagaré hacia la izquierda", y esas señales se pueden combinar de modo que cada grupo de, digamos, cuatro unidades de anticipación de acarreo se convierta en parte de un "supergrupo" que gobierna un total de 16 bits de los números que se van sumando. La lógica de acarreo anticipado del "supergrupo" podrá decir si un acarreo que ingresa al supergrupo se propagará a través de él y, utilizando esta información, podrá propagar acarreos de derecha a izquierda 16 veces más rápido que un ingenuo. transporte de ondas. Con este tipo de implementación de dos niveles, un acarreo puede propagarse primero a través del "camino lento" de sumadores individuales y luego, al llegar al extremo izquierdo de su grupo, propagarse a través del "camino rápido" de anticipación de 4 bits. lleva lógica, luego, al llegar al extremo izquierdo de su supergrupo, se propaga a través del "camino superrápido" de la lógica de acarreo anticipado de 16 bits.

Nuevamente, los tamaños de grupo que se elegirán dependen de los detalles exactos de qué tan rápido 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 supersupergrupos 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 anticipado que sumadores. Sin embargo, los "caminos lentos" en el camino hacia los niveles más rápidos comienzan a imponer un lastre 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 al otro de un número largo comienza a ser un problema. En estos tamaños, son preferibles los sumadores de ahorro de acarreo , ya que no dedican ningún tiempo a la propagación del acarreo.

Llevar el método de anticipación

La lógica de anticipación del acarreo utiliza los conceptos de generación y propagación de acarreos. Aunque en el contexto de un sumador de acarreo anticipado, lo más natural es 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, la palabra dígito se puede reemplazar por bit cuando se hace referencia a la suma binaria de 2.

Se dice que la suma de dos entradas de 1 dígito A y B genera si la suma siempre se llevará, independientemente de si hay un acarreo de entrada (de manera equivalente, independientemente de si se llevan dígitos menos significativos en la suma). Por ejemplo, en la suma decimal 52 + 67, la suma de los dígitos de las decenas 5 y 6 se genera porque el resultado se lleva al dígito de las centenas independientemente de 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 de las decenas 5 y 6 aún 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 A y 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, an y ). ${\displaystyle A\cdot B}$

Se dice que la suma de dos entradas de 1 dígito A y B se propaga si la suma se lleva a cabo siempre que haya un acarreo de entrada (de manera equivalente, cuando se acarrea el siguiente dígito menos significativo en la suma). Por ejemplo, en la suma decimal 37 + 62, la suma de los dígitos de las decenas 3 y 6 se propaga porque el resultado se trasladaría al dígito de las centenas si las unidades se llevaran (lo cual, en este ejemplo, no es así). Tenga en cuenta 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 en la suma.

En el caso de la suma binaria, se propaga si y sólo si al menos uno de A o B es 1. If se escribe para representar el predicado binario que es verdadero si y sólo si se propaga, se 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 propagar . Según esta definición, se dice que A + B se propaga si la suma se llevará siempre que haya un acarreo de entrada, pero no se propagará si no hay acarreo de entrada. 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 por

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

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

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

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

Dados estos conceptos de generación y propagación, un dígito de suma se transporta precisamente cuando la suma genera o el siguiente bit menos significativo se transporta y la suma se propaga. 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

Un sumador completo parcial , con salidas de propagación y generación.

Implementación de puerta lógica de un sumador de anticipación de acarreo de 4 bits.

Un diagrama de bloques de un sumador de anticipación de acarreo de 4 bits.

Para cada bit que se agregue en una secuencia binaria, la lógica de anticipación del acarreo 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 suman para determinar el acarreo con anticipación. Luego, cuando se realiza la suma real, no hay demora por esperar el efecto de acarreo dominó (o el tiempo que tarda el acarreo desde el primer sumador completo en pasar al último sumador completo).

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 declaraciones 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 . 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 utiliza normalmente dentro de un circuito sumador completo básico; el OR es una opción alternativa (solo para anticipación de acarreo), 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}}$

Para el ejemplo proporcionado, la lógica para los valores de generación ( ) y propagación ( ) se proporciona 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}}$

Sustituyendo en , luego en , luego en se obtienen 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}}$

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 propagación y genere una señal a un circuito lógico CLA de nivel superior. El grupo propagar ( ) y el grupo generar ( ) 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}}$

Luego se pueden utilizar para crear una transferencia para ese grupo de 4 bits en particular:

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

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

Al juntar cuatro CLA de 4 bits se obtienen cuatro propagaciones de grupo y cuatro generaciones de grupo. Una unidad de anticipación de acarreo (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 una quinta igual a . ${\displaystyle C_{i}}$ ${\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 sumador de acarreo rizado.

A partir del momento 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 2, ${\displaystyle PG}$
• el cálculo del se realiza en el momento 3, ${\displaystyle GG}$
• El cálculo de los insumos 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 del se realiza en: ${\displaystyle S_{i}}$
  • 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 retrasos de puerta (para ). ${\displaystyle S_{[8-15]}}$

Un sumador de acarreo rizado estándar de 16 bits necesitaría 16 × 2 − 1 = 31 retrasos de puerta.

Expansión

Este ejemplo es un sumador anticipado de acarreo de 4 bits, hay 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 Y B0) O ((A0 XOR B0) Y Cin)) '4dt S2 = (A2 XOR B2) XOR ((A1 Y B1) O ((A1 XOR B1) Y (A0 Y B0)) O ((A1 XOR B1) Y (A0 XOR B0) Y Cin)) '4dtS3 = (A3 XOR B3) XOR ((A2 Y B2) O ((A2 XOR B2) Y (A1 Y B1)) O ((A2 XOR B2) Y (A1 XOR B1) Y (A0 Y B0)) O ((A2 XOR B2) Y (A1 XOR B1) Y (A0 XOR B0) Y Cin)) '4dtSalida = (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 0Ginebra = Cin '0dtP00 = A0 XOR B0 '1dtG00 = A0 Y B0 '1dtP10 = A1 XOR B1 '1dtG10 = A1 Y B1 '1dtP20 = A2 XOR B2 '1dtG20 = A2 Y B2 '1dtP30 = A3 XOR B3 '1dtG30 = A3 Y B3 '1dt'Paso 1G01 = G00 O_ P00 Y Gin '3dt, C0, valencia-2G11 = G10 O_ P10 Y G00 O_ P10 Y P00 Y Gin '3dt, C1, valencia-3G21 = G20 O_ P20 Y G10 O_ P20 Y P10 Y G00 O_ P20 Y P10 Y P00 Y Gin '3dt, C2, valencia-4G31 = 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'SumaS0 = P00 XOR Gin '2dtS1 = P10 XOR G01 '4dtS2 = P20 XOR G11 '4dtS3 = P30 XOR G21 '4dtS4 = G31 '3dt, Salida

Cadena de transporte Manchester

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 acarreos intermedios desconectando 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 retraso de propagación aumente mucho más rápidamente que una anticipación de acarreo normal. Una sección de la cadena de transporte Manchester generalmente no supera los 4 bits.

Ver también

• Sumador de acarreo y salto
• llevar operador
• Ejecución especulativa

Referencias

1. "Motor analítico - Historia del motor analítico Charles Babbage". historia-computadora.com . 4 de enero de 2021 . Consultado el 19 de junio de 2021 .
2. Babbage, Charles (1864). Pasajes de la vida de un filósofo. Londres: Longman, Green, Longmand Roberts & Green. págs. 59–63, 114–116.
3. Rojas, Raúl (7 de junio de 2014). "El Z1: arquitectura y algoritmos de la primera computadora de Konrad Zuse". arXiv : 1406.1886 [cs.AR].
4. Rosenberger, Gerald B. (27 de diciembre de 1960). "Sumador de transporte simultáneo". Patente estadounidense 2.966.305.
5. "Sumdora de cadena de transporte de Manchester - WikiChip". es.wikichip.org . Consultado el 24 de abril de 2017 .

Otras lecturas

• Algoritmos de hardware para módulos aritméticos, grupo de investigación ARITH, laboratorio Aoki, Universidad de Tohoku
• Katz, Randy (1994). Diseño de lógica contemporánea . vol. 26. Compañía editorial Benjamin/Cummings . págs. 249-256. doi :10.1016/0026-2692(95)90052-7. ISBN 0-8053-2703-7. {{cite book}}: |journal=ignorado ( ayuda )
• Savard, John JG (2018) [2006]. "Técnicas Aritméticas Avanzadas". cuadribloc . 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