Un sumador de acarreo y guardado [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 estas salidas. Un sumador de ahorro de acarreo se usa típicamente 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 sumador grande implementado utilizando esta técnica generalmente será mucho más rápido que la suma convencional de esos números.
Considere la suma:
12345678+ 87654322= 100000000
Usando 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", etc. hasta el final de la suma. Aunque conocemos el último dígito del resultado de inmediato, no podemos conocer el primer dígito hasta que hayamos revisado cada dígito en el 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 tomar 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, usando bits (dígitos binarios), esto significa que incluso si tenemos n sumadores de un bit a nuestra disposición, todavía tenemos que permitir un tiempo proporcional a n para permitir que un posible acarreo se propague desde un extremo del número. al otro. Hasta que hayamos hecho esto,
Un sumador de anticipación de acarreo puede reducir el retraso. En principio, el retraso se puede reducir para que sea proporcional a log n , pero para números grandes este ya no es el caso, porque incluso cuando se implementa el carry look-ahead, las distancias que las señales tienen que recorrer en el chip aumentan proporcionalmente. an , y los retrasos de propagación aumentan al mismo ritmo. 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 , la anticipación del acarreo no es de mucha ayuda.
La idea de retrasar la resolución de acarreos hasta el final, o salvar acarreos, se debe a John von Neumann . [3]
La suma de dos dígitos nunca puede llevar más de 1, y la suma de dos dígitos más 1 tampoco puede llevar nunca 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 suma la suma y los dígitos de acarreo a la tercera cifra y produce una suma y los dígitos de acarreo. En binario, los únicos dígitos son cero y uno, por lo que , y con un 1 transportado. Agregar el bit de acarreo puede dar, como máximo, un 1 transportado, por lo que es posible una suma de tres vías. Debido a esto, también es posible sumar las tres primeras cifras y producir la suma y llevar; para las cifras siguientes, la suma y el acarreo son dos términos, y a estos se les suma la siguiente cifra.
A continuación se muestra un ejemplo de una suma binaria de 3 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 calcular ((a+b)+c). La aritmética de ahorro de acarreo funciona al abandonar 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 sumando 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, se compone 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 propagación por acarreo que generará el resultado.
Esto fue muy ventajoso desde la perspectiva del retraso (tiempo de cálculo). Si tuviera que sumar estos 3 números usando métodos convencionales, le tomaría 2 retrasos del sumador de propagación de acarreo para llegar a la respuesta. Si utiliza la técnica de guardado de acarreo, solo necesita 1 retraso del sumador de propagación de acarreo y 1 retraso del sumador completo (que es mucho menor que un retraso de propagación de acarreo). Por tanto, los CSA suelen ser muy rápidos.
Suponiendo que tenemos dos bits de almacenamiento por dígito, podemos usar 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 guardado sin desbordar nuestra capacidad de almacenamiento: pero ¿luego qué?
La clave del éxito es que en el momento de cada suma parcial sumamos tres bits:
Para decirlo de otra manera, 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 del actual. En cada ciclo de reloj, los acarreos sólo 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 funcionar mucho más rápido. ..
Todavía es necesario convertir el resultado a binario al final de un cálculo, lo que efectivamente 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 de acarreo,
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 es algo así como la suma con ahorro de acarreo, conlleva un costo fijo, 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 del error [6] permite tomar una decisión acerca de restar el módulo incluso 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 gastos generales fijos asociados a cada secuencia de multiplicaciones.
La unidad de guardado de acarreo consta de n sumadores completos , cada uno de los cuales calcula una suma única y un 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 , se produce una suma parcial ps y un desplazamiento y acarreo sc :
Luego, la suma total se puede calcular mediante:
