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]обр


 

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

24046. Аутоиммунный тиреоидит: клиника, диагностика, лечение 19.36 KB
  Хронический аутоиммунный тиреоидит или лимфоматозный тиреоидит болезнь Хашимото это воспалительное заболевание щитовидной железы аутоиммунной природы когда в организме человека образуются антитела и лимфоциты повреждающие собственные клетки щитовидной железы. Итогом этого процесса является повреждение клеток щитовидной железы тироцитов. Из поврежденных клеток щитовидной железы в кровь попадает содержимое фолликулов: гормоны разрушенные части внутренних органелл клетки которые в свою очередь способствуют дальнейшему образованию антител к...
24047. Синдром диссеминированного внутрисосудистого свертывания: клиника, диагностика, лечение 37.21 KB
  это свертывание крови и тромбообразование в результате которых происходит потребление факторов свертывания крови чрезмерная активация фибринолиза и часто наступают кровотечения.синонимы: синдром РВС рассеянного внутрисосудистого свертывания крови ВСФ внутрисосудистое свертывание и фибринолиз ТГС тромбогеморрагический синдром коагулопатия потребления. При этом наступают полимикросвертывание крови и тромбоз переходящие в дальнейшем в кровотечение вследствие гипо и афибриногенемии потребления и активации фибринолиза.[3] I стадия ...
24048. Острый инфаркт миокарда, клинические варианты, стадии, классификации 46.88 KB
  Инфа́ркт миока́рда одна из клинических форм ишемической болезни сердца протекающая с развитием ишемического некроза участка миокарда обусловленного абсолютной или относительной недостаточностью его кровоснабжения. Инфаркт миокарда левого желудочка передний боковой нижний задний. Изолированный инфаркт миокарда верхушки сердца.
24049. Болезнь и синдром Иценко-Кушинга. Лабораторные и инструментальные методы диагностики 44.56 KB
  В настоящее время доказана связь между опухолями легкого поджелудочной железы тимуса щитовидной предстательной околощитовидных желез мозгового слоя надпочечников яичника яичек различных участков желудочнокишечного тракта с развитием клиники синдрома ИценкоКушинга АКТГэктопированный синдром. Методы определения функции щитовидной железы и степени тяжести тиреотоксикоза. аутоиммунное заболевание обусловленное избыточной секрецией тиреоидных гормонов диффузной тканью щитовидной железы которое приводит к отравлению этими гормонами ...
24050. Язвенная болезнь желудка и двенадцатиперстной кишки, эпидемиология, этиология, патогенез, классификация, осложнения 19.56 KB
  Язвенная болезнь связана с нарушением нервных а затем и гуморальных механизмов регулирующих секреторную моторную функции желудка и двенадцатиперстной кишки кровообращение в них трофику слизистых оболочек. Образование язвы в желудке или двенадцатиперстной кишке является лишь следствием расстройств указанных выше функций. В механизме же развития язв в выходном отделе желудка и особенно в двенадцатиперстной кишке напротив решающим фактором явяется усиление агрессивности кислотнопептического фактора.
24051. Злокачественные и доброкачественные опухоли пищевода 27.72 KB
  К числу доброкачественных опухолей пищевода относятся эпителиальные папилломы аденомы и неэпителиальные лейомиомы гемангиомы. Они берут начало в толще стенки пищевода затем образуют тонкую длинную ножку. Полипы пищевода как правило бывают одиночными локализуются на уровне раздвоения трахеи или в нижней половине пищевода.
24052. Хронический гастрит, Классификация, этиология и патогенез, клиника, лечение 56.92 KB
  Гастрит типа А эндогенный аутоимунный гастрит. Гастрит типа Б. Доказано что в основе патогенеза хронического гастрита типа В лежит персистирующая инфекция HP что подтверждается тем что этот микроорганизм находят в пилорическом отделе у подавляющего большинства больных. Гастрит типа С реактивный химический гастрит рефлюксгастрит.
24053. Бронхиальная астма. Аллергологическая диагностика 35.85 KB
  самостоятельное хроническое рецидивирующее заболевание основным и обязательным патогенетическим механизмом которого является изменённая реактивность бронхов обусловленная специфическими иммунологическими сенсибилизация и аллергия или неспецифическими механизмами а основным обязательным клиническим признаком приступ удушья вследствие бронхоспазма гиперсекреции и отёка слизистой оболочки бронхов Исследование функции внешнего дыхания Для определения функции внешнего дыхания повсеместно у пациентов в возрасте старше 5 лет используются...
24054. Острая и хроническая недостаточность коры надпочечников. Методы неотложной терапии 22.74 KB
  Синдром раздраженного кишечника: клиника диагностика лечение. Синдром раздраженного кишечника это не самостоятельное заболевание а комплекс расстройств которые не связаны с непосредственным поражением самого кишечника. Причины возникновения синдрома раздраженного кишечника: нервнопсихические психоэмоциональные расстройства стрессы нарушение привычного режима питания недостаток клетчатки в пище малоподвижный образ жизни гинекологические заболевания вызывают рефлекторные нарушения функции кишечника кишечника эндокринные нарушения ...