Considere un sumador anticipado de acarreo para sumar dos enteros de n bits, construido usando puertas de fan-in como máximo dos. El tiempo para realizar la suma usando este sumador es
(A) Θ(1)
(B) Θ(Log (n))
(C) Θ(√ n)
(D) Θ(n)
Respuesta: (B)
Explicación: mirar hacia adelante El generador de acarreo da salida en tiempo constante si fan-in = número de entradas.
Por ejemplo:
It will take O(1) to calculate
c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0c4
= g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0,
if OR gate with 5 inputs is present.
Y, si fan-in != número de entradas, entonces tendremos retraso en cada nivel, como se indica a continuación.
Si tenemos 8 entradas y una puerta OR con 2 entradas, para construir una puerta OR con 8 entradas, necesitaremos 4 puertas en el nivel 1, 2 en el nivel 2 y 1 en el nivel 3. Por lo tanto, 3 retrasos de puerta, para cada nivel.
De manera similar, una puerta de n entradas construida con puertas de 2 entradas, el retraso total será O (log n).
// Esta explicación ha sido proporcionada por Saksham Raj Seth.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA