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

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

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

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

·        возможность представления любого числа в рассматриваемом диапазоне величин;

·        единственность представления (каждой комбинации символов должна соответствовать одна и только одна величина);

·        простоту оперирования числами.

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

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

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

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

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

 

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

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

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

Например:

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

11010.101₂ = 1 · 2⁴ + 1 · 2³ + 0 · 2² + 1 · 2¹ + 0 · 2⁰ + 1 · 2^-1 + 0 · 2^-2 + 1 · 2^-3;

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

22120.212₃ = 2 · 3⁴ + 2 · 3³ + 1 · 3² + 2 · 3¹ + 0 · 3⁰ + 2 · 3^-1 + 1 · 3^-2 + 2 · 3^-3;

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

A3F.1CD₁₆ = A · 16² + 3 · 16¹ + F · 16⁰ + 1 · 16^-1 + C · 16^-2 + D · 16^-3.

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

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

где

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

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

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

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

61 | 2

60  30 | 2

b₀ = 1 30 15 | 2

b₁ = 0 14 7 | 2

b₂ = 1 6 3 | 2

b₃ = 1 2 1 = b₅

b₄ = 1

Ответ: 61₁₀ = 101111₂.

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

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

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

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

(q₂ = 2).

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

Десятичное число	Двоичное число
100	0001
101	1010
102	110 0100

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

A = 113 = 1 · 10² + 1 · 10¹ + 3 · 10⁰ = 001 · 1100100 + 0001 · 1010 + 0011 · 0001 = 1110001₂.

Ответ: 1110001₂.

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

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

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

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

A=[A]_ф K_A,

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

-1 < [A]_ф < 1;

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

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

№ разряда

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

0

0

1

0

0

1

1

1

0

0

0

1

0

1

1

1

A₁ = 0.010011100010111₂;

1

0

1

0

0

1

1

1

0

0

0

1

0

1

1

1

A₂ = — A₁ = 0.010011100010111_2.

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

A = m_Ap_A,

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

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

№ разряда

 

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

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

С = A Ñ B,

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

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

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

[C] = [A] Ñ [B],

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

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

На основе правил двоичной арифметики можно записать правила  сложения двоичных цифр так, как показано в табл. 1, где a_i, b_i — разряды операндов A и B соответственно; c_i — результат сложения (сумма); П_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

 

ГЛАВА2. Погрешности представления числовой информации

 

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

Абсолютная погрешность  представления — разность между истинным значением входной величины А и ее значением, полученным из машинного изображения А_м, т. е. Δ[А] = А – А_м.

Относительная погрешность  представления — величина

.      

Входные величины независимо от количества значащих цифр могут  содержать грубые ошибки, возникающие  из-за опечаток, ошибочных отсчетов показаний каких-либо приборов, некорректной постановки задачи или отсутствия более  полной и точной информации. Например, часто принимают  π = 3,14. Однако эта  величина может быть получена с более  высокой точностью. Если принять, что  точное значение π = 3,14139265, то абсолютная погрешность равна Δ[π] = 0,00159265.

Часто некоторая величина в одной системе счисления  имеет конечное значение, а в другой системе счисления становится бесконечной  величиной, например, дробь 1/10 имеет  конечное десятичное представление, но, будучи переведена в двоичную систему  счисления, становится бесконечной  дробью 0,00011000110011... .

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

В соответствии числа изображаются в машине в виде А_q = [А]К_A, где масштабный коэффициент К_A выбирают так, чтобы абсолютное значение машинного изображения числа А в системе счисления с основанием q = 2 было всегда меньше 1:        А_q =К_A [а_-1q^-1 + а_-2q^-2 + ... + а_-пq^-n +…].

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

   

Если q = 2 , то при а_i = 1 максимальное значение этой погрешности

    

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

Усредненная абсолютная погрешность  перевода чисел в двоичную систему  счисления Δ[A] = (0 + 2^-n)/2 = 0,5·2^-n.

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

     

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

Для ЭВМ, как правило, п = 16...64, поэтому 1>>2^-n, откуда

Аналогично, для максимального  значения:

   

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

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

     

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