Detección de desbordamiento en un CSA (Adicionar-guardar)

En un sumador de acarreo-ahorro hay tres entradas y dos salidas. Muchos pares de salida diferentes representan el mismo número. Los sumadores de acarreo-ahorro no tienen una sobrecarga de propagación de acarreo, por lo que son buenos para sumar muchos operandos en baja latencia, pero el costo de esa velocidad es que realmente no se sabe nada sobre el resultado (incluso si es positivo o negativo ) hasta que agregue las dos salidas finales juntas utilizando un sumador "normal" (por ejemplo, ripple carry, carry-select, carry-skip o carry-lookahead).

No conozco ninguna manera de determinar el desbordamiento simplemente observando los bits más significativos (como puede hacerlo en un sumador que lleva). Por ejemplo, aquí hay un ejemplo que se desborda en el complemento de 3 bits 2 (3 + 3-2 = 4).

  0 1 1     (3)
  0 1 1     (3)
  1 1 0     (-2)
  -----
  1 1 0     (-2)
0 1 1       (6)

Y otro con todos los bits más significativos que no se desbordan:

  0 1 1     (3)
  0 1 1     (3)
  1 0 1     (-3)
  -----
  1 0 1     (-3)
0 1 1 0     (6)

Tuve que profundizar en mi manual de 68HC11 para averiguar en qué me estaba yendo mal en mi respuesta. ¡Asi que! La respuesta es mirar los bits de signo tanto de las entradas como de los resultados.

• Si sumas dos números positivos y el resultado es negativo, has tuvo un desbordamiento.
• Si sumas dos números negativos y el resultado es positivo, has tuvo un desbordamiento
• La adición de un número negativo y positivo no puede desbordarse

Puede detectar el desbordamiento después de la CSA utilizando los dos bits de acarreo más significativos, denotar \ $ C_o \ $ (el bit que se descarta), y \ $ C \ $, y el bit de signo más significativo, \ $ S \ $. La adición se desbordará si \ $ C_o = S = 0 \ $ y \ $ C = 1 \ $, es decir, todos los números positivos en, pero la suma no puede representarse en la representación de complemento de los dos correctos (aunque en realidad terminas con un número positivo al final causado por desbordamientos dobles) o \ $ C_0 = S = 1 \ $ y \ $ S = 0 \ $, es decir, todas las entradas negativas pero una magnitud demasiado alta (pero aún puede resultar en un número negativo debido a los dobles desbordamientos).

El desbordamiento en la adición final (acarreo-guardado a forma no-redundante) se detecta como de costumbre (comparando los dos bits de acarreo finales, si son diferentes, hay un desbordamiento, como veremos, no es posible verificar los signos) ).

Ejemplo 1:

  011
  011
 +011
-----
 011  carry
  011 sum

Desbordamiento como \ $ C_o = 0, S = 0, C = 1 \ $

  110
 +011
 ----
  001

Aquí, se produce otro desbordamiento al final (aunque no se detecta, ya que desde la perspectiva del complemento a dos \ $ - 2 + 3 \ $ no se desborda), por lo que se obtiene un número positivo a pesar del desbordamiento.

Ejemplo 2:

  010
  010
 +110
-----
 010  carry
  110 sum

No hay desbordamiento como \ $ C_o = 0, S = 1, C = 1 \ $

  100
 +110
 ----
  010

Respuesta correcta! Sin embargo, parece que se ha producido un desbordamiento al ver la adición del complemento de los dos. Esto se puede resolver reemplazando los bits de signo como \ $ S '= C_o \ $ y \ $ C' = C \ oplus S \ oplus C_o \ $ (esto también hará que la representación de carry-save se pueda cambiar) lo que lleva a

  000
 +010
 ----
  010

y no se detectó ningún desbordamiento (lo que es correcto).

Ejemplo 3:

  011
  011
 +111
-----
 011  carry
  111 sum

No hay desbordamiento como \ $ C_o = 0, S = 1, C = 1 \ $

  110
 +111
 ----
  101

Tampoco se ha detectado ningún desbordamiento aquí, aunque hay uno. Reemplace los bits de signo como se discutió anteriormente:

  010
 +011
 ----
  101

Ahora, dado que el acarreo entrante a la etapa final (1) es diferente del saliente (0), se detectó un desbordamiento, lo que por supuesto es correcto ya que \ $ 3 + 3-1 \ $ está fuera de \ $ [-4,3] \ $ rango posible

Todo esto se sugiere y se explica en "Arquitecturas de transporte para el procesamiento de señales digitales de alta velocidad" de Tobias Noll.