50953

Представление информации в цифровых автоматах

Лекция

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

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

Русский

2014-02-03

136 KB

22 чел.

Дисциплина: ИНФОРМАТИКА                     II-КУРС: Т28, ВМ, АСОИ, САПР

Лекция № 11

Тема: Представление информации в цифровых автоматах

  1.  Основы представления информации в цифровых автоматах
  2.  Позиционные системы счисления
  3.  Методы перевода чисел
  4.  Форматы представления чисел с плавающей запятой
  5.  Двоичная арифметика
  6.  Коды: прямой, обратный, дополнительный, модифицированный
  7.  Выполнение арифметических операций с числами с фиксированной и плавающей запятой


Лекция № 11

Тема: Представление информации в цифровых автоматах

Основы представления информации в цифровых автоматах


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

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

  •  возможность представления любого числа в рассматриваемом диапазоне величин;
  •  единственность представления (каждой комбинации символов должна соответствовать одна и только одна величина);
  •  простоту оперирования числами.

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

Непозиционная система счисления – система, для которой значение символа не зависит от его положения в числе.

Для их образования используют в основном операции сложения и вычитания. Например, система с одним символом-палочкой встречалась у многих народов. Для изображения какого-то числа в этой системе нужно записать количество палочек, равное данному числу. Эта система неэффективна, так как запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: I, V, X, L, C, D, M и т. д. В этой системе существует отклонение от правила независимости значения цифры от положения в числе. В числах LX и XL символ X принимает два различных значения: +10 – в первом случае и –10 – во втором случае.

Позиционная система счисления – система, в которой значение символа определяется его положением в числе: один и тот же знак принимает различное значение. Например, в десятичном числе 222 первая цифра справа означает две единицы, соседняя с ней – два десятка, а левая – две сотни.

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

Для позиционной системы счисления справедливо равенство

(1)

где A(q) – произвольное число, записанное в системе счисления с основанием q; ai – коэффициенты ряда (цифры системы счисления); n, m – количество целых и дробных разрядов.

На практике используют сокращенную запись чисел:

(2)

Например:

а) в двоичной системе (q=2)

11010.1012 = 1 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 0 · 20 + 1 · 2-1 + 0 · 2-2 + 1 · 2-3;

б) в троичной системе (q=3)

22120.2123 = 2 · 34 + 2 · 33 + 1 · 32 + 2 · 31 + 0 · 30 + 2 · 3-1 + 1 · 3-2 + 2 · 3-3;

в) в шестнадцатиричной системе (q=16)

A3F.1CD16 = A · 162 + 3 · 161 + F · 160 + 1 · 16-1 + C · 16-2 + D · 16-3.

Методы перевода чисел

Числа в разных системах счисления можно представить следующим образом:

где  

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

Перевод чисел делением на основание новой системы

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

Пример 1. Перевести десятичное число A = 6110 в систему счисления с q = 2.

    61       | 2   

    60       30       | 2

b0 = 1       30      15       | 2

           b1 = 0     14         7      | 2

                    b2 = 1         6        3     | 2

                               b3 = 1       2       1 = b5

                                         b4 = 1

Ответ: 6110 = 1011112.

Табличный метод перевода

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

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

Пример 2. Перевести десятичное число A = 113 в двоичную систему счисления, используя таблицу эквивалентов цифр и степеней основания

(q2 = 2).

Таблица 1 – Таблица эквивалентов

Десятичное число

Двоичное число

100

0001

101

1010

102

110 0100

Решение. Подставив значения двоичных эквивалентов десятичных цифр и степеней основания в (3), получим

A = 113 = 1 · 102 + 1 · 101 + 3 · 100 = 001 · 1100100 + 0001 · 1010 + 0011 · 0001 = 11100012.

Ответ: 11100012.

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

Число 0,028 можно записать так: 28·10-3, или 2,8·10-2, или 0,03 (с округлением) и т. д. В компьютере используются две формы представления чисел.

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

Число А можно представить в виде

A=[A]ф KA,

где [A]ф – машинное изображение числа в формате с фиксированной запятой, значение которого лежит в пределах

-1 < [A]ф < 1;

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

Формат (разрядная сетка) машинного изображения чисел с фиксированной запятой разбивается на знаковую часть и поле числа. В знаковую часть записывается информация о знаке числа: 0, если A≥0; 1, если A<0.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

№ разряда

Например, числа А1 и A2 в прямом коде имеют машинное изображение:

0

0

1

0

0

1

1

1

0

0

0

1

0

1

1

1

A1 = 0.0100111000101112;

1

0

1

0

0

1

1

1

0

0

0

1

0

1

1

1

A2 = – A1 = 0.0100111000101112.

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

A = mApA,

где mA – мантисса числа A; при представлении числа в компьютере мантисса должна удовлетворять ограничению 2-1 ≤ | mA | ≤ 1 – 2-n; n – количество разрядов для изображения мантиссы без знака; pA – порядок числа A.

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

№ разряда

5. Двоичная арифметика

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

С = A  B,

где – знак арифметического действия (сложение, вычитание, умножение, деление).

Операнд – число, участвующее в арифметической операции, выполняемой цифровым автоматом.

Так как цифровой автомат оперирует только машинными изображениями

[C] = [A] [B],

где [   ] – обозначение машинных изображений операндов.

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

На основе правил двоичной арифметики можно записать правила сложения двоичных цифр так, как показано в табл. 1, где ai, bi – разряды операндов A и B соответственно; ci – результат сложения (сумма); Пi – перенос из данного разряда в соседний старший.


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

Таблица 2

ai

bi

ci

Пi

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

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

Таблица 3

ai

bi

Пi-1

ci

Пi

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

1

0

0

1

1

0

1

1

0

1

0

1

1

1

1

1

1

Обобщая вышеизложенное, можно сформулировать правила поразрядных действий при сложении операндов A и B:

ai + bi + Пi-1 = ci + Пi,

где ai, bii-й разряд 1-го и 2-го операндов соответственно; cii-й разряд суммы; Пi-1 – перенос из (i–1)-го разряда; Пi – перенос в (i+1)-й разряд (переносы принимают значения 0 или 1).

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

Вычитание двоичных чисел.

На основе правил двоичной арифметики можно записать правила вычитания двоичных цифр так, как показано в табл. 4, где aii-й разряд уменьшаемого; bii-й разряд вычитаемого; cii-й разряд разности; zi+1 – заем в старшем разряде.


Таблица 4

ai

bi

ci

zi+1

0

0

0

0

1

0

1

0

1

1

0

0

0

1

1

–1

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

Таблица 5

ai

bi

zi

ci

zi+1

0

0

0

0

0

1

0

0

1

0

1

1

0

0

0

0

1

0

1

–1

0

0

–1

1

–1

1

0

–1

0

0

1

1

–1

1

–1

0

1

–1

0

–1

Если A – уменьшаемое (1-й операнд), B – вычитаемое (2-й операнд), то для поразрядных действий

aibi + zi = ci + zi+1,

где ai, bi, ci – соответственно i-е разряды уменьшаемого, вычитаемого и разности; zi – заем из младшего i-го разряда; zi+1 – заем в старшем (i+1)-м разряде.

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

  1.  Коды: прямой, обратный, дополнительный, модифицированный

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

AB = A + (–B).

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

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

Прямой код числа A = – 0, a1 a2 ... an – машинное изображение этого числа в виде [A]пр = 1, a1 a2 ... an.

Из определения следует, что в прямом коде все цифровые разряды остаются неизменными, а в знаковой части записывается единица. Например, если A = – 0,101110, то [A]пр = 1,101110.

Положительное число в прямом коде не меняет своего изображения. Например, если A = 0,110101, то [A]пр = 0,110101.

Дополнительный код числа A = – 0, a1 a2 ... an – машинное изображение этого числа [A]д = 1, ā1 ā2 ... ān, для которого āi = 0, если ai = 1, и āi = 1, если ai = 0, за исключением последнего значащего разряда, для которого āk = 1 при ak = 1.

Например, число A = – 0,101110 запишется в дополнительном коде так: [A]д = 1,010010.

Дополнительный код является математическим дополнением до основания системы счисления:

| A | + [A]д = q,

где | A | – абсолютное значение числа A.

Обратный код числа A = – 0, a1 a2 ... an – такое машинное изображение этого числа [A]об = 1, å1 å 2 ... ån, для которого åi = 0, если ai = 1, и åi = 1, если ai = 0.

Из определения следует, что обратный код двоичного числа является инверсным изображением самого числа, в котором все разряды исходного числа принимают инверсное (обратное) значение, т. е. все нули заменяются на единицы, а все единицы – на нули, например если A = – 0,101110, то [A]об = 1,010001.

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

| A | + [A]об = qq-n,

где | A | – абсолютная величина числа A; n – количество разрядов после запятой в изображении числа.

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

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

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

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

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

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

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

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

Наиболее распространен метод, по которому произведение получается по следующей схеме: A = 0, a1 a2 ... an – множимое, а B = 0, b1 b2 ... bn = (... (((bn x 2-1 + bn-1) x 2-1 + bn-2) x 2-1 + ... b2) 2-1 + b1) 2-1 – множитель, произведение равно С = A x B = (...((bn x 0.a1 ... an) 2-1 + bn-1 x 0.a1 a2 ... an) 2-1 + ... + b1 x 0.a1 a2 ... an) 2-1,

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

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

При умножении чисел, представленных в дополнительном коде, одновременно получают знаковую и цифровую части произведения. Результат представляется в дополнительном коде только при положительном множителе; при отрицательном множителе для получения результата в дополнительном коде вводится коррекция в виде прибавления [Ā]д к произведению дополнительных кодов сомножителя.

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

а) на первом шаге формирования произведения прибавлением поправки [A]об;

б) на последнем шаге прибавлением к содержимому сумматора [Ā]об.

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

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

Деление двоичных чисел, представленных в формате с фиксированной запятой представляет последовательные операции алгебраического сложения делимого и делителя, а затем остатков и сдвига. Деление выполняется на двоичных сумматорах дополнительного и обратного кодов. Результат получается в прямом коде. Знаковую и цифровую часть частного получают в прямом коде. Знак частного Sg С = Sg A  Sg B,

где  –  операция сложения по mod 2; Sg A – знак делимого A; Sg B – знак делителя B.

Для определения цифр частного Ci используют следующие правила.

Правило 1. Если делимое A и делитель B представлены в соответствии с таблицей 1,

Таблица 1

Sg A

+

+

Sg B

+

+

представление операндов

A+

A+B

A+B

A+

где – изменение знака операнда на противоположный, то необходимо сравнивать на каждом шаге знаки делимого A и остатков Ai и принимать Ci = 1, если знаки совпали, и Ci = 0 – при несовпадении знаков A и Ai.

Правило 2. Если делимое A и делитель B представлены в соответствии с табл. 2, то в очередной разряд частного Ci переписывается содержимое знакового разряда сумматора на каждом шаге.

Таблица 2

Sg A

+

+

Sg B

+

+

представление операндов

+ B

+

A+B

A+

Необходимым условием выполнения операции деления чисел с фиксированной запятой является | A | < | B |, B  0, в противном случае – переполнение разрядной сетки сумматора.

Для нахождения результата с точностью n разрядов надо найти (n+1)-й разряд частного, а затем округлить результат.

Признаки окончания операции деления:

  1.  достижение заданной точности;

получение очередного остатка, равного нулю.

PAGE  1


 

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

81460. Глюкоза как важнейший метаболит углеводного обмена. Общая схема источников и путей расходования глюкозы в организме 139.63 KB
  Общая схема источников и путей расходования глюкозы в организме Глюкоза является альдогексозой. Циклическая форма глюкозы предпочтительная в термодинамическом отношении обусловливает химические свойства глюкозы. Расположение Н и ОНгрупп относительно пятого углеродного атома определяет принадлежность глюкозы к D или Lряду. В организме млекопитающих моносахариды находятся в Dконфигурации так как к этой форме глюкозы специфичны ферменты катализирующие её превращения.
81461. Аэробный распад — основной путь катаболизма глюкозы у человека и других аэробных организмов. Последовательность реакций до образования пирувата (аэробный гликолиз) 220.81 KB
  Все ферменты катализирующие реакции этого процесса локализованы в цитозоле клетки. Реакции аэробного гликолиза Превращение глюкозо6фосфата в 2 молекулы глицеральдегид3фосфата Глюкозо6фосфат образованный в результате фосфорилирования глюкозы с участием АТФ в ходе следующей реакции превращается в фруктозо6фосфат. В ходе этой реакции катализируемой фосфофруктокиназой фруктозо6фосфат превращается в фруктозо16бисфосфат. Продукты реакции альдольного расщепления изомеры.
