***** Google.Поиск по сайту:


4. Системы счисления

Вычислительная техника

4. Системы счисления

4.1. Общие сведения

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

Система изображения любых чисел с помощью ограниченного числа символов называется системой счисления. Используемые в системе счисления символы называются цифрами.

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

Примером непозиционной системы счисления является римская система, в которой используются римские цифры I, V, X, L, С, М. Соответственно значение числа, например, CCXXIV вычисляется следующим образом: С=100, Х=10, V=5, I=1. При этом вес цифры не зависит от ее местоположения в записи числа, а знак зависит. Если цифра с меньшим весом стоит слева от цифры с большим весом, то ее знак -, а если цифра с меньшим весом стоит справа от цифры с большим весом то ее знак +. Общим недостатком непозиционных систем счисления являются трудности записи в таких системах больших чисел и трудности выполнения арифметических операций, поскольку для этого используются громоздкие правила. Поэтому в цифровой технике непозиционные системы практически не нашли применения.

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

В десятичной системе основание р=10 и для записи чисел используется десять цифр: 0, 1, 2, ..., 9. Каждая цифра числа занимает в нем определенный разряд, который имеет весовые коэффициенты для разрядов влево от запятой 100, 101, 102... и вправо от запятой 10-1, 10-2, 10-3, ...

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

Наибольшее распространение в цифровой технике имеет двоичная система счисления. В этой системе используются только две цифры: 0 и 1. В двоичной системе любое число может быть представлено последовательностью двоичных цифр:

N2=am am-1 am-2……a0 a-1 a-2 ,

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

N2= am 2m+am-1 2m-1+am-22m-2+….+a0 20+a-1 2-1+a-12-2

Вес разрядов, отсчитываемых влево от запятой, в целой части числа равен соответственно 1, 2, 4, 8, 16, .... вес же разрядов правее запятой в дробной части будет ?, ?, и т.д. Например, число 11010,112 соответствует следующему количеству:

11010,112= 1*24+1*23+0*22+1*21+0*20+1*1/2+1*1/4

которое, как следует из приведенного разложения его по степеням числа 2, равно десятичному числу 26,7510. В восьмеричной системе счисления употребляется восемь цифр: 0, 1, 2, ..., 7. Любое число в восьмеричной системе представляется последовательностью"

N8=bm bm-1 bm-2……b0 b-1 b-2 ,

в которой цифры bi могут принимать значения от 0 до 7. Вес разрядов целой части 1, 8, 64, 256, ..., в дробной части 1/8, 1/64, 1/256. Например, восьмеричное число 756,2:

756,258 = 7* 82 + 5*81 + 6* 80 + 2.8-1

равно десятичному числу 494, 32812510.

В шестнадцатеричной системе счисления для изображения чисел употребляется 16 цифр: 0... 15. При этом, чтобы одну цифру не изображать двумя символами, приходится вводить специальные обозначения для цифр больше девяти. В качестве шести символов обычно используются буквы латинского алфавита А, В, С, D, Е, F, которым в десятичной системе соответствуют числа 10, 11, 12, 13, 14, 15. Таким образом, шестнадцатеричное число А7В,C8 соответствует следующему количеству:

A7B,C816= 10*162+7*161+11*160+12*16-1+8*16-2, равному десятичному числу 2683,7812510.

4.2. Перевод чисел из одной системы счисления в другую

Основания восьмеричной и шестнадцатеричной систем счисления выражаются целой степенью двух (8=23, 16=24). Этим объясняется простота преобразования чисел, представленных в этих системах, в двоичную систему счисления и обратно.

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

762,358=111 110 010, 011 1012.

Перевод шестнадцатеричных чисел в двоичную систему счисления достигается представлением цифр шестнадцатеричного числа четырехразрядными двоичными числами. Например,

А7В, С716=1010 0111 1011, 1100 01112 .

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

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

4.3. Арифметические операции в двоичной системе счисления

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

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

Сложение положительных чисел.

Сложение чисел в двоичной системе счисления выполняется на основе таблицы двоичного сложения:
0+0=0
0+1=1
1+0=1
1+1=10

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

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

Пример сложения двух многоразрядных двоичных чисел:
1101101 - первое слагаемое
+
1001111 - второе слагаемое
0100010 - поразрядная сумма без учета переносов
+
1 11 1 - переносы
10111100- окончательная сумма.

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

Вычитание двух чисел в двоичной системе выполняется на основе таблицы двоичного вычитания

0-0=0,
1-0= 1,
1-1=0,
10-1 = 1.

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

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

Обратный код отрицательных двоичных чисел может быть сформирован по следующему правилу: цифры всех разрядов, кроме знакового, заменяются на обратные (инвертируются)-единицы заменяются нулями, а нули единицами. В знаковый разряд ставится единица. Обратное преобразование из обратного кода в прямой производится по тому же правилу. При использовании обратного кода операция вычитания реализуется как арифметическое сложение положительного числа, представленного в прямом коде, с отрицательным числом, представленным в обратном коде. Например, при вычитании из числа 0 10110 числа 1 01101 уменьшаемое представляется как положительное число в прямом коде 0 10110, а вычитаемое - как отрицательное число в обратном коде 1 10010. В представлении чисел знаковые разряды выделены подчеркиванием. При выполнении операции арифметического сложения над этими числами получаем алгебраическую сумму:
0 10110 - первое слагаемое в прямом коде,
+
1 10010 - второе слагаемое в обратном коде,
+
10 01000
1
0 01001 - сумма в прямом коде.

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

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

При использовании дополнительного кода для вычитания двоичных чисел из предыдущего примера получим:
0 10110 - первое слагаемое в прямом коде,
+
1 10011 - второе слагаемое в дополнительном коде,
0 01001 - сумма в прямом коде.

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

Умножение двоичных многоразрядных чисел включает в себя две операции - определение знака произведения и определение его абсолютной величины. Знаковый разряд может быть получен суммированием цифр знаковых разрядов сомножителей без формирования переноса:
0+0=0,
0+1=1,
1+0=1,
1+1= 0 - без формирования переноса.

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

Абсолютная величина значения произведения определяется путем перемножения чисел без учета их знаков. Перемножение многоразрядных двоичных чисел производится на основе таблицы двоичного умножения
0х0=0,
0х1=0,
1х0=0,
1х1=1.

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

Получающиеся в результате умножения и сдвига частичные произведения после суммирования дают полное произведение. Особенность умножения двоичных чисел состоит в том, что частичное произведение может быть либо сдвинутым на соответствующее число разрядов множимым, если соответствующая цифра множителя равна 1, либо нулем, если соответствующая цифра множителя равна 0:
     10111 - множимое,
*
       1101 - множитель
      10111 - первое частичное произведение
     00000 - второе частичное произведение
    10111 - третье частичное произведение
   10111 - четвертое частичное произведение
  100101011 - произведение

Тот же результат можно получить при умножении, начиная со старших разрядов множителя и сдвигая частичные произведения вправо.

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

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

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

Если множимое, или множитель, или оба вместе содержат и целую и дробную части, то запятые в множимом и множителе не учитываются, они умножаются как два целых числа и от полученного произведения справа отделяются запятой m+n разрядов, где n - число дробных разрядов множимого, a m - число дробных разрядов множителя.

Деление двоичных многоразрядных чисел включает в себя две операции-определение знака частного и определение его абсолютной величины.

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

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

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

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

4.4. Формы представления чисел с фиксированной и плавающей точками

В вычислительной технике применяют две формы представления чисел: с фиксированной точкой (запятой) и с плавающей точкой (запятой). Эти формы называют также соответственно естественной и полулогарифмической. Множество чисел, которые могут быть изображены с помощью n двоичных разрядов, представляет собой на числовой оси ряд из 2n равностоящих точек с дискретностью, т. е. расстоянием между точками, равной весу младшего разряда, который заполняет некоторую область между Nmin и Nmax. Любое число между Nmin и Nmax может быть изображено с абсолютной погрешностью, не превышающей половины младшего разряда. Относительная погрешность зависит от абсолютной величины числа и может меняться в широких пределах.

Представление числа таким способом называется представлением с фиксированной точкой. Такое название связано с тем, что точка, отделяющая дробную часть от целой, фиксируется в определенном месте относительно разрядов числа. Обычно точка находится или перед старшим разрядом, или после младшего. В первом случае могут быть представлены только числа по модулю меньшие единицы, а во втором случае-только целые числа. На рис. 20,а показаны примеры форматов для представления двоичных чисел с фиксированной точкой. Для кода знака выделяется знаковый разряд - обычно крайний слева. В знаковом разряде 1 соответствует минусу, а 0 - плюсу. На рис. 20,а показан формат для числа с точкой, фиксированной перед старшим разрядом. В этом формате могут быть представлены числа - правильной дроби с точностью до 2-(n-1). При этом диапазон представления чисел будет

2-(n-1) > | N | > 1 - 2-(n-1).

Если точка фиксирована справа от младшего разряда, то при п разрядах можно представить целые числа в диапазоне

1 >| N | > 2-(n-1) - 1.

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

Кроме способа представления чисел с фиксированной точкой широкое распространение получил другой способ - представление чисел с плавающей точкой. При этом число представляется в виде:

N = ±q, ±m,

что соответствует следующей записи:

N = р±q (± m),

где р - основание системы счисления; q - целое число, выражающее порядок числа N; m - мантисса числа, причем всегда выполняется неравенство |m| > 1 (рис. 20, б). Запись числа в таком виде называется полулогарифмической потому, что в логарифмической форме представляется не все число, а только его часть р±q. При полулогарифмической записи положение точки в мантиссе m определяется величиной порядка q. С изменением порядка в большую или меньшую сторону точка перемещается влево или вправо, т. е. "плавает" в изображении числа.

Представление числа в форме р±q (± m) не является однозначным, так как его значение не изменится при записи в разрядах мантиссы числа m*qk вместо m и числа (q-k) в разрядах порядка вместо q. Поэтому на изображение числа в форме с плавающей точкой накладывается еще одно дополнительное условие, чтобы независимо от значения числа абсолютная величина мантиссы изменялась в узких пределах. Число, представленное в записи р±q (± m), называется нормализованным, если мантисса удовлетворяет условию

1 > | т | > 1/р,

т. е. если старший разряд мантиссы в системе счисления с основанием р отличен от нуля.

Операция преобразования ненормализованного числа в нормализованное называется нормализацией. Для выполнения операции нормализации под знак числа отводится два разряда. Если нормализованное двоичное число положительно, то в старшем цифровом разряде должна стоять 1, а если оно отрицательное -то 0. Сочетание 01 и 10 в знаковом и старшем цифровых разрядах означает выполнение одного из условий нормализации

1/2 > | m | ,

а сочетание 00 и 11 в этих же разрядах - нарушение этого условия. Для нормализации числа в данном случае следует повторять цикл сдвига цифровой части влево на один разряд (умножение на 2) с одновременным вычитанием единицы из порядка (деление на 2) до тех пор, пока не начнет выполняться условие нормализации.

Нормализацию можно осуществить сдвигом мантиссы вместе со знаком на один разряд вправо с одновременным добавлением единицы к порядку.

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

М = 2k, где k - число двоичных разрядов, используемых для модуля порядка. Смещенный порядок

qсм = q + М

будет всегда положительным. Для его представления необходимо такое же число разрядов, как и для модуля и знака порядка q. Важная особенность смещенных порядков состоит в том, что если для порядков p1 и p2, представляющих собой целые числа со знаками, выполняется соотношение p1 > p2, то и для положительных целых чисел соответствующих смещенных порядков p1 см и р2 см также будет выполняться соотношение р1 см > р2 см.

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

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

Pm > | N |> рl - рm при l + m = n,

где l - число разрядов, отведенных для представления целой части числа; m - число разрядов, используемых для записи дробной части.

При использовании формы записи числа с плавающей точкой диапазон представимых чисел будет

P - pn > N > ( 1 - p-m) ppn

где q - количество разрядов, отводимых для записи порядка, а m - для записи мантиссы.

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

Вычислительная техника



***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.