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

Подтема № 1- Операция сложения и вычитания, двоичных беззнаковых чисел в компьютерных системах

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

Правила сложения:	Правила вычитания:
1. 0 + 0 = 0	1. 0 - 0 = 0
2. 0 + 1 = 1	2. 1 - 1 = 0
3. 1 + 0 = 1	3. 1 - 0 = 1
4. 1 + 1 = 10	4. 10 - 1 = 1

Рисунок 4.1 - Правила сложения и вычитания, двоичных беззнаковых чисел

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

Например: необходимо перевести в двоичную систему счисления, а затем сложить два числа: 7₍₁₀₎ и 5₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти разность двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам вычитания двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам рис.4.3.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти сумму двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна четырем битам рис.4.4.

Десятичное число	Двоичное число
7(10)	0111(2)
5(10)	0101(2)
12(10)	1100(2)

Рисунок 4.2 - Пример вычисления суммы двух чисел: 7₍₁₀₎ и 5₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

Десятичное число	Двоичное число
9(10)	1001(2)
7(10)	0111(2)
2(10)	0010(2)

Рисунок 4.3 - Пример вычисления разности двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам вычитания двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

Десятичное число	Двоичное число
9(10)	1001(2)
7(10)	0111(2)
16(10)	1	0000(2)

Рисунок 4.4 - Пример вычисления суммы двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при четырехразрядной сетке операндов

В примере, представленном на рис.4.4 видно, что (1) вышла за пределы разрядной сетки операнда.

При обработке полученной суммы она не учитывается и следовательно сумма получилась равной (0), а не (16), что является не верным результатом.

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

Например: необходимо перевести в двоичную систему счисления, а затем найти сумму двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ). Длина разрядной сетки операндов равна восьми битам рис.4.5:

Десятичное число	Двоичное число
9(10)	00001001(2)
7(10)	00000111(2)
16(10)	00010000(2)

Рисунок 4.5 - Пример вычисления суммы двух чисел: 9₍₁₀₎ и 7₍₁₀₎ записанных в десятичной системе счисления ( по правилам сложения двоичных беззнаковых чисел ), при восьмиразрядной сетке операндов

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

Так, для фиксирования ситуации выхода за разрядную сетку результата, как в данном примере, предназначен флаг переноса (FC). Он располагается в бит - (0) регистра флагов eflags. Именно установкой этого флага фиксируется факт переноса (1) из старшего разряда операнда за пределы разрядной сетки.

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

Подтема № 2- Операция сложения и вычитания двоичных знаковых чисел в компьютерных системах

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

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

Для этого рассмотрим отдельно формирование числовой и знаковой частей суммы.

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

В этом случае граничное число (C) станет равным весу знакового разряда, который становится отсутствующим.

Представим операцию сложения в общем виде:

. (4.1)

где Z - сумма;

X - первое слагаемое;

Y - второе слагаемое.

В зависимости от знаков слагаемых возможны следующие варианты:

1. , тогда:

.

Например: рассмотрим два случая а) и б).

Случай а): необходимо вычислить сумму двух чисел записанных в десятичной системе счисления (5+2=7), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита. Формат суммы представлен на рис. 4.6, а вычисление суммы и значения флагов на рис.4.7.

0,	1	1	1
D3	D2	D1	D0

Рисунок 4.6 - Формат суммы

Случай а)
Десятичное число	Двоичное число	Значения флагов
5(10)	0,101(2)	FC=0
2(10)	0,010(2)	FS=0
7(10)	0,111(2)	FZ=0
		FO=0

Рисунок 4.7 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет.

Случай б): необходимо сложить два числа записанных в десятичной системе счисления (7+7=14), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.8, а вычисление суммы и значения флагов на рис.4.9.

1,	1	1	0
D3	D2	D1	D0

Рисунок 4.8 - Формат суммы

Случай б)
Десятичное число	Двоичное число	Значения флагов
7(10)	0,111(2)	FC=1
7(10)	0,111(2)	FS=1
14(10)	1,110(2)	FZ=0
		FO=1

Рисунок 4.9 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=1, потому, что есть перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1, а это не правильно так как оба слагаемых положительные числа, значит и сумма должна быть положительной, а в данном случае сумма получается отрицательной так как знаковый бит равен (1).

- FZ=0, потому, что сумма не равняется (0).

- FO=1, потому, что результат не правильный и переполнение разрядной сетки есть.

2. и , тогда:

.

Например: необходимо сложить два числа записанных в десятичной системе счисления (5+(-2)=3), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.10, а вычисление суммы и значения флагов на рис.4.11.

1	0,	0	1	1
	D3	D2	D1	D0

Рисунок 4.10 - Формат суммы

Десятичное число	Двоичное число	Значения флагов
5(10)	0,101(2)	FC=0
(-2)(10)	1,110(2)	FS=0
(3)(10)	10,011(2)	FZ=0
		FO=0

Рисунок 4.11 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что есть перехода (1) из разряда D2 в знаковый разряд D3 и есть перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Единица, которая вышла за пределы разрядной сетки не учитывается.

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

. так как

.

Например: необходимо сложить два числа записанных в десятичной системе счисления (2+(-5)=(-3)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.12, , а вычисление суммы и значения флагов на рис.4.13.

1	0,	0	1	1
	D3	D2	D1	D0

Рисунок 4.12 - Формат суммы

Десятичное число	Двоичное число	Значения флагов
2(10)	0,010(2)	FC=0
(-5)(10)	1,011(2)	FS=1
(-3)(10)	1,101(2)	FZ=0
		FO=0

Рисунок 4.13 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Число 1,101 и есть (-3). Для того, чтобы перейти к прямому коду необходимо все биты проинвертировать, а затем к младшему биту прибавить (1), рис.4.14:

1,101(2)	(-3)
0,010(2)	инверсия
1(2)	+1
0,011(2)	(+3)

Рисунок 4.14 - Пример перехода от дополнительного кода числа к прямому коду

4., тогда:

.

Например: рассмотрим два случая а) и б).

Случай а): необходимо сложить два числа записанных в десятичной системе счисления ((-5)+(-2)=(-7)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита. Формат суммы представлен на рис. 4.15, а вычисление суммы и значения флагов на рис.4.16.

1	1,	0	0	1
	D3	D2	D1	D0

Рисунок 4.15 - Формат суммы

Случай а)
Десятичное число	Двоичное число	Значения флагов
(-5)(10)	1,011(2)	FC=0
(-2)(10)	1,110(2)	FS=1
(-7)(10)	11,001(2)	FZ=0
		FO=0

Рисунок 4.16 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=0, потому, что есть переход (1) из разряда D2 в знаковый разряд D3 и есть перехода из знакового разряда D3 за пределы разрядной сетки.

- FS=1, потому, что значение знакового бита D3=1.

- FZ=0, потому, что сумма не равняется (0).

- FO=0, потому, что результат правильный и переполнение разрядной сетки нет. Единица, которая вышла за пределы разрядной сетки не учитывается.

Число 1,001 и есть (-7). Для того, чтобы перейти к прямому коду необходимо все биты проинвертировать, а затем к младшему биту прибавить (1), рис.4.17. Случай б): необходимо сложить два числа записанных в десятичной системе счисления ((-7)+(-7)=(-14)), для этого необходимо оба числа перевести в двоичную систему счисления, а затем представить в дополнительном коде, для удобства возьмем длину разрядной сетки четыре бита.

Формат суммы представлен на рис. 4.18, а вычисление суммы и значения флагов на рис.4.19.

1,001(2)	(-7)
0,110(2)	инверсия
1(2)	+1
0,111(2)	(+7)

Рисунок 4.17 - Пример перехода от дополнительного кода числа к прямому коду

1	0,	0	1	0
	D3	D2	D1	D0

Рисунок 4.18 - Формат суммы

	Случай б)
Десятичное число	Двоичное число	Значения флагов
(-7)(10)	1,001(2)	FC=1
(-7)(10)	1,001(2)	FS=0
(-14)(10)	10,010(2)	FZ=0
		FO=1

Рисунок 4.19 - Пример вычисления суммы двух чисел и значение флагов после получения результата

Значение флагов:

- FC=1, потому, что нет перехода (1) из разряда D2 в знаковый разряд D3 и есть переход из знакового разряда D3 за пределы разрядной сетки.

- FS=0, потому, что значение знакового бита D3=0, а это не правильно так как оба слагаемых отрицательные числа, значит и сумма должна быть отрицательные, а в данном случае сумма получается положительной так как знаковый бит равен (0).

- FZ=0, потому, что сумма не равняется (0).

- FO=1, потому, что результат не правильный и переполнение разрядной сетки есть. Единица, которая вышла за пределы разрядной сетки не учитывается.

Из вышесказанного на примере (4^х- разрядной) сетки можно сделать следующие выводы:

- переполнение разрядной сетки возможно, когда оба операнда имеют одинаковые знаки;

- есть переход (1) из разряда D2 в знаковый разряд D3 и нет перехода из знакового разряда D3 за пределы разрядной сетки.

- нет перехода (1) из разряда D2 в знаковый разряд D3 и есть переход из знакового разряда D3 за пределы разрядной сетки.

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

4.3 Операции сдвига в компьютерных системах

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

Существует несколько вариантов сдвига:

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

2. Арифметический сдвиг. Не влияет на положение знака операнда.

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

3. Модифицированный сдвиг. Арифметический сдвиг операндов, представленных обратным или дополнительным кодом:

- обратный код - при правом и левом сдвигах в освобождающиеся разряды регистра записываются цифры знакового разряда;

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

4. Циклический сдвиг. Операнд перемещается в регистре как в замкнутом контуре, поступая с выхода последнего разряда на вход первого.

Схемы выполнения операций сдвига приведены на рис. 4.20.

Рисунок 4.20 - Схемы выполнения операций сдвига

Лекция № 9 (90-минут)

Тема: Умножение двоичных беззнаковых чисел в компьютерных системах

Пусть сомножителями X и Y являются s-битные целые числа без знака:

где: (Х) - множимое, (Y) - множитель, (Z) произведение. Тогда:

Z = X ∙ Y. (4.2)

где: ;

.

Представим множитель Y в развернутой форме:

. (4.3)

Тогда:

(4.4)

Произведение множимого на один бит множителя называется частичным произведением. Полное произведение числа представляет собой сумму (s) частичных произведений (ЧП). При умножении вручную существует два способа: - способ № 1, начиная с младшей цифры множителя и сдвиг частичных произведений влево; - способ № 2, начиная со старшей цифры множителя и сдвиг частичных произведений вправо.

Например. Необходимо перемножить два беззнаковых числа (7∙3=21).

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

Правило умножения вручную заключается в следующем: - шаг 1.

Анализируется младший (правый) бит множителя, если младшая цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого, если младшая цифра множителя равна (0), то в сумму частичных произведений записываются все (0); - шаг 2. Анализируется следующий после младшего бит множителя, если цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого сдвинутые на один разряд влево, если цифра множителя равна (0), то в сумму частичных произведений записываются все (0), сдвинутые на один разряд влево; - шаг 3. Шаги (1) и (2) повторяются до тех пор, пока не будут проанализированы все цифры множителя; - шаг4. Производится сложение всех сумм частичных произведений. Полученная сумма и будет равна произведению множимого на множитель. Итак: необходимо перемножить два беззнаковых числа (7∙3=21) где: (7) - множимое; (3) - множитель; (21) - произведение. Необходимо вычислить сумму частичных произведений - (ЧП), а следовательно и произведение, рис.4.21 и рис.4.22.

Способ №1

Десятичное число	Двоичное число	Комментарии
7(10)	0111(2)	множимое
3(10)	0011(2)	множитель
	4321	номера цифр множителя
	0111	1ое – ЧП
	0111	2ое – ЧП
	0000	3ое – ЧП
0000		4ое – ЧП
21(10) 0010101(2)		сумма ЧП - произведение

Рисунок 4.21 - Умножение, начиная с младшей цифры множителя и сдвиг частичных произведений влево

Способ №2

Десятичное число	Двоичное число	Комментарии
7(10)	0111(2)	множимое
3(10)	0011(2)	множитель
	1234	номера цифр множителя
	0000	1ое – ЧП
	0000	2ое – ЧП
	0111	3ое – ЧП
0111		4ое – ЧП
21(10) 0010101(2)		сумма ЧП - произведение

Рисунок 4.22 - Умножение, начиная со старшей цифры множителя и сдвиг частичных произведений вправо.

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

Длина произведения s-битных сомножителей равна 2s бит:

(4.5)

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

(4.6)

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

- анализируется очередной бит () множителя;

- в зависимости от его значения происходит (y_i=1) или нет (y_i=0) прибавление множимого к предыдущей сумме частичных произведений;

- производится изменение взаимного положения множимого (X) и суммы частичных произведений с учетом веса (2ⁱ).

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

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

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

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

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

Рисунок 4.23 - Схемы выполнения операции умножения двоичных беззнаковых чисел

Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.

Схема 1

. (4.7)

. (4.8)

Время выполнения операции умножения:

(4.9)

где (t_с) - время, затрачиваемое на выполнение операции сдвига на один разряд;

(t₊) - время, затрачиваемое на выполнение операции сложения.

Схема 2

. (4.10)

(4.11)

. (4.12)

Схема 3

. (4.13)

. (4.14)

. (4.15)

Схема 4

. (4.16)

. (4.17)

. (4.18)

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

Алгоритм №1.  Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ЧП вправо.

1. Исходное значение суммы (ЧП) принимается равным (0), счетчику тактов - (Сч.Т) присваивается значение, равное числу разрядов множителя.

2. Анализируется младшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по старшим разрядам; если (0) - прибавление не производится.

3. Производится сдвиг множителя и суммы ЧП вправо на (1) разряд. Содержимое (Сч.Т) уменьшается на (1).

4. Анализируется содержимое (Сч.Т). Если оно не равно (0), то переход к (п.2), иначе - (п.5).

5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая - на месте суммы (ЧП). Например: необходимо перемножить два беззнаковых числа (7∙3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т.е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.1.

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

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
0	1	1	1	0	0	1	1	00000000	4
								0111		множимое
								01110000		1Я СЧП
					0	0	1	00111000	3	1ЫЙсдвиг СЧП
								0111		множимое
								10101000		2Я СЧП
						0	0	01010100	2	2 ОЙсдвиг СЧП
							0	00101010	1	3 ИЙсдвиг СЧП
								00010101	0	4ЫЙсдвиг СЧП
								СТОП

Алгоритм №2. Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ЧП влево.

1. Исходное значение суммы (ЧП) принимается равным (0), (Сч.Т) присваивается значение, равное числу разрядов множителя.

2. Производится сдвиг суммы (ЧП) влево на (1) разряд.

3.Анализируется старшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по младшим разрядам; если (0) - прибавление не производится.

4.Производится сдвиг множителя влево на (1) разряд. Содержимое (Сч.Т) уменьшается на (1).

5.Анализируется содержимое (Сч.Т). Если оно не равно (0), то переход к (п.2), иначе - (п.6).

6.Умножение закончено, произведения находится на месте суммы (ЧП), которая имеет удвоенную разрядность. Например: необходимо перемножить два беззнаковых числа (7∙3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т.е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.1.

Таблица 4.2 - Алгоритм умножения со сдвигом влево двоичных беззнаковых чисел

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
0	1	1	1	0	0	1	1	00000000	4
								00000000		1ЫЙсдвиг СЧП
				0	1	1		00000000	3	2 ОЙсдвиг СЧП
								00000000		3 ИЙсдвиг СЧП
				1	1			00000000	2	4ЫЙсдвиг СЧП
								00000000		5ЫЙсдвиг СЧП
								0111		множимое
								00000111		1Я СЧП
				1					1
								00001110		6ОЙ сдвиг СЧП
								0111		множимое
								00010101	0	2Я СЧП
								СТОП

Лекция № 10 (90-минут)

Тема: Деление двоичных беззнаковых чисел в компьютерных системах

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

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

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

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

Обозначим X - делимое, Y - делитель, а Z - частное. Тогда:

. (4.19)

Пусть (X), (Y) и (Z) являются беззнаковыми числами.

Операция деления характеризуется также дополнительным результатом (R) - остатком.

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

- первый тип это когда делимое, делитель и частное имеют одну и ту же длину (s);

- второй тип это когда делимое имеет длину (2s) - удвоенную по сравнению с делителем и частным. Рассмотрим случай 1.

, . (4.20)

, . (4.21)

, . (4.22)

, . (4.23)

. (4.24)

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

. (4.25)

или

. (4.26)

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

Переполнение исключено, если делимое и делитель имеют одинаковую длину. Как особый случай переполнения рассматривают попытку деления на нуль.

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

Цифра () частного определяется следующим образом: если текущий остаток () больше или равен делителю, цифра частного равна (1), если меньше, то цифра частного равна (0).

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

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

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

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

В зависимости от способа обработки отрицательного частичного остатка, различают два алгоритма деления:

- алгоритм №1, с восстановлением остатка;

- алгоритм №2 без восстановления остатка.

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

Данный шаг на этом заканчивается.

Рисунок 4.9 - Схемы деления двоичных беззнаковых чисел

Если текущий остаток отрицателен, то в очередную цифру частного записывается (0), а к остатку прибавляется делитель для восстановления предыдущего, сдвинутого влево остатка, который становится «предыдущим» для следующего шага.

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

Алгоритм №1. Деление целых двоичных беззнаковых чисел методом с восстановлением остатка.

1. Исходное значение частного (Z) полагается равным (0). (Сч.Т) присваивается значение (s). Исходное значение частичного остатка (R₀) полагается равным (s) старшим разрядам делимого.

2. Выполняется пробное вычитание делителя (Y) из исходного значения частичного остатка – (ЧО). Положительная разность указывает на то, что частное превысит (s-разрядную сетку), и будет выполнено прерывание. Если же результат вычитания отрицательный, то деление можно выполнять.

3. Восстанавливается исходное значение (ЧО) прибавлением делителя к полученному отрицательному остатку.

4. (ЧО) удваивается путем сдвига на один разряд влево.

5. Из (ЧО) вычитается делитель и анализируется знак результата вычитания: если остаток положительный, то очередная цифра частного равна (1), иначе – (0).

6. Частное сдвигается влево с занесением очередной полученной цифры частного в освободившийся младший разряд. (Сч.Т) уменьшается на (1).

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

8. (Пп. 4-7) последовательно выполняются до получения всех цифр частного, пока (Сч.Т) не станет равным (0).

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

Недостатки:

- нерегулярность выполнения операций, что усложняет устройство управления (для получения одной цифры частного необходимо выполнять либо одно вычитание и сдвиг, либо одно вычитание, одно сложение и сдвиг);

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

T=(s+l)(l,5t₊+t_c)–t_c.

Например: необходимо разделить два беззнаковых числа (21:7=3).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = 21 – делимое;

Y = 7 – делитель;

Z = 3 – частное.

Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т.е длина разрядной сетки делимого в два раза больше делителя и частного.

Алгоритм деления приведен в табл. 4.3.

Таблица 4.3 - Алгоритм деление целых двоичных беззнаковых чисел методом с восстановлением остатка.

	Регистр (В) делимое X											Регистр (С) делитель Y				Регистр (А) частное Z				Счетчик тактов (Сч.Т)
	0	0	0	1	0	1			0	1		0	1	1	1	0	0	1	1	4
	1	0	0	1
	1	0	1	0	<0
	0	1	1	1
1	0	0	0	1
	0	0	1	0	1		0	1
	1	0	0	1
	1	0	1	1	<0															3
	0	1	1	1
1	0	0	1	0
	0	1	0	1	0		1
	1	0	0	1
	1	1	1	0	<0															2
	0	1	1	1
1	0	1	0	1
	1	0	1	0	1
	1	0	0	1
1	0	0	1	1	>0															1
	0	1	1	1
	1	0	0	1
1	0	0	0	0	>0															0
												СТОП

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

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

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

- () - предыдущий остаток;

- () - текущий;

- () - последующий.

Пусть:

. (4.27)

При этом, в соответствии с правилом деления, должны выполняться три действия:

- восстановление предыдущего (сдвинутого влево) остатка:

. (4.28)

- сдвиг восстановленного остатка влево на один разряд:

. (4.29)

- вычитание модуля делителя из полученной кодовой комбинации:

. (4.30)

Таким образом, требуется перейти от текущего остатка:

. (4.31)

к последующему виду (4.31), избавившись от операции восстановления.

Если первым действием является сдвиг отрицательного остатка () влево, то:

. (4.32)

Правая часть (4.32) отличается от требуемого вида величиной |Y|.

Поэтому вторым действием будет корректировка (4.33):

. (4.33)

Сформулируем общее правило.

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

Алгоритм №2. Деления целых двоичных чисел методом без восстановления остатка

1-2. Аналогично п.п. 1, 2 предыдущего.

3. Аналогично п. 4.

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

5. Частное сдвигается; в младший разряд заносится очередная цифра частного (1 — при положительном остатке, 0 — при отрицательном);

6. П.п. 3-5 последовательно выполняются для получения всех цифр частного, пока (Сч.Т) не станет равен (0).

7. Аналогично последнему пункту предыдущего алгоритма.

Реализация данного алгоритма не требует никаких дополнительных аппаратурных затрат. .

Например: необходимо разделить два беззнаковых числа (21:7=3).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = 21 – делимое;

Y = 7 – делитель;

Z = 3 – частное.

Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т.е длина разрядной сетки делимого в два раза больше делителя и частного.

Алгоритм деления приведен в табл. 4.4.

Таблица 4.4 - Алгоритм деление целых двоичных беззнаковых чисел методом без восстановлением остатка.

	Регистр (В) делимое X											Регистр (С) делитель Y				Регистр (А) частное Z				Счетчик тактов (Сч.Т)
	0	0	0	1	0	1			0	1		0	1	1	1	0	0	1	1	4
	1	0	0	1
	1	0	1	0	<0
	0	1	0	0	1		0	1
	0	1	1	1
	1	0	1	1	<0															3
	0	1	1	1	0		1
	0	1	1	1
	1	1	1	0	<0															2
	1	1	0	0	1
	0	1	1	1
1	0	0	1	1	>0															1
	0	1	1	1
	1	0	0	1
1	0	0	0	0	>0															0
												СТОП

Лекция № 11 (90-минут)

Тема: Умножение двоичных знаковых чисел в компьютерных системах

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

. (4.34)

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

. (4.35)

Определение знака произведения показано в табл. 4.5. Где (0) - обозначает (+), а (1) – обозначает (-).

Таблица 4.5 – Определение знака произведения

00=0

01=1

10=1

11=0

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

Такой прием не является эффективным. Поэтому на практике чаще всего используют специальные алгоритмы умножения чисел в дополнительных кодах. Алгоритмы корректного умножения операндов в ДК можно разделить на две группы:

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

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

Теорема: произведение дополнительных кодов сомножителей равно дополнительному коду результата только в случае положительных сомножителей. Если хотя бы один сомножитель отрицателен, то произведение чисел на сумматоре дополнительных кодов получается прибавлением поправки () к произведению дополнительных кодов сомножителей. Рассмотрим арифметическое обоснование алгоритмовпервой группы при различных вариантах комбинаций знаков операндов. С этой целью у операндов отбрасывается знаковая цифра и выполняется умножение полученных псевдомодулей по одному из известных алгоритмов. Результат такого умножения назовем псевдопроизведением (). Обозначим вес знакового разряда сомножителей (). Тогда, в соответствии с рассмотренным ранее правилом формирования дополнительного кода, отрицательные сомножители будут представлены в ДК следующим образом:

. (4.36)

При удалении знакового разряда получаем псевдомодули:

. (4.37)

Всего возможны четыре варианта сочетания знаков сомножителей:

Случай №1. .

. (4.38)

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

Случай №2. .

(4.39)

Результат значительно отличается от модуля кода истинного произведения:

;

. (4.40)

Сомножитель представляет собой (s-1)-разрядный псевдомодуль числа (-X), представленного в ДК. Сомножитель эквивалентен сдвигуна (s-1) разряд влево. Сравнение (Z) и (Z’) показывает, что результат умножения должен быть скорректирован посредством сложения (Z’) с поправкой ().

Случай №3. .

. (4.41)

. (4.42)

Случай №4. .

. (4.43)

На практике используют упрощенную поправку , поскольку нескорректированный операнд (C) проявит себя в виде (1) в знаковом разряде. Это не имеет значения, поскольку знак (Z) был сформирован отдельно на начальном этапе. Подход к формированию алгоритма умножения состоит в следующем.

1. Получим псевдомодули операндов, отбросив старшие (знаковые) цифры: (0) - в положительном числе, (1) - в отрицательном.

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

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

4. Выполняя их умножение по правилам, рассмотренным выше, получаем уже не модуль (Z’), а само псевдопроизведение с некоторыми псевдознаковыми цифрами в двух самых старших разрядах. Указанные цифры относятся к знаковым по расположению, но не имеют смысла таковых.

5. Возникает задача найти истинное значение знаковой цифры числа (Z).

Рассмотрим арифметическое обоснование алгоритмов второй группы при различных вариантах комбинаций знаков операндов, т.е. умножение чисел в ДК с обработкой знаковых разрядов вместе с числовыми в зависимости от сочетания знаков сомножителей. При этом используем предпосылки, приведенные в предыдущем доказательстве. Считаем, что вес знакового разряда равен (A). Тогда вес разряда, следующего за знаковым: .

Случай №1. .

Перемножая машинные представления сомножителей в ДК, получим:

. (4.44)

Случай №2. .

Учитывая, что разрядность произведения (и псевдопроизведения) составит (2s) - бит, вес разряда, следующего за знаковым разрядом произведения:

(4.45)

Тогда:

(4.46)

Перемножая ДК сомножителей, получим:

. (4.47)

Истинное значение произведения получается:

. (4.48)

. (4.49)

Случай №3. .

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

. (4.50)

Случай №4. .

. (4.51)

На практике используют упрощенную поправку:

. (4.52)

При умножении в ДК по любому из вариантов данной группы в процессе прибавления () к (Z’) важно соблюдать соответствие весов разрядов псевдопроизведения и корректирующей поправки (с учетом наличия псевдознака). Старший разряд корректирующей поправки сформирует знаковую цифру. Из рассмотренных ранее вариантов умножения в соответствии с алгоритмами обеих групп, следует, что для коррекции результата умножения ДК операндов необходимо в каждом случае по комбинации знаков определять величину коррекции, а затем выполнять 1-2 шага суммирования. Однако этого можно избежать, если коррекцию совмещать с процессом суммирования частичных произведений. Рассмотренные алгоритмы являются базовыми и реализуют непосредственный способ введения поправок. Более широкое применениена практике получили алгоритмы с косвенным способом введения поправок.

Случай №1. .

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

Случай №2. .

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

Случай №3 .

Если сдвиг суммы ЧП вправо на (i) разрядов выполнять по правилам сдвига модифицированного ДК, а затем выполнять суммирование ЧП по правилам суммирования модифицированных ДК (с потерей переноса из знакового разряда), то будет получено правильное произведение исходных чисел в ДК, т.е. (). Т.о., коррекция не требуется.

Случай №4 .

Коррекция результата выполняется объединением двух предыдущих вариантов, т.е. при умножении на знаковый разряд множителя выполняют вычитание, а суммирование и сдвиг частичных произведений производят с использованием МДК. Таким образом при положительном множителе умножение в ДК можно выполнять по алгоритмам умножения в ПК, если только суммировать ЧП и сдвиг выполнять по правилам сложения и сдвига модифицированного ДК (перенос из ЗР будет игнорироваться). Существует еще один способ умножения знаковых чисел в ДК. Он заключается в том, что отрицательный множитель необходимо преобразовать в положительный. Это выполняется умножением на (-1) множимого и множителя. В итоге, в соответствии с выше приведенной теоремой, умножение выполняется по обычным правилам, а результат не нуждается в корректировке. Общий алгоритм умножения целых двоичных знаковых чисел, представленных в ДК заключается в следующем:

1. Исходное значение суммы ЧП принимается равным (0), (Сч.Т) присваивается значение, равное числу разрядов множителя.

2. Анализируется младшая разрядная цифра множителя. Если она равна (1), то к сумме ЧП прибавляется множимое; если (0) - прибавление не производится. Множимое при этом совмещается с суммой ЧП по старшим разрядам и представлено в исходном коде.

3. Производится арифметический сдвиг суммы ЧП вправо на (1) разряд с учетом флагов переноса (FC) и переполнения (FO). Содержимое (Сч.Т) уменьшается на (1).

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

5. Если множитель — положительное число, то полученный результат является истинным произведением (Z). Если множитель - отрицательное число, то к полученному результату (Z’) прибавляется множимое с обратным знаком (дополнение), совмещенное по старшим разрядам. Полученная сумма представляет собой истинное произведение (Z). . Рассмотрим примеры вышеописанного алгоритма.

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

((+7)∙(+3) = (+21)). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = (+7) – множимое, Y = (+3) – множитель, Z = (+21) – произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т.е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.6.

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

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
0	1	1	1	0	0	1	1	00000000	4
								0111		множимое
								01110000		1Я СЧП
					0	0	1	00111000	3	1ЫЙсдвиг СЧП
								0111		множимое
								10101000		2Я СЧП
						0	0	01010100	2	2 ОЙсдвиг СЧП
							0	00101010	1	3 ИЙсдвиг СЧП
								00010101	0	4ЫЙсдвиг СЧП и получили число – (+21)
								СТОП

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

((+7)∙(-3) = (-21)).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = (+7) – множимое;

Y = (-3) – множитель;

Z = (-21) – произведение.

Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением.

То есть длина разрядной сетки произведения в два раза больше множимого и множителя.

Алгоритм умножения приведен в табл. 4.7.

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

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
0	1	1	1	1	1	0	1	00000000	4
								0111		множимое
								01110000		1Я СЧП
					1	1	0	00111000	3	1ЫЙсдвиг СЧП
						1	1	00011100	2	2 ОЙсдвиг СЧП
								0111		множимое
								10001100		2Я СЧП
							1	01000110	1	3 ИЙсдвиг СЧП
								0111		множимое
								10110110		3Я СЧП
								01011011	0	4ЫЙсдвиг СЧП и (получили (Z’))
								1001		кор-ция на (ХД)
								11101011		число (-21)
								СТОП

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

((-7)∙(+3) = (-21)).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = (-7) – множимое;

Y = (+3) – множитель;

Z = (-21) – произведение.

Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением.

То есть длина разрядной сетки произведения в два раза больше множимого и множителя.

Алгоритм умножения приведен в табл. 4.8.

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

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
1	0	0	1	0	0	1	1	00000000	4
								1001		множимое
								10010000		1Я СЧП
					0	0	1	01001000	3	1ЫЙсдвиг СЧП
								1001		множимое
								11011000		2Я СЧП
						0	0	01101100	2	2 ОЙсдвиг СЧП
							0	00110110	1	3 ИЙсдвиг СЧП
								00011011	0	4ЫЙсдвиг СЧП и (получили (Z’))
								1101		кор-ция на (YД)
								11101011		число (-21)
								СТОП

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

((-7)∙(-3) = (+21)).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = (-7) – множимое;

Y = (-3) – множитель;

Z = (+21) – произведение.

Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением.

То есть длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.9.

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

Регистр (В) множимое X				Регистр (С) множитель Y				Регистр (А) произведение Z	Счетчик тактов (Сч.Т)	Комментарии
1	0	0	1	1	1	0	1	00000000	4
								1001		множимое
								10010000		1Я СЧП
					1	1	0	01001000	3	1ЫЙсдвиг СЧП
						1	1	00100100		2 ОЙсдвиг СЧП
								1001		множимое
								10110100		2Я СЧП
							1	01011010	2	3 ИЙсдвиг СЧП
								1001		множимое
								11101010		3Я СЧП
								01110101	0	4ЫЙсдвиг СЧП и (получили (Z’))
								0111		кор-ция на (XД)
								11100101
								0011		кор-ция на (YД)
				1				00010101		число (+21)
								СТОП

Лекция № 12 (90-минут)

Тема: Деление двоичных знаковых чисел в компьютерных системах

Так как данные в памяти компьютера хранятся в ДК, операцию деления целесообразно выполнять в ДК.

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

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

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

Пусть:

- разрядность (2s), - .

- разрядность (s), - .

- разрядность (s), - .

- разрядность(s), - .

Для проверки на корректность операции деления используется условие:

. Таким образом, при пробном вычитании делитель должен быть сдвинут на (s-1) разряд влево. Однако чтобы обеспечить регулярность процесса деления, делитель сдвигается влево на s разрядов, а перед пробным вычитанием делимое сдвигается на один разряд влево.

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

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

Очередная цифра определяется на основе анализа знаков частичного остатка и делителя. Если знак полученного остатка совпадает со знаком делителя, то цифра частного равна (1), если нет – (0). При этом частное формируется в прямом или обратном коде (в зависимости от соотношения знаков делимого и делителя). На этапе пробного вычитания автоматически формируется старшая цифра частного, которая представляет его знак. Если знак полученного частичного остатка совпадает со знаком делителя, участвующего в операции пробного вычитания, деление является корректным. В противном случае имеет место переполнение разрядной сетки компьютерной системы.

Алгоритм деления целых двоичных знаковых чисел заключается в следующем:

1. Частному присваивается значение (0); (Сч.Т) – (s). Исходное значение частичного остатка равно (s) старшим разрядам делимого.

2. Частичный остаток удваивается сдвигом влево на (1) разряд, с занесением в младший разряд очередной цифры делимого.

3. Если частичный остаток и делитель разного знака, то они складываются, если же одного знака, то из частичного остатка вычитается делитель.

4. Частное сдвигается влево на (1) разряд. В освобождающийся младший разряд заносится очередная цифра частного: (1) - если знак делителя и остатка совпадают, (0) - в противном случае (Сч.Т) уменьшается на (1).

5. Пункты 2-4 повторяются до тех пор, пока (Сч.Т) не станет равным (0).

6. Частное и остаток сформированы в обратном коде. Если знак окончательного остатка не совпадает со знаком делимого, то выполняется его восстановление. Для получения ДК результата выполняется его коррекция в зависимости от соотношения знаков делимого и делителя.

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

Случай №1 X > 0; Y > 0. Деление в этом случае ничем не отличается от деления положительных операндов в прямом коде. Коррекция не требуется;

Случай №2 X > 0; Y < 0. Этот случай легко сводится к обычному делению в прямом коде, если считать, что в наличии имеется (-Y) и (+Y). Однако для формирования правильного знака частного и обратного кода отрицательного результата необходимо псевдознаковую цифру и цифры частного получать равными цифрам знаковых разрядов соответствующих остатков. Переполнение разрядной сетки здесь фиксируется по (). В конце деления для образования дополнительного кода и округления частного следует прибавить единицу к младшему разряду: (Z=Z’+1);

Случай №3 X < 0; Y > 0. Из отрицательного делимого должен вычитаться положительный делитель, в отличие от деления без восстановления остатка в прямом коде, когда на первом шаге (Х>0, Y<0). Поэтому псевдознаковая цифра частного (), полученная по знаку нулевого остатка в соответствии с алгоритмом деления без восстановления остатка, здесь указывает на переполнение разрядной сетки. Если же переполнения разрядной сетки нет, эта цифра является правильной знаковой цифрой частного (то есть,).

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

В результате будет записан обратный код отрицательного частного.

Для округления и получения дополнительного кода результата необходимо добавить единицу в младший разряд, если полученный остаток не равен нулю: (Z=Z’+1).

Случай№4 X < 0; Y < 0.

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

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

В случае, когда полученный остаток равен нулю, к частному следует прибавить единицу (Z=Z’+1).

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

Поэтому надо оперировать двумя знаковыми разрядами.

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

Знак остатка от деления должен совпадать со знаком делимого.

Например: необходимо разделить два беззнаковых числа (21:7=3).

Для удобства возьмем длину разрядной сетки равную четырем битам, а именно:

Х = 21 – делимое;

Y = 7 – делитель;

Z = 3 – частное.

Если (Z) и (Y) равняется четырем битам, то как было отмечено выше (X) должно быть восьмиразрядным значением, т.е длина разрядной сетки делимого в два раза больше делителя и частного.

Алгоритм деления приведен в табл. 4.10.

Таблица 4.10 - Алгоритм деление целых двоичных знаковых чисел методом без восстановлением остатка.

	Регистр (В) делимое X											Регистр (С) делитель Y				Регистр (А) частное Z				Счетчик тактов (Сч.Т)
	0	0	0	1	0	1			0	1		0	1	1	1	0	0	1	1	4
	1	0	0	1
	1	0	1	0	<0
	0	1	0	0	1		0	1
	0	1	1	1
	1	0	1	1	<0															3
	0	1	1	1	0		1
	0	1	1	1
	1	1	1	0	<0															2
	1	1	0	0	1
	0	1	1	1
1	0	0	1	1	>0															1
	0	1	1	1
	1	0	0	1
1	0	0	0	0	>0															0
												СТОП

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

1. Перевести в двоичную систему счисления и вычислить выражение:

((19₍₁₀₎ – 15₍₁₀₎) * (18₍₁₀₎ – 11₍₁₀₎))/7₍₁₀₎.

2. Перевести в двоичную систему счисления и вычислить выражение:

((10₍₁₀₎ – 15₍₁₀₎) * (18₍₁₀₎ – 12₍₁₀₎))/6₍₁₀₎.

3. Перевести в двоичную систему счисления и вычислить выражение:

((17₍₁₀₎ – 12₍₁₀₎) * (23₍₁₀₎ – 17₍₁₀₎))/(-6₍₁₀₎).

4. Перевести в двоичную систему счисления и вычислить выражение:

((25₍₁₀₎ – 21₍₁₀₎) * (10₍₁₀₎ – 17₍₁₀₎))/(-7₍₁₀₎).

5. Перевести в двоичную систему счисления и вычислить выражение:

((14₍₁₀₎ – 21₍₁₀₎) * (10₍₁₀₎ – 16₍₁₀₎))/5₍₁₀₎.

6. Перевести в двоичную систему счисления и вычислить выражение:

((15₍₁₀₎ – 11₍₁₀₎) * (12₍₁₀₎ – 17₍₁₀₎))/5₍₁₀₎.

Лекция № 13 (90-минут)

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

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

. (5.1)

где M — мантисса;

P — порядок.

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

. (5.2)

где M — мантисса.

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

Порядок определяет фактическое положение запятой вместо положения, которое она занимает в изображении мантиссы, и может быть положительным или отрицательным, но обязательно целым числом. Понятие «ПЗ» можно рассматривать как перемещение запятой в изображении числа влево, если Р<0, или вправо, если P>0. Для обозначения чисел с плавающей точкой используют форму вида:

. (5.3)

где М – мантисса числа;

Е – разделитель мантиссы и порядка;

Р – порядок числа.

Вместо E могут использоваться другие символы, например, D (double — двойная точность), когда для мантиссы отводится большее количество разрядов. Если для записи порядка используется (Р) разрядов, а для записи мантиссы (М) разрядов, то в форме с плавающей точкой может быть представлено следующее максимальное (по абсолютной величине) число:

(5.4)

В свою очередь, минимальное по абсолютной величине, но не равное нулю, число в форме с плавающей точкой может быть представлено в виде:

(5.5)

При получении последней оценки полагаем, что минимальное значение мантиссы равно (2^-1) из-за условия нормализации. Подобные рассуждения применимы и для определения максимального и минимального отрицательных чисел, поскольку они представляются в компьютерных системах. В компьютерных системах, где используется представление чисел в форме с плавающей точкой, арифметические операции выполняются как над мантиссами операндов, так и над их порядками. При этом часто необходимо выполнять операцию нормализации чисел. Поэтому процессоры с плавающей точкой являются более сложными и менее быстродействующими, чем процессоры с фиксированной точкой (естественно, при сравнимом быстродействии электронных компонентов этих процессоров). Вместе с тем, в компьютерных системах с фиксированной точкой возникают определенные трудности из-за необходимости масштабирования данных. Кроме того, здесь значительно уже диапазон представимых чисел. В этом легко убедиться, сравнивания отношения для различных форм представления числовых данных:

(5.6)

Для чисел с плавающей точкой:

(5.7)

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

Таблица 5.1- Зависимость диапазона представимых чисел от разрядности порядка

P
6
7
8

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

5.2 Форматы двоичных числовых данных с плавающей точкой

Формат данных с плавающей точкой, использовавшийся в компьютерных системах первых поколений, включал четыре поля, а именно: указанные ранее поля для мантиссы и ее знака (длиной (m+1) разряд), а также два дополнительных поля для порядка и его знака (длиной (p+1) разряд).

Рисунок 5.1 — Классический формат данных с плавающей точкой

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

Смещенный порядок (Е_х) представляет собой целое беззнаковое число, равное истинному порядку, увеличенному на некоторое значение смещения.

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

. (5.8)

где — некоторая константа (смещение).

Если Р_х > Р_y, то E_x > E_y. Если (D = 2^p-1), то такой смещенный код называют кодом с положительным нулем. Для перехода от смещенного кода к дополнительному достаточно проинвертировать знаковый бит.

Широко применяются смещенные коды с отрицательным нулем, когда

(D = 2^p-1 - 1). При сложении и вычитании смещенных порядков результирующий порядок также должен быть смещенным.

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

, (5.9)

где Е^’_y - смещенный порядок с инвертированным старшим разрядом.

В этом случае может возникать как положительное, так и отрицательное переполнение. Если во втором слагаемом старший разряд (1) был инвертирован в (0), а при сложении возник перенос (CY=1), то имеет место переполнение порядка. Результат оказывается за пределами представления. Признаком получения отрицательного переполнения (антипереполнение) является отсутствие переноса (CY=0) из старшего разряда суммы при условии, что во втором слагаемом старший разряд из (0) был инвертирован в (1).

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

, (5.10)

где Е^’_y - инверсное значение смещенного порядка с инвертированным старшим разрядом.

5.3 Стандарт IEEE-754

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

Поэтому был разработан международный стандарт IEEE-754, нормам которого должны удовлетворять практически все вновь разрабатываемые компьютерные системы. Указанный стандарт решает следующие задачи:

- упорядочивает форматы чисел с плавающей точкой;

- унифицирует реакции на особые случаи в процессе обработки;

- определяет требования к точности вычислений.

В соответствии со стандартом IEEE-754 определены два базовых и два расширенных формата. Во всех форматах используется смещенный код порядка. Мантисса имеет старший разряд (m₀) с весом (2⁰), относящийся к целой части. Поэтому условие нормализации изменяется:

. (5.11)

Базовый одинарный формат - (БОФ) имеет длину в 32 разряда. Поле порядка в этом формате содержит 8 разрядов, а смещение равно 127.

Максимальный положительный порядок числа здесь равен +127, минимальный отрицательный -128.

Базовый двойной формат - (БДФ) имеет одноразрядное знаковое поле, 11-разрядное поле смещенного порядка и 52-разрядное поле мантиссы.

Смещение здесь равно 1023. Особенность двух указанных форматов заключается в том, что минимальный и максимальный смещенные порядки зарезервированы для представления специальных чисел. Поля мантисс в явном виде не содержат разряда (m₀), так как в памяти должны храниться нормализованные мантиссы чисел, а значит, их старший разряд всегда равен (1). При передаче числа из памяти в процессор этот «неявный» разряд становится «явным», и в операциях участвует 24-разрядная (БОФ) или 56-разрядная (БДФ) мантисса.

Расширенный одинарный формат - (РОФ) не имеет жестко фиксированных параметров, однако для конкретных реализаций он устанавливается, исходя из следующих требований:

- наличие одноразрядного знакового поля;

- наличие явного или скрытого разряда в мантиссе;

- длина мантиссы не менее 31 разряда;

- диапазон значений порядка — -1023... +1024.

Расширенный двойной формат - (РДФ) отличается от одинарного тем, что диапазон порядка составляет -16383...+16384, а поле мантиссы - не менее 63 разрядов. В качестве примера практической реализации форматов стандарта IEEE-754 можно рассмотреть представление числовых данных с плавающей точкой в компьютерных системах. Здесь используются данные трех типов (таблица 5.2):

- вещественные числа одинарной точности (single real), соответствующие БОФ;

- вещественные числа двойной точности (double real), соответствующие БДФ;

- вещественные числа расширенной точности (extended real) или временные вещественные числа, соответствующие РДФ.

Временные вещественные числа имеют в своем представлении явный бит (m₀). В памяти компьютера числа хранятся чаще всего в форматах БОФ или БДФ, а их обработка выполняется в РДФ.

Следует отметить, что целые числа в диапазоне (2^-64….2⁺⁶⁴ ) представляются абсолютно точно в РДФ.

Таблица 5.2 - Зависимость диапазона представимых чисел от базовых форматов

Тип	Длина	Точность	Диапазон (дв.)	Диапазон (дес.)
БОФ	32	24
БДФ	64	53
РДФ	80	64

Если в процессе вычислений результат выходит за пределы представимых чисел, то имеет место особый случай:

- нарушение нормализации;

- если результат превышает |X_max|, то такой случай называют переполнением или переполнением порядка, и вычисления при этом останавливают (прерывание);

- если результат меньше |X_min|, имеет место антипереполнение или исчезновение порядка, что обычно воспринимается как нулевой результат (машинный 0);

- в результате выполнения сложения-вычитания мантисса может оказаться равной (0) при ненулевом порядке. Это ситуация потери значимости (псевдонуль). Результат интерпретируется как машинный (0).

Лекция № 14 (90-минут)

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

Пусть требуется выполнить некоторую арифметическую операцию над операндами X и Y в форме с плавающей точкой:

. (5.12)

. (5.13)

Результатом операции будет число:

. (5.14)

Порядки чисел X и Y представлены p разрядами, а мантиссы – (m-разрядные) правильные дроби, то есть,

, . (5.15)

5.5 Сложение и вычитание чисел в форме с плавающей точкой

Представим операцию сложения в виде:

Z = X + Y. (5.16)

Пусть Р_х > P_y, тогда:

. (5.17)

где .

. (5.18)

где ;.

Операция сложения и вычитания операндов в форме с плавающей точкой включает следующие этапы:

- выравнивание порядков операндов и определение порядка результата;

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

- нормализация результата;

- округление результата.

Выравнивание порядков необходимо для того, чтобы цифры мантисс с определенными весами располагались в соответствующих им разрядах регистров. Выполняется такая операция путем сдвига вправо мантиссы того операнда, порядок которого меньше. (Не выравнивать в сторону меньшего порядка! — теряем значащие цифры). Алгоритм выравнивания порядков сводится к следующему:

- сформировать разность порядков .

- если >0, то сдвинуть на один разряд вправо мантиссу (Y) и вычесть единицу из разности порядков( ); если <0, то сдвинуть на один разряд вправо мантиссу (X) и прибавить единицу к разности порядков ();

- пункт 2 алгоритма повторять до тех пор, пока выполняется неравенство ≠0; при =0 выравнивание порядков считают законченным.

Так как порядки операндов могут иметь разные знаки, то для представления их разности () может понадобиться (p+1) разряд. Абсолютная величина () может превышать число разрядов (m), отводимых для представления мантисс. В этом случае все разряды сдвигаемой вправо мантиссы выходят за пределы разрядной сетки и далее, при сложении и вычитании мантисс, абсолютная величина мантиссы, которая оставалась неподвижной, не меняется. Следовательно, при выполнении условия ||>m можно прекратить выравнивание порядков и присвоить окончательному результату значение операнда, мантисса которого не сдвигалась.

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

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

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

Необходимость нормализации результата обусловлена тем, что при мантиссах операндов, удовлетворяющих условиям нормализации, в зависимости от знака операции, мантисса результата может находиться в пределах 0≤|z|<2.

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

- если 1≤|z|<2 (нормализация нарушена влево), то сдвинуть мантиссу результата на один разряд вправо и прибавить единицу к порядку результата.

При этом может возникнуть переполнение порядков.

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

Если 0<|z|<1/2, то сдвинуть мантиссу влево и вычесть единицу из порядка результата. Эти действия продолжать до тех пор, пока сохраняются условия указанного выше неравенства (если мантисса результата представлена прямым кодом, то до тех пор, пока в старшем разряде мантиссы в результате сдвига появится единица). В этом случае может возникнуть антипереполнение.

Если |z|=0, то результату присваивается машинный нуль (потеря значимости), а выполнять нормализацию нет необходимости.

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

5.6 Умножение и деление чисел в форме с плавающей точкой

Представим операцию умножения в виде:

Z = X · Y. (5.19)

тогда:

. (5.20)

где: ;.

Знак произведения определяют путем суммирования по модулю 2 цифр в знаковых разрядах сомножителей: .

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

Представим операцию деления в виде:

Z = X/Y. (5.21)

Следует помнить, что при делении чисел с плавающей точкой остатка не бывает:

(5.22)

где: ;.

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

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

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

Общий алгоритм выполнения операций умножения и деления:

- определение знака результата;

- сложение и вычитание порядков;

- умножение и деление мантисс;

- нормализация результата;

- округление результата.

Как отмечалось ранее, необходимость округления результата вызвана тем, что при нормализации результата может выполняться правый сдвиг мантиссы результата и младший ее разряд при этом выходит за пределы разрядной сетки. Если считать, что результат представлен прямым кодом, то отбрасывание этого разряда вносит в абсолютную величину результата либо нулевую погрешность (если отбрасывается цифра 0), либо погрешность, равную 1/2 веса младшего разряда (если отбрасывается цифра 1). Для того, чтобы погрешность по абсолютной величине результата была знакопеременной и ее среднее значение в достаточно большой последовательности операций было равно нулю, округление следует производить следующим образом. Если за пределы разрядной сетки сдвигается цифра (1), то младший разряд мантиссы результата устанавливают в единицу независимо от того, какая цифра была в этом разряде ранее. В другом случае значение младшего разряда не меняют.

Пусть( х_m) - младшая цифра мантиссы результата до округления, (х'_m) - та же цифра после округления, (x_m+1) - цифра мантиссы, выходящая за пределы разрядной сетки при округлении, () - погрешность округления. Тогда все возможные ситуации при округлении иллюстрируются табл. 11.4, из которой видно, что при таком округлении погрешность абсолютной величины мантиссы результата будет равна 0 или ±1/2 веса младшего разряда, а ее среднее значение равно нулю.

Таблица 5.3 – Результаты округления мантиссы результата

xm	xm+1	x’m	
0	0	0	0
0	1	1	+(1/2)2-m
1	0	1	0
1	1	1	-(1/2)2-m

5.7 Алгоритмы выполнения операций над числами в форме с плавающей точкой, в представлении IEEE-754

Вещественное число может быть представлено в каком-либо формате стандарта IEEE-754 следующим образом:

. (5.23)

С учетом условия нормализации (), минимальные и максимальные абсолютные значения мантисс:

. (5.24)

. (5.25)

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

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

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

Проанализируем различные ситуации:

1. .

Нет нарушения нормализации.

2.

Нет нарушения нормализации.

3. .

Здесь имеет место нарушение нормализации влево на 1 разряд.

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

1. .

Нет нарушения нормализации.

2. ; 0,5<Z<1

Нарушение нормализации вправо на 1 разряд.

3. ; 1<Z<2

Нет нарушения нормализации.

4. .

Нет нарушения нормализации.

Лекция № 15 (90-минут)

Тема: Представление числовых данных в коде BCD

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

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

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

Однако эмпирическим путем установлено, что для создания десятичных вычислительных средств наиболее целесообразно использовать двоично-десятичные коды (BCD или ДДК), обладающие свойствами взвешенности, упорядоченности, четности, дополнительности и единственности (так называемыми свойствами Рутисхаузера).

ДДК называется взвешенным, если каждому из (h) разрядов двоичного представления (a_ha_h-1...a₁) десятичной цифры (А) поставлены в соответствие веса – ( _h, _h-1,…,₁ ) причем:

A=a_h_h+a_h-1_h-1+...+a₁₁. (6.1)

где: А - десятичная цифра;

(a_ha_h-1...a₁) - ) разряды двоичного представления;

( _h, _h-1,…,₁ ) – веса.

Свойство взвешенности упрощает выполнение логических и арифметических операций. ДДК, получаемые друг из друга простой перестановкой весов (_i), образуют кодовую группу. Для обозначения конкретных ДДК и кодовых групп часто используют последовательность их весов, записанную в порядке их убывания, например, "8,4,2,1", "4,4,2,1" и т.п.

Упорядоченность ДДК состоит в выполнении одного из условий:

0₍₂₎<1₍₂₎<2₍₂₎<...<9₍₂₎. (6.2)

0₍₂₎>1₍₂₎>2₍₂₎>...>9₍₂₎. (6.3)

для двоичных представлений ( 0₍₂₎,1₍₂₎,2₍₂₎,...,9₍₂₎ ) десятичных цифр. Наличие упорядоченности ДДК необходимо для реализации логических операций.

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

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

Особенностью взвешенных ДДК, имеющих только положительные веса, кроме ДДК группы "8,4,2,1", является отсутствие однозначного представления десятичных цифр. Это означает, что некоторые десятичные цифры могут быть записаны несколькими комбинациями двоичных цифр. Например, в ДДК "4,4,2,1" цифру 4 можно представить как 1000 и как 0100, цифру 5 – как 1001 и как 0101, цифру 6 – как 1010 и как 0110, цифру 7 – как 1011 и как 0111. Причиной этого служит неоднозначность решения уравнения (6.1) относительно переменных a_i (i=l,h).

Однозначность представления десятичных цифр, состоящая в том, что каждой такой цифре соответствует только одна из 16 двоичных тетрад, обеспечивается в ДДК группы "8,4,2,1".

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

Таблица 6.1 – Кодовые группы однозначных ДДК

«8,4,2,1»	«8,-4,2,1»	«8,-6,4,1»	«8,-4,3,2»	«8,-5,4,2»
«8,4,2,-1»	«8,4,3,-2»	«8,-6,5,3»	«7,-6,5,3»	«8,-4,-2,1»
«8,4,-2,1»	«8,6,-4,1»	«8,4,-3,2»	«8,-4,2,-1»	«8,5,-4,2»
«8,-4,3,-2»	«7,6,-5,3»	«8,4,-3,-2»	«8,5,-4,-2»	«8,6,-4,-1»
«8,7,-4,-2»

В этом перечне ему соответствует более слабое свойство единственности. Это свойство для неоднозначных ДДК может быть обеспечено выбором одной и исключением из ДДК избыточных (хотя, в принципе, правильных) двоичных представлений десятичных цифр. В этом отношении свойство единственности ДДК не эквивалентно свойству однозначности систем счисления, так как единственность ДДК можно обеспечить искусственно, а однозначность должна быть присуща счислению «органически». Существует 86 кодовых групп безизбыточных ДДК, обладающих свойствами взвешенности и единственности. Среди них есть ДДК, отрицательными весами, например, "8,4,2,1", "8,4,2,-1", "6,3,-1,-1". Свойством дополнительности обладают все взвешенные ДДК с положительными весами, у которых сумма весов равна (9). Существуют четыре кодовых группы взвешенных ДДК, обладающих также и свойствами единственности и дополнительности, с именно: "5,2,1,1", "4,3,1,1", "4,2,2,1", "3,3,2,1". Среди взвешенных ДДК с отрицательными весами свойствами единственности и дополнительности обладают ДДК из 19 кодовых групп, перечисленных в табл. 6.2.

Таблица 6.2 – Кодовые группы ДДК с отрицательными весами, обладающие свойствами единственности, дополнительности и взвешенности

«6,3,1,-1»	«7,3,1,-2»	«6,4,1,-2»	«6,5,1,-3»	«7,5,1,-4»
«6,2,2,-1»	«5,3,2,-1»	«6,3,2,-2»	«8,3,2,-4»	«4,4,2,-1»
«6,4,2,-3»	«8,4,2,-5»	«6,5,2,-4»	«4,4,3,-2»	«5,4,3,-3»
«8,4,3,-6»	«7,5,3,-6»	«8,4,-2,-1»	«8,6,-1,-4»

Упорядоченность присуща лишь ДДК, не имеющим отрицательных весов. Одновременно свойствами единственности, упорядоченности, дополнительности и взвешенности обладают ДДК кодовых групп "5,2,1,1", "4,3,1,1", "3,3,2,1","4,2,2,1". Всеми пятью свойствами обладают ДДК кодовой группы "4,2,2,1", называемые также кодами Эмери ("2,4,2,1" – код Айкена).

Недостатком ДДК этой кодовой группы является искусственный порядок весов, что затрудняет выполнение арифметических операций.

Наиболее распространенным в компьютерных системах является ДДК "8,4,2,1", который называется также кодом прямого замещения. Этот ДДК получают путем записи десятичных цифр в двоичной позиционной однородной системе счисления с естественным порядком весов. Он обладает всеми перечисленными выше свойствами ДДК, кроме свойства дополнительности. Этим обусловлен ряд неудобств при реализации операций алгебраического сложения в таком ДДК из-за трудностей формирования переносов из младшей тетрады в старшую. Достоинством ДДК "8,4,2,1" следует считать простоту и удобство перевода чисел из десятичной системы счисления в двоично-десятичную и обратный перевод. В каждом конкретном случае применение какого-либо ДДК обуславливается определенными его преимуществами по сравнению с другими типами ДДК. Например, код "7,4,2,1" применяется в электромеханических цифровых устройствах, где двоичной единице соответствует замкнутое состояние некоторой контактной пары и энергопотребляющее состояние соответствующей электрической цепи, а двоичному нулю - разомкнутое состояние контактной пары и не потребляющее энергии состояние электрической цепи. В этом случае каждое двоичное представление десятичной цифры содержит не более двух единиц, что обеспечивает минимальное и постоянное потребление энергии от источника питания. В ДДК "5,4,2,1", десятичные цифры можно рассматривать как двоично-пятеричные с кодированным представлением цифр. Три младших разряда в каждой тетраде изображают одну пятеричную цифру, с старшая цифра тетрады соответствует двоичному разряду. Этот ДДК имеет ряд достоинств при выполнении арифметических операций и переводе чисел из одной системы счисления в другую.

Для представления десятичных цифр могут быть использованы и невзвешенные ДДК. Например, код "с избытком 3" обладает свойством дополнительности и его удобно использовать для выполнения операции алгебраического сложения. Для записи десятичной цифры в ДДК "с избытком 3" необходимо двоичную тетраду этой цифры в ДДК "8,4,2,1" сложить с двоичным представлением числа (3).

ДДК "8,4,2,1" и коды с избытком (полученные из кода "8,4,2,1" по аналогии с кодом "с избытком 3") обладают еще одним важным свойством, не входящим в перечень Рутисхаузера, а именно: свойством аддитивности. Это свойство состоит в том, что ДДК суммы двух десятичных цифр равен двоичной сумме ДДК этих цифр или отличается от нее на некоторую константу. Это свойство позволяет свести операции десятичной арифметики в таких ДДК к выполнению операций по правилам двоичной арифметики.

Примерами избыточных ДДК, где каждая десятичная цифра кодируется пятью двоичными разрядами, являются ДДК "3А+2" и "2 из 5". Первый из этих ДДК обладает свойством дополнительности, а двоичные представления десятичных цифр получают в нем путем записи в двоичной системе с естественным порядком весов числа ЗА+2, где А – заданная десятичная цифра.

В ДДК "2 из 5" каждая десятичная цифра изображается пятью двоичными разрядами, из которых только два содержат единицы. Можно считать, что ДДК "2 из 5" получается из ДДК "7,4,2,1" путем добавления справа дополнительного разряда с весом, равным нулю. В этот разряд записывают такую цифру, чтобы общее число единиц было равно двум (за исключением десятичного нуля). ДДК "3А+2" и "2 из 5" используют обычно для передачи информации, поскольку они позволяют обнаруживать одиночные ошибки, возникающие в процессе такой передачи, сравнительно простыми средствами.

Рефлексный ДДК (код Грея, соседний код) обладает тем свойством, что двум соседним десятичным цифрам в нем соответствуют кодовые комбинации, отличающиеся только в одном двоичном разряде. Это свойство эффективно используется при построении измерительных преобразователей (датчиков) величины углового или линейного перемещения в цифровой эквивалент.

ДДК – (w,x,y,z,) - обладает следующим свойством. Для десятичной цифры (А) в таком ДДК перестановка ее двоичных разрядов вида (z,w,x,y) равна младшему десятичному разряду (в двоичном представлении) произведения (А) на (3); перестановка вида (x,y,z,w) равна младшему разряду произведения (А) на (7); перестановка (y,z,w,x) равна младшему разряду произведения (А) на( 9).

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

6.1 Форматы числовых данных BCD - кодов

В современных компьютерных системах, обрабатывающих не только числовую информацию, но и текстовую (алфавитно-цифровую), отдельные символы чаще всего представляются словами длиной в один байт. Так как байт равен двум двоичным тетрадам, то в компьютерных системах с байтовым представлением информации можно записывать две десятичные цифры в один байт. Такую запись называют также упакованной записью или упакованным форматом записи десятичных цифр. Вместе с тем, можно записывать в один байт и по одной десятичной цифре, используя остальные четыре разряда для записи знаков и вспомогательных символов. Такую запись называют распакованной записью или распакованным форматом. В компьютерных системах широкого назначения обычно реализуются обе возможности записи десятичных цифр. Рассмотрим упакованный десятичный формат. Младшая цифра занимает в байте правую тетраду (биты 3-0), а старшая – левую (биты 7-4). Обе цифры представлены в коде «8,4,2,1». Многоразрядные упакованные десятичные числа занимают несколько байт. Для представления знака числа используют запрещенные кодовые комбинации: для «+» – C₍₁₆₎, для «–» – D₍₁₆₎. Код знака числа записывают в старшей тетраде старшего байта.

Распакованный формат называют символьным или ASCII - форматом.

Каждый байт содержит код, соответствующий десятичной цифре в кодовой таблице ASCII. В ней цифры имеют коды 30₍₁₆₎-39₍₁₆₎. Таким образом, значение десятичной цифры представлено в младшей тетраде, а старшая тетрада является кодом «зоны» (3). Поэтому такой формат также называют зонированным. Для обозначения знака используют коды символов «+» и «–» из кодовой таблицы ASCII (2B₍₁₆₎ 2D₍₁₆₎ соответственно).

Лекция № 16 (90-минут)

Тема: Арифметические операции над числовыми данными BCD - кодов

Сложение и вычитание десятичных двоично-кодированных операндов может быть реализовано на основе тех же принципов, что и двоичных операндов с учетом лишь особенностей суммирования десятичных цифр в двоичном их представлении:

- правила формирования десятичного переноса отличаются от правил формирования двоичного переноса;

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

По этим причинам при использовании ДДК, обладающих свойством аддитивности, суммирование десятичных цифр в двоичном представлении проводят в два этапа:

1) суммируют двоичные представления десятичных цифр по правилам двоичной арифметики;

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

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

Рассмотрим, как можно определить корректирующую поправку и правильно сформировать перенос в старший десятичный разряд для ДДК "8,4,2,1". Для этого составим таблицу двоичных сумм, их представлений после первого этапа сложения, правильных их представлений в ДДК "8,4,2,1" десятичных переносов и корректирующих поправок (табл. 6.3).

Таблица 6.3 - Таблица двоичных сумм после первого этапа сложения

Десятичная сумма	Сумма после первого этапа s5s4s3s2s1	Правильная сумма pz4z3z2z1	Коррекция с5с4с3с2с1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19	0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1	0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0

Из таблицы видно, что если результат, полученный на первом этапе, находится в пределах от 0 до 9, то корректировать его нет необходимости, а двоичный и десятичный перенос в этом случае совпадают. Если же результат первого этапа находится в пределах от 10 до 19, то для образования правильной суммы (pz₄z₃z₂z₁) к предварительной сумме (s₅s₄s₃s₂s₁) необходимо прибавить корректирующую поправку (00110). Признаком нахождения суммы первого этапа в диапазоне от 10 до 19 может служить наличие единичного значения переноса p. Таким образом, если при прибавлении коррекции перенос (р=0), то как правильную сумму необходимо взять результат первого этапа, если же (p=l), то как правильную сумму необходимо взять откорректированный результат.

При сложении или вычитании многоразрядных десятичных операндов описанные действия должны выполняться по каждому десятичному разряду (в ДДК "8,4,2,1" – по каждой тетраде двоичных разрядов).

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

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

- суммирование частичных произведений должно осуществляться по правилам десятичной арифметики (то есть, используются для этого десятичные сумматоры);

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

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

Для учета особенности при умножении с младших разрядов или при умножении со старших разрядов десятичный разряд регистра множителя снабжают цепями вычитания единиц и в каждом такте суммирования цифру в этом разряде уменьшают на единицу. Такты суммирования производят до тех пор, пока в десятичном разряде, управляющем умножением, не будет получен нуль. Если для представления десятичных цифр используется ДДК "8,4,2,1", то указанный десятичный разряд выполняют в виде счетчика.

При умножении по этому алгоритму на один разряд множителя в среднем приходится 4,5 тактов суммирования (предполагаем, что цифры 0,1,...,9 появляются во всех разрядах множителя с равными вероятностями).

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

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

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