Федотова Мария

 

ИНФОРМАЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

 

Целью настоящей работы является описание нового широкого класса систем счисления, обобщающего башенные [2] и итерационные [1].

 

Начнем с уточнения терминологии.

 

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

 

Среди универсальных наиболее широкое распространение получили основные позиционные системы счисления (прежде всего, десятичная, а также двоичная и шестнадцатеричная). Слово «позиционная»  означает, что значение каждой цифры зависит не только от написания, но и от ее места в записи числа. Слово «основная» указывает на то, что вес каждой цифры изменяется в одно и то же число раз при переходе от одного разряда к соседнему. Само это число и есть основание – 10, 2, 16 или любое другое.

 

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

 

Далее описывается конструкция, позволяющая преодолеть этот недостаток.

 

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

 

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

 

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

 

На втором шаге нужно разбить на два интервала выбранный на старте луч. Ясно, что один из этих интервалов будет отрезком, а второй – лучом.

 

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

 

Не так важно, какие именно символы будут использованы в качестве цифр. Точнее всего передают смысл знаки «<» и «>» , либо «+» и «-» , но можно использовать обычные цифры 0 и 1 или цифры N и P, как в троичной уравновешенной, башенной [2] и итерационной [1] системах счисления.

 

Выбор последующих точек разбиения может быть произвольным. Но ясно, что правило их выбора должно быть фиксировано заранее (и не зависеть от числа t). Если в качестве точек разбиения будут выбраны корни последовательных итераций некоторой монотонной функции, то получится соответствующая итерационная система счисления [1]. А если эта функция – логарифм, то башенная [2].

 

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

 

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

 

Для примера я переведу в такую систему счисления номер своей школы – 114. В двоичной системе счисления этот номер записывается как 1110010. Теперь проверим, что получится в записи по правилу предыдущего абзаца.

 

Так как 114>0 , то знак числа - «+». Так как 114>1, 114>2, 114>4, 114>8, 114>16, 114>32 и 114>64, то первые 7 цифр – единицы. Так как 114<128, то восьмая цифра – ноль. Затем делим пополам интервал между 64 и 128. Середина – 96. Так как 114>96, то девятая цифра – 1. Делим пополам интервал между 96 и 128. Середина – 112. Так как 114>112, то и десятая цифра – 1. Делим пополам интервал между 112 и 128. Середина – 120. Так как 114<120, то 11-ая цифра – ноль. Следующая середина – 116. Так как 114<116, то 12-ая цифра – ноль. Наконец, очередная середина совпала со 114. Запишем 1, а все последующие цифры – 0 (их можно не писать). Получили 1111111011001.

 

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

 

 

Литература

 

1. Баранова Н.В. Итерационные системы счисления. 6-ая Межд. конф. молодых ученых памяти С.Н.Бернштейна. СПб, 2000.

2. Федотов В.П. Башенные системы счисления.- В сб. "Информационные технологии в образовании. К 80-летию РГПУ им. Герцена". СПб, 1998.