8.6. Умножители

Настоящий раздел посвящен умножителям, играющим особенно важную роль в устройствах цифровой обработки сигналов. С точки зрения принципа действия умножители можно разделить на многотактные и матричные. В обоих случаях произведение является результатом последовательных сложений с той лишь разницей, что достаточный параллелизм матричных умножителей позволяет обойтись без запоминания промежуточных результатов. Сначала кратко рассмотрим применяемые в умножителях системы числения, а затем опишем различные алгоритмы многотактного и матричного умножения. Более полный анализ систем счисления содержится в пятой главе.

Фиг. 8.29. Блок-схема умножения на основе сложения и сдвига.

При анализе систем счисления было описано представление чисел в прямом (с использованием знака и величины), обратном и дополнительном кодах. Сравнение двух последних систем счисления показало, что дополнительный код больше подходит для выполнения высокоскоростных операций, поэтому в дальнейшем будут рассматриваться только прямой и дополнительный коды. Перемножение чисел в прямом коде несколько проще, чем в дополнительном, поэтому сначала будут рассмотрены способы умножения положительных чисел. Однако больше внимания будет уделено методам умножения чисел в дополнительном коде, так как сложение двух чисел в прямом коде менее удобно, чем в дополнительном.

На фиг. 8.29 изображена схема простого умножителя пятиразрядного числа на четырехразрядное, использующего сложения и сдвиги. Если соответствующее значение у из правого столбца равно 1, то в этом устройстве последовательно накапливаются следующие слагаемые:

При  на сумматор с выхода вентилей поступают нули. После логического умножения и накопления очередной строки сумма сдвигается на один разряд вправо, чтобы обеспечить в соответствии с требованием алгоритма добавление следующей строки в более старшие разряды. По команде тактового импульса 1 (см. наверху) разряды  последовательно поступают на вентили И и обеспечивают подачу на вход сумматора либо числа  либо нуля. После окончания цикла сложения по команде тактового импульса 2 результат суммирования заносится в триггерный регистр накопителя и затем после завершения процесса установления сдвигается на один разряд вправо. Этот умножитель достаточно простой, но и медленный. Поскольку в сумматоре отсутствует схема ускорения переноса, операция накопления завершается лишь после того, как сигнал переноса пройдет через весь сумматор. Наибольшее значение времени установления для -разрядного сумматора примерно равно, где   — соответственно время распространения переноса и время образования суммы в одноразрядном сумматоре,  — время установления регистра сдвига . Если -разрядное число умножается на -разрядное, то общее время умножения будет приблизительно равно .

Приведенная на фиг. 8.29 схема отражает тот важный с аппаратурной точки зрения факт, что в умножителях, основанных на сложении и сдвиге, разряды  хранятся в последовательном сдвиговом регистре. В гл. 9 будет показано, что представление данных в виде последовательного потока положительно влияет на структуру цифрового фильтра и приводит к снижению стоимости его памяти.

Рассмотрим теперь, каким образом следует модифицировать этот умножитель для работы с числами разного знака, заданными в дополнительном коде. Напомним сначала формулы для представления и перемножения чисел в дополнительном коде. Значение числа , представленного в дополнительном коде, равно

,         (8.9)

где  — разряды дополнительного кода, а  — знаковый разряд, причем сумма понимается в арифметическом, а не логическом смысле. В качестве упражнения предлагаем читателю, используя уравнение (8.9), составить алгоритм перевода числа в дополнительном коде из положительного в отрицательное.

Из формулы (8.9) можно получить арифметическое выражение для произведения  двух чисел в дополнительном коде, когда  и  соответственно -  и -разрядные числа:

                       (8.10)

Первый и четвертый члены в правой части (8.10) — положительные числа, второй и третий — отрицательные. Четвертый член равен окончательному результату в случае перемножения положительных чисел, который получается при последовательных сложениях в схеме на фиг. 8.29. Из равенства (8.10) видно, что если  или  равны единице, то суммы должны как складываться, так и вычитаться. Модификация логической структуры умножителя, основанного на сложении и сдвиге, учитывающая знаковые разряды, известна под названием алгоритма Бута. Чтобы понять этот алгоритм, представим число  в следующем виде:

    (8.11)

Итак, при последовательном умножении множимого () на разряды множителя () операции будут производиться над последовательными строками, составленными из разрядов , по следующим правилам:

1. Если , то накапливается не множимое, а нулевая строка.

2. Если , а , то множимое добавляется в накопитель.

3. Если , а , то множимое вычитается из накопителя.

В качестве примера читателю предлагается, используя алгоритм Бута, умножить  на  и, кроме того, модифицировать схему на фиг. 8.29 для реализации этого алгоритма.

Скорость выполнения алгоритма Бута можно увеличить в два раза, сдвигая множитель сразу на два разряда и анализируя одновременно три соседних разряда, чтобы определить характер накопления множимого; этот вариант также рекомендуется для самостоятельной проработки.

Самые быстрые умножители состоят из двумерной матрицы одноразрядных сумматоров и называются матричными умножителями. В отличие от многотактного умножителя (фиг. 8.29) матричный умножитель представляет собой законченную логическую схему без элементов памяти, поэтому результат умножения образуется после подачи сомножителей за время, равное времени установления схемы. Существует много различных вариантов построения матрицы, причем они могут быть достаточно хорошо классифицированы по методам соединения сумматоров и обработки отрицательных чисел. На фиг. 8.30 показан пример не слишком быстродействующего матричного умножителя, оперирующего с положительными числами. Каждый кружок обозначает одноразрядный сумматор. Видно, что каждая строка сумматоров представляет собой многоразрядный сумматор с распространением переноса. Она формирует частичную сумму и передает ее последующей строке. Чтобы оценить время установления в таком умножителе, учтем, что разряд результата  образуется спустя время, равное  задержкам суммирования и  задержкам переноса, а разряд  — на  задержек переноса позже. Таким образом, общее время установления  равно

                              (8.12)

Фиг. 8.30. Матричный умножитель положительных чисел  и

Эта величина значительно меньше, чем для схемы на фиг. 8.29. Если обеспечить распространение сигналов переноса по диагонали (фиг. 8.31),то суммарную задержку можно уменьшить. В этом случае безразлично, на какую строку поступает перенос от предыдущего столбца. Схемы, показанные на фиг. 8.30 и 8.31, дают одно и то же произведение, однако последняя имеет преимущество, поскольку сигналы переноса и сумм, распространяющиеся от сумматоров в младших разрядах, одновременно поступят на сумматоры в более старших разрядах. Это так называемая схема с сохранением переноса, которая применяется не только для матричных умножителей.

Фиг 8.31 Структура матричного умножителя, более быстродействующего по сравнению со схемой, изображенной на фиг. 8.30.

Например, сигнал на выходе  в столбце 8 появится спустя время, равное пяти задержкам суммирования или восьми задержкам переноса, в зависимости от того, какой отрезок времени длиннее. Если они равны, то временем суммирования можно пренебречь. Поэтому для последней строки сумматоров нужно учитывать суммарное время переноса. Таким образом, если, то в наихудших условиях находится выход , задержка образования которого равна . В противном случае время умножения будет равно . Итак,

|                 (8.13)

При использовании одноразрядных сумматоров, у которых  значительно больше, чем , нужна схема умножителя с минимальным числом последовательно выполняемых сложений. Идея построения такого умножителя с матрицей сумматоров, организованной в виде «дерева», иллюстрируется на фиг. 8.32. Он предназначен для умножения -разрядного множимого на 16-разрядный множитель. Каждый из кружков обозначает -разрядный сумматор. При такой организации время суммирования будет лишь учетверяться. Общее количество сумматоров остается прежним, но больше строк сумматоров работает теперь параллельно. Блок-схема умножителя такого типа с разрядностью, равной, как и раньше, (6х8), в котором сигналы переноса распространяются вдоль строк, показана на фиг. 8.33. Суммирование в каждой строке сумматоров происходит за время формирования переноса, равное . Поскольку таких уровней суммирования четыре, общее время умножения равно . Таким образом, если  не очень велико, эффективность данной схемы ниже, чем приведенной на фиг. 8.31.

Фиг. 8.32. Древовидная структура матричного умножителя.

Возможно, что наибольшего быстродействия можно достичь, сочетая идеи древовидного соединения и диагонального распространения переносов. Соответствующая структурная схема приведена на фиг. 8.34. Так как эта структура обладает, по-видимому, наибольшим быстродействием из рассмотренных выше матричных схем, возникает вопрос о целесообразности рассмотрения других матричных структур. Ответ на этот вопрос может быть получен только в процессе проектирования системы на основе конкретных интегральных схем. Обычно ИС разрабатываются и выпускаются в расчете на самые разнообразные применения. Поэтому при создании матричного умножителя разработчик должен выбрать наиболее подходящие ИС из числа имеющихся. В качестве примера рассмотрим выпущенную в 1971 г. интересную ИС МС10181, которая представляет собой четырехразрядный сумматор с ускоренным переносом. На ее основе можно построить диагональную (как на фиг. 8.31) или горизонтальную (как на фиг. 8.30 и 8.33) структуры. Хотя схема, приведенная на фиг. 8.31, и оказывается более быстродействующей, для формирования частичных произведений  требуются дополнительные корпусы. В схеме с горизонтальным распространением переносов эти корпусы не нужны, поскольку каждый управляющий разряд можно логически умножить сразу на четыре входных разряда. Итак, выбор «наилучшей» схемы определяется характеристиками используемых микросхем и компромиссом между быстродействием и стоимостью умножителя.

Фиг. 8.33. Древовидный матричный умножитель размером (6x8)

Фиг. 8.34. Матричный умножитель с диагональным распространением переноса и древовидной организацией суммирования.

Рассмотрим умножение чисел, представленных в дополнительном коде, пользуясь основной формулой (8.9). Сущность этой формулы состоит в следующем: каждый разряд, за исключением знакового, принимает арифметические значения 0 или 1, а знаковый — значения 0 или -1. При таком подходе, выполняя суммирование согласно формуле (8.9), всегда будем получать правильный результат.

Одноразрядный сумматор может быть описан подобно тому, как это делалось ранее, с помощью логических уравнений или таблицы истинности. Если каждый из трех входных разрядов принимает (арифметические) значения 0 или 1, то двухразрядный выход может иметь значения 0, 1, 2 или 3. При реализации этой функции значения 0 или 2 приписываются разряду переноса, а значения 0 или 1 — разряду суммы; оба эти разряда описывают выход сумматора. Таблица истинности (Т.И.4) дает состояния выходных разрядов сумматора — суммы  (младший разряд) и переноса  — в зависимости от состояния входов ,  и . Ясно, что совершенно необязательно обозначать два возможных состояния выходных разрядов либо нулем, либо единицей; для этого можно использовать + или —, 0 или 2, 0 или 100 и т. д. Система обозначений, интуитивно принятая в таблице истинности (Т.И.4), фактически соответствует двоичному представлению выхода сумматора:

           (Т.И.4)

, ,  — входы;  — сумма (булева);  — перенос (арифметическая сумма минус булева сумма). Эту систему обозначении можно обобщить на случай арифметического суммирования и положительных и отрицательных чисел. Рассмотрим, например, трехвходовую схему, у которой один из входных сигналов принимает значения — 1 или 0, а два других — значения 0 или 1. В этом случае сумма по-прежнему принимает четыре возможных значения -1, 0, +1, +2 и может быть представлена двухразрядным числом с младшим разрядом, равным 0 или -1, и старшим, равным 0 или 2.

Снова из таблицы истинности такой логической схемы (Т.И.5) следует, что результат сложения в сумматоре, рассматриваемый как арифметическая сумма двух выходов, соответствует также арифметической сумме всех трех входов. Аналогично можно рассмотреть еще два случая с таблицами истинности (Т.И.6) и (Т.И.7).

Воспользовавшись введенной системой обозначений и располагая интегральными схемами, способными суммировать отрицательные числа, можно построить матричный умножитель чисел в дополнительном коде, основанный на последовательных сложениях. Пример такого умножителя, в котором использованы три типа интегральных схем, — обычные сумматоры, описываемые таблицей истинности (Т.И.4), а также сумматоры, соответствующие (Т.И.6) и (Т.И.7), — показан на фиг. 8.35.

Фиг. 8.35. Матричный умножитель чисел в дополнительном коде размером (6х5).

               (Т.И.5)

                 (Т.И.6)

Таблица 8.2. Сравнение различных умножителей

Продолжение таблицы 8.2.

               (Т.И.7)

В табл. 8.2 даны некоторые оценки, рассчитанные для различных вариантов построения умножителей. Здесь приведены оценки времени умножения и требуемого числа корпусов интегральных схем с 16 выводами для трех умножителей чисел в дополнительном коде. Поскольку серийно выпускаемый четырехразрядный сумматор имеет 24 вывода, рассчитывалось эквивалентное количество ИС с 16 выводами; во всех остальных случаях использовались только корпусы с 16 выводами. Анализ этой таблицы позволяет сделать несколько интересных замечаний. Из первой строки видно, что специально разрабатываемые ИС (они будут описаны в разд. 8.8) имеют заметные преимущества перед серийными. Из сопоставления строк 2 и 3 (а также 6 и 7) можно оценить увеличение быстродействия умножителя при замене ИС ТТЛ на более быстродействующие ИС ЭЛС; оно возросло более чем в два раза. Влияние структуры умножителя как на его быстродействие, так и на количество корпусов можно проследить, обратившись к строкам 1 и 5; несколько неожиданно, что наилучший компромисс между быстродействием и числом корпусов достигается при построении матричных умножителей. Одной из причин является чрезвычайно простое управление матричным умножителем по сравнению с многотактным (строки 5, б, 7). Интересно также отметить, что с точки зрения общего количества корпусов двухразрядный сумматор с 16 выводами (строка 1) оказывается выгоднее использовать, чем четырехразрядный сумматор с 24 выводами (строка 2 или 3). Таким образом, в некоторых структурах, когда кристалл размещается в корпусе больших размеров, увеличение уровня интеграции может оказаться даже вредным.