Sumador con acarreo anticipado

Circuito lógico aritmético

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 necesario para determinar los bits de acarreo. Se puede contrastar con el sumador de acarreo de ondulación (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 su propio bit de suma y bit de acarreo. 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 del siglo XIX, Charles Babbage reconoció la penalización del rendimiento impuesta por el acarreo de ondulación utilizado en su máquina diferencial y, posteriormente, diseñó mecanismos para anticipar el acarreo para su máquina analítica nunca construida . ^{[1] [2] Se cree que} Konrad Zuse implementó el primer sumador de acarreo-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 para un sumador binario de acarreo-anticipación moderno en 1957. ^[4]

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

Teoría del funcionamiento

Adición de ondulación

Un sumador binario de acarreo por ondulación funciona de la misma manera que la mayoría de los métodos de suma con lápiz y papel. Comenzando por 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. Puede ocurrir un "acarreo" si el resultado requiere un dígito más alto; por ejemplo, "9 + 5 = 4, acarreo 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 caso 1+1 genera un acarreo. En consecuencia, todas las posiciones de dígitos que no sean la más a la derecha deben esperar la posibilidad de tener que agregar un 1 adicional a partir de un acarreo en los 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 hay o no un acarreo que viene de la derecha. Además, si la suma sin acarreo es el valor más alto en la base (9 en métodos de lápiz y papel en base 10 o 1 en aritmética binaria), no es posible saber si una posición de dígito dada va a pasar o no un acarreo a la posición de 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 en absoluto hasta que se conozca el valor del acarreo que viene de la derecha; ese acarreo debe propagarse hacia la izquierda, un paso a la vez, a medida 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 al sumador de ondulación-acarreo su nombre y lentitud. Al sumar números 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 adelante

El carry lookahead depende de dos cosas:

1. Calcular para cada posición de dígito si esa posición va a propagar un acarreo si uno entra desde la derecha.
2. Combinando estos valores calculados se puede deducir rápidamente si, para cada grupo de dígitos, ese grupo va a propagar un acarreo que viene desde la derecha.

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

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 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 hacia su izquierda.
3. Si ese acarreo se va a propagar a través del siguiente grupo, la unidad de anticipación ya lo habrá deducido. Por lo tanto, antes de que el acarreo emerja del siguiente grupo , la unidad de anticipación puede inmediatamente (dentro de un retardo de puerta) decirle al siguiente grupo a la izquierda que va a recibir un acarreo y, al mismo tiempo, decirle a la 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, como en un sistema de acarreo de ondulación, 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, este se propaga lentamente dentro de los dígitos de ese grupo.

Cuantos más bits haya en un grupo, más compleja se torna la lógica de acarreo anticipado y más tiempo se pasa en las "rutas lentas" de cada grupo en lugar de en la "ruta 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 se deben recorrer para llegar de un extremo de un número al otro y, como resultado, se obtiene menos aceleración.

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

Es posible tener más de un nivel de lógica de acarreo anticipado, y de hecho esto se hace habitualmente. Cada unidad de acarreo anticipado ya produce una señal que dice "si un acarreo viene de la derecha, lo propagaré a la izquierda", y esas señales se pueden combinar de modo 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 entra en el 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 acarreo de ondulación ingenuo. Con este tipo de implementación de dos niveles, un acarreo puede primero propagarse a través de la "ruta lenta" de sumadores individuales, luego, al llegar al extremo izquierdo de su grupo, propagarse a través de la "ruta rápida" de la lógica de acarreo de anticipación de 4 bits, luego, al llegar al extremo izquierdo de su supergrupo, propagarse a través de la "ruta superrápida" de la lógica de acarreo de anticipación de 16 bits.

Nuevamente, los tamaños de grupo a elegir 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 lookahead-carry 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 las unidades de lookahead carry que hay sumadores. Sin embargo, los "caminos lentos" en el camino hacia los niveles más rápidos comienzan a imponer un lastre en todo el sistema (por ejemplo, un sumador de 256 bits podría tener hasta 24 demoras de puerta en su procesamiento de carry), y la mera transmisión física de señales desde 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 gastan tiempo en la propagación del carry en absoluto.

Método de look-ahead de carry

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 lo más natural es pensar en la generación y propagación en el contexto de la suma binaria, los conceptos se pueden utilizar de forma más general. En las descripciones que aparecen a continuación, la palabra dígito se puede sustituir 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 lleva a cabo, independientemente de si hay un acarreo de entrada (equivalentemente, independientemente de si hay o no 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 genera porque el resultado se lleva al dígito de las centenas independientemente de si se lleva o no el dígito de las unidades; en el ejemplo, el dígito de las unidades no se 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 se generaría de todos modos porque el resultado se lleva una vez más al dígito de las centenas independientemente de que 4 y 9 creen un acarreo.

En el caso de la adición 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, un 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 (equivalentemente, cuando se lleva a cabo 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 llevaría al dígito de las centenas si se llevaran a cabo los dígitos de las unidades (lo que en este ejemplo no ocurre). 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 adición binaria, se propaga si y solo si al menos uno de A o B es 1. Si se escribe para representar el predicado binario que es verdadero si y solo 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 propagación . Según esta definición, se dice que A + B se propaga si la suma se acarreará siempre que haya un acarreo de entrada, pero no se acarreará si no hay acarreo de entrada. Debido a la forma en que la lógica de acarreo-búsqueda anticipada 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}$

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

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 implementarse. Sin embargo, para un sumador de acarreo con anticipación de varios niveles, es más sencillo utilizar . ${\displaystyle P'(A,B)}$

Dados estos conceptos de generar y propagar, un dígito de adición se transmite precisamente cuando la adición genera o el siguiente bit menos significativo se transmite y la adición se propaga. Escrito en álgebra booleana, con el bit de acarreo del dígito i , y 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 implementación

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

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

Diagrama de bloques de un sumador con acarreo anticipado de 4 bits.

Para cada bit de una secuencia binaria que se va a sumar, la lógica de acarreo anticipado determinará si ese par de bits generará un acarreo o lo propagará. Esto permite que el circuito "preprocese" 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 dominó del acarreo (o el tiempo que tarda el acarreo del primer sumador completo en pasarse 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, funciona cualquiera de las siguientes afirmaciones 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 utiliza normalmente dentro de un circuito sumador completo básico; el OR es una opción alternativa (solo para un acarreo-lookahead), que es mucho más simple en términos de conteo 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 generar ( ) y propagar ( ) se muestra 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 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 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 para un circuito lógico CLA de nivel superior. El grupo de propagación ( ) y el grupo de generación ( ) 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 un carryout para ese grupo particular de 4 bits:

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

Se puede ver que esto es equivalente a 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 acarreo 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 compuerta de un sumador de 16 bits (que utiliza 4 CLA y 1 LCU) no es tan sencillo como el sumador de acarreo de rizado.

Comenzando en el tiempo cero:

• El cálculo de y se realiza en el momento 1, ${\displaystyle P_{i}}$ ${\displaystyle G_{i}}$
• El cálculo se realiza en el momento 2, ${\displaystyle PG}$
• El cálculo se realiza en el momento 3, ${\displaystyle GG}$
• 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,
• El cálculo del se realiza en: ${\displaystyle S_{i}}$
  • hora 4 para el primer CLA,
  • tiempo 8 para el segundo, tercero 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 × 2 − 1 = 31 retrasos de compuerta.

Expansión

Este ejemplo es un sumador de acarreo anticipado de 4 bits, con 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)) '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 acarreo con previsión de 4 bits más simple:

'Paso 0Ginebra = Cin '0dtP00 = A0 O B0 '1dtG00 = A0 Y B0 '1dtP10 = A1 O B1 '1dtG10 = A1 Y B1 '1dtP20 = A2 O B2 '1dtG20 = A2 Y B2 '1dtP30 = A3 O 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 O G01 '4dtS2 = P20 O G11 '4dtS3 = P30 O G21 '4dtS4 = G31 '3dt, corte

Cadena de transporte Manchester

La cadena de acarreo Manchester es una variación del sumador de acarreo anticipado ^[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 Manchester genera los acarreos intermedios al extraer nodos de la compuerta 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 compuerta de transmisión . Una de las principales desventajas de la cadena de acarreo 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 acarreo anticipado regular. Una sección de cadena de acarreo Manchester generalmente no supera los 4 bits.

Véase también

• Sumador de acarreo y salto
• Operador de transporte
• Ejecución especulativa

Referencias

1. "Máquina analítica - Historia de la máquina analítica de Charles Babbage". history-computer.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, Raul (7 de junio de 2014). "El Z1: Arquitectura y algoritmos del primer computador de Konrad Zuse". arXiv : 1406.1886 [cs.AR].
4. Rosenberger, Gerald B. (27 de diciembre de 1960). "Sumador de acarreo simultáneo". Patente estadounidense 2.966.305.
5. "Sumador de cadena de transporte Manchester - WikiChip". en.wikichip.org . Consultado el 24 de abril de 2017 .

Lectura adicional

• Algoritmos de hardware para módulos aritméticos, grupo de investigación ARITH, laboratorio Aoki, Universidad de Tohoku
• Katz, Randy (1994). Diseño lógico contemporáneo . Vol. 26. The Benjamin/Cummings Publishing Company . 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». quadibloc . Archivado desde el original el 2018-07-03 . Consultado el 2018-07-16 .

Enlaces externos

• Simulador de JavaScript de sumador de aspecto anticipado