Система счисления — совокупность приемов и правил для записи чисел цифровыми знаками.
Любая предназначенная для практического применения система счисления должна обеспечивать:
Типы систем счисления:
Непозиционные системы счисления (СС) характеризуются тем, что для представления какого-либо числа используется определенный набор символов, который изменяется при изменении диапазона представляемых чисел. В качестве типичного примера непозиционной системы счисления обычно приводится римская система счисления, в которой для небольших чисел и коррекции чисел с большим значением используется символ I. Для представления больших чисел приходится вводить новые символы (V, X, C и т.д.).
В позиционных системах счисления значение единицы цифры каждого разряда числа имеет постоянный вес. Этот вес определяется позицией, которую разряд занимает по отношению к запятой:
234,5610 = 2*102 + 3*103 + 4*104 + 5*10-1 + 6*10-2
С этой точки зрения, римская система счисления не является чисто непозиционной, т.к., например, число IV равно четырем, а число VI – шести.
Любая позиционная система счисления характеризуется своим основанием.
Основание (базис) p-й позиционной системы счисления – количество знаков, или символов, используемых для изображения числа в данной системе:
p=10 → {ai} = 0,1, …,9;
p=2 → {ai} = 0,1;
p=5 → {ai} = 0,1,2.3.4;
p=16 → {ai} = 0, 1, …, 9, A, B, C, D, E, F;
p=q→ {ai} = 0,1.,…,q-1
| Десятичное число | Эквиваленты в некоторых других системах счисления | |||
|---|---|---|---|---|
| p = 2 | p = 5 | p = 8 | p = 16 | |
| 0 | 0000 | 00 | 00 | 0 |
| 1 | 0001 | 01 | 01 | 1 |
| 2 | 0010 | 02 | 02 | 2 |
| 3 | 0011 | 03 | 03 | 3 |
| 4 | 0100 | 04 | 04 | 4 |
| 5 | 0101 | 10 | 05 | 5 |
| 6 | 0110 | 11 | 06 | 6 |
| 7 | 0111 | 12 | 07 | 7 |
| 8 | 1000 | 13 | 10 | 8 |
| 9 | 1001 | 14 | 11 | 9 |
| 10 | 1010 | 20 | 12 | A |
| 11 | 1011 | 21 | 13 | B |
| 12 | 1100 | 22 | 14 | C |
| 13 | 1101 | 23 | 15 | D |
| 14 | 1110 | 24 | 16 | E |
| 15 | 1111 | 30 | 17 | F |
| 16 | 10000 | 31 | 18 | 10 |
Для любой позиционной системы счисления основание изображается числом 10 в данной системе.
В общем виде число А в p-ной позиционной системе счисления представляется в виде:
$$A=a_n*p^n+a_{n-1}*p^{n-1}+. . .+a_1*p^1+a_0*p^0+a_{-1}*p^{-1}+a_{-2}*p^{-2}+. . . a_{-m}*p^{-m}=p^k \sum_{i=-m}^{n}a_i*p^i$$При k = Const получается число, носящее, в общем случае, название числа с фиксированной точкой, но имеющее две разновидности:
k=0: правильная дробь – число с фиксированной запятой, то есть правильную дробь
A = a-1*p-1+a-2*p-2+…+a-m*p-m
k=r: целое число – число с фиксированной точкой, то есть целое число
A = an*pn+an-1*pn-1+…+a1*p1+a0*p0
При k ≠Const получается число с плавающей запятой.
Представление в виде числа с фиксированной точкой (или ее разновидности – с фиксированной запятой) влияет на диапазон представляемых чисел и их точность.
Микропроцессоры, которые в настоящее время служат основой для построения ЭВМ различных типов, содержат в своем составе как блоки, предназначенные для обработки целых чисел (СPU –CentralPointUnit), так и блоки для обработки чисел с плавающей запятой (FPU – FloatingPointUnit, в силу англоязычной специфики представления дробных чисел целая часть от дробной отделяется не запятой, а точкой). Представление чисел с плавающей запятой включает в себя порядок (целое число) и мантиссу (правильную дробь), которые обрабатываются в отдельных блоках FPU. Поэтому изучение особенностей представления и обработки каждого из типов чисел чрезвычайно важно для изучения устройства ЭВМ, выбора необходимого формата данных как с точки зрения требуемого диапазона, так и допустимой погрешности.
Обсуждение способов кодирования и различных алгоритмов обработки чисел мы будем проводить, в основном, на примере чисел с фиксированной запятой, так как именно в этом формате представляются мантиссы чисел с плавающей запятой, что сказывается на обработке чисел с плавающей запятой в целом. В свою очередь использование чисел с плавающей запятой играет в настоящее время весьма важную роль в процессе человеко-машинного общения, снимая с программиста во многих случаях обязанность по отслеживанию диапазона и точности используемых и получаемых данных.
К тому же числа с фиксированной запятой играют заметную самостоятельную роль в специализированных компьютерах, работающих в определенном диапазоне чисел, повышая при этом быстродействие таких вычислений, что особенно проявилось в ЭВМ второго и третьего поколений.
Основными определяющими факторами в данном вопросе являются
Если принять, что каждый разряд числа представлен не одним элементом с p устойчивыми состояниями, a p элементами, каждый из которых имеет одно устойчивое состояние, то показатель экономичности укажет условное количество оборудования, которое необходимо затратить на представление чисел в этой системе.
Допустим, что имеется n разрядов для изображения числа в р-ичной системе счисления. В этом случае максимальное число М будет отвечать выражению:
$$M=p^n-1 \approx p^n$$Наряду с величиной М, являющейся мерой максимального количества информации, которое может быть представлено в п разрядах, оценим число элементов N, необходимое для изображения числа М:
$$p*n$$Равенство (6.2) справедливо при условии, что для изображения каждого из допустимых в некотором разряде символов (цифр) требуется один элемент.
Определим N как непрерывную функцию от р и М. Из равенства (6.2) следует, что
$$n=In M/ln p$$Подставляя это выражение в (6.3), получаем
$$N=p In M/ln p$$Используя полученную зависимость, можно найти основание системы счисления, при которой требуется минимум оборудования. Так, определив производную
$$dN/dp= N' = lnM*((lnp – 1)/ln^2p)$$и приравняв ее к нулю, получим экстремум при р = е.
Характер экстремума соответствует минимуму, так как при р = е
N''>0
Таким образом, система при р = е требует минимума оборудования.
Но e = 2, 718… , т. е. не целое число. Поэтому на практике целесообразно использовать системы с основаниями р = 3 или р = 2. Эти системы, согласно приведенной оценке, практически равноценны, так как отношение
N2/N3 = (2 ln3) / (3 ln2)≈1,056
Подобное сравнение десятичной и двоичной систем показывает, что десятичная система примерно в полтора раза менее экономична двоичной:
N10/N2 = (10 ln2) / (2 ln10) ≈ 1,505
При переводе чисел из одной позиционной системы счисления в другую необходимо выполнять различные арифметические операции. Не останавливаясь подробно на механизме выполнения этих операций в каждой системе счисления, отметим лишь, что числа, представленные в различных позиционных системах счисления, обрабатываются схожим образом с учётом, естественно, особенностей данной системы счисления и имеющихся в ней символов.
Так, на примере операции сложения это будет выглядеть следующим образом:
Cq = Aq +Bq
Aq = an*qn+an-1*qn-1+…+a1*q1+a0*q0
Bq = bm*qm+bm-1*qm-1+…+b1*q1+b0*q0
Промежуточная сумма:
si = ai+bi+ pi-1 ,
где ai, и bi - соответствующие разряды слагаемых,
pi-1– перенос из предыдущего разряда.
Пример:
52648 + 65318 = 140158
Выполнение операции по шагам:
| +5 | 2 | 6 | 4 | A8 | |
| 6 | 5 | 3 | 1 | B8 | |
| 11 | 7 | 9 | 5 | S1 | |
| +3 | 7 | 1 | 5 | C1 | |
| 1 | 0 | 1 | 0 | 0 | P1 |
| 1 | 3 | 8 | 1 | 5 | S2 |
| 1 | 3 | 0 | 1 | 5 | C2 |
| 0 | 1 | 0 | 0 | 0 | P2 |
| 1 | 4 | 0 | 1 | 58 | S3=A+B |
Для перевода смешанного числа, то есть числа, содержащего как целую, так и дробную части, из p-ичной системы счисления в q-ю существует несколько способов.
Прежде всего, отметим, что перевод целой части числа и его дробной части осуществляется по различным правилам. Рассмотрим некоторые из них.
Метод 1. Данный метод используется наиболее часто. Его суть состоит в том, что исходное p-ичное число делится на основание q новой системы счисления. Получаемый остаток представляет собой p-ичную запись q-ичной цифры нового представления числа. Частное от деления вновь делится на основание qновое системы счисленияи т.д. до тех пор, пока не будет получено частное, меньшее, чем q. Запись нового представления числа начинается с младшей цифры. Действия производятся в p-ичной системе счисления.
Обоснование метода 1:
Ap = an*pn+an-1*pn-1+…+a1*p1+a0*p0
Bq = br*qr+br-1*qr-1+…+b1*q1+b0*q0
Aq /q = {А1,S1}, гдеА1 –целая часть результата, S1 – остаток.
Bq /q = {В1,R1}, гдеB1- целая часть результата, R1-остаток.
B1= br*qr-1+br-1*qr-2+…+b1*q0
R1= b0
Т.к. Ap ≡ Bq,тоb0 = S1.
Пример 6.1. Перевести число 179 из 10-й системы счисления в 7-ю.
В результате преобразования получим: 18110= 3467
Пример 6.2. Перевести число 346 из 7-й системы счисления в 10-ю.
При выполнении этого перевода необходимо помнить следующие особенности:
Так, 35 х 35 = 215, т.к. символа "6" в 5-й системе счисления нет, а согласно общей записи числа в позиционной системе счисления (см 6.1) 215 = 2*51 + 1*50.
Основание новой системы счисления будет представлено в исходной 7-й системе значением: 1010 = 137.
Вернемся к нашему первому методу перевода. Выполним перевод:
На одном из этапов деления мы получили остаток, меньший делителя, но не являющийся одной цифрой. Вспомним, что мы переводим число в систему счисления с бОльшим основанием, где количество символов для представления знаков числа больше, поэтому запишем окончательный результат:
3467 = 18110,
что согласуется с предыдущим примером.
Метод 2. Все цифры и основание представления числа согласно формуле (6.1) в исходной системе счисления записываются в новой системе счисления. Над полученным выражением проводятся вычисления, результат которых и будет представлять собой запись исходного числа в новой системе счисления.
Пример. Перевести число 321 из 4-й в 3-ю систему счисления.
3214 = (3х42+2х41+1х40)4 = (10х112+2х111+1х110)3 =
= (10х11х11+2х11+1)3 = 20103
3214 = 20103
Метод 3. Основным недостатком метода 2 является необходимость выполнения большого количества операций умножения при большой разрядности переводимого числа. Некоторое сокращение этих операций может быть получено при вычислении многочлена по схеме Горнера для многоразрядного числа.
Покажем это на том же примере:
3214 = (3х42+2х41+1х40)4 = (10х112+2х111+1х110)3 =
= (10х11х11+2х11+1)3=
=(((0+10)х11+2)х11+1)3 = 20103
Если в предыдущем примере для получения результата потребовалось выполнить четыре операции умножения, то в этом примере только три. Так как умножение выполняется в компьютере достаточно долго, то сокращение этих операций может существенно уменьшить общее время преобразования целого числа из одной системы счисления в другую.
В этом случае исходное p-ичное число имеет следующий вид:
Ap = a-1*p-1+a-2*p-2+…+a-m*p-m
Основной метод, используемый для перевода чисел с фиксированной запятой из p ичной системы счисления в q-ичную заключается в следующем. В q-ичной системе счисления данная дробь будет иметь вид:
Bq = b-1*q-1+b-2*q-2+…+b-n*q-n...
Очевидно, что в новой системе счисления количество разрядов может отличаться от количества разрядов числа в исходной системе счисления и, более того, в новой системе счисления некоторые числа не могут быть представлены конечным числом знаков.
Погрешность числа в его новом представлении должна соответствовать его погрешности в исходной системе счисления, то есть
0,5 a-m*p-m= 0,5b-n*q-n
Отсюда, решая данное показательное уравнение относительно n, получаем
n = p lnn / lnq
На практике рекомендуется получить (n+1) знак в новом представлении дроби и округлить дробь до n знаков, используя общее правило округления: если (n+1)-я цифра больше или равна половине основания новой системы счисления, то к остающимся разрядам добавляется "1". В противном случае - "0".
Так, 0,543147 ≈ 0,54327.
А теперь рассмотрим собственно метод перевода. Для перевода правильной дроби из p-ичной системы счисления в q-ичную необходимой исходную дробь умножить на основание q новой системы счисления. Целая часть полученного результата даст старшую цифру дроби нового представления числа. Дробная часть результата будет использована на следующем шаге операции перевода. Операция проводится до получения необходимого количества знаков в новом представлении числа.
Этот метод достаточно легко обосновать.
Обоснование правила перевода правильных дробей
$$A_p= a_{-1}*p^{-1}+a_{-2}*p^{-2}+…+ a_{-m}*p^{-m}$$ $$B_q = b_{-1}*q^{-1}+b_{-2}*q^{-2}+…+ b_{-s}*q^{-s} + ...$$Ap*q = {D1,S1}, где D1 – целая часть результата, S1 – дробная часть результата.
Bq *q = {K1,R1}, где K1– целая часть результата, R1 – дробная часть результата.
Из (6.5): K1 = b-1.
Т.к. Ap≡ Bq, то b-1 = D1.
Умножив Bq на q, получим целую часть результата, равную b-1.
Так как Bq = Ap, то умножение AP на q в качестве целой части результата тоже даст b-1.
Аналогичные действия над полученной дробной частью результата позволят получать очередные цифры нового представления числа.
Пример 6.3. Перевести число с фиксированной запятой 0,652 из 10-й системы счисления в 4 ю.
Сначала определим необходимое количество знаков в новом числе: p=10, q=4, n=3.
m = 3 ln10/ln4 ≈ 5
Следовательно, в новом представлении числа нужно получить n+1 = 6 знаков и округлить число до 5 знаков.
Таким образом, 0,65210 = 0,2212324 ≈ 0,221304
Пример 6.4. Перевести число с фиксированной запятой 0,2011 из 3-й системы счисления в 7 ю.
Число знаков в новом представлении числа:
m = 4 ln7/ln3 ≈ 2
Учитываем, что 7 = 213.
Получаем: 0,20113 = 0,5457 ≈ 0,557
Если основания систем счисления связаны таким соотношением, то на основании (6.1) после некоторых преобразований можно получить правила, которые существенно облегчат перевод из одной системы счисления в другую. Обычно они применяются при переводе между 16-ми и двоичными или 8-ми и двоичными системами счисления.
Перевод целых чисел
При переводе целых чисел из p-ичной СС в q-ичную необходимо каждую цифру исходного p-ичного числа заменить ее k-разрядным q ичным эквивалентом. При необходимости, дополнить число слева нулями.
Пример 6.5. Перевести число 101101 из 2-й системы счисления в 16-ю.
Решение. Определим k. 16=24. Следовательно, k=4. Исходное число содержит только 6 знаков. Но цело число не изменится, если слева к нему приписать необходимое количество нулей. Таким образом, получаем 2 группы по 4 знака в каждой: 0010 1101. Заменяя каждую группу одной 16-й цифрой, получим результат:
1011012 = 2D16
Перевод правильных дробей
При переводе правильных дробей из p-ичной СС в q-ичную необходимо каждую цифру исходного p-ичного числа заменить ее k разрядным q-ичным эквивалентом. При необходимости, дополнить число справа нулями.
Пример 6.6. Перевести число 0,1011011 из 2-й системы счисления в 8 ю.
Решение. Определим k. 8=23. Следовательно, k=3.
Перевод чисел между такими системами счисления (как для случая, когда q=pk) имеет большое практическое значение. Как известно, информация в ЭВМ передается и обрабатывается в двоичном виде. В то же время на экране или печатающем устройстве мы видим зачастую ее отображение в 16-м (в некоторых типах ЭВМ – в 8-м) виде. Это имеет ряд преимуществ.
Во-первых, экономится место на экране или печатающем устройстве. Одна 16-я цифра заменяет четыре двоичные. В то же время, при некотором навыке, легко представить, что за двоичное число отображается.
Во-вторых, существенно облегчается ввод числовой информации. Гораздо проще набрать на клавиатуре набор "A4C", чем "101001001100". При этом также сокращается и количество ошибок ввода.
Перевод целых чисел
При переводе целых чисел из p-ичной СС в q-ичную необходимо исходное p ичное число разбить на группы по k разрядов, начиная справа, и каждую группу заменить одной q ичной цифрой. При необходимости старшая группа дополняется слева нулями до k разрядов.
Перевод правильных дробей
При переводе правильных дробей из p-ичной СС в q-ичную необходимо исходное p ичное число разбить на группы по k разрядов, начиная слева, и каждую группу заменить одной q-ичной цифрой. При необходимости младшая группа дополняется справа нулями до k разрядов.
Примеры перевода чисел, представленных в 2k-ичных системах счисления
Пример 6.7. Перевести число 571,45 из 8-й в 2-ю систему счисления.
Так как 8 = 23, то каждую 8-ричную цифру необходимо заменить её 3-х разрядным двоичным эквивалентом:
571,458 = 101 111 001, 100 1012.
Пример 6.8. Перевести число 10111011001,1011012 из 2-й в 16-ю CC.
Так как 16 = 24, то исходное число необходимо разбить на группы по 4 разряда, при этом придется дополнить старшую группу целой части числа двумя нулями слева, а младшую группу дробной части нулем справа:
0010 1101 1001,1011 00102 = 2D9,B216
Пример 6.9. Перевести число E4,57 из 16-й в 8-ю систему счисления.
Так как 16 ≠ 8k, то прямой перевод по упрощенным правилам невозможен. В этом случае необходимо либо воспользоваться правилами перевода в произвольных СС, либо выполнить промежуточный перевод в 2-ю СС, так как 8=23 и 16=24: Воспользуемся вторым подходом.
E4,5716 = 1110 0100,0101 01112 = 011 100 100,010 101 1102 = 344,2568
Перевод смешанных чисел
Как отмечалось выше, перевод смешанных чисел, то есть чисел, имеющих как целую, так и дробную части, проводится раздельно для целой части и для дробной части числа. Так, чтобы перевести число 343,201 из 5-й системы счисления в 3-ю, сначала одним из описанных выше методов переводим целую часть числа:
3435 = 101223
Затем переводим дробную часть числа:
0,2015 ≈ 0,10203
Таким образом, итоговый результат будет выглядеть следующим образом:
343,2015 = 10122,10203
Здесь встает вопрос: "А что изменится, если вместо числа 10122,10203мы запишем число 10122,1023 ?" . Разрядность числа тесно связана с двумя его характеристиками: погрешностью и точностью представления числа. Рассмотрим их на примере чисел в двоичной системы счисления как используемой в подавляющем количестве ЭВМ.
Для чисел с фиксированной запятой, у которых под запись самого числа отводится n разрядов и 1 разряд отводится для указания знака числа, то есть они имеют вид (Рис. 6.1)
(рис 6.1) Представление числа с фиксированной запятой
модуль максимального числа будет иметь значение
| X | макс = 0,1 ... 1 = 1 – 2-п,
а модуль минимального числа, не равного нулю:
| X | мин = 0,0 ...01 = 2-п.
Для чисел с фиксированной точкой также при условии, что один разряд отводится под значение знака числа и n разрядов – под значение самого числа (Рис. 6.2), получим:
(рис 6.2) Представление числа с фиксированной точкой
| X | макс = 0,1 ... 1 = 2п-1,
а модуль минимального числа, не равного нулю:
| X | мин = 0,0 ...01 = 20 = 1.
Абсолютная погрешность представления – разность между истинным значением входной величины А и ее значением, полученным из машинного изображения Ам, т. е.
Δ[А] = А –Ам. ,
где Ам – машинное представление величины А, которое отличается от истинной в силу ограниченного количества разрядов машинной сетки.
Относительная погрешность представления – величина
σ [А] = Δ[А] / А
Погрешности представления чисел с фиксированной точкой
Абсолютная погрешность составляет половину единицы младшего разряда числа.
Для правильных дробей (числа с фиксированной запятой):
Δ[А] = 0.5* 2-n.
σ [А]мин = Δ[А] / Амакс = (0.5 * 2-n)/ (1-2-n) ≈ 0.5 *2-n
σ [А]макс = Δ[А] / Амин = (0.5 * 2-n) / 2-n = 0.5
Для целых чисел (числа с фиксированной точкой):
Δ[А] = 0.5* 20= 0.5.
σ [А]мин = Δ[А] / Амакс = 0.5 / (2п-1) ≈0.5 / 2п =0.5* 2-n
σ [А]макс = Δ[А] / Амин = 0.5 / 1 = 0.5
Как мы видим, и в том и в другом случае эта погрешность может существенно меняться в зависимости от представляемой величины.
Диапазон и точность представления чисел с плавающей запятой
k – порядок числа;
M – мантисса числа
Пример:
567 = 567*100 = 5670*10-1 = 5,67*102 = 0,567*103 = 0,00567*105 = …
Нормализованная мантисса удовлетворяет условию:
1 > |M| ≥ p-1
567 → 0,567*103
ЗнП |
2n-1 |
. . . |
21 |
20 |
ЗнМ | 2-1 |
2-2 |
. . . |
2-m |
| Порядок (n+1 разряд) | Мантисса (m+1разряд) | ||||||||
Пмакс = 0,1 ... 1 = 2п-1
М макс = 0,1 ... 1 = 1-2-m
-Пмакс = -(2п-1)
М мин = 0,1 = 2-1
Погрешности представления чисел с плавающей запятой
Δ[А] = 0.5* 2-m* 2P
σ [А]мин = Δ[А] / Амакс = ((0.5 * 2-m) * 2P) /((1-2-m) * 2P)≈ 0.5 *2-m
σ [А]макс = Δ[А] / Амин = ((0.5 * 2-m) * 2P) / 2-1 = 2-m
Особенности использования действующего в настоящее время ГОСТа 754-2008 на представление чисел с плавающей запятой мы обсудим в лекции, касающейся порядка обработки таких чисел и особых ситуаций, встречающихся в процессе этой обработки.
Рассмотрены типы систем счисления. По критерию минимальности используемого оборудования выбрана двоичная система счисления для реализации элементов вычислительной техники. Приведены правила перевода целых и дробных чисел из одной произвольной системы счисления в другую. Особое внимание обращено на перевод чисел, представленных в 2k-ичных системах счисления (двоичных, восьмеричных, 16-ных) между собой, что, с одной стороны, выполняется достаточно просто, а с другой стороны, требуется делать относительно часто в тех или иных случаях как при программировании, так и при разработке аппаратуры. Показаны механизмы расчета диапазонов представления и погрешностей для чисел различных форматов.
Система счисления — совокупность приемов и правил для записи чисел цифровыми знаками.
Любая предназначенная для практического применения система счисления должна обеспечивать:
Типы систем счисления:
Непозиционные системы счисления (СС) характеризуются тем, что для представления какого-либо числа используется определенный набор символов, который изменяется при изменении диапазона представляемых чисел. В качестве типичного примера непозиционной системы счисления обычно приводится римская система счисления, в которой для небольших чисел и коррекции чисел с большим значением используется символ I. Для представления больших чисел приходится вводить новые символы (V, X, C и т.д.).
В позиционных системах счисления значение единицы цифры каждого разряда числа имеет постоянный вес. Этот вес определяется позицией, которую разряд занимает по отношению к запятой:
234,5610 = 2*102 + 3*103 + 4*104 + 5*10-1 + 6*10-2
С этой точки зрения, римская система счисления не является чисто непозиционной, т.к., например, число IV равно четырем, а число VI – шести.
Любая позиционная система счисления характеризуется своим основанием.
Основание (базис) p-й позиционной системы счисления – количество знаков, или символов, используемых для изображения числа в данной системе:
p=10 → {ai} = 0,1, …,9;
p=2 → {ai} = 0,1;
p=5 → {ai} = 0,1,2.3.4;
p=16 → {ai} = 0, 1, …, 9, A, B, C, D, E, F;
p=q→ {ai} = 0,1.,…,q-1
| Десятичное число | Эквиваленты в некоторых других системах счисления | |||
|---|---|---|---|---|
| p = 2 | p = 5 | p = 8 | p = 16 | |
| 0 | 0000 | 00 | 00 | 0 |
| 1 | 0001 | 01 | 01 | 1 |
| 2 | 0010 | 02 | 02 | 2 |
| 3 | 0011 | 03 | 03 | 3 |
| 4 | 0100 | 04 | 04 | 4 |
| 5 | 0101 | 10 | 05 | 5 |
| 6 | 0110 | 11 | 06 | 6 |
| 7 | 0111 | 12 | 07 | 7 |
| 8 | 1000 | 13 | 10 | 8 |
| 9 | 1001 | 14 | 11 | 9 |
| 10 | 1010 | 20 | 12 | A |
| 11 | 1011 | 21 | 13 | B |
| 12 | 1100 | 22 | 14 | C |
| 13 | 1101 | 23 | 15 | D |
| 14 | 1110 | 24 | 16 | E |
| 15 | 1111 | 30 | 17 | F |
| 16 | 10000 | 31 | 18 | 10 |
Для любой позиционной системы счисления основание изображается числом 10 в данной системе.
В общем виде число А в p-ной позиционной системе счисления представляется в виде:
$$A=a_n*p^n+a_{n-1}*p^{n-1}+. . .+a_1*p^1+a_0*p^0+a_{-1}*p^{-1}+a_{-2}*p^{-2}+. . . a_{-m}*p^{-m}=p^k \sum_{i=-m}^{n}a_i*p^i$$При k = Const получается число, носящее, в общем случае, название числа с фиксированной точкой, но имеющее две разновидности:
k=0: правильная дробь – число с фиксированной запятой, то есть правильную дробь
A = a-1*p-1+a-2*p-2+…+a-m*p-m
k=r: целое число – число с фиксированной точкой, то есть целое число
A = an*pn+an-1*pn-1+…+a1*p1+a0*p0
При k ≠Const получается число с плавающей запятой.
Представление в виде числа с фиксированной точкой (или ее разновидности – с фиксированной запятой) влияет на диапазон представляемых чисел и их точность.
Микропроцессоры, которые в настоящее время служат основой для построения ЭВМ различных типов, содержат в своем составе как блоки, предназначенные для обработки целых чисел (СPU –CentralPointUnit), так и блоки для обработки чисел с плавающей запятой (FPU – FloatingPointUnit, в силу англоязычной специфики представления дробных чисел целая часть от дробной отделяется не запятой, а точкой). Представление чисел с плавающей запятой включает в себя порядок (целое число) и мантиссу (правильную дробь), которые обрабатываются в отдельных блоках FPU. Поэтому изучение особенностей представления и обработки каждого из типов чисел чрезвычайно важно для изучения устройства ЭВМ, выбора необходимого формата данных как с точки зрения требуемого диапазона, так и допустимой погрешности.
Обсуждение способов кодирования и различных алгоритмов обработки чисел мы будем проводить, в основном, на примере чисел с фиксированной запятой, так как именно в этом формате представляются мантиссы чисел с плавающей запятой, что сказывается на обработке чисел с плавающей запятой в целом. В свою очередь использование чисел с плавающей запятой играет в настоящее время весьма важную роль в процессе человеко-машинного общения, снимая с программиста во многих случаях обязанность по отслеживанию диапазона и точности используемых и получаемых данных.
К тому же числа с фиксированной запятой играют заметную самостоятельную роль в специализированных компьютерах, работающих в определенном диапазоне чисел, повышая при этом быстродействие таких вычислений, что особенно проявилось в ЭВМ второго и третьего поколений.
Основными определяющими факторами в данном вопросе являются
Если принять, что каждый разряд числа представлен не одним элементом с p устойчивыми состояниями, a p элементами, каждый из которых имеет одно устойчивое состояние, то показатель экономичности укажет условное количество оборудования, которое необходимо затратить на представление чисел в этой системе.
Допустим, что имеется n разрядов для изображения числа в р-ичной системе счисления. В этом случае максимальное число М будет отвечать выражению:
$$M=p^n-1 \approx p^n$$Наряду с величиной М, являющейся мерой максимального количества информации, которое может быть представлено в п разрядах, оценим число элементов N, необходимое для изображения числа М:
$$p*n$$Равенство (6.2) справедливо при условии, что для изображения каждого из допустимых в некотором разряде символов (цифр) требуется один элемент.
Определим N как непрерывную функцию от р и М. Из равенства (6.2) следует, что
$$n=In M/ln p$$Подставляя это выражение в (6.3), получаем
$$N=p In M/ln p$$Используя полученную зависимость, можно найти основание системы счисления, при которой требуется минимум оборудования. Так, определив производную
$$dN/dp= N' = lnM*((lnp – 1)/ln^2p)$$и приравняв ее к нулю, получим экстремум при р = е.
Характер экстремума соответствует минимуму, так как при р = е
N''>0
Таким образом, система при р = е требует минимума оборудования.
Но e = 2, 718… , т. е. не целое число. Поэтому на практике целесообразно использовать системы с основаниями р = 3 или р = 2. Эти системы, согласно приведенной оценке, практически равноценны, так как отношение
N2/N3 = (2 ln3) / (3 ln2)≈1,056
Подобное сравнение десятичной и двоичной систем показывает, что десятичная система примерно в полтора раза менее экономична двоичной:
N10/N2 = (10 ln2) / (2 ln10) ≈ 1,505
При переводе чисел из одной позиционной системы счисления в другую необходимо выполнять различные арифметические операции. Не останавливаясь подробно на механизме выполнения этих операций в каждой системе счисления, отметим лишь, что числа, представленные в различных позиционных системах счисления, обрабатываются схожим образом с учётом, естественно, особенностей данной системы счисления и имеющихся в ней символов.
Так, на примере операции сложения это будет выглядеть следующим образом:
Cq = Aq +Bq
Aq = an*qn+an-1*qn-1+…+a1*q1+a0*q0
Bq = bm*qm+bm-1*qm-1+…+b1*q1+b0*q0
Промежуточная сумма:
si = ai+bi+ pi-1 ,
где ai, и bi - соответствующие разряды слагаемых,
pi-1– перенос из предыдущего разряда.
Пример:
52648 + 65318 = 140158
Выполнение операции по шагам:
| +5 | 2 | 6 | 4 | A8 | |
| 6 | 5 | 3 | 1 | B8 | |
| 11 | 7 | 9 | 5 | S1 | |
| +3 | 7 | 1 | 5 | C1 | |
| 1 | 0 | 1 | 0 | 0 | P1 |
| 1 | 3 | 8 | 1 | 5 | S2 |
| 1 | 3 | 0 | 1 | 5 | C2 |
| 0 | 1 | 0 | 0 | 0 | P2 |
| 1 | 4 | 0 | 1 | 58 | S3=A+B |
Для перевода смешанного числа, то есть числа, содержащего как целую, так и дробную части, из p-ичной системы счисления в q-ю существует несколько способов.
Прежде всего, отметим, что перевод целой части числа и его дробной части осуществляется по различным правилам. Рассмотрим некоторые из них.
Метод 1. Данный метод используется наиболее часто. Его суть состоит в том, что исходное p-ичное число делится на основание q новой системы счисления. Получаемый остаток представляет собой p-ичную запись q-ичной цифры нового представления числа. Частное от деления вновь делится на основание qновое системы счисленияи т.д. до тех пор, пока не будет получено частное, меньшее, чем q. Запись нового представления числа начинается с младшей цифры. Действия производятся в p-ичной системе счисления.
Обоснование метода 1:
Ap = an*pn+an-1*pn-1+…+a1*p1+a0*p0
Bq = br*qr+br-1*qr-1+…+b1*q1+b0*q0
Aq /q = {А1,S1}, гдеА1 –целая часть результата, S1 – остаток.
Bq /q = {В1,R1}, гдеB1- целая часть результата, R1-остаток.
B1= br*qr-1+br-1*qr-2+…+b1*q0
R1= b0
Т.к. Ap ≡ Bq,тоb0 = S1.
Пример 6.1. Перевести число 179 из 10-й системы счисления в 7-ю.
В результате преобразования получим: 18110= 3467
Пример 6.2. Перевести число 346 из 7-й системы счисления в 10-ю.
При выполнении этого перевода необходимо помнить следующие особенности:
Так, 35 х 35 = 215, т.к. символа "6" в 5-й системе счисления нет, а согласно общей записи числа в позиционной системе счисления (см 6.1) 215 = 2*51 + 1*50.
Основание новой системы счисления будет представлено в исходной 7-й системе значением: 1010 = 137.
Вернемся к нашему первому методу перевода. Выполним перевод:
На одном из этапов деления мы получили остаток, меньший делителя, но не являющийся одной цифрой. Вспомним, что мы переводим число в систему счисления с бОльшим основанием, где количество символов для представления знаков числа больше, поэтому запишем окончательный результат:
3467 = 18110,
что согласуется с предыдущим примером.
Метод 2. Все цифры и основание представления числа согласно формуле (6.1) в исходной системе счисления записываются в новой системе счисления. Над полученным выражением проводятся вычисления, результат которых и будет представлять собой запись исходного числа в новой системе счисления.
Пример. Перевести число 321 из 4-й в 3-ю систему счисления.
3214 = (3х42+2х41+1х40)4 = (10х112+2х111+1х110)3 =
= (10х11х11+2х11+1)3 = 20103
3214 = 20103
Метод 3. Основным недостатком метода 2 является необходимость выполнения большого количества операций умножения при большой разрядности переводимого числа. Некоторое сокращение этих операций может быть получено при вычислении многочлена по схеме Горнера для многоразрядного числа.
Покажем это на том же примере:
3214 = (3х42+2х41+1х40)4 = (10х112+2х111+1х110)3 =
= (10х11х11+2х11+1)3=
=(((0+10)х11+2)х11+1)3 = 20103
Если в предыдущем примере для получения результата потребовалось выполнить четыре операции умножения, то в этом примере только три. Так как умножение выполняется в компьютере достаточно долго, то сокращение этих операций может существенно уменьшить общее время преобразования целого числа из одной системы счисления в другую.
В этом случае исходное p-ичное число имеет следующий вид:
Ap = a-1*p-1+a-2*p-2+…+a-m*p-m
Основной метод, используемый для перевода чисел с фиксированной запятой из p ичной системы счисления в q-ичную заключается в следующем. В q-ичной системе счисления данная дробь будет иметь вид:
Bq = b-1*q-1+b-2*q-2+…+b-n*q-n...
Очевидно, что в новой системе счисления количество разрядов может отличаться от количества разрядов числа в исходной системе счисления и, более того, в новой системе счисления некоторые числа не могут быть представлены конечным числом знаков.
Погрешность числа в его новом представлении должна соответствовать его погрешности в исходной системе счисления, то есть
0,5 a-m*p-m= 0,5b-n*q-n
Отсюда, решая данное показательное уравнение относительно n, получаем
n = p lnn / lnq
На практике рекомендуется получить (n+1) знак в новом представлении дроби и округлить дробь до n знаков, используя общее правило округления: если (n+1)-я цифра больше или равна половине основания новой системы счисления, то к остающимся разрядам добавляется "1". В противном случае - "0".
Так, 0,543147 ≈ 0,54327.
А теперь рассмотрим собственно метод перевода. Для перевода правильной дроби из p-ичной системы счисления в q-ичную необходимой исходную дробь умножить на основание q новой системы счисления. Целая часть полученного результата даст старшую цифру дроби нового представления числа. Дробная часть результата будет использована на следующем шаге операции перевода. Операция проводится до получения необходимого количества знаков в новом представлении числа.
Этот метод достаточно легко обосновать.
Обоснование правила перевода правильных дробей
$$A_p= a_{-1}*p^{-1}+a_{-2}*p^{-2}+…+ a_{-m}*p^{-m}$$ $$B_q = b_{-1}*q^{-1}+b_{-2}*q^{-2}+…+ b_{-s}*q^{-s} + ...$$Ap*q = {D1,S1}, где D1 – целая часть результата, S1 – дробная часть результата.
Bq *q = {K1,R1}, где K1– целая часть результата, R1 – дробная часть результата.
Из (6.5): K1 = b-1.
Т.к. Ap≡ Bq, то b-1 = D1.
Умножив Bq на q, получим целую часть результата, равную b-1.
Так как Bq = Ap, то умножение AP на q в качестве целой части результата тоже даст b-1.
Аналогичные действия над полученной дробной частью результата позволят получать очередные цифры нового представления числа.
Пример 6.3. Перевести число с фиксированной запятой 0,652 из 10-й системы счисления в 4 ю.
Сначала определим необходимое количество знаков в новом числе: p=10, q=4, n=3.
m = 3 ln10/ln4 ≈ 5
Следовательно, в новом представлении числа нужно получить n+1 = 6 знаков и округлить число до 5 знаков.
Таким образом, 0,65210 = 0,2212324 ≈ 0,221304
Пример 6.4. Перевести число с фиксированной запятой 0,2011 из 3-й системы счисления в 7 ю.
Число знаков в новом представлении числа:
m = 4 ln7/ln3 ≈ 2
Учитываем, что 7 = 213.
Получаем: 0,20113 = 0,5457 ≈ 0,557
Если основания систем счисления связаны таким соотношением, то на основании (6.1) после некоторых преобразований можно получить правила, которые существенно облегчат перевод из одной системы счисления в другую. Обычно они применяются при переводе между 16-ми и двоичными или 8-ми и двоичными системами счисления.
Перевод целых чисел
При переводе целых чисел из p-ичной СС в q-ичную необходимо каждую цифру исходного p-ичного числа заменить ее k-разрядным q ичным эквивалентом. При необходимости, дополнить число слева нулями.
Пример 6.5. Перевести число 101101 из 2-й системы счисления в 16-ю.
Решение. Определим k. 16=24. Следовательно, k=4. Исходное число содержит только 6 знаков. Но цело число не изменится, если слева к нему приписать необходимое количество нулей. Таким образом, получаем 2 группы по 4 знака в каждой: 0010 1101. Заменяя каждую группу одной 16-й цифрой, получим результат:
1011012 = 2D16
Перевод правильных дробей
При переводе правильных дробей из p-ичной СС в q-ичную необходимо каждую цифру исходного p-ичного числа заменить ее k разрядным q-ичным эквивалентом. При необходимости, дополнить число справа нулями.
Пример 6.6. Перевести число 0,1011011 из 2-й системы счисления в 8 ю.
Решение. Определим k. 8=23. Следовательно, k=3.
Перевод чисел между такими системами счисления (как для случая, когда q=pk) имеет большое практическое значение. Как известно, информация в ЭВМ передается и обрабатывается в двоичном виде. В то же время на экране или печатающем устройстве мы видим зачастую ее отображение в 16-м (в некоторых типах ЭВМ – в 8-м) виде. Это имеет ряд преимуществ.
Во-первых, экономится место на экране или печатающем устройстве. Одна 16-я цифра заменяет четыре двоичные. В то же время, при некотором навыке, легко представить, что за двоичное число отображается.
Во-вторых, существенно облегчается ввод числовой информации. Гораздо проще набрать на клавиатуре набор "A4C", чем "101001001100". При этом также сокращается и количество ошибок ввода.
Перевод целых чисел
При переводе целых чисел из p-ичной СС в q-ичную необходимо исходное p ичное число разбить на группы по k разрядов, начиная справа, и каждую группу заменить одной q ичной цифрой. При необходимости старшая группа дополняется слева нулями до k разрядов.
Перевод правильных дробей
При переводе правильных дробей из p-ичной СС в q-ичную необходимо исходное p ичное число разбить на группы по k разрядов, начиная слева, и каждую группу заменить одной q-ичной цифрой. При необходимости младшая группа дополняется справа нулями до k разрядов.
Примеры перевода чисел, представленных в 2k-ичных системах счисления
Пример 6.7. Перевести число 571,45 из 8-й в 2-ю систему счисления.
Так как 8 = 23, то каждую 8-ричную цифру необходимо заменить её 3-х разрядным двоичным эквивалентом:
571,458 = 101 111 001, 100 1012.
Пример 6.8. Перевести число 10111011001,1011012 из 2-й в 16-ю CC.
Так как 16 = 24, то исходное число необходимо разбить на группы по 4 разряда, при этом придется дополнить старшую группу целой части числа двумя нулями слева, а младшую группу дробной части нулем справа:
0010 1101 1001,1011 00102 = 2D9,B216
Пример 6.9. Перевести число E4,57 из 16-й в 8-ю систему счисления.
Так как 16 ≠ 8k, то прямой перевод по упрощенным правилам невозможен. В этом случае необходимо либо воспользоваться правилами перевода в произвольных СС, либо выполнить промежуточный перевод в 2-ю СС, так как 8=23 и 16=24: Воспользуемся вторым подходом.
E4,5716 = 1110 0100,0101 01112 = 011 100 100,010 101 1102 = 344,2568
Перевод смешанных чисел
Как отмечалось выше, перевод смешанных чисел, то есть чисел, имеющих как целую, так и дробную части, проводится раздельно для целой части и для дробной части числа. Так, чтобы перевести число 343,201 из 5-й системы счисления в 3-ю, сначала одним из описанных выше методов переводим целую часть числа:
3435 = 101223
Затем переводим дробную часть числа:
0,2015 ≈ 0,10203
Таким образом, итоговый результат будет выглядеть следующим образом:
343,2015 = 10122,10203
Здесь встает вопрос: "А что изменится, если вместо числа 10122,10203мы запишем число 10122,1023 ?" . Разрядность числа тесно связана с двумя его характеристиками: погрешностью и точностью представления числа. Рассмотрим их на примере чисел в двоичной системы счисления как используемой в подавляющем количестве ЭВМ.
Для чисел с фиксированной запятой, у которых под запись самого числа отводится n разрядов и 1 разряд отводится для указания знака числа, то есть они имеют вид (Рис. 6.1)
(рис 6.1) Представление числа с фиксированной запятой
модуль максимального числа будет иметь значение
| X | макс = 0,1 ... 1 = 1 – 2-п,
а модуль минимального числа, не равного нулю:
| X | мин = 0,0 ...01 = 2-п.
Для чисел с фиксированной точкой также при условии, что один разряд отводится под значение знака числа и n разрядов – под значение самого числа (Рис. 6.2), получим:
(рис 6.2) Представление числа с фиксированной точкой
| X | макс = 0,1 ... 1 = 2п-1,
а модуль минимального числа, не равного нулю:
| X | мин = 0,0 ...01 = 20 = 1.
Абсолютная погрешность представления – разность между истинным значением входной величины А и ее значением, полученным из машинного изображения Ам, т. е.
Δ[А] = А –Ам. ,
где Ам – машинное представление величины А, которое отличается от истинной в силу ограниченного количества разрядов машинной сетки.
Относительная погрешность представления – величина
σ [А] = Δ[А] / А
Погрешности представления чисел с фиксированной точкой
Абсолютная погрешность составляет половину единицы младшего разряда числа.
Для правильных дробей (числа с фиксированной запятой):
Δ[А] = 0.5* 2-n.
σ [А]мин = Δ[А] / Амакс = (0.5 * 2-n)/ (1-2-n) ≈ 0.5 *2-n
σ [А]макс = Δ[А] / Амин = (0.5 * 2-n) / 2-n = 0.5
Для целых чисел (числа с фиксированной точкой):
Δ[А] = 0.5* 20= 0.5.
σ [А]мин = Δ[А] / Амакс = 0.5 / (2п-1) ≈0.5 / 2п =0.5* 2-n
σ [А]макс = Δ[А] / Амин = 0.5 / 1 = 0.5
Как мы видим, и в том и в другом случае эта погрешность может существенно меняться в зависимости от представляемой величины.
Диапазон и точность представления чисел с плавающей запятой
k – порядок числа;
M – мантисса числа
Пример:
567 = 567*100 = 5670*10-1 = 5,67*102 = 0,567*103 = 0,00567*105 = …
Нормализованная мантисса удовлетворяет условию:
1 > |M| ≥ p-1
567 → 0,567*103
ЗнП |
2n-1 |
. . . |
21 |
20 |
ЗнМ | 2-1 |
2-2 |
. . . |
2-m |
| Порядок (n+1 разряд) | Мантисса (m+1разряд) | ||||||||
Пмакс = 0,1 ... 1 = 2п-1
М макс = 0,1 ... 1 = 1-2-m
-Пмакс = -(2п-1)
М мин = 0,1 = 2-1
Погрешности представления чисел с плавающей запятой
Δ[А] = 0.5* 2-m* 2P
σ [А]мин = Δ[А] / Амакс = ((0.5 * 2-m) * 2P) /((1-2-m) * 2P)≈ 0.5 *2-m
σ [А]макс = Δ[А] / Амин = ((0.5 * 2-m) * 2P) / 2-1 = 2-m
Особенности использования действующего в настоящее время ГОСТа 754-2008 на представление чисел с плавающей запятой мы обсудим в лекции, касающейся порядка обработки таких чисел и особых ситуаций, встречающихся в процессе этой обработки.
Рассмотрены типы систем счисления. По критерию минимальности используемого оборудования выбрана двоичная система счисления для реализации элементов вычислительной техники. Приведены правила перевода целых и дробных чисел из одной произвольной системы счисления в другую. Особое внимание обращено на перевод чисел, представленных в 2k-ичных системах счисления (двоичных, восьмеричных, 16-ных) между собой, что, с одной стороны, выполняется достаточно просто, а с другой стороны, требуется делать относительно часто в тех или иных случаях как при программировании, так и при разработке аппаратуры. Показаны механизмы расчета диапазонов представления и погрешностей для чисел различных форматов.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.