Мы уже познакомились с АЛУ, арифметико-логическим устройством, которое является центральным элементом подавляющего большинства процессоров. Однако, наше АЛУ не выполняло ни операции умножения, ни операции деления. Причина проста, АЛУ является универсальным элементом, который обычно выполняет лишь базовый набор операций. И вся его внутренняя структура ориентированна именно на универсальность и быстродействие.
Операции умножения и деления нельзя отнести к базовым, даже с точки зрения математики. Да, они входят в список основных арифметических операций, но их можно выразить через последовательность операций сложения и вычитания. Умножение и деление можно добавить в АЛУ, но это неэффективно, так как большая часть схем выполняющих эти операции будет фактически отдельными блоками в составе АЛУ.
А поскольку умножение и деление действительно требуются далеко не всегда, более оптимальным вариантом будет реализация их в виде отдельных функциональных блоков/микросхем работающих совместно с АЛУ.
Сегодня мы познакомимся с выполнением операции умножения на аппаратном, схемотехническом, уровне. Рекомендую прочитать, если вы этого еще не сделали, статьи
- Элементы ЭВМ. АЛУ - арифметико-логическое устройство. Часть 1
- Элементы ЭВМ. АЛУ. Часть 2. Внутренний мир
Статья не является учебником. Не является пересказом учебника, тем более, не является копией. Это рассказ о том, почему умножители строятся именно так. И рассматривать мы будем простейший случай.
Умножение в столбик
Всех нас в школе учили выполнять умножение в столбик, даже если сегодняшние школьники и считают, что это "каменный век, есть же калькуляторы". Правда всем привычно умножение в столбик десятичных чисел, а не двоичных. Поэтому стоит немного внимания уделить особенностям связанным не просто с двоичными числами, а с их представлением в ЭВМ.
- В ЭВМ числа представлены в виде агрегатов данных - тетрада, байт, слово, двойное слово, и т.д. То есть, количество разрядов числа может быть разным, но не любым. В большинстве случаев, количество разрядов кратно 8 (число бит в байте).
- В ЭВМ двоичные числа могут быть знаковыми и беззнаковыми. Знаковые числа могут быть положительными и отрицательными. Однако форма их представления может быть разной. Одним из наиболее распространенных форм представления отрицательных чисел является "дополнение до 2" (дополнительный код). Беззнаковые числа могут быть только положительными.
- В ЭВМ представление целых чисел и вещественных (с дробной частью) существенно различается. Однако, иногда используется представление вещественных чисел как целых с неявно заданным положением запятой. Такой формат представления вещественных чисел называется "числа с фиксированной точкой". В рамках сегодняшней статьи такие числа можно считать целыми.
Более подробно обо всем этом я рассказывал в статье "Простые типы данных. Машинное представление простых типов. Операции с простыми типами.", написанной еще в 1999 году. Там же я говорил, что результат умножения двух двоичных чисел разрядностью N имеет разрядность 2N. И это очень важно.
В сегодняшней статье я буду рассматривать умножение двух 4-разрядных целых чисел, причем чисел беззнаковых.
Умножение в столбик основано на вот таких формулах
Для тех, кто не любит математику это может выглядеть страшновато, но на самом деле тут все просто. Достаточно вспомнить, мы используем позиционные системы счисления. Просто теперь у нас основание системы счисления не 10, а 2. Это и позволяет записать наши сомножители в таком виде (первые две строки иллюстрации).
На третьей строке просто записано собственно умножение, до математических преобразований. Используя простейшие арифметические правила для умножения мы можем получить тот результат, который и показан на последней строке. Причем видно и всем известное "от перестановки сомножителей сумма не меняется".
Теперь мы можем взглянуть на то, как вся эта математика связана с нашим классическим "столбиком"
На этом небольшой экскурс в математику закончен. Теперь можно приступать построению схемы умножителя, который и будет реализовывать всю эту математику "в железе".
Схемотехника умножителя целых двоичных чисел
Каждое слагаемое называется частичным произведением. В общем случае, это результат умножения множимого на очередную цифру множителя. Но для двоичных чисел такое умножение эквивалентно простой операции логического И. Таким образом, формирование частичных произведений в нашем 4-разрядном умножителе будет осуществляться вот такой простейшей схемой
Может возникнуть вопрос, почему я не показал умножение на степень 2 у b? По той причине, что степень 2 у нас будет везде разная, что эквивалентно сдвигу влево каждого очередного частичного произведения в примере умножения столбиком. А наша схема формирует частичное произведение без привязки к таким сдвигам. Что делать со "сдвигами" мы скоро увидим.
Итоговый результат операции умножения формируется из частичных произведений сумматорами. Однако, результат каждой операции сложения будет занимать не 4, а 5 разрядов. Забывать об исходящем переносе нельзя. Причем этот исходящий перенос не будет являться входящим для следующего сложения, он будет складываться лишь со старшим разрядом! Как это показано на следующей иллюстрации
Входящие переносы для операций сложения в целом вообще будут всегда равны 0, в нашем случае. Поскольку устройство сумматора мы уже знаем по второй части статьи про АЛУ (ссылки я давал ранее), мы можем сразу перейти к полной схеме нашего умножителя
Как видно, умножитель имеет довольно регулярную структуру и в точности повторяет способ умножения чисел столбиком. Слева четыре элемента формирования частичных произведений. И три ступени суммирования для получения окончательного результата. Как видно, никаких дополнительных схем сдвига данных не требуется. Умножитель полностью статический.
Схема умножителя не выглядит сложной, но эта простота несколько обманчива. Дело в том, что это очень медленный умножитель, так как я не стал показывать схему ускорения переносов. И дольше всего будет формироваться разряд y7 результата. Причем он будет формироваться долго даже в том случае, если сумматоры имеют внутри схемы ускоренного переноса. Потому что нужно ускорять еще и распространение переноса между сумматорами.
Кроме того, наш умножитель не имеет возможности объединения нескольких умножителей для повышения разрядности. Что бы получить возможность расширения потребуется увеличить разрядность каждого сумматора до 5. Это необходимо для каскадирования умножителей. Добавится и еще одна ступень суммирования. Кроме того, теперь входящие переносы сумматоров тоже будут использоваться для каскадирования.
Я, пожалуй, не буду уделять дополнительного внимания обеспечению наращивания разрядности. В конечном итоге цель статьи показать основные принципы построения умножителя, и не более того. Скажу только, что увеличение разрядности умножителя в два раза, до 8 разрядов, потребует использования не двух, а четырех 4-разрядных умножителей, подобных рассмотренному нами.
Заключение
Схемы реальных умножителей целых двоичных чисел сложнее рассмотренного нами простейшего варианта. И их действительно целесообразнее реализовывать в виде отдельных функциональных блоков, а не включать в состав АЛУ.
Разумеется, нельзя не упомянуть, что существуют частные случаи умножения, которые не требуют построения полноценных умножителей. Это всем известное умножение на степени двойки, которое эквивалентно простому сдвигу влево, что может быть реализовано, например, мультиплексорами.
Но и умножение на константы отличные от степеней двойки иногда можно реализовать без умножителя. Так умножение на 10 можно реализовать как сумму сдвигов на 3 и на 1 разряд. А для этого достаточно простого сумматора.