19333

АУ C ФИКСИРОВАННОЙ ЗАПЯТОЙ

Лекция

Информатика, кибернетика и программирование

АК ЛЕКЦИЯ № 10 АУ C ФИКСИРОВАННОЙ ЗАПЯТОЙ Базис целочисленных операционных устройств Для большинства современных ВМ общепринятым является такой формат с фиксированной запятой ФЗ когда запятая фиксируется справа от младшего разряда кода числа. По этой причине со...

Русский

2013-07-11

425.5 KB

28 чел.

АК ЛЕКЦИЯ № 10 АУ C ФИКСИРОВАННОЙ ЗАПЯТОЙ

Базис целочисленных операционных устройств

Для большинства современных ВМ общепринятым является такой формат с фиксированной запятой (ФЗ), когда запятая фиксируется справа от младшего разряда кода числа. По этой причине соответствующие операционные устройства называют целочисленными ОПУ. В форме с ФЗ могут быть представлены как числа без знака, когда все п позиций числа отводятся под значащие цифры, так и со знаком. В последнем случае старший (п - 1)-й разряд числа занимает знак числа (0 — плюс, 1 — минус), а под значащие цифры отведены разряды с (п - 2)-го по 0-й.

При записи отрицательных чисел используется дополнительный код, который для числа N получается по следующей формуле:

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

• сложение/вычитание;• сложение/вычитание;

• умножение;

• деление.

АУ для сложения

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

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

Вычитание выполняется в соответствии с правилом: для вычитания одного чисда (вычитаемого) из другого (уменьшаемого) необходимо взять дополнение вычитаемого и прибавить его к уменьшаемому. Под дополнением здесь понимается вычитаемое с противоположным знаком, представленное в дополнительном коде. Вычитание иллюстрируется примерами (рис. 7.11). Два последних примера (см. рис. 7.11, д и 7.1 \,е) демонстрируют ранее рассмотренное правило обнаружения переполнения.

Чтобы упростить обнаружение ситуации переполнения, часто применяется так называемый модифицированный дополнительный код, когда для хранения знака отводятся два разряда, причем оба участвуют в арифметической операции наравне с цифровыми разрядами. В нормальной ситуации оба знаковых разрядах содержат одинаковые значения. Различие в содержимом знаковых разрядов служит признаком возникшего переполнения (рис. 7.12).

На рис. 7.13 показана возможная структура операционного блока для сложения и вычитания чисел со знаком в формате с фиксированной запятой. Центральным звеном устройства является n-разрядный двоичный сумматор. Операнд А поступает на вход сумматора без изменений. Операнд В предварительно пропускается через схемы сложения по модулю 2, поэтому вид кода В, поступающего на другой вход сумматора, зависит от выполняемой операции. Если задана операция сложения (управляющий код 0), то результат на выходе ОПБ определяется выражением S.= А + В. При операции вычитания (управляющий код 1) на вход сумматора подаются инверсные значения всех разрядов В, и, кроме того, на вход переноса в младший разряд сумматора С  поступает 1. В итоге на выходе ОПБ будет S = А + В + 1, что соответствует прибавлению к А числа В с противоположным знаком, то есть вычитанию.

На рис. 7.13 не показана схема формирования признака переполнения V, который согласно описанным ранее правилам определяется логическим выражением

Целочисленное умножение

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

Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) Wi  по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего согласно весу цифры множителя, которой это ЧП соответствует. Поскольку операндами являются двоичные числа, вычисление ЧП упрощается — если цифра множителя bi равна 0, то Wi тоже равно 0, а при bi = 1 частичное произведение равно множимому (Wi = A). Перемножение двух n-разрядных двоичных чисел Р - А х В приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций — сложения и сдвига (рис. 7.14). Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратурные издержки. Согласно данной схеме, устройство умножения предполагает наличие регистрв множимого, множителя и суммы частичных произведений, а также сумматора ЧП и, возможно, схем сдвига, если операция сдвига не реализована иным способом, например за счет «косой» передачи данных между узлами умножителя.

В зависимости от способа получения суммы частичных произведений (СЧП) возможны четыре варианта реализации «традиционной» схемы умножения [10]:

1. Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо и при неподвижном множимом.

2. Умножение, начиная со старших разрядов множителя, при сдвиге суммы частичных произведений влево и неподвижном множимом.

3. Умножение, начиная с младших разрядов множителя, при сдвиге множимого влево и неподвижной сумме частичных произведений.

4. Умножение, начиная со старших разрядов множителя, со сдвигом множимого вправо и при неподвижной сумме частичных произведений.

Варианты со сдвигом множимого на практике не используются, поскольку для их реализации регистр множимого, регистр СЧП и сумматор должны иметь разрядность 2n, поэтому остановимся на вариантах 1 и 2. Первый из них назовем алгоритмом сдвига вправо, а второй — алгоритмом сдвига влево.

Умножение чисел без знака

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

Алгоритм сдвига вправо

Алгоритм сводится к следующим шагам:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается с младшей цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

3. Выполняется сдвиг суммы частичных произведений вправо на один разряд,

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

Процедура умножения иллюстрируется примером вычисления произведения 10x11 (рис. 7.15)

Первоначально множимое и множитель заносятся в n-разрядные регистры множимого (РМт) и множителя (РМт) соответственно, а все разряды 2n-разрядного регистра суммы частичных произведений (РЧП) устанавливаются в 0. Умножение происходит за n шагов. На каждом шаге, в зависимости от состояния младшего разряда регистра множителя, управляющего мультиплексором, на один из входов n-разрядного сумматора подается либо множимое, либо 0. На второй вход поступает содержимое п старших разрядов РЧП. Новое частичное произведение из сумматора пересылается в старшие разряды РЧП. Далее содержимое РЧП сдвигается на один разряд вправо, причем в освободившийся старший разряд регистра заносится значение переноса из старшего разряда сумматора. Поскольку мультиплексор управляется младшим разрядом РМт, то содержимое этого регистра также сдвигается на один разряд вправо. Описанная последовательность повторяется п раз. Более экономичным в плане аппаратуры является иное решение, когда вместо двух регистров — n-разрядного РМт и 2м-разрядного РЧП — используется один комбинированный 2л-разрядный регистр (показан на рис 7.16 справа). Множитель первоначально заносится в младшие п разрядов этого регистра, а старшие разряды обнуляются. По мере сдвигов вправо младшие, уже проанализированные разряды множителя выталкиваются из регистра, освобождая место для очередной цифры СЧП. Обычно такой регистр строится из двух n-разрядных регистров, объединенных цепями сдвига. Дополнительно отметим, что если очередная цифра множителя равна 1, то для вычисления суммы ЧП требуются операции сложения и сдвига, а при нулевой цифре множителя в принципе можно обойтись без сложения, ограничившись только сдвигом. Это, естественно, требует некоторого видоизменения схемы.

Алгоритм сдвига влево

Процедура традиционного умножения со сдвигом влево включает в себя следующие шаги:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается со старшей

цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

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

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

На рис. 7.17 приведен пример умножения со сдвигом влево(10х 11).

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

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

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

Рис. 7.17 Пример умножения со сдвигом влево

Рис. 7.18. Схема устройства умножения по алгоритму левого сдвига

Целочисленное деление

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

Задача сводится к вычислению частного Q и остатка S:

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

Операция выполняется за n итераций и может быть описана следующим образом:

После п итераций получается

Частное от деления 2n-разрядного числа на n-разрядное может содержать более, чем п разрядов. В этом случае возникает переполнение, из-за чего перед выполнением деления необходима проверка условия

Из выражения следует, что переполнения не будет, если число, содержащееся в старших п разрядах делимого, меньше делителя.

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

Реализовать деление можно двумя основными способами:

- с неподвижным делимым и сдвигаемым вправо делителем;

- с неподвижным делителем и сдвигаемым влево делимым.

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

Ниже на. примере чисел без знака рассматриваются два основных алгоритма целочисленного деления.

Деление с восстановлением остатка

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

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

2. Частичный остаток удваивается путем сдвига на один разряд влево. При этом в освобождающийся при сдвиге младший разряд 40 заносится очередная цифра частного.

3. Из сдвинутого Ч0 вычитается делитель и анализируется знак результата вычитания.

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

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

На рис. 7,48 показан процесс деления с восстановлением остатка, здесь число 41 делится на 8.

Деление без восстановления остатка

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

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

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

2, Частичный остаток удваивается путем сдвига на один разряд влево. При этом в освобождающийся при сдвиге младший разрядЧ0 заносится очередная цифра частного.

3, Из сдвинутого частичного остатка вычитается делитель, если остаток положителен, и к сдвинутому частичному остатку прибавляется делитель, если остаток отрицательный.

4. Очередная цифра модуля частного равна единице, когда результат вычитания положителен, и нулю, если он отрицателен.

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

Как видим, пункты 1,2,5 полностью совпадают с соответствующими пунктами предыдущего алгоритма деления.

Процесс деления без восстановления остатка для ранее рассмотренного примера демонстрируется на рис. 7.49.

Деление чисел со знаком

Как и в случае умножения, деление чисел со знаком может быть выполнено путем перехода к абсолютным значениям делимого и делителя, с последующим присвоением частному знака «плюс» при совпадающих знаках делимого и делителя либо «минус» — в противном случае.

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

Так как делимое и делитель не обязательно имеют одинаковые знаки, то действия с частичным остатком (прибавление или вычитание D) зависят от знаков остатка и делителя и определяются содержимым табл. 7,5:

Таблица 7.5

И Если знак остатка совпадает со знаком делителя, то очередная цифра частного — 1, иначе — 0.

- Ecли Z>0 и D< 0, частное необходимо увеличить на 1.

- Если Z < 0 и D > 0, то при ненулевом остатке от деления частное нужно увеличить на единицу.

- Если Z < 0 и D < 0, то при нулевом остатке от деления частное нужно увеличить на единицу.

Остаток всегда приводится к положительному числу, то есть если по завершении деления он отрицателен, к нему следует прибавить модуль делителя.

Устройство деления

Рассмотренный алгоритм деления без восстановления остатка может быть реализован с помощью устройства, схема которого приведена на рис. 7.50.

Процедура начинается с занесения делимого в 2n-разрядный регистр делимого (РДМ) и делителя в n-разрядный регистр делителя (РДТ). В счетчик цикла (СЧЦ — на схеме не показан), служащий для подсчета количества полученных цифр частного, помещается исходное значение, равное п.

На каждом шаге содержимое регистра делимого (РДМ) и регистра частного (РЧ) сдвигается на один разряд влево. В зависимости от сочетания знаков частичного остатка и делителя определяется значение очередной цифры частного и требуемое действие: вычитание или прибавление делителя. Вычитание делителя производится посредством прибавления дополнительного кода делителя. Преобразование в дополнительный код осуществляется за счет передачи делителя на вход сумматора обратным (инверсным) кодом с последующим добавлением единицы к младшему разряду сумматора.

Описанная процедура повторяется до исчерпания всех цифр делимого, о чем свидетельствует нулевое содержимое счетчика циклов (содержимое СЧЦ уменьшается на единицу после каждой итерации). По окончании операции деления частное располагается в регистре частного, а в регистре делимого будет остаток от деления.

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

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