Probablemente haya dedicado más tiempo a esta pregunta del que debería, pero aquí están mis conclusiones.
No puedo encontrar ningún ejemplo de un sumador de prefijo paralelo "puro" para números negativos. También creo que es un problema abierto, ya que no he visto ninguna prueba de que no sea posible
Lo más cercano que puedo conseguirte es mediante el uso de una adición negativa negativa de dos pasos (comúnmente abreviada n.n.b.a. en la literatura). Se basa en la siguiente propiedad:
Deje que \ $ f (x) = \ overline {x_ {n-1}} x_ {n-2} ... \ overline {x_1} x_0 \ $ y \ $ g (x) = x_ {n- 1} \ overline {x_ {n-2}} ... x_1 \ overline {x_0} \ $. Estas son básicamente una operación XOR con 0xAA...AA y 0x55...55 respectivamente.
Entonces puedes probar que
$$ - (a + _ {nb} b) = g \ left (f (a) + f (b) + 1 \ right) $$
Donde el lado izquierdo es la suma negativa \ $ + _ {nb} \ $, mientras que el \ $ + \ $ en el lado derecho es una suma binaria normal.
La suma negativa puede entonces simplemente invertirse usando la misma propiedad pero con un operando cero:
$$ - x = g \ left (f (x) + f (0) + 1 \ right) $$
Entonces, para encontrar la suma usando sumadores de prefijos paralelos, puedes:
- Calcular \ $ f (a) \ $ y \ $ f (b) \ $, es decir. invirtiendo cada bit impar de los números negativos
- Calcule la suma binaria regular mientras establece el bit de acarreo para el LSB (el \ $ + 1 \ $), lo que lleva a una primera suma intermedia \ $ s_1 \ $.
- Invierta todos los bits de \ $ s_1 \ $ (esto es \ $ f (g (s_1)) \ $). Este es el final de la primera suma, mientras que también se inicia la inversión.
- Incremente el resultado con
0xAA...AB (\ $ = f (0) +1 \ $) usando un sumador de prefijo paralelo, obteniendo la segunda suma intermedia \ $ s_2 \ $
- Calcular \ $ g (s_2) \ $ (invirtiendo cada bit par) para encontrar la suma negativa final.
En realidad, traté de encontrar un sumador de prefijos paralelos "puro", pero lo consideré demasiado complejo para el tiempo que estaba dispuesto a dedicarle. He aquí por qué:
El punto central de los agregadores de prefijos paralelos es encontrar alguna operación de \ $ \ {0,1 \} ^ n \ times \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n \ $ que le permite calcular fácilmente los (en este caso 2) acarreos de estos bits. Como una restricción adicional, la operación debe ser asociativa para ser computada en paralelo. Por ejemplo, esto básicamente excluye cualquier operador NOT (que no es parte de una doble negación). Por ejemplo: \ $ a \ circ b = a \ cdot \ bar b \ $ no es un operador asociativo, porque
$$ \ begin {align}
(a \ circ b) \ circ c & = a \ cdot \ bar b \ cdot \ bar c \\
a \ circ (b \ circ c) & = a \ cdot \ overline {b \ cdot \ bar c}
\ end {align} $$
Tenga en cuenta que el operador booleano para los acarreos en su pregunta incluye los términos mixtos \ $ c_i ^ + \ overline {c_i ^ -} \ $ y \ $ c_i ^ - \ overline {c_i ^ +} \ $, por lo que imposible usarlo como está. Para un único acarreo en adición binaria normal, se hizo bastante obvio cómo construir este operador cuando se piensa en términos de generación y propagación , pero parece que no es así. obvio para los acarreos negativos.
