Универсальная система кодирования
Исторически системы счисления возникали как системы кодирования информации о количестве чего-либо. Всем известны арабская десятичная и римская системы счисления. В римской системе счисления каждому количеству ставится в соответствие число (код), представляющее собой специфическое сочетание символов (XIV, CXXVII и т.п.). Недостатком римской системы счисления является то, что она не даёт общего правила получения уникального кода для любого количества. Это означает, что в практической деятельности может возникнуть необходимость обозначать такие количества, для которых в римской системе счисления соответствующие числа не придуманы. Арабская десятичная система счисления лишена этого недостатка. Это связано с тем, что арабская система счисления определяет правило формирования знака (числа) для любого количества, используя ограниченный набор базовых (исходных) знаков (цифр). При этом число представлялось состоящим из необходимого количества позиций, заполненных цифрами по определенному правилу. Поэтому арабская система счисления называется позиционной системой счисления. Важность открытия арабами позиционной системы счисления с точки зрения информатики заключается в том, что позиционная система счисления оказалась универсальной системой кодирования информации. Действительно, любая информация с заданной степенью точности может быть представлена в дискретной форме, состоящей из перечисляемой совокупности элементов. Каждый такой элемент, сколько бы их не было, может быть обозначен (закодирован) числом позиционной системы счисления. Следовательно, любая исходная информация может быть преобразована в конечную или счетную совокупность чисел. Учитывая важность открытого арабами принципа позиционного кодирования информации, рассмотрим его более подробно и проиллюстрируем на примерах различных систем счисления.
В позиционной системе счисления определяется исходный (базовый) набор знаков, которые называют цифрами. Количество (P) различных цифр в наборе называется основанием системы счисления. Цифры – это уникальные знаки, которые обозначают количественные значения в пределах от 0 до P-1. Для системы счисления с основанием 10 (десятичной системы счисления) соответствие между количественными значениями и цифрами следующее:
пусто - 0
h - 1
hh - 2
hhh - 3
hhhh - 4
hhhhh - 5
hhhhhh - 6
hhhhhhh - 7
hhhhhhhh - 8
hhhhhhhhh - 9
Для количества большего P-1 строится составной знак (число). Число представляет собой последовательность значащих и незначащих разрядов (позиций), первоначально заполненных цифрой 0. Разряды располагаются по порядку справа налево и их количество не ограничено. Самый правый (первый) разряд называется младшим разрядом. В каждом разряде располагается цифра. Последний (самый левый), отличный от 0 разряд, называется старшим разрядом числа. Остальные следующие за ним разряды, заполненные нулями, называются незначащими и в изображении числа участия не принимают. Число как минимум состоит из одного разряда, даже если он содержит 0.
Чтобы сопоставить заданному количеству соответствующее число, его необходимо сосчитать. Алгоритм счета, записанный на псевдокоде, выглядит следующим образом:
АЛГОРИТМ Формирование числа
ВВЕСТИ(количество, цифры_основания_системы_счисления)
<Встать в младший разряд формируемого числа>
ЦИКЛ<Количество не пусто>
ЕСЛИ<В разряде не последняя цифра системы счисления>ТО
<Заменить цифру в разряде следующей по порядку цифрой>
<Встать в младший разряд формируемого числа >
<Уменьшить количество на 1>
ИНАЧЕ
<В разряд поместить 0>
<Перейти к следующему по порядку разряду числа>
ВСЕ_ЕСЛИ
ВСЕ_ЦИКЛ
ВЫВЕСТИ(Число)
ВСЕ_АЛГОРИТМ
Для дробных значений кодирование выполняется по такому же принципу, только подсчитываются доли, на которые делится целое.
В общем случае запись любого смешанного числа
N= цm-1 цm-2. . .ц1 ц0, ц-1 ц-2. . .ц-s
в системе счисления с основанием P можно представить в виде суммы:
N = цm-1Pm-1+ цm-2P m-2+ . . . + ц1P1+ ц0P0+ ц-1P-1+ ц-2P –2+ . . . + ц-sP –s (1)
где цi – цифры, принимающие значения 0, 1, 2, …, P-1; нижние индексы определяют местоположение цифры в числе (разряд): положительные значения индексов – для целой части числа (m разрядов); отрицательные значения – для дробной части числа (s разрядов). Например, десятичное число 123410 представляется рядом вида: 123410 = 1×103 + 2×102 + 3×101 + 4×100.
Если количество разрядов в числе ограничить, то максимальное целое число, которое может быть представлено в m разрядах будет равно:
Nmax= Pm-1.
Минимальное значащее (не равное 0) число, которое можно записать в s разрядах дробной части будет равно:
Nmin= P-s.
Имея в целой части только m, а в дробной части только s разрядов, можно записать всего Pm+s разных чисел.