Xreferat.com » Рефераты по математике » Конспект лекций по дискретной математике

Конспект лекций по дискретной математике

23 22 0

sign

характеристика

мантисса

В качестве основания порядка S=2. Смещенный порядок (характеристика) занимает 8 разрядов, величина смещения равна весу старшего разряда смещения. В мантиссе используется скрытый разряд.

0ЈxaЈ255

-128ЈPaЈ127

-1ЈMaHЈ1

IEEE

КФ (КВ) 31 30 23 22 0

sign

характеристика

мантисса

ДФ (ДВ) 63 62 52 51 0

sign

характеристика

мантисса

РФ (РВ) 79 78 64 63 0

sign

характеристика

мантисса

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


КФ: d=27-1=127; ДФ: d=210-1=1023; РФ: d=214-1=16383


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

Максимальное значение характеристики, представленное всеми единицами при положительном знаке зарезервированно для представления значения +Ґ (нулевая мантисса) и представление так называемых “не чисел” (NAN). Максимальное значение характеристики используется для преставления -Ґ,¤, (неопределенность) в старшем разряде единица, в остальных - ноль.

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

КФ:

1ЈxaЈ254

-126ЈPaЈ127

1ЈMaHЈ2


ДФ: 10-308<|Ап.з.|<10308

РФ: 10-4932<|Ап.з.|<104932


Точность представления чисел


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


Абсолютная погрешность: А=А-А*, где А - точное значение

А* - машинное представление

А - знаковая величина

Относительная погрешность:

, иногда


Погрешность двоичной дроби


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


правильная дробь:

(n-разрядная)

1 1 1 …


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



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

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

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

Точность представления для коротких форматов в ЭВМ различных типов


ЕС ЭВМ



СМ ЭВМ



IEEE



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


Методы округления чисел с плавающей запятой


Используются для увеличения точности представления чисел и применяются в тех случаях, когда результат операции представленный в ДФ или РФ переписывается из сопроцессора или FPU в память в более коротком формате. Методы округления в РС оговариваются международным стандартом IEEE-754(854). К ним относятся:

  1. Округление усечением (разряды не вмещающиеся в формат отбрасываются)

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

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

  4. Округление к ближайшему меньшему (к -Ґ) (для положительных -мантисса не меняется; для отрицательных чисел - к ней добавляется единица).

Использование любого метода округления, исключая округление усечением, позволяет уменьшить максимальную относительную погрешность до значения . При этом максимальная относительная погрешность мантиссы становится равной весу старшего из отбрсываемых разрядов. По умолчанию используется метод округления к ближайшему. Методы округления (к -Ґ) и (к +Ґ) используются в “интервальной” арифметике для определения границ полученных результатов в смысле их точности.

Принципы выполнения арифметических операций в ЭВМ.

Основы двоичной арифметики.

Операция сложения целых чисел.


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

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

Для беззнаковых чисел переполнение фиксируется при возникновении переноса из старшего разряда .Этот перенос в процессорах 80Х86 фиксируется во флаге CF-carry flag.

Для знаковых чисел фиксация фиксируется во флаге OF-overflow flag.

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

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

Примеры сложения: n=6

-32<=Aз<=31

0<=Aб<=63

A+B=C

A= -11 1.10101

B= -20 +1.01100

----------

C= -31 1.00001

зн. беззн.

A=11 0.01011 11 11

B=-20 1.01100 -20 44

-----------

C= -9 1.10111 -9 55(55)


Переполнение при знаковом сложении и способы его фиксации.

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

зн. беззн.

A=17 0.10001 17 17

B=19 0.10011 19 19

----------

C= 1.00100 -28? 36(36)

зн. беззн.

A= -17 1.01111 -17 47

B= -19 1.01101 -19 45

-----------

C= 0.11100 28? 28?(92)

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

1) Сравнением знаков операндов и результата (при наличии ++ или - - знаков операндов и - или + соответственно в знаке результата фиксируется переполнение).

2) Сравнение переносов из двух старших разрядов (при наличии одного и только одного переноса фиксируется переполнение).Именно этот способ используется в процессорах корпорации INTEL для установки флага OF.


Операция вычитания целых чисел.


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

1) Сведением к сложению путем предварительного изменения знака второго операнда. При использовании дополнительного кода изменение знака предполагает операцию дополнения над ним ,то есть invert,+1.

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

Таблица истинности одноразрядного двоичного вычитателя имеет вид:

ai bi zi-1 ri zi

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 0 1

a i - i-й разряд уменьшаемого.

b i - i-й разряд вычитаемого.

z i-1 - заем из предыдущего разряда.

z i - заем в последующий разряд.

Примеры: n=6

зн. беззн.

A= -13 1.10011 -13 51

B= -28 1.00100 -28 36

-----------

C= 0.01111 15(15) 15(15)


A= -28 1.00100 -28 36

B= -13 1.10011 -13 51

-----------

C= 1.10001 -15(-15) 49?

Для беззнакового вычитания результат не корректный .Факт получения не корректного числа объясняется вычитанием из меньшего большего то есть результат должен быть отрицательным. О факте получения отрицательного беззнакового результата свидетельствует заем в старший разряд .Этот заем при выполнении вычитания фиксируется во флаге CF. Если от полученного результата взять дополнение то получается правильный результат равный 15. В связи с этим при наличии заема в старший разряд полученный результат можно интерпретировать как беззнаковый дополнительный код.


Переполнение при вычитании и способы его фиксации.


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

Пример: n=6

зн. беззн.

A= -13 1.10011 -13 51

B= 24 0.11000 24 24

----------

C= 0.11011 27(-37) 27(27)


A= 24 0.10011 24 24

B= -13 1.10011 -13 51

-----------

C= 1.00101 -27? 37?


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

1) Анализ знаков операндов и результата. Если знаки операндов разные и знак результата отличен от знака первого операнда то фиксируется переполнение.

2) Сравнение заемов в два старших разряда. Если один и только один из заемов имеет место то фиксируется переполнение. При наличии обоих заемов или их отсутствии результат вычитания является корректным.

В процессорах INTEL реализован второй способ в соответствии с которым осуществляется установка флага OF.


Сложение и вычитание чисел с плавающей запятой.


Пример:

А=0,527103 Pa=3

B=0,923102 Pb=2 B=0,0923103

C=Ma+Mb=0.6193103

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

1) Сравнение порядков.

2) Выравнивание порядков.

3) Сложение мантисс.

4) Нормализация результата.

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

1) Сравнение порядков реализуется по средством вычитания. При этом в целях однозначности принято из Ра вычитать Рb при использовании смещенных порядков осуществляется вычитание характеристики как беззнаковых целых чисел. Естественно что разность характеристик имеет тоже значение что и разность порядков если при вычитании характеристик имеет место заем в старший разряд то результат вычитания отрицательный и представлен в дополнительном беззнаковом коде. Для второго этапа необходимо его преобразование в прямой код.

2) Этот этап опускается при равенстве порядков операндов то есть если: Xa-Xb=0

При выполнении этого этапа всегда операнд с меньшим порядком приводится к большему порядку. Это реализуется сдвигом мантиссы вправо на количество разрядов равное |Xa-Xb| .В данной трактовке понятие разряда зависит от основания порядка. Для ЕС ЭВМ при |Xa-Xb|=2 мантисса сдвигается на 2-а шестнадцатеричных разряда то есть на 8 двоичных. При сдвиге мантиссы операнда с меньшим порядком происходит потеря ее младших разрядов ,что приводит к уменьшению точности в общем случае.

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

При большом модуле разности порядков может оказаться что мантисса с меньшим порядком полностью выйдет за пределы формата. Этот факт можно учесть для ускорения выполнения операций следующим образом на первом этапе |Xa-Xb| сравнивается с числом разрядов мантиссы и если он оказывается больше то операция завершается путем присвоения результату значения операнда с большим порядком.

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

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

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

Для каждого из трех способов

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: