Глава 4. Арифметические основы ЭВМ

4.1 Системы счисления

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

Можно считать, что любое число имеет значение (содержа­ние) и форму представления(т. е. запись числа). Значение числа задает порядок расположения чисел на числовой оси, или другими словами его отно­шение к значениям других чисел («больше», «меньше», «равно»). Форма представления определяет поря­док записи числа с помощью предназначенных для этого знаков. При этом значение числа не зависит от способа его представления. Это означает также, что число с одним и тем же значением может быть записано по-разному, т.е. отсутствует взаимно однозначное соответствие между пред­ставлением числа и его значением. Например, число пять в римской системе счисления представляется как символ «V», в двоичной системе счисления как набор символов – цифр «101», в десятичной системе счисления как символ – цифра «5» и т.д., этот ряд можно продолжать бесконечно. В связи с этим возникают во­просы, во-первых, о формах представления чисел, и, во-вторых, о возможности и способах перехода от одной формы к другой.

Способ представления числа определяется системой счис­ления.

Система счисления – совокупность приёмов и правил для записи числа символами(цифровыми знаками).

Любая предназначенная для практического применения система счисления должна обеспечивать единственность представления числа и простоту оперирования числами.

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

Непозиционные системы счисления.

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

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

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

Наиболее известная непозиционная система счисления - римская. В римской системе счисления для изображения чисел используются символы I, V, X, L(50), C(100), D(500),М(1000). Десятичное число 27 представляется следующим образом: XXVII=10+10+5+1+1. В непозиционных системах счисления не представляются дробные и отрицательные числа. Арифметические операции выполнять в непозиционной системе счисления очень сложно, так как отсутствуют правила для выполнения действий.

Позиционные системы счисления.

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

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

Для записи чисел в конкретной системе счисления используется некоторый конечный алфавит, состоящий из цифр - символов.

При этом основанием традиционной системы счисления может быть любое натуральное число р³2. Наименование системы счисления соответствует ее основанию. Количество цифр, используемых в р-ичных системах счислениях для записи алфавита равно основанию системы счисления Например, алфавит двоичной системы счисления состоит из двух цифр 0 и 1. Алфавит двенадцатеричной системы счисления состоит из 12 цифр-символов: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B. Традиционных цифр-символов для записи алфавита этой системы счисления оказалось недостаточно, поэтому были введены в качестве цифр заглавные буквы латинского алфавита.

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

Запишем алфавиты систем счисления, используемых в информатике:

- двоичная система счисления 0,1;

- четверичная система счисления 0,1,2,3;

- восьмеричная система счисления 0,1,2,3,4,5,6,7;

- шестнадцатеричная система счисления 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

Любое число А в позиционной системе счисления можно представить суммой произведений целых однозначных коэффициентов a_i, взятых из алфавита системы на последовательные целые степени основания p (так называемая развернутая форма записи числа):

, (4.1)

где m — количество цифр в целой части числа или А_q= ×q_k, для целой части числа и А_q= ×q^k (4.2)

где а_к-любая цифра из алфавита системы с основанием равным q, m, n-число позиций соответственно для целой и дробной частей числа.

Степенной ряд для целой и дробной частей числа можно представить эквивалентными выражениями по схеме Горнера:

для целой части: А_q= a_k×q_k=(…((a_m-1q+a_m-2q)q+a_m-3)q+…+a₁)q+a₀; (4.3)

для дробной части A_q= a_kq_k=q^-1(a_-1+q^-1(a_-2+…q^-1 (a_-k+1+a_-kq^-1)…)). (4.4)

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

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

Целое число в системе счисления q может быть представлено эквивалентным числом в системе счисления р по формуле (1.3)

А_q=А_р=(…((b_m-1p+b_m-2p)q+b_m-3)p+…+b₁)p+b_0. (4.5)

Задача перевода числа из одной системы счисления(q) в другую систему счисления (р) заключается в отыскании значений цифр b_k числа в новой системе счисления.

Разделив обе части равенства (4.5) на основание новой системы р, выраженное цифрами системы счисления q, получим:

(4.6)

или А_q=A_p=(A_q)₁+b₀, где (А_q)₁ – целое частное, b₀ – остаток, являющийся первой младшей цифрой числа в новой системе счисления, остаток выражен цифрами исходной системы счисления.

При следующем делении частного на основание системы счисления р будут получены новое частное и новый остаток: (А_q)₁=(A_q)₂+b₁, где b_{1 –} вторая младшая цифра числа. Продолжая деление целых целых частных до нулевого значения частного, находим все цифры числа в новой системе счисления.

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

1) последовательно делить данное число и получаемые целые частные на основание новой системы счисления, выраженные цифрами исходной системы, до тех пор, пока частное не станет равным нулю.

2) Полученные остатки, являющиеся цифрами числа в новой системе счисления, выразить цифрами алфавита этой системы счисления.

3) Записать число в новой системе, начиная с последнего остатка.

2) Перевод дробных чисел.

Рассуждая по аналогии с переводом для целых чисел, но используя операцию умножения, сформулируем правило перевода дробных чисел.

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

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

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

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

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

1.) Используем изложенный способ перевода числа из одной системы счисления в другую при р=10 и q=2.

Пусть десятичное число равно 13. Чтобы перевести его в двоичную систему счисления необходимо проделать следующие арифметические операции:

1

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

Каждое очередное частное делится на 2 до тех пор, пока частное от деления не станет не станет равным 0.

Последнее частное является старшим разрядом двоичного числа. Запишем полученное последнее частное и все остатки по порядку справа—налево — 1101, это и есть число 13 в двоичной системе счисления, 13₁₀=1101₂.

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

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

Поясним на примерах.

1) переведем число 0,5 (десятичное) в двоичную систему счисления. Для наглядности будем приводить умножение «столбиком».

0

2) 0,75₁₀ переводим в двоичную систему счисления.

0	75 2
	50 2

Выписываем разряды «сверху—вниз».

3) 0,33₁₀ переводим в двоичную систему.

0	33 2
	66 2
1	32 2
	64 2
	28 2
	56 2
	12 2
	24 2
	48 2
	96 2
	92...

4) Перевести 10,25₁₀ в двоичную систему счисления.

0,	25 2
	50 2
	0

10,25₁₀=1010,01₂.

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

Таблица степеней числа 2.

20	21	22	23	24	25	26	27	28	29	210

123=64+32+16+8+2+1=1×2⁶+1×2⁵+1×2⁴+1×2³+0×2²+1×2¹+1×2⁰=1111011².

Рассмотрим перевод целых и дробных чисел из десятичной системы счисления в восьмеричную систему счисления.

В восьмеричной системе счисления для представления числа используются цифры от 0 до 7. Правила перевода естественно остаются прежними.

Пример

21,25₁₀ переведем в восьмеричную систему счисления.

2110=258 0,2510=0,28   21,2510=25,28

	25 8

При переводе из десятичной системы счисления в шестнадцатеричную, необходимо помнить о том, что количество символов алфавита шестнадцатеричной системы счисления превышает количество символов алфавита десятичной системы счисления и двузначные числа 11,12,13,14,15 десятичной системы счисления являются однозначными в системе счисления по основанию 16.

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

Алфавит шестнадцатеричной системы счисления:

A

B

C

D

E

F

Пример.

Перевести десятичное число 142,25 в шестнадцатеричную систему счисления.

14210=8E8 0,2510=0,416   142,2510=8E,416

(E)

0,	25 16

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

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

Пример 1.

Перевести из восьмеричной системы счисления в десятичную следующие числа:

-13.4₈; 27.51₈; 14.2₈; 127.03₈

Запишем развернутую форму записи числа в восьмеричной системе счисления, основание системы счисления10₈, выразим цифрой десятичной системы счисления 10₈=8₁₀

Выполним перевод для первого числа:

-13.4₈= -(13₈+0.4₈)

-13.4₈= -11.5₁₀.

Остальные примеры решите самостоятельно.

Пример 2.

Перевести следующие числа: 1110011.01₂, -456.07₈, 1АС.15₁₆.

1110011.01=1×2⁶+1×2⁵+1×2⁴+0×2³+0×2²+1×2¹+1×2⁰+

0×2^-1=64+32+16+2+1+0.25=115.25; остальные примеры выполните самостоятельно.

4.5 Системы счисления с основаниями, являющимися степенью 2.

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

Таблица переводов.