Sumador con selección de acarreo

En electrónica, un sumador de selección de acarreo es una forma particular de implementar un sumador , que es un elemento lógico que calcula el $(n+1)$ -suma de dos bits $n$ números de bits. El sumador de selección de acarreo es simple pero bastante rápido, con una profundidad de nivel de puerta de $O({\sqrt {n}})$ .

Construcción

El sumador con selección de acarreo generalmente consta de sumadores de acarreo en cascada y un multiplexor . La suma de dos números de n bits con un sumador con selección de acarreo se realiza con dos sumadores (por lo tanto, dos sumadores de acarreo en cascada) para llevar a cabo el cálculo dos veces: una vez suponiendo que el acarreo de entrada es cero y la otra suponiendo que será uno. Una vez calculados ambos resultados, el multiplexor selecciona la suma correcta, así como el acarreo de salida correcto, una vez que se conoce el acarreo de entrada correcto.

El número de bits en cada bloque de selección de acarreo puede ser uniforme o variable. El retardo óptimo se produce cuando se aplica un tamaño variable a los bloques ^{[ 1 ].} $\lfloor {\sqrt {n}}\rfloor$ Cuando es variable, el tamaño del bloque debe tener un retardo, desde las entradas de suma A y B hasta la salida de acarreo, igual al de la cadena del multiplexor que lo precede, de modo que la salida de acarreo se calcule justo a tiempo. $O({\sqrt {n}})$ El retardo se deriva del dimensionamiento uniforme, donde el número ideal de elementos sumadores completos por bloque es igual a la raíz cuadrada del número de bits que se suman, ya que eso producirá un número igual de retardos del multiplexor.

bloque de construcción básico

Arriba se muestra el bloque básico de un sumador con selección de acarreo, donde el tamaño del bloque es 4. Dos sumadores de acarreo en cascada de 4 bits se multiplexan, y los bits de acarreo y suma resultantes se seleccionan según el acarreo de entrada. Dado que un sumador de acarreo en cascada asume un acarreo de entrada de 0 y el otro asume un acarreo de entrada de 1, seleccionar qué sumador tuvo la suposición correcta mediante el acarreo de entrada real produce el resultado deseado.

Víbora de tamaño uniforme

Se puede crear un sumador de selección de acarreo de 16 bits con un tamaño de bloque uniforme de 4 utilizando tres de estos bloques y un sumador de acarreo en cascada de 4 bits. Dado que el acarreo de entrada se conoce al inicio del cálculo, no se necesita un bloque de selección de acarreo para los primeros cuatro bits. El retardo de este sumador será de cuatro retardos de sumador completos, más tres retardos de multiplexor.

Sumador de tamaño variable

Se puede crear de manera similar un sumador de selección de acarreo de 16 bits con tamaño variable. Aquí mostramos un sumador con tamaños de bloque de 2-2-3-4-5, este es el tipo especial de sumador de selección de acarreo de tamaño variable, llamado sumador de selección de acarreo de raíz cuadrada. ^{[ 2 ]} Esta división es ideal cuando el retardo del sumador completo es igual al retardo del multiplexor, lo cual es improbable. El retardo total es dos retardos de sumador completo y cuatro retardos de multiplexor. Intentamos que el retardo a través de las dos cadenas de acarreo y el retardo del acarreo de la etapa anterior sean iguales.

Sumador de suma condicional

Un sumador de suma condicional ^{[ 3 ]} es una estructura recursiva basada en el sumador de selección de acarreo. En el sumador de suma condicional, el nivel MUX elige entre dos entradas de n/2 bits que, a su vez, están construidas como sumadores de suma condicional. El nivel inferior del árbol consta de pares de sumadores de 2 bits (1 semisumador y 3 sumadores completos) más 2 multiplexores de un bit.

El sumador de suma condicional sufre de una ramificación muy grande de las salidas de acarreo intermedias. La ramificación puede ser tan alta como n/2 en el último nivel, donde $c_{n/2-1}$ controla todos los multiplexores desde $s_{n/2}$ a $s_{n-1}$ .

Combinación con otras estructuras de suma

El diseño del sumador con selección de acarreo se puede complementar con una estructura de sumador con anticipación de acarreo para generar las entradas del multiplexor, logrando así un rendimiento aún mayor como sumador de prefijo paralelo y reduciendo potencialmente el área.

En el artículo sobre la víbora de Kogge-Stone se muestra un ejemplo .

Lecturas adicionales

Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .

Referencias

↑ VG Oklobdzija y ER Barnes, "Algunos esquemas óptimos para la implementación de ALU en tecnología VLSI", Actas del 7.º Simposio sobre Aritmética Computacional ARITH-7, págs. 2-8. Reimpreso en Aritmética Computacional, EE Swartzlander (editor), vol. II, págs. 137-142, 1985.
↑ VG Oklobdzija y ER Barnes, "Sobre la implementación de la suma en la tecnología VLSI", IEEE Journal of Parallel and Distributed Computing, No. 5, pp. 716-728, 1988.
↑ Lógica de suma condicional. Sklansky J. IRE Transaction on Electronic Computer. 1960. p.226.

[1] VG Oklobdzija y ER Barnes, "Algunos esquemas óptimos para la implementación de ALU en tecnología VLSI", Actas del 7.º Simposio sobre Aritmética Computacional ARITH-7, págs. 2-8. Reimpreso en Aritmética Computacional, EE Swartzlander (editor), vol. II, págs. 137-142, 1985.

[2] VG Oklobdzija y ER Barnes, "Sobre la implementación de la suma en la tecnología VLSI", IEEE Journal of Parallel and Distributed Computing, No. 5, pp. 716-728, 1988.

[3] Lógica de suma condicional. Sklansky J. IRE Transaction on Electronic Computer. 1960. p.226.

[ 1 ].

[ 2 ]

[ 3 ]