Основы информатики_Савельев А.Я_Учебник_2001
.pdf'. /. формальные правила двоичной арифметики
Рассмотрим формальные правила выполнения арифметических опера ций сложения и вычитания на уровне разрядов операндов.
На ocFioBe правил двоичной арифметики можно записать правила сло жения двоичных цифр так, как показано втаблице 4.1, где й,, i, — разряды операндов А и В соответственно; с, — разряд суммы; п, — перенос из дан
ного разряда в соседний старший. |
|
|
|
|
|
|
|
|
|||||
Двоичный |
полусумматор |
— устройство, выполняющее арифметические |
|||||||||||
действия по правилам, указанным в таблице 4.1. |
|
|
|
|
|
||||||||
|
|
|
абл и ца 4.1 |
|
|
|
|
1 аб л и ца 4.2 |
|||||
«, |
|
ь, |
с, |
t i, |
|
|
|
а. |
*, |
II,_i |
с, |
п, |
|
0 |
|
0 |
0 |
0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
|
1 |
I |
0 |
|
|
|
0 |
I |
0 |
1 |
0 |
|
1 |
|
() |
1 |
0 |
|
|
|
1 |
0 |
0 |
I |
0 |
|
1 |
|
1 |
0 |
1 |
|
|
|
I |
I |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
0 |
I |
1 |
0 |
I |
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
I |
|
|
|
|
|
|
|
|
|
1 |
I |
I |
1 |
1 |
|
ИояЕикчгие СДИПИЕ1Ы переноса при сложении двух разрядов |
несколько |
||||||||||||
H3Mciiflet правила сложения двоичных цифр (табл. 4.2). |
|
|
|
||||||||||
Обобщая вьпиеизложепное, можно сформу;гировать правила поразряд |
|||||||||||||
ных действий при сложении 01терандов А и В: |
|
|
|
|
|
||||||||
|
|
|
|
а, + Ь, + п,_| = с, + п,, |
|
|
|
|
(4.3) |
||||
где п^ , — [теренос нз ( i - 1 )-го |
разряда; |
п, — |
перенос |
в (( + 1)-й |
разряд |
||||||||
(переносы принимают значения О или I). |
|
|
|
|
|
|
|||||||
Двоичный |
сумматор |
— |
устройство, |
выполняющее |
арифметические |
||||||||
действия |
гю |
правилам, указанным в таблице 4.2. Условные обозначения |
|||||||||||
двоичных |
[юяусумматоров и сумма |
Ix. и$ |
|
|
|
|
|
||||||
торов показаны |
на рис. 4.1, а и б со |
S |
|
|
SM |
s |
|||||||
ответственно. |
|
|
|
|
|
ii. |
|
|
|
StL |
|
|
|
На |
основе |
гтравил |
двоичной |
|
р |
|
|
p |
|||||
|
|
f |
|
||||||||||
арифметики можно записать правила |
|
|
|
|
|
|
|
||||||
вычитания двоичных цифр так, как |
|
|
|
|
|
|
|
||||||
гтоказаио |
на таблице 4.3, где |
z,^, |
— |
|
Рис. 4.1. Условное обозначение |
||||||||
заем в сгаршем разряде.
4 Алгоритмы выполнения операций на двоичных сумматорах
|
|
Т а б л и ц а 4 3 |
|
|
|
Т а б л и ц а 4.4 |
||
а, |
*, |
с, |
z,^, |
(7, |
ь, |
Z, |
с, |
Z,,, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
i l |
- 1 |
0 |
1 |
0 |
1 |
- 1 |
|
|
|
|
0 |
0 |
- 1 |
1 |
- 1 |
|
|
|
|
1 |
0 |
- 1 |
0 |
() |
|
|
|
|
|
||||
|
|
|
|
0 |
1 |
- 1 |
0 |
- 1 |
Заем равносилен вычитанию единицы из старшего разряда. С учетом единицы заема из старшего соседнего разряда правила вычитания двоич ных цифр можно записать так, как показано в таблице 4.4 (чтобы отличить заем ог переноса, перед единицей iiocTaBjteH знак минус).
Если А — уменьшаемое (1-й операнд), В — вычитаемое (2-й операнд), то для поразряд1Гых действий
а, -Ь, +2, =с, +2,^1 . |
(4.4) |
Двоичный вычитатель — устройство, выполняющее арифметическое действие по правилам, указанным в таблице 4.4.
С точки зрения технической реализации всегда irponie сложить дна электрических сигнала, чем вычесть их друг из друга.
В машине «Иллиак» был использован вычитатель кодов и метод избыТОЧ1ЮГО кодирования чисел. При этом любой разряд числа 11редстав;гяегся
двумя битами, один из которых является знаковым |
.(,, а другой — знача |
||
щим а,. |
|
|
|
Таблица кодирования выпгядит следуюндим образом (таб;г. 4.5). |
|||
|
|
Т а б л и ц а |
4 5 |
Значение |
Кодирование |
|
|
разряда |
5, |
а, |
|
|
|
||
+0 |
0 |
0 |
|
+ 1 |
0 |
1 |
|
- 0 |
1 |
0 |
|
- 1 |
1 |
\ |
|
Вместо сложения используется операция вычитания (условное обозна чение вычитателя показано на рис. 4.2).
4 2 Сложение чисел на двоичных сумматорах
|
На рис. 4.2 условно обозначены; s,, |
а, — знаковый |
|
, |
. i |
||||
|
|
- |
|
|
и |
|
''ЫЧ |
||
и значащий разряды уменьшаемого соответственно; о, — |
|
t |
• Т |
||||||
двоичный разряд вычитаемого; |
|
|
|
N£G |
SB |
|
|||
п,, п,,, — нераспростра- ~ j — |
|
|
|||||||
нягощийся перенос; NEO — управление дополнением |
с^; |
J!L- |
|
|
|||||
G |
— управление цепями переноса; г,, с, — знаковый и |
|
|Zi |
|
|||||
значащий разряды результата (разности). |
|
|
|
|
|||||
|
|
|
|
|
|||||
|
При этом |
|
|
|
|
|
Рис. 4.2. Ус- |
||
|
|
г, = п |
Ф yVfiG, с- = п |
ф а ф 6„ |
1 |
|
'""»""= "*""""- |
||
|
|
' |
! ^ ' ^ ' ' |
,^"i^<^ |
{ |
( 4 5 ) |
чение вычита- |
||
|
п,_| = (sa, V a,h, }G, п, = (^..^.а.^ v а„|*,^, )G.J |
' |
|
теля |
|||||
|
Символ Ф |
принят для обозначения |
поразрядного сложения по моду |
||||||
лю 2 (см. § 2.3). |
|
|
|
|
|
|
|
||
|
Результач всегда получается в избыточной форме, т. е. С' |
=^ А' - В , где |
|||||||
С\ |
А' |
- избы точное представление. |
|
|
|
|
|
||
|
Тогда операцию сложения можно осуществить путем инверсирования |
||||||||
числа А' |
и снятия результата при NEG = I, т. е. |
|
|
|
|
||||
|
|
|
С" =-(-А' |
-В). |
|
|
|
|
|
В rloлaвJrяlou^eм большинстве ЭВМ основное устройство — двоич1п,ги HjHi десятичный сумматор, в зависимости от принятой системы счислений.
4.2.Сложение чисел, представленных в форме
сфиксированной запятой, на двоичных сумматорах
Рассмотрим HecKOJtbKO видов двоичных сумматоров.
Лвоичиый сумматор прямого кода (ДСПК) — сумматор, в котором от сутствует цети, тюразрядпого переноса между старшим цифровым и знаковьтм разрядами (рис. 4.3, а). На ДСПК можно складывать только числа, имеющие одинаковые знаки, т. е. такой сумматор не может выполнять операцито алгебраического с;южения. В самом деле, пусть заданы операнды
|
['iU=Sg^a^a^...a„, |
[В]„^= Sgsb,bj...b„, |
тде %,,, Л)?„ |
соответственно |
содержимое знаковых разрядов изобра |
жений для А и В (символ происходит от английского слова sign — знак); U,, Л, — ттифровьте разряды изображений.
93
4 Алгоритмы выполнения операций на двоичных сумматорах
Если Sg^ =Sgfi, то сумма чисел будет иметь знак любого из слагае мых, а цифровая часть результата получится после сложения цифровых частей операндов.
Пример 4.1. Сложить числа |
А- 0,1011, |
S = 0,0!00 |
на сумма-горе ггрямоЕо кола |
|
Р е ш е н и е . |
|
|
|
|
|
Mlnp - 0,1011 |
1 = 0 . |
||
|
[ Д | „ , = 0.0100 |
, |
= 0 . |
|
|
[С)„, =0.1111 * , . |
|
= 0 . |
|
Отеет- [Г|„, =0.1111. |
|
|
|
|
Пример 4.2. Сложить числа |
А - -0,0101, |
В = -0,100! насуммаюре ггрямою коуш |
||
Р е ш е н и е . |
|
|
|
|
[Л1„р= 1,0101; |
Sg^=\ |
|
.0101 |
|
|Я)„р =1.1<'01,- |
Sg„=\ |
|
.1001 |
|
Ответ. (Г),,, = 1.1110
При сложении чисел на ДСПК возможен случай, когда абсолготпое значение суммы операндов превышает единицу. Тогда имеет месю пере
— HS iJ |
|
полнение |
разрядной ceiKH |
автомата. |
||
ISs. |
Признак |
переполнения — |
наличие |
|||
/7. |
rti,. |
единицы переноса из старшего разря |
||||
да цифровой части сумматора. В этом |
||||||
|
|
|||||
|
|
случае должен вырабатываться cni- |
||||
iJ |
\К |
нал переполнения <р = 1, по коюрому |
||||
происходит |
автоматический |
ocianoB |
||||
*7 |
|
машины |
и |
корректировка |
масштаб |
|
|
|
ных коэффициентов с таким расче |
||||
|
-'^рм' 14 |
том, чтобы избежать появления пере |
||||
<к. |
полнения. |
|
|
|
||
Двоичный сумматор |
дополни |
|||||
|
а |
тельного кода (ДСДК) — сумматор, |
||||
|
оперирующий изображениями чисел в |
|||||
дополнительном коде. Харакгерная особенность ДСДК — наличие цени поразрядного переноса из оаршего
разряда цифровой части в знаковый разряд (рис. 4.3, б). Определим правила сложения чисел на ДСДК.
94
4 2 Сло.жеиие чисел на двоичных сумматорах
Теорема. Сумма дополнительных кодов чисел есть дополни тельный код результата.
Доказательство. Предположим, что числа представлены в фор ме с фиксированной запятой, стоящей перед старшим разрядом. Рас
смотрим возможные случаи. |
|
|
|
|
|
|
|||
|
I) |
|
/1>0, В > 0 , |
А + В<\. |
|
|
|
||
Так как [А1=А, |
[В], = В , т о |
[А],+[В]^ |
= А +В = [А +В\ |
^ |
|||||
резулыат положительный. |
|
|
|
|
|
|
|||
|
2) А<0, |
B>Q,\A\>B. |
|
|
|
||||
Здесь |
[A]^ = A + q, |
|
[В], = В . Тогда [А], + [В\ = .4 + В + </ — ре |
||||||
зультат отрицательный. |
|
|
|
|
|
|
|
|
|
|
3) .4<0, В > 0 , |
|.4|<В. |
|
|
|
||||
Здесь |
[A]^ = A + q, |
[B],=B |
+ q. |
Тогда |
1А],+[В], |
= А +B + q . |
|||
Так как значение этой суммы больше q, появляется единица переноса |
|||||||||
из знакового разряда, что равносильно изъятию из суммы q единиц, |
|||||||||
т. е. резулыат равен [А]^ + [В]„ = А + В . |
|
|
|
||||||
|
4) |
|
/1<0, В < 0 , |
|/1 + В|<1 . |
|
|
|||
Здесь |
\A\,^ = A + q, |
{B]^=B |
+ q. |
Тогда |
[/1], + [В]. =/1 + В + |
||||
4 (/*-(/--[/1 + В]^ — |
результат |
отрицательный (здесь |
появляется |
||||||
е;1ипи[!а переноса из з^гакового разряда).
Таким образом, теорема справедлива для всех случаев, в которых не возникает переполнение разрядной сетки, что позволяет складывать авто
матные |
изображения чисел |
ио правилам двоичной арифметики (см. |
табл. 4.2), не раздедгяя знаковую и цифровую части изображений. |
||
П|И1мер 4.3. Найти сумму чисел |
Л = 0,1010, Я = 0,0100, Hcriojrfc3yfl сумматор домалии- |
|
ieju,Hoio |
кола |
|
Г е m с и и с С'клалываются машинные изображения этих чисел:
[Л), =0,1010 [Я), =*0,0100
| С 1 , =0,1110
Пример 4.4. ИаГии сумму чисел /1 = Ч).1011, 5 = 0.0100 на сумматоре дополнительно- ) кола
4 Алгорипты выполнения операций на двоичных сумматорах
[Л], =1,0101 [Я],-0,0100 [CJ, = ЫОоГ
11|)имер 4.5. Ианти сумму чисел Л = 0.1011, В =-0,0100 на сумматоре лополиигелыю-
го кода.
Р е ш е н и е .
[Л), =0,1011
\B],ii,um
[П. =O0lll
Двоичный сумматор обратного кода (ДСОК) — сумматор, oiiepHpyioщий изображениями чисел в обратном коде. Характерная особенность ДСОК — наличие цепи кругового, или циклического, переноса нз знаково го разряда в младший разряд цифровой части (рис. 4.3, в).
Определим правила сложения чисел иа ДСОК.
Теорема. Сумма обратных кодов чисел есть обратный код ре зультата.
Доказательство. Рассмочрим следующие основные cjiytajr:
\) А>0, В>0, |
А +В <\.Топа [А]^+{В1^= |
А+ В = [А+ 41^,. |
|
2) А<0, |
В>й. |
|Л|>В . Здесь[,4у = , - , - " |
+ ,4,[B]„5 = B, |
Тогда [А]^ |
+ [В]„|5 =q^q-" +А + В = [А + В]^, |
так как результат |
|
отрицательный. |
|
|
|
3) |
А<0, |
В > 0 , |/1|<В.Здесь [,4J„5 =<?-</" + А. |
|
Тогда [/(]„„ + [В]^ -q- q" + А+ В . Так как [,4]„г, + [Й1„г, поло жительна, правая часть этого выражения становится больше q, чю вызывает появление единицы переноса из знакового разряда. По скольку в ДСОК существует цепь переноса из знакового разряда в младший разряд (величина переноса из знакового разряда равна
q-q~"), то [А]^ |
+1Щ„6 = [-4 + ^*]„б, результат положи1ельг1ын. |
4) А<0, |
В<0, \А + В\<\.Здесь [А]^ =q'q"' + А, |
96
4,2 Спогисеиие чисел на двоичных сумматорах
Следовательно, [Л]^ + [В]^ =q~q'" +q~q " + А + В. Здесь появляется единица переноса из знакового разряда, что равносиль
но изъятию из суммы |
величины |
q-q"", т. е. [А]^ |
+[^]об ~ |
|
Ъ)\Л\ = В, |
А<0, |
В > 0 . Тогда [А]^^ = q - q~" •¥ А. |
|
|
Следовательно, |
{А\^ |
+ {В]^^ =q-д'" |
+ А + В = q-q~" |
— резуль |
тат указывает иа то, что сумма равна нулю (получим одно из изобра жений нуля в обратном коде).
Таким образом доказано, что на ДСОК машинные изображения чисел также складываются по правилам, приведенным в таблице 4.2.
11;}нме;| 4.6. Найт сумму чисел А-0,0101 и Я = 0,0111, используя сумматор обрат ною кола.
Р е ш е н и е ,
[AU =^0,0101
[CJ^ =0,1100
Отает Г ^ (1.1 1(10
Пример 4.7. liaihn сумму чисел /i = -0,0101 и S = 0,0111. используя ДСОК. Р с III е II и е .
[AU |
=1,1010 |
[ДУ-0,0111 |
|
|
.^0,0001 |
[Си |
= 0,0010 |
Ответ С =0,0010.
М|и|ме|> 4.8. Май i и сумму чисел /( = 0,0101 и S = -0,0111, используя ДСОК. Р е и( с и и с -
[AU =^0,0101
[ду J|,iooo
[CJ^ =1,110!
Отает С ^-0,0010.
Пример 4.!). ПаИги сумму чисел А = -0,0101 и Я = -0,1000 , используя ДСОК.
4- Алгоритмы выполнения операций на двоичных сумматорах
\AU = 1,1010 \ви=+1,01111,000|
[си = 1,0010
Ответ С = -0,1101.
В дальнейшем для упрощения записи передача циклическои) irepenoca будет осуществляться сразу при получении результата и отдельно фиксиро ваться не будет.
4.3. Переполнение разрядной сетки
При сложении чисел одинакового знака, представленных в форме с фиксированной запятой, может возникнуть переполнение разрядной сетки.
I. Признак переполнения разрядной сетки сумматора прямого кода — появление единицы переноса из старшего разряда цифровой части числа.
•имер 4.10 |
|
|
|
\а А == 0,1010 и1 Я =0,110 |
Ы .4 = -0,1100 и Д =-0,1010 |
||
|
= 0,1010 |
[.-1), = 1.1100 |
|
|
[Я)„„ i |
0,1101 |
[Д|„р = 1,1010 |
|
VX, * |
0.0111 |
ia„p*i.oiio |
1 |
единица переноса |
1 ,^~ единица переноса |
|
I I . Признак |
переполнения разрядной сетки сумматора дополнитель |
||
ного кода при сложении положительных чисел — отрицательный знак
результата, а при сложении отрицательных чисел — |
п о л о ж т е л ь н ы й |
|
знак результата. |
|
|
Зо. ..< = 0.1011 и Я = 0,1010 |
4<1. /t = -0.10ll и |
й = -0.1001 |
|/t], =0,1011 |
[.^1. =1,0101 |
|
[Я), =VlOIO |
[Я), =1,0111 |
|
[С1, * l.oiol |
[ П , * 0,1100 |
|
I I I . Признак переполнения |
разрядной сетки сумматора обратно! о |
|
кода — знак результата, противоположный знакам операндов.
98
|
4.3 Переполнение разрядной сетки |
|
|
5<1. /f = 0,0111 |
и Я = 0,1101. |
6а. Л=-0,0110 |
и fi = -0,110l . |
[Л)^ =0,0111 |
М].е= 1,1001 |
||
[ДЦ =0.1101 |
[В|„б =1.0010 |
||
[ C J ^ * |
1,0100 |
[ С у * |
0,1011 |
Для обнаружения переполнения разрядной сетки в составе цифрового автомата должны быть предусмотрены аппаратные средства, автоматически вырабатывающие признак переполнения — сигнал <р.
Чтобы обнаружить переполнение разрядной сетки ДСОК и ДСДК, вво
дится вспомогательный разряд в знаковую |
Разр„) „,/,е„,„„,,^„ |
|
|||||||||
часть изс^ражеиия числа (рис. 4.4, а), |
который |
| |
|
|
|
|
|
||||
называют |
разрядом |
переполнения. |
На |
|
|
|
|
_____ |
|||
рис. 4.4, б, в |
соответственно |
представлены |
р я ^ |
f | г | J| |
• |
. • [rt-zjn-'ln |
|||||
изображения положительного и отрицательно- |
" ЗнакВ5Г~ |
|
|
|
|||||||
... |
|
|
|
|
|
часть |
|
|
--- |
- |
|
ГО чисел. 1акое представление |
числа |
называ- |
Iglgl f h |
[oh Ig jolf I |
\i I |
||||||
ется модифицированным. Тогда в случае по- |
5' ' |
* ' |
' i |
I |
1 1 1 I 1 |
||||||
явления переполнения сигнал <р = I : |
|
|
g I 'I ^|о|о|^ | о | ' I f И1^|0| |
||||||||
.Sj^, л |
Sgj = 1, 'S'g, л Sgj |
~ 1; |
|
('^•6) |
Рис. 4.4. Представление чисел |
||||||
в ocтaJи.пыx случаях ф - и . |
|
|
|
в модифицированном коде |
|||||||
|
|
|
|
|
|
|
|
|
|||
Это подтверждается следующими примерами. |
|
|
|
|
|
||||||
'^^> \А\" -OO.iOll |
модифиЕшровалное изображение операнда Л; |
|
|
||||||||
\В]" |
=00,!010 ^ |
модифицированное изображение операнда S; |
|
|
|
||||||
[С J^ == 01.010 i |
— О i — признак переполнения в знаковых разрядах, ф = t; |
||||||||||
46|,((" = 1 j OJOi - модифицированное изображение операнда Л; {И]" =f И,0 i 11 — модифицированное изображение операнда В;
|
\С\" =10.1100 — 10 —признак переполнения в знаковых разрядах, ф = ! ; |
|
56 |
[Л|^ = 00.0111 — модифицированное изображение операнда/i; |
|
|
[lift |
+ |
|
= 00,! lOl — модифицированное изображение операнда В; |
|
|
{(']"(, |
-01.0100 — 01 — признак переполнения в знаковых разрядах, ф=1 ; |
66 |
\,4\"' |
-М.ИЮ! -" модифицированное изображение операнда Л; |
|
[ Д|'^ = 11,00(0 — модифицированное изображение операнда В; |
|
|
\(']'^ |
= f 0.( 100 ^ 10 -— признак перенолнения в знаковых разрядах, ф = 1 . |
Здесь и п лальпейшем тексте символ л означает логическую функцию И, а черта над HMBojiOM S^ —функцию HF. (см § 10,1).
99
4Алгоритмы выполнения операций на двоичных i-умматорах
4.4.Особенности сложения чисел, представленных в форме с плавающей запятой
Числа, представленные в форме с плавающей запятой, изображаются двумя частями — мантиссой и порядком. При операции алгебраического сложения действия, выполняемые над мантиссами и порядками, различны. Следовательно, в цифровом автомате должны быть два раздельных устрой ства для обработки мантисс и для обработки порядков.
Так как для чисел с плавающей запятой справедливо условие (3.21), то всякий результат, не удовлетворяющий этому условию, должен быть при веден в соответствие с формулой (3.21). Такую операцию называют норма лизацией числа. Операция нормализации числа состоит из проверки выпол нимости условия (3.21) и сдвига изображения мантиссы в ту или иную сторону. Сдвиги могут осуществляться на один разряд и более в левую или правую сторону в пределах разрядной сетки машины.
Простой сдвиг — операция, выполняемая по следующим ггравилам:
Исходная |
Сдвинутая влево |
Сдвинутая вправо |
|
комбинация |
на один разряд |
на один разряд |
|
0, й|а2-.-^я |
^1,^3--- |
^„О |
О, 0^1---^„-1 |
1, й|Й2...й„ |
й | , Й 2 . . . |
й „ а |
0,1«, ...й„_| |
Модифицированный сдвиг — операция над модифицированными изо бражениями, выполняемая следующим образом :
Исходная |
Сдвинутая |
влево |
Сдвинутая вправо |
|||||
комбинация |
на один |
ряд |
на один |
рачря/! |
||||
00, |
йг, ЙГ2... |
а„ |
ОйГ|, ^2 |
• • • <^п 0 |
00, |
Ой| |
...я„ 1 |
|
0 1, |
ЙГ| «2 ... |
ЙГ„ |
1йГ,,йГ2 |
• • • « „ 0 |
00,1й|... |
«„_, |
||
1 0 , |
ЙГ| ЙГ2 . . . |
ЙГ„ |
Ойг,,йГ2 |
. . |
. а „ а |
1, |
Ойг, .••йг„^1 |
|
1 i , |
(3|ЙГ2 . - - |
й Г , , |
1йГ,, «2 |
•••й„СС |
1, |
1а, ..•йг„_. |
||
Нарушение нормализации числа — невыгюлнение условия (3.21). Так как ycjroBHe (3.21) содержит два неравенства, то может быть нарушение справа и слева. Признак нарушения нормализации числа сгграва у (когда величина результата равна или превышает единицу) — наличие разноимен ных комбинаций в знаковых разрядах сумматора, т. е.
у = 1,если Sg, л5^2 = 1: Jg^/^Sg^ =1 |
(4.7) |
Величина а зависит от кода: для допоямительного кода а = О . для обратно1х) кода а = I.