139
правок
Изменения
Нет описания правки
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляется посредством логических элементов “2И”.
Помимо этого, рассматриваемая схема содержит шесть дополнительных двухвходовых элементов "исключающее ИЛИ" и два дополнительных входа <tex> u1, u2 </tex>. При этом в рабочем режиме на входы <tex> c, u1, u2, p1, p2, p3 </tex> подаются сигналы логического "0".
Это нужно для работы теста проверяющего неисправности. Но рассматривать мы это не будем.
===== Работа схемы =====
Схема работает по достаточно простому принципу.
<tex>O(n) + O(n) + O(\log n) = O(n) </tex>
Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
== Литература и источники ==
* Е. Угрюмов "Цифровая схемотехника" 2001г.
* В.Л. Шило "Популярные цифровые микросхемы" 1988г.
* [http://library.espec.ws/section6/article46.html Схема умножителя]
* ''[http://ru.wikipedia.org/wiki/Кормен Кормен Т.], [http://ru.wikipedia.org/wiki/Лейзерсон,_Чарльз_Эрик Лейзерсон Ч.], [http://ru.wikipedia.org/wiki/Ривест,_Рональд_Линн Ривест Р.]''. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5
