Рубрики

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 43

Рассмотрим переносной сумматор для сложения двух n-битных целых чисел, построенный с использованием вентилей не более двух. Время выполнения сложения с помощью этого сумматора
(A) Θ (1)
(B) Θ (Log (n))
(C) Θ (√ n)
(D) Θ (н)

Ответ: (Б)
Пояснение: Переносящий генератор переноса выдает выходной сигнал в постоянное время, если вход вентилятора = количество входов.

Например:

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.

И, если fan-in! = Количество входов, то у нас будет задержка на каждом уровне, как показано ниже.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 43

0.00 (0%) 0 votes