1.4. Кодирование информации

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

История кодирования очень обширна. В быту используются такие системы кодиров- ки, например, как код Морзе , Брайля , код морских сигналов и т. п. В вычислительной тех-

нике система кодирования называется двоичным кодированием и основана на представление данных в двоичной системе. Такое представление наиболее просто реализовать в электрон- ных схемах с двумя устойчивыми состояниями: есть ток – 1, нет тока – 0. Таким образом, ис- пользуются два знака 0 и 1. Эти знаки называются двоичными цифрами (binary digit или со- кращенно bit). Двумя битами можно закодировать четыре различных комбинации 00, 01, 10 и 11, три бита дадут восемь комбинаций 000, 001, 010, 011, 100, 101, 110, 111 и т. д. Общая

формула имеет вид	N = 2m ,	(1.4.1)
где N - количество независимых кодируемых значений,		m - разрядность кодирования, при-
нятая в данной системе.

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

Непозиционные системы для записи числа используют бесконечное множество сим- волов, и значение символа не зависит от того места, которое он занимает в числе. Примером непозиционной системы может служить римская система счисления. Например, числа один, два и три кодируются буквой I: I, II, III. Для записи числа пять выбирается новый символ V, для десяти – Х и т. д. Кроме сложной записи самих чисел такая форма их представления при- водит к очень сложным правилам арифметики.

Число в позиционной системе счисления с основанием q может быть представлено в

виде многочлена по степеням q следующим образом
X = x	n−1	qn−1 + x	n−2	qn−2 + ... + x q1	+ x q0 + x	−1	q−1	+ ... + x	−m	q−m ,	(1.4.2)
				1	0
где X - запись числа в системе счисления с основанием q ,								xi - цифра в i -ом разряде, n -
число разрядов целой части, m - число разрядов дробной части.

Записывая слева направо числа, получим закодированную запись числа в q -ичной системе счисления X = xn−1xn−2...x1x0 x−1...x−m . В двоичной системе счисления все арифмети-

ческие действия выполняются весьма просто, например таблица сложения и умножения бу- дет иметь восемь правил (см. табл. 1.1). Однако запись числа в двоичной системе счисления длиннее записи того же числа в десятичной системе счисления в log2 10 раз (примерно в 3.3

раза). Это громоздко и неудобно для использования.

Наряду с двоичной системой в информатике применяются восьмеричная и шестнадца- теричная системы счисления. Восьмеричная система счисления имеет восемь цифр: 0, 1, 2, 3,

Сэмюэль Финли Бриз Морзе (1791 – 1872) - американский художник и изобретатель. В 1838 г. Морзе разрабо- тал специальный код (азбуку Морзе) и послал первое телеграфное сообщение.

Луи Брайль (1809 – 1852) - французский тифлопедагог.

4, 5, 6, 7, 8, шестнадцатеричная – шестнадцать – 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Таблица 1.1

0+0=0	0×0=0
0+1=1	0×1=0
1+0=1	1×0=0
1+1=0	1×1=1

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

зом: 13710 =100010012 = 2118 = 8916 .

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

Таблица 1.2

			Сложение									Умножение
+	0	1	2	3	4	5	6	7	×	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7	0	0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7	10	1	0	1	2	3	4	5	6	7
2	2	3	4	5	6	7	10	11	2	0	2	4	6	10	12	14	16
3	3	4	5	6	7	10	11	12	3	0	3	6	11	14	17	22	25
4	4	5	6	7	10	11	12	13	4	0	4	10	14	20	24	30	34
5	5	6	7	10	11	12	13	14	5	0	5	12	17	24	31	36	43
6	6	7	10	11	12	13	14	15	6	0	6	14	22	30	36	44	52
7	7	10	11	12	13	14	15	16	7	0	7	16	25	34	43	52	61

1.4.2. Преобразование чисел из одной системы счисления в другую. Преобразова-

ние из десятичной в прочие системы счисления производится с помощью правил умножения и деления. При этом целая и дробная части переводятся отдельно. Рассмотрим алгоритм пе- ревода на примере целого числа 137 в двоичную систему. Разделим его нацело на 2, получим 137 : 2 = 68 , остаток 1. Полученный результат можно записать следующим образом:

137 = 68× 21 +1× 20 . Продолжим операцию деления дальше

68 : 2 = 34, остаток 0, 137 = (34 × 2 + 0)× 21 +1× 20 = 34× 22 + 0 × 21 +1× 20 ; 34 : 2 = 17 , остаток 0, 137 = (17× 2 + 0)× 22 + 0× 21 +1× 20 =17× 23 + 0× 22 + 0× 21 +1× 20 ; 17 : 2 = 8, остаток 1, 137 = (8× 2 +1)× 23 + 0× 22 + 0× 21 +1× 20 = 8× 24 +1× 23 + + 0× 22 + 0× 21 +1× 20 ;

8: 2 = 4 , остаток 0, 137 = (4 × 2 + 0)× 24 + 1× 23 + 0× 22 + 0× 21 + 1× 20 = 4× 25 + + 0× 24 +1× 23 + 0 × 22 + 0 × 21 +1× 20 ; 4 : 2 = 2 , остаток 0, 137 = (2× 2 + 0)× 25 + 0× 24 +1× 23 + 0× 22 + 0× 21 +1× 20 =

= 2× 26 + 0× 25 + 0× 24 +1× 23 + 0× 22 + 0× 21 +1× 20 ; 2 : 2 = 1, остаток 0, 137 = (1× 2 + 0)× 26 + 0× 25 + 0× 24 +1× 23 + 0× 22 + 0× 21 +

+1× 20 = 1× 27 + 0 × 26 + 0 × 25 + 0 × 24 + 1× 23 + 0× 22 + 0× 21 + 1× 20 .

Далее процесс продолжать нельзя, т. к. 0 не делится нацело на 2. Таким образом, последова- тельное деление нацело на 2 позволяет разложить число по степеням двойки, а это в краткой записи и есть двоичное изображение числа: 13710 =100010012 . Все приведенные выкладки

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

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

систем счисления все описанные действия выполняются аналогичным способом. Например, это же число 137 в

восьмеричную и шестнадцатеричную систему счисления переводится по похожим схемам.

	137		8					137			16
	136			17		8
								128			8
	1			16		2
								9
			1

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

ления. Умножим 0.2 на 2, т. е. 0.2× 2 = 0.4 или 0.2 = (0 + 0.4)× 2−1 = 0× 2−1 + 0.4× 2−1 . 0.4× 2 = 0.8, 0.2 = 0× 2−1 + (0 + 0.8)× 2−1 × 2−1 = 0× 2−1 + 0× 2−2 + 0.8× 2−2 ;

0.8× 2 =1.6 , 0.2 = 0× 2−1 + 0 × 2−2 + (1+ 0.6)× 2−3 = 0 × 2−1 + 0 × 2−2 + 1× 2−3 + 0.6 × 2−3 ; 0.6 × 2 = 1.2 , 0.2 = 0× 2−1 + 0× 2−2 +1× 2−3 + (1+ 0.2)× 2−4 = 0× 2−1 + 0× 2−2 +1× 2−3 +

+1× 2−4 + 0.2× 2−4 ; 0.2 × 2 = 0.4, 0.2 = 0 × 2−1 + 0 × 2−2 + 1× 2−3 + 1× 2−4 + (0 + 0.4)× 2−5 = 0 × 2−1 +

+ 0 × 2−2 +1× 2−3 +1× 2−4 + 0× 2−5 + 0.4 × 2−5 ,

т. е. 0210 = 0.00110011...2 . Все вышеприведенные выкладки можно свести в следующую таб- лицу 1.3.

	Таблица 1.3
0	0.2
	2
0	0.4
	2
1	0.8
	2
1	0.6
	2
0	0.2
	2
…	…

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

двоек и пятерок, т. е. дробь имеет вид k(2m5n ). Аналогично в двоичной системе счисления

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

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

137.210 = 10001001.00110011...2 = 1× 27 +1× 23 +1× 20 +1× 2−3 + 1× 2−4 +1× 2−7 + 1× 2−8 + ... = ≈137.1992...10 .

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

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

1.4.3. Представление целых и действительных чисел в двоичном коде. Совокуп-

ность двоичных разрядов данных в ЭВМ образуют некий битовый рисунок. Группа из вось- ми взаимосвязанных битов называется байтом. Байт – это минимальная по размеру адресуе- мая часть памяти компьютера.

Существует несколько типов чисел. Числа могут быть положительные и отрицатель- ные, целые точные, дробные точные, рациональные, иррациональные, дробные приближен- ные. Оптимального представления в памяти ЭВМ для всех типов чисел создать невозможно, поэтому для каждого в отдельности типа создается собственный способ представления.

Целые положительные числа от 0 до 255 можно представить непосредственно в двоич- ной системе счисления, при этом они будут занимать один байт в памяти компьютера (см.

табл. 1.4).

	Таблица 1.4
Число	Двоичный код
0	0000 0000
1	0000 0001
2	0000 0010
3	0000 0011
…	…
255	1111 1111

Знак отрицательного числа кодируется обычно старшим битом, нуль интерпретируется как плюс, единица как минус. Поскольку один бит будет занят, то одним байтом могут быть закодированы целые числа в интервале от –127 до +127. Такой способ представления целых чисел называется прямым кодом. Существует способ кодирования отрицательных целых чи- сел в обратном коде. В этом случае положительные числа совпадают с положительными числами в прямом коде, а отрицательные получаются в результате вычитания из двоичного числа 1 0000 0000 соответствующего положительного числа, например, число –7 получит код 1111 1000. Целые числа больших диапазонов представляются в двухбайтовых и четы- рехбайтовых ячейках памяти.

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

вающей точкой:

X = m×q p ,

(1.4.3)

где m - мантисса числа, q - основание системы счисления, p - целое число, называемое по- рядком. При этом для десятичной системы счисления мантисса выбирается в диапазоне 1q £ m < q , т. е. 0.1£ m <1. Такая форма представления называется нормализованной.

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

Чем больше разрядов отводится под запись мантиссы, тем выше точность представ- ления числа. Чем больше разрядов занимает порядок, тем шире диапазон представления чи- сел в компьютере при заданном формате.