18978

ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

Реферат

Информатика, кибернетика и программирование

ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМ СЧИСЛЕНИЯ Вся информация в ЭВМ представляется в виде чисел. Выразив эти числа в какой-либо системе счисления можно получить код основанный на данной системе счисления. Для пон...

Русский

2013-07-10

128 KB

10 чел.

9

PAGE  9

ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

  1.  ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМ СЧИСЛЕНИЯ

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

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

В зависимости от способа изображения чисел системы счисления делятся на 2 типа:

  •  непозиционные;
  •  позиционные.

В непозиционных системах счисления значение любой цифры не зависит от занимаемой ею позиции в числе. Например, римская система, в которой в числе XXX каждый разряд означает 10 единиц (L – 50, C – 100, D – 500, М – 1000). В непозиционных системах счисления не представляются дробные и отрицательные числа, действия над числами связаны с большими трудностями и не имеют правил.

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

Основным понятием любой позиционной системы счисления является основание. Оно показывает:

  1.  сколько различных цифр в системе счисления;
  2.  во сколько раз изменяется количественное значение цифры при перемещении ее на соседнюю позицию.

В зависимости от основания различают следующие системы счисления:

  •  десятичную (Dec)(0, 1, 2, 3,…, 9);
  •  восьмеричную (Oct)(0, 1, 2,…, 7);
  •  двоичную (Bin) (0, 1);
  •  шестнадцатеричную (Hex) (0, 1,…, 9, A (10), B (11), C (12), D (13), E (14), F (15)).

В древнем Вавилоне использовали систему счисления с основанием 60. Деление часа на 60 минут, а минуты на 60 секунд заимствовано именно из этой системы.

  1.  Представление целых неотрицательных чисел

Любое целое неотрицательное число, записанное в позиционной системе счисления:

можно представить в виде степенного ряда (полинома):

Здесь Qm – число в m - й системе счисления, m – основание системы счисления, l – количество разрядов целого числа, i – номер разряда данного числа, ai – цифра числа, записанного в m – й системе счисления, принимающая любые значения от 0 до (m-1) и показывающая, сколько единиц i- го разряда содержится в числе, mi-1 – вес i-того разряда.

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

Qmaх=ml -1

Имея l разрядов, можно записать всего ml разных чисел.

Каждое слагаемое в приведенном выражении называется термом. Крайняя правая цифра любого числа называется его младшим или наименьшим (a1) значащим разрядом (МЗР), крайняя левая – старшим или наибольшим (al) значащим разрядом (СЗР).

Кроме полиномиальной записи используется еще одна форма записи, которая называется схемой Горнера.

Эта форма используется при переводе чисел из одной системы счисления в другую.

В ЭВМ для представления информации (данных) используется двоичная система счисления. Ее достоинства:

  •  используется только 2 символа (цифры) 0 и 1, что хорошо согласуется с техническими характеристиками цифровых схем, имеющих, как правило, 2 устойчивых состояния;
  •  в двоичной системе легко реализуются арифметические операции над числами:

0+0=0

00=0

1+0=1

10=0

0+1=1

01=0

1+1=10

11=1

Недостаток: длинные числа, которые неудобно записывать. Двоичное представление числа требует примерно в 3.3 раза большего числа разрядов, чем его десятичное представление.

Двоичная цифра называется битом.

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

  1.  Перевод целых чисел

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

Если между основаниями двух систем счисления m и p соблюдается связь m1= pk, где k – целое число, то перевод является наиболее простым и осуществляется по правилу 1.

Правило 1. Каждая цифра числа с основанием m представляется k цифрами системы счисления  с основанием p и наоборот.

По этому правилу осуществляется перевод между 16-ичной и 2-ичной системами: 161=24 и между 8-ичной и 2-ичной системами: 81=23. В первом случае одна шестнадцатеричная цифра заменяется четырьмя двоичными цифрами (тетрадой). Во втором случае одна восьмеричная цифра заменяется тремя двоичными цифрами (триадой). И наоборот. Замена начинается с младших разрядов. Если цифр до триады или тетрады не хватает, необходимо дополнить число слева нулями. В таблице 3.1 приведены двоичные коды всех 16-ричных цифр.

Таблица 3.1.

Таблица двоичных кодов десятичных и шестнадцатеричных цифр.

Цифра

0

1

2

3

4

5

6

7

8

9

А

В

С

D

E

F

Код

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Пример 3.1. В коде ASCII строчное латинское «а» есть 011000012, а в 16-ричной системе счисления – 6116. Как видим, каждый байт может быть представлен двумя 16-ричными цифрами.

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

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

Эти три правила часто называют правилами замещения.

Пример 3.2. 9Е316 = 9162 + 14161 + 3160 = 253110

       9Е316 = (916 + 14)16 + 3 = 253110

Рассмотрим теперь правило перевода целого неотрицательного десятичного числа в систему счисления с другим основанием.

Целое число в системе счисления с основанием m может быть представлено эквивалентным числом в системе счисления с основанием p по следующей формуле:

Таким образом, для перевода необходимо отыскать значения цифр bk (k=1,…,n) в новой системе счисления p.

Разделив обе части равенства (3.4) на основание новой системы счисления p, выраженное цифрами соответствующей системы счисления, получим:

Слагаемое в скобках – это частное от деления (Qm)1. Второе слагаемое – это остаток. Т. е.

Число b1 и есть младшая цифра числа в новой системе счисления с основанием p.

При следующем делении целого частного (Qm)1 будет получено новое целое частное (Qm)2 и новый остаток b2.

Деление необходимо продолжать до тех пор, пока частное не станет меньше основания p. Отсюда правило 4 для десятичных чисел (m=10), которое называют правилом деления.

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

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

В ЭВМ преобразование десятичных чисел в двоичные проводится не так, а по правилу 3, используя схему Горнера и выполняя действия в двоичной системе.

17310 = (00011010 + 0111)1010 + 0011 = 101011012

  1.  Представление дробных чисел

В общем случае любое неотрицательное число (смешанную дробь), представленное в позиционной системе счисления, вида:

можно записать в виде полинома:

Здесь k – количество разрядов в дробной части числа, l – количество разрядов в целой части числа. Старший разряд имеет обозначение al-1, а младший – a-k.

Минимальное значащее (не равное 0) число, которое можно записать в k разрядах дробной части:

Qmin=m-k

Имея в целой части числа l, а в дробной k разрядов, можно записать всего ml+k разных чисел.

Для правильных дробей также может быть использована форма записи в виде схемы Горнера:

  1.  Перевод дробных чисел

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

Крайние триады (тетрады) слева и справа дополняются нулями в случае, если не хватает цифр до полной триады (тетрады).

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

Рассмотрим теперь перевод правильной десятичной дроби в систему счисления с другим основанием. Поступим аналогично целым числам. Пусть исходная система счисления имеет основание m, новая система счисления – основание p.

Для перевода числа из системы счисления с основанием m необходимо отыскать значения цифр bj (j=-1,…,-n) в новой системе с основанием p.

Умножив обе части равенства (4.7) на основание новой системы счисления p, выраженное числами соответствующей системы счисления, получим:

Первое слагаемое – это целая часть произведения, первая цифра в дробной части новой системы счисления. Второе слагаемое – это дробная часть произведения.

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

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

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

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

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

Пример 3.3.

101110,1012 =1*25+0*24+1*23+1*22+1*21+0*20+1*2-1+0*2-2+1*2-3=46,62510

  1.  Арифметические действия над числами

Для выполнения арифметических операций  над числами, представленными в любой системе счисления надо пользоваться известными правилами арифметики:

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

Вычитание двух многоразрядных чисел начинается с младших разрядов с учетом при необходимости переноса единиц (количество которых соответствует основанию системы счисления) из старших разрядов.

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

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

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

Здесь полная аналогия с операцией «остаток от деления на 2» A mod 2, которая означает, что число A делится на 2 и заменяется остатком (например,    9 mod 2 = 1). Так и в случае сложения по модулю 2 сумма разрядов делится на 2 и заменяется остатком (например, 2 mod 2 = 0).

  1.  ПРЕДСТАВЛЕНИЕ ОТРИЦАТЕЛЬНЫХ двоичных ЧИСЕЛ.

Существует несколько способов представления отрицательных двоичных чисел.

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

Пример 3.4. Семиразрядный натуральный двоичный код числа 2810 = 00111002. Так как число положительное, то к указанному коду следует приписать слева 0 (бит положительного знака):  [00111002]пр. = 0.00111002.

Если же число отрицательное (-2810), то требуется добавить 1 (бит отрицательного знака): [-00111002]пр. =1.00111002.

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

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

  1.  Обратный код. Обратный код отрицательного двоичного числа формируется заменой всех нулей симметричного кода этого числа на единицы, а всех единиц на нули, кроме бита знака. Обратный код числа  [-00111002]обр. = 1.11000112.

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

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

где m – основание системы счисления, a – цифра числа, записанного в прямом коде.

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

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

Пример 3.5. 68110 и 31910 в сумме дают 1000 (т.е. нули с переносом единицы в старший разряд). Таким образом, 681 является дополнением числа 319, а 319 – дополнение к числу 681.

Пример 3.6. 1012 и 0112 в сумме дают 1000 (т.е. нули с переносом единицы в старший разряд). Таким образом, 101 является дополнением числа 011, а 011 – дополнение к числу 101.

Или более строго:

Дополнением числа A будет число Aдоп = KA > 0, где K = mn – константа дополнения, m – основание системы счисления, n – максимальное количество разрядов для представления чисел.

Пример 3.7. Пусть m=10, n=7, A=75, тогда K=107=1000000010,

Aдоп =  1 0000000

        -            75

          -------------

             9999925

Пример 3.8. Пусть m=2, n=7, A=11, тогда K=27=100000002,

Aдоп =  1 0000000

        -            11

          -------------

             1111101

Для поиска дополнения можно пользоваться и таким приемом.

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

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

Обратите внимание, что во всех представления старший разряд несет информацию о знаке числа.

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

Вычитание С = А - В при этом выполняется следующим образом:

  1.  определяется дополнительный код вычитаемого В и производится сложение этого кода с уменьшаемым А; перед преобразованием прямых кодов в дополнительные необходимо их выровнять по числу разрядов.
  2.  если разность – число положительное, то бит переноса из старшего (знакового) разряда необходимо отбросить (тем самым как бы удалить из результата константу дополнения).

Сущность заключается в том, что вычитаемое В, как отрицательное число, представляется в виде дополнения до константы К = mn, при которой выполняется условие К - В > 0. Следовательно, операцию С = A - B, где А и В целые положительные числа в любой системе счисления, можно представить в виде

С = А - В = А + (-В )=А + (mn - B) -mn,   (3.10)

где m — основание любой системы счисления; mn – константа образования дополнительного кода, n – количество разрядов для представления чисел. Из выражения для разности (3.10) следует, что из полученной суммы нужно исключить добавленную константу.

Пример 3.9. Пусть необходимо найти разность 5 – 2:

         0.101  [+5]пр=[+5]доп

     +  1.110  [-2]доп

     -------------

                        0.011  [+3]пр =[+3]доп

  1.  если разность – число отрицательное (бит старшего разряда 1), то результат представлен в дополнительном коде (константа дополнения осталась в результате). Для определения абсолютного значения отрицательного результата, необходимо применить к нему операцию вычисления дополнения (т.к. дополнение от дополнения есть исходное число).

Пример 3.10. Пусть необходимо найти разность 2 – 5:

         0.010  [+2]пр=[+2]доп

     +  1.011  [-5]доп

     -------------

                        1.101  [-3]доп

Из примеров 3.9 и 3.10 следует, что при сложении чисел с разными знаками  единица переноса из старшего (знакового) разряда является признаком положительного результата, отсутствие переноса – признаком отрицательного результата, при этом константа образования дополнительного кода не скомпенсирована и осталась в сумме.

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

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

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

Объясним это. По сути обратный и дополнительный коды отличаются выбором значения константы К: mn – константа образования дополнительного кода, а mn - 1 — константа образования обратного кода.

Выражение (3.10) можно представить в виде

С = А - В = А + (-В )=А + (mn - 1 - B) - mn + 1    (3.11)

здесь mn -1 – константа образования обратного кода. Из выражения для разности следует, что из полученной суммы также нужно исключить добавленную константу (- mn + 1). Но для этого надо исключить 1 переноса из знакового разряда (т.е. mn ) и добавить 1 к младшему разряду суммы, т.е. требуется дополнительная операция сложения. Именно поэтому в ЭВМ для выполнения действий используется дополнительный код, а обратный только для образования дополнительного кода.

Пример 3.11. Пусть необходимо найти разность 5 – 2 используя обратный код:

         0.101  [+5]пр=[+5]обр

     +  1.101  [-2]обр

     -------------

                        0.010

                   +        1

                 ---------------

                        0.011 [+3]пр =[+3]обр


 

А также другие работы, которые могут Вас заинтересовать

39548. Расчет и проектирование Локальной Вычислительной Сети для организации «Подольский совет ветеранов» 1.83 MB
  В связи с техническим прогрессом, и необходимости минимизации бумажного документооборота, организациям как государственным так и коммерческим, необходим более функциональный и надежный вид ведения документации, и своевременность получения необходимой информации в короткие сроки для улучшения качества выполняемой работы и достижения максимального результата. Для этого в каждой организации используется Локальная вычислительная сеть.
39549. Динамика вариабельности сердечного ритма у одних и тех же студентов, занимающихся силовыми нагрузками в тренажерном зале на протяжении двух лет (до и после учебного занятия) 245.5 KB
  Ведь именно изменения параметров ритма сердца отражают адаптивные возможности регуляторных систем организма и динамику их развития. Состояние механизмов регуляции сегодня изучают с помощью математического анализа ритма сердца [21]. Математический анализ ритма сердца является достаточно информативным методом для изучения самых разнообразных стрессовых реакций организма [4].
39550. Методические основы проектирования интерьера учебного помещения на факультете технологии и предпринимательства 1.57 MB
  Влияние цвета света формы в интерьере на психику человека. При этом визуальная среда с которой человек соприкасается каждый день представляет собой такой же экологический фактор как и упомянутые выше и имеет не меньшую степень важности для человека. определение сущности интерьера и его элементов; анализ истории развития интерьера учебных помещений; определение основных требований к организации внутреннего пространства учебных помещений; рассмотрение освещения и предпочтительных цветовых гармоний интерьера в учебном помещении; определение...
39551. Разработка компактного неодимового лазера с диодной накачкой и волоконным выходом 17.44 MB
  В рабочем теле лазера путём накачки создаётся избыточное количество атомов в верхнем энергетическом состоянии. рис1 Вынужденное испускание фотона Классическая трёхуровневая система накачки рабочей среды используется например в рубиновом лазере. Именно это делает возможным использование немонохроматического излучения в качестве накачки. Следует отметить что создать инверсию населённостей атомов хрома Cr с помощью накачки непосредственно с уровня E0 на уровень E1 нельзя.
39552. ПУТИ СОВЕРШЕНСТВОВАНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ФИНАНСАМИ МО Г. НОВОРОССИЙСК 1.91 MB
  Валовое производство молока составляло 554 тыс. тонн производство мяса в живом весе 148 тыс. Восемь сельскохозяйственных предприятий производят почти 36 тыс. тонн молока; 14 тыс.
39553. МАЗ предназначен для обеспечения подразделений головного предприятия автотранспортными средствами обес. 343.47 KB
  20 Площадь помещения м 2 88 Объем помещения м3 528 Средний разряд рабочих 2 Среднемесячная заработная плата рабочего с учетом премий руб. руб. руб.зд Км руб.