Un sumador con acarreo y ahorro [1] [2] [nb 1] es un tipo de sumador digital que se utiliza para calcular de manera eficiente la suma de tres o más números binarios . Se diferencia de otros sumadores digitales en que genera dos (o más) números y la respuesta de la suma original se puede lograr sumando estos resultados. Un sumador con acarreo y ahorro se utiliza normalmente en un multiplicador binario, ya que un multiplicador binario implica la suma de más de dos números binarios después de la multiplicación. Un gran sumador implementado con esta técnica normalmente será mucho más rápido que la suma convencional de esos números.
Considere la suma:
12345678+ 87654322= 100000000
Utilizando aritmética básica, calculamos de derecha a izquierda: "8 + 2 = 0, lleva 1", "7 + 2 + 1 = 0, lleva 1", "6 + 3 + 1 = 0, lleva 1", y así sucesivamente hasta el final de la suma. Aunque conocemos el último dígito del resultado de inmediato, no podemos saber el primer dígito hasta que hayamos recorrido todos los dígitos del cálculo, pasando el acarreo de cada dígito al de su izquierda. Por lo tanto, sumar dos números de n dígitos tiene que llevar un tiempo proporcional a n , incluso si la maquinaria que estamos utilizando sería capaz de realizar muchos cálculos simultáneamente.
En términos electrónicos, utilizando bits (dígitos binarios), esto significa que incluso si tenemos n sumadores de un bit a nuestra disposición, aún tenemos que permitir un tiempo proporcional a n para permitir que un posible acarreo se propague de un extremo del número al otro. Hasta que hayamos hecho esto,
Un sumador con acarreo anticipado puede reducir el retraso. En principio, el retraso se puede reducir de modo que sea proporcional a log n , pero para números grandes esto ya no es así, porque incluso cuando se implementa el acarreo anticipado, las distancias que las señales tienen que recorrer en el chip aumentan en proporción a n , y los retrasos de propagación aumentan a la misma velocidad. Una vez que llegamos a los tamaños de números de 512 bits a 2048 bits que se requieren en la criptografía de clave pública , el acarreo anticipado no es de mucha ayuda.
La idea de retrasar la resolución de los acarreos hasta el final, o de salvarlos, se debe a John von Neumann . [3]
La suma de dos dígitos nunca puede llevar más de un 1, y la suma de dos dígitos más 1 tampoco nunca puede llevar más de 1. Por ejemplo, en decimal, , que lleva un 1; , que también lleva un 1. Al sumar tres cifras, podemos sumar las dos primeras y producir una suma y los dígitos de acarreo; luego sumar la suma y los dígitos de acarreo a la tercera cifra y producir una suma y los dígitos de acarreo. En binario, los únicos dígitos son cero y uno, y así , , y con un 1 acarreado. Sumar el bit de acarreo puede dar, como máximo, con un 1 acarreado, por lo que es posible una suma triple. Debido a esto, también es posible sumar las tres primeras cifras y producir la suma y el acarreo; para las cifras posteriores, la suma y el acarreo son dos términos, y la siguiente cifra simple se suma a estos.
A continuación se muestra un ejemplo de una suma binaria de tres números binarios largos:
1011 1010 1010 1101 1111 0000 0000 1101 (a)+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)
La forma más sencilla de hacerlo sería calcular primero (a+b) y luego ((a+b)+c). La aritmética de ahorro de acarreo funciona abandonando cualquier tipo de propagación de acarreo. Calcula la suma dígito por dígito, como:
1011 1010 1010 1101 1111 0000 0000 1101 (a)+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)= 2113 2130 3031 2313 2223 1121 1211 2222
La notación no es convencional, pero el resultado sigue siendo inequívoco: Σ2 i d i . Si asumimos que los tres números son a, b y c, entonces aquí, el resultado se describirá como la suma de dos números binarios, donde el primer número, S, es simplemente la suma obtenida al sumar los dígitos (sin ninguna propagación de acarreo), es decir, S i = a i ⊕ b i ⊕ c i y el segundo número, C, está compuesto de acarreos de las sumas individuales anteriores, es decir, C i+1 = (a i b i ) + (b i c i ) + (c i a i ):
0111 0110 1011 0111 0001 1101 1011 0000 y 1 0011 0101 0101 1011 1110 0100 1001 1110
Ahora estos 2 números se pueden enviar a un sumador de acarreo-propagación que generará el resultado.
Esto resultó muy ventajoso desde la perspectiva del retraso (tiempo de cálculo). Si tuviera que sumar estos tres números utilizando métodos convencionales, necesitaría dos retrasos en el sumador de propagación de acarreo para llegar a la respuesta. Si utiliza la técnica de ahorro de acarreo, solo necesitaría un retraso en el sumador de propagación de acarreo y un retraso en el sumador completo (que es mucho menor que un retraso en el sumador de propagación de acarreo). Por lo tanto, los CSA suelen ser muy rápidos.
Suponiendo que tenemos dos bits de almacenamiento por dígito, podemos utilizar una representación binaria redundante , almacenando los valores 0, 1, 2 o 3 en cada posición de dígito. Por lo tanto, es obvio que se puede agregar un número binario más a nuestro resultado de acarreo-guardado sin desbordar nuestra capacidad de almacenamiento: pero ¿y luego qué?
La clave del éxito es que en el momento de cada adición parcial sumamos tres bits:
En otras palabras, tomamos un dígito de acarreo de la posición a nuestra derecha y pasamos un dígito de acarreo a la izquierda, tal como en la suma convencional; pero el dígito de acarreo que pasamos a la izquierda es el resultado del cálculo anterior y no el actual. En cada ciclo de reloj, los acarreos solo tienen que avanzar un paso, y no n pasos como en la suma convencional.
Como las señales no tienen que moverse tan lejos, el reloj puede avanzar mucho más rápido.
Todavía es necesario convertir el resultado a binario al final de un cálculo, lo que en realidad significa simplemente dejar que los acarreos recorran todo el número como en un sumador convencional. Pero si hemos realizado 512 sumas en el proceso de realizar una multiplicación de 512 bits, el costo de esa conversión final se divide efectivamente entre esas 512 sumas, por lo que cada suma representa 1/512 del costo de esa suma "convencional" final.
En cada etapa de una adición de ahorro y transporte,
Este último punto es un inconveniente cuando se utilizan sumadores con ahorro de acarreo para implementar la multiplicación modular (multiplicación seguida de división, manteniendo solo el resto). [4] [5] Si no podemos saber si el resultado intermedio es mayor o menor que el módulo, ¿cómo podemos saber si debemos restar el módulo?
La multiplicación de Montgomery , que depende del dígito más a la derecha del resultado, es una solución; aunque, al igual que la suma con acarreo y ahorro, conlleva una sobrecarga fija, de modo que una secuencia de multiplicaciones de Montgomery ahorra tiempo, pero una sola no. Afortunadamente, la exponenciación, que es efectivamente una secuencia de multiplicaciones, es la operación más común en criptografía de clave pública.
Un análisis cuidadoso de los errores [6] permite elegir si se debe restar el módulo, aunque no sepamos con certeza si el resultado de la suma es lo suficientemente grande como para justificar la resta. Para que esto funcione, es necesario que el diseño del circuito pueda sumar −2, −1, 0, +1 o +2 veces el módulo. La ventaja sobre la multiplicación de Montgomery es que no hay una sobrecarga fija asociada a cada secuencia de multiplicaciones.
La unidad de acarreo-guardado consta de n sumadores completos , cada uno de los cuales calcula una única suma y bit de acarreo basándose únicamente en los bits correspondientes de los tres números de entrada. Dados los tres números de n bits a , b y c , produce una suma parcial ps y un acarreo por desplazamiento sc :
La suma total puede entonces calcularse así:
