Представление данных в памяти эвм

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

Элементарная ячейка памяти ЭВМ имеет длину 8 бит (байт). Каждый байт имеет свой номер (его называют адресом). Наибольшую последовательность бит, которую ЭВМ может обрабатывать как единое целое, называют машинным словом. Длина машинного слова зависит от разрядности процессора и может быть равной 16, 32 битам и т.д.

Для кодирования символов достаточно одного байта. При этом можно представить 256 символов (с десятичными кодами от 0 до 255). Набор символов персональных ЭВМ IBM PC чаще всего является расширением кода ASCII (American Standart Code for Information Interchange — стандартный американский код для обмена информацией). В настоящее время в новых операционных системах используется UNICODE. В этой системе для кодирования одного байта применяется 2 байта, что позволяет кодировать 65536 символов. Это вызвано необходимостью размещения всех символов всех алфавитов народоа мира.

В некоторых случаях при представлении в памяти ЭВМ чисел используется смешанная двоично-десятичная «система счисления», где для хранения каждого десятичного знака нужен полубайт (4 бита) и десятичные цифры от 0 до 9 представляются соответствующими двоичными числами от 0000 до 1001. Например, упакованный десятичный формат, предназначенный для хранения целых чисел с 18 значащими цифрами и занимающий в памяти 10 байт (старший из которых знаковый), использует именно этот вариант.

Другой способ представления целых чисел - дополнительный код. Диапазон значений величин зависит от количества бит памяти, отведенных для их хранения. Например, величины типа Integer (все названия типов данных здесь и ниже представлены в том виде, в каком они приняты в языке программирования Pascal, в других языках такие типы данных тоже есть, но могут иметь другие названия) лежат в диапазоне от - 32768 (- 2¹⁵) до 32767 (2¹⁵ - 1), и для ж хранения отводится 2 байта; типа Longlnt - в диапазоне от -2³¹ до 2³¹ - 1 и| размещаются в 4 байтах; типа Word - в диапазоне от 0 до 65535 (2¹⁶- 1) (используется 2 байта) и т.д.

Как видно из примеров, данные могут быть интерпретированы как числа со знаками, так и без знаков. В случае представления величины со знаком самый левый (старший) разряд указывает на положительное число, если содержит нуль, | и на отрицательное, если - единицу.

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

Дополнительный код положительного числа совпадает с его прямым кодом. Прямой код целого числа может быть получен следующим образом: число переводится в двоичную систему счисления, а затем его двоичную запись слева дополняют таким количеством незначащих нулей, сколько требует тип данных, к которому принадлежит число. Например, если число 37₍₁₀₎ = 100101₍₂₎ объявлено величиной типа Integer, то его прямым кодом будет 0000000000100101, а если величиной типа Longlnt, то его прямой код будет 00000000000000000000000000100101. Для более компактной записи чаще используют шестнадцатеричный код. Полученные коды можно переписать соответственно как 0025₍₁₆₎ и 00000025₍₁₆₎.

Дополнительный код целого отрицательного числа может быть получен по следующему алгоритму:

1) записать прямой код модуля числа;

2) инвертировать его (заменить единицы нулями, нули - единицами);

3) прибавить к инверсному коду единицу.

Например, запишем дополнительный код числа (-37), интерпретируя его как величину типа Longlnt:

1) прямой код числа 37 есть 00000000000000000000000000100101;

2) инверсный код 11111111111111111111111111011010;

3) дополнительный код 11111111111111111111111111011011 или FFFFFFDB_(I6). При получении числа по его дополнительному коду прежде всего необходимо определить его знак. Если число окажется положительным, то просто перевести его код в десятичную систему счисления. В случае отрицательного числа необходимо выполнить следующий алгоритм:

1) вычесть из кода числа 1;

2) инвертировать код;

3) перевести в десятичную систему счисления. Полученное число записать со
знаком минус.

Примеры. Запишем числа, соответствующие дополнительным кодам:

а) 0000000000010111. Поскольку в старшем разряде записан нуль, то результат
будет положительным. Это код числа 23;

б) 1111111111000000. Здесь записан код отрицательного числа. Исполняем алгоритм:

1) 1111111111000000₍₂₎ – 1₍₂₎ = 1111111110111111₍₂₎

2) 0000000001000000;

3) 1000000₍₂₎ = 64₍₁₀₎.
Ответ: - 64.

 

Несколько иной способ применяется для представления в памяти персонального компьютера действительных чисел. Рассмотрим представление величин с плавающей точкой.

