Постников А.И. Теория автоматов - файл B02-2.doc

приобрести
Постников А.И. Теория автоматов
скачать (963 kb.)
Доступные файлы (25):
B02-2.doc142kb.10.06.2007 18:06скачать
B03-2.doc363kb.10.06.2007 18:34скачать
B04-2.doc581kb.10.06.2007 19:10скачать
B05-2.doc109kb.10.06.2007 19:17скачать
B06-2.doc356kb.10.06.2007 19:42скачать
B08-2.doc357kb.16.05.2000 14:46скачать
B09-2.doc187kb.08.11.2001 11:20скачать
B11-2.doc126kb.12.05.2000 13:15скачать
B12-2.doc230kb.12.05.2000 13:21скачать
B13-2.doc115kb.08.11.2001 11:11скачать
B14-2.doc105kb.12.05.2000 13:44скачать
B15-2.doc112kb.12.05.2000 13:58скачать
B16-2.doc243kb.12.05.2000 14:29скачать
B17-2.doc155kb.08.11.2001 11:01скачать
n15.doc27kb.12.05.2000 14:44скачать
n16.doc22kb.12.05.2000 15:20скачать
PRIL-2.doc53kb.21.03.2000 20:43скачать
PRIL-3.doc72kb.21.03.2000 20:50скачать
n19.doc8kb.17.05.2000 01:18скачать
Pril1_1-4.doc1564kb.17.05.2000 21:45скачать
Pril1_5-15.doc107kb.17.05.2000 21:48скачать
n22.doc54kb.08.11.2001 11:22скачать
n23.doc19kb.12.05.2000 15:22скачать
Titl1-2.doc23kb.17.05.2000 01:31скачать
~$B05-2.doc1kb.05.12.2008 00:58скачать

B02-2.doc

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

2.1. Основные понятия и определения
Система счисления - совокупность приемов и правил для записи чисел цифровыми знаками.

Любая, предназначенная для практического применения, система счисления должна обеспечивать:

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

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

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

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

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

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

Другая известная непозиционная система счисления - римская. В изображениях чисел IX и XI для получения числа надо вычесть единицу из 10 в первом случае и прибавить единицу к 10 - во втором.

В позиционных системах счисления (ПСС) значение символа зависит от его положения в числе. Любая ПСС характеризуется основанием q.

Основание q позиционной системы счисления - количество знаков или символов, используемых для изображения числа в данной системе. Если q - целое положительное число, позиционная система счисления называется естественной.

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

A(q) = anqn + an-1qn-1 + ... + a1q1 + a0q0 + a-1q-1 + ... + a-mq-m (2.1)

или

A(q) = aiqi ,

где А(q) - произвольное число, записанное в ПСС с основанием q; (n+1) - количество разрядов целой части числа; m - количество разрядов дробной части числа; аi - символы ПСС.

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

А(q) = an an-1 ... a1 a0 , a-1 ... a-m .

В этой последовательности запятая отделяет целую часть числа от дробной. Например, в десятичной системе счисления число А(10)=325,68 записывается так:

A(10) = 310 2 + 210 1 + 510 0 + 610 -1 + 810 -2.

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

Для любой ПСС справедливо, что основание изображается символом 10 в своей системе (табл. 2.1).


Таблица 2.1

q=10

q=2

q=3

q=8

q=16

0

0

0

0

0

1

1

1

1

1

2

10

2

2

2

3




10

3

3

4







4

4

5







5

5

6







6

6

7







7

7

8







10

8

9










9

10










A

11










B

12










C

13










D

14










E

15










F

16










10


Длиной числа называют количество позиций (разрядов) в записи числа. Применительно к ВМ длина числа интерпретируется как длина разрядной сетки. Чем выше значение q, тем меньше разрядов требуется для записи числа.

Если заданы основание ПСС q и количество разрядов для записи чисел n, то максимальное и минимальное числа определяют по формулам

Aq max = qn-1 , Aq min = -(qn-1) .

Интервал между максимальным и минимальным числами называется диапазоном представления чисел в заданной ПСС.


2.2. Выбор системы счисления
Система счисления влияет на такие технические характеристики ЭВМ, как скорость вычислений, объем памяти, элементная база, сложность алгоритмов выполнения арифметических операций.

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

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

длина числа зависит от основания системы счисления;

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

Наибольшее распространение в ЭВМ имеет двоичная система счисления. В этой системе используются только две цифры: 0 и 1. Двоичное изображение числа требует большего (для многоразрядного числа примерно в 3,3 раза [8]) количества разрядов, чем его десятичное представление. Тем не менее, применение двоичной системы счисления создает большие удобства при проектировании ЭВМ, т.к. для представления в машине разряда двоичного числа может быть использован любой простой элемент, имеющий всего два устойчивых состояния. Рациональность использования двоичной системы с точки зрения затрат оборудования можно оценить с помощью показателя экономичности системы счисления, равному произведению основания системы счисления на длину разрядной сетки:

