1 Математические основы работы ЭВМ. Математические основы работы эвм системы счисления

• Название: Математические основы работы эвм системы счисления
• Дата: 20.02.2022
• Размер: 26.78 Kb.
• Имя файла: 1 Математические основы работы ЭВМ.docx
• Тип: Документы; #367551

Глава 5

МАТЕМАТИЧЕСКИЕ ОСНОВЫ РАБОТЫ ЭВМ
5.1. Системы счисления

Человек (по классификации живых существ Гомо Сапиенс — Человек Разумный) мыслит и обменивается мыслями с себе по­добными. Обмен этот осуществляется в основном с помощью зву­ков — речи, состоящей из отдельных слов. Для сохранения мы­слей, выраженных словами, служит письмо, т.е. запись речи оп­ределенными значкам. Наибольшее распространение получила бук­венная запись, когда для обозначения каждого из звуков, состав­ляющих слово, служит определенный знак. Для обозначения ко­личественных соотношений между объектами, ситуациями, про­цессами используются числа, которые также могут быть выраже­ны словами. Но для записи чисел используется более экономный способ, чем буквенная запись слов. Числа могут быть записаны с помощью специальных знаков — цифр.

Современное написание цифр десятичной системы счисления пришло к нам из Индии через арабов. Само слово «цифра» проис­ходит от арабского слова «сифр». В XIII в. этими цифрами стали пользоваться в Италии благодаря флорентийским купцам, торго­вавшим с арабскими. Использование так называемых арабских цифр стало повсеместным в XV в.

При создании ЭВМ надежнее пользоваться схемами, которые могут быть только в двух устойчивых положениях. Например, элек­тромагнитное реле может иметь замкнутый или разомкнутый кон­такт, определенный участок магнитной ленты может быть намаг­ничен или размагничен и т.д. Поэтому, как уже отмечалось в гл. 4, большинство ЭВМ оперирует числами, записанными при помо­щи только двух цифр: 0 и 1. Как же представить любое число при помощи только двух цифр? Для этого необходимо использовать двоичную систему счисления.

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





ков, т.е. цифр. При записи чисел в десятичной системе счисления пользуются десятью цифрами: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Деся­тичная система является позиционной, поскольку значение каж­дой цифры в числе зависит от ее положения (позиции) среди других цифр этого числа. Например, в числе 2724,25 имеются три цифры 2. Все они имеют разные значения. Левая цифра указыва­ет значение тысяч (2 тысячи), средняя — значение десятков (2 де­сятка), а правая (справа от запятой) — значение десятых долей (2 десятых доли). Указанное число является сокращенной записью следующей суммы:

2724,25 = 2 • 10³ + 7 • 10² + 2 • 10¹ + 4 • 10°+ 2 • НИ + 5 • 1(Н.

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

Вдвоичной системе счисления единица каждого разряда равна двум единицам предыдущего разряда. Слева от разряда единиц рас­положены разряды двоек, четверок, восьмерок и т.д. Чтобы запи­сать число в двоичной системе, нужно представить его в виде сум­мы последовательных степеней числа 2, умноженных на 0 или 1:

2724,25 = 1 • 2¹¹ + 0 • 2¹⁰ + 1 • 2⁹ + 0 • 2⁸ + 1 • 2⁷ + 0 • 2⁶ + 1 • 2⁵ + 0 • 2⁴ +
+ 0 • 2³ + 1 • 2² + 0 • 2¹ + 0 • 2° + 0 • 2-¹ + 1 • 2².

Вместо того чтобы записывать десятичное число как сумму последовательных степеней числа 10, умноженных на одну из цифр от 0 до 9, мы пользуемся сокращенной записью (2724,25), т.е. выписываем подряд те цифры, на которые умножаются различ­ные степени числа 10. Аналогично при записи чисел в двоичной системе счисления, вместо того чтобы записывать сумму последо­вательных степеней числа 2, умноженных на 0 или 1, выписыва­ют только те цифры, на которые эти степени умножаются. Таким образом, (2724,25)₁₀ = (101010100100,01)₂.

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

При записи чисел в восьмеричной системе единица в каж­дом разряде равна восьми единицам предыдущего разряда. Поэто­му в этой системе счисления пользуются только восемью цифра­ми: 0, 1, 2, 3, 4, 5, 6, 7. Запишем число (9775)₁₀ в восьмеричной системе счисления:

(9775)₁₀ = 2 • 8⁴ + 3 • 8³ + 0 • 8² + 5 • 8¹ + 7 • 8° = (23057)₈.

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





цифр применяют прописные буквы латинского алфавита. Весь набор цифровых символов для шестнадцатеричной системы счисления выглядит так: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F.

При записи чисел в шестнадцатеричной системе единица в каждом разряде равна шестнадцати единицам предыдущего раз­ряда. Запишем число (9775)₁₀из предыдущего примера в шестнад­цатеричной системе счисления:

(9775)₁₀ = 2 • 16³ + 6 • 16² + 2 • 16¹ + F • 16° = (262F)₁₆.

Представление информации в шестнадцатеричной системе го­раздо компактнее, поскольку каждая группа из четырех двоичных цифр заменяется одним символом. Запомнить информацию в ше­стнадцатеричной системе (например, из трех символов) человеку легче, чем в двоичной (из 12 символов).

5.2. Перевод чисел из одной системы счисления в другую

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

Для записи, например, числа (173)₁₀ в двоичной системе нуж­но найти такие цифры 4, А_ь Л₂,..., Л„, равные 0 или 1, чтобы

42" + 42" -¹ + ... + Л„ _ ,2 + А„ = 173. (5.1)

Разделим правую и левую части равенства (5.1) на 2. Так как А, равно 0 или 1, то в частном от деления левой части на 2 получим 4,2" ¹ + 42""² + ... + А_п _ ₂2 + А„ _ j, а в остатке число А_п.

Получившиеся частное и остаток должны соответственно рав­няться частному и остатку от деления правой части равенства (5.1) на 2, поэтому

4 = 1;

42"-¹ +42"-² + ... +4_₂2 + 4_, = 86. (5.2)

Разделим теперь на 2 обе части равенства (5.2) и приравняем получившиеся частные и остатки. В результате будем иметь

4-1 = 0;

42" -² + 42" -³ + ... + 4 - з2 + 4 - 2 = 43. (5.3)

Разделим еще раз на 2 обе части равенства (5.3) и, сравнив частные и остатки, получим

4 - 2 = 1;

42"-³ + 42"-⁴ +... +4-₄2 + 4-з = 21.

Аналогичным образом найдем значения остальных цифр 4- в результате получим: 4 = 1; 4 = 0; 4 = 1; 4 = 0; 4 = 1; 4 = 1; 4 = о и 4 = 1-



Следовательно, 173 = Aq2⁷ + А{2^Ь + ... + A^l + А₇ = 1 • 2⁷ + 0 • 2⁶ + 1 • 2⁵ + 0 • 2⁴ + 1 • 2³ +1 • 2² + 0 • 2¹ + 1 • 2°, т. е. (173)₁₀ = (10101101)₂.

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


173

172

1


86 L2—


8$. _43

О 42 _²¹¹²


Т 20 10Т2_ 1 "10 _5 0 _4 1


2l2_ 2 1 0


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

Можно пользоваться более простой формой записи:

173 86 43 21 10 5 2 1 1 01 1010'

Над чертой записывают заданное число и получающиеся част­ные, под чертой — остатки от деления соответствующих частных на 2.

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

Рассмотрим, как осуществляется перевод дробных чисел из десятичной системы в двоичную. Пусть, например, число (0,6875)ю требуется записать в двоичной системе. Для этого нужно найти такие цифры А_и А₂, ..., А„, равные 0 или 1, чтобы

А_х2^х + А₂2² + А₃2-³ + ... + А„_ ₂'2^_(”“²⁾ + Л- Г2⁴”- ^!) +

+ А„2^п = 0,6875. (5.4)

Умножим обе части равенства (5.4) на 2:

А_х + А₂2¹ + А₃2² + ... + А„ _ ₂ 2^{(п 3)} + А„ - {2^{{п 2)} +


+ Л2-^(Я1) = 1,3750.


(5.5)



В левой части равенства (5.5) цифра А, есть целая часть числа в правой части (т.е. 1), а подчеркнутая сумма составляет дробную часть, поэтому А_х = 1,

Л₂2-> + А₃ 2² + ... + А„ _ ₂2“⁽" - ³> + А„ . j2-(^{n 2}> +

+ А„ 2-<«-= 0,375. (5.6)

Теперь умножим на 2 обе части равенства (5.6):

А₂ + А₃2-> + ... + А„ _ ₂2<” - ⁴> + А„_а-^{(п 3)} +


+ А„2^{(п 2)} = 0,75. (5.7)

Отсюда А₂ = 0, а подчеркнутая часть равна 0,75.

Умножим на 2 обе части равенства (5.7):

А₃ + 4,2-^! + ... + А„ 2^{(п 3)} =1,5. (5.8)

Следовательно, А₃ = 1, а подчеркнутая часть равна 0,5, т.е.

+Л2-^(я-³⁾ = 0,5. (5.9)

После умножения на 2 равенства (5.9) получим А_л = \. По­


скольку дробная часть равна 0 (результат умножения 0,5 на 2 мож-
но записать как 1,000... 00), то и все остальные цифры А,- равны 0,
т.е. А₅ =Аб = ... =А„= 0.

Таким образом, (0,6875)₁₀ = (0,1011)₂.

Приведенные вычисления удобнее записать в следующем виде:
0,6875

X

2

1,3750

0,3750

х


0,750

х


1,50

0,50

X

2_

1,0

Цифры, выделенные полужирным шрифтом, и являются ис­комыми двоичными цифрами, причем первой получается цифра, стоящая сразу после запятой.

Наше дробное число в двоичной системе можно представить в виде суммы: (0,1011)₂= (0,1000)₂+ (0,0010)₂+ (0,0001)₂



Каждому слагаемому соответствует своя десятичная дробь: (0,1000)₂ = (0,5000)_1О; (0,0010)₂ = (0,1250)₁₀; (0,0001)₂ = (0,0625)_1О. Сложив эти дроби, получим исходное число в десятичной системе: 0,5 + 0,125 + 0,0625 = 0,6875. Это свидетельствует о том, что перевод из десятичной системы в двоичную выполнен верно.

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

Перевод числа из восьмеричной системы в двоичную и обрат­но очень прост. Чтобы число, записанное в восьмеричной системе счисления, записать в двоичной системе, нужно каждую восьме­ричную цифру заменить тройкой двоичных цифр: (0)₈ = (000)₂; (1)₈ = (001)₂; (2)₈ = (010)₈; (3)₈ = (011)₂; (4)₈ = (100)₂; (5)₈ = (101)₂; (6)₈ = (110)₂; (7)₈ = (111)₂.

При переводе из двоичной системы в восьмеричную разбива­ют двоичное число справа налево на группы из трех двоичных цифр каждая. Сначала выделяют крайнюю правую группу (пос­ледние три цифры двоичной записи), затем следующую группу (три цифры слева от крайней группы) и т.д. Если в последней группе остается менее трех цифр, то вместо недостающих цифр ставят нули. Заменив каждую группу соответствующей восьме­ричной цифрой, получают число, записанное в восьмеричной системе счисления.

Например, двоичное число 11001101 разбивается на следу­ющие группы: 011; 001; 101. Поскольку (011)₂ = (3)₈, (001)₂ = (1)₈, (101)₂ = (5)₈, то в восьмеричной системе это будет число 315, т.е. (11001101)₂ = (315)₈.

Аналогичные правила действуют и при использовании шест­надцатеричной системы счисления.

При переводе из двоичной системы в шестнадцатеричную дво­ичное число разбивают на группы из четырех цифр каждая. Такие группы называются тетрадами. Тетрады для шестнадцатеричных цифр от 0 до 7 подобны тем группам, что приведены выше для этих же восьмеричных цифр (только добавляется 0 слева). Осталь­ным шестнадцатеричным цифрам соответствуют следующие тет­рады: (8) 1₆ = (1000)₂; (9)₁₆ = (Ю01)₂; (А),₆ = (1010)₂; (В)₁₆ = (1011)₂; (С)₁₆ = (1Ю0)₂; (D)i₆ = (1101)₂; (Е)₁₆ = (1110)₂; (F)₁₆ = (1111)₂.

Первое слагаемое	Второе слагаемое
	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	10
2	2	3	4	5	6	7	10	11
3	3	4	5	6	7	10	11	12
4	4	5	6	7	10	11	12	13
5	5	6	7	10	11	12	13	14
6	6	7	10	11	12	13	14	15
7	7	10	11	12	13	14	15	16

Сомножители	0	1
0	0	0
1	0	1

ницу. Если в младшем разряде уже стоит единица, то при этом приходится изменять цифру в следующем, а, возможно, и в более старших разрядах.

Например, при вычитании из числа ЮНО числа 01101 умень­шаемое представляют как положительное число в прямом коде 010110, а вычитаемое — как отрицательное число, прямой код которого 101101 (полужирным шрифтом выделены цифры знако­вого разряда). Определяют дополнительный код вычитаемого. Сна­чала инвертируют цифры всех разрядов, кроме знакового (резуль­тат 110010), затем прибавляют единицу в младший разряд (110011). Выполняют операцию сложения уменьшаемого (в прямом коде) с вычитаемым (в дополнительном коде):

010110

+

110011

001001.

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

Убедимся в этом на примере, из числа 01101 (в прямом коде 001101) вычтем 10110. Для этого определим дополнительный код отрицательного числа 110110: сначала инвертируем цифры всех разрядов, кроме знакового (101001), потом добавим единицу в младший разряд (101010). Выполним сложение уменьшаемого в прямом коде и вычитаемого в дополнительном коде:

001101

+

101010

110111.

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

Правильность вычислений проверим на десятичных числах: (10110)₂ = (22) ₁₀; (01101)₂ = (13)₁₀; (01001)₂ = (9)₁₀; 22 - 13 = 9; 13 - - 22 = -9.

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





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

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

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

Рассмотрим пример:


10111

х

1101

10111

00000

10111

10111

100101011

• 
  множимое
  
• 
  множитель
  
• 
  первое частичное произведение
  
• 
  второе частичное произведение
  
• 
  третье частичное произведение
  
• 
  четвертое частичное произведение
  
• 
  произведение
  

Тот же результат можно получить при умножении, начиная со старших разрядов множителя:

10111

х

1101

10111

10111

00000

10111

100101011.





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

Можно привести следующее обоснование тому, что умноже­ние сводится к сдвигу и сложению. Пусть надо перемножить 101101 и 101101.

Запишем это в такой форме: 101101 • 101101 = 101101(100000 + + 1000 + 100 + 1) = 10110100000 + 101101000 + 10110100 + 101101.

Таким образом, умножение на 100000 свелось к приписыва­нию пяти нулей (т.е. сдвигу на пять разрядов влево), на 1000 — трех (сдвиг на три разряда), на 100 — двух (сдвиг на два разряда). Иными словами, из первого сомножителя формируется столько частичных слагаемых, сколько единиц имеется во втором со­множителе. Сдвиг производится на столько разрядов влево, на каком месте (в каком разряде) находится соответствующая еди­ница, минус один. Например, если единица есть в шестом раз­ряде, сдвиг производится на пять разрядов, а если в четвертом, то на три. Если единица в первом разряде, то никакого сдвига делать не надо, в качестве одного из слагаемых берется сам пер­вый сомножитель. Затем все полученные частные слагаемые скла­дываются.

Операция деления в ЭВМ может быть сведена к нескольким операциям вычитаний и сдвигов. Результат деления (частное) оп­ределяется как число вычитаний с учетом сдвигов. Например, де­ление 132 : 11 = 12 можно осуществить в виде такой последова­тельности вычитаний и сдвигов:

_ 132

110 — первое вычитание

022

220 — сдвиг

110 — первое вычитание

_¹¹⁰

110 — второе вычитание

000

Ответ: 12 (одно вычитание до сдвига и два после).

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





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

Иными словами, во многих машинах операция деления заме­няется умножением, так как а/Ъ = а(1/Ь). По числу b машина авто­матически вычисляет число 1 /Ь, которое затем умножается на а.

Довольно часто результат деления вычисляется не вполне точ­но, т.е. с некоторым приближением. Ведь деление без остатка не всегда возможно. В привычной нам десятичной системе это тоже часто бывает. Например, если разделить 2 на 3, то в ответе полу­чится 0,666..., т.е. 6 в периоде. На практике принимают результат с округлением: 0,67, или 0,667, или 0,6667. Чем больше знаков после запятой, тем меньше ошибка вычисления.


5.4. Способы представления чисел в разрядной сетке ЭВМ


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

При выполнении операции сложения двоичных чисел возмож­но переполнение разрядной сетки, которое проявляется в том, что результат операции (получившаяся сумма) требует большего количества разрядов, чем имеется в устройстве для его хранения. Для выявления переполнения разрядной сетки используется мо­дифицированный код. К двоичному числу добавляются два знако­вых разряда, причем в обоих разрядах положительные числа со­держат нули, а отрицательные числа — единицы. Выполнение операций суммирования с использованием модифицированного дополнительного кода производится по обычным приведенным выше правилам. Если результат суммирования содержит в знако­вых разрядах комбинации 01 или 10 (т.е. разные цифры), то это служит признаком переполнения разрядной сетки.

Насмотрим пример сложения чисел:


+


00 11011 — первое слагаемое в прямом модифицированном
коде


11 01011 — второе слагаемое в дополнительном модифици­рованном коде

00 00110 — сумма в прямом модифицированном коде


Переполнение разрядной сетки в данном случае не возникает (в знаковых разрядах комбинация 00). Перенос из старшего знако­вого разряда при сложении отбрасывается.