Тема 6. Двоичная арифметика с фиксированной запятой

1. Формальные правила двоичной арифметики

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

сложение вычитание умножение

0 + 0 = 0 0 - 0 = 0 0 × 0 = 0

0 + 1 = 1 1 - 0 = 1 0 × 1 = 0

1 + 0 = 1 1 - 1 = 0 1 × 0 = 0

1 + 1 = (1)0 0 - 1 = (1)1 1 × 1 = 1

перенос заем

в старший разряд из старшего разряда

Правила поразрядных действий при сложении двух двоичных чисел А + В представлены в табл. 6, где c_{i -1} – перенос из (i - 1)-го разряда, c_i – перенос в (i + 1)-й разряд, s_i – i -й разряд суммы.

Таблица 6

ai	bi	ci -1	si	ci

Правила поразрядных действий при вычитании двух двоичных чисел представлены в табл. 7, где z _i – заем из i -го разряда, c_{i +1} – заем из (i + 1)-го разряда, r_i – i -й разряд разности.

Таблица 7

ai	bi	zi	ri	zi +1
				-1
		-1		-1
		-1
		-1		-1
		-1		-1

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

2. Сложение и вычитание чисел со знаком в форме с фиксированной
запятой

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

Пример. Сложить два числа в прямых кодах: A = +1011, B = +100, n = 4.

Решение. [ A ]_пр = 0.1011; [ B ]_пр = 0.0100

1011 | A |

+ 0100 | B |

1111 | A + B |

[ A + B ]_пр = 0.1111

Ответ: A + B = +1111.

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

Определим правила сложения чисел в дополнительном коде.

Теорема. Сумма дополнительных кодов чисел есть дополнительный код суммы чисел.

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

1. A > 0, В > 0, А + В < 2 ⁿ.

положительное число

Так как [ A ]_доп = A, [ В ]_доп = В, то [ А ]_доп + [ В ]_доп = А + В = [ А + В ]_доп.

2. A < 0, В > 0, | А | > В.

отрицательное число

Так как [ A ]_доп = 2 ^{n +1} + A, [ В ]_доп = В, то [ А ]_доп + [ В ]_доп = 2 ^{n +1} + (А + В) = [ А + В ]_доп.

3. A < 0, В > 0, | А | < В.

Также как и в предыдущем случае здесь

[ A ]_доп = 2 ^{n +1} + A, [ В ]_доп = В, [ А ]_доп + [ В ]_доп = 2 ^{n +1} + (А + В).

Однако в этом случае (А + В) число положительное, и поэтому

2 ^{n +1} + (А + В) > 2 ^{n +1}.

Так как значение этой суммы больше 2 ^{n +1}, то появляется единица переноса из знакового разряда, что равносильно изъятию из суммы 2 ^{n +1} единиц. Если отбросить эту единицу переноса из знакового разряда, то получим

положительное число

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

[ А ]_доп + [ В ]_доп = 2 ^{n +1} + (А + В) = (А + В) = [ А + В ]_доп.

4. A < 0, В < 0, | А + В | < 2 ⁿ.

Так как [ A ]_доп = 2 ^{n +1} + A, [ В ]_доп = 2 ^{n +1} + В, то

отрицательное число

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

[ А ]_доп + [ В ]_доп = 2 ^{n +1} + 2 ^{n +1} + (А + В) = 2 ^{n +1} + (А + В) = [ А + В ]_доп.

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

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

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

Пример. Сложить два числа в дополнительных кодах: A = +1001, B = -101, n = 4.

Решение. [ A ]_доп = 0.1001; [ B ]_доп = 1.1011

0.1001 [ A ]_доп

+ 1.1011 [ B ]_доп

отбрасывается

10.0100 [ A + B ]_доп = [ A + B ]_пр

Ответ: A + B = +100.

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

Определим правила сложения чисел в обратном коде.

Теорема. Сумма обратных кодов чисел есть обратный код суммы чисел.

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

1. A > 0, В > 0, А + В < 2 ⁿ.

положительное число

Так как [ A ]_обр = A, [ В ]_обр = В, то [ А ]_обр + [ В ]_обр = А + В = [ А + В ]_обр.

2. A < 0, В > 0, | А | > В.

Так как [ A ]_обр = 2 ^{n +1} -1 + A, [ В ]_обр = В, то

отрицательное число

[ А ]_обр + [ В ]_обр = 2 ^{n +1} -1 + (А + В) = [ А + В ]_обр.

3. A < 0, В > 0, | А | < В.

Также как и в предыдущем случае здесь

[ A ]_обр = 2 ^{n +1} -1 + A, [ В ]_обр = В, [ А ]_обр + [ В ]_обр = 2 ^{n +1} -1 + (А + В).

Однако в этом случае (А + В) число положительное, и поэтому

2 ^{n +1} -1 + (А + В) > 2 ^{n +1}.

Так как значение этой суммы больше 2 ^{n +1}, то появляется единица переноса из знакового разряда, что равносильно изъятию из суммы 2 ^{n +1} единиц. Кроме того, сумма получается уменьшенной на единицу. Если отбросить единицу переноса из знакового разряда и добавить ее в младший разряд суммы, то получим

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

положительное число

[ А ]_обр + [ В ]_обр = 2 ^{n +1} -1 + (А + В) = (А + В) = [ А + В ]_обр.

4. A < 0, В < 0, | А + В | < 2 ⁿ.

Так как [ A ]_обр = 2 ^{n +1} -1 + A, [ В ]_обр = 2 ^{n +1} -1 + В, то

отрицательное число

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

[ А ]_обр + [ В ]_обр = 2 ^{n +1} -1 + 2 ^{n +1} -1 + (А + В) = 2 ^{n +1} -1 + (А + В) = [ А + В ]_обр.

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

5. A < 0, В > 0, | А | = В.

В этом случае [ A ]_обр = 2 ^{n +1} -1 + A, [ В ]_обр = В, поэтому

равно нулю

равно нулю

n

равно нулю

[ А ]_обр + [ В ]_обр = 2 ^{n +1} -1 + (А + В) = 2 ^{n +1} -1 = 1.11…11 = [-0]_обр,

т.е. сумма равна нулю (получаем одно из изображений нуля в обратном коде).

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

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

Пример. Сложить два числа в обратных кодах: A = +1001, B = -101, n = 4.

Решение. [ A ]_обр = 0.1001; [ B ]_обр = 1.1010

0.1001 [ A ]_обр

+ 1.1010 [ B ]_обр

10.0011

+ 1 циклический перенос

0.0100 [ A + B ]_доп = [ A + B ]_пр

Ответ: A + B = +100.

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

Следует помнить, что при сложении двух одинаковых по абсолютной величине чисел с разными знаками в случае применения обратного кода получается отрицательный нуль 1.11…11. Однако отрицательный нуль в ЭВМ автоматически преобразуется к положительному, т.е. к виду 0.00…00.

Сложение правильных дробей ничем не отличается от сложения целых чисел.

Операция вычитания чисел в ЭВС сводится к операции сложения с использованием дополнительного и обратного кодов.

3. Переполнение при сложении чисел с фиксированной запятой

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

При сложении правильных дробей переполнение означает, что результат по абсолютной величине получился большим или равным единице, а при сложении целых чисел – 2 ⁿ.

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

При сложении чисел в прямом коде признаком переполнения разрядной сетки является появление единицы переноса из старшего разряда значащей части числа.

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

Пример. Сложить два отрицательных числа в дополнительных кодах:

A = -1011, B = -1101, n = 4.

Решение. [ A ]_доп = 1.0101; [ B ]_доп = 1.0011

1.0101 [ A ]_доп

+ 1.0011 [ B ]_доп

отбрасывается

10.1000 [ A + B ]_доп переполнение.

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

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

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

Пример. Сложить два дробных отрицательных числа в дополнительных кодах:

A = -0,1011, B = -0,0101, n = 4.

Решение. [ A ]_доп = 1.0101; [ B ]_доп = 1.1011

1.0101 [ A ]_доп

+ 1.1011 [ B ]_доп

отбрасывается

11.0000 [ A + B ]_доп переполнение.

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

4. Модифицированные коды

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

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

Пример. Записать в модифицированном коде: а) положительное число А = +1011; б) отрицательное число А = -1011.

Решение:

а);

б);;.

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

Признаком переполнения при использовании модифицированных кодов является комбинация 10 (при сложении двух отрицательных чисел) или 01 (при сложении двух положительных чисел) в знаковых разрядах суммы.

Пример. Сложить два отрицательных числа в модифицированных дополнительных кодах: A = -1010, B = -1101, n = 4.

Решение. [ A ]_доп = 11.0110; [ B ]_доп = 11.0011

11.0110 [ A ]_доп

+ 1 1.0011 [ B ]_доп

отбрасывается

110.1001 [ A + B ]_доп комбинация 10 указывает на переполнение.

5. Умножение чисел с фиксированной запятой

Используемая в ЭВС схема умножения похожа на известную из школьного курса процедуру умножения «в столбик». Вычисление произведения P (p _{2 n -1} р _{2 n -2} … p ₁ p ₀) двух n -разрядных двоичных чисел без знака A (a_{n -1} a_{n -2} … а ₁ а ₀) и В (b_{n -1} b_{n -2} … b ₁ b ₀) сводится к формированию частичных произведений (ЧП) W_i по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего согласно весу цифры множителя, которой это ЧП соответствует. Поскольку сомножителями являются двоичные числа, вычисление ЧП упрощается – если цифра множителя b_i, равна 0, то W_i, тоже равно 0, а при b_i = 1 частичное произведение равно множимому (W_i = А). Перемножение двух n -разрядных двоичных чисел Р = А × В приводит к получению результата, содержащего 2 n разрядов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций – сложения и сдвига. Суммирование ЧП обычно производится не на завершающем этапе, а по мере их получения. Это позволяет избежать необходимости хранения всех ЧП, то есть сокращает аппаратные затраты. Процесс получения произведения включает умножение множимого (Мн) А на каждую цифру b_i множителя (Мт) В. Получаемые при этом частичные произведения W_i = Ab_i последовательно складываются (накапливаются), образуя суммы частичных произведений (частичные суммы) СЧП. Последняя сумма частичных произведений равна полному произведению.

Таким образом, процесс умножения n -разрядного двоичного множимого А на n -разрядный двоичный множитель В состоит из повторяющейся n раз последовательности умножения А на каждую очередную цифру В. Такая последовательность называется циклом умножения. На каждом цикле умножения сначала определяется очередное ЧП _i, далее ЧП _i, прибавляется к СЧП _{i -1}, в результате чего определяется очередная сумма частичных произведений СЧП _i, и так до получения СЧП _n.

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

Таким образом, возможны четыре варианта реализации схемы умножения (метода умножения). Методы умножения двоичных беззнаковых чисел основаны на представлении произведения в виде полинома.

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

.

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

1) обнуление СЧП₀;

2) анализ младшего разряда множителя: если b ₀ = 1, выполняется сложение ЧП₀ = A с СЧП₀ и переход к п. 3; если b ₀ = 0, сразу переход к п. 3;

3) сдвиг множимого влево;

4) анализ очередного разряда множителя: если b ₁ = 1, выполняется сложение ЧП₁·2¹ с СЧП₁ и переход к п. 5; если b ₁ = 0, непосредственно переход к п. 5;

5) сдвиг множимого влево;

6) анализ очередного b_i разряда множителя и т.д. После анализа старшего b _{n -1} разряда множителя осуществляется последнее сложение ЧП _{n -1}·2 ^{n -1} с суммой частичных произведений СЧП _{n -1} (если b_{n -1} = 1), и процесс прекращается. Результирующая СЧП _n является искомым произведением.

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