81462. Распространение и физиологическое значение аэробного распада глюкозы. Использование глюкозы для синтеза жиров в печени и в жировой ткани 103.86 KB
  Использование глюкозы для синтеза жиров в печени и в жировой ткани. Основное физиологическое назначение катаболизма глюкозы заключается в использовании энергии освобождающейся в этом процессе для синтеза АТФ. Энергия выделяющаяся в процессе полного распада глюкозы до СО2 и Н2О составляет 2880 кДж моль.
81463. Анаэробный распад глюкозы (анаэробный гликолиз). Гликолитическая оксиредукция, пируват как акцептор водорода. Субстратное фосфорилирование. Распространение и физиологическое значение этого пути распада глюкозы 121.38 KB
  Реакции анаэробного гликолиза При анаэробном гликолизе в цитозоле протекают все 10 реакций идентичных аэробному гликолизу. Восстановление пирувата в лактат катализирует лактатдегидрогеназа реакция обратимая и фермент назван по обратной реакции. С помощью этой реакции обеспечивается регенерация ND из NDH без участия митохондриальной дыхательной цепи в ситуациях связанных с недостаточным снабжением клеток кислородом. Таким образом значение реакции восстановления пирувата заключается не в образовании лактата а в том что данная...
81464. Биосинтез глюкозы (глюконеогенез) из аминокислот, глицерина и молочной кислоты. Взаимосвязь гликолиза в мышцах и глюконеогенеза в печени (цикл Кори) 215.46 KB
  Глюконеогенез процесс синтеза глюкозы из веществ неуглеводной природы. Его основной функцией является поддержание уровня глюкозы в крови в период длительного голодания и интенсивных физических нагрузок. Эти ткани могут обеспечивать синтез 80100 г глюкозы в сутки.
81465. Представление о пентозофосфатном пути превращений глюкозы. Окислительные реакции (до стадии рибулозо-5-фосфата). Распространение и суммарные результаты этого пути (образование пентоз, НАДФН и энергетика) 135.5 KB
  Окислительные реакции до стадии рибулозо5фосфата. Распространение и суммарные результаты этого пути образование пентоз НАДФН и энергетика Пентозофосфатный путь называемый также гексомонофосфатным шунтом служит альтернативным путём окисления глюкозо6фосфата. Пентозофосфатный путь состоит из 2 фаз частей окислительной и неокислительной.
81466. Свойства и распространение гликогена как резервного полисахарида. Биосинтез гликогена. Мобилизация гликогена 173.81 KB
  Биосинтез гликогена. Мобилизация гликогена. Таким образом в молекуле гликогена имеется только одна свободная аномерная ОНгруппа и следовательно только один восстанавливающий редуцирующий конец.
81467. Особенности обмена глюкозы в разных органах и клетках: эритроциты, мозг, мышцы, жировая ткань, печень 110.65 KB
  Метаболизм глюкозы в эритроцитах. В эритроцитах катаболизм глюкозы обеспечивает сохранение структуры и функции гемоглобина целостность мембран и образование энергии для работы ионных насосов. Около 90 поступающей глюкозы используется в анаэробном гликолизе а остальные 10 в пентозофосфатном пути.
81468. Представление о строении и функциях углеводной части гликолипидов и гликопротеинов. Сиаловые кислоты 110.57 KB
  Сиаловые кислоты Гликопротеины – сложные белки содержащие помимо простого белка или пептида группу гетероолигосахаридов. К полипептидуприсоединяются гетероолигосахаридные цепи содержащие от 2 до 10 реже 15 мономерных остатков гексоз галактоза и манноза режеглюкоза пентоз ксилоза арабиноза и конечный углевод чаще всего представленный Nацетилгалактозамином Lфукозой или сиаловой кислотой; в отличие от протеогликанов гликопротеины не содержат уроновых кислот и серной кислоты. Сиа́ловые кисло́ты ациальные производные...