ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ

Системы счисления и формы представления чисел

Информация в ЭВМ кодируется, как правило, в двоичной или в двоично-десятичной системе счисления.

Система счисления - это способ наименования и изображения чисел с помощью символов, имеющих определенные количественные значения.

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

В позиционной системе счисления количественное значение каждой цифры зависит от ее места (позиции) в числе. В непозиционной системе счисления цифры не меняют своего количественного значения при изменении их расположения в числе. Количество (Р) различных цифр, используемых для изображения числа в позиционной системе счисления, называется основанием системы счисления. Значения цифр лежат в пределах от 0 до Р-1. В общем случае запись любого смешанного числа в системе счисления с основанием Р будет представлять собой ряд вида:

a_m-1P^m-1+a_m-2P^m-2+...+a₁P¹+a₀P^O+a_-1P^-1+a_-2P^-2+...+a_-sP^-s, (1)

где нижние индексы определяют местоположение цифры в числе (разряд):

• положительные значения индексов - для целой части числа (m разрядов);

• отрицательные значения - для дробной (s разрядов).

Пример 4.1. Позиционная система счисления - арабская десятичная система, в которой:основание P=10, для изображения чисел используются 10 цифр (от 0 до 9). Непозиционная система счисления - римская, в которой для каждого числа используется специфическое сочетание символов (XIV, CXXVII и т.п.).

Максимальное целое число, которое может быть представлено в т разрядах:

N_maх=P^m-1.

Минимальное значащее (не равное 0) число, которое можно записать в s разрядах дробной части:

N_min=P^-s.

Имея в целой части числа m, а в дробной s разрядов, можно записать всего P^m+s разных чисел.

Двоичная система счисления имеет основание Р=2 и использует для представления информации всего две цифры: 0 и 1. Существуют правила перевода чисел из одной системы счисления в другую, основанные в том числе и на соотношении (1).

Пример 4.2.

101110,101₍₂₎ =1*2⁵+0*2⁴+1*2³+l*2²+1*2¹+0*2⁰+l*2^-1+0*2^-2+l*2^-3=46,625₍₁₀₎ ,

т.е. двоичное число 101110,101 равно десятичному числу 46,625.

В вычислительных машинах применяются две формы представления двоичных чисел:

• естественная форма или форма с фиксированной запятой (точкой);

• нормальная форма или форма с плавающей запятой (точкой).

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

Пример 4.3. В десятичной системе счисления имеются 5 разрядов в целой части числа (до запятой) и 5 разрядов в дробной части числа (после запятой); числа, записанные в такую разрядную сетку, имеют вид:

+00721,35500; +00000,00328; -10301,20260.

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

Пример 4.4. Диапазон значащих чисел (N) в системе счисления с основанием Р при наличии m разрядов в целой части и s разрядов в дробной части числа (без учета знака числа) будет:

Р^-s ≤ N ≤ Р^m- P^-s.

При Р=2, m=10 и s = 6: 0,015≤ N≤ 1024.

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

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

N=±MP^±r,

где М-мантисса числа (|М| < 1);

r- порядок числа (r- целое число);

Р- основание системы счисления.

Пример 4.5. Приведенные в примере 4.3 числа в нормальной форме запишутся так:

+0,721355*10³; +0,328* 10^-3; -0,103012026*10⁵.

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

Пример 4.6. Диапазон значащих чисел в системе счисления с основанием Рпри наличии m разрядов у мантиссы и s разрядов у порядка (без учета знаковых разрядов порядка и мантиссы) будет:

P^-m*P^-(P-1) ≤ N ≤ (1-P^-m)*P^(P-1).

При P=2, m=10 и s=6 диапазон чисел простирается примерно от 10^-19 до 10¹⁹ .

Знак числа обычно кодируется двоичной цифрой, при этом код0 означает знак "+", код 1 -знак "-".

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

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

Таблица 4.1. Таблица двоичных кодов десятичных и шестнадцатеричных цифр.

Пример 4.7. Десятичное число 9703 в двоично-десятичной системе выглядит так:

1001011100000011.

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

Для изображения цифр, больших 9, в шестнадцатеричной системе счисления применяются буквы А=10, В=11, С=12, D=13, Е=14, F=15.

Пример 4.8. Шестнадцатеричное число F17B в двоичной системе выглядит так:

1111000101111011.

Варианты представления информации в ПК

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

Таблица 4.2. Двоичные совокупности

Последовательность нескольких битов или байтов часто называют полем данных Биты в числе (в слове, в поле и т.п.) нумеруются справа налево, начиная с 0-го разряда.

В ПК могут обрабатываться поля постоянной и переменной длины.

Поля постоянной длины:

Числа с фиксированной запятой чаще всего имеют формат слова и полуслова, числа с плавающей запятой - формат двойного и расширенного слова.

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

Пример 4.9. Структурно запись числа -193₍₁₀₎=-11000001₍₂₎ в разрядной сетке ПК выглядит следующим образом.

Число с фиксированной запятой формата слово со знаком:

Число с плавающей запятой формата двойное слово:

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

В упакованном формате для каждой десятичной цифры отводится по 4 двоичных разряда (полбайта), при этом знак числа кодируется в крайнем правом полубайте числа (1100 - знак "+" и 1101 - знак "-").

Структура поля упакованного формата:

Здесь и далее: Цф - цифра,Знак - знак числа.

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

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

Структура поля распакованного формата:

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

Пример 4.10. Число-193₍₁₀₎=-000110010011_(2-10) в ПК будет представлено:

в упакованном формате

в распакованном формате

КОДЫ ASCII

Распакованный формат представления двоично-десятичных чисел (иногда его называют "зонный") является следствием использования в ПК ASCII-кода для представления символьной информации.

Код ASCII (American Standard Code for Information Interchange - Американский стандартный код для обмена информацией) имеет основной стандарт и его расширение (табл. 4.3).Основной стандарт для кодирования символовиспользует шестнадцатеричные коды 00-7F,расширение стандарта - 80 -FF. Основной стандарт является международным и используется для кодирования управляющих символов, цифр и буквлатинского алфавита; в расширении стандарта кодируются символы псевдографики и буквынационального алфавита (естественно, в разных странах разные).

Таблица 4.3. Таблица кодов ASCII

ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ПК

Основы алгебры логики

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

Алгебра логики - это раздел математической логики, значениявсех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.

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

Пример 4.11. Высказывания: "Сейчас идет снег"- это утверждение может быть истинным или ложным; "Вашингтон столица США" истинное утверждение; "Частное от деления 10 на 2 равно 3" -ложное утверждение.

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

Простейшими операциями в алгебре логики являются операции логического сложения (иначе, операция ИЛИ, операция дизъюнкции) и логического умножения (иначе, операция И, операция конъюнкции). Для обозначения операции логического сложения используют символы + или V, а логического умножения - символы * или L .

Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий.

В частности, для алгебры логики выполняются законы:

1) сочетательный:

(a + b) + с = а + ( b + с);

(а * b) * с = а * (b * с);

2) переместительный:

а + b = b + а;

а * b = b * а;

3) распределительный:

а* (b + с) = a * b + а* с;

а+ b * с= а * b + а* с.

Справедливы соотношения:

a+a=a; a+b=b, если а≤b;

a*a=a; a*b=a,если a≤b;

a+a*b=a; a+b=b,если a≥b

a+b=a, если а≥b; и др.

Наименьшим элементом алгебры логики является 0, наибольшим элементом-1.

В алгебре логики также вводится еще одна операция- операция отрицания (иначе, операция НЕ, операция инверсии), обозначаемая чертой над элементом.

По определению: a+ā=1,a* ā=0, 0=1, 1=0.

Справедливы, например, такие соотношения: а=а, a+b=а*b, a*b=а+b.

Функция в алгебре логики это алгебраическое выражение, содержащее элементы алгебры логики а, b, с ..., связанные между собой операциями, определенными в этой алгебре.

Пример 4.12. Примеры логическихфункций.

f(a,b,c) = ā + a*b*ń + a+c;

f(a,b,c) = a*b + а*с +a*b*c

Согласно теоремам разложения функций на конституэнты (составляющие) любая функция может быть разложена на конституэнты "1":

f(a)=f(1)*a+f(0)* ā;

f(a,b)=f(1,b)*a+f(0,b)*ā=f(1,1)*a*a+f(1,0)*a*b+f(0,1)*ā*b+f(0,0)*ā*b, (2)

и т.д.

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

Логический синтез вычислительных схем

Рассмотрим логический синтез (создание) вычислительных схем на примере одноразрядного двоичного сумматора, имеющего два входа ("а" и "b") и два выхода ("S" и "Р") и выполняющего операцию сложения в соответствии с заданной таблицей:

где f₁(a,b)=S - значение цифры суммы в данном разряде;

f₂(a,b)=P - цифра переноса в следующий (старший) разряд.

Согласно соотношению (2), можно записать:

S=f₁(a,b)=0*a*b+ 1* ā *b+ 1*a*b +0* ā *b= ā *b+ ą*b;

Р =f₂(a,b) = 1 *a*b + 0* ā *b + 0*a*b + 0* ā* b = a*b.

Логическая схема сумматора, реализующего полученную функцию, представлена на рис. 4.1.

Здесь изображены логические блоки в соответствии с международным стандартом:

схема ИЛИ, реализующая операцию логического сложения

схема И, реализующая операцию логического умножения

схема НЕ, реализующая операцию инверсии

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

2. Для логических схем ИЛИ, И и НЕ существуют типовые технические схемы, реализующие их на реле, электронных лампах, дискретных полупроводниковых элементах. Для построения современных ЭВМ обычно применяются системы интегральных элементов, у которых с целью большей унификации в качестве базовой логической схемы используется всего одна из схем: И НЕ (штрих Шеффера), ИЛИ НЕ (стрелка Пирса) или И ИЛИ НЕ.

ПРОГРАММНОЕ УПРАВЛЕНИЕ ЭВМ

Структура и виды команд

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

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

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

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

Машинная команда состоит из двух частей: операционной и адресной.

Операционная часть команды это группа разрядов в команде, предназначенная для представления кода операции машины.

Адресная часть команды это группа разрядов в команде, в которых записываются коды адреса (адресов) ячеек памяти машины, предназначенных для оперативного хранения информации, или иных объектов, задействованных при выполнении команды. Часто эти адреса называются адресами операндов, т.е. чисел, участвующих в операции.

По количеству адресов, записываемых в команде, команды делятсяна безадресные, одно-, двух- и трехадресные.

Типовая структура трехадресной команды:

где КОП -код операции;

а1 и а2 - адреса ячеек (регистров), где расположены соответственно первое и второе числа, участвующие в операции;

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

Типовая структура двухадресной команды:

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

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

Типовая структура одноадресной команды:

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

Безадресная команда содержит только код операции, а информация для нее должна быть заранее помещена в определенные регистры машины (безадресные команды могут использоваться только совместно с командами другой адресности).

Пример 4.13. Поступила представленная на языке символического кодирования команда:

Такую команду следует расшифровать так: "сложить число, записанное в ячейке 0103 памяти, с числом, записанным в ячейке 5102, а затем результат (т.е. сумму) поместить в ячейку 0103".

Примечание. В кодах машины такая команда содержит только двоичные цифры записанных выше объектов.

Состав машинных команд

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

• операции пересылки информации внутри ЭВМ;
• арифметические операции над информацией;
• логические операции над информацией;
• операции обращения к внешним устройствам ЭВМ;
• операции передачи управления;
• обслуживающие и вспомогательные операции.

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

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

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