Дискретные структуры. Системы счисления. (Раздел 1)

1.

ДИСКРЕТНЫЕ СТРУКТУРЫ
Раздел 1
СИСТЕМЫ СЧИСЛЕНИЯ
Компьютерная арифметика
1

2.

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

3.

Непозиционными - такие системы счисления, для которой
значение символа не зависит от его положения в числе.
Недостатки:
1) отсутствие нуля;
2) неограниченность количества символов
3) сложность арифметических действий с числами.
Позиционные - системы счисления, где значение каждой цифры в
числе строго зависит от её позиции.
Имеет ограниченное число символов.
Основное достоинство таких СС - удобство выполнения
арифметических операций.
В общем виде число A в позиционной системе счисления может
быть представлено следующим образом:
A=anpn-1…p1+an-1pn-2…p1+…+a2p1+a1,
где:
ai — цифра i-го разряда числа, ai = (0, рj –1) - база СС;
i
pj — основание СС
pi = П – вес i-го разряда числа
Компьютерная арифметика
3
j=0

4.

Пример:
235 = 2 10 10 +3 10+5
Здесь a0=5; a1=3;a2=2. pj=10;
База = 0,9.
2
p2= П 10= 10 10 =20
0
Неоднородные позиционные системы счисления
В них pi – e не зависят друг от друга и могут принимать любые
значения - это с.с. со смешанным основанием.
Специально для ЭВМ была
0
00
5
10
создана неоднородная двоично1
01
6
11
пятеричная система счисления,
2
02
7
12
в которой в нечетных разрядах
3
03
8
13
основание p1 = 5 (ai = 0 – 4), а в
4
04
9
14
четных разрядах основание p2 =
2 (аi = 0, 1).
Т.к. произведение двух соседних (четного и нечетного) разрядов равно
10, то двумя двоично-пятеричными разрядами можно кодировать одну
Компьютерная арифметика
4
десятичную цифру
A10
a2–5
A10
a2–5

5.

Так число 23510 в двоично-пятеричной системе счисления:
А= 23510 = 02 03 10. Здесь n = 6, основания p1=5;p2=2;р3=5;p4=2;p5=5;р6=2.
При вычислении количественного эквивалента числа A2 – 5
получаем A = 0 5 2 5 2 5+2 2 5 2 5+0 5 2 5+
+ 3 2 5+1 5+0 = 200+30+5 = 23510.
Однородные позиционные системы счисления
Это частный случай позиционных систем при pi = рj для всех i и j,
т. е. в них веса отдельных разрядов представляют собой ряд членов
геометрической прогрессии со знаменателем р (системы с
естественным порядком весов) иначе с искусственным порядком
весов). Поэтому число в однородных системах может быть
представлено полиномом вида:
A = an pn + an - 1pn - 1+…+a1p1+ a0p0+a- 1p-1+…+a-kp-k
n
A= aipi ), причем ai = (0, (p-1)).
i= -k
Знаменатель геометрической прогрессии p называется основанием
системы счисления. Основанием однородной позиционной системы м. б.
любое целое число.
Компьютерная арифметика
5

6.

Обычно число в однородной позиционной системе записывается в
сокращенном виде: anan-1… a1a0a-1…a-k, а название системы
определяет ее основание: десятичная, двоичная, восьмеричная и т. д.
Кодированные позиционные системы счисления - это такие
системы, в которых цифры одной системы счисления кодируются
цифрами другой системы
Пример: двоично-десятичная система с весами 8—4—2—1. В ней
каждая цифра десятичного числа кодируется двоичной тетрадой.
Так, десятичное число 1593 в этой двоично-десятичной системе
примет вид: 0001010110010011.
Пример: системы счисления с искусственными весами разрядов двоично-десятичная система счисления с весами 2— 4—2—1.
Десятичное число 1593 в этой системе примет соответственно
следующий вид: 0001101111110011.
Видно, что этот код является самодополняющимся.
т.е. если их десятичная сумма равна 9, в системе 2-4-2-1 они дополняют
друг друга до 1510=11112421.
Компьютерная арифметика
6

7.

Еще одним самодополняющимся кодом является «код с избытком три»
— «8421» + 3. Он получается из естественного кода 8421 добавлением к
нему числа 310 = 00112. Десятичное число 1593 в этой системе примет
соответственно следующий вид: 0100100011000110.
цифра
8421
8421+3
цифра
8421
0
0000
0000
0011
5
0101
1011
1000
1
0001
0001
0100
6
0110
1100
1001
2
0010
0010
0101
7
0111
1101
1010
3
0011
0011
0110
8
1000
1110
1011
4
0100
0100
0111
9
1001
1111
1100
2421
Компьютерная арифметика
2421
8421+3
7

8.

Специальные системы счисления
Это системы счисления с основаниями 1,1 и 1,0,1 .
Позиционные системы счисления с
непостоянными (искусственными) весами разрядов
Пример: код Грея. В нем соседние числа различаются
цифрой только в одном разряде.
Двоичные разряды в коде Грея не имеют постоянного веса. Так в
числе 810, представленном в коде Грея, единица второго разряда имеет
вес, равный трем
10 СС
2 СС
Код Грея
10 СС
2 СС
Код Грея
0
0000
0000
8
1000
1100
1
0001
0001
9
1001
1101
2
0010
0011
10
1010
1111
3
0011
0010
11
1011
1110
4
0100
0110
12
1100
1010
5
0101
0111
13
1101
1011
6
0110
0101
14
1110
1001
7
0111
0100
15
1111
1000
Это рефлексный код – можно выделить оси симметрии. Главная ось
симметрии расположена Компьютерная
между кодами
(2n-1 — 1) и 2n-1 (отсюда
арифметика
8
название).

9.

Символические системы счисления
В них цифры являются символами, каждый из которых в отдельности
никак не характеризует какое-либо число. Определенным комбинациям
цифр условно поставлены в соответствие определенные числа.
Примерами символических систем счисления являются
знакологарифмическая система счисления и система представления
чисел в остатках или система остаточных классов (СОК).
Если целым числам А и В соответствует один и тот же остаток
от деления на третье число S, то числа А и В называются
сравнимыми по mod S, что выражается записью A В (mod S).
Число в СОК изображается в виде остатков от деления заданного
числа на ряд взаимно простых чисел S1, S2, …, Sn . При этом
образуется число с весами разрядов, соответственно равными S1, S2,
…, Sn, т.е. Aсок= a1,a2,a3,…,an, где ai = А10 – ki Si и ki = [А10/Si ],
где [x] — целая часть х. Следовательно, A ai (mod Si). Остаток
ai называют также вычетом числа А по модулю Si.
Так для S1=2, S2=3, S3=5:
Компьютерная арифметика
9

10.

Десятичная
система
СОК
Десятичная
система
а1
а2
а3
0
0
0
0
1
1
1
2
0
3
СОК
а1
а2
а3
8
0
2
3
1
9
1
0
4
2
2
10
0
1
0
1
0
3
11
1
2
1
4
0
1
4
12
0
0
2
5
1
2
0
13
1
1
3
6
0
0
1
14
0
2
4
7
1
1
2
15
1
0
0
Операции сложения, вычитания и умножения являются в СОК
поразрядными. При сложении чисел переносов не возникает:
110
111С0К
+
+
510
120С0К
610
231СОК
Компьютерная арифметика
10

11.

Шестнадцетиричная система счисления
Т.е. основание с.с. 16, цифры обозначаются первые 10: 0-9, остальные 6
(10-15): A-F:
10
2
8
16
10
2
8
16
0
0000
0
0
8
1000
10
8
1
0001
1
1
9
1001
11
9
2
0010
2
2
10
1010
12
A
3
0011
3
3
11
1011
13
B
4
0100
4
4
12
1100
14
C
5
0101
5
5
13
1101
15
D
6
1100
6
6
14
1110
16
E
7
0111
7
7
15
1111
17
F
Компьютерная арифметика
11

12.

Выбор системы счисления для применения в ЭВМ.
От нее зависят:
- б.д. ЭВМ
- объем памяти.
Учитываются следующие факторы:
1. Наличие физических элементов – проще чем меньше состояний,
т.е. чем меньше основание с.с. 2я с.с.
2. Экономичность системы – чем больше основание с.с., тем
меньше количество разрядов (элементов) для изображения
числа, но тем больше количество символов, которое изображает
каждый элемент, т.е. больше количество устойчивых состояний
выше сложность.
Более эффективен р=3, затем р=2,р=4, (уступают на 5,8%), т.к.
троичный элемент менее надежен, то двоичная с.с.
3. Трудоемкость выполнения операций – чем меньше цифр, тем
проще 2я с.с.
4. Б.д. вычислений – чем больше количество цифр в с.с., тем меньше
б.д. ЭВМ 2я с.с.
Компьютерная арифметика
12

13.

5. Наличие формального математического аппарата для анализа и
синтеза вычислительных устройств – алгебра логики двоичная
логика двоичные элементы. Т.е. для анализа и синтеза один и тот
же математический аппарат 2я с.с.
6. Удобство работы человека с ЭВМ
10я с.с. На 2 м месте с.с., где:
-проще арифметические действия
-проще запомнить операции сложения, вычитания, умножения,
деления 2я с.с.
7. Наибольшая помехоустойчивость. При нахождении помехи не
основной сигнал (цифра) наибольшая ошибка в устройствах с с.с. с
самым большим основанием 2я с.с.
Компьютерная арифметика
13

14.

ДВОИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ
это такая система, в которой для изображения чисел используются два
символа, а веса разрядов меняются по закону 2±k, где k —
произвольное целое число). Классической двоичной системой
является система с символами 0, 1.
В общем виде все двоичные числа представляются n
в виде полинома:
A = ai 2i
i= -k
Сложение производится по правилам сложения полиномов. Поэтому
i-й разряд суммы Si и перенос Пi из данного разряда в (i + 1)-й будет
определяться согласно выражению: ai + bi + Пi-1 = Si + 2Пi
ai
bi
Пi-1
Si
Пi
ai
bi
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
1
0
0
1
Пi-1
Si
Пi
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
1
Компьютерная арифметика
14