2011-gre-cs-practice-book.pdf/Q45 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q45-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
(не показано 6 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
== Вопрос: Q45-08c765 == | == Вопрос: Q45-08c765 == | ||
− | + | Если задержка через одноразрядный сумматор составляет 3 (измеряется в задержках логических элементов) для выхода суммы и 2 для выхода переноса, то какова задержка через сумматор с переносом длиной в k-разрядов? | |
− | + | ||
− | + | ||
− | + | ||
− | + | === Ответы === | |
− | + | * 2k-1 | |
+ | * Правильный ответ: 2k+1 | ||
+ | * 3k-1 | ||
+ | * 3k | ||
+ | * 3k+1 | ||
− | + | === Объяснение === | |
+ | {{cstest-source|2011-gre-cs-practice-book.pdf|19|45}} | ||
− | + | В k-разрядном сумматоре с переносом: | |
− | + | ||
− | + | ||
− | + | Перенос проходит последовательно через все k разрядов, так как это схема с последовательным переносом ([https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder, ripple-carry adder]). | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | Задержка через каждый разряд определяется задержкой для выхода переноса (2). Следовательно, общее время задержки для переноса = 2k. | |
− | + | ||
− | + | ||
+ | Однако, для последнего разряда сумма не может быть вычислена, пока не придёт перенос, а вычисление суммы требует дополнительной задержки 1 (из-за зависимости от выхода переноса). | ||
+ | |||
+ | Итак, общая задержка = 2k+1. | ||
− | |||
− | |||
− | |||
− | + | [[Участник:StasFomin|StasFomin]] 19:39, 23 декабря 2024 (UTC): Гм. Мне кажется логика проще и другая — (k-1)-разрядов для переноса, и вывод, итого | |
+ | 2*(k-1)+3 = 2k+1 | ||
− | |||
− | |||
− | |||
− | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 19:47, 23 декабря 2024 (UTC)}} | |
− | + | [[Категория:Процессорная архитектура]] |
Текущая версия на 19:47, 23 декабря 2024
Вопрос: Q45-08c765
Если задержка через одноразрядный сумматор составляет 3 (измеряется в задержках логических элементов) для выхода суммы и 2 для выхода переноса, то какова задержка через сумматор с переносом длиной в k-разрядов?
Ответы
- 2k-1
- Правильный ответ: 2k+1
- 3k-1
- 3k
- 3k+1
Объяснение
Исходники — вопрос 45 на 19 странице книги «2011-gre-cs-practice-book.pdf»
В k-разрядном сумматоре с переносом:
Перенос проходит последовательно через все k разрядов, так как это схема с последовательным переносом (ripple-carry adder).
Задержка через каждый разряд определяется задержкой для выхода переноса (2). Следовательно, общее время задержки для переноса = 2k.
Однако, для последнего разряда сумма не может быть вычислена, пока не придёт перенос, а вычисление суммы требует дополнительной задержки 1 (из-за зависимости от выхода переноса).
Итак, общая задержка = 2k+1.
StasFomin 19:39, 23 декабря 2024 (UTC): Гм. Мне кажется логика проще и другая — (k-1)-разрядов для переноса, и вывод, итого
2*(k-1)+3 = 2k+1