Sumador de acarreo y salto - Carry-skip adder

Un sumador de acarreo y omisión (también conocido como sumador de acarreo y derivación ) es una implementación de sumador que mejora el retraso de un sumador de acarreo de ondulación con poco esfuerzo en comparación con otros sumadores. La mejora del retraso en el peor de los casos se logra mediante el uso de varios sumadores de acarreo y salto para formar un sumador de bloque de acarreo y salto.

A diferencia de otros sumadores rápidos, el rendimiento del sumador de acarreo y salto se incrementa con solo algunas de las combinaciones de bits de entrada. Esto significa que la mejora de la velocidad es solo probabilística .

Sumador de acarreo simple

El peor de los casos para un sumador de acarreo de ondulación simple de un nivel ocurre cuando la condición de propagación es verdadera para cada par de dígitos . Luego, el acarreo fluye a través del sumador de bits y aparece como el acarreo posterior . ${\ Displaystyle (a_ {i}, b_ {i})}$${\ Displaystyle n}$${\ Displaystyle \ tau _ {CRA} (n) \ approx n \ cdot \ tau _ {VA}}$

Sumador completo con señales adicionales de generación y propagación.

Para cada par de bits de entrada de operando, las condiciones de propagación se determinan utilizando una puerta XOR. Cuando todas las condiciones de propagación son verdaderas , el bit de transferencia determina el bit de ejecución. ${\ Displaystyle (a_ {i}, b_ {i})}$${\ Displaystyle p_ {i} = a_ {i} \ oplus b_ {i}}$${\ Displaystyle c_ {0}}$

El n bits-carry-skip sumador consiste en un n -cadena de bits-equipaje de ondulación, un n -input puerta Y y un multiplexor. Cada bit Propagar , que es proporcionada por la cadena de transporte de rizado está conectado a la n -input puerta AND. El bit resultante se utiliza como bit de selección de un multiplexor que conmuta el último bit de acarreo o el último bit de transferencia a la señal de transferencia . ${\ Displaystyle p_ {i}}$${\ Displaystyle c_ {n}}$${\ Displaystyle c_ {0}}$${\ Displaystyle c_ {out}}$

• ${\ Displaystyle s = p_ {n-1} \ wedge p_ {n-2} \ wedge \ dots \ wedge p_ {1} \ wedge p_ {0} = p _ {[0: n-1]}}$

Esto reduce en gran medida la latencia del sumador a través de su ruta crítica, ya que el bit de acarreo para cada bloque ahora puede "omitir" bloques con una señal de propagación de grupo configurada en lógica 1 (a diferencia de una cadena de acarreo de ondulación larga, que requeriría el acarreo para ondular a través de cada bit en el sumador). El número de entradas de la puerta AND es igual al ancho del sumador. Para un ancho grande, esto se vuelve poco práctico y conduce a retrasos adicionales, porque la puerta AND debe construirse como un árbol. Una buena anchura se consigue, cuando la suma lógica tiene la misma profundidad como el n -input puerta Y y el multiplexor.

Sumador de arrastre de 4 bits.

Actuación

La ruta crítica de un sumador de acarreo y salto comienza en el primer sumador completo, pasa por todos los sumadores y termina en el bit de suma . Los sumadores de acarreo y omisión están encadenados (consulte los sumadores de acarreo y omisión de bloques) para reducir la ruta crítica general, ya que un sumador de acarreo y omisión de un solo bit no tiene ningún beneficio de velocidad real en comparación con un sumador de acarreo de ondulación de -bit. ${\ Displaystyle s_ {n-1}}$${\ Displaystyle n}$${\ Displaystyle n}$

${\ Displaystyle \ tau _ {CSA} (n) = \ tau _ {CRA} (n)}$

La lógica de salto consta de una puerta Y de entrada y un multiplexor. ${\ Displaystyle m}$

${\ Displaystyle T_ {SK} = T_ {AND} (m) + T_ {MUX}}$

Como las señales de propagación se calculan en paralelo y están disponibles de forma anticipada, la ruta crítica para la lógica de salto en un sumador de acarreo y salto consiste solo en el retardo impuesto por el multiplexor (salto condicional).

${\ Displaystyle T_ {CSK} = T_ {MUX} = 2D}$.

Sumadores de bloque-acarreo-salto

Sumador de salto de acarreo de bloque fijo de 16 bits con un tamaño de bloque de 4 bits.

Los sumadores de bloques de acarreo y salto se componen de varios sumadores de acarreo y salto. Hay dos tipos de sumadores de bloque, acarreo y salto. Los dos operandos y se dividen en bloques de bits. ${\ Displaystyle A = (a_ {n-1}, a_ {n-2}, \ dots, a_ {1}, a_ {0})}$${\ Displaystyle B = (b_ {n-1}, b_ {n-2}, \ dots, b_ {1}, b_ {0})}$${\ Displaystyle k}$${\ Displaystyle (m_ {k}, m_ {k-1}, \ dots, m_ {2}, m_ {1})}$

• ¿Por qué se utilizan sumadores de bloques-acarreos-saltos?
• ¿El tamaño del bloque debe ser constante o variable?
• Ancho de bloque fijo frente a ancho de bloque variable

Sumadores de bloque-acarreo-salto de tamaño fijo

Los sumadores de bloque-acarreo-salto de tamaño fijo dividen los bits de los bits de entrada en bloques de bits cada uno, lo que da como resultado bloques. La ruta crítica consiste en la ruta de rizo y el elemento de salto del primer bloque, los caminos de salto que están encerrados entre el primer y el último bloque, y finalmente el camino de rizo del último bloque. ${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle k = {\ frac {n} {m}}}$

${\ Displaystyle T_ {FCSA} (n) = T_ {CRA _ {[0: c_ {out}]}} (m) + T_ {CSK} + (k-2) \ cdot T_ {CSK} + T_ {CRA} (m) = 3D + m \ cdot 2D + (k-1) \ cdot 2D + (m + 2) 2D = (2m + k) \ cdot 2D + 5D}$

El tamaño de bloque óptimo para un ancho de sumador dado n se obtiene al igualar a 0

${\ Displaystyle {\ frac {dT_ {FCSA} (n)} {dm}} = 0}$

${\ Displaystyle 2D \ cdot \ left (2-n \ cdot {\ frac {1} {m ^ {2}}} \ right) = 0}$

${\ Displaystyle \ Rightarrow m_ {1,2} = \ pm {\ sqrt {\ frac {n} {2}}}}$

Solo se pueden realizar tamaños de bloque positivos

${\ Displaystyle \ Rightarrow m = {\ sqrt {\ frac {n} {2}}}}$

Sumadores de bloque-acarreo-salto de tamaño variable

El rendimiento se puede mejorar, es decir, todos los transportes se propagan más rápidamente variando los tamaños de los bloques. En consecuencia, los bloques iniciales del sumador se hacen más pequeños para detectar rápidamente las generaciones de acarreo que deben propagarse a los posteriores, los bloques del medio se hacen más grandes porque no son el caso problemático, y luego los bloques más significativos se vuelven a hacer más pequeños para que las entradas de acarreo que llegan tarde se pueden procesar rápidamente.

Sumadores multinivel de acarreo y salto

Mediante el uso de bloques de salto adicionales en una capa adicional, las señales de propagación de bloque se resumen y se utilizan para realizar saltos más grandes: ${\ Displaystyle p _ {[i: i + 3]}}$

${\ Displaystyle p _ {[i: i + 15]} = p _ {[i: i + 3]} \ wedge p _ {[i + 4: i + 7]} \ wedge p _ {[i + 8: i + 11 ]} \ wedge p _ {[i + 12: i + 15]}}$

De este modo, el sumador es aún más rápido.

Optimización de acarreos

El problema de determinar los tamaños de bloque y el número de niveles requeridos para hacer el sumador de acarreo y salto más rápido físicamente se conoce como el "problema de optimización del sumador de acarreo y salto". Este problema se complica por el hecho de que los sumadores de acarreo y salto se implementan con dispositivos físicos cuyo tamaño y otros parámetros también afectan el tiempo de adición.

Thomas W. Lynch resolvió el problema de optimización de arrastre para tamaños de bloques variables y niveles múltiples para un nodo de proceso de dispositivo arbitrario. Esta referencia también muestra que la adición de acarreo-salto es lo mismo que la adición de prefijos paralelos y, por lo tanto, está relacionada con, y para algunas configuraciones, idénticas a Han-Carlson , Brent-Kung , Kogge-Stone sumador y una serie de otros tipos de sumadores .

Resumen de implementación

Desglosando esto en términos más específicos, para construir un sumador de derivación de acarreo de 4 bits, se necesitarían 6 sumadores completos . Los buses de entrada serían un 4 bits A y un 4-bit B , con un carry-in ( CIN señal). La salida sería un bus X de 4 bits y una señal de ejecución ( COUT ).

Los dos primeros sumadores completos sumarían los dos primeros bits. La señal de ejecución del segundo sumador completo ( ) conduciría la señal de selección para tres multiplexores 2 a 1. El segundo conjunto de 2 sumadores completos agregaría los dos últimos bits asumiendo que es un 0 lógico. Y el conjunto final de sumadores completos asumiría que es un 1 lógico. ${\ Displaystyle C_ {1}}$${\ Displaystyle C_ {1}}$${\ Displaystyle C_ {1}}$

Los multiplexores entonces controlar qué señal de salida se utiliza para COUT , y . ${\ Displaystyle X_ {2}}$${\ Displaystyle X_ {3}}$

Notas

Referencias

enlaces externos

• Explicación de la ruta crítica del sumador de salto variable