Lection02

Лекция 2. Системы счисления с целым основанием

разряд цифры того же знака, что и слагаемые, и установки в текущем разряде цифры противоположного знака. Пример:

204 +79 = 283

20410 =10 1 1 103

7910 =100113

Проведем процедуру сложения столбиком в троичной уравновешенной системе счисления:

1 0 1 1 1 0 + 1 0 0 1 1

1 0 1 1 1 1

1011113 =35 +33 +32 +31 +30 = 28310

Приведем пример сложения чисел с разными знаками: –204 + 79. В троичной уравновешенной системе счисления эти числа

выглядят следующим образом:

Для проверки переведем получившееся число в десятичную систему счисления:

1111013 = −35 +34 +33 +32 +30 = −12510

Перевод целых десятичных чисел в троичную уравновешенную систему счисления

Очевидно, что для перевода числа из десятичной системы счисления в троичную следует пользоваться стандартным алгоритмом перевода, при котором число в десятичной системе счисления делится нацело на новое основание 3, находится остаток и частное от деления, затем частное от деления снова делится на основание 3, и т.д. пока частное от деления не станет меньше основания. Для того чтобы понять, как связаны числа в троичной и в троичной уравновешенной системах счисления, рассмотрим, как можно представить двойку n-го разряда троичного числа, т.е. число 2 3n (n – целое): 2 3n =(3 −1)3n =3n+1 −3n .

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

35

Принципы построения цифровых вычислительных систем

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

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

Алгоритм

1.Выполнить деление исходного числа на 3 в десятичной системе счисления.

2.Если остаток от деления равен 2, записываем его как 1 , а к результату от деления добавляем 1; если результат меньше 2 (т. е. 1 или 0), оставить его без изменений.

3.Делить результат на 3 и повторять действия, описанные в п. 2; деление продолжается до тех пор, пока целая часть не будет равна 0.

4.Переписать полученные значения остатков (снизу вверх), начиная с последнего результата деления.

Пример

Переведем по предложенному правилу число 15810 в троичную уравновешенную систему счисления.

Результаты перевода сведены в таблицу:

Итак, 15810 =1100113

Второй способ перевода в троичную уравновешенную систему предложен известным программистом Дональдом Кнутом. Его суть заключается в следующем. Сначала записываем произвольное число A = 208,3 в обычной троичной системе счисления.

36

Лекция 2. Системы счисления с целым основанием

208,310 = 21201,022002200220...3 .

Очевидно, что если к этому числу добавить другое число B и затем его же вычесть, то в результате получится то же самое число A. Возьмем в качестве B бесконечное число, состоящее из одних единиц:

B = …11111111,11111111…; в результате получим:

A + B =(...111210012,210121012101...)3 .

Теперь вычтем из суммы число B, причем при вычитании 1 из 2 получаем в результате 1, при вычитании 1 из 1 получаем 0, а при

вычитании 1 из 0 получаем в результате 1 .

208,310 =(10 1 101,10 1010 1010 10...)3 .

На самом деле, число B, которое нужно прибавить к произвольному числу A, является конечным. Для получения корректного результата длина числа B (количество разрядов) должна быть не меньше длины числа A.

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

Алгоритм.

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

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

3.Из полученного числа вычесть промежуточное число, состоящее из одних единиц, по следующим правилам: при вычитании 1 из 2 результат 1, при вычитании 1 из 1 результат 0,

а при вычитании 1 из 0 результат 1 .

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

Очевидно, что уравновешенная троичная система счисления обладает многими привлекательными свойствами, в частности:

отрицание числа осуществляется взаимной заменой 1 и 1 ;

знак числа задается его наиболее значимым ненулевым тритом;

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

естественное представление отрицательных и положительных чисел позволяет не использовать дополнительный код числа, как

37

Принципы построения цифровых вычислительных систем

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

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

38

Лекция 2. Системы счисления с целым основанием

Контрольные вопросы и задания

1.Дайте определение системы счисления с натуральным основанием.

2.Дайте определение базиса и основания системы счисления.

3.Назовите преимущества троичной уравновешенной системы счисления.

4.Переведите целые числа из десятичной системы счисления в двоичную, шестнадцатеричную, восьмеричную и троичную уравновешенную системы счисления:

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

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

39

Принципы построения цифровых вычислительных систем

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

110111 10101101 11010110 1101, 101 10110,1011 110101,0101

1010101 11100101 11011110 1111,101 11101, 101 100111,1101

10. Проведите следующие арифметические вычисления «столбиком» в двоичной системе счисления.

11001011+11001

10101011+11011001

10011 10101

11011 1111

Список литературы к лекции 2

1.Кнут Д.Э. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. - М.: Издательский дом

"Вильямс", 2000. - 832 с.: ил.

2.Андреева Е., Фалина И. Информатика: Системы счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний, 1999. – 256 с. : ил.

3.Фомин С.В. Системы счисления. – 4-е изд. – М.: Наука, Гл. ред. физ.-мат. лит. – 48 с.

40