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

записи чисел с помощью цифр.

 

 

СС

непозиционные

позиционные

иероглифические

алфавитные

специальные

однородные

неоднородные

символические

с постоянным весом

с естественным порядком весов

с искусственным порядком весов

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

1) отсутствие нуля;

2) неограниченность количества символов

Недостатки:

3) сложность арифметических действий с числами.

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

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

В общем виде число A в позиционной системе счисления может быть представлено следующим образом:
A=anpn-1…p1+an-1pn-2…p1+…+a2p1+a1,

где:

ai — цифра i-го разряда числа, ai = (0, рj –1) - база СС;

pj — основание СС

i
pi = П – вес i-го разряда числа
j=0

a0=5; a1=3;a2=2. pj=10;

В них pi – e не зависят друг от друга и могут принимать любые значения - это с.с. со смешанным основанием.

Т.к. произведение двух соседних (четного и нечетного) разрядов равно 10, то двумя двоично-пятеричными разрядами можно кодировать одну десятичную цифру

Неоднородные позиционные системы счисления

Специально для ЭВМ была создана неоднородная двоично-пятеричная система счисления, в которой в нечетных разрядах
основание p1 = 5 (ai = 0 – 4), а в четных разрядах основание p2 = 2 (аi = 0, 1).

2
p2= П 10= 10×10 =20
0

База = 0,9.

позиционных систем при 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

получаем 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.

Так число 23510 в двоично-пятеричной системе счисления:

А= 23510 = 02 ∙03 ∙10.

Здесь n = 6, основания p1=5;p2=2;р3=5;p4=2;p5=5;р6=2.

При вычислении количественного эквивалента числа A2 – 5

Однородные позиционные системы счисления

Знаменатель геометрической прогрессии p называется основанием
системы счисления. Основанием однородной позиционной системы м. б.
любое целое число.

в сокращенном виде: anan-1… a1a0a-1…a-k, а название системы определяет ее основание: десятичная, двоичная, восьмеричная и т. д.

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

Пример: двоично-десятичная система с весами 8—4—2—1. В ней каждая цифра десятичного числа кодируется двоичной тетрадой.

Так, десятичное число 1593 в этой двоично-десятичной системе примет вид: 0001010110010011.

Десятичное число 1593 в этой системе примет соответственно следующий вид: 0001101111110011.

Видно, что этот код является самодополняющимся.

Пример: системы счисления с искусственными весами разрядов - двоично-десятичная система счисления с весами 2— 4—2—1.

т.е. если их десятичная сумма равна 9, в системе 2-4-2-1 они дополняют
друг друга до 1510=11112421.

- это такие системы, в которых цифры одной системы счисления кодируются цифрами другой системы

является «код с избытком три» — «8421» + 3. Он получается из естественного кода 8421 добавлением к нему числа 310 = 00112. Десятичное число 1593 в этой системе примет соответственно следующий вид: 0100100011000110.

постоянного веса. Так в числе 810, представленном в коде Грея, единица второго разряда имеет вес, равный трем

Это рефлексный код – можно выделить оси симметрии. Главная ось симметрии расположена между кодами (2n-1 — 1) и 2n-1 (отсюда название).

Специальные системы счисления

Это системы счисления с основаниями 1,1 и 1,0,1 .

Позиционные системы счисления с непостоянными (искусственными) весами разрядов

Пример: код Грея. В нем соседние числа различаются цифрой только в одном разряде.

отдельности никак не характеризует какое-либо число. Определенным комбинациям цифр условно поставлены в соответствие определенные числа. Примерами символических систем счисления являются знакологарифмическая система счисления и система представления чисел в остатках или система остаточных классов (СОК).

Если целым числам А и В соответствует один и тот же остаток от деления на третье число 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:

Символические системы счисления

СОК поразрядными. При сложении чисел переносов не возникает:

110
+
510

610

111С0К
+
120С0К

231СОК

Т.е. основание с.с. 16, цифры обозначаются первые 10: 0-9, остальные 6
(10-15): A-F:

Выбор системы счисления для применения в ЭВМ.

- б.д. ЭВМ
- объем памяти.

Учитываются следующие факторы:

1. Наличие физических элементов – проще чем меньше состояний, т.е. чем меньше основание с.с. → 2я с.с.

4. Б.д. вычислений – чем больше количество цифр в с.с., тем меньше б.д. ЭВМ → 2я с.с.

3. Трудоемкость выполнения операций – чем меньше цифр, тем проще → 2я с.с.

2. Экономичность системы – чем больше основание с.с., тем меньше количество разрядов (элементов) для изображения числа, но тем больше количество символов, которое изображает каждый элемент, т.е. больше количество устойчивых состояний → выше сложность.
Более эффективен р=3, затем р=2,р=4, (уступают на 5,8%), т.к. троичный элемент менее надежен, то двоичная с.с.

От нее зависят:

м месте с.с., где:
-проще арифметические действия
-проще запомнить операции сложения, вычитания, умножения, деления → 2я с.с.

7. Наибольшая помехоустойчивость. При нахождении помехи не основной сигнал (цифра) наибольшая ошибка в устройствах с с.с. с самым большим основанием → 2я с.с.

5. Наличие формального математического аппарата для анализа и синтеза вычислительных устройств – алгебра логики → двоичная логика → двоичные элементы. Т.е. для анализа и синтеза один и тот же математический аппарат → 2я с.с.

чисел используются два символа, а веса разрядов меняются по закону 2±k, где k — произвольное целое число). Классической двоичной системой является система с символами 0, 1.

n
A = Σai×2i
i= -k

В общем виде все двоичные числа представляются
в виде полинома:

Сложение производится по правилам сложения полиномов. Поэтому i-й разряд суммы Si и перенос Пi из данного разряда в (i + 1)-й будет определяться согласно выражению: ai + bi + Пi-1 = Si + 2Пi