 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Позиционными называются системы счисления, в которых значение каждой цифры в изображении числа определяется ее положением (позицией) в ряду других цифр
|
|
Наиболее распространенной и привычной является десятичная система счисления, в которой для записи чисел используются 10 цифр: 0, 1, 2, … 9.
Число в позиционной системе счисления представляет собой краткую запись многочлена, в который входят степени некоторого другого числа – основания системы счисления (в десятичной системе это 10).
Например, 272.12 = 2 ×102 + 7 × 101 + 2 × 100 + 1 × 10-1 + 2 × 10-2.
В данном числе цифра 2 встречается 3 раза, однако значение этой цифры разное и определяется позицией в числе.
Количество цифр для построения чисел равно основанию системы счисления. Также очевидно, что максимальная цифра на 1 меньше основания.
Причина широкого распространения десятичной системы счисления, очевидно, связана со счетом в унарной системе с пальцами рук в качестве «палочек». Однако в истории человечества имеются свидетельства использования и других систем счисления – пятеричной, шестеричной, двенадцатеричной, двадцатеричной и даже 60-ричной.
Главной особенностью позиционного представления является то, что в нем посредством конечного набора знаков можно записать неограниченное количество различных чисел.
Кроме того, в позиционной системе счисления гораздо легче выполняются операции умножения и деления. Именно эти обстоятельства обуславливают доминирование позиционной системы при обработке чисел, как человеком, так и компьютером.
Пусть р – основание системы счисления. Тогда любое число Z (пока ограничимся только целыми числами) может быть представлено в виде многочлена
. (5.1)
Из коэффициентов ai при степенях основания строится сокращенная запись числа 
.
Индекс р у числа Z указывает, что оно записано в системе счисления с основанием р; общее количество цифр числа равно k.
Все коэффициенты ai – целые числа, удовлетворяющие условию
0 £ ai £ p –1.
Каково минимальное значение р? р =1 невозможно, поскольку тогда все ai = 0 и форма (4.1) теряет смысл.
Первое допустимое значение р = 2 – оно и является минимальным для позиционных систем счисления. Такая система счисления называется двоичной. Ее цифрами являются 0 и 1, а форма (4.1) строится по степеням двойки. Интерес именно к этой системе счисления связан с тем, что любая информация в компьютере представляется с помощью состояний 0 и 1, которые легко реализуются технически.
Наряду с двоичной системой счисления в компьютере используется
8-ричная и 16-ричная системы счисления.
Примечание. В первых компьютерах не использовались возможности двоичного представления. Вопрос, как числа должны быть представлены в вычислительных машинах, активно обсуждался в конце 30-х и в 40-х годах ХХ века. Одним из возможных способов представления была двоично-пятеричная система, в которой каждая цифра в десятичной записи была закодирована семибитной последовательностью, представляющей два числа, сумма которых равнялась числу, представляемому исходной цифрой в десятичной системе. Старшие (левые) 2 бита, определяют, является ли первое слагаемое 0 (комбинация 01), или 5 (комбинация 10). Оставшиеся 5 битов представляют числа 4,3,2,1,0. Они обязательно содержат четыре 0 и одну 1. 1 стоит в том разряде, который представляет собой второе слагаемое. (Например, число 3 имеет представление 0101000, а число 7 - 1000100). Именно эта система использовалась в машине ENIAC.
Еще раз подчеркнем, что значение целого числа (то есть общее количество входящих в него единиц) не зависит от способа его представления и остается одинаковым во всех системах счисления – различают только формы представления одного и того же количественного содержания числа.
Так, например, ||(1) = 5(10) = 101(2) = 10(5) = 5(6) = 12(3).
5.2 Перевод чисел из одной системы счисления в другую
Рассмотрим правила перевода целой части числа из десятичной системы счисления в систему счисления с основанием р: Z (10) ® Z (р):
1. целочисленно разделить (деление с остатком) исходное число Z (10) на основание новой системы счисления р и найти остаток от деления;
2. частное от деления снова целочисленно разделить на р с выделением остатка. Шаг 2 повторять, пока частное от деления не окажется меньше р;
3. образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Z(p).
Пример 1. Перевести из десятичной в пятеричную систему счисления число 123. 123(10) ® Z (5)
Ответ: Z (5) = 443(5).
Полученное число нельзя читать «четыреста сорок три», поскольку десятки, сотни, тысячи и прочие подобные обозначения чисел относятся только к десятичной системе счисления. Прочитывать число следует простым перечислением его цифр с указанием системы счисления (число четыре, четыре, три в пятеричной системе счисления).
Правило перевода целых чисел из системы счисления с основанием р в десятичную систему счисления Z (р) ® Z (10):
1. необходимо представить Z (р) в форме многочлена (5.1) и выполнить все операции по правилам десятичной арифметики.
Пример 2.Перевести из пятеричной системы счисления в десятичную число 443(5). 443(5)® Z (10).
4 × 52 + 4 × 51 + 3 × 50 = 4 × 25 + 20 + 3 = 123(10).
Ответ: Z (10) = 123(10).
Перевод дробной части чисел из одной системы счисления в другую.
Правила перевода из десятичной системы счисления в систему счисления с основанием р Z (10) ® Z (р):
1. умножить исходную дробь в 10-ной системе счисления на (р), выделить целую часть - она будет первой цифрой новой дроби; отбросить целую часть;
2. для оставшейся дробной части операцию умножения с выделением целой и дробной частей повторять, пока в дробной части не окажется 0 или не будет достигнута желаемая точность конечного числа; появляющиеся при этом целые будут числами новой дроби;
3. записать дробь в виде последовательности цифр после ноля с разделителем в порядке их появления в п.1. и п.2.
Пример 3. Перевести из десятичной в двоичную систему счисления число 0.375. 0.375(10) ® 0.Y(2)?
0.375 * 2 = 0.750 (0 – целая часть); 0,750 * 2 = 1.500 (1 – целая часть);
0.500 * 2 = 1.000 (1 – целая часть).
Процесс завершен, так как в результате очередного умножения получился 0 в дробной части.
Ответ: 0.375(10) ® 0.011(2).
! Следует сознавать, что после перевода дроби, которая была конечной в исходной системе счисления, она может оказаться бесконечной в новой системе счисления. И, наоборот, иррациональное число в исходной системе счисления в иной системе счисления может оказаться рациональным.
Так, 0.3(3)10 ® 0.1(3).
Правило перевода дробной части из системы счисления с основанием р в десятичную систему счисления Z (р) ® Z (10):
необходимо представить Z (р) в форме многочлена (5.1) и выполнить все операции по правилам десятичной арифметики.
Пример 4. Перевести из двоичной в десятичную систему счисления число 0.011(2). 0.011(2) ® 0.Y(10)
0.011(2)= 0 × 2-1 + 1 × 2-2 + 1 × 2-3 = 0.25 + 0.125 = 0.375(10)
Ответ: 0.011(2) ® 0.375(10).
! Как уже было сказано, значение целого числа не зависит от формы его представления и выражает количество входящих в него единиц. Простая дробь имеет смысл доли единицы, и это «дольное» содержание также не зависит от выбора способа представления. Другими словами, треть пирога остается третью в любой системе счисления.
5.3 Перевод чисел между системами счисления с основанием 2k
Интерес к двоичной системе счисления вызван тем, что именно эта система используется для представления чисел в компьютере. Однако двоичная запись оказывается громоздкой, поскольку содержит много цифр, и, кроме того, она плохо воспринимается и запоминается человеком из-за зрительной однородности (только две цифры – 0 и 1).
Поэтому в нумерации ячеек памяти, записи кодов команд, нумерации регистров и устройств и пр., используются системы счисления с основанием 8 и 16.
Двоичная система счисления: р =2=21, цифры 0 и 1.
Восьмеричная система счисления: р =8=23, цифры (0,1,2,3,4,5,6,7).
Шестнадцатеричная система счисления: р = 16 = 24, цифры (0 ¸ 9, А, B, C, D, E, F).
В таблице 5.1 приведено соответствие между цифрами указанных систем счисления и цифрами десятичной системы.
Таблица 5.1 – Соответствие цифр систем счисления
| р =10 | р =2 | р =8 | р =16 |
| A B C D E F |
Выбор этих систем обусловлен тем, что переход от них к двоичной системе и обратно выполняется очень просто, в то же время для человека запись становится более компактной и удобочитаемой.
Правила перевода из двоичной системы счисления в систему счисления с основанием 2k:
1. разбить двоичную запись числа справа налево на группы по k разрядов. Эти группы цифр называются соответственно: для k = 2 – диада, для k = 3 – триада, для k = 4 – тетрада;
2. заменить каждую k- разрядную группу соответствующей цифрой из системы счисления с основанием 2 k.
Пример 5. Представить двоичное число 10111011101(2) в восьмеричной и шестнадцатеричной системе счисления
10111011101(2) ® Y(8); Y(16) ?
Разбиение на триады 010 111 011 101(2) ® 2735(8).
Разбиение на тетрады 0101 1101 1101(2) ® 5DD(16).
Обратное преобразование числа из системы счисления с основанием 2k в двоичную систему счисления выполняется аналогично:
– каждая цифра исходного числа заменяется группой из k разрядов, соответствующих представлению цифры в двоичной системе счисления.
Пример 6. Представить заданные числа в двоичной системе счисления. А02С(16) ® X(2); 357(8) ® X(2) ?
Ответ: 1010 0000 0010 1100(2) 011 101 111(2).
5.4 Формы представления вещественных чисел
Вещественное число X может быть представлено в двух формах – естественной и нормализованной.
В естественной форме у X имеется целая и дробная части, между которыми помещается разделитель (запятая или точка), например, 123.4567. Однако, такая запись неудобна для слишком больших, или, наоборот, для слишком малых чисел.
Кроме того, использование такой формы (она называется также представлением числа с фиксированной запятой) в компьютере вызвало бы снижение точности вычислений из-за необходимости приведения в соответствие разрядов обрабатываемых чисел и связанных с этим округлений; или могло бы породить ситуацию переполнения, когда старший разряд числа не умещается в отведенной разрядной сетке.
По этим причинам вещественные числа в компьютере представляются в нормализованном виде (представление числа в форме с плавающей запятой). Главным достоинством этой формы является автоматическое масштабирование числа на каждом этапе обработки, что, с одной стороны, обеспечивает максимальную точность, а с другой – избавляет от необходимости принимать меры по предотвращению переполнения.
Число X (10) называется нормализованным, если оно представлено в виде X (10) = ± M(10) ×10± k 10.
В этой записи М10 называется мантиссой нормализованного числа; значение мантиссы лежит в интервале 0,1 £ M(10) < 1;
k (10) называется порядком нормализованного числа – это целое положительное десятичное число.
Примеры нормализованного представления: 1234(10) = 0.1234 × 104 ;
0.00356 = 0.356 × 10-2 .
Понятие нормализованного числа следует отличать от понятия числа в нормальной форме (эту форму часто используют для записи чисел в математике, физике, технических дисциплинах). Мантисса в этой форме лежит в интервале 1 £ M(10) < 10.
Преобразование числа из естественной формы к нормализованному виду выполняется по следующим правилам.
1 ситуация. X (p) >1 – нормализация влево:
необходимо перемещать разделитель разрядов влево по числу до тех пор, пока не исчезнет целая часть числа, но первая цифра после разделителя будет ненулевой; показатель степени (порядок) должен возрастать на 1 при каждом сдвиге.
Например, 13756.23 = 0.1375623 × 105, 1.328 = 0.1328 × 101,
114.3 = 0.1143 × 103.
2 ситуация. X (p) < p-1 (X (10) <10-1) - нормализация вправо:
число X p необходимо умножать на основание системы р с одновременным уменьшением показателя на 1 до тех пор, пока первая цифра после разделителя станет ненулевой
Например, 0.000101 × 10-3 = 0.101 × 10-6, 0.000987 = 0.987 × 10-3.
5.5 Кодирование целых чисел в компьютере
Специфической особенностью представления чисел в регистрах и памяти компьютера является то, что, в отличие от записи числа на бумаге, компьютерные ячейки имеют ограниченный размер, и, следовательно, вынуждают использовать при записи чисел и действиях с ними конечное количество разрядов.
Это приводит к тому, что бесконечное множество вещественных чисел заменяется конечным множеством их представлений, которые называются кодами чисел, а обычные арифметические операции с числами заменяются операциями с кодами.
Способы кодирования и допустимые над ними действия оказываются различными для следующих числовых множеств:
целые положительные числа (целые числа без знака);
целые числа со знаком.
5.5.1 Кодирование в компьютере целых чисел без знака
Для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Размер одной адресуемой ячейки обычно составляет несколько байтов, например, 2 – такая комбинация связанных соседних ячеек, обрабатываемая совместно, называется машинным словом.
Конечный размер разрядной сетки порождает понятие «наибольшее целое число», которого в обычном представлении чисел просто не существует.
Если количество разрядов k и p =2, то Z max = 2 k –1.
Например, если k = 16, p = 2, то Z max = 216 – 1 = 11 … 1 = 65535(10).
Другими словами, целого числа, большего 65535(10), в компьютере просто не может существовать, и появление чисел, превышающих Zmax, должно интерпретироваться как ошибка.
Минимальным числом в беззнаковом представлении является
Zmin = 0 … 0 = 0.
Например, в языке Pascal тип целых чисел без знака, для записи которых отводится 2 байта, определен как Word, 1 байт – Byte. Тип устанавливает способ кодирования числа, количество отводимых разрядов для записи, а также перечень допустимых операций при обработке.
Выход за границу 65535(10) возможен только путем увеличения количества разрядов для записи числа, но это уже будет другой тип со своим Zmax.
(Например, тип LongInt, 4 байта – Zmax = 2147483647(10)).
Рассмотрим, как с беззнаковыми числами выполняется одна из наиболее часто используемых операций, не меняющая типа числа – сложение.
Сложение производится согласно таблице сложения (таблица 5.2).
Место, где сохраняется переносимая в старший разряд 1 до того, как она будет использована в операции, называется битом переноса.
Таблица 5.2 Сложение двоичных чисел.
| Перенос в следующий разряд Pi+1 | Результат S i | Слагаемые | Перенос из младшего разряда Pi-1 |
| 0 0 | |||
| 0 0 | |||
| 1 0 | |||
| 1 0 | |||
| 1 1 | |||
| 1 1 |
Пример 7. Найти сумму 1494(10) + 1392(10) при беззнаковой двоичной кодировке и 16-битном машинном слове для представления чисел.
Переведем исходные числа в соответствующие 16-битные двоичные представления (разбиение на тетрады – условное, для удобочитаемости).
1494(10) = 0000 0101 1101 0110(2);
1392(10) = 0000 0101 0111 0000(2).
Выполним сложение по правилам таблицы 5.2.
0000 0101 1101 0110
0000 0101 0111 0000
0000 1011 0100 0110
Проверим получившийся результат
211 + 29 + 28 + 26 + 22 + 21 =2048 + 512 + 256 + 64 + 4 + 2 = 2886(10).
Пример 8. Найти сумму коротких целых чисел (byte), для представления которых отводится 1 байт: 159(10) + 100(10)
159(10) = 1001 1111(2) 100(10) = 0110 0100(2)
Выполним сложение по правилам таблицы 5.2.
1001 1111
0110 0100
1 0000 0011 Перенос из старшего разряда называется битом переполнения. Ответ:0000 0011(2) = 3(10).
5.5.2 Кодирование в компьютере целых чисел со знаком
Кодирование целых чисел, имеющих знак, можно осуществить двумя способами. В первом варианте один (старший) разряд в машинном слове отводится для записи знака числа; при этом условились кодировать знак «+» - нулем, «-» - единицей.
Под запись самого числа остается (k -1) двоичных разрядов, что обеспечивает наибольшее значение числа Zmax = 2 k -1. Например, для k=16,
Zmax = 215 – 1 = 3276710.
Такое представление чисел называется прямым кодом.
Например, - 36(10) = 1 0010100 (знаковый разряд выделен),
+ 36(10) = 0 0010100.
Однако применение прямого кода усложняет порядок обработки чисел – например, операция сложения двух чисел с разными знаками должна быть заменена операцией вычитания меньшего из большего с последующим присвоением результата знака большего по модулю числа. Таким образом, операция сопровождается большим количеством проверок условий и выработкой признаков, в соответствии с которыми выбирается то или иное действие.
Альтернативным вариантом является представление чисел со знаком в дополнительном коде (ДК). Его применение позволяет заменить вычитание чисел их суммированием в дополнительных кодах.
Как строится дополнительный код?
Дополнением (D) k –разрядного целого числа Z (р) в системе счисления с основанием р называется величина D(Z p, k) = рk – Z.
Данную формулу можно представить в ином виде:
D(Z p, k) = ((рk -1) – Z) + 1. Число (рk -1) состоит из k наибольших в данной системе счисления цифр (р -1), например, 999(10), FFF(16) или 11111(2).
Поэтому дополнение числа Z может быть получено путем дополнения до (р - 1) каждой цифры числа Z и последующим прибавлением к последнему разряду 1.
Например, дополнение числа 278(10) D( 278(10), 3) = 7 2 1 + 1 = 722.
(дополнение 2 до 9 – 7, 7 до 9 – 2, 8 до 9 – 1).
!!! Важным свойством дополнения является то, что его сумма с исходным числом в заданной разрядной сетке будет равна 0.
В рассматриваемом примере
278 + 722 = 1 000 (выделенную 1 отбрасываем, она не входит в отведенную разрядную сетку k =3).
Так как в двоичной системе счисления дополнением 1 является 0, а дополнением 0 является 1, то построение D(Z2, k) сводится к инверсии данного числа (т.е. замене нулей единицами, и единиц нулями), и прибавлению 1 к последнему разряду.
Дополнительный код (ДК) целых чисел строится по следующим правилам:
первый разряд кодирует знак: знаку «+» соответствует 0, знаку «–» 1;
для Zp ³ 0 ДК совпадает с самим числом ДК = Zp;
для Zp < 0 ДК совпадает с дополнением модуля числа, то есть,
ДК = D(|Zp|).
Пример 9. Построить дополнительные коды заданных чисел. (Код знака отделен от кода числа).
1235(10) ДК = 0 1235 8632(16) ДК = 0 8632
- 1235(10) ДК = 1 8765 - 8632(16) ДК = 1 79CЕ
- 5790(10) ДК = 1 4210 10211(3) ДК = 0 10211
- 3204(5) ДК = 1 1241 - 10211(3) ДК = 1 12012
Пример 10. Построить дополнительный код чисел в двоичной системе.
- 10110111(2) ДК = 1 01001001.
- 11001101(2) ДК = 1 00110011.
Пример 10 позволяет сформулировать правило «механического» перевода в ДК отрицательных двоичных чисел: находим крайнюю правую 1, ее оставляем, а все цифры перед ней – инвертируем.
Так, для числа - 1110001101(2) ДК = 1 0001110011.
При использовании дополнительных кодов операция вычитания двух чисел как самостоятельная отсутствует – она заменяется сложением первого числа с дополнительным кодом второго, то есть просто сложением двух ячеек памяти. При этом знаковый разряд участвует в операциях по правилам двоичного сложения (см. в следующей главе).
Перевод в дополнительный код производится автоматически при вводе чисел; в таком виде числа хранятся в ОЗУ и затем участвуют в операциях. При этом операция вычитания отрицательного числа автоматически переводит число в прямой код и вместо вычитания производится сложение.
На следующем примере рассмотрим еще одну интересную особенность двоичных дополнительных кодов.
Чему соответствует код 10000000? Отрицательного нуля не бывает! Поэтому этот код является дополнительным кодом числа «–128». Именно поэтому нижняя граница диапазона возможных значений для целых чисел со знаком всегда по модулю больше на 1 верхней границы диапазона.
Так, для языка Pascal диапазоны возможных значений для соответствующих типов следующие:
Shortint (целый, 1 байт со знаком) – [- 128; + 127];
Integer (целый, 2 байта со знаком) – [ - 32768; 32767].
Приведенные особенности типов данных необходимо учитывать при программировании, чтобы избежать ситуаций, подобных приведенной в следующем примере.
Пример 11. Фрагмент программы:
L: integer; /* диапазон (- 32768 ¸ 32767)
k: byte; /* диапазон (0 ¸ 255)
…………….
L: = - 300; /* ДК 11111110 11010100
k: = L; /* k присваивается младший байт, что при переводе в десятичную систему дает k = 11010100(2) = + 212(10)
L: = +300; /* ДК 00000001 00101100
k: = L; /* в результате k = +44(10) .
5.6 Кодирование в компьютере вещественных чисел
Вернемся к обсуждению того обстоятельства, что в компьютере для записи числа в любой форме представления отводится конечное число разрядов.
Для целых чисел это приводит к появлению понятия наибольшего целого числа. Однако для каждого целого числа, не превышающего по модулю наибольшего, имеется только одно представление в машинном коде, и, если не происходит переполнения, результат выполнения операции над целыми числами будет точным.
Но ситуация коренным образом меняется при представлении и обработке вещественных чисел. На математической оси вещественные числа образуют непрерывное множество (континуум), то есть два числа могут находиться сколь угодно близко друг к другу, и на любом отрезке содержится бесконечное множество значений чисел.
В машинном представлении количество возможных значений чисел конечно: для двоичной системы оно определяется как 2 k, где k – количество двоичных разрядов в представлении мантиссы.
Таким образом, вещественные числа в компьютере заменяются их кодами, которые образуют конечное дискретное множество; каждый код оказывается представлением целого интервала значений континуума.
Из данного обстоятельства вытекает ряд следствий:
1) строгие отношения между числами континуума превращаются в нестрогие для их компьютерных кодов, то есть
если x 1 > x 2, то X 1 ³ X 2;
если x 1 = x 2, то X 1 = X 2;
если x 1 < x 2, то X 1 £ X 2;
2) поскольку код вещественного числа в компьютере является приблизительным представителем многих чисел из интервала, то и результаты вычислений также будут заведомо неточными, то есть содержать неизбежную погрешность.
В этом состоит главная особенность обработки вещественных чисел в компьютере – она всегда ведется с погрешностью (оценка этой погрешности – самостоятельная и непростая задача);
3) наряду с понятием наибольшего вещественного числа (из-за ограниченности разрядной сетки) появляется понятие наименьшего числа или машинного нуля.
Например, в типе Real языка Pascal любое число, по модулю меньше 2.3×10-39 оказывается машинным нулем, то есть считается равным 0 при сохранении и в операциях с ним.
Таким образом, понятие «0» как точное значение числа в компьютерном представлении заменяется понятием «машинный нуль» как значение числа меньше некоторой определенной величины.
Как уже было сказано, основной формой представления кодов вещественных чисел в компьютере является двоичная нормализованная. При этом записываться и храниться в памяти компьютера должны все составляющие нормализованной формы (знак числа, мантисса, знак порядка, порядок), что требует нескольких ячеек памяти.
Например, число типа Real в Pascal размещается в 6 байтах. Непосредственное распределение компонентов нормализованного числа по разрядам определяется конструктивными особенностями компьютера и программным обеспечением.
Например, возможно следующее распределение разрядов для размещения числа в 32 разрядах:
Номер бита
31 30 29 28 27 26 25 24 23 … 1 0
Знак порядок знак мантисса
порядка числа
Поскольку значение мантиссы, лежит в интервале 0.1(2)£ M<1, ноль в разряде целых и разделитель десятичных разрядов в представление не включается, то есть мантисса содержит только цифры дробной части.
Более того, можно не сохранять и первую значащую цифру мантиссы, поскольку она всегда 1 (но, естественно, восстанавливать ее при вычислениях) – это дает возможность хранить дополнительный «скрытый» разряд, то есть несколько повысить точность обработки.
Как и в случае целых чисел, для кодов вещественных чисел существует понятие переполнение, однако возникает оно не после заполнения разрядной сетки мантиссы – это приводит лишь к нормализации числа, а при заполнении всех разрядов порядка.
Для представленного выше примера размещения числа в 32-х битах, |X2max| = 0,1111 …1(2) × 2 111111» 2,147(10) ×109 (в мантиссе 24 единицы).
Причиной возникновения погрешности при обработке кодов вещественных чисел является ограниченность разрядной сетки при их представлении. Однако ее величина зависит от количества имеющихся разрядов, и, в частности, уменьшить погрешность можно за счет расширения разрядов сетки, то есть выделения большего количества ячеек памяти для записи числа.
Например, в языке Pascal определен вещественный тип Extended (10 байт), для которого точность мантиссы достигает 20 десятичных знаков и значение модуля порядка до 4932(10).
Следовательно, повышение точности вычислений требует б о льших ресурсов памяти компьютера; одновременно с этим возрастает и время вычислений. Таким образом, при составлении программы для практических задач, решается проблема нахождения компромисса между точностью расчета и временем обработки.
5.7 Двоично-десятичные коды
В двоично-десятичных кодах каждая цифра десятичного числа заменяется некоторым двоичным кодом, q двоичными разрядами с весами p1, … pq.
При S = 10 минимальное число двоичных разрядов, с помощью которых можно закодировать все десятичные цифры равно 4.
Число двоичных тетрад – 16, а число цифр – 10, следовательно, возможно неоднозначное соответствие тетрад цифрам (варианты кодирования).
Общее число способов кодирования, учитывая и абсолютно бессмысленные, равно 29 млрд. Следовательно, необходимо отобрать лишь те способы кодирования, которые являются удобными для использования в ЭВМ.
Требования, которым должны удовлетворять двоично-десятичные коды при намерении использовать двоично-десятичную систему в вычислительной технике, были сформулированы Рутисхаузером:
единственность – каждой десятичной цифре должна взаимно однозначно сопоставляться некоторая двоичная тетрада;
упорядоченность – б о льшим десятичным цифрам должны соответствовать б о льшие тетрады;
четность – четным десятичным цифрам соответствует четная тетрада, а нечетным – нечетная;
дополнительность – если цифры ai и aj являются десятичными дополнениями (2 и 7, 3 и 6 и т.п.), то соответствующие им тетрады должны быть инверсиями друг друга;
весомозначность – должна существовать такая четверка целых чисел p 1, p 2, p 3, p 4, называемая весами, что для любой цифры ai десятичной системы выполняется следующее:
если m4, m3, m2, m1 есть соответствующая цифре тетрада, то
ai = m 1 ×p 1 + m 2 ×p 2 + m 3 ×p 3 + m 4 ×p 4
Рассмотрим некоторые варианты двоично-десятичных кодов.
5.7.1 Код (8421) – код прямого замещения
В этом коде каждая десятичная цифра заменяется двоичным эквивалентом, записанным в 4-х разрядах.
Например, представим в коде (8421) следующие десятичные числа:
136(10) 0001 0011 0110 259(10) 0010 0101 1001
487(10) 0100 1000 0111 709(10) 0111 0000 1001
Код прямого замещения (КПЗ) удовлетворяет всем требованиям Рутисхаузера, кроме требования дополнительности.
Правило сложения в коде (8421) имеет вид (теоретическое обоснование правил не рассматривается):
1. выполнить по-тетрадное суммирование по правилам двоичного сложения с передачей переноса между тетрадами;
2. в те тетрады, где произошло десятичное переполнение, необходимо добавить поправку (+6) – 0110.
Пример 12. Найти сумму чисел
| а) 1052(10)+2697(10) 1052 0001 0000 0101 0010 26970010 0110 1001 0111 3749 0011 0110 1110 1001 0011 0111 0100 1001 3 7 4 9 Ответ: 1052(10)+2697(10) = 3749(10) | б) 579(10)+6023(10) 579 0000 0101 0111 1001 60230110 0000 0010 0011 6602 0110 0101 1001 1100 0110 0110 0101 1010 0010 0110 ____ 0110 0110 0000 0010 6 6 0 2 Ответ: 579(10)+6023(10) = 6602(10). |
Из-за того, что код (8421) не удовлетворяет принципу дополнительности, операция вычитания выполняется по усложненным правилам и в данном пособии рассматриваться не будет.
5.7.2 Код с избытком (+3)
Этот код не удовлетворяет требованиям весомозначности, но оказывается просто связанным с весомозначным кодом прямого замещения, обладая при этом удобными свойствами, упрощающими выполнение арифметических операций.
Код с избытком (+3) получается из кода прямого замещения путем добавления к каждой тетраде постоянного избытка (+3).
Приведем пример представления в данном коде некоторых десятичных чисел:
123(10) 0001 0010 0011 (КП3)
0100 0101 0110 (+3);
658(10) 0110 0101 1000 (КПЗ)
1001 1000 1011 (+3);
479(10) 0111 1010 1100 (+3).
Код с избытком (+3) удовлетворяет требованиям четности, единственности, упорядоченности, дополнительности.
Правила сложения в коде с избытком (+3) (теоретическое обоснование правил не рассматривается):
1. поправка (+3) добавляется в те тетрады, откуда при первоначальном суммировании был перенос и поправка (+12) – откуда переноса не было;
2. перенос, возникающий из тетрады при внесении поправок, учитывается в младшем разряде этой же тетрады;
3. для представления отрицательных чисел используется обратный код.
Пример 13. Найти сумму чисел.
| а) 402(10) +79(10) 402 0111 0011 0101 790011 1010 1100 481 1010 1110 0001 1100 1100 0011 / поправки 0110 1010 0100 1 1 / перенос из- за поправок 0111 1011 0100 4 8 1 Ответ: 402(10) +79(10) = 481(10). | б) 402(10) -79(10) 402 0111 0011 0101 -791100 0101 0011 323 0011 1000 1000 1 / перенос при сложении в ОК 0011 1000 1001 0011 1100 1100 / внесение поправок 0110 0100 0101 1 1 / перенос из-за поправок 0110 0101 0110 3 2 3 Ответ: 402(10) -79(10) = 323(10). |
Еще раз повторим и обобщим сказанное в данной главе:
1. в компьютере арифметические устройства выполняют действия не с самими двоичными числами по правилам двоичной арифметики, а с их двоичными кодами (представлениями) по правилам арифметики двоичных кодов;
2. причиной отличий правил арифметики двоичных кодов от правил обычной арифметики является ограниченность разрядной сетки, применяемой для записи чисел в компьютере.
По этой же причине отличаются понятия «ноль» и «машинный ноль», «бесконечность» - «максимальное число», а также становится возможной ситуация переполнения, что требует ее постоянного отслеживания;
3. применение при вычислениях формы представления чисел с плавающей запятой обеспечивает единообразие при их записи и обработке, и, что важно, в результате автоматического масштабирования числа на каждом этапе его обработки сокращается погрешность вычислений;
4. различие правил обработки целых и нормализованных чисел приводит к необходимости точного описания типов переменных перед их использованием в программах. Вторая причина описания типов состоит в оптимизации расходования памяти компьютера, поскольку числа разных типов требуют для хранения различных ресурсов памяти.
Дата публикования: 2014-12-30; Прочитано: 1000 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
