¿Cómo comparar los agregadores carry-lookahead y ripple-carry?

2

Estoy un poco atascado con el concepto de sumador de acarreo con vista así que me gustaría compararlo con otro concepto con el que estoy más familiarizado: el sumador de ondulación de ondulación. Estoy tratando de hacer una comparación matemática básica entre los dos.

Suponiendo que cada compuerta puede aceptar como máximo 2 (dos) entradas y tiene un retraso de '1', y que, al menos por el momento, estamos agregando dos números de 4 bits.

Comencemos con el sumador de ondulación. Lo he construido poniendo cuatro sumadores completos en columna. Cada carry-out se calcula como

$$ c_i ^ {(\ text {out})} = a_i \ cdot b_i + \ left [a_i + b_i \ right] \ cdot c_i ^ {(\ text {in})} \ qquad \ text {donde } \; \ cdot \ equiv \ text {AND}, \, + \ equiv \ text {OR} $$

Desde

$$ \ left [a_i + b_i \ right] $$

se calcula en paralelo para cada sumador completo, el costo para calcular el K-th carry-out es

$$ 1 + 2k $$

¿verdad?

Ahora digamos que queremos calcular el acarreo al principio, luego la suma, bit por bit. Usando la fórmula anterior, (y omitiendo el superíndice) escribimos eso

$$ c_ {i + 1} = g_i + p_i c_i $$

Por lo tanto, podemos escribir recursivamente el cuarto término en función del primero, es decir,

$$ c_1 = g_0 + p_0 c_0 \\ c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0 \\ \ vdots \\ c_4 = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 + p_3 p_2 p_1 p_0 c_0 $$

Por supuesto, es el último término que cuesta más. ¿Cuánto cuesta? Yo diría

$$ \ lceil \ log_2 {4} \ rceil + \ lceil \ log_2 {4} \ rceil $$

donde se necesita el primer término para calcular todas las operaciones Y , mientras que el segundo para calcular todas las operaciones O .

Por lo tanto, para una visión general ...

$$ 1 + \ lceil \ log_2 {k} \ rceil + 2 $$

donde el primer término es el retardo de puerta necesario para calcular cada término de propagador / generador, el segundo término es el que se necesita para calcular cada carry_in , entonces el último término es el retardo de puerta de una sola sumador completo.

Es decir, la comparación de "tiempo" entre un sumador de ondulación y un encabezado de carry-lookahead es la comparación de las siguientes dos funciones

$$ 1 + 2k $$ $$ 3 + \ lceil \ log_2 {k} \ rceil $$

Sé que carry-lookahead puede mejorarse más, y lo he hecho por mi cuenta ... aunque me gustaría que me diera algunos comentarios sobre las cosas anteriores por ahora.

    
pregunta Giuseppe

0 respuestas

Lea otras preguntas en las etiquetas