Применив схему Горнера, выражение для произведения можно записать следующим образом:

.

Выражения в скобках в формуле представляют собой последовательные значения СЧП _i, определяемые рекуррентной формулой

.

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

1) обнуление СЧП₀;

2) сдвиг СЧП₀ влево;

3) анализ старшего разряда множителя: если b_{n -1} = l, выполняется сложение ЧП _{n -1} = A с СЧП₀·2¹ и переход к п. 4; если b_{n -1} = 0, сразу переход к п. 4;

4) сдвиг СЧП₁ влево;

5) анализ очередного b_{n -2} разряда множителя и т.д. После анализа младшего b ₀ разряда множителя выполняется последнее сложение ЧП₀ = A с СЧП _{n -1} (если b ₀ = 1), и процесс прекращается.

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

,

где – множимое, сдвинутое влево на n разрядов.

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

1) обнуление СЧП₀;

2) сдвиг множимого вправо;

3) анализ старшего разряда множителя: если b_{n -1} = 1, выполняется сложение ЧП _{n -1}·2^-1 с СЧП₀ и переход к п. 4; если b_{n -1} =0, сразу переход к п. 4;

4) сдвиг множимого вправо;

5) анализ очередного разряда b_{n -2} множителя и т.д. После анализа младшего разряда b ₀ множителя осуществляется последнее сложение ЧП₀·2^-1 с СЧП (если b ₀ =1), и процесс прекращается.

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

Применив схему Горнера к методу 3, выражение для произведения можно записать следующим образом:

;

.

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

1) обнуление СЧП₀;

2) анализ младшего разряда множителя: если b ₀ = 1, сложение ЧП₀ = V с СЧП₀ и переход к п. 3; если b ₀ = 0, непосредственно переход к п. 3;

3) сдвиг СЧП₁ вправо;

4) анализ очередного разряда b ₁ множителя и т.д. После анализа старшего разряда b_{n -1} множителя осуществляются последнее сложение ЧП _{n -1} с СЧП _{n -1} (если b_{n -1} = l) и последний сдвиг СЧП _n вправо, после чего процесс прекращается.

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

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

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

Пример. Умножить по второму методу два целых числа без знака:

A = 1111, B = 101, n = 4.

Решение.

Шаг	Мт	Мн и СЧП	Действие
			СЧП0 = 0
			СЧП0·21 ЧП1 = A · b 3 = 0 СЧП1 = СЧП0·21+ЧП1
			СЧП1·21 ЧП2 = A · b 2 = A СЧП2 = СЧП1·21+ЧП2
			СЧП2·21 ЧП3 = A · b 1 = 0 СЧП3 = СЧП2·21+ЧП3
			СЧП3·21 ЧП4 = A · b 0 = A P = СЧП4 = СЧП3·21+ЧП4

Ответ: A × B = 1001011.

Пример. Умножить по четвертому методу два целых числа без знака:

A = 1111, B = 101, n = 4.

Решение. V = A ·2⁴.

Шаг	Мт	Мн и СЧП	Действие
			СЧП0 = 0
			ЧП1·= V · b 0 = V СЧП1 = СЧП0 + ЧП1 СЧП1 2-1
			ЧП2·= V · b 1 = 0 СЧП2 = СЧП1·2-1 + ЧП2 СЧП2 2-1
			ЧП3·= V · b 2 = V СЧП3 = СЧП2·2-1 + ЧП3 СЧП3 2-1
			ЧП4·= V · b 3 СЧП4 = СЧП3·2-1 + ЧП4 P = СЧП4·2-1

Ответ: A × B = 1001011.

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

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

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

1. Множимое произвольного знака, множитель положительный.

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

Пример. Умножить два целых числа со знаком A = -13, B = +10, n = 4.

Решение. Умножение будем выполнять по четвертому методу.

[ A ]_доп = 1.0011; [ B ]_пр = [ B ]_доп = 0.1010; V = [ A ]_доп·2⁴.

Шаг	Мт	Мн и СЧП	Действие
		0.00000000	СЧП0 = 0
		0.0000 0.00000000 0.00000000	ЧП0·= 0 СЧП1 = СЧП0 + ЧП0 СЧП1 2-1
		1.0011 1.00110000 1.10011000	ЧП1·= V СЧП2 = СЧП1·2-1 + ЧП1 СЧП2 2-1
		0.0000 1.10011000 1.11001100	ЧП2·= 0 СЧП3 = СЧП2·2-1 + ЧП2 СЧП3 2-1
		1.0011 10.11111100 1.01111110	ЧП3·= V СЧП4 = СЧП3·2-1 + ЧП3 [ P ]доп = СЧП4·2-1
		1.10000010	[ P ]пр

Ответ: A × B = -130.

2. Множимое произвольного знака, множитель отрицательный.

Так как множитель отрицателен, он записывается в дополнительном коде [ В ]_доп = 2 ^{n +1} - [ В ], и в цифровых разрядах кода будет представлено число 2 ⁿ - | В |. При типовом умножении (как в случае В ≥ 0) получим Р ´ = А ×(2 ⁿ - | B |) = -| В |× А + А ×2 ⁿ. Псевдопроизведение Р ´ больше истинного произведения Р на величину A ·2 ⁿ, что и необходимо учитывать при формировании окончательного результата. Для этого необходимо выполнить коррекцию результата, которая заключается в том, что после последнего сдвига из полученного псевдопроизведения вычитается избыточная величина A ·2 ⁿ.

Пример. Умножить два целых числа со знаком A = +13, B = -10, n = 4.

Решение. Умножение будем выполнять по четвертому методу.

[ A ]_пр = [ A ]_доп = 0.1101; [ B ]_доп = 1.0110; V = [ A ]_пр·2⁴.

Величина коррекции - A ·2⁴ = [- A ]_доп·2⁴ = 1.0011·2⁴.

Шаг	Мт	Мн и СЧП	Действие
		0.00000000	СЧП0 = 0
		0.0000 0.00000000 0.00000000	ЧП0·= 0 СЧП1 = СЧП0 + ЧП0 СЧП1 2-1
		0.1101 0.11010000 0.01101000	ЧП1·= V СЧП2 = СЧП1·2-1 + ЧП1 СЧП2 2-1
		0.1101 1.00111000 0.10011100	ЧП2·= V СЧП3 = СЧП2·2-1 + ЧП2 СЧП3 2-1
		0.0000 0.10011100 0.01001110	ЧП3·= 0 СЧП4 = СЧП3·2-1 + ЧП3 P ´ = СЧП4·2-1
Коррекция		1.0011 1.01111110	[- A ]доп·24 [ P ]доп
		1.10000010	[ P ]пр

Ответ: A × B = -130.

7. Методы ускорения умножения

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

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

– методы, позволяющие уменьшить количество сложений в ходе умножения;

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

Рассмотрим первую группу логических методов.

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

2 ^m + 2 ^{m -1} + … + 2 ^k = 2 ^{m +1} – 2 ^k,

где m и k – номера крайних разрядов в группе из последовательных единиц. Например, 011110 = 2⁵ - 2¹. Это означает, что при наличии в множителе групп из нескольких единиц (комбинаций вида 011110), последовательное добавление к СЧП множимого с нарастающим весом (от 2 ^k до 2 ^m) можно заменить вычитанием из СЧП множимого с весом 2 ^k и прибавлением к СЧП множимого с весом 2 ^{m +1}.

Алгоритм предполагает три операции: сдвиг, сложение и вычитание. Помимо сокращения числа сложений (вычитаний) у него есть еще одно достоинство – он в равной степени применим к числам без знака и со знаком.

Алгоритм Бута сводится к перекодированию множителя из системы (0, 1) в избыточную систему (-1, 0, 1), из-за чего его часто называют перекодированием Бута (Booth recoding). В записи множителя в новой системе 1 означает добавление множимого к сумме частичных произведений, -1 – вычитание множимого и 0 не предполагает никаких действий. Во всех случаях после очередной итерации производится сдвиг множимого влево или суммы частичных произведений вправо. Реализация алгоритма предполагает последовательный в направлении справа налево анализ пар разрядов множителя – текущего b_i и предшествующего b_{i -1} (b_i b_{i -1}). Для младшего разряда множителя (i = 0) считается, что предшествующий разряд равен 0, то есть имеет место пара b ₀0. На каждом шаге i (i = 0, 1,…, n - 1) анализируется текущая комбинация b_i b_{i -1}.

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

Комбинация 01 соответствует завершению цепочки единиц, и здесь множимое прибавляется к СЧП.

Комбинация 00 свидетельствует об отсутствии цепочки единиц, а 11 – о нахождении внутри такой цепочки. В обоих случаях никакие арифметические операции не производятся.

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

Описанную процедуру рассмотрим на примерах (используется вариант со сдвигом множимого влево).

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

При наиболее благоприятном сочетании цифр множителя количество суммирований равно n /2, где n – число разрядов множителя.

Пример. Умножить два целых числа без знака по алгоритму Бута:

A = 110, B = 11, n = 4.

Решение. [- A ]_доп = 11111010. После перекодирования Мт 0011 приобретает вид 010-1.

Шаг	Мт	Мн и СЧП	Действие
			СЧП0 = 0
	-1		Начало цепочки единиц (-Мн) СЧП1 Сдвиг Мн влево
		--------	Внутри цепочки единиц СЧП2 Сдвиг Мн влево
			Конец цепочки единиц (+Мн) СЧП3 Сдвиг Мн влево
		--------	Вне цепочки единиц P = СЧП4

Ответ: A × B = 10010.

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

A = -4, B = 3, n = 4.

Решение. [ A ]_пр = 0.00000100; [ A ]_доп = 1.11111100; [- A ]_доп = 0.00000100;

[ B ]_пр = [ B ]_доп = 0.0011

Шаг	Мт	Мн и СЧП	Действие
		0.00000000	СЧП0 = 0
	-1	0.00000100 0.00000100 1.11111000	Начало цепочки единиц (-Мн) СЧП1 Сдвиг Мн влево
		---------- 0.00000100 1.11110000	Внутри цепочки единиц СЧП2 Сдвиг Мн влево
		1.11110000 1.11110100 1.11100000	Конец цепочки единиц (+Мн) СЧП3 Сдвиг Мн влево
		-------- 1.11110100	Вне цепочки единиц [ P ]доп = СЧП4
		1.00001100	[ P ]пр

Ответ: A × B = -12.

Модифицированный алгоритм Бута. На практике большее распространение получила модификация алгоритма Бута, где количество операций сложения при любом сочетании единиц и нулей в множителе всегда равно n /2. В модифицированном алгоритме производится перекодировка цифр множителя из стандартной двоичной системы (0, 1) в избыточную систему (-2, -1, 0, 1, 2), где каждое число представляет собой коэффициент, на который умножается множимое перед добавлением к СЧП. Одновременно анализируются три разряда множителя b_{i +1} b_ib_{i -1} (два текущих и старший разряд из предыдущей тройки) и, в зависимости от комбинации 0 и 1 в этих разрядах, выполняется прибавление или вычитание множимого, прибавление или вычитание удвоенного множимого, либо никакие действия не производятся (табл. 8).

Таблица 8

bi +1	bi	bi -1	Код (-2-1 0 1 2)	Выполняемые действия
				Не выполнять никаких действий
				Прибавить к СЧП множимое
				Прибавить к СЧП множимое
				Прибавить к СЧП удвоенное множимое
			-2	Вычесть из СЧП удвоенное множимое
			-1	Вычесть из СЧП множимое
			-1	Вычесть из СЧП множимое
				Не выполнять никаких действий

Пример. Умножить два целых числа со знаком по модифицированному алгоритму Бута: A = 26, B = -18, n = 5.

Решение. [ A ]_пр = [ A ]_доп = 0.0000011010; [- A ]_доп = 1.1111100110;

[-2 A ]_доп = 1.1111001100;

[ B ]_пр = 0.10010; [ B ]_доп = 1.01110

Шаг	Мт	Мн и СЧП	Действие
	1.01110	0.0000000000	СЧП0 = 0
	1.011100 -2	1.1111001100 1.1111001100 0.0001101000	-2Мн СЧП1 Сдвиг Мн влево на 2 разряда
	1.01110	------------ 1.1111001100 0.0110100000	– СЧП2 Сдвиг Мн влево на 2 разряда
	1.01110 -1	1.1001100000 11.1000101100	-Мн [ P ]доп = СЧП3
		1.0111010100	[ P ]пр

Ответ: A × B = -468.

Алгоритм Лемана. Еще большее сокращение количества сложений может дать модификация, предложенная Леманом. Здесь, даже при наименее благоприятном сочетании цифр множителя, количество операций сложения не превышает величины n /2, а в среднем же оно составляет n /3. Суть модификации заключается в следующем:

– если две группы нулей разделены единицей, стоящей в k -й позиции, то вместо вычитания в k -й позиции и сложения в (k +1)-й позиции достаточно выполнить только сложение в k -й позиции;

– если две группы единиц разделены нулем, стоящим в k -й позиции, то вместо сложения в k -й позиции и вычитания в (k +1)-й позиции достаточно выполнить только вычитание в k -й позиции.

Обработка двух разрядов множителя за шаг. Из второй группы логических методов остановимся на умножении с обработкой за шаг двух разрядов множителя. В принципе это более эффективная версия алгоритма Бута. Анализ множителя начинается с младших разрядов. В зависимости от входящей двухразрядной комбинации предусматриваются следующие действия:

00 – простой сдвиг на два разряда вправо суммы частичных произведений (СЧП);

01 – к СЧП прибавляется одинарное множимое, после чего СЧП сдвигается на 2 разряда вправо;

10 – к СЧП прибавляется удвоенное множимое, и СЧП сдвигается на 2 разряда вправо;

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

Так как в случае пары 11 из СЧП вычитается одинарное множимое вместо прибавления утроенного, для корректировки результата к СЧП перед выполнением сдвига надо было бы прибавить учетверенное множимое. Но после сдвига на два разряда вправо СЧП уменьшается в четыре раза, так что на следующем шаге достаточно добавить одинарное множимое. Это учитывается при обработке следующей пары разрядов множителя, путем обработки пары 00 как 01, 01 – как 10, 10 – как 11, а 11 – как 00. В последних двух случаях фиксируется признак коррекции.

Правила обработки пар разрядов множителя с учетом признака коррекции приведены в табл. 9.

Таблица 9

Пара разрядов множителя	Признак коррекции из предыдущей пары	Признак коррекции в следующую пару	Знак действия	Кратность множимого
			+
			+
			-
			+
			+
			-

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

Пример. Умножить два целых числа без знака методом умножения на два разряда множителя: A = 101, B = 1101, n = 4.

Решение.

Шаг	Мт	Мн и СЧП	Действие
			СЧП0 = 0
			+Мн СЧП1 Сдвиг Мн влево на 2 разряда
			-Мн (сдвинутое) СЧП2 Сдвиг Мн влево на 2 разряда
Коррекция, т.к. старшая пара Мт равна 11	101000001	+Мн P

Ответ: A × B = 1000001.

Аппаратные методы ускорения умножения. Аппаратные методы ускорения умножения сводятся:

– к уменьшению времени распространения переносов при суммировании частичных произведений;

– к параллельному вычислению частичных произведений.

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

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

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

8. Деление чисел с фиксированной запятой

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

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

, S = Z - QD, S < D, где Z – делимое, D – делитель.

Деление выражается как последовательность вычитаний делителя (Дт) сначала из делимого (Дм), а затем из образующихся в процессе деления частичных остатков (ЧО). Делимое Z (z _{2 n -l} z _{2 n -2} … z ₁ z ₀) обычно представляется двойным словом (2 n разрядов), делитель D (d_{n -1} d_{n -2} … d ₁ d ₀), частное Q (q_{n -1} q_{n -2} … q ₁ q ₀) и остаток S (s_{n -1} s_{n -2} … s ₁ s ₀) имеют разрядность n.

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

, при и;

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

.

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

.

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

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

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

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

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

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

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

В ЭВС для деления двоичных чисел можно использовать два метода: деление с восстановлением остатка и деление без восстановления остатка.

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

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

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

2) частичный остаток сдвигается на один разряд влево;

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

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

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

В общем случае для определения (n - i)-й цифры частного анализируется частичный остаток. Если ЧО _{i -1} ≥ 0, он сдвигается влево и из него далее вычитается Дт, в результате чего получается остаток ЧО _i. Если же ЧО _{i -1} < 0, то сначала восстанавливается предыдущий положительный (сдвинутый) остаток, для чего к ЧО _{i -1} прибавляется Дт. Далее восстановленный остаток сдвигается влево, из него вычитается Дт, и в результате получается остаток ЧО _i. При ЧО _i ≥ 0 (n - i)-я цифра частного равна единице, при ЧО _i <. 0 – нулю.

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

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

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

2) частичный остаток сдвигается на один разряд влево;

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

4) очередной разряд частного равен единице, когда результат вычитания положительный, и нулю, если он отрицательный;

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

Пример. Разделить с восстановлением остатка Дм A = 41 на Дт B = 7, n = 4.

Решение. A = 00101001; B = 0111; [- B ]_доп = 1.1001

Дм				0111 Дт
ЧО0				0101 Частное 5
Сдвиг ЧО0 влево
-Дт
ЧО1 < 0
+Дт (восстановление ЧО0)
Восстановленный ЧО0
Сдвиг ЧО0 влево
-Дт
ЧО2 > 0
Сдвиг ЧО2 влево
-Дт
ЧО3 < 0
+Дт (восстановление ЧО2)
Восстановленный ЧО2
Сдвиг ЧО2 влево
-Дт
ЧО4 > 0
			Остаток 6

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

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

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

Пример. Разделить без восстановления остатка Дм A = 41 на Дт B = 7, n = 4.

Решение. A = 00101001; B = 0111; [- B ]_доп = 1.1001

Дм				0111 Дт
ЧО0			1001	0101 Частное 5
Сдвиг ЧО0 влево
-Дт
ЧО1 < 0
Сдвиг ЧО1 влево
+Дт
ЧО2 > 0
Сдвиг ЧО2 влево
-Дт
ЧО3 < 0
Сдвиг ЧО3 влево
+Дт
ЧО4 > 0
			Остаток 6

Так как делимое и делитель не обязательно имеют одинаковые знаки, то действия с частичным остатком (прибавление или вычитание D) зависят от знаков остатка и делителя и определяются содержимым табл. 10. Если знак остатка совпадает со знаком делителя, то очередная цифра частного – 1, иначе – 0.

Таблица 10

Знак остатка	Знак делителя	Действие
+	+	Вычитание делителя
+	-	Прибавление делителя
-	+	Прибавление делителя
-	-	Вычитание делителя

После завершения алгоритма может потребоваться коррекция частного:

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

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

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

10. Ускорение целочисленного деления

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

1) замена делителя обратной величиной, с последующим ее умножением на делимое;

2) сокращение времени вычисления частичных остатков в традиционных методах деления (с восстановлением или без восстановления остатка) за счет ускорения операций суммирования (вычитания);

3) сокращение