Лекции

Пример. Получить машинное представление в 32-х разрядной сетке числа 350,001. 350,00110 = 101011110,0000000001000012. Приводим к стандартному виду полученное двоичное число: 1,01011110000000000100001∙(102)1000, q' = 11111112+10002 = 100001112.

Мантисса m = 01011110000000000100001. Знак числа положителен, поэтому s = 0. Окон-

чательно получаем: 01000011101011110000000000100001 или 43AF0021.

Обратную задачу получения десятичного числа из чисел, представленных в стандарте IEEE 754, решает следующая формула:

Если применить эту формулу для вычисления минимального и максимального числа представленного в IEEE 754, то получим следующие результаты:

00 00 00 00h = 5,87747175411144·10-39 (минимальное положительное число)

7f ff ff ffh = 6,80564693277058·1038 (максимальное положительное число)

80 00 00 00h =-5,87747175411144·10-39 (максимальное отрицательное число)

ff ff ff ff h = -6,80564693277058·1038 (минимальное отрицательное число)

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

1.Число 00000000h считается числом +0. Число 80000000h считается числом -0.

2.Число 800000h считается числом +∞. Число 800000h считается числом -∞.

3.Числа FF(1xxx)XXXXXh не считается числами (NAN), кроме случая п.2. Числа 7F(1xxx)XXXXXh не считается числами (NAN), кроме случая п.2. Число представленное в битах с 0...22 могут быть любым числом кроме 0.

4.(x000)(0000)(0xxx)XXXXXh считаются денормализованными числами, за исключением чисел п. 1.

Стандарт IEEE 754 широко применяется в технике и программировании, несмотря на это, он подвергается эмоциональной и вполне справедливой критике из-за ряда сущест-

венных недостатков (см. напр. http://www.yur.ru/science/computer/IEEE754.htm).

2.4. Кодирование чисел. Операция алгебраического сложения.

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

прямой код (ПК);

обратный код (ОК);

дополнительный код (ДК).

двоично-десятичный код (BCD или код «8421»).

Простейшим двоичным машинным кодом является прямой код X П К получаемый при

кодировании в числе X только знаковой информации, причем знак + кодируется нулем, а знак – единицей. Если под поле цифр разрядов выделено больше, чем это необходимо для представления числа X, то разряды (цифры) числа X заносятся в разрядную сетку ЭВМ в соответствии со своими весами. Код знака числа практически во всех ЭВМ заносится в старший разряд разрядной сетки. Например, прямой код двоичных чисел

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

1.Сравнить знаки слагаемых.

2.Сравнить слагаемые по модулю при неравенстве их знаков.

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

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

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

Обратный код X О К , также как и в прямой код, для обозначения знака положитель-

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

два действия:

1.Сложение кодов, включая знаковый разряд.

2.Прибавление переноса к младшему значащему разряду суммы. Пример 1: Вычислить выражение -3(10) -2(10).

Прямой код Обратный код

Пример 2: Вычислить 7(10) -3(10).

Работа с обратным кодом вызывает ряд трудностей. В частности, также как и в прямом коде возникают два нуля: +0 и –0, т.е. в прямом коде (в котором представлены положительные числа) имеет место (+0) = 000...0, а в обратном коде (в котором представлены отрицательные числа): (–0) = 111...1.

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

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

Использование ДК для представления отрицательных чисел устраняет двусмысленное представление нулевого результата, так как –0 исчезает.

В общем случае использованием дополнительного кода для записи отрицательных чисел можно перекрыть диапазон десятичных чисел от –2k-1 до +2k-1–1, где k – число используемых двоичных разрядов, включая знаковый. Так, с помощью одного байта можно представить десятичные числа от 128 до +127, либо только положительные числа от 0 до 255 (здесь под положительными числами понимаются числа без знака).

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

Пример: Число –44(10) = 10101100 (2) перевести в дополнительный код и обратно.

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

Алгоритм сложения в дополнительном коде включает в себя два действия:

1.Сложение кодов, включая знаковый разряд.

2.Отбрасывание переноса при его возникновении. Пример: Вычислить алгебраическую сумму 58 - 23.

При суммировании есть перенос в знаковый разряд суммы, а перенос из знакового разряда отсутствует, т.е. имеет место положительное переполнение. Формальный результат равен –4.

Пример 4: Алгебраическое суммирование с одним переносом. (Отрицательное переполнение).

0перенос

Число -5 нельзя представить 3-битовой комбинацией. Формальный результат равен +3. Для обнаружения переполнения разрядной сетки можно использовать модифицированные коды. Модифицированные коды отличаются от обычных кодов тем, что знак числа кодируется двумя разрядами. Знак «+» в этих кодах кодируется двумя нулевыми знаковыми разрядами, а знак «-» – двумя единичными разрядами. При выполнении алгебраического сложения или вычитания два знаковых разряда участвуют в операции как равноправные цифровые разряды. После выполнения операции содержимое знаковых разрядов определяет знак результата (левый знаковый разряд) и наличие переполнения (несовпадение знаковых разрядов): комбинация 01 фиксирует переполнение при сложении положительных чисел (положительное переполнение), а 10 – отрицательных (отрицательное переполнение).

[A] МДК +[B] МДК = 10,101

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

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

Для преодоления этого пользуются простым и оригинальным приемом: предварительно в двоичную ПСС переводят не все число, а поразрядно все его цифры – в результате получается некоторый смешанный двоично-десятичный код десятичного числа (BCD, Binary Coded Decimals). Можно отметить, что двоично-десятичное представление чисел используется и в тех случаях, когда предъявляются повышенные требования к точности вычислений.

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

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

9 8, 31 0 1 0 0 1 1 0 0 0 , 0 0 1 1 B C D .

Для некоторых типов ЭВМ в АЛУ имеются специальные блоки десятичной арифметики, выполняющие операции над числами в двоично-десятичном коде. Это позволяет в ряде случаев существенно повышать производительность ЭВМ. Эта система при представлении каждой тетрады имеет веса разрядов равные 8,4,2,1. Поэтому код BCD иногда обозначают как код «8421».

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

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

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

Pобщ. Далее можно общий множитель вынести за скобки и провести сложение мантисс:

X 1 X 2 2 Pо б щ ( m1 m 2' ).

Очевидно, при конечной длине поля цифр мантиссы Робщ необходимо выбирать из условия Робщ = max{P1,P2}, так как в противном случае произойдет переполнение разрядной сетки. В ЭВМ определен следующий порядок выполнения операции сложения чисел, представленных в форме с плавающей запятой:

1.Вычитание порядков складываемых чисел. Если разность порядков равна нулю (порядки равны), то перейти к пункту 3. Если порядки не равны, то осуществить выравнивание порядков (пункт 2).

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

3.Сложение мантисс. Если не произошло переполнения разрядной сетки мантиссы и сумма получена в нормализованном виде, то вычисления закончить. Сумма мантисс является мантиссой суммы чисел, а порядок суммы чисел равен порядку большего числа (или общему порядку). В противном случае перейти к пункту 4.

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

2.5.Выполнение операций умножения и деления в ЭВМ.

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

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

Пусть нам нужно перемножить два целых числа (напомним, что в большинстве случаев они хранятся в ЭВМ как правильные дроби): X 0 , x1 x 2 ...x m 1 x m , Y 0 , y1 y 2 ... y n 1 y n . Тогда

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

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

0 X y n 2 n X y n 1 2 n + 1 X y 1 2 1 0 X y n 2 1 X y n 1 2 1 X y 1 2 1

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

3) Умножение со старших разрядов со сдвигом частичных сумм влево.

X Y = 0 , x1 x 2 x m y 1 2 1 y 2 2 2 y n 2 n X ( y 1 2 n 1 y 2 2 n 2 y n ) 2 n( X y 1 2 n 1 X y 2 2 n 2 X y n ) 2 n 0 X y 1 2 X y 2 2 X y n ) 2 n

4) Умножение со старших разрядов со сдвигом частичных произведений вправо.

X Y = 0, x1 x 2 x m y 1 2 1 y 2 2 2 y n 2 n 0 X y 1 2 1 X y 2 2 2 X y n 2 n

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

1.Значению суммы присваивается ноль. Начиная с младшей цифры множителя:

2.Аанализируется цифра множителя. Если она равна единице, то множимое участвует в формировании части произведения. В противном случае – не участвует.

3.К сумме прибавляют множимое. Полученная (частичная) сумма сдвигается вправо на один разряд.

4.Операции по пунктам 2 и 3 выполняются до старшего разряда.

Конечно, за рамками рассмотрения остаются вопросы переполнения разрядной сетки (в общем случае для размещения произведения нужно m+n разрядов), возможные варианты ускорения алгоритмов и ряд других очень важных вопросов. И естественно, указанными алгоритмами не исчерпывается весь список применяемых на сегодня алгоритмов умножения целых чисел в ЭВМ.

Алгоритм умножения чисел, представленных в форме с плавающей запятой, определяется следующим соотношением: ( X 1 2 P1 m 1 ) ( X 2 2 P2 m 2 ) ( m 1 m 2 ) 2 P1 P2 . При реализации

операции умножения над числами с плавающей запятой в ЭВМ выделяют следующие этапы:

1.определение знака произведения путем сложения по модулю два знаков мантисс операндов;

2.перемножение модулей мантисс по правилам умножения дробных чисел с фиксированной запятой;

3.определение порядка произведения путем алгебраического сложения порядков сомножителей;

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

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

Пример: Вычислить 1100,011(2)/10,01(2).

-1100011 10010

10010 101,1

-11011 10010

-10010

10010

0

Здесь после каждого вычитания делитель сдвигается вправо по отношению к делимому. Если остаток после вычитания получился положительный, в разряд частного записывается 1, если отрицательный – 0.

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

( X 1 2 P1 m 1 ) : ( X 2 2 P2 m 2 ) ( m 1 : m 2 ) 2 P1 P2 .

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

3. ЛОГИЧЕСКИЕ И СХЕМОТЕХНИЧЕСКИЕ ОСНОВЫ ЭВМ

3.1. Двоичные переменные и переключательные функции.

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

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

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

Любая логическая схема, принимая на входе некоторый n-разрядный двоичный код, формирует на выходе какой-то m-разрядный двоичный код. Для того чтобы описать поведение этой схемы, необходимо определить зависимость каждой из выходных переменных от входного двоичного кода. Эта зависимость выходных переменных представляет собой функцию алгебры логики.

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

Двоичные переменные – это переменные, которые могут принимать два значения: 0 и 1. Они называются также логическими или булевыми переменными и обозначаются символами х0,x1,х2,..., хn-1.

Логические функции (ЛФ) зависят от двоичных переменных. Они, как и аргументы, могут принимать лишь два значения: 0 или 1. ЛФ называют также булевыми или переключательными функциями. Будем обозначать ЛФ в виде f(х0,x1,х2,…, хn-1) указывая в скобках аргументы. ЛФ в свою очередь могут служить аргументами еще более сложных логических функций. Следовательно, можно построить ЛФ любой заранее заданной сложности, пользуясь ограниченным числом логических связей.

Различают несколько способов задания ЛФ, основными из которых являются: словес-

ный, табличный, аналитический, с помощью карт Карно.

Словесный способ предполагает задание функции ее описанием.

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

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

быть равна 0 или 1. Если число аргументов ЛФ равно n, то существует 2n различных сочетаний этих переменных.

Пример: Таблица 4.1.1 представляет собой таблицу истинности для ЛФ f1 и f2, зависящих от двоичных переменных х0, x1, х2. Так как n=3, то таблица содержит 8 строк, соответствующих 23 = 8 наборам переменных х0, x1, х2. Для каждого набора в таблице записаны значения ЛФ f1 и f2, равные 0 или 1.

Табл. 4.1.1 Пример табличного задания ЛФ

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

Пример:

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

Рис. 4.1.2 Пример задания ЛФ картами Карно

3.2. Логические элементы.

Логический элемент в электронных схемах – это устройство, реализующее ту или иную логическую функцию. Для изображения логических элементов всегда используются условные графические обозначения, описывающие только выполняемую элементами функцию. В настоящее время в мире существует несколько общепринятых стандартов условных обозначений. Наиболее распространенными являются американский стандарт MILSPEC 806В и стандарт МЭК 117-15А, созданный международной электротехнической комиссией. Часто в литературе используются обозначения в европейской системе DIN