Конспект лекций по дискретной математике
Отрицательный результат будет получен в дополнительном коде и требует преобразования в прямой код.
4) Нормализация
Этот этап имеет место только при получении не нормализованного результата.
На предыдущем этапе может быть получен один из двух видов не нормализованного результата.
а) Результат денормализованый влево получается получается при сложении положительных или отрицательных операндов в случае переполнения.
Нормализация производится посредством сдвига мантиссы в право и увеличении порядка на единицу.
Если порядок результата равный порядку большего операнда был максимальным то увеличение на единицу даст особый случай "переполнение порядка".
б) Результат денормализованый вправо получается при сложении операндов с разными знаками при наличии в мантиссе результата старших нулей.
Нормализация производится сдвигом мантисса влево с целью удаления ведущих нулей .Этот сдвиг сопровождается уменьшением порядка что может повлечь "исчезновение порядка"(анти-переполнение).
Вычитание
Операция вычитания чисел с плавающей запятой сводится к сложению путем предварительного изменения знака второго операнда на противоположный.
В связи с тем, что мантисса числа представляется в прямом коде, при изменении знака числа меняется только знаковый разряд, а мантисса остается прежней.
Операция умножения целых чисел и
принципы ее реализации в ЭВМ
Основные положения двоичного умножения
А=13 x1101
В=11 1011
---------
1101
+ 1101
1101
-------------
10001111=(143)10
Другой метод:
x1101
1011
--------
1101
+ 1101
1101
------------------
10001111=(143)10
Умножение двоичных чисел (как и десятичных) состоит в последовательном умножении множимого на отдельные разряды множителя с суммированием результатов умножения. Результат умножения множимого на один разряд множителя принято называть частичным произведением. Результат умножения двух чисел представляет собой сумму всех частных произведений.
Каждое частное произведение либо совпадает с множимым, либо равно 0.
Формируемые частные произведения должны быть определенным образом сдвинуты друг относительно друга для их последующего суммирования.
Частные произведения можно формировать как начиная от младших, так начиная и от старших разрядов множителя.
В общем случае для результата умножения требуется количество цифр равное сумме количества цифр операндов. При одинаковой разрядности операндов: 2n - разрядов.
Особенности реализации умножения в ЭВМ
В операционном устройстве для умножения двоичных чисел должен использоваться многоразрядный двоичный сумматор, что предопределяет умножение в виде последовательного многошагового процесса, на каждом шаге которого проводится умножение на один разряд множителя. Сумма частных произведений: СЧП.
Для фиксации этой суммы на каждом шаге необходимо использовать 2n-разрядный процессор, n-разрядного операнда.
Перед началом операции необходимо осуществить сброс этого регистра (установить в “ноль”).
На каждом шаге умножения анализируется определенный разряд множителя, и если он равен единице, то на этом шаге производится сложение СЧП с множимым. Если разряд множителя равен нулю, то сложения на данном шаге производится.
Любой шаг умножения должен сопровождаться сдвигом множимого относительно неподвижной СЧП: принципиально возможен и подход, при котором множимое остается неподвижным, но происходит сдвиг СЧП.
Реализацию умножения принципиально можно начинать как от младшего, так и от старшего разряда множителя.
В целях упрощения схемы управления умножением регистр множителя реализуется как сдвигающий, при этом последовательные разряды множителя, на которые производится умножение на каждом шаге, постепенно перемещаются так, что дают возможность связать схему анализа с одним разрядом множителя.
При выполнении умножения начиная от младших разрядом множителя, схема анализа привязывается к младшему разряду регистра множителя, и в этом регистре реализуется сдвиг вправо. При реализации умножения начиная от старших разрядом множителя схема анализа привязывается к старшему разряду регистра множителя и в нем реализуется сдвиг вправо.
Для фиксации момента завершения операции, в операционном устройстве умножения должен быть использован счетчик (суммирующий или вычитающий).
Так как в реализации умножения можно использовать различные подходы, связанные с тем, от какого разряда множителя начинается умножение, а так же с тем относительно чего сдвигается, можно использовать четыре способа (схемы) умножения.
Способы (схемы) реализации умножения
Умножение, начиная с младших разрядов множителя со сдвигом множимого влево.
Умножение, начиная с младших разрядов множителя со сдвигом СЧП вправо.
Умножение, начиная со старших разрядов множителя со сдвигом множимого вправо.
Умножение, начиная со старших разрядов множителя со сдвигом СЧП влево.
Анализ схем:
В схемах умножения со сдвигом множимого для его представления требуется 2n-разрядный регистр.
А в схеме умножения, начиная с младших разрядов множителя со сдвигом СЧП вправо для представления множимого требуется n-разрядный регистр.
А в схеме умножения, начиная со старших разрядов множителя со сдвигом множимого вправо необходимо использовать 2n-разрядный сумматор, связанный по входу с регистром множителя.
Четвертая схема требует 2n-разрядного сумматора.
Вторая схема - n-разрядного.
В целях минимизации оборудования целесообразно использовать схему 2, на основе которой реализуется умножение практически во всех ЭВМ.
Упрощенная схема операционного устройства для реализации умножения по второму способу

Операция деления и ее реализация в ЭВМ
Особенности двоичного деления
Пример: 130/10
А= 10000010 | 1010
1010 |--------
------------- |01101
0110010
1010
-------------
001010
1010
-----------
1010
1010
Операция двоичного деления сводится к последовательному вычитанию делителя из делимого и остатков на последующих шагах.
1) Под текущим остатком понимается результат полуученый при вычитании делителя из делимого на первом шаге или из предыдущего остатка на последующих шагах.
2) На предварительном шаге делитель совмещается со старшими разрядами делимого ,а затем на каждом шаге сдвигается вправо на одну цифру относительно неподвижного остатка На последнем шаге делитель совмещается с младшими разрядами остатка.
3) Цифры частного вырабатываемые каждом шаге определяются знаком текущего остатка ,для остатка >= 0 цифра частного равна единице ,для остатка < 0 цифра равна нулю.
Особенности реализации деления в ЭВМ.
(по отношению к целым числам)
1) Делимое по сравнению с делителем представляется в удвоенном формате.
2) В качестве результата деления формируется как частное так и остаток .При этом как правило остаток замещает старшие разряды ,а частное младшие.
3) В целях экономии оборудования на каждом шаге осуществляется не сдвиг делителя вправо относительно остатка ,а сдвиг остатка влево относительно неподвижного делителя. При этом делитель совмещается со старшими разрядами делимого ,а далее остатка.
4) При получении отрицательного остатка на каком либо шаге для перехода к следующему шагу требуется восстановление остатка путем сложения с делителем. Подобный метод называется делением с восстановлением остатка .В целях экономии времени деление как правило реализуется в ЭВМ с применением метода без восстановления .В соответствии с этим методом при получении отрицательного остатка он не восстанавливаясь сдвигается влево так же как и положительный однако при этом на следующем шаге производится не вычитание делителя ,а сложение с делителем.
Доказательство:Допустим на i-м шаге получен отрицательный остаток тогда по методу с восстановлением :Ri+1=2(Ri+B)-B
Ri+1 =2Ri +2B-B=2Ri+B
5) При некоторых соотношениях между делимым и делителем может оказаться что частное не помещается в отводимый формат. Подобная ситуация возникает также при делении на 0. Этот особый случай распознается на начальном шаге деления и приводит к прерыванию выполняемой программы по причине ошибки деления.
Деление беззнаковых.
А/В<2^n А-В*2^n<0 из этого неравенства следует что для проверки корректности деления необходимо вычесть делитель из старших разрядов делимого. Если результат вычитания положителен или равен 0 то операция прекращается выходом на прерывание. В остальном беззнаковое деление реализуется по описанным выше принципам так как цифра частного вырабатываемая на каждом шаге деления определяется знаком текущего остатка ,точнее представляет собой инверсию его знакового разряда, целесообразно расширить n-разрядный сумматор дополнительным разрядом для явного представления знака остатка.
Если по завершению всех шагов деления остаток является отрицательным то требуется его восстановление путем сложения с делителем.
Деление знаковых.
IDIV
По аналогии с операцией умножения знаковое деление может быть реализовано одним из двух методов:
1) Метод деления в прямых кодах .
2) Метод деления в дополнительных кодах.
При использовании первого метода отрицательные операнды предварительно преобразуются в прямой код и далее над ними выполняют деление по аналогии с беззнаковым .Знак частного формируется отдельным действием как сумма по модулю два знаков операндов. Знак остатка совпадает со знаком делимого. Исключением из этого правила является нулевой остаток содержащий в знаковом разряде 0.
Отрицательные результаты в конце операции преобразуют из прямого в дополнительный код.
Существенным отличием деления модулей операндов в прямых кодах от беззнакового деления является проверка корректности деления. Действительно модуль n-разрядного знакового числа размещается в (n-1)-разряде в связи с этим условие корректности для деления в прямых кодах имеет вид |A|/|B|<2^(n-1) ; |A|-|B|^(n-1)<0
В соответствии с последним неравенством пробное вычитание модулей с целью проверки корректности должно выполнятся путем совмещения делителя не со старшими разрядами делимого ,а со сдвинутыми на один разряд вправо.
В целях однообразия выполнения пробного вычитания с основным циклом деления в котором делитель совмещен со старшими разрядами остатка делимое предварительно сдвигают на один разряд влево после чего производится пробное вычитание из старших разрядов сдвинутого делимого.
Деление в дополнительных кодах.
Основное отличие этого метода от предыдущих состоит в том, что операнды вступают в операцию в коде своего представления вместе со знаком. Однако при этом возникает ряд нюансов :
Цифры частного, в том числе и знак, формируемые на каждом шаге, определяются не только остатком, но и знаком делителя. При их совпадении цифра частного равна единице, иначе - нулю.
Действие выполняемое над текущим остатком на каждом шаге определяется не только этим остатком, но и знаком делителя. При их совпадении выполняется вычитание делителя из старших разрядов делителя, при не совпадении выполняется сложение делителя со старшими разрядами делителя.
Коррекция остатка производится в конце операции в том случае, если его знак не совпадает со знаком делимого. Эта коррекция осуществляется действием над остатком, аналогичным основному циклу деления.
Коррекция частного выполняется только при отрицательном делимом и нулевом остатке деления и состоит в инкременте (увеличение на единицу) положительного частного и декременте отрицательного.
Проверка корректности деления выполняется также как при делении прямых кодов только в случае положительных операндов.
A>0, B>0 => A/B<2n-1 A-B*2n-1<0
A<0, B<0 => A/B<2n-1 A-B*2n-1>0
A<0 , B>0 => A/Bі-2n-1 A/B>-2n-1 A+B*2n-1+B>0
A>0, B>0 => A/B>-2n-1-1 A+B*2n-1+B<0
При одинаковых знаках операндов для проверки корректности деления необходимо сдвинуть делимое на 1 разряд влево а затем вычесть делитель из его старших разрядов.
Проверка корректности осуществляется сравнением знака первого остатка со знаком делимого. Если они НЕ совпадают деление корректно, в противном случае - не корректно.
При разных знаках пробное вычитание фактически заменяется сложением.
В этом нет ничего необычного, так как для первого шага в качестве остатка для первого шага фигурирует само делимое и его знак не совпадает со знаком делителя в соответствии с действиями для основного цикла над текущим остатком в этом случае необходимо выполнять сложение с остатком.
В связи с тем, что при разных знаках операндов получается отрицательное, имеющее диапазон, больший на единицу, чем положительное, начальные шаги, связанные с проверкой корректности деления содержат такую последовательность действий :
Сложение делимого с делителем, совмещенным с его младшими разрядами. При этом выполняется знаковое расширение делимого на старшие разряды делителя.
Сдвиг полученного остатка на один разряд влево.
Сложение с делителем, совмещенным со старшими разрядами остатка.
Сравнение знака остатка со знаком делимого выполняется также как и для операндов с одинаковыми знаками.
В связи с тем, что при проверке корректности деления используется знак делимого необходимо при схемной реализации предусмотреть его сохранение до конца операции. По результату пробного вычитания формируется старшая цифра частного, интерпретируемая как знак.
Действительно, при корректном делении получается верный знак частного.
Пример : A=-168 B=-14 n=5
A=1101011000 ; B=10010
Выполняемые действия
|
N шага |
обозначения |
A/R (старшие) |
A/C (младшие) |
| 0 |
A ¬ A B R0 |
11010 -10101 10010 ѕѕѕ 00011 sign R0№sign B® |
11000 10000 1000|0 ®® |
|
1 |
¬ R0 B R1 |
+00111 10010 ѕѕѕ 11001 sign R1=sign B |
000|00 000|01 |
|
2 |
¬ R1 B R2 |
+10010 10010 ѕѕѕ 00000 sign R2№sign B® |
00|010 00|010 ®® |
|
3 |
¬ R2 B R3 |
+00000 10010 ѕѕѕ 10010 sign R3=sign B |
0|0100 0|0101 |
|
4 |
¬ R3 B R4 |
-00100 10010 ѕѕѕ 10010 sign R3=sign B |
01010 01011 |
|
псевдо- коррекция |
R4 B R |
-10010 10010 ѕѕѕ 00000 |
|
| коррекция частного |
+01011 1 ѕѕѕ 01100 |
Приведенный пример иллюстрирует ряд дополнительных нюансов деления в дополнительных кодах :
На четвертом шаге при сдвиге остатка произошло искажение его знака. Выполняемое действие над остатком должно определяться его знаком для предыдущего шага (до сдвига). В схемной реализации этот факт необходимо учитывать путем применения модифицированного кода с удвоенным знаковым разрядом. В связи с этим разрядность регистра для хранения остатка и частного должна быть 2n+1, а разрядность сумматора (сумматора вычитателя) n+1. При получении нулевого остатка на коком либо шаге деления для следующего шага остаток будет равен делителю. При его сдвиге влево он станет равен удвоенному делителю. И после вычитания делителя на следующем шаге он снова станет равен делителю. Таким образом в конце операции после выработки всех цифр частного остаток будет не нулевым, а равным делителю. Если при этом его знак совпадает со знаком делимого, то в соответствии с основным алгоритмом деления он не подлежит коррекции.
Для устранения этого недостатка алгоритма во всех случаях совпадения знака остатка и делимого выполняется попытка так называемой псевдокоррекции. Если после этой коррекции остаток равен нулю, то он является истинным, если же остаток не равен нулю, то требуется его восстановление обратным по сравнению с псевдокоррекцией действием с делителем.