Степени S играют в естественной системе счисления роль весов разрядов. Нулевому разряду сопоставляется 5° = 1. . .

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

В заключение введения отметим, что запись некоторого количества в определенной системе счисления

будем в дальнейшем называть кодом числа. При этом запись {x)f означает код числа (количества) x в системе счисления R. Для естественных систем счисления с основанием S код числа х в этой системе записывается как {x)g. Там, где это не приводит к недоразумению, «запись [(йу)]о будет заменяться за-

,ПИСЬЮ" (Uj).

Глава первая

СИСТЕМЫ СЧИСЛЕНИЯ С НАТУРАЛЬНЫМ ОСНОВАНИЕМ

§ 1.1. Общие свойства систем

•Для задания системы с натуральным основанием S необходимо задать алфавит цифр A = {ai, а,... а„\, каждому элементу которого сопоставить его количественный эквивалент в нулевом разряде. Алфавит весов специально задавать нет необходимости, так как этот алфавит всегда имеет вид

Р~{ ... , 5*, ... , 1, S ... , S ...\,

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

х= "f [{aj)lSK (1.1)

Таким образом, каждый код числа можно рассматривать как бесконечный ряд по степеням S.

Естественно ввести некоторые очевидные требо-. вания к рассматривающимся системам счисления. ;. 1. Однозначность. Каждому числу л: должен ,г соответствовать единственный код, и наоборот.

2. Конечность. Каждому .целому числу л: дол-.жен сопоставляться код конечной длины. ; 3. Эффективность. Существует алгоритм, .с помощью которого за конечное число шагов возможен лереход от кода числа (для конечного кода) к самому числу. При переходе от числа к его коду • для целого числа должен существовать алгоритм, . реализующий этот переход за конечное-число шагов. Для дробного числа х должен существовать алгоритм,

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

Мы будем рассматривать, в основном, системы счисления, обладающие этими тремя свойствами. И лишь в исключительных случаях будут рассматриваться системы, не обладающие свойством однозначности или конечности.

Определение. 1.1. Системы счисления с натуральным основанием S, удовлетворяющие требованиям конечности и эффективности, но не удовлетворяющие требованию однозначного кодирования хотя бы для одного числа х, называются избыточными. * . Определение 1.2. Системы счисления, удовлетворяющие требованиям однозначности, конечности и эффективности, называются каноническими.

/Рассмотрим вначале канонические системы. Пусть цифрам из множества А сопоставлены, в нулевом разряде только положительные целые количественные эквиваленты. В этом случае из соотношения (1.1) вытекает, что все числа х, коды которых могут быть получены в данной канонической системе счисления, являются положительными. Для получения кода числа, соответствующего количеству нуль, необходимо иметь среди А цифру О, которой сопоставлено количество Нуль. В силу конечности представления для целого числа имеем

1 = [{aj)l-S + ... + [{aj)],.S + [{aj)U.S- + ... +

Это означает, что для представления числа, равного единице, мы можем использовать либо цифру с количественным эквивалентом, равным единице (в этом случае число единица будет представляться как ... 01,00...), либо цифру вида S" (тогда число единица будет представляться как ... 0,0 ... 05"0 ... , где S" стоит в разряде с весом S~". Однако второй способ представления единицы по сравнению с первым способом не дает ничего принципиально нового, так как в этом случае можно просто переместить запятую так, чтобы разряд с весом S" стал нулевым разрядом (другими словами, умножить веса всех разрядов