С = q·n.

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

Учитывая, что Aq max = qn-1, можно определить требуемую длину разрядной сетки:

n = logq(Aq max+1).

Тогда для любой системы счисления

C = qlogq(Aq max+1).

Если допустить, что q - непрерывная величина, то сравнение двух систем счисления можно произвести по относительному показателю экономичности

,

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


Таблица 2.2

q

2

3

4

6

8

10

F

1,0

0,946

1,0

1,148

1,333

1,505


Рассматривая функцию F(q) как непрерывную, из условия dF/dq=0 можно определить минимум, который соответствует значению q = e 2,72.

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

M = (q-1)n = (q-1)logq(Aq max+1) .

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

.

Результаты сравнения представлены в табл.2.3 [18].


Таблица 2.3

q

2

3

4

5

6

7

8

9

10

Ф

1,0

1,262

1,5

1,725

1,917

2,138

2,333

2,524

2,709

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

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

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

оптимизация аппаратурных затрат при электронном исполнении элементов ЭВМ;

высокая помехоустойчивость представления информации посредством двух электрически устойчивых состояний;

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

высокая скорость решения арифметических и логических задач.
2.3. Перевод чисел из одной ПСС в другую
Поскольку человеку удобнее пользоваться десятичными числами, а ЭВМ работает в двоичной системе счисления, то необходим перевод из одной ПСС в другую. Одно и то же число в системах счисления с основаниями q1 и q2 можно представить следующим образом:

Aq1 =aiq1i =biq2i = Aq2 .

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

Aq2 = bkq2k + bk-1q2k-1 + ... + b1q21 + b0q20 . (2.2)

Переписав это выражение по схеме Горнера, получим

Aq2 = (...(bkq2 + bk-1)q2 + ... + b1)q2 + b0 . (2.3)

Разделив правую часть выражения (2.3) на величину основания q2 , получим целую часть (...(bkq2 + bk-1)q2 + ... + b1)и остаток, представляющий собой коэффициент b0. Разделив полученное частное на q2 , также получим целую часть от этого деления и остаток - коэффициент b1.

Таким образом, перевод целых чисел из ПСС с основанием q1 в ПСС с основанием q2 заключается в следующем:

исходное число, записанное в системе с основанием q1, разделить на q2, выраженное в системе счисления с основанием q1, и определить остаток;

частное снова разделить на q2 и т.д., пока полученное частное не станет меньше, чем q2.

Искомое число записывается в таком порядке: последнее частное, последний остаток, предпоследний остаток и т.д., первый остаток.
Пример 2.1. Перевести десятичное число А(10) = 46 в двоичную и шестнадцатеричную системы счисления.

Решение.



Ответ: A(2)= 101110; A(16)= 2Е, т.к. на основании табл.2.1 можно записать b1 = 2; b0 = E.
Обратный перевод в десятичную систему счисления можно осуществить, используя соотношение (2.2).
Пример 2.2. Перевести двоичное число A(2) = 101110 и шестнадцатеричное число А(16) = 2Е в десятичную систему счисления.

Решение.

1. A(10) = 125 + 024 + 123 + 122 + 121 + 020 = 46 .

2. На основании табл.2.1 заменим шестнадцатеричную цифру Е ее десятичным эквивалентом 14.

А(10) = 2161 + 14160 = 46

Ответ: А(10) = 46.
Остается заметить, что для перевода чисел из ПСС с основанием q1 в ПСС с основанием q2, ни одна из которых не является десятичной, все арифметические операции (деление, умножение, сложение и вычитание) нужно производить в ПСС с основанием q1. Например, при переводе числа из пятеричной системы в троичную все вычисления должны производиться в пятеричной системе. Так как для человека привыкшего к десятичной системе, это крайне неудобно, то в этом случае целесообразно воспользоваться десятичной системой в качестве промежуточной, т.е. сделать перевод из пятеричной системы в десятичную, а затем из десятичной в троичную.
2.3.2. Перевод дробей
В общем виде число, представляющее собой правильную дробь, записанное в ПСС с основанием q1, имеет вид

Aq1 = a-1q1-1 + ... + a-mq1-m .

Тогда в новой системе счисления с основанием q2 это число будет изображено как

Aq2 = b-1q2-1 + ... + b-sq2-s (2.4)

Если переписать выражение (2.4) по схеме Горнера, то получим следующее:

Aq2 = q2-1(b-1 + q2-1(b-2 + ... +q2-1b-s)...). (2.5)

При умножении правой части выражения на q2 получим новую неправильную дробь, в целой части которой будет цифра b-1 (умножение на величину q2 используется вместо деления на величину q2-1 = 1/q2 ). Затем умножив оставшуюся дробную часть на величину основания q2, получим дробь, в целой части которой будет b-2, и т.д. Повторяя процесс умножения S раз, найдем s цифр числа в новой системе счисления. При этом все действия должны выполняться по правилам q1-арифметики, и следовательно, в целой части получающихся дробей будут появляться эквиваленты цифр новой системы счисления, записанные в исходной системе счисления.

При переводе правильных дробей из одной ПСС в другую можно получить дробь в виде бесконечного ряда (например, при переводе числа А(10) = 0,8 в двоичную систему получается бесконечная дробь). Поэтому перевод числа можно считать завершенным, если:

получится дробная часть, имеющая во всех разрядах нули;

будет достигнута требуемая точность перевода;

произойдет заполнение разрядной сетки.
Пример 2.3. Перевести десятичную дробь А(10) = 0,68 в двоичную систему счисления с точностью до 6 двоичных разрядов и в шестнадцатеричную - с точностью до 4 шестнадцатеричных разрядов.

Решение.



Ответ: А(2) = 0,101011. Заменив десятичные цифры, получающиеся в целой части, на шестнадцатеричные (табл.2.1), можно записать:

b-1 = А; b-2 = Е; b-3 = 1; b-4 = 4. А(16) = 0,АЕ14.
Обратный перевод в десятичную систему можно осуществить, пользуясь соотношением (2.4). В случае, если перевод из десятичной системы в ПСС с основанием qi осуществлялся с точностью до S разрядов, то при обратном переводе возникает погрешность.
Пример 2.4. Перевести двоичное число А(2) = 0,101011 и шестнадцатеричное число А(16) = 0,АЕ14 в десятичную систему счисления.

Решение.

1. А(10) = 12-1 + 02-2 + 12-3 + 02-4 + 12-5 + 12-6 = 0,671875 .

Ответ: А(10) = 0,671875.

2. На основании табл.2.1 заменяем шестнадцатеричные цифры их десятичными эквивалентами:

А(10) = 1016-1 + 1416-2 + 116-3 + 416-4 = 0,679988

Ответ: А(10) = 0,679988.
Для перевода неправильных дробей из одной системы счисления в другую необходим раздельный перевод целой и дробной частей по правилам, описанным выше. Полученные результаты записывают в виде новой неправильной дроби в ПСС с основанием q2.


2.3.3. Системы счисления с кратными основаниями
ПСС с основаниями q1 и q2 называются системами с кратными основаниями, если выполняется равенство

q1 = q2k ,

где k = 2, 3, 4, ...

Таким образом, для двоичной системы счисления кратными будут системы с основаниями 4, 8, 16, 32 и т.д. Для троичной ПСС кратными будут системы с основаниями 9, 27, 81 и т.д.

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

Двоичные эквиваленты цифр четверичной, восьмеричной и шестнадцатеричной систем счисления приведены в табл.2.4.
Пример 2.5. Перевести двоичное число А(2) = 10011101,1001011 в четверичную и шестнадцатеричную системы.

Решение.



Ответ: А(4) = 2131,2112.



Ответ: А(16) = 9D,96.


Таблица 2.4

q = 2

q = 4

q = 2

q = 8

q = 2

q = 16

00

0

000

0

0000

0

01

1

001

1

0001

1

10

2

010

2

0010

2

11

3

011

3

0011

3







100

4

0100

4







101

5

0101

5







110

6

0110

6







111

7

0111

7













1000

8













1001

9













1010

A













1011

B













1100

C













1101

D













1110

E













1111

F



В случае обратного перевода из q1 в q2 (если q1 > q2) каждая цифра числа в системе с основанием q1 заменяется соответствующей диадой, триадой, тетрадой и т.д. цифр системы с основанием q2.
Пример 2.6. Перевести восьмеричное число А(8) = 305,62 в двоичную систему счисления.

Решение.




Ответ: А(2) = 11000101,11001.
Шестнадцатеричная (и реже восьмеричная) система счисления используется при составлении программ для более короткой и удобной записи двоичных кодов команд, т.к. эти системы не требуют специальных операций для перевода в двоичную систему.

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

В следующем примере показано, что при переводе из десятичной системы в двоичную, используя в качестве промежуточной системы восьмеричную, число операций деления сокращается в четыре раза. Следовательно, примерно во столько же раз увеличивается скорость перевода.
Пример 2.7. Перевести десятичное число А(10) = 345 в двоичную систему счисления, используя в качестве промежуточной восьмеричную систему счисления.

Решение.


Ответ: А = 345(10) = 531(8) = 101011001(2).






2. Системы счисления
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации