Построение арифметико-логического устройства для выполнения операции умножения целых чисел

Построение арифметико-логического устройства для выполнения операции умножения целых чисел

АЛУ – основной операционный блок микропроцессора и предназначен для следующих групп операций:

    Арифметические операции с целыми операндами.

Под операндами понимаются N разрядное двоичное слово, которое может быть размещено в регистрах микропроцессора и подвергнуто обработки в АЛУ.

В состав арифметических операций с целыми операндами входят:

    Короткие операции: сложение, вычитание, алгебраическое сложение.

    Длинные операции: умножение, деление целых чисел.

    Логические:

      Дизъюнкция.

      Конъюнкция.

      Операция сравнения на равенство.

    Арифметические операции чисел с плавающей точкой:

    Алгебраическое сложение.

    Умножение.

    Деление.

    Группа специальных арифметических операций:

    Сдвиговые операции.

    Арифметические или логические.

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

    Операции индексной арифметики:

Выполняются при формировании исполнительных адресов с учетом различного состава регистров.

АЛУ могут реализовываться как последовательно, так и параллельно.

    В последовательном АЛУ обработка операндов выполняются последовательно по разрядам операнда. Очевидно, что увеличение длинны операнда приводит к увеличению точности обработки, но требует дополнительных аппаратных затрат и увеличивается время выполнения обработки.

    В параллельных АЛУ в каждый момент времени происходит обработка более одного разряда операнда вплоть до обработки всех разрядов сразу. Они высокопроизводительны и дороги.

По времени выполнения операций АЛУ делятся на асинхронные и синхронные.

    В асинхронных АЛУ длительность выполнения операций зависит от содержания и длины операнда.

    В синхронных АЛУ длительность выполнения операции определяется импульсами синхронизируемого таймера (генератора) и имеет функциональную длительность не зависящую от операндов.

Операционные компоненты АЛУ могут быть выполнены в виде совокупности функциональных блоков, либо в виде одного многофункционального блока, который настраивается на выполнение соответствующей операции по результатам декодирования хода операции.

Второй вариант позволяет выполнить либо части одной операции, либо несколько операций параллельно, тем самым увеличить производительность АЛУ.

В современных микропроцессорах типа Pentium размещается несколько АЛУ, что позволяет увеличить производительность за счет параллельной обработки различных команд выполняемой программы.

В состав АЛУ входят:

    многоразрядный сумматор

    совокупность регистров с цепями сдвига и обратными связями

Любая выполняемая операция в АЛУ представляется последовательностью микроопераций устройством управления, в соответствии с кодом операции текущей команды.

В состав входят:

    рабочий регистр – регистр, имеющий N разрядов

    рабочий регистр сумматора

    параллельный комбинационный N разрядный сумматор

    выходной N разрядный регистр сумматор

    Логическая схема Пр, формирующая признаки результатов выполнения операций.

Каждый регистр оснащается схемами управления, которые позволяют подключить входные цепи к разрядам регистров для их установки, либо выходные цепи для считывания содержимого разрядов регистров (регистр сумматор). Информация из регистра 1 может передаваться в регистр А, либо с использованием прямых кодов, извлекаемых из основных выходов триггеров в составе регистров, либо с использованием инверсных кодов, извлекаемых из инверсных выходов соответствующих триггеров

Входные операнды представляются позиционными входами:

,

где

Xi – значение i -того разряда.

- старший разряд двоичного поля, выделяемый для хранения знака.

Для представления двоичных чисел может использоваться прямой код, обратный и дополнительный.

Прямой код:

Используя 4-х разрядное битовое поле, десятичное число 3 можно представить в следующем виде:

3пр = 0011

-3пр = 1011

Старший разряд определяет знак числа, а числовые разряды определяют значение числа.

      Для выполнения арифметических операций с операндами, представленными в виде двоичного поля, имеющими одинаковый код производится суммирование числовых разрядов операторов. Знак результата совпадает со знаком операнда.

      Если операнды имеют разные знаки, то необходимо определить вначале операнд с большими значениями, из которого вычесть числовые разряды операнда с меньшим значением. Знак результата совпадает со знаком операнда, большего по модулю.

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

Xобр X<0

Чтобы получить обратный код достаточно каждый разряд двоичного поля заменить инверсным значением: -3обр = 1100

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

Дополнительный код получается как дополнение до числа 2n Xдоп . Т.О. чтобы получить дополнительный код числа нужно инвертировать каждый разряд числа и добавить к результату единицу.

Указанное свойство дополнительных кодов для представления отрицательных чисел позволяет заменить операцию вычитания операцией сложения, которую нам представляет сумматор.

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

На практике используется прямой код для представления неотрицательных чисел, и дополнительный - для представления отрицательных. Это дает возможность получать результат в прямом коде, если он положительный, и в дополнительном, если он отрицательный.

