Элементы теории кодирования данных

1.3.1 Язык и алфавит

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

Термин «язык» является достаточно общим понятием. Для человека язык является естественным средством общения и в то же время средством кодирования информации, т.к. языки отдельных областей знаний и сфер деятельности часто являются специализированными. В информатике язык, прежде всего, – это средство информационного моделирования, система знаков, совокупность символов, соглашений и правил, используемых для отображения и передачи информации, а также средство описания данных и алгоритмов решения задач. К универсальным понятиям, характеризующим язык, относят: алфавит, синтаксис и семантика.

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

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

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

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

Для машинной кодировки безусловный приоритет имеет двоичная система счисления, имеющая всего две цифры – 0 и 1. Перед другими системами кодирования двоичная система имеет ряд преимуществ:

· для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток – нет тока, намагничен – не намагничен и т.п.)

· представление информации посредством только двух состояний надежно и помехоустойчиво;

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

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

1.3.2 Системы счисления

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

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

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

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

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

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

где – цифры системы счисления; n и m – число целых и дробных разрядов, соответственно.

Например:

757,7₁₀=7·10²+5·10¹+7·10⁰+7·10^-1;

1001₂=1·2³+0·2²+0·2¹+1·2⁰=9₁₀.

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

Таблица 1.1 Запись натуральных чисел от 0 до 17 в различных системах счисления q

q =10

q =2

q =8

q =16

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

Пример 1.2. Перевод числа 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:

т.е. 75₁₀= 1 001 011₂ = 113₈ = 4B₁₆.

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

Пример 1.3. Перевод числа 0,35 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:

0,35	0,35	0,35

0,7	2,80	5,60

1,4	6,40	9,60

0,8	3,20	9,60

1,6	1,60

1,2

т.е. 0,35₁₀ = 0,01011₂ = 0,263₈ = 0,59₁₆.

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

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

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

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

1.3.3 Представление в компьютере целых чисел

Используя двоичную систему счисления компьютер в одном байте может хранить любое число в диапазоне от 0 до 255 (от 00000000 до 11111111), а в двух байтах от 0 до 65535.

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

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

Таблица 1.2 – Двоичное представление чисел в трехразрядном дополнительном коде

Десятичное число					-1	-2	-3	-4
Двоичное представление

Фактически получается, что в данной таблице отсутствует битовая комбинация, представляющая, например, число 4. Это означает, что на машине с хранением чисел в трехразрядном дополнительном коде будет невозможно получить решение задачи «два плюс два».

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

Естественно, реальные машины работают с более длинными битовыми комбинациями, чем в рассмотренном примере. В частности, 32 бита позволяют обрабатывать числа до 1 147 483 647. Если же требуется обработка чисел, превышающих это значение, используются более длинные битовые комбинации или изменяются единицы измерения (1000 мм = 1 м, 1000 байт = 1 кбайт и т.д.). Поэтому ошибки переполнения при правильном использовании программных средств возникают достаточно редко.

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

Таблица 1.3 – Двоичное представление чисел в трехразрядной нотации с избытком

Десятичное число					-1	-2	-3	-4
Двоичное представление

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

1) в большинстве компьютеров операции вычитания нет, вместо нее производится операция сложения;

2) во многих компьютерах умножение производится как последовательность сложений и сдвигов.

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

Другой регистр процессора, участвующий в выполнении этой операции, вначале содержит множитель. Затем по мере выполнения сложений содержащееся в нем число уменьшается, пока не достигнет нулевого значения. Для иллюстрации умножим 110011₂ на 101101₂ (рисунок 1.15).

Накапливающий сумматор	Множитель
+

+
		Сдвиг на две позиции влево
+
		Сдвиг на одну позицию влево
+
		Сдвиг на две позиции влево

Рисунок 1.15 – Иллюстрация процесса умножения двоичных чисел

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

1.3.4 Представление в компьютере дробных чисел

Числа, имеющие дробную часть, в информатике также называют вещественными. В большинстве программных систем при их написании вместо запятой принято писать точку. Так, например, число 5 – целое, а числа 5.1 и 5.0 – вещественные.

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