В машинах с плаваю щ ей запятой действия осуществляются над числами в нормальной форме. При сложении двоичных чисел, зад ан н ы х в нормальной форме а — 10/;а и b = 10ffp, сн ач ал а вы
равниваются порядки. Если p > q , т. е. р = q + Һ (/г > 0 ), то сл ага ем о е b зам ен яетс я ненормализованным числом Ьх = К У '^, где Зі образован о сдвигом числа (3 на к р азр я д о в в п р а в о * ) . З а тем производится сложение цифровых частей а и (3j по п р а
вилам слож ения двоичных чисел в. м аш инах с ф и кси рован ной запятой. После сложения цифровых частей мож ет о к а заться, что сумма не является нормализованным числом При | а + pi | > 1 появляется нарушение норм али зац ии влево;
при j а —j— pj I < резул ьтат получается с нарушением н орм али зации вправо.
Таким образом, после сложения цифровых частей требуется произвести н орм али зац ию результата.
П ри зн аком нарушения н ормализации вправо (т. е. получе
ния цифровой части суммы, меньшей по абсолютной величине 0,1) явл яется наличие двух одинаковы х цифр 0,0 (для по
л о ж и тел ьны х чисел) или 1,1 ( д л я , отрицательны х чисел
*) Ч исло. совпадает с числом Ь с точностью д о 10/; - я (все цифры зд есь и дальш е, пока не б у д ет особо оговорено, даны в двоичной системе
счислении),:. •
3 8 П Р И Н Ц И П Ы У С Т Р О Й С Т В А Э Л Е К Т Р О Н Н Ы Х В Ы Ч И С Л И Т Е Л Ь Н Ы Х М А Ш И Н [ г л . I
в обратном или дополнительном кодах) в двух соседних р а з р я д ах : в р а з р я д е зн ака и в старшем цифровом разряде.
П р и м е р , а — 1010 • 0,110110 Ь = Ю1» • (— 0,101011)
порядок цифровая часть
обратны й код числа а 0 010 0,110110
обратны й код числа b 0 010 1,010100
10,001010 циклический п еренос
код суммы 0 010 0,001011
П осле нормализации (сдвига влево на два разряда) получим циф ро
вую часть суммы 0,101100. Сумма равна а + b — І010 • Ю -10 • 0,101100 —
= 10°-0,101100.
Д л я определения нарушения нормализации влево (т. е. по
лучения цифровой части суммы, большей по абсолютной в ел и чине, чем единица) применяется так называемый м о д и ф и ц и р о ва н н ы й код, при котором знаки чисел и зображ аю тся д вум я р а з ряд ам и : положительные числа представляются в виде 00, а\ а2 . . . . . . а пч отрицательные — модифицированным дополнительным кодом
[&]доп. м === 100 —)— а или модифицированным обратным кодом
И о б р . „ = 1 0 0 — ( 1 0 ' " ) + а .
ft
Числа, по абсолютной величине меньшие единицы, в м од и фицированном коде имеют в знаковых р азр я д а х либо д ва нуля (00, . . . ) , либо две единицы ( 11, . . . ) . Сложение чисел в м од и ф и цированном дополнительном коде производится так же, как и в обычном дополнительном коде, только отбрасы вается еди ница переноса, возникаю щ ая в старшем знаковом разряде. С л о
ж ение чисел в модифицированном обратном коде производится т а к же, ка к в обычном обратном коде, только циклический пере
нос осущ ествляется из старшего знакового р а з р я д а в младш ий цифровой разряд.
П ри зн аком нарушения нормализации влево при сложении мантисс двух чисел в модифицированном коде будет появление в знаковых р а зр я д а х разных цифр 10 или 01.
П р и м е р 1. о. — 1010 • 0,110110, b = Ю10- 0,010110.
Сумма цифровых частей в модифицированном коде
,
00,110110 00,010110 01,001100О П Е Р А Ц И И Н А Д Ч И С Л А М И В Ц И Ф Р О В Ы Х М А Ш И Н А Х 3 9
Сдвиг на одни разр я д вправо даст нормализованную цифровую часть суммы. Получаем:
д -j-/; = Ю11 -0,100110.
П р и м е р 2. а = Ю 'о(— 0,111011), 6 = 10‘° (— 0,010110).
Сумма цифровых частей в модифицированном дополнительном коде 11,000101
11,101010 10,101111 *
П осле сдвига на один разр я д вправо и занесения в старшин р азряд знака единицы получим нормализованную сум м у цифровых частей в модифициро
ванном «дополнительном коде: 11,010111. С ледовательно, а + /; = 1011 (— 0,1010001).
Вычитание чисел в нормальной форме сводится к ал г е б р а и ческому сложению их обратных или дополнительных кодов, так ж е как и в маш и нах с фиксированной запятой.
3. Умножение и деление. Умножение чисел в маш инах обычно осуществляется в прямом коде. Умножение цифровых частей чисел, задан н ы х в двоичной системе счисления, состоит в по
следовательном сдвиге влево множимого на количество р а з р я дов, равное номерам зн ачащ и х цифр множителя, и сложении полученных частей произведений. З н а к произведения полу
чается сложением зн аков сомножителей па одноразрядном двоичном сум маторе по следующим правилам:
0 + 0 = 0; 1 + 0 = 1 ; 0 + 1 = 1; 1 + 1 = 0 .
ГІ р п м е р.
0,110101 Х 0,101101 110101 110101 110101 110101 0,100101010001
Умножение чисел, зад ан н ы х в нормальной форме, проводится в три этапа:
1. Сложение цифр, и зо б р а ж аю щ и х знаки сомножителей, в результате чего получается знак произведения.
2. Алгебраическое сложение порядков сомножителей, которое д ает порядок произведения.
3. Умножение цифровых частей сомножителей, что д ает ц иф ровую часть произведения.
В случае необходимости производится н ормализация ре
зультата.
4. Деление чисел в машинах с фискированной запятой. Д е л е ние чисел в двоичной системе осущ ествляется последовательным
4 0 П Р И Н Ц И П Ы У С Т Р О Й С Т В А Э Л Е К Т Р О Н Н Ы Х В Ы Ч И С Л И Т Е Л Ь Н Ы Х М А Ш И Н [ Г Л . I
определением цифр частного путем вычитания д ел ител я.
Если при вычитании делителя разность полож ительна, то соот
ветствую щ ая цифра частного равна единице; если разность от
рицательна, то соответствующая цифра частного равна нулю, а предыдущий остаток сдвигается на один р а зр я д влево и т. д.
В озвращ ение к предыдущему остатку происходит путем п р и б а в ления делителя к отрицательному остатку. Этот цикл операций повторяется п раз (п — количество разрядов числа).
П р и м е р. Д ели м ое а — 0,100101, делитель b = 0,110101.
0.1001010 0,110101 ____ І 10Ю1 0,101100
0010101
“ 110101
— 001011 101010
— 110101 0011111
“ 110101
001001
— 110101
— 100011 010010 110101
— 10001“
100100 Ч астное 0,101100,
остаток 0,0000001.
При определении второй, пятой и шестой цифр частного разность полу
чилась отрицательной. При этом сохраняю тся соответственно первый, четвер
тый и пятый остатки, сдвинутые на один разряд влево.
Д елен ие чисел в нормальной форме производится в три этапа:
1. Определение знака частного сложением знаков делимого и д елителя на одноразрядном сумматоре.
2. Вычитание порядков с учетом знаков порядков. В резу л ь тате получается порядок частного.
3 . Д еление цифровой части делимого на цифровую часть де
лителя, что д ает цифровую часть частного.
В случае необходимости производится норм али зац ия резуль
тата.
5. Поразрядные операции. Если операции над цифрами к а ждого р а з р я д а чисел производятся независимо друг от друга, то такие операции назы ваю тся поразрядными. Рассмотрим неко
торые примеры поразрядных операций.
О П Е Р А Ц И И Н А Д Ч И С Л А М И П Ц И Ф Р О В Ы Х М А Ш И Н А Х 4 1
1. П о р а з р я д н о е д о п о л н е и и е. О п ераци я преобразует набор а 0а ха 2 . . . а п в набор а'0а[ . . . а ' , где а'к = 1 — а к (к —
= О, 1, 2, п). В м аш и нах с фиксированной запятой т ак ая операция п рев р ащ а ет число а, зад ан н ое обратным кодом, в число —а, задан н ое тем же-кодом, так как [а]обр + | д | = 1,1 . . . 1 = 1 0 — (2-«).
Таким образом, при зад ан и и чисел в машине с фиксирован
ной запятой в обратном коде операция изменения зн а к а я в ляется операцией поразрядного дополнения.
2. П о р а з р я д н о е с л о ж е н и е . П о р а зр я д н о е сложение явл яется сложением цифр по модулю 2:
0 + 0 = 0; 0 + 1 = 1 + 0= 1; 1 + 1= 0.
С помощью операции поразрядного слож ения можно осуще
ствить п оразрядное дополнение числа, слож ив его с числом, имеющим во всех р а з р я д а х цифру 1.
3. П о р а з р я д н о е л о г и ч е с к о е с л о ж е н и е . Л огич е
ское сложение двоичных цифр определяется таблицей, приве
денной на стр. 20.
П ользуясь этой операцией, молено получить из числа, з а д а н ного’ прямым кодом, его отрицательный модуль путем слож е
ния этого числа с кодом 1,00 . . . 0.
4. П о р а з р я д н о е л о г и ч е с к о е у м н о ж е н и е. Л огиче
ское умножение двоичных цифр определяется таблицей, приве
денной па стр. 19). Эта операция позволяет из набора а0а х ... а п выбрать любые его разря ды . Д л я этого нужно зад ан н ы й набор умножить на набор, в котором в соответствующих р азря да х стоят 1, а в остальных р а зр я д а х —0 . Таким образом выясняется
•знак числа, абсолю тная величина п орядка числа или цифровой его части, код операции или код какого-либо адреса. Эта опе
рация мож ет быть использована д л я выделения той пли другой части кода.
5. С д в и г . О пераци я сдвига зак л ю ч ается в смещении цифр кода и на фиксированное число разрядов влево или вправо.
Сдвиг кода а0а х . . . а п на s разрядов влево зам ен яет его на код
#s-*-ia s-H2 • * •
ап
0 ••• 0 . Сдвиг на 5 разр я д о в вправо д аст кодS
0 . . . 0 а0а 1 . . . a n_s.
S
В маш и нах с п лаваю щ ей запятой существует операция сдвига цифровой части числа. О п ерация сдвига в маш инах с фиксированной запятой эквивален тн а умножению или д е л е нию без округления на 2 к.
6. Операция сравнения. Эта операция выясняет, какое из двух чисел а и Ь больше (м еньше). Д л я сравнения двух чисел а и Ь производится вычитание а — Ь, и по зн аку разности
4 2 П Р И Н Ц И П Ы У С Т Р О Й С Т В А Э Л Е К Т Р О Н Н Ы Х В Ы Ч И С Л И Т Е Л Ь Н Ы Х М А Ш И Н [ г л . I
определяется, какое из этих чисел больше. Случай равенства а и Ь воспринимается по разности в зависимости от того, какой кол применяется д ля представления чисел. При д ополн и тель
ном коде нуль имеет один зн ак плюс и, следовательно, зн а к равен ства воспринимается как неравенство а > Ь. При о б р а т ном коде вычитание равных чисел дает отрицательный нуль
[— 01обР= 1,11 . . . 1
и, следовательно, знак равенства воспринимается как н ер ав ен ство а < Ь.
7. Точность производства операций и округление р езу л ь тата . Точность выполнения операций над числами в машине о п ред е
л яется видом операции и способом ее реализации.
1. О п е р а ц и я с д в и г а . Выполнение этой операции соот
ветствует умножению на 2/v>. При допустимом сдвиге влево не происходит потери значащих цифр. Такой сдвиг есть точная опе
рация умножения на 2'1, где к — положительное число. При сдвиге вправо на р разрядов последние р значащ их цифр те ряются. В результате операции сдвига вправо по сравнению с точным делением на 2Р появляется ошибка, меньш ая ед и ницы последнего разряда.
Н а и б о л ь ш а я ошибка, равная двоичному числу 10"" (1 — ІСГ7').
произойдет при наличии единиц во всех р отбрасы ваем ы х р а з рядах. В соответствии с этим в машинах с плаваю щ ей запятой при нормализации числа с цифровой частью, большей 1 по а б солютной величине, соверш ается ошибка, пе п рев осход ящ ая единицы последнего р азр я д а цифровой части числа.
2. С л о ж е н и е и в ы ч и т а н и е . В машинах с ф и кси ров ан ной запятой операции сложения и вычитания являю тся точными.
При сложении и вычитании чисел в машинах с плаваю щ ей з а п я той возникают сдвиги для выравнивания порядков и н о р м а л и зации результатов, которые создают ошибки. В ы равнивание по
рядков д ает ошибку, меньшую единицы последнего зн ака , однако после нормализации влево ошибка может превратиться д а ж е в единицу первого знака. Действительно, пусть п = 6 , а = 10 11 * 0 , 100000, b — 1010 • 0, 111111. При вычитании в ы равн и ваются порядки: b\ = 1011 - 0,011111 и а — Ь — 10'1 • 0,000001 —
= 10-10 • 0 , 100000. Точное значение разности есть 10-10 *0 ,01.
Такое положение мож ет возникнуть при условии, если по
рядки отличаются на единицу. Такой рост ошибки исключается при наличии в сумматоре дополнительного разря д а , т. е. если число цифровых разрядов сум матора на единицу больше, чем цифровых разрядов в ячейках ЗУ (запоминающ его устройства).
В самом деле, если порядки чисел отличаются больше чем на
П Е Р Е В О Д И З О Д Н О Й С И С Т Е М Ы С Ч И С Л Е Н И Я В Д Р У Г У Ю 4 3
единицу, то при н орм ал и зац ии резул ьтата мож ет происходить сдвиг влево лиш ь на один разр я д , что д ает ошибку, меньшую единицы последнего разря д а . Н о р м а л и за ц и я р езул ьтата больше чем на один р а з р я д мож ет произойти только при условии, что порядки слагаем ы х отличаются не больше чем на единицу.
Но в этом случае наличие дополнительного р а з р я д а в су м м а
торе обеспечивает сохранение всех цифр и, следовательно, точ
ность результата.
3. У м н о ж с н и е и д е л е и и е. При умножении и делении чисел в машине ош ибка не превосходит единицы младш его р а з ряда.
Д л я уменьшения ошибок при производстве операций над чис
л ам и в машине вводятся операции с округлением, для чего используется дополнительный р а зр я д на сумматоре.
При производстве операций н ад числами с округлением ошибка, как правило, не превосходит половины единицы младшего р азр я д а . Кроме того, при выполнении последующих операций с округлением в озм ож н а компенсация ошибок.
§ 6. Перевод из одной системы счисления в другую При преобразовании чисел из десятичной системы в двоич
ную, а та к ж е из двоичной — в десятичную в качестве пром еж у
точного этапа применяется запись в двоично-десятичной си
стеме. В двоично-десятичной системе к а ж д а я цифра десятичной записи задается в двоичной системе. Ц ифры 0 , 1, 2, 3 , . . . , 9 з а
писываются в виде двоичных четырехзначных чисел 0000, 0001, 0010, . . 1001. Двоично-десятичная система мепее экономна, чем двоичная, т а к как четыре двоичных р а з р я д а используются всего лиш ь для записи 10 цифр (вместо 16 в о зм о ж н ы х ); запись числа в двоично-десятичной системе па 20% длиннее чисто двоичной его записи. Н апример, число 637 в двоичпо-десятичиой системе имеет вид 0110 0011 0111 (12 цифр), а в двоичной записи 1001111101 (10 ц иф р).
П
Чтобы найти двоичную запись числа а = 2 а,. • 10"'- *, к а ж д а я
Ar 1
циф ра которого ак з а д а н а в виде четверки двоичных цифр:
а к= я 1і1я1.2*і{з‘хы U 2, . . . , я ) ,н у ж н о последовательно выделять четверки цифр числа а (т. е. коэффициенты а !{) и производить
т
вычисление многочлена 2 a kt m~k при t = 10 (в двоичной сн- к 1
стсме / = 1010).
Рассмотрим теперь п реобразование двоичного числа в д е с я тичное. Пусть а — 0 , «1 а 2 . . . а п — д воичная запись числа (ак = 0
4 4 П Р И Н Ц И П Ы У С Т Р О Й С Т В А Э Л Е К Т Р О Н Н Ы Х В Ы Ч И С Л И Т Е Л Ь Н Ы Х М А Ш И Н [гл. I или 1, k = 1, 2 , . . п ). Ц ифры д л я десятичной записи
т
а = к =- 1
находим последовательно по такой схеме:
1) вычисляем целую часть числа 10а а, = [10а];
2) вычисляем дробную часть числа 10а
т
ьх = { 1 0 л } = 2 а * Ю " * ; к ~ 2 3) вычисляем целую часть числа 10 6]
«2 = 110^1
и т. д. И так, последовательность цифр а ь а.2, ■ ■ о.т десятичной зап и си числа а находится по следующей схеме:
«* = [10^*], Ьк = { 10Ьк_ г}, b0 = a (к = 1, 2 , . . ., ,//).
Д л я преобразования двоичного числа, заданного в н о р м а л ь ной форме а = 10/Jg, в десятичную систему счисления ц и ф ров а я часть преобразуется в десятичную систему по предыдущ ему п р а вилу и определяется порядок числа s в десятичной системе из условия 10л > а 105-1.
Г Л Л В Л II
ПРИ НЦИ П Ы ПРОГРАММНОГО УП РАВЛ ЕНИ Я НА ЦИФРОВЫХ АВТОМАТИЧЕСКИХ МАШИНАХ В сяк ая вычислительная машина с точки зрения математика представляет собой устройство, способное выполнять некоторый набор арифметических и логических операций, хранить и в ы д а
вать сведения о р езул ь тата х этих операций.
В зависимости от того, может ли маш ина выполнять лишь определенную последовательность операций, обеспечивающую решение некоторого специального круга зад ач , или эти последо
вательности операций, а значит, и задачи, реш аем ы е на машине, могут быть самыми различными, цифровые электронные машины разделяю тся па два типа: специализированные и универсальные.
В этой главе мы изложим основы программного (автом ати ческого) решения за д а ч на универсальных электронных м а шинах.
§ 1. Принципиальная схема Ц А М
1. Общие принципы построения. К ак у ж е отмечалось,