В результате операции могут возникнуть следующие ситуации:

      Перенос из знакового разряда при отсутствии переноса в знаковый разряд (эта ситуация соответствует отрицательному переполнению разрядной сетки)

      Наличие переноса в знаковый разряд при отсутствии при отсутствии переноса в знаковый разряд(положительный перенос).

      При отсутствии общих переносов, либо при их обоих наличий, результат размещается в разрядной сетке.

Таким образом приведенная схема формирует в соответствии с алгоритмом: z=xy. Выполнение операции соответствует сложению операндов ч и н. Выполняется прием первого операнда в регистр В. Выполняется прием второго операнда в регистр А.

Второй операнд передается в РгА в коде, который соответствует выполненной операции:

1) прямой при сложении

2) инверсный при вычитании

Сумматор выполняет сложение кодов, при выполнении операции с обратным кодом оператора младшему разряду добавляется 1. Результат операции размещается в регистре сумматора. Если результат положительный, то он представляется прямым кодом, если отрицательный, то дополнительным кодом.

Помимо этого логическая схема Пр формируется признаками результатов выполнения операции

n1 n2

    0

    1 z=0

    0 z<0

1 1 z>0

Указанные условия проверяются соответствующими логическими схемами, которые обеспечивают формирование сигналов n1 и n2 поступающих на устройство управления.

Операция умножения – последовательность операций сложения и сдвига. При этом результат операции при размерности операндов числовые разряды (n-1). Размерность результата (2n-1) – числовой разряд. Если операнды – двоичные слова, то результат тоже. Поскольку в распоряжении имеются аппаратные средства, в виде сумматоров и цепей сдвига по разрядной сетке, то операция умножения представляется как результат последовательного анализа цифр множителя и добавления к текущему значению суммы частичных произведений с первичным нулевым значением множимого, если анализируемая цифра множителя равна единице. После этого сумму частичных произведений или множимое следует сдвинуть по разрядной сетке для выполнения очередной итерации., по сути операция умножения – в трактуемом содержании соответствует умножению «в столбик».

Варианты умножения.

Все компоненты имеют одинаковую размерность, соответствующую слову, обрабатываемому в АЛУ. Регистр множителя должен иметь цепи сдвига вправо. Сумматор частичных произведений должен иметь также цепи сдвига вправо. Причём, младшие разряды соединяются со старшими разрядами регистра множителя. В результате производится анализ младшей цифры множителя после чего, если равны «1», то к текущему значению суммы частичных приведений (который первоначально равен «0») добавляется содержимое регистра множимого. Если, анализируемая цифра равна «0», то операция сложения не выполняется после этого содержимое регистра множителя сдвигается вправо на один разряд и в освободившийся старший разряд регистра множителя переносится младший разряд суммы частичных произведений, в результате сдвига её вправо по разрядной сетке. Далее продолжается с анализа разряда. В результате после окончания операции в регистре множителя: младший разряд результата, а в сумматоре – старшая часть разряда.

В данном варианте используется двойная размерность сумматора частичных произведений и двойная размерность регистра множимого. Как и в 1-м варианте регистр множителя имеет цепи сдвига вправо по разрядной сетке, а регистр множимого – влево по разрядной сетке. Сумматор частичных произведений не оснащён цепями сдвига. Аналогично производится анализ младшего разряда множителя, и если он равен «1», то производится произведение текущей суммы и содержимого регистра множимого. После этого производится сдвиг вправо содержимого регистра множителя и сдвиг влево содержимого регистра множимого. Аналогично рассматриваются варианты со старшим разрядом.

Сумматор частичных произведений имеет цепи сдвига влево и регистры множителя тоже. Действия аналогично. Если анализируемая цифра множителя равна «1», то к текущему значению суммы частичных произведений добавляются содержимое регистра множимого. Выполняется сдвиг влево по разрядной сетке и содержимого сумматора и всё до окончания анализа всех разрядов множителя. В результате произведение размещается в сумматоре частичного произведения.

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

Достоинства I, II, IV – возможность более эффективно реализовывать операцию деления. Кроме того II, IV варианты, имеющие неподвижную сумму частичных произведений позволяют параллельно выполнять операцию суммирования и сдвига, что есть производительнее.

Будем рассматривать I вариант.

Алгоритм операции умножения.

Будем считать, что операнды представлены прямым кодом, т.е. старший разряд знаковый, остальные – числовые.

    Берутся модули от сомножителей;

    Сумма частичных произведений полагается равной нулю;

    Анализируется младший разряд множителя, если значение «1», то к текущему значению суммы частичных произведений добавляется множимое;

    Содержимое регистра множителя и сумматора частичных произведений сдвигается вправо на одно деление;

    п.3 и п.4 повторяются для всех разрядов множителя.

    Для окончательного размещения результата в двоичном виде производят сдвиг вправо на 1 разряд.

    Знак результата полагается «0», если сомножители имеют одинаковый знак и «1» (отрицательный результат), если сомножители имеют разные знаки. Операция не производится, если один из «0», и результат равен «0».

Основа для алгоритма является: Z=X(множимое)*Y(множитель)

Y – представим как соответствующие степени

Y=y>n-2 >2n-2 + y>n-3>2n-3+ y>0 >20, тогда

Z=x*(y>n-2 >2n-2 + y>n-3>2n-3+y>0 >20) =x*2n-1(y>n-2 >2-1 + y>n-3>2-2+ y>0 >2--(n--1))=

=2n-1((..(0+x* y>0>)z--1 + x* y>1>)* 2--1 +…+x*y> n-1>) 2-1 =A*2n-1.

Текущему значению суммы частичных произведений добавляется множимое, если соответствующий разряд равен «1» и далее суммы частичных произведений сдвигаются вправо и т.д. Перенеся условную точку вправо через (n-1) разряд мы получим результат.

Рг1 для приёма множимого; Рг2 для приёма множителя. Входной РгА сумматора для размещения в нём очередной добавляемой компоненты к сумме частичных произведений. Входной РгБ См используется для размещения текущего значения суммы частичных произведений. Рг2' используется для формирования сдвига множителя вправо по разрядной сетке. Выходной РгСм, в котором формируются текущее значение суммы частичных произведений. Счётчик циклов используется для отображения количества обрабатываемых разрядов множителя.

На 1-м этапе выполняется размещение множимого в Рг1. Множимое может передаваться в РгА в прямом или инверсном кодах. На 2-м этапе в Рг2 размещается множитель, поступающий по ШД. Обнуляется содержимое РгВ, используемое вы качестве начального значения суммы частичных произведений. Далее анализируется младшая цифра множителя в Рг2. Если она =1, то в РгА передаётся содержимое Рг1 и на выходе См формируется текущее значение суммы частичных произведений. Одновременно передают множитель для анализа очередной цифры. Для этого его содержимое передаётся в Рг2' с сдвигом вправо на 1 по разрядной сетке. В свободный разряд Рг2' помещается младший разряд со входа См. Остальные разряды См предаются в РгСм со сдвигом вправо на 1 разряд. После этого значение РгСм размещается в РгВ. Содержимое Рг2' размещается в Рг2 и значение СчЦ уменьшается на 1 по отношению к первоначальному значению, равному количеству числовых разрядов.

Процесс продолжается для следующей цифры множителя. Когда содержимое СчЦ становится =0, процесс анализа завершается с получением в РгСм старших разрядов и в Рг2 младших разрядов произведения. После этого выполняется ещё 1 цикл с 0 значением РгА для правилного размещения результата в разрядной сетке двойного слова.

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

Алгоритм умножения целых чисел с использованием прямого кода для положительных чисел и дополнительного для отрицательных.

1.Фиксируется знак сомножителей в специальных триггерах.

2.Сумма частичных произведений полагается =0.

3.Анализируется младшая цифра множителя. Если она =1, то к сумме частичных произведений добавляется множимое в том коде, в котором оно представлено. Если она =0, то добавление не производится.

4.Выполняется сдвиг вправо суммы частичных произведений на 1 разряд, причём, если значение суммы ≥0, то производится обычный сдвиг. Если текущее значение суммы частичных произведений <0, то производится модифицированный сдвиг с занесением 1 в знаковый разряд.

5.Пункты 3 и 4 повторяются для всех числовых разрядов множителя.

6.Если множитель ≥0, то текущее значение суммы частичных произведений представляет собой результат в прямом коде для положительного значения и в дополнительном коде для отрицательного значения. Если множитель <0, то к текущему значению суммы частичных произведений необходимо добавить множимое с обратным знаком.

7.Размещение результатов в формате двойного слова путём сдвига суммы частичных произведений вправо на 1 разряд.

Z = X * Y, Y > 0

Алгоритм тот же, за исключением модифицированного сдвига. При этом может возникнуть следующее: если младший разряд множителя =0, а множимое <0, то нет необходимости выполнять модифицированный сдвига (нельзя), поскольку сумма частичных произведений =0, а нуль в дополнительном коде знака не имеет. И лишь только с появлением отрицательного значения суммы частичных произведений сдвиг должен быть модифицированным.

Y < 0

Y>доп> = 2n - |Y|

Весовой коэффициент: 2n-1. Поэтому, если вычислить псевдопроизведение:

Z' = X * (2n-1 - |Y|) = -X * |Y| + X * 2n-1

Z' больше истинного значения на величину множимого, поэтому на завершительном этапе перед размещением результатов в формате двойного слова перед последним сдвигом необходимо из результата вычесть множимое. Поэтому при СчЦ = 0 к текущему значению суммы частичных произведений добавляют множимое с обратным знаком.