Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Дубинин Н.М. Организация ЭВМ и Систем - файл Глава 1.doc


Загрузка...
Дубинин Н.М. Организация ЭВМ и Систем
скачать (1177.9 kb.)

Доступные файлы (9):

Введение.doc24kb.10.03.2003 23:05скачать
Глава 1.doc439kb.27.11.2003 21:23скачать
Глава 2.doc868kb.27.11.2003 21:30скачать
Глава 3.doc1403kb.28.11.2003 12:28скачать
Глава 4.doc384kb.04.11.2003 20:36скачать
Глава 5.doc959kb.27.11.2003 21:52скачать
МАИ (серый).wmf
Оглавление.doc45kb.04.11.2003 20:41скачать
Титульный.doc62kb.28.11.2003 12:27скачать

Глава 1.doc

  1   2
Реклама MarketGid:
Загрузка...
Глава I. Организация вычислений в ЭВМ
1. Позиционные системы счисления
Способ представления чисел посредством знаков называется системой счисления (СС). Для кодирования информации в ЭВМ используются позиционные СС, в которых значение любого символа (цифры) определяется его позицией или расположением в представлении числа. Любое действительное число можно представить в позиционной системе счисления в виде степенного ряда
Х = (x m km + xm-1km-1 + + x1k1 + x0k0 + x-1k-1 + + x-n k-n),
где kоснование системы счисления (k  2, целое положительное число); xi – цифры (xi  {0, 1, …, k-1}); i – номер позиции (разряд) числа, ki – вес цифры. Так как в вычислениях часто используется одинаковое основание, то оно не присутствует в записи числа, а число без весовых коэффициентов ki представляется в виде
X = xmxm-1 x1x0, x-1 x-n ,
где целая часть числа отделяется от дробной запятой. С целью упрощения записи числа в нем опускают запятую для целых чисел и индексы i, определяющие вес цифры в представлении числа. Для того чтобы отличить числа различных СС, их в конце помечают цифрами или символами основания, например, 506(8), 506,Аh – числа восьмеричной и шестнадцатеричной систем счисления.

Определим диапазон представления числа в (m+n+1)- разрядной сетке. Для этого вычислим максимальное число без знака, которое можно разместить в этой сетке в k-й СС. Подставляя в разряды наибольшую цифру в представлении числа в виде степенного ряда, получим
Xmax =.
В данном выражении есть сумма членов геометрической прогрессии, которая равна значению
.
Подставляя это значение в выражение Xmax, получим
Xmax = km+1k-n,
где (m+1) – число разрядов целой части числа без знака, а n – дробной. Тогда с учетом знака диапазон представления чисел X будет определяться выражением
- (km+1k-n)  X  + (km+1k-n).
В этом диапазоне может быть размещено наименьшее отличное от нуля число без знака

Xmin = k-n.
Число различных цифр, которое можно разместить в (m+n+1)-разрядной сетке без знака, включая и нуль, можно определить из выражения
.
Для представления М различных цифр в k-й СС потребуется следующее число разрядов

L =] log k M [,
где скобки   указывают на округление до большего целого.

Затраты оборудования (число элементов) для представления любого (m+n+1)-разрядного числа без знака в k-й СС могут быть определены по формуле

Nk = k (m+n+1).
Подставляя вместо (m+n+1) значение, определенное путем логарифмирования выражения для М, получим
Nk = k log k M.
Для определения наилучшей СС для ЭВМ по затратам оборудования воспользуемся функцией F = Nk / N2, вид которой показан на рис. 1.1.

Можно показать, что минимальные затраты оборудования при непрерывном k будут соответствовать системе с основанием е  2,72 натурального логарифма и F = N3 / N2 = 0,946.

Рис. 1.1. Зависимость затрат оборудования в k-й СС
Таким образом, для ЭВМ оптимальной СС по затратам оборудования является троичная, а затем, чуть хуже, двоичная. Учитывая то, что многие ал­горитмы арифметических операций в двоичной СС выполняются проще, чем в троичной, и намного быстрее и удобней запоминать и передавать цифры 1,0 (вклю­чено, выключено), вся информация в ЭВМ кодируется, преобразуется и запоминается в двоичной СС. Кроме двоичной СС из-за кратности оснований ис­пользуются также восьмеричная и шестнадцатеричная СС, цифры и символы которых кодируются двоичными эквивалентами.

Для обозначения цифр восьмеричной СС 0, 1, …, 7 пользуются двоичными кодами: <000>, <001>, …, <111>. Цифры и символы шестнадцатеричной СС 0, 1, …, 9, А(10), B(11), C(12), D(13), E(14), F(15) кодируются тетрадами: <0000>, <0001>, …, <1001>, <1010>, <1011>, <1100>, <1101>, <1110>, <1111> с использованием всех комбинации в тетраде нулей и единиц с весами <23, 22, 21, 20>, т.е. код <8, 4, 2, 1>.

Так, если в тетраде имеется код <1011>, то легко определить цифру 16 СС путем сложения значащих весовых коэффициентов <123 + 022 + 121 + 120>(2) = 11(10) = В(16) = Bh.
^ 2. Алгоритмы перевода чисел из одной системы счисления в другую
Наиболее общий алгоритм перевода числа X(k1) с основанием k1 в число X(k2) с основанием k2 выполняется в следующей последовательности:

- число X(k1) представляют в виде степенного ряда;

- заменяют цифры хi с основанием k1 их k2-ми представлениями;

- выполняют все операции сложения, умножения, возведение в степень в k2-й СС;

- с учетом точности определяют число целых и дробных цифр в числе X(k2), округляют и представляют по необходимости X(k2) в виде степенного ряда.

Рассмотрим общий алгоритм перевода чисел на примере числа ^ X(2)= 1001,101, которое переведем в Х(10) .

1001,101 = 123 + 022 + 021 + 120 + 12-1 + 02-2 + 12-3 =

=8 +1 + 1/2 + 1/8 = 9,625(10) .

Однако применение этого алгоритма в случае k1 > k2 связано с громоздкими вычислениями, например, Х(10) = 36 переведем в Х(2) .

36(10) = 3101 + 6100 = (0011)(1010)1 + (0110)(1010)0 = 100100(2) .

Поэтому для перевода числа из 10 СС в 2 СС при k1 > k2 целую и дробную часть переводят отдельно по упрощенным алгоритмам. Для перевода це­лой части числа X(k1) отделяют у него целую часть Хц (k1) и делят его на основание k2 в k1-ой СС. В результате деления получают остаток О0 и ча­стное Ч1. Если частное Ч1k2, его делят вновь Ч1/k2. Получают остаток О1 и частное Ч2. Деление частного продолжают до тех пор, пока на i-ом шаге не будет получен остаток Оi-1 и частное Чi < k2. Последнее частное прини­мается за цифру хi, а цифры xi-1, …, x0 определяются соответствующими остатками Оi-1, …, О1, О0. Располагая цифры в порядке Чi Оi-1 … О0, полу­чают целую часть числа Х(k2).

Для определения дробной части числа Х(k2) берут дробную часть Хд (k1) числа Х(k1) и умножают ее на основание k2 по правилам k1 СС. В результате первого умножения получают целую часть произведения Ц1 и дробную часть D1. На втором шаге вновь берут дробную часть 0, D1 и умножают на основание k2. Умножение дробных частей продолжают до n-го шага Цn, Dn, пока не будет достигнута необходимая точность представления дроби. Приравнивая x-i = Цi получают значение дроби Хд (k2) =, x-1 x-2x-n. Рассмотрим алгоритм раздельного перевода целой и дробной части числа на примере. Пусть Х(10) = 20,4 необходимо перевести в двоичную СС. То­гда процесс перевода числа можно показать как деление (слева) и умножение (справа) по шагам:


1)




20

2
















20

10 = Ч1







0,4  2 = 0,8 (Ц 1 = 0);







О0 = 0













2)

10/2 = 5 (Ч2 = 5, О1 = 0)




0,8  2 = 1,6 (Ц 2 = 1);

3)

5/2 = 2 (Ч3 = 2, О2 = 1)




0,6  2 = 1,2 (Ц 3 = 1);

4)

2/2 = 1 (Ч4 = 1, О3 = 0)




0,2  2 = 0,4 (Ц 4 = 0).


При переводе дробной части числа 20,4 умножение может быть продол­жено на любое число шагов, т. к. величину 0,4(10) нельзя точно представить в 2 СС. Ограничиваясь числом шагов, получим

Хц (k2)= х4 х3 х2 х1 х0, = Ч4 О3 О2 О1 О0, = 10100,

Хд (k2)=, х -1 х -2 х -3 х -4 =, Ц 1 Ц 2 Ц 3 Ц 4 =, 0110 …

20,4(10)  10100,0110(2)

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


123,02(4) =

1

2

3,

0

2(4)

= 11011,001 (2)

01

10

11,

00

10(2)






















621,34(8) =

6

2

1,

3

4

= 110010001,0111(2)

110

010

001,

011

100






















9Е,1D(16) =

9

E,

1

D




= 10011110,00011101(2).

1001

1110,

0001

1101





При переводе из двоичной СС в четверичную, восьмеричную, шестнадцатеричную СС цифры двоичной системы соответ­ственно объединяются в группы по две, три, четыре цифры слева и справа от запятой, а затем эти группы заменяются на эквивалентные цифры четверичной, восьмеричной, шестнадцатеричной СС. Например, число 1101101011,11(2) будет преобразовано


3

1

2

2

3,

3

= 31223,3(4);

11

01

10

10

11,

11






















1

5

5

3,

6




= 1553,6(8);

001

101

101

011,

110

























3

6

В,

С

0




= 36В,С(16).

0011

0110

1011,

1100

0000





^ 3. Формы представления чисел в двоичной системе счисления
В ЭВМ используют две формы представления чисел: с фиксирован­ной (“естественная форма”) или с плавающей (“полулогарифмическая форма”) запятой. При представлении чисел с фиксированной запятой положение запятой устанавливается для всех чисел или перед старшим, или после младшего разряда и остается неизменным, т.е. фиксируется. Для кодирования знака числа S используется старший разряд. Нуль в этом разряде соответствует плюсу, а единица - минусу. В остальных разрядах числа располагается мантисса М, сдвинутая таким образом (умноженная на коэффициент фиксации 2 P), что она будет либо целая, либо дробная для всех чисел в зависимости от положения запятой. Если запятую зафиксировать после младшего разряда, то все числа программист считает целыми, разрядная сетка имеет вид


2m

2m-1

2m-2




21

20




S

xm-1

xm-2

. . .

x1

x0

.


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


63

62




1

0










. . .







.


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

Современные процессоры фирмы Intel ориентированы на систему арифметических команд для работы с фиксиро­ванной запятой после младшего разряда для m+1 = 8/16/32/64. Увеличение разрядности чисел с 8 до 64 бит способствует по­вышению точности и диапазона представления чисел новых типов ЭВМ. Пусть m+1 = 64, тогда целые числа без знака могут быть представлены от нуля до 264-1 (все единицы в разрядной сетке). С учетом знака число Х целое может лежать в диапазоне

- (263-1)  Х  (263-1).

Все числа  Х  1 и Х  263, а также результаты вычислений не могут быть представлены в принятой разрядной сетке и способствуют появле­нию особых случаев и прерываний в вычислениях. Для исключения подобных случаев осуществляют масштабирование массива чисел, т.е. ум­ножают все числа (или часть) на соответствующий коэффициент фиксации. Например, требуется числа Х1 = - 10101,1111 и Х2 = + 101,111110 разместить в разрядной сетке 8 бит с фиксированной запятой со знаком как целые. Тогда определяют наибольшее число  Хi; его масштабируют (сдвигают) 2P таким образом, чтобы наибольшее число значащих старших цифр разместилось в разрядной сетке; младшие цифры, которые не размещаются в разрядной сетке, отбрасывают или иногда используют для округления; все другие числа умножают на полученный коэффициент фиксации и разме­щают в соответствующие разряды.

Так как Х1  Х2, то используем Х1 для определения коэффициента фиксации Х1 = 1.1010111,2-2. Заметим, что в Х1 за знаком располагается единица и что точка, отделяющая знак числа от мантиссы, не включается в разрядную сетку ЭВМ. Тогда число Х1 будет представлено с наибольшей точностью в виде

1101 0111,

где слева старший разряд, а справа младший. С учетом знака и коэффициента фиксации 2-2 число ^ Х2 будет представлено как 00010111. Причем младшие цифры 11 в Х1 и 1110 в Х2 невозможно разместить в этой разряд­ной сетке. Они отброшены, и точность представления этих чисел уменьшается.

Если использовать масштабный коэффициент 2+5, то числа Х1 и Х2 будут представлены в ЭВМ как дробные с фиксированной запятой перед старшим разрядом 1101 0111(Х1), 0001 0111 (Х2). Запятая в них предполагается слева после знака, старшая цифра имеет вес 2-1, младшая - 2-7.

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

Для повышения точности и диапазона представления чисел в ЭВМ используется форма с плавающей запятой вида

Х = 2P М, 1/2   М  1,

где М – нормализованная мантисса числа, 2P – характеристика числа Х, р –порядок, 2 – основание.

В этой форме порядок представлен целым числом р со знаком (Sp), ман­тисса – правильная дробь, т.е. представлена с фиксированной запятой перед старшим разрядом со знаком (S). Так как мантисса нормали­зована 1/2  М  1, старшая цифра мантиссы числа всегда равна 1, и любое число размещается в разрядной сетке ЭВМ с наибольшей возможной точностью.

Так число

^ Х1 = - 2+5  0,1010111110…0.

Тогда в разрядной сетке Х1(2) будет представлено с плавающей запятой значениями порядка и мантиссы со знаками в виде


Sp

p

S

M

0

0 … 0101

1

1 0 1 0 1 1 1 1 1 0 … 0

m

0



-1 -n


Для упрощения действий над порядками их сводят к микрооперациям над целыми положительными числами путем искусственного смещения значения р на величину +pmax.­ Смещенный порядок определяется по формуле

E = p +  pmax.

В смещенном порядке знак отсутствует. Для представления Е необходимо столько же разрядов, как и для представления модуля порядка и знака. Так, если порядок будет занимать один байт в числе, то 7 разрядов в обычном представлении в нем отводится под модуль порядка, и pmax = 27-1. Теперь, прибавляя к любому порядку число pmax (+127), получим смещенный поря­док. Например, если p = + 5, то E(10) = 5 + 127 = 132. Размещая Е(2) без знака, получим представление смещенного порядка 1000 0100 в разрядной сетке 1 байт. Смещенный порядок 0…0 соответствует наибольшему отрицатель­ному порядку, а 1…1 - наибольшему положительному порядку. Величина E = pmax указывает на нулевой порядок. Смещенный порядок намного упро­щает операции сравнения и сдвига чисел.

Если при сложении мантисс появляется цифра с весом 20, то есть ман­тисса вида 1, …, то считается, что произошло левое нарушение нормализации числа, когда  М  1. А если в микрооперациях получена мантисса  М  1/2, то это соответствует правому нарушению нормализации числа, ко­гда в старшем разряде мантиссы с весом 2-1 появляется нуль.

Учитывая, что нормализованная мантисса всегда содержит 1 в стар­шем разряде, часто мантиссу сдвигают на один разряд влево, увеличивая точность представления числа включением в разрядную сетку еще одного младшего разряда мантиссы. Единица с весом 2-1 сдвигается в разряд с весом 20, однако в разрядной сетке ОЗУ она не размещается и восстанавливается только в регистрах сопроцессора. Если представить число Х1 в формате с одинарной точностью (ОТ), где под порядок отводится байт, оно будет иметь вид


Наибольшее отличное от нуля по модулю число, которое может быть представлено в фор­мате ОТ, будет равно Xmax = 2+127  (1 - 2-23), а наименьшее Xmin = 2-127  1/2 = 2-128. В зависимости от целей программирования в ЭВМ используются различные форматы данных.
^ 4. Операции сложения чисел в прямом, обратном и дополнительном кодах с фиксированной запятой
Для выполнения арифметических операций над двоичными числами в ЭВМ могут использоваться прямой, обратный или дополнительный код. Прямой код Хпр числа Х = хm xm-1... x0 x-1 x-n с учетом знака S можно опре­делить из выражения

[Х]пр = S.X.

Если в ЭВМ модуль числа представлен с фиксированной запятой, то Хпр или целое, или дробное. Так, число Х = 1101101,11 в прямом коде может иметь два вида: как целое или дробное (с масштабным коэффициентом 2+7) в разрядной сетке 1 байт 0.1101101 или 1.1101101 (число отрицательное). В зависимости от масштабного коэффициента и разрядности сетки часть разрядов мантиссы любого числа может теряться. Нуль в прямом коде допускается двух видов: 0.0...0 или 1.0...0. В прямом коде легко выполнять операции ввода чисел, умножения и сложения с одинаковыми знаками сла­гаемых. Однако операции вычитание и деление без изменения схемы сумматора проще реализуются с использованием обратных [Х]0 или до­полнительных [X]Д кодов. Обратный и дополнительный коды можно получить по формулам


пр

пр
и ,

где m и n -номера позиций старшего и младшего разряда. В зависимости от положения запятой, если числа целые, то n = 0, а если дробные, то m = 0.

Из формул получения [Х]0 и [Х]Д видно, что прямой, обратный и дополни­тельный коды положительного числа совпадают. Обратный код отрицательного числа можно получить путем инверсии разрядов ман­тиссы



так как равенство подтверждается сложением

.

Отсюда справедливо также равенство


пр
.

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


Д
.

Справедливо также равенство


Д

Д

пр
.

Представим числа Х1 = +125(10), Х2 = -5,5(10) с фиксированной запятой после младшего разряда в разрядной сетке 1 байт в двоичной СС в прямом, обратном и дополнительном кодах:


пр

Д
;


пр
.


Д
.

Сложим числа Х1 иХ2 в 2СС с фиксированной запятой в прямом (а), обрат­ном (б) и дополнительном (в) кодах:

а)




+

.1111101




б)

+

0.1111101




в)




+

0.1111101










.0000101







1.1111010










1.1111011







1



.0000010










0.1110111







1



0.1111000

























1








































0.1111000




















Из примеров сложения видно, что при сложении чисел в прямом, обрат­ном и дополнительном коде результат получается в этих кодах. В прямом коде числа складываются без знака (в примере +125+5), если знаки раз­ные, то опе­рация не выполняется, наличие переноса в знаковый разряд (пример (а)) указывает на переполнение разрядной сетки. В об­ратном и дополнитель­ном кодах числа складываются со знаками. Перенос из знакового разряда в дополнительном коде отбрасывается, а в обратном коде распространяется в сторону младшего разряда (цепь циклического переноса).

Недостатком обратного кода является двоякое представление нуля 0.0... 0 и 1.1... 1, а также увеличение времени сложения за счет распространения циклического переноса. В дополнительном коде нуль представлен только 0.0... 0, отсутствует циклический перенос и корректировка резуль­тата сложения заключается в простом отбрасы­вании переноса из знакового разряда. Однако для получения дополнительного кода отрицательного числа требуется не только ин­вертирование разрядов числа, которое заме­няется в АЛУ передачей с обратных выходов триггеров регистра, но и прибавление единицы к младшему разряду в сумматоре. Недостатком сложения в обратном и дополнительном кодах является трудность опреде­ления переполне­ния разрядной сетки (ПП), которое определяется вычислением функции

ПП,

где x3,y3,z3 - знаки слагаемых и результата соответственно. Знаки слагаемых x3,y3 могут стираться после выполнения операции в одно- или двухадресных командах. Для устранения этого недостатка при сложении чисел с одинаковыми знаками могут использоваться модифицированные обратный и дополнительный коды. В них для представления числа используют два одинаковых знаковых раз­ряда 00.(+) или 11.(-). Если после сложения по тем же правилам в знаковых разрядах окажется 00. или 11., то результат правильный, соответственно, положительный или отрицательный, а если 10. или 01., то необходимо фиксировать переполнение разрядной сетки. Эти результаты при сложе­нии в модифицированном дополнительном коде можно пояснить примерами





00.111110













11.110011










00.000111













00.100010










01.000101

(ПП)




1



00.010101

(нет ПП).






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


4.1. Операция умножения чисел с фиксированной запятой в прямых кодах
Ч
пр

пр

пр

пр
аще всего для исключения потери старших разрядов из-за переполне­ния разрядной сетки умножение выполняют в прямых кодах с числами, представленными с фиксированной запятой перед старшим разрядом (с отрицательными индексами). Для чисел [Х]пр = x3. x-1,...,x-n, [Y]пр = y3. y-1, ..., y-n ([Х]пр , [Y]пр <1) требуется получить произведение

[
пр

пр

пр
Z]пр = [Х]п р[Y]пр = z3. z-1 , z-2, ... z-n.

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

Операция выполняется в два этапа. Отдельно определяется знак произведения z3 с учетом знаков сомножителей x3 и y3 в соответствии с выражением:

z3 = x3 y3.

Затем определяется цифровая часть произведения мантисс сомножителей. С этой целью процесс умножения можно представить в следующем виде

Z = ХY = Х (y1 2-1 + y2 2-2 + ...+ y(n-1) 2-n+1+ y(n) 2-n) =

(1).

= Х 2-1 y1 + Х 2-2 y2 + ... + Х 2-n+1 y(n-1) + X 2-n y(n).

Это выражение после преобразования можно представить в виде:

Z = ((...(( 0 + Xy(n) ) 2-1 + Xy(n-1) ) 2-1 +... + Xy2) 2-1 + Xy1) 2-1

(2).

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

Согласно выражению (2) при умножении с младших разрядов должна выполняться следующая последовательность микроопераций:

    - анализируется младшая цифра множителя. Если yn = 1, то множимое Х участвует в формировании цифровой части произведения; если yn = 0, то Х не участвует в формировании произведения;

    - полученное первое частичное произведение, равное 0+Xyn, сдвигается на один разряд вправо, то есть умножается на 2-1. Указанная последовательность действий справедлива при умножении на все последующие разряды. Так, при умножении на разряд y(n-1):

    - анализируется цифра множителя yn-1. Если yn-1 = 1, то множимое прибавляется к сдвинутому первому частичному произведению, т.е. A2 = (0 + Xyn) 2-1 + X1. Если yn-1=0, то множимое не участвует в формировании произведения, т.е.

A2 = (0 + Xyn)·2-1 + X0.

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

A(i) = A(i-1) · 2-1 + y(n+1-i) · Х

(3).

Для выполнения умножения необходимо повторить n тактов (i=1,2,..,n) в соответствии с формулой (3) и в заключение осуществить последний n-й сдвиг A(n)2-1 = XY = Z. Отметим, что при перемножении n-разрядных чисел получается 2n-разрядное произведение (n старших разрядов и n младших). При этом получение только n старших разрядов произведения или всех 2n разрядов обеспечивается суммированием в n-разрядном сумматоре. Время умножения равно:

Тх = (tSM+ tСД) · n, где tSM - время суммирования; tСД - время сдвига.

Согласно выражению (1) умножение со старших разрядов множителя должно выполняться в следующей последовательности:

    - множимое сдвигается на 1 разряд вправо, т.е. ^ X·2-1;

    - анализируется старшая цифра множителя y1. Если y1 = 1, то X·2-1 участвует в формировании произведения, при y1 = 0, X·2-1 - не участвует в формировании произведения.

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

    - производится второй сдвиг множимого, т.е. (^ X·2-1)·2-1;

    - анализируется значение y2 и осуществляется или не осуществляется передача X·2-1 на суммирование.

Процесс умножения повторяется до просмотра всех y(i), i = 1,2,...,n.
^

4.2. Умножение чисел в дополнительных кодах



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

    - если Х>0 и Y>0, то поскольку [Х>0]Д = Х, [Y>0]Д = Y, специфика выполнения умножения здесь не проявляется (см. гл.I. п.4.1);

    - если Х<0, а Y>0, то [Х<0]Д = 2+Х и [Х]Д [Y]Д = 2Y + ХY – получается так называемое псевдопроизведение, и для того чтобы получить правильный результат [ХY<0]Д = 2+ХY, необходимо к псевдопроизведению прибавить 2 и вычесть 2Y;

    - если Х>0, Y<0, то [Х]Д [Y]Д = 2Х+ХY, и здесь необходима поправка, равная +2 и -2Х;

    - если Х<0 и Y<0, то [Х]Д [Y]Д = (2+Х)(2+Y), а правильный результат ХY, и необходима поправка - 4 - 2Х - 2Y.

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

    - если y(n+1-i) = y(n-i), то производится лишь сдвиг частичного произведения A(i-1)·2-1;

    - если y(n-i) = 0, а y(n+1-i) = 1, то к A(i-1)·2-1 прибавляется [Х]Д;

    - если y(n-i) = 1, а y(n+1-i) = 0, то из A(i-1)·2-1 вычитается [Х]Д или к A(i-1)·2-1 прибавляется [-(Х)Д]Д со сменой знака X.

Для этого алгоритма справедлива следующая рекуррентная формула

A(i) = A(i-1)·2-1 + [(у(n+1-i)-у(n-i))·(Х)]Д.

При этом операция состоит из n+1 такта для i=1,...,n+1. Другими словами, умножение производится и на знаковый разряд множителя y0. После умножения на последнем шаге получаем A(n+1) = [Х]Д [Y]Д = [Z]Д и сдвиг A(n+1) не производится.

Рассмотренная методика применима и к умножению со старших разрядов множителя со сдвигом множимого вправо. Алгоритм выполнения операции имеет следующий вид:

[Х]Д [Y]Д = (у1-у0) [Х]Д + (у2-у1) [Х]Д ·2-1 + ...

+ (уn-уn-1) [Х]Д ·2-n+1 + (уn+1-уn) [Х]Д ·2-n.


Умножим в дополнительном двоичном коде десятичные числа -5 и -6 с фиксированной запятой перед старшим разрядом:

[-5]пр=1.0101, [-5]д=1.1011 (∙2+4,число дробное),

[-6]пр=1.0110, [-6]д=1.1010 (множитель y0. y1 y2 y3 y4∙2+4).

Берем дополнительный разряд множителя y5=0 и вычисляем разность двух старших разрядов множителя на очередном шаге умножения при сдвиге влево с выполнением следующих микроопераций (м/о):

  1. y1-y0=0, (A(0)=0)∙2-1

  2. y2-y1=-1, A(1) +0.ХПР∙2-1

  3. y3-y2=+1, A(2)+[-Х]Д∙2-2

  4. y4-y3=-1, A(3)+(0.ХПР )∙2-3

  5. y5-y4=0, [Z]Д = (A(4)+0)

С учетом сдвига множителя влево и сумм частичных произведений A(i) влево, и с учетом сдвига Х∙2-1 множимого вправо 1.1011 на каждом шаге умножения имеем:


Ш

а

г

Со сдвигом A(i) вправо




Со сдвигом Х вправо

ХПР

0.010100000

ХПР

0.010100000

[-Х]Д

1.101100000

[-Х]Д

1.101100000

м/о

Сумматор

м/о

Сумматор

1

(A(0)=0)∙2-1

0.000000000

(A(0)=0)+0

0.000000000

2

SM+0.ХПР

0.010100000

SM+(0.Хп)∙2-1

0.001010000

A(1)∙2-1

0.001010000




3

+[-Х]Д

1.101100000

+[-Х]Д∙2-2

1.111011000

SM+[-Х]Д

1.110110000

SM+[-Х]Д∙2-2

0.000101000

[A(2)]Д∙2-1

1.111011000




Ш

а

г

Со сдвигом A(i) вправо




Со сдвигом Х вправо

+(0.Хпр)∙2-3

0.000010100

SM+(0.Хпр)∙2-3

0.000111100

4

+0.Хпр

0.010100000




SM+0.Хп

0.001111000

[Z]Д=A(4)+0

0.000111100

A(3)∙2-1

0.000111100

5

[Z]Д=A(4)+0

0.000111100


Для проверки правильности вычислений умножим полученный результат 0.000111100 на коэффициент 2+8 , получим +11110,0 = + (1∙24 + 1∙23 + 1∙22 + 1∙21) = + (16 + 8 + 4 + 2) = + 30. Заметим, что операция умножения со сдвигом сумм частичных произведений выполняется медленнее, чем со сдвигом множимого, так как микрооперации суммирования и сдвига не могут выполнятся одновременно в сумматоре.

^

4.3. Операция умножения над обратными кодами сомножителей



Рассмотрим умножение с младших разрядов с анализом знаков сомножителей:

    - если Х>0 и Y>0, то здесь используется обычная методика,

    - если Х<0 и Y>0, то в данном случае:

    A(i) = A(i-1)∙2-1 + [Х<0]0у(n+1-i),

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

- если Х>0, а Y<0 ,то необходимо осуществить передачу [-0, x1, ..., xn]0 = 1,... в сумматор, если y(i) = 0. При y(i) = 1 передача множимого не производится. При этом y(i) – цифры обратного кода отрицательного множителя;

    - если Х<0 и Y<0, то при yi = 0 осуществляется передача не исходного кода [Х<0]0 = 1, , а положительного кода множимого 0,x1...xn, который получается с помощью логической операции отрицания; при y(i) = 1 передача множимого не осуществляется. Произведение в этом случае получается положительным.

Данную методику можно распространить и на умножение со старших разрядов обратных кодов. Преимущество умножения чисел в дополнительных и обратных кодах заключается в том, что знак и цифровая часть произведения получаются за один этап, состоящий из (n+1) тактов сдвига и сложения.
^ 4.4. Умножение на два разряда одновременно
Для сокращения времени, затрачиваемого ЭВМ на умножение, часто используют способ обработки двух разрядов множителя одновременно. При умножении прямых кодов чисел с младших разрядов этот способ предполагает рассмотрение всех комбинаций кодов множителя в двух разрядах: 00,01,10,11. Код 00 – нет передачи множимого, код 01 – одна передача множимого, код 10 – также одна «косая» передача множимого со сдвигом (X∙2+1). Код 11 можно образовать из кодов 100 и -01, так как 100 01=11. Т.е. при умножении на код 11 можно осуществлять передачу множимого в соответствии с кодом -01 (т.е. вычитать множимое), но при умножении на следующую пару необходимо к коду пары разрядов множителя прибавить единицу.
4.5. Деление чисел с фиксированной запятой перед старшим разрядом
Операция деления в двоичной системе счисления может быть записана в виде

Z=X/Y=z3.z-1z-2...z-m; z3, zi{0,1}.

При делении делимого Х на делитель Y получается частное Z и остаток O, который может быть равен нулю или некоторому числу в зависимости от значений Х и Y и числа шагов деления. Различают деление со сдвигом остатка или со сдвигом делителя. При делении n-разрядных чисел по любому из этих способов на первом шаге выполняют пробное вычитание (сложение в обратных или дополнительных кодах с положительным знаком делимого и отрицательным знаком делителя)

X-Y=O1 при X,Y 0.

В результате пробного вычитания получают остаток

O0 = O3. O-1 O-2 … O-(n-1)

со знаком О3 в старшем разряде. Если знак положителен О3=0, то первая цифра частного с весом 20 равна единице z0=1, т.е. |Z|1, и частное не может быть представлено дробью (с фиксированной запятой перед старшим разрядом). Следовательно, |X||Y|. Выдается сигнал переполнения разрядной сетки (ПП=1) и деление прекращается. При О3=1, z0=0 деление продолжают до получения остатка, равного нулю в любом коде, или до получения необходимого числа m цифр частного (обычно m=n). При делении со сдвигом остатка дальнейшие шаги выполняются по формуле



При делении со сдвигом делителя



Очередная цифра частного по любому из способов деления определяется по правилу



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

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

Частное в конце деления получается в прямом коде, поэтому если на k-м шаге Ok=0, то деление прекращают и z-k,...,z-m=0.

Например, если X=0.1001, Y=1.1100 представлены в прямом коде, а вычитание осуществляется в дополнительном коде, тогда




0.1001

[X]Д+[-Y]Д

+1.0100




1.1101

После пробного вычитания остаток 1.1101 отрицателен и, следовательно, в частном отсутствует целая часть, то есть z0=0.

Так как остаток отрицателен О3=1, то на следующем шаге к сдвинутому остатку прибавляют делитель (или прибавляют по другому способу сдвинутый делитель, как показано на примере справа).

1.1010

(O02+1)

1.1101




+0.1100




+ 0.0110

(Y2-1)

0.0110

(O1)

0.0011

(O1)

Остаток получен положительный (z-1=1) и не равный нулю. Деление продолжают

0.1100

(O12+1)

0.0011




+1.0100




+1.1101

([-Y2-2]Д)

0.0000

(O2)

0.0000

(O2)

Так как знак остатка положителен, то z-2=1, а весь остаток равен нулю, то приравнивая z-3=z-4=0, деление прекращают.

Знак частного определяется как zз=xз  yз и в приведенном примере zз=0  1=1. В результате деления получается частное Z=0.1001 / 1.1100=1.1100 отрицательное, дробное. Если X и Y, например, имели коэффициент фиксации равным нулю, то результат деления можно проверить, представив числа в десятичной системе счисления

X=; Y=; Z=.

  1   2



Скачать файл (1177.9 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru