Материалы к докладу
Классификация систем счисления
на 7-ой Международной конференции памяти П.Л.Чебышева
(Санкт-Петербург, СПбГУ, февраль 2002г.,
докладчик - Федотова М.В. ,
научный руководитель - Федотов В.П.)
Текст цитируемого доклада
ИНФОРМАЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
докладчик - Федотова Мария, тогда я училась в 9 кл. гимн. № 114 СПб,
научный руководитель - Федотов В.П.)
В последние годы появились несколько публикаций, в которых были введены новые
системы счисления. В 1998г. мой научный руководитель
Федотов В.П. [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] системах счисления.
Выбор последующих точек разбиения может быть произвольным. Но ясно, что правило их
выбора должно быть фиксировано заранее (и не зависеть от числа). Если
в качестве точек разбиения будут выбраны корни последовательных итераций
некоторой монотонной функции, то получится соответствующая итерационная система
счисления [1]. А если эта функция – возведение в степень, то башенная
[2].
Специальный выбор точек разбиения позволяет получить и такие информационные системы
счисления, которые будут представлять собой лишь модификацию обычной записи
числа (в двоичной, двоично-десятичной или иной системе). Это очень удобно, так
как, с одной стороны, облегчит перевод чисел из одной системы в другую и
обратно, но при этом избавит традиционную запись от недостатка, о котором было
сказано выше.
Например, возьмем геометрическую прогрессию со знаменателем 2 и будем сравнивать t с ее
членами. Пока t остается больше каждого очередного из этих чисел,
пишем 1. А после первого нуля в записи
t соответствующий отрезок на
каждом последующем шаге делим пополам. Тогда все последующие цифры в точности
совпадут с цифрами обычной двоичной записи числа t.
Для примера я переведу в такую систему счисления номер своей школы – 114. В
двоичной системе счисления этот номер записывается как 1110010. Теперь
проверим, что получится в записи по правилу предыдущего абзаца.
Так как 114>0 , то знак числа – «+». Запишем вместо него цифру 1. Так как
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, то и 11-ая цифра – 1. Делим пополам интервал между 112 и
128. Середина – 120. Так как 114<120, то 12-ая цифра – ноль. Следующая
середина – 116. Так как 114<116, то 13-ая цифра – ноль. Наконец, очередная
середина совпала со 114. Запишем 1, а все последующие цифры – 0 (их можно не
писать). Получили 11111111011001.
Сравнение последней записи с двоичной записью того же числа позволяет сформулировать
общее правило преобразования (модификации). Сначала в обычной двоичной записи
отбрасываются все незначащие цифры: последние нули (сколько бы их ни было) и
первая единица (так как нули впереди числа не пишутся, а цифр в двоичной
системе счисления всего две, то двоичная запись всегда начинается с единицы,
которая почти не несет никакой информации). Вместо отброшенной спереди единицы
пишется ноль, а перед ним столько единиц, сколько цифр было в целой части
исходного числа. Наконец, в случае положительного числа впереди вместо знака
пишется еще одна единица, а минус отрицательного числа заменяется нулем.
В описанном примере использовались две цифры (0 и 1) и на каждом шаге интервал
делился пополам. Ясно, что совершенно аналогично можно делить интервал и на
большее число частей, используя для их указания соответствующее количество
цифр. Всевозможные возникающие при этом системы счисления я предлагаю называть
интервальными.
Наконец, если при разбиении допускать множества, не
являющиеся интервалами, то появляется более широкий класс систем счисления,
которые я предлагаю называть информационными.
Литература