Часть 7 Вопросы 19-21

Экономичность системы счисления.

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

Речь в данном случае идет не о количестве разрядов, а об общем количестве сочетаний цифр, которые интерпретируются как различные числа. Поясним на примере: пусть в нашем распоряжении имеется 12 цифр. Мы можем разбить их на 6 групп по 2 цифры («0» и «1») и получить шестиразрядное двоичное число; общее количество таких чисел, как уже неоднократно обсуждалось, равно 2⁶. Можно разбить заданное количество цифр на 4 группы по три цифры и воспользоваться троичной системой счисления – в этом случае общее количество различных их сочетаний составит 3⁴. Аналогично можно произвести другие разбиения; при этом число групп определит разрядность числа, а количество цифр в группе – основание системы счисления. Результаты различных разбиений можно проиллюстрировать таблицей:

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

Точное расположение максимума экономичности может быть установлено путем следующих рассуждений. Пусть имеется n знаков для записи чисел, а основание системы счисления p. Тогда количество разрядов числа k = n/p , а общее количество чисел (N), которые могут быть составлены, равно:

Если считать N(p) непрерывной функцией, то можно найти то значение p_m, при котором N принимает максимальное значение. Функция имеет вид, представленный на рис.3.

Зависимость количества чисел от основания системы счисления при использовании 12-ти возможных цифр для записи чисел.

Для нахождения положения максимума нужно найти производную функции N(p), приравнять ее к нулю и решить полученное уравнение относительно p.

Приравнивая полученное выражение к нулю, получаем ln p = 1, или p_m = e, где e=2,71828… – основание натурального логарифма. Ближайшее к e целое число, очевидно, 3 – по этой причине троичная система счисления оказывается самой экономичной для представления чисел. В 60-х годах в нашей стране была построена вычислительная машина «Сетунь», которая работала в троичной системе счисления. Предпочтение все же отдается двоичной системе, поскольку по экономичности она оказывается второй за троичной, а технически она реализуется гораздо проще остальных. Таким образом, простота технических решений оказывается не единственным аргументом в пользу применения двоичной системы в компьютерах.

Перевод чисел из 2-чной системы счисления в систему с основанием 8 и 16 и обратно.

Интерес к двоичной системе счисления вызван тем, что именно эта система используется для представления чисел в компьютере. Однако двоичная запись оказывается громоздкой, поскольку содержит много цифр, и, кроме того, она плохо воспринимается и запоминается человеком из-за зрительной однородности (все число состоит из нулей и единиц). Поэтому в нумерации ячеек памяти компьютера, записи кодов команд, нумерации регистров и устройств и пр. используются системы счисления с основаниями 8 и 16; выбор именно этих систем счисления обусловлен тем, что переход от них к двоичной системе и обратно осуществляется, как будет показано ниже, весьма простым образом.

Двоичная система счисления имеет основанием 2 и, соответственно, 2 цифры: 0 и 1.

Восьмеричная система счисления имеет основание 8 и цифры 0, 1,…, 7.

Шестнадцатеричная система счисления имеет основание 16 и цифры 0, 1, …, 9, A, B, C, D, E, F. При этом знак «A» является 16-ричной цифрой, соответствующей числу 10 в десятичной системе; B₁₆ = 11₁₀; С₁₆ = 12₁₀; D₁₆ = 13₁₀; E₁₆ = 14₁₀; F₁₆ = 15₁₀. Другими словами, в данном случае A … F - это не буквы латинского алфавита, а цифры 16-ричной системы счисления и поэтому они имеют только такое начертание (не могут быть представлены в виде, например, соответствующих строчных букв, как в текстах).

Пользуясь алгоритмами, сформулированными в разделе 4.2.1, можно заполнить таблицу:

Теорема 1. Для преобразования целого числа Z_p Z_q в том случае, если системы счисления связаны соотношением q = p^r, где r - целое число большее 1, достаточно Z_p разбить справа налево на группы по r цифр и каждую из них независимо перевести в систему q.

Пример 6

Выполнить преобразование Z₂ = 110001₂ Z₈. Исходное число разбивается на группы по три разряда справа налево (8 = 2³, следовательно, r = 3) и каждая тройка в соответствии с таблицей 4.1. переводится в 8-ричную систему счисления независимо от остальных троек:

Следовательно, 110001₂ = 61₈ . Аналогично, разбивая Z₂ на группы по 4 двоичные цифры и дополняя старшую группу незначащими нулями слева, получим 110001₂= 31₁₆.

Теорема 2. Для преобразования целого числа Z_p Z_q в том случае, если системы счисления связаны соотношением p = q^r, где r - целое число большее 1, достаточно каждую цифру Z_p заменить соответствующим r-разрядным числом в системе счисления q, дополняя его при необходимости незначащими нулями слева до группы в r цифр.

Пример 7 Выполнить преобразование D3₁₆ Z₂.

Переходы Z₈ Z₁₆ и Z₁₆ Z₈, очевидно, удобнее осуществлять через промежуточный переход к двоичной системе. Например, 123₈ = 001010011₂ = 53₁₆.