Представление (кодирование) данных

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

Подготовка данных для обработки на компьютере (представление данных) в информатике имеет свою специфику, связанную с электроникой. Рассмотрим ее. Например, мы хотим проводить расчеты на компьютере. При этом нам придется закодировать цифры, которыми записаны числа. На первый взгляд, представляется вполне естественным кодировать цифру ноль состоянием электронной схемы, где напряжение на некотором элементе будет равно 0 вольт, цифру единица – 1 вольт, двойку – 2 вольт, и т.д. девятку – 9 вольт. Для записи каждого разряда числа в этом случае потребуется элемент электронной схемы, имеющий десять состояний. Однако, элементная база электронных схем имеет разброс параметров, что может привести к появлению напряжения, скажем, 3,5 вольт, а оно может быть истолковано и как тройка и как четверка, т.е. потребуется на уровне электронных схем объяснить компьютеру, где заканчивается тройка, а где начинается четверка. Кроме того, придется создавать весьма непростые электронные элементы для производства арифметических операций с числами, т.е. на схемном уровне должны быть созданы таблица умножения - 10х10=100 схем и таблица сложения – тоже 100 схем. Для электроники сороковых годов (время, когда появились первые вычислительные машины) это была непосильная задача. Еще сложнее выглядела бы задача обработки текстов, ведь русский алфавит содержит 33 буквы. Очевидно, такой путь построения вычислительных систем не состоятелен.

В то же время, весьма просто реализовались электронные схемы с двумя устойчивыми состояниями: есть ток – 1, нет тока – 0, есть электрическое (магнитное) поле – 1, нет – 0. Взгляды создателей вычислительной техники были обращены на двоичное кодирование, как универсальную форму представления данных для дальнейшей обработки их средствами вычислительной техники. Предполагается, что данные располагаются в некоторых ячейках, представляющих упорядоченную совокупность из двоичных разрядов, а каждый может временно содержать одно из состояний – 0 или 1. Тогда группа из двух двоичных разрядов (двух бит) может закодировать 2²= 4 различных комбинации кодов (00 01 10 11); аналогично, три бита дадут 2³= 8 комбинаций, восемь бит или 1 байт - 2⁸= 256 и т.д.

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

1.3.1. Представление чисел в двоичном коде

Существуют различные способы записи чисел,

Например:

- можно записать число в виде текста - сто двадцать три;

- римской системе счисления CXXIII;

- в арабской 123.

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

Совокупность приемов записи и наименования чисел называется системой счисления.

Числа записываются с помощью символов, и по количеству символов, используемых для записи числа, системы счисления подразделяются на позиционные и непозиционные. Если для записи числа используется бесконечное множество символов, то система счисления называется непозиционной. Примером непозиционной системы счисления может служить римская. Например, для записи числа один используется буква I, два и три выглядят как совокупности символов II, III, но для записи числа пять выбирается новый символ V, шесть – VI , десять - вводится символ X, сто – C, тысяча – M, и так далее. Бесконечный ряд чисел потребует бесконечного числа символов для записи чисел. Кроме того, такой способ записи чисел приводит к очень сложным правилам арифметики.

Позиционные системы счисления для записи чисел используют ограниченный набор символов, называемых цифрами, и величина числа зависит не только от набора цифр, но и от того, в какой последовательности записаны цифры, т.е. от позиции, занимаемой цифрой, например, 125 и 215. Количество цифр, используемых для записи числа, называется основанием системы счисления, в дальнейшем обозначим q.

В повседневной жизни мы пользуемся десятичной позиционной системой счисления, q=10, т.е. используется 10 цифр: 0 1 2 3 4 5 6 7 8 9.

Рассмотрим правила записи чисел в позиционной десятичной системе счисления. Числа от 0 до 9 записываются цифрами, для записи следующего числа цифры не существует, поэтому вместо 9 пишут 0, но левее нуля образуется еще один разряд, называемый старшим, где записывается (прибавляется) 1, в результате получается 10. Затем пойдут числа 11, 12, но на 19 опять младший разряд заполнится и мы его снова заменим на 0, а старший разряд увеличим на 1, получим 20. Далее по аналогии 30, 40 … 90 91 92… до 99. Здесь заполненными оказываются два разряда сразу, чтобы получить следующее число, мы заменяем оба на 0, а в старшем разряде, теперь уже третьем, поставим 1, т.е. 100, и т.д. до бесконечности, причем заметим, что при конечном числе цифр можно записать любое сколь угодно большое число. Заметим также, что производство арифметических действий в десятичной системе счисления весьма просто.

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

123,45= 1*10²+2*10¹+3*10⁰+4*10^-1+5*10^-2

или в общем виде это правило запишется так

X_(q)=x_n-1q^n-1+x_n-2q^n-2+…+x₁q¹+x₀q⁰+x_-1q^-1+x_-2q^-2+…+x_-mq^-m

Здесь X_(q) – запись числа в системе счисления с основанием q;

x_i – натуральные числа меньше q, т.е. цифры;

n – число разрядов целой части;

m – число разрядов дробной части.

Записывая слева направо цифры числа, мы получим закодированную запись числа в q-ичной системе счисления:

X_(q)=x_n-1x_n-2x₁x_{0 ,} x_-1x_-2x_-m

В информатике, вследствие применения электронных средств вычислительной техники, большое значение имеет двоичная система счисления, q=2 . На ранних этапах развития вычислительной техники арифметические операции с действительными числами производились в двоичной системе ввиду простоты их реализации в электронных схемах вычислительных машин. Например, таблица сложения и таблица умножения будут иметь по четыре правила,

0+0=0	0х0=0
0+1=1	0х1=0
1+0=1	1х0=0
1+1=10	1х1=1

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

Но запись числа в двоичной системе счисления длиннее записи того же числа в десятичной системе счисления в log₂10 раз (примерно в 3.3 раза). Это громоздко и не удобно для профессионального и для повседневного использования, так как нормальный объем человеческого внимания составляет примерно три – четыре объекта, т.е. удобно будет пользоваться такими системами счисления, в которых наиболее часто используемые числа (от единиц до тысяч) записывались бы одной – четырьмя цифрами. Как это будет показано ниже, перевод числа, записанного в двоичной системе счисления в восьмеричную и шестнадцатеричную очень сильно упрощается по сравнению с переводом из десятичной в двоичную. Запись же чисел в них в три раза короче для восьмеричной и в четыре для шестнадцатеричной системы, чем в двоичной, но длины чисел в десятичной, восьмеричной и шестнадцатеричной системах счисления будут различаться не намного. Поэтому, наряду с двоичной системой счисления, в информатике имеют хождение восьмеричная и шестнадцатеричная системы счисления.

Восьмеричная система счисления имеет восемь цифр: 0 1 2 3 4 5 6 7. Шестнадцатеричная - шестнадцать, причем первые 10 цифр совпадают по написанию с цифрами десятичной системы счисления, а для обозначения оставшихся шести цифр применяются большие латинские буквы, т.е. для шестнадцатеричной системы счисления получим набор цифр: 0 1 2 3 4 5 6 7 8 9 A B C D E F.

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

231₍₁₀₎=11100111₍₂₎=347₍₈₎=E7₍₁₆₎

Запишем начало натурального ряда в десятичной, двоичной, восьмеричной и шестнадцатеричной системах счисления.

десятичная	двоичная	восьмеричная	шестнадцатеричная
			A
			B
			C
			D
			E
			F

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

Так как десятичная система для нас удобна и привычна, все арифметические действия мы делаем в ней, то преобразование чисел из произвольной недесятичной (q ¹10) системы в десятичную удобно выполнять на основе разложения по степеням q, например:

11100111₍₂₎= 1´2⁷+1´2⁶+1´2⁵+0´2⁴+0´2³+1´2²+1´2¹+1´2⁰=128+64+32+4+2+1=231_(10),

или 347₍₈₎= 3´8²+4´8¹+7´8⁰=3´64+4´8+7=231₍₁₀₎

Преобразование из десятичной в прочие системы счисления проводится с помощью правил умножения-деления. При этом целая и дробная части переводятся отдельно.

Рассмотрим алгоритм на примере перевода десятичного числа 231 в двоичную систему, совершенно аналогичен перевод из десятичной системы в любую q-ичную. Разделим число на два (основание системы) нацело 231¸2=115 и остаток 1, т.е. можно записать

231=115´2¹+1´2⁰.

Число 115 (такой двоичной цифры нет) тоже может быть разделено нацело на 2, т.е. 115¸2=57 и остаток 1. По аналогии запишем

231=(57´2+1)´2+1= 57´2²+1´1¹+1´2⁰

аналогично продолжим процесс дальше

57¸2=28 остаток 1; 231=((28´2+1)´2+1)´2+1= 28´2³+1´2²+1´2¹+1´2⁰

28¸2=14 остаток 0; 231=(((14´2+0)´2+1)´2+1)´2+1=14´2⁴+1´2²+1´2¹+1´2⁰

14¸2=7 остаток 0; 231=((((7´2+0)´2+0)´2+1)´2+1)´2+1=7´2⁵+1´2²+1´2¹+1´2⁰

7¸2=3 остаток 1; 231=(((((3´2+1)´2+0)´2+0)´2+1)´2+1)´2+1=3´2⁶+1´2⁵+1´2²+1´2¹+1´2⁰

3¸2=1; остаток 1; далее процесс продолжать нельзя т.к. 1 не делится нацело на 2

231=((((((1´2+1)´2+1)´2+0)´2+0)´2+1)´2+1)´2+1=1´2⁷+1´2⁶+1´2⁵+1´2²+1´2¹+1´2⁰

Таким образом, последовательное деление нацело позволяет разложить число по степеням двойки, а это в краткой записи и есть двоичное изображение числа.

231 =1´2⁷+1´2⁶+1´2⁵+0´2⁴+0´2³ +1´2²+1´2¹+1´2⁰ = 11100111₍₂₎

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

_231|_2_

230| 115|_2_

1 114| 57|_2_

1 56| 28|_2_

1 28| 14|_2_ 231₍₁₀₎=11100111₍₂₎

0 14| 7 |_2_

0 6 | 3 |_2_

1 2| 1

1

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

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

Умножим его на 2, т.е. 0.8125´2=1.625 или 0.8125=(1+0.625)´2^-1=1´2^-1+0.625´2^-1

Аналогично 0.625=(1+0.25)´2^-1 или

0.8125=1´2^-1+(1+0.25)´2^-1 ´2^-1=1´2^-1+1´2^-2+0,25´2^-2 , но 0.25=0.5´2^-1

0.8125=1´2^-1+(1+0.5´2^-1)´2^-1 ´2^-1=1´2^-1+1´2^-2+0,5´2^-3 , но 0.5=1´2^-1

0.8125=1´2^-1+1´2^-2+1´2^-1´2^-3 =1´2^-1+1´2^-2+1´2^-4 .

В итоге получаем, что 0.8125₍₁₀₎ =1´2^-1+1´2^-2+1´2^-4=0.1101₍₂₎. Сокращая выкладки, получим правило (алгоритм) последовательного умножения.

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

Если ведутся приближенные вычисления, то последний разряд является сомнительным, и для обеспечения в приближенных вычислениях одинаковой точности в двоичной и десятичной записях числа без бесконечных дробей, достаточно взять число двоичных разрядов в (log₂10»3.3) 4 раза больше, чем десятичных .

Между двоичной системой счисления с одной стороны и восьмеричной и шестнадцатеричной (заметим 8 и 16 – есть третья и четвертая степени двойки) с другой стороны, существует связь, позволяющая легко переводить числа из одной системы в другую. Рассмотрим на примере:

231.8125₍₁₀₎=11100111.1101₍₂₎= 1´2⁷+1´2⁶+1´2⁵+1´2²+1´2¹+1´2⁰+1´2^-1+1´2^-2+1´2^-4 .

Для перевода в шестнадцатеричную систему счисления сгруппируем целую и дробную части в группы по четыре члена и вынесем в каждой группе за скобки множители кратные 2⁴ , получим:

(1´2³+1´2²+1´2¹+0´2⁰)´2⁴+(1´2³+1´2²+1´2¹+1´2⁰)+(1´2³+1´2²+0´2¹ +1´2⁰) ´2^-4= =(1´2³+1´2²+1´2¹+0)´16¹+(1´2²+1´2¹+1´2⁰)´16⁰+(1´2³+1´2²+0´2¹ +1´2⁰) ´16^-1= =14´16¹+7´16⁰+13´16^-1 =E7.D₍₁₆₎

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

Аналогичное правило для восьмеричной системы читатель выведет сам.