Любое действительное число можно записать в стандартном виде M∙10^p, где 1 <М< 10, р— целое. Например, 120100000 = 1,201∙0⁸. Поскольку каждая позиция десятичного числа отличается от соседней на степень числа 10, умножение на 10 эквивалентно сдвигу десятичной запятой на одну позицию вправо. Аналогично деление на 10 сдвигает десятичную запятую на позицию влево. Поэтому приведенный выше пример можно продолжить: 120100000 = 1,20Ы0⁸= 0,120Ы0⁹= 12,01-10⁷... Десятичная запятая «плавает» в числе и больше не помечает абсолютное место между целой и дробной частями.

В приведенной выше записи М называют мантиссой числа, а p - его порядком. Для того чтобы сохранить максимальную точность, вычислительные машины почти всегда хранят мантиссу в нормализованном виде, что означает, что мантисса в данном случае есть число, лежащее между 1₍₁₀₎ и 2₍₁₀₎ (1 < М< 2). Основание системы счисления здесь, как уже отмечалось выше, — число 2. Способ хранения мантиссы с плавающей точкой подразумевает, что двоичная запятая находится на фиксированном месте. Фактически подразумевается, что двоичная запятая следует после первой двоичной цифры, т.е. нормализация мантиссы делает единичным первый бит, помещая тем самым значение между единицей и двойкой. Место, отводимое для числа с плавающей точкой, делится на два поля. Одно поле содержит знак и значение мантиссы, а другое содержит знак и значение порядка.

Персональный компьютер IBM PC позволяет работать со следующими действительными типами (диапазон значений указан по абсолютной величине):

Тип	Диапазон	Мантисса	Байты
Real	2,9∙10^-39…1,7∙10^38	11-12
Single	1,5∙10^-45…3,4∙10^38	7-8
Double	5,0∙10^-324…1,7∙10^308	15-16
Extended	3,4∙10^-4932…1,1∙10^4932	19-20

Покажем преобразование действительного числа для представления его в памяти ЭВМ на примере величины типа Double.

Как видно из таблицы, величина это типа занимает в памяти 8 байт. На рисунке показано, как здесь представлены поля мантиссы и порядка:

 

S	Смещенный порядок	Мантисса

Можно заметить, что старший бит, отведенный под мантиссу, имеет номер 51, т.е. мантисса занимает младшие 52 бита. Черта указывает здесь на положение двоичной запятой. Перед запятой должен стоять бит целой части мантиссы, но поскольку она всегда равна 1, здесь данный бит не требуется и соответствующий разряд отсутствует в памяти (но он подразумевается). Значение порядка для упрощения вычислений и сравнения действительных чисел хранится в виде смещенного числа, т.е. к настоящему значению порядка перед записью его в память прибавляется смещение. Смещение выбирается так, чтобы минимальному значению порядка соответствовал нуль. Например, для типа Double порядок занимает 11 бит и имеет диапазон от 2"¹⁰²³ до 2¹⁰²³, поэтому смещение равно 1023₍₁₀₎ = 1111111111₍₂₎. Наконец, бит с номером 63 указывает на знак числа.

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

1) перевести модуль данного числа в двоичную систему счисления;

2) нормализовать двоичное число, т.е. записать в виде М-2^Р, где М— мантисса (ее целая часть равна 1₍₂₎) и р — порядок, записанный в десятичной системе счисления;

3) прибавить к порядку смещение и перевести смещенный порядок в двоичную систему счисления;

4) учитывая знак заданного числа (0 - положительное; 1 -отрицательное),
выписать его представление в памяти ЭВМ.

Пример. Запишем код числа —312,3125.

1) Двоичная запись модуля этого числа имеет вид 100111000,0101.

2) Имеем 100111000,0101 = 1,001110000101 • 2⁸.

3) Получаем смещенный порядок 8 + 1023 = 1031. Далее имеем 1031₍₁₀₎ = 10000000Ш₍₂₎.

4) Окончательно

 

Очевидно, что более компактно полученный код стоит записать следующим образом: С073850000000000₍₁₆₎.

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

Пример. Пусть дан код 3FEC600000000000₍₁₆₎ или

1) Прежде всего замечаем, что это код положительного числа, поскольку в разряде с номером 63 записан нуль. Получим порядок этого числа: 01111111110₍₂₎ = 1022₍₁₀₎;1022 - 1023 = -1.

2) Число имеет вид 1,1100011-2^-1 или 0,11100011.

3) Переводом в десятичную систему счисления получаем 0,88671875.

4. ЛОГИЧЕСКИЕ ОСНОВЫ

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

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

Аристотель исследовал различные формы суждений и их комбинаций, ввел понятие силлогизма, т.е. рассуждения, в котором из заданных двух суждений выводится третье. Как известно, в конце XVI века в алгебре словесная форма записи алгебраических выражений стала тормозить развитие науки и, чтобы облегчить выполнение алгебраических преобразований, была создана буквенная символика, позволяющая выполнять эти преобразования по строго определенным правилам. Точно также, чтобы облегчить проверку и преобразование сложных цепочек рассуждений, было создано особое буквенное исчисление.

Оно получило название алгебры логики или математической логики. Основы математической логики были заложены в XVII веке великим немецким математиком Г.Лейбницем (1646-1716).

Он сделал попытку построить первые логические исчисления, считая, что можно заменить простые рассуждения действиями со знаками, и привел соответствующие правила. Но Лейбниц высказал только идею, а развил ее окончательно англичанин Джордж Буль (1815-1864).

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

АЛГЕБРА ЛОГИКИ

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

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

1.сегодня идет дождь; 2. 1983г-високосный год; 3.стриж - перелетная птица.

Из этих трех высказываний первое может быть истинно или ложно, второе - ложно, третье - истинно. В этих высказываниях говорится только об одном факте (истинном или ложном), и потому они называются простыми. Основным понятием математической логики является высказывание.

ВЫСКАЗЫВАНИЕ это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

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

ОТРИЦАНИЕ (инверсия). Отрицание высказывания получим, если присоединим частицу НЕ к сказуемому высказывания или “НЕВЕРНО, ЧТО” ко всему выражению.

Как вы уже заметили, для обозначения отрицания над прописной буквой ставится черта (в этом случае читаем: А с чертой или не А) или знак 

Действие логического отрицания выражается следующей таблицей:

А	А

или словами: отрицая верное высказывание, мы говорим ложь (не истину); отрицая неверное высказывание, мы говорим истину.

УМНОЖЕНИЕ (конъюнкция). Умножение двух высказываний выражается с помощью союза И. Результат умножения называют логическим произведением. Обозначается знаками /\, &.

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

Например:

1. 2>3 5x5=15 (2>3) и (5x5=15)	А=0 В=0 А & В=0
2. 2<3 5x5=15 (2<3) и (5x5=15)	А=1 В=0 А & В=0
3. 2>3 5x5=25 (2>3) и (5x5=25)	А=0 В=1 А & В=0
4. 2<3 5x5=25 (2<3) и (5x5=25)	А=1 В=1 А & В=1
5. Погода безоблачная Не идет дождь Погода безоблачная И не идет дождь	А=1 В=1 А & В=1
6. Река Ангара вытекает из озера Байкал Сосна – вечнозеленое дерево Река Ангара вытекает из озера Байкал И сосна – вечнозеленое дерево	А=1 В=1 А & В=1

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

 

A	B	А & В		&
			или

СЛОЖЕНИЕ (дизъюнкция). Сложение двух высказываний выражается с помощью союза ИЛИ. Результат сложения называют логической суммой. Обозначается знаком V.

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

Например:

Логическая сумма допускает одновременную истинность îäíîãî èç двух высказываний, так как ее истинность определяется следующей таблицей:

A	B	А V В		V
			или

 

ТАБЛИЦЫ ИСТИННОСТИ

В алгебре высказываний любую логическую функцию можно выразить через основные логические операции, записать ее в виде логического выражения и упростить, применяя законы логики и свойства логических операций. По формуле логической функции легко рассчитать ее таблицу истинностè. Необходимо только учитывать порядок выполнения логических операций (приоритет) и скобки. Операции в логическом выражении выполняются слева направо с учетом скобок. Приоритет логических операций:

Номер приоритета	Имя функции	знак
3.	ИНВЕРСИЯ
2.	КОНЪЮНКЦИЯ	&
1.	ДИЗЪЮНКЦИЯ	V

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

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

Сложные высказывания часто называют формулами логики высказываний.

Построить таблицу истинности достаточно просто.

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в формуле;

2. определить число строк в таблице m= 2ⁿ;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов в таблице: число переменных и число операций;

6. выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n- разрядных двоичных чисел от 0 до 2ⁿ-1;

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

Пример.

Для формулы

Х = (А & В V  С)

составим следующую таблицу истинности:

A	B	C	A & B	С	А & В V С	(А & В V С)

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

а) определить количество наборов входных переменных;

б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю - 1;

в) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;

г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей, заполняя их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

ЗАКОНЫ ЛОГИКИ ВЫСКАЗЫВАНИЙ

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

Х1 = (А V В) & (А V С); Х2 = А V В&С

таблица истинности будет следующей:

А	В	С	АVВ	АVС	(АVВ)&(АVС)	В&С	АVВ&С

Шестой и восьмой столбцы в этой таблице одинаковы. Следовательно,

Х1=Х2 и (А V В) & (А V С) = А V В &С.

В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования формул. Приведем соотношения, отражающие эти законы.

1. Закон двойного отрицания:

(А)=А

2. Переместительный (коммутативный) закон:

-для логического сложения:

А V В= В V А;

-для логического умножения:

А & В = В & А.

В обычной алгебре

a + b = b + a, a * b =b * a.

3. Сочетательный (ассоциативный) закон:

- для логического сложения:

(А V В) V С = А V (В V С)= AV BVC;

- для логического умножения:

(А & В) & С = А & (В & С)=A & B & C.

В обычной алгебре

(a + b) + c = a + (b + c) = a + b + c,

a* (b * c) = (a * b) * c = a * b * c.

4. Распределительный (дистрибутивный) закон:

- для логического сложения:

(А V В) & С = (А & С) V (В & С);

- для логического умножения:

(А & В) V С = (А V С) & (В V С).

В обычной алгебре

(a + b)* c = a * c + b * c.

5. Закон общей инверсии (законы де Моргана):

- для логического сложения:

(А V В) = А & В;

- для логического умножения:

(А & В) = А V В.

6. Закон идемпотентности:

-для логического сложения:

А V А = А;

-для логического умножения:

А & А = А.

7. Законы исключения констант:

-для логического сложения:

А V 1 = 1, А V 0 = А;

-для логического умножения:

А & 1 = А, А & 0 = 0.

8. Закон противоречия:

А & А = 0

значение которого всегда равно 0 (никогда не истинно).

Например:

неверно, что поезд движется И поезд не движется;

9. Закон исключенного третьего:

А V А = 1

Из двух противоречивых высказываний одно истинно.

Например: верно, что снег белый ИЛИ снег не белый.

10. Закон поглощения:

-для логического сложения:

А V (А & В) = А;

- для логического умножения:

А & (А V В) = А.

11.Закон исключения (склеивания):

-для логического сложения:

(А & В) V (А & В) = A;

-для логического умножения:

(А V В) & (А V В) = A

5. ДОПОЛНИТЕЛЬНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

СТРОГАЯ ДИЗЪЮНКЦИЯ. В отличие от рассмотренной выше операции дизъюнкции, можно рассмотреть строгую дизъюнкцию (двойное или), которой в естественном языке соответствует связка либо, либо.Имеет обозначение 

Суть этой операции ясна из приведенной таблицы:

A	B	А  В		
			или

ИМПЛИКАЦИЯ (лат. Implicatio - тесно связываю), или логическое следование, соответствует обороту если, то и обозначается .

Высказывание А  В ложно в том и только в том случае, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Таблица истинности импликации:

 

A	B	А В		
			Или

ЭКВИВАЛЕНЦИЯ (лат. Aequivalens- равноценное), или равнозначность, соответствует оборотам речи тогда и только тогда и в том и только в том случае. Операция обозначается .

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

Таблица истинности эквиваленции:

A	B	А В
			или

НЕ ЭКВИВАЛЕНЦИЯ (лат. Aequivalens- равноценное), или сложение по модулю 2, ñîответствует оборотам речи тогда и только тогда (в том и только в том случае) если значения не совпадают. Операция обозначается ≠ или .

Выражение А ≠ В истинно в том и только в том случае, когда оба исходных высказывания одновременно принимают разные значения.

Таблица истинности не эквиваленции:

A	B	А ≠ В		≠
			или

ШТРИХ ШЕФФЕРА. (отрицание конъюнкции) в отличиè от рассмотренной выше операции принимает противоположное значение, т.е. если оба высказывания истинны, то результат ложен, а иначе результат истинен. Обозначается |

 

 

Суть этой операции ясна из приведенной таблицы:

A	B	А | В		|
			или

Приоритет логических операций. (порядок выполнения операций при вычислении логических выражений). Логические операции выполняются слева направо с учетом приоритета логической операции:

1. в начале выполняются операции с высшим приоритетом,

1. равноприîритетные операции выполняются слева направо.

Уровень приоритета	Операции
	&
	V
	, , ≠, |, 

Пример.

Рассмотрим два высказывания:

А={ Петя выучит уроки };

В={ Пете поставят хорошую отметку }.

Их эквиваленцией является новое высказывание:

А В = {Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку}.

Это высказывание истинно, если:

1. Петя не выучит уроки и Пете не поставят хорошую отметку;

1. Петя выучит уроки и Пете поставят хорошую отметку.

Это высказывание ложно, если: