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

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

Существуют позиционные и непозиционные системы счисления.

В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.

В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая - 7 единиц, а третья - 7 десятых долей единицы.

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

При переводе чисел из десятичной системы счисления в систему с основанием P > 1 обычно используют следующий алгоритм:

1. если переводится целая часть числа, то она делится на P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению;
2. если переводится дробная часть числа, то она умножается на P, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P.

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

1. Для её реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток - нет тока, намагничен - не намагничен и т.п.), а не с десятью, - как в десятичной;
2. Представление информации посредством только двух состояний надёжно и помехоустойчиво;
3. Возможно применение аппарата булевой алгебры для выполнения логических преобразований информации;
4. Двоичная арифметика намного проще десятичной.
5. Недостаток двоичной системы - запись числа будет, как правило, длиннее, чем в десятичной.

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

Задача перевода из одной системы счисления в другую часто встречается при программировании и особенно часто - при программировании на языке Ассемблера.

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

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

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

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

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

В ЭВМ применяются две формы представления чисел: с фиксированной (ффт) и плавающей (фпт) точкой. В случае ффт положение точки фиксируется в определенном месте относительно разрядов числа, как правило, перед старшим или после младшего; в первом случае представляются числа |N| <1, во втором - только целые числа.

По традиции нумерация бинарных разрядов (битов) в ЭВМ общего назначения ведется слева направо. Знаковый разряд является, как правило, крайним слева. В случае использования прямого кода диапазон представления чисел составляет 1<=|N|<= 2 ^(n-1)-1; дополнительный код позволяет использовать числа в диапазоне -2^n-1<= N<=2^(n-1) -1, что при n=32 примерно соответствует диапазону десятичных целых чисел 1<=N<= 10⁹. Для других рассмотренных кодов установление диапазонов представимости чисел оставляем читателю. В настоящее время форма фиксации точки перед старшим разрядом используется для представления целых чисел с фиксацией точки после младшего разряда. Если точка фиксируется справа от младшего разряда, то регистром целых чисел со знаком можно представлять нуль, положительные и отрицательные целые бинарные числа. В зависимости от модели ЭВМ используются два формата ффт представления целых чисел: со знаком и без; в последнем случае все разряды регистра служат для представления модуля числа. Форматы чисел с ффт используются в качестве основных только в ограниченных по возможностям ЭВМ, ориентированных на работу в системах передачи данных, управлении технологическими процессами и работы в режиме реального времени. Остальные типы ЭВМ используют эти форматы, главным образом, для работы с целыми числами.

В ЭВМ общего (универсального) назначения основной является форма представления чисел с плавающей точкой (фпт), не требующая масштабирования данных. Но и в таких ЭВМ часто используется рассмотренная выше ффт, ибо операции с целыми числами в таких форматах выполняются быстрее; сюда же относятся и операции индексной арифметики над кодами адресов (обеспечение адресации). В общем случае представление N-числа в фпт имеет следующий вид: N=A^pM, где M - мантисса; А - основание характеристики и р - ее порядок. Как правило, величина Ар представляет целую степень двух. Мантисса (М; является дробью со знаком) и порядок (р; целое со знаком) представляются в А-с. с. в соответствующей бинарно-кодированной форме. Знак N-числа совпадает со знаком М-мантиссы; р-порядок определяет положение точки в представлении N-числа.

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

Так как под мантиссу отводится фиксированное число битов, то для получения максимальной точности используются нормализованные числа, для которых выполняется условие А <=|М|<1. В некоторых ЭВМ используется другое условие нормализации - 1<=|М|<A, т.е. старший бит мантиссы в А-с. с. отличен от нуля. Если в процессе вычислений получается ненормализованное число, оно, как правило, автоматически нормализуется: если d старших битов мантиссы нулевые, то производится ее сдвиг на d битов влево (младшие биты обнуляются) с одновременным уменьшением порядка числа на d единиц (при нулевой мантиссе нормализации не производится). В различных ЭВМ используются фпт при А=2^m(m=1,3,4,...); при этом, р-порядок представляется целым числом, а М-мантисса - бинарным числом, состоящим из групп по m битов, изображающих цифры мантиссы в А-с. с. Наиболее распространенными являются основания A{2,8,16}. Использование небинарного А-основания несколько уменьшает точность вычислений, но позволяет увеличивать диапазон представимых чисел и скорость выполнения ряда операций, уменьшая вероятность появления ненормализованных чисел. Диапазон представимых чисел в фпт зависит от А-с. с. и числа битов, отведенных под р-порядок; тогда как точность вычислений определяется числом битов М-мантиссы. С увеличением разрядности мантиссы растет точность вычислений, но уменьшается скорость выполнения арифметических операций. Ввиду различных требований, предъявляемых к точности вычислений, многие ЭВМ используют несколько форматов для представления чисел в фпт (разные разрядности мантиссы). В первую очередь, это относится к сопроцессорам ПК и микро-ЭВМ. Такое архитектурное решение позволяет более гибко организовывать вычислительный ход.

Представление символьной информации

Кодирование символьной информации осуществляется на основе двоичных кодов, первоначально для нужд телеграфной связи. Этот двоичный код называется ASCII (American Standard Code for Information Interchange). Оба эти кода совпадают по первым 128 позициям. Это фактически есть неизменяемая часть любого кода для ЭВМ.

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

В настоящее время широко распространен BCD - Binary Coded Decimal - каждая десятичная цифра записывается четырехбитовым двоичным эквивалентом.

Представление логической информации

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

В АЛУ ЭВМ имеется набор элементарных логических устройств, соответствующих основным логическим операциям. На входы логических устройств подаются двоичные коды, которые рассматриваются как логические переменные, а выход зависит от таблицы истинности. Логическому значению "истина" соответствует 1, а значению "ложь" - 0.