Арифметические основы электронных вычислительных машин

Размещено на http://www.allbest.ru/

АРИФМЕТИЧЕСКИЕ ОСНОВЫ ЭВМ



1. Основные положения

арифметический операция сложение деление

Основой всех арифметических операций в ЭВМ являются операции сложения/вычитания, умножения и деления.

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

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

Обычно все операции над данными в современных ЭВМ выполняются параллельно-последовательно. Количество параллельно обрабатываемых разрядов определяется шириной трактов передачи и обработки информации. Обычно это 1, 2 , 4 или 8 байт. В десятичной арифметике и при обработке строк символов, вне зависимости от ширины трактов, используется побайтовая обработка данных.

Основными арифметическими операциями в ЭВМ являются операции:

· сложения / вычитания,

· умножения,

· деления.

2. Арифметические операции с плавающей запятой

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

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

1. сравниваются порядки операндов,

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

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

Пример:

Операнд А=0,1111₂ Ч 2¹,^, после выравнивания порядков А = 0,0111₂ Ч 2²

Операнд В=0,1101₂ Ч 2²,

Порядки операндов не равны. Производится денормализация операнда А. После выравнивания порядков А = 0,01112 Ч 2²

С = А+В = 1,0100₂ Ч 2^2, после нормализации С = 0,1010₂ Ч 2³.

С = В-А = 0,0100₂ Ч 2², после нормализации С= 0,1000₂ Ч 2¹.

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

· умножение или деление мантисс,

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

· Если мантисса результата получается ненормализованной, то производится ее нормализация.

Пример:

Операнд А=0,1000₂ Ч 2¹,^,

Операнд В=0,1001₂ Ч 2²,

С=А Ч В

Умножение мантисс: М_С = 0,1000₂ Ч 0,1001₂= 0,0100 1000₂ или, с учетом разрядности регистров, М_С = 0,0100₂

Сложение порядков: П_С = 1+2=3 (2¹Ч 2²=2³)

Предварительный результат: С=0,0100₂Ч 2³

Или, После нормализации мантиссы - С=0,1000₂ Ч 2².

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

3. Десятичная арифметика

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

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

Когда сумма цифр равна десяти (1010₍₂₎) двоично-десятичный сумматор должен формировать единицу переноса и тетраду 0000₍₂₎ результата Для этого применяются коды с избытком 6. При сложении разрядных цифр слагаемых к ним при помощи дополнительных цепей добавляется цифра 6 (0110₍₂₎). В результате значение суммы увеличивается на 6 и при сумме равной десяти и более формируется единица переноса в старший разряд (тетраду) и правильная разрядная цифра суммы. Но в случае, когда разрядная сумма принимает значение меньше десяти, она оказывается смещенной в диапазон от 6 до 15, что не соответствует двоично-десятичной кодировке. Для получения правильной суммы делается коррекция.

При отсутствии переноса в старшую тетраду к полученной разрядной сумме добавляется число 1010₍₂₎ с блокировкой переноса в старшую тетраду. Это равносильно уменьшению числа на 6 (0110₍₂₎), т.е. снятию смещения.

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

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

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

Если из старшей тетрады нет переноса, то получен отрицательный результат, представленный в дополнительном коде. В этом случае, результат инвертируется и к нему прибавляется 1. Новый результат корректируется, при этом к тетрадам, из которых не возникал перенос, прибавляется число 1010₍₂₎.

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

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

· схемы алгебраического сложения/вычитания чисел (действия сложения и вычитание рассматриваются как однотипные) в прямом, обратном и дополнительных кодах,

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

· схемы умножения дробных чисел в прямом, обратном и дополнительных кодах,

· схемы деления целых чисел в прямом, обратном и дополнительных кодах.

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

Алгебраическое сложение/вычитание чисел в прямом коде

Пример:

С = А В, где:

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

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

· проверка знака первого операнда; если первый операнд отрицательный, то формируют его представление в дополнительном или обратном коде,

· проверка знака второго операнд; если второй операнд отрицательный, то формируют его представление в дополнительном или обратном коде,

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

Эту цепочку действий можно модифицировать.

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

1. А + В= + (А + В)

2. А + (- В)= + (А - В)

3. (- А) + В= - (А - В)

4. (-А) + (-В)= - (А + В)

А - В= + (А - В)

6. А - (- В)= + (А + В)

7. (- А) - В= - (А + В)

8. (- А) - (- В)= - (А - В)

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

· сравнение знаков операндов. Если знаки операндов разные, то арифметическое действие заменяется обратным (вычитание - сложением, а сложение - вычитанием),

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

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

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

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

В блок схеме используются два типа блоков:

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

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

Рис. 1. Блок схема алгоритма выполнения алгебраического сложения / вычитания чисел в прямом коде

T&/V триггер кода операции/переполнения T&/v

Алгебраическое сложение/вычитание чисел в дополнительном коде

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

Схемы умножения целых чисел в прямом коде

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

Произведение чисел без знака А и В можно записать в виде:

АВ=А(b_n 2ⁿ + b_n-₁ 2^n-1 + …+ b₁ 2 + b₀),

где b - двоичная цифра числа В.

Умножение числа А на 2ⁿ равносильно сдвигу числа А вправо на n разрядов. Таким образом, умножение в двоичной системе сводится к последовательности сдвигов множителя и сложению его с частичным произведением, при единичном значении соответствующей разрядной цифры множителя. Начальное значение частичного произведения устанавливается нулевым, после выполнения всех сложений оно равно произведению А на В. Сдвиг множителя производится относительно частичного произведения. Здесь возможны четыре варианта схем умножения:

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

· умножение с младших разрядов множителя и сдвиг множимого влево (вариант схема b на рис. 2.),

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

· умножение со старших разрядов множителя и сдвиг множимого вправо (вариант схема d на рис. 2.).

При умножении n-разрядных чисел результат формируется 2n-разрядный.

Умножение по схеме a использует три n-разрядных регистра. При этом сдвигаемые вправо разряды суммы частичных произведений принимаются в освобождаемые разряды множителя. Эта схема требует минимального оборудования и часто используется в ЭВМ.

Схема b не имеет никаких преимуществ по сравнению с а и практически не используется.

Рис. 2. Схемы выполнения умножения



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

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

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

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

А = 7₍₁₀₎ =SignA 111₍₂₎ - множимое.

В = 5₍₁₀₎ =SignВ 101₍₂₎ - множитель.

С - произведение.

При умножении числа А и В рассматриваются как числа без знаков. Знак произведения определяется отдельно. Знак произведения будет положительным, если знаки сомножителей совпадают. Положительное значение произведения определяется по совпадению знаков сомножителей. При умножении n-разрядных чисел разрядность результата не превышает 2n, но возможен перенос из старшего разряда сумматора при вычислении сумм частичных произведений. Для его сохранения регистр суммы сумм частичных произведений должен иметь дополнительный разряд.

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

Множимое А (3 бита)	Произведение С (4 бита)	Множитель В (3 бита)	Комментарии
111	0 000	101	Исходное состояние.
	0 000 0 111 0 111	101	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений
	0 011	110	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	0 011 0 000 0 011	110	Анализ младшего бита множителя (0) и блокировка прибавления множимого к сумме частичных произведений.
	0 001	111	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	0 001 0 111 1 000	111	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений
	0 100	011	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.

Результат С =0,100011₍₂₎ = 35₍₁₀₎.

Блок схема алгоритма выполнения умножения целых чисел в прямом коде по схеме а (умножение с младших разрядов множителя со сдвигом частных произведений вправо) представлена на рис. 3.

Рис. 3. Блок схема алгоритма выполнения умножения целых чисел в прямом коде по схеме а (умножение с младших разрядов множителя со сдвигом частных произведений вправо).

Схемы умножения дробных чисел в прямом коде

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

Рис. 4. Блок схема алгоритма выполнения умножения дробных чисел в прямом коде по схеме а (умножение с младших разрядов множителя со сдвигом частных произведений вправо)

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



Схемы умножения чисел в дополнительном коде

Схема умножение чисел в дополнительном коде отличается от умножения в прямом коде тем, что:

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

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

· в схеме с знаковый разряд должен распространяться на все старшие разряды сумматора,

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

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

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

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

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

А =-7₍₁₀₎ = 11,001₍₂₎ - множимое.

В = +5₍₁₀₎ = 0,101₍₂₎ - множитель

С - произведение.

Множимое А (3 бита)	Произведение С (4 бита)	Множитель В (3 бита)	Комментарии
11,001	00,000	0,101	Исходное состояние.
	00,000 11,001 11,001	0,10 1	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений
	11,100	10,1 0	Сквозной сдвиг суммы частичных произведений (с распространением знака) и множителя вправо на один разряд
	11,100 00,000 11,100	10,1 0	Анализ младшего бита множителя (0) и блокировка прибавления множимого к сумме частичных произведений.
	11,110	010, 1	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	11,110 11,001 10,111	010, 1	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений
	11,011	1010,	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	11,011	1010,	Анализ младшего бита (знака) множителя (0) и блокировка прибавления множимого к сумме частичных произведений.

Результат С = 11,011101₍₂₎ = - 35₍₁₀₎.

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

А =-7₍₁₀₎ = 00,111 - множимое.

В = -5₍₁₀₎ = 1,011 - множитель

С - произведение.



Множимое А (3 бита)	Произведение С (4 бита)	Множитель В (3 бита)	Комментарии
11,001	00,000	1,011	Исходное состояние.
	00,000 11,001 11,001	1,011	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений
	11,100	11,01	Сквозной сдвиг суммы частичных произведений (с распространением знака) и множителя вправо на один разряд
	11,100 11,001 10,101	11,01	Анализ младшего бита множителя (1) и прибавление множимого к сумме частичных произведений.
	11,010	111,0	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	11,010 00,000 11,010	111,0	Анализ младшего бита множителя (0) и блокировка прибавления множимого к сумме частичных произведений
	11,101	0111	Сквозной сдвиг суммы частичных произведений и множителя вправо на один разряд.
	11,101 00,111 00,100	0111	Умножение на разряд знака: анализ знака множителя (1) и вычитание множимого (прибавление в дополнительном коде) из суммы частичных произведений.

Результат С = 00,100011₍₂₎ = + 35₍₁₀₎.

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

Схемы умножения дробных чисел в дополнительном коде

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

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

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

Схемы ускоренного умножения

Схемы ускоренного умножения строятся на основе перехода на системы счисления с большим основанием. Для быстрого преобразования используются системы счисления с основаниями, равными степеням двойки: 4, 8, 16 и т.д. При использовании этих схем приходится использовать таблицы умножения для этих систем. Для быстроты преобразования используют системы счисления с основаниями, равными степеням двух: 4, 8, 16 и т.д. При этом приходится применять таблицы умножения для этих систем счисления. Это табличные методы. Например, нужно построить схему умножения для однобайтных чисел. Для этого нужна таблица в 2¹⁶ двухбайтных строк (128 Кбайт). В этой таблице нужно разместить результаты перемножения любых двух однобайтных чисел. Адресом служат комбинации байтовых операндов. Результат читается из таблицы. Произведение считывается из таблицы по адресу, которым служит комбинация этих однобайтнах чисел.

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

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

А = а₁ 2⁴ + а₀

B = b₁ 2⁴ + b₀

С = АB = 2⁸ а₁ b₁+ 2⁴ a₀ b₁ + 2⁴ a₁ b₀ + а₀ b₀

Для вычисления этого выражения требуется четыре обращения к комбинационным схемам (или одно обращение к четырем комбинационным схемам) с аргументами: а₁ b₁, a₀ b₁, a₁ b₀, а₀ b₀ и сложение полученных произведений с соответствующими сдвигами на 8, 4, 4, и 0 разрядов влево. В этом решении случае требуется таблица всего на 64 байта, реализованная в виде комбинационной схемы.

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

Эта схема умножения применима только при сдвиге множителя вправо (схемы а и b - умножение с младших разрядов).

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

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

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

· 0 00 -блокировка прибавления множимого.

· 0 01 -суммирование множимого с суммой частичных произведений.

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

· 0 11 - вычитание значения множимого из суммы частичных произведений. При этом сумма частичных произведений становится отрицательной, так как учетверенное множимое всегда больше суммы частичных произведений. Здесь сложение множимого, умноженного на три, заменяется его вычитанием в текущем цикле, с последующим прибавлением учетверенного множимого. (3=4-1).

· 1 00 -суммирование множимого с суммой частичных произведений.

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

· 1 10 -вычитание значения множимого из суммы частичных произведений.

· 1 11 -блокировка прибавления множимого.

Блок схема алгоритма умножения со сдвигом на два разряда множителя представлена на рис.6.

Рис.6. Блок схема алгоритма умножения со сдвигом на два разряда множителя

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

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

А = +15₍₁₀₎ = 0,1111₍₂₎ - множимое.

В = +13₍₁₀₎= 0,1101₍₂₎ - множитель.

С = 0,0000 - сумма частичных произведений.

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

Множимое А	Произведение С	Множитель В	Комментарии
0,1111	0,0000	1101	Исходное состояние
	0,0000	0011 01	Сквозной сдвиг суммы частичных произведений и множителя вправо на два разряда с размножением знака.
	0,0000 0,1111 0,1111	0011 01	Анализ трех бит 001 (знака суммы частичных произведений и двух младших разрядов множителя) и прибавления множимого.
	0,0011	1100 11	Сквозной сдвиг суммы частичных произведений и множителя вправо на два разряда с размножением знака
	0,0011 1,0001 1,0100	1100 11	Анализ трех бит 011 (знака суммы частичных произведений и двух младших разрядов множителя) и вычитание множимого
	1,1101	0011 00	Дополнительный сквозной сдвиг суммы частичных произведений и множителя вправо на два разряда с размножением знака
	1,1101 0,1111 0,1100	0011 00	Анализ трех бит 100 (знака суммы частичных произведений и двух младших разрядов множителя) и прибавления множимого.

Результат С = 0,11000011₍₂₎ = 195₍₁₀₎.

Схемы деления целых чисел без знака

В ЭВМ деление целых чисел - это целочисленное деление с получением частного и остатка. В большинстве ЭВМ имеется две команды деления целых чисел: DIV (деление чисел без знака) и IDIV (деление чисел со знаком).

При выполнении команды IDIV остатку приписывается знак делимого. Например, при делении числа (-5) на (-2) в частном получается 2 и (-1) в остатке.

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

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

Машинное деление реализуется по двум основным схемам:

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

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

2. Устройство деления с сумматором обычной (не удвоенной) разрядности позволяет использовать способ деления со сдвигаемым влево делимым. Это наиболее распространенная схема деления.

Устройство деления со сдвигаемым влево делимым.

Данный способ деления позволяет использовать сумматор обычной (не удвоенной) разрядности Это наиболее распространенная схема деления.

Схема выполнения деления со сдвигаемым делимым представлена на рис. 7.

Рис. 7. Схема выполнения деления со сдвигаемым делимым

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

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

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

· При делении 2n-разрядного делимого на n-разрядный делитель возможно получение (n+1)-разрядного частного. Это случай переполнения разрядной сетки. Переполнение разрядной сетки выявляется при первом пробном вычитании. Если результат пробного вычитания дает положительный частный остаток, то это признак переполнения при делении.

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

Схемы деления целых чисел без знака (в прямом коде)

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

Пример. Деление целых чисел без знака с восстановлением отрицательных остатков:

А = 38₁₀ = 100110₍₂₎делимое (число без знака),

В = 5₁₀ = 101₍₂₎делитель (число без знака),

С - частное от деления (число без знака),

В модифицированном дополнительном коде (- В)=11 1011₍₂₎

№ цикла	Делимое/ частичный остаток	Делитель	Частное	Комментарии
0	0,0100110 +1,1011 . 1,1111 +0,0101 0,0100110	101		Исходное состояние Пробное вычитание (дополнительный код) Результат отрицательный (переполнения нет) Восстановление остатка. Остаток восстановлен
2	0,100110 +1,1011 0,010010	101	1	Сдвиг делимого, Первое вычитание (дополнительный код) Результат положительный. Цифра частного 1
3	0,1001 +1,1011 . 0,0100	101	11	Сдвиг делимого Второе вычитание (дополнительный код) Результат положительный. Цифра частного 1.
4	0,1000 +1,1011 0,0011	101	111	Сдвиг делимого Третье вычитание) Результат положительный. Цифра частного 1

Результат деления 100110 (38₁₀) на 101(5₁₀):частное - 111 (7₁₀), остаток - 011(3₁₀) (числа без знаков).

Результат :

частное С = 111_(2), =7(₁₀₎ (число без знака).

остаток - 0011₍₂₎ =3₍₁₀₎ (число без знака).

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

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

Если при очередном вычитании получился отрицательный частичный остаток (А-В) = а<0, то его восстановление заключается в операции а + В.

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

2 (а + В) = 2а + 2В.

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

2а + 2В - В = 2а + В.

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

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

Пример: Деление целых чисел без восстановления отрицательных остатков.

А = 55₍₁₀₎ = 110111₍₂₎делимое (число без знака),

В = 7₍₁₀₎ = 111₍₂₎делитель (число без знака),

С - частное от деления (число без знака).



№ цикла	Делимое/ частичный остаток	Делитель	Частное	Комментарии
0	00.110000 +11.001 . 11.111000	00.111		Исходное состояние Пробное вычитание (дополнительный код) Результат отрицательный. (Переполнения нет)
2	11.11000 +00.111 . 00.10100	00.111	1	Сдвиг отрицательного делимого влево и вместо вычитания - сложение с делителем. Результат положительный, цифра частного = 1.
3	01.0100 +11.001 . 00.0110	00.111	11	Сдвиг положительного делимого влево и вычитание (дополнительный код) делителя. Результат положительный, цифра частного = 1.
4	00.0110 +11.001 11.110	00.111	110	Сдвиг положительного делимого влево и вычитание (дополнительный код) делителя. Результат отрицательный, цифра частного = 0.
	11.110 00.111 00.110	00.111		Восстановление отрицательного остатка.

Результат деления 110111 на 101:

частное - 110, остаток - 0110. (числа без знаков).

Результат :

Частное С = 110₍₂₎ = 6₍₁₀₎, (число без знака).

остаток - 0110₍₂₎ =6₍₂₎, (число без знака).

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

Рис.8. Блок схема алгоритма деления целых чисел без знаков (в прямом коде) без восстановления отрицательных остатков.

Схемы деления целых чисел со знаком (в дополнительном или обратном кодах)

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

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

· действия с делимым и частичными остатками (сложение или /вычитание) определяются соотношениями знаков делителя и делимого или частичных остатков:

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

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

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

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

1. при положительном делимом и отрицательном делителе,

2. при отрицательном делимом, положительном делителе и при ненулевом остатке,

3. при отрицательных делимом и делителе и при нулевом остатке.

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

Делимое - А = 27₍₁₀₎ = 0.0100011₍₂₎,

Делитель - В = -5_{(10) ,} = 1.1011₍₂₎ (в дополнительном коде)

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



№ цикла	Делимое/ частичный остаток	Делитель	Частное	Комментарии
0	0.0011011 +1.1011 . 1.1110011	1.1011	1.	Исходное состояние Знаки не совпадают - сложение Знаки совпадают - цифра (знак частного) = 1
2	1.110011 +0.0101 . 0.000111	1.1011	1.0	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного 0
3	0.00111 +1.1011 . 1.11101	1.1011	1.01	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
4	1.1101 +0.0101 0.0010	1.1011	1.010	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного 0
5	0.0010		1.011	А>0, B<0, Коррекция частного(+1)

Результат деления 011011 (27₍₁₀₎) на 1.011 (-5₍₁₀₎),

Частное - 1.011 (-5₍₁₀₎), остаток - 0.010 (2₍₁₀₎)

Результат деления

частное - 1.011₍₂₎ = -5₍₁₀₎,

остаток - 0.010 ₍₂₎= 2_(10).

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

Делимое - А = - 27₍₁₀₎ = 1.100101₍₂₎ (в дополнительном коде).

Делитель - В = 5₍₁₀₎ = 0.101₍₂₎.

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

№ цикла	Делимое/ частный остаток	Делитель	Частное	Комментарии
0	1.1100101 +0.0101 . 0.0001101	0.0101	1.	Исходное состояние Знаки не совпадают - сложение Знаки совпадают - цифра (знак частного) = 1
2	0.001101 +1.1011 . 1.111001	0.0101	1.0	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного 0
3	1.11001 +0.0101 . 0.00011	0.0101	1.01	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
4	0.0011 +1.1011 1.1110	0.0101	1.010	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного 0
5	1.1110	0.0101	1.011	А>0, B<0, Коррекция частного(+1)

Результат деления 1.100101 на 0.101, частное - 1.011, остаток - 1.110 (дополнительный код).

Результат деления:

частное - 1.011₍₂₎ = - 5₍₁₀₎ ,

остаток - 1.110₍₂₎ = - 2_(10).

Схемы деления дробных чисел

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

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

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

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

Делимое - А = -27/64₍₁₀₎ = 1.100101₍₂₎ (в дополнительном коде).

Делитель - В = 40/64₍₁₀₎ = 0.101000_(2)..

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

№ цикла	Делимое/ частичный остаток	Делитель	Частное	Комментарии
0	1.1100101 +0.0101000. 0.0001101	0.0101000	1.	Исходное состояние Знаки не совпадают - сложение Знаки совпадают - цифра (знак частного) = 1
2	0.0011010 +1.1011000. 1.1110010	0.0101000	1.0	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного = 0
3	1.1100100 +0.0101000 0.0001100	0.0101000	1.01	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
4	0.0011000 +1.1011000 1.1110000	0.0101000	1.010	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного = 0
5	1.1100000 0.0101000 0.0001000	0.0101000	1.0101	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
6	0.0010000 1.1011000 1.1101000	0.0101000	1.01010	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного = 0
7	1.1101000 0.0101000 0.0001000	0.0101000	1.010101	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
8	0.0010000 1.1011000 1.1101000	0.0101000	1.0101010	Сдвиг делимого Знаки совпадают - вычитание Знаки не совпадают - цифра частного = 0
9	1.1101000 0.0101000 0.0001000	0.0101000	1.01010101	Сдвиг делимого Знаки не совпадают - сложение Знаки совпадают - цифра частного = 1
			1.01010101 0.00000001 1.0101011	Округление результата

Результат деления:

частное = 1.101011₍₂₎ ? -0,675₍₁₀₎ (ответ отрицательный ? Какой это код)

Блок схема алгоритма деления дробных чисел со знаками без восстановления отрицательных остатков представлена на Рис.9.

Рис.9. Блок схема алгоритма деления дробных чисел со знаками без восстановления отрицательных остатков.



Список литературы

1. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. Л.: Машиностроение, 1979. 384с.

2. Каган Б.М. Электронные вычислительные машины и системы: Учеб. пособие для вузов. - 2-е изд. перераб. и доп. - М.: Энергоатомиздат, 198 - 552с., ил.

3. Организация ЭВМ. 5-е изд./ К. Хамахер, З. Заки. - СПб.: Питер; Киев: Издательская группа BHV, 2003. -848 с.: ил. - (Серия "Классика computer science").

4. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. - СПб.: Питер. 2004. - 668 с.: ил.

Размещено на Allbest.ru