Sumador para llevar y guardar - Carry-save adder

Parte de una serie sobre
circuitos aritméticos lógicos
Navegacion rapida
Teoría
Componentes
Categorías
Ver también

Un sumador de acarreo y ahorro 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 carry save 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 con esta técnica generalmente será mucho más rápido que la suma convencional de esos números.

Motivación

Considere la suma: 

   12345678
+  87654322
= 100000000

Usando aritmética básica, calculamos de derecha a izquierda, "8 + 2 = 0, acarreo 1", "7 + 2 + 1 = 0, acarreo 1", "6 + 3 + 1 = 0, acarreo 1", y así sucesivamente. hasta el final de la suma. Aunque conocemos el último dígito del resultado de una vez, no podemos conocer el primer dígito hasta que hayamos pasado por todos los dígitos del cálculo, pasando el acarreo de cada dígito al de su izquierda. Por lo tanto la adición de dos n de dígitos números debe tomar un tiempo proporcional a n , incluso si la maquinaria que estamos utilizando otro modo 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 an para permitir que un posible acarreo se propague desde un extremo del número. para el otro. Hasta que hayamos hecho esto

  1. No conocemos el resultado de la suma.
  2. No sabemos si el resultado de la suma es mayor o menor que un número dado (por ejemplo, no sabemos si es positivo o negativo).

Un sumador de anticipación de acarreo puede reducir el retraso. En principio, el retardo 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 la anticipación de acarreo, las distancias que las señales tienen que viajar en el chip aumentan en proporción a n , y los retardos de propagación aumentan a la misma velocidad. Una vez que llegamos a los tamaños de número de 512 bits a 2048 bits que se requieren en la criptografía de clave pública , la búsqueda anticipada no es de mucha ayuda.

El concepto básico

La idea de retrasar la resolución de acarreos hasta el final, o salvar acarreos, se debe a John von Neumann .

Aquí hay un ejemplo de una suma binaria de 3 números binarios largos: 

  10111010101011011111000000001101 (a)
+ 11011110101011011011111011101111 (b)
+ 00010010101101110101001101010010 (c)

La forma convencional de hacerlo sería calcular primero (a + b) y luego calcular ((a + b) + c). La aritmética carry-save funciona abandonando cualquier tipo de propagación de carry. Calcula la suma dígito por dígito, como: 

  10111010101011011111000000001101
+ 11011110101011011011111011101111
+ 00010010101101110101001101010010
= 21132130303123132223112112112222

La notación no es convencional, pero el resultado sigue siendo inequívoco. Si asumimos que los tres números son a, by c. Entonces, aquí, el resultado se describirá como la suma de 2 números binarios, donde el primer número, S, es simplemente la suma obtenida al sumar los dígitos (sin propagación de acarreo), es decir, S i = a i ⊕ b i ⊕ c iy 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 ): 

  01110110101101110001110110110000 and
 100110101010110111110010010011110

Ahora estos 2 números se pueden enviar a un sumador de acarreo-propagación que generará el resultado.

Esto fue muy ventajoso desde una perspectiva de retraso (tiempo de cálculo). Si tuvieras que sumar estos 3 números usando métodos convencionales, te tomaría 2 retrasos de sumador de acarreo-propagación para llegar a la respuesta. Si usa la técnica de acarreo-guardado, solo necesita 1 retraso de sumador de acarreo-propagación y 1 retraso de sumador completo (que es mucho más bajo que un retraso de acarreo-propagación). Por lo tanto, los sumadores de CSA suelen ser muy rápidos.

Acumuladores de transporte

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 acarreo y ahorro sin desbordar nuestra capacidad de almacenamiento: pero ¿luego qué?

La clave del éxito es que en el momento de cada adición parcial agregamos tres bits:

  • 0 o 1, del número que estamos sumando.
  • 0 si el dígito en nuestra tienda es 0 o 2, o 1 si es 1 o 3.
  • 0 si el dígito a su derecha es 0 o 1, o 1 si es 2 o 3.

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, 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 adición convencional.

Debido a que las señales no tienen que moverse tanto, el reloj puede marcar mucho más rápido. ..

Todavía existe la necesidad de convertir el resultado a binario al final de un cálculo, lo que efectivamente significa dejar que los acarreos recorran todo el número como en un sumador convencional. Pero si hemos hecho 512 adiciones en el proceso de realizar una multiplicación de 512 bits, el costo de esa conversión final se divide efectivamente entre esas 512 adiciones, por lo que cada adición conlleva 1/512 del costo de esa adición "convencional" final.

Inconvenientes

En cada etapa de una adición de acarreo y ahorro,

  1. Conocemos el resultado de la suma de una vez.
  2. Nosotros todavía no sabemos si el resultado de la suma es mayor o menor que un número dado (por ejemplo, no sabemos si es positivo o negativo).

Este último punto es un inconveniente cuando se usan sumadores de acarreo y guardado para implementar la multiplicación modular (multiplicación seguida de división, manteniendo solo el resto). Si no podemos saber si el resultado intermedio es mayor o menor que el módulo, ¿cómo podemos saber si 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 se parece más a la adición de acarreo y ahorro, tiene 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 la criptografía de clave pública.

El análisis cuidadoso del error permite elegir entre 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 adjunta a cada secuencia de multiplicaciones.

Detalles técnicos

La unidad de acarreo-ahorro consta de n sumadores completos , cada uno de los cuales calcula una única suma y un bit de acarreo basándose únicamente en los bits correspondientes de los tres números de entrada. Teniendo en cuenta los tres n números -bit un , b , y c , se produce una suma parcial ps y un cambio de llevar sc :

Entonces, la suma completa se puede calcular mediante:

  1. Cambiando la secuencia de acarreo sc a la izquierda en un lugar.
  2. Añadiendo un 0 al frente ( bit más significativo ) de la secuencia de suma parcial ps .
  3. Usando un sumador de acarreo de ondulación para sumar estos dos y producir el valor de bits ( n + 1) resultante .

Ver también

Notas

Referencias

Otras lecturas