Лекция 2. Представление (кодирование) данных

Лекция 2. Представление (кодирование) данных

План лекции:

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

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

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

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

5. Представление символьных и текстовых данных

6. Представление звуковых данных в двоичном коде

7. Представление графический данных в двоичном коде

8. Понятие сжатия информации

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

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

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

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

Существуют различные способы записи чисел, например: мож­но записать число в виде текста – сто двадцать три; римской систе­ме счисления СХХШ; арабской — 123.

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

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

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

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

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

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

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

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

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

0 + 0 = 0	0 x 0 = 0
0 + 1 = 1	0 x 1 = 0
1 + 0 = 1	1 x 0 = 0
1 + 1 = 10	1 x 1 = 1

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

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

Восьмеричная система счисления имеет восемь цифр: 0 12 3 4 5 6 7. Шестнадцатеричная – шестнадцать, причем первые 10 цифр совпадают по написанию с цифрами десятичной системы счисления, а для обозначения оставшихся шести цифр применяются большие латинские буквы, т.е. для шестнадцатеричной системы счисления получим набор цифр: 0123456789ABCDEF.

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

231₍₁₀₎=11100111₍₂₎=347₍₈₎=Е7₍₁₆₎.

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

Десятич­ная	Двоичная	Восьме­рич­ная	Шестнад­цате­ричная
			А
			В
			С
			D
			Е
			F

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

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

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

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

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

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

231 \2

¹ Ц4 \57 [2 '56

231_(|0)=11100111₍₂₎

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

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

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

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

Понятие сжатия информации

Еще одна проблема, тесно связанная с моделями представления информации — сжатие информации.

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

Разработаны и применяются два типа алгоритмов сжатия: сжатие с изменением структуры данных (оно происходит без потери данных) и сжатие с частичной потерей данных. Алгоритмы первого типа пре­дусматривают две операции: сжатие информации для хранения, пе­редачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмена и Лемпеля-Зива). Алгоритмы второго типа не позволяют полностью вос­становить оригинал и применяются для хранения графики или зву­ка; для текстов, чисел или программ они неприменимы.

Лекция 2. Представление (кодирование) данных

План лекции:

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

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

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

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

5. Представление символьных и текстовых данных

6. Представление звуковых данных в двоичном коде

7. Представление графический данных в двоичном коде

8. Понятие сжатия информации