2011-gre-cs-practice-book.pdf/Q45 — различия между версиями

Версия 19:40, 23 декабря 2024

Вопрос: Q45-08c765

Если задержка через одноразрядный сумматор составляет 3 (измеряется в задержках логических элементов) для выхода суммы и 2 для выхода переноса, то какова задержка через сумматор с переносом длиной в k-разрядов?

Ответы

Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так (префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)

• 2k-1
• Правильный ответ: 2k+1
• 3k-1
• 3k
• 3k+1

Если ответы длинные, многострочные, или там графы, используйте способ задания ответов разделами, Но такое очень редко встречается.

Объяснение

В k-разрядном сумматоре с переносом:

Перенос проходит последовательно через все k разрядов, так как это схема с последовательным переносом (ripple-carry adder).

Задержка через каждый разряд определяется задержкой для выхода переноса (2). Следовательно, общее время задержки для переноса = 2k.

Однако, для последнего разряда сумма не может быть вычислена, пока не придёт перенос, а вычисление суммы требует дополнительной задержки 1 (из-за зависимости от выхода переноса).

Итак, общая задержка = 2k+1.

StasFomin 19:39, 23 декабря 2024 (UTC): Гм. Мне кажется логика проще и другая — (k-1)-разрядов для переноса, и вывод, итого

 2*(k-1)+3 = 2k+1