PUERTA | PUERTA-CS-2003 | Pregunta 11

Considere un multiplicador de array para multiplicar dos números de n bits. Si cada puerta en el circuito tiene una unidad de retardo, el retardo total del multiplicador es
(A) Θ(1)
(B) Θ(log n)
(C) Θ(n)
(D) Θ(n ² )

Respuesta: (C)
Explicación: número de puertas utilizadas en el multiplicador de array de bits ‘n’ (n * n) = (2n – 1)
Cada puerta en el circuito tiene una unidad de retardo.

retraso total,

= 1 * (2n – 1) 
= O(2n – 1) 
= O(n)  

Supongamos 2 números A y B.

Tomar,

A = A0 A1 A2 A3
B = B0 B1 B2 B3 

Para multiplicar A y B tenemos que hacer,

1. Multiplique A0 A1 A2 A3 con B1 necesita 1 compuerta AND
2. Multiplique A0 A1 A2 A3 con B2 necesita 1 compuerta AND
3. Multiplique A0 A1 A2 A3 con B3 necesita 1 compuerta AND
4. Multiplique A0 A1 A2 A3 con B4 necesita 1 compuerta AND

También se requieren 3 compuertas OR para agregar términos obtenidos por compuertas AND.
Entonces, puertas totales requeridas = 4+3 = 7 que es 2N-1.

Asi que,

Time complexity = ϴ(n) 

La opción (C) es correcta.
Cuestionario de esta pregunta