Позиционные системы счисления

Системой счисления называется совокупность приемов записи чисел. Запись числа в некоторой системе счисления называют кодом числа. Отдельную позицию в изображении числа называют разрядом, а номер позиции – номером разряда. Любая система счисления, предназначенная для практического использования, должна обладать следующими свойствами:

– возможностью представления любого числа в заданном диапазоне;

– однозначностью представления чисел;

– простотой оперирования числами.

Системы счисления можно разделить на позиционные и непозиционные. К последним относится, например, римская система счисления. Основными недостатками непозиционных систем счисления являются:

– отсутствие нуля;

– необходимость использования бесконечного количества символов;

– сложность арифметических операций над числами.

Позиционными называют системы счисления, алфавит которых содержит ограниченное число символов, а значение каждой цифры числа определяется ее местоположением в числе. Например, десятичное число 545 означает 5 сотен, 4 десятка и 5 единиц.

В общем виде число в позиционной системе счисления может быть представлено как

,

где – цифра i-го разряда числа, ; – основание системы счисления.

Позиционные системы счисления подразделяются на неоднородные и однородные.

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

A = 5∙365∙24∙60∙60∙1+10∙24∙60∙60∙1+22∙60∙60∙1+11∙60∙1+50∙1

является записью времени в 5 лет, 10 суток, 22 часа, 11 минут, 50 секунд. В этом примере p₄ = 365 суток, p₃ = 24 часа, p₂ = 60 минут, p₁ = 60 секунд, p₀ = 1 секунда.

Однородные позиционные системы счисления характеризуются тем, что в них веса отдельных разрядов числа представляют собой ряд членов геометрической прогрессии со знаменателем p. Число в таких системах счисления представляется полиномом вида

,

причем целой части числа соответствует полином

,

а дробной части – полином

.

Здесь, как и ранее, – цифры числа, p – натуральное целое число, называемое основанием системы счисления. Следует помнить, что основание p записывается числом «10» в своей системе счисления.

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

Примером такой системы может служить так называемая двоично-десятичная система представления чисел (D-код), в которой каждой цифре десятичного числа соответствует двоичная тетрада с весами 8421. Например, десятичное число 259 в двоично-десятичной системе с естественными весами 8421 запишется как

D-код 8421 редко применяется в вычислительной технике, поскольку он не является самодополняющимся, т.е. двоичные коды любых двух десятичных цифр, дополняющих друг друга до 9 (их сумма равна 9), не дополняют друг друга до 15. Примером самодополняющегося D-кода является D-код 8421+3 с потетрадным избытком 3, в котором вышеприведенное число 259 запишется как

Более подробно о D-кодах см. в разделе 1.5.

1.2. Обоснование применения в ЭВМ
двоичной системы счисления

При выборе системы счисления для применения в ЭВМ следует учитывать совокупность различных параметров, среди которых можно выделить:

– наличие физических элементов для представления и хранения цифр системы;

– экономичность системы, т.е. количество элементов, требуемых для представления и хранения многоразрядных чисел;

– быстродействие вычислительных устройств;

– высокую помехоустойчивость кодирования цифр.

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

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

Оценим экономичность использования различных систем счисления. Для этого введем некоторую оценочную величину , пропорциональную количеству деталей оборудования [4], где индекс i соответствует i-й системе счисления, а – число разрядов.

Количество чисел, которые можно представить в i-й системе счисления, определяется следующим образом:

,

откуда

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

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

получим следующий вывод: оптимальное значение основания системы счисления равно основанию натурального логарифма, т.е. p_опт = e » 2,7182. Для определения экономичности системы счисления с целочисленным основанием введем относительное значение

откуда, с учетом предыдущих формул, получим

Сведем в таблицу решения вышеприведенного уравнения для различных целочисленных оснований систем счисления.

Таблица 1.1

Основание
	1,062	1,005	1,062	1,143	1,598

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

Рассмотрим еще один критерий оценки систем счисления с разными основаниями – по быстродействию выполнения арифметических операций. В качестве характеристики быстродействия выберем количество элементарных сложений, выполняемых при умножении n-разрядных p-ичных чисел.

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

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

Таблица 1.2

Основание
	1,000	1,262	1,500	1,725	2,709

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

1.3. Представление двоичных чисел с фиксированной
и плавающей запятой

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

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

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

На рис. 1.1 изображено машинное представление n-разрядного числа с фиксированной после знакового разряда запятой.

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

Величины двоичных чисел (правильных дробей), представляемых в машинах с фиксированной запятой, лежат в пределах

а диапазон представления чисел в машине с фиксированной запятой равен

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

где a – правильная дробь, удовлетворяющая условию , называемая мантиссой числа; p – основание системы счисления; m – целое положительное или отрицательное число, называемое порядком числа, указывающее местоположение запятой в числе.

На рис. 1.2 изображено машинное представление числа с плавающей запятой.

Максимальное по абсолютной величине число, которое может быть представлено в машине с плавающей запятой, определяется как

,

однако, учитывая, что при больших n величина мала, ею можно пренебречь.

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

а диапазон представления чисел в машине с плавающей запятой равен

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