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

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

.

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

.

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

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

Числовой пример деления без восстановления остатка приведен в таблице 1. Показан только процесс обработки модулей. |A| = 33; |В| = 5.

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

Из сравнения микропрограмм на рисунках 1 и 2 еще не видно преимуществ второго варианта. Напротив, схема на рис. 2 сложнее, а что касается числа последовательно выполняемых в каждом цикле операций, то оно в обоих вариантах одинаково и равно трем. Однако можно слегка изменить схему второго алгоритма, совместив во времени запись в младший бит частного и установку триггера Т со сдвигом А и С и с декрементом счетчика. В качестве триггера Т при этом целесообразно использовать младший разряд частного (только теперь нулевое значение С [0] нужно интерпретировать, как единичное состояние триггера Т ).

С учетом сказанного скорость выполнения деления во втором варианте получается выше примерно на 30%. Это настолько чувствительный выигрыш, что на практике применяется только вариант без восстановления остатка.

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

Ваша задача будет решена с вашими исходными данными OnLine и бесплатно

Задача:

Разделить число A = 213₁₀ на число B = 17₁₀ в двоичной системе счисления, методом без восстановления остатка.

Решение:

1) Переведем числа в двоичную систему счисления (работать будем только с модулями чисел, знак результата получим из анализа знаков исходных чисел):

213₁₀ = 11010101₂
17₁₀ = 10001₂

2) Впишем делимое A в 16-ти разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
A:									1	1		1		1		1

Обратите внимание! Так как для выполнения деления требуется производить операцию вычитания, это требует использования знаковой ариaметики. И поэтому в нашем случае 15-й разряд является знаковым (0 – соответствует положительному числу, 1 – отрицательному), а старшим разрядом числа является 14-й разряд.

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

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
B:												1				1

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

4) Предварительный сдвиг делителя. Сдвинем делитель B влево так, чтобы позиция старшей значащей единицы, в нем, совпала с позицией старшей значащей единицы в делимом A. Количество необходимых для этого сдвигов запомним в числе k В нашем случае старшая значащая единица в делимом A расположена в 7-м разряде, a в делителе B – в 4-м разряде. Следовательно нам необходимо сдвинуть число B влево на 3 разряда (k = 3).
Сдвинутый делитель выглядит следующим образом :

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
B:									1				1

5) Так как в процессе деления множитель B придется не только прибавлять но и вычитать, то нам необходимо иметь число -B. Для этого представим B в дополнительном коде. Перевод в дополнительный код осуществим в два этапа:

5.1)Вначале получим обратный код. Для этого просто проинвертируем каждый разряд регистра (заменим "0" на "1", а "1" на "0").

Разр.	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
Bобр	1	1	1	1	1	1	1	1		1	1	1		1	1	1

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

Разр.	c	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
1	1	1
Bобр	1	1	1	1	1	1	1	1		1	1	1		1	1	1
+																1
Bдоп	1	1	1	1	1	1	1	1		1	1	1	1

Таким образом -B = B_доп

6) Процесс деления будет следующий:

6.1) Вычитаем из делимого А делитель В (т.е. прибавляем -В).

6.2) Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае. Помним, что отрицательному числу соответствует наличие единицы в 15-м разряде и наоборот.

6.3) Сдвигаем частичный остаток на один разряд влево. При этом крайний правый (младший) разряд заполняется нулем, а знаковый разряд (15-й) в процессе сдвига не участвует.

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

6.5) Анализируем знак полученного частичного остатка (15-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае.

6.6) Действия описанные в пунктах 6.3-6.5 выполняем k раз (если k=0, то ни разу не выполняем).
Весь процесс деления выглядит следующим образом :

Прямой код

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

Рассмотрим случай сложения чисел с разными знаками. Он сводится к вычи­танию модулей слагаемых, причем уменьшаемым должен стать больший мо­дуль. Чтобы избежать дополнительной модульной операции сравнения, мож­но произвести "наугад" вычитание А-В . Признаком того, что |А| >|B| будет отсутствие заема из нулевого в первый разряд. Поскольку рассматривается случай разных знаков слагаемых, то при отсутствии заема значение знакового разряда разности определится как 0-1 = 1-0 = 1, а при наличии заема 0-1-1 = 1-0-1 = 0. Таким образом, если при вычитании а-в получим с=1, это будет означать, что |A|>|B|, и результату следует присвоить знак числа а (с :=а). Если окажется с =0, то |A|

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

Сложение в обратном коде

1. а>0, в>0, а + в 0, в 0 (коррекция)

Еще одним достоинством применения обратного кода можно считать просто­ту взаимного преобразования прямого и обратного кода.

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

Дополнительный код

1. а>0, в>0, а + в 0, в 0 (коррекция)

3. а>0, в ДК выполняются относительно редко — только при вводе и выводе.

□ , b — знаковые разряды слагаемых;

□ с — код знака результата;

□ , bj, — двоичные переменные;

□ f — тип выполняемой операции: f = 0 — сложение, f = 1 — вычи­тание;

□ OV — признак переполнения,

□ А’ = —модули чисел;

□ — перенос из знакового разряда;

□ — ситуации переполнения в дополни­тельном коде.

Умножение в прямом коде

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

В изображенном на рис. 3.23 алгоритме, в отличие от алгоритмов сло­жения/вычитания, значение OV — 0 устанавливается безусловно. Действительно, А и В — дробные числа; очевидно при |A|

Дата добавления: 2018-09-22 ; просмотров: 282 ; ЗАКАЗАТЬ РАБОТУ