Лекция 2. Системы счисления в машинной арифметике цифровых ЭВМ

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

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

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

Для определения количественного эквивалента полной записи числа исполь-зуется некоторая функция от количественных экви­валентов совокупности цифр в его записи. Если этой функцией яв­ляется функция сложения, то система счисления называется аддитивной, если умножения – то мультипликативной. Для большинства существующих систем счисления указанная функ­ция является функцией десятич- ного сложения. В этом случае для нахождения количественного эквивалента чис- ла необходимо про­суммировать все количественные эквиваленты цифр в его запи- си по правилам десятичной арифметики.

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

Преимущественное распространение в ВТ получили однородные позицион- ные системы счисления. Во всех разрядах числа, представ­ленного в однородной системе, используются цифры из одного и то­го же множества. Например, в обыч- ной десятичной системе во всех разрядах любого числа используются цифры из множества {0, 1,..., 9}, в двоичной системе — цифры из множества {0, 1} и т. п. В од­нородной позиционной системе при непосредственном представлении цифр число записывается в виде

 

(1)

 

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

(2)

где х_i – цифры i -го разряда записи числа, принимающие значения из определенно- го множества, a k называется основанием системы счисления и равно количеству цифр, используемых в данной систе­ме. Величину kⁱ принято называть весом i -го разряда. В n -разрядном слове (1), где п = s + т + 1, целая часть числа представ- лена s + 1 разрядами слева от запятой, а дробная часть – т разря­дами справа от запятой. В данном случае вес i -го разряда в k раз больше веса i – 1-го разряда. Такая система счисления называется системой с естественным порядком весов (естественной). Существу­ют также системы с искусственным порядком весов, для которых указанное соотношение весов соседних разрядов не является обя­затель- ным. Известны, например, системы с искусственным поряд­ком весов, в которых целое положительное число X выражается как

где j может принимать одно из значений, принадлежащих множеству {1, 2,..., п }, т.е. j { 1, 2,..., п }. При k = 2, j = 3 веса разрядов в такой системе образуют ряд 2⁰, 2¹, 2², 2⁰ (2³ - 1), 2¹ (2³ - 1),... или 1, 2, 4, 7, 14,... Такие системы применяются в средствах ВТ, оптими­зированных по некоторым показателям (например, по потребляе­мой мощности), для создания высоконадежных вычис-лительных средств и для кодирования цифр других систем счисления с боль­шим основанием.

Системы с естественным порядком весов различают также по виду основа- ния k. Известны, например, системы с натуральными, отрицательными, дробными, комплексными основаниями. Наиболь­шее распространение в ВТ получили системы счисления с натураль­ными основаниями. Однако другие системы обладают рядом особен­ностей, которые в некоторых случаях делают их более эффективны­ми, чем системы с натуральными основаниями.

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

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

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

К применяемым вВТ системам счисления предъявляются следу­ющие оче-видные требования.

Однозначность. Каждому числу должно соответствовать единст­венное его представление в заданной системе и наоборот.

Конечность. Каждому целому числу должно сопоставляться сло­во конечной длины.

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

Системы счисления с натуральным основанием, удовлетворя­ющие требова-ниям однозначности, конечности и эффективности, на­зываются каноническими. Для таких систем цифра 0 (нуль) является обязательной, а количество различных цифр равно основанию k.

В зависимости от множества цифр, допустимых в каждом разря­де, систе- мы счисления делятся на симметричные, смещенные и кососимметричные. Систе- мы счисления с нечетными натуральны­ми основаниями k = 2 r + 1 и цифрами x_i {- r,- r + 1,..., 0,..., r }называются симметричными. Такие системы позво- ляют представить любое целое число (как положительное, так и отрицательное) в ко­нечном виде. Если основание системы счисления является четным числом, то построение симметричной канонической системы стано­вится невозможным. При-мером симметричной канонической систе­мы является троичная система (k = 3) с цифрами {-1, 0, 1}.

Если канонические системы с натуральным основанием k имеют только цифры x_i {0, 1,..., k - 1} или только цифры x_i {- k + 1, - k + 2,..., 0}, то они называются смещенными. С помощью таких систем можно представить в конечном виде либо только по­ложительное, либо только отрицательное целое число. К указанным системам относятся, например, десятичная система с цифра- ми {0, 1,..., 9} и двоичная система с цифрами {0, 1}.

Кососимметричными каноническими системами называются систе­мы с нату-ральным основанием k и цифрами x_i {- q,- q + 1,..., 0,..., g }, причем q+g+ 1 = =k, q g. Такие системы по своим свой­ствам занимают промежуточное положение между симметричными и смещенными системами.

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

Подставляя в (2) вместо x_i их возможные максимальные и ми­нимальные значения для различных систем, можно определить, что диапазоны представления чисел для симметричных, смещенных с положительными цифрами, смещенных с отрицательными цифрами и кососимметричных систем определяются соответст- венно интерва­лами

 

 

причем любые два ближайшие по значению числа отличаются на еди­ницу младше- го разряда, т. е. на величину k ^{- m}.

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

Избыточные системы счисления с натуральным основанием k = 2 r и циф- рами x_i {- r, - r +1,..., 0,..., r, r + 1} или основанием k = 2 r + 1 и цифрами x_i {- r - 1, - r,..., 0,..., r, r + 1} назы­ваются квазиканоническими.

Примерами таких систем являются десятичная система с цифра­ми {- 5, - 4, - 3, - 2, - 1, 0, 1, 2, 3, 4, 5, 6} и троичная система с цифрами {- 2, - 1, 0, 1, 2}. Об- щее количество различных цифр в таких системах равно k + 2.

Системы счисления с натуральным основанием k = 2 r и цифра­ми x_i {- r, - r + 1,..., 0,..., r - 1, r } или с основанием k = 2 r + 1 и цифрами x_i {- r, - r + 1,..., 0,..., r, r + 1} называются модифицированными квазиканоническими избыточ- ными системами счисления. В таких системах количество различных цифр лишь на единицу больше основания системы счисления. К модифицирован­ным квазика-ноническим системам счисления относятся, например, троичная система с цифра- ми {- 1, 0, 1, 2} и двоичная система с циф­рами {-1, 0, 1). Указанные системы счис- ления могут быть эффек­тивно использованы, например, при выполнении операций умно­жения и деления.

При выполнении операций деления и извлечения корня находит также применение неканоническая двоичная система счисления с цифрами {-1, 1}. В данной системе вес каждого разряда является целой степенью числа 2, а диапазон представления чисел при ес­тественном порядке весов заключен между максималь- ным числом 11...1,1...11 = 2^s+1 - 2^-m и минимальным числом ... , ... = = –2^s+1 + 2^-m (здесь означает –1). Отсутствие цифры 0 в этой системе приводит к невозможности конечным образом представить любое четное число и нуль.

Большой практический интерес представляют смешанные систе­мы, в кото- рых каждый разряд канонической десятичной системы заменяется несколькими двоичными разрядами с определенными весами.

В системах счисления с естественным и искусственным порядком весов каждый разряд в записи числа имеет свой вес. Такие системы называются также взвешенными или весомозначными. Наряду с этим возможны такие системы счисления, в которых каждая отдельная цифра никак не связана с каким-либо количественным эквивален­том и лишь определенным комбинациям цифр ставится в соответ­ствие некоторый количественный эквивалент. Такие системы счис­ления на-зываются невзвешенными (невесомозначными, символиче­скими).

Главное преимущество взвешенных систем счисления состоит в удобстве представления чисел и простоте выполнения арифмети­ческих операций. Недоста- ток таких систем заключается в невоз­можности выполнения арифметических опе- раций как поразрядных. Поразрядной операцией называется такая операция, ре- зультат которой в лю­бом разряде не зависит от результата выполнения этой опе- рации во всех остальных разрядах. Примером системы счисления, в кото­рой ариф-метические операции могут выполняться поразрядно, яв­ляется система остаточных классов (СОК), являющаяся невзвешен­ной системой. В СОК для представления це- лых положительных чисел выбирается набор взаимно простых модулей (оснований) Р_i (i = ) та­ким образом, чтобы выполнялось ус­ловие X _max < P₁P₂...P_m,где Х _mах – максимальное из представляемых чи­сел. Любое целое положительное чис­ло X представляется в виде

X = (X ₁, X ₂, …, X _m),

где Х_i — целочисленный остаток (вы­чет) от деления X на модуль P_i,т. е.

Запись [ А ]означает округление А в сторону ближайшего мень­шего целого числа, если А дробное ([ А ] = int А). Максимальное количество чисел, которое можно представить с помощью т модулей, равно N = Р₁Р₂...Р_т . В табл.1 приве- дено изображение некото­рых чисел при использовании системы модулей Р₁ = 2,Р₂ = 3 и Р₃ = 5.

Таблица 1.

Десятичное число	Запись числа в СОК(Р1 = 2; Р2 = 3; Р3 = 5)	Десятичное число	Запись числа в СОК(Р1 = 2; Р2 = 3; Р3 = 5)
	0 0 0		1 2 1
	1 1 1		0 0 2
	0 2 2		1 1 3
	1 0 3		0 2 4
	0 1 4		1 0 0
	1 2 0		0 1 1
	0 0 1		1 2 2
	1 1 2		0 0 3
	0 2 3		1 1 4
	1 0 4		0 2 0
	0 1 0

 

К недостаткам СОК, затрудняющим ее применение в ВТ, относятся: отсут-ствие удобного способа сравнения чисел; трудность выполнения операции деления и округления; отсутствие удобного способа определения выхода результата опера- ции за пределы диа­пазона допустимых чисел. Указанные недостатки ограничивают область применения СОК рамками специализированных ЭВМ, для которых эти недостатки не являются существенными.

Выбор системы счисления для представления информации в ЭВМ оказыва- ет существенное влияние на ее надежность и эконо­мичность. От используемой системы счисления зависит струк­тура аппаратных средств машины, удобство и ско-рость выполне­ния арифметических и логических операций. Необходимо учитывать также простоту перевода чисел в десятичную систему счисления, так как общение человека с машиной строится на основе деся­тичной системы независимо от сис- темы, используемой для пред­ставления информации в самой машине. Практика разработки и эксплуатации ЭВМ показывает, что вычислительные машины, пред­назначенные для решения задач, в которых количество вычисли­тельных операций, приходящихся на один символ вводимой-выво­димой информации, велико, как пра-вило, проектируются с исполь­зованием двоичной системы счисления. К таким за- дачам относится широкий круг научно-технических задач, задачи оптимального планирования, транспортные задачи и др. В ЭВМ, где время ввода – вывода дан- ных значительно превышает время обработки информа­ции, а также в малых уни-версальных ЭВМ, характеризующихся интенсивным обменом информацией между человеком и машиной, применяется десятичная система счисления.

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