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

Введение

Для использования в ЭВМ данные информации (как числовой, так и  не числовой) кодируются с помощью  чисел. Кодирование информации отражает фундаментальную необходимость  представления информации в определенной форме для обеспечения удобства ее восприятия, хранения или передачи по каналам связи. При этом информационный процесс можно рассматривать как последовательность этапов кодирования информации.  
Введение 
Используемые в ЭВМ данные имеют значение (величина - число 10, наименование команды - stop, знак операции - /, *, …) и форму представления, определяющую запись букв и чисел посредством предназначенных для этого знаков. Значение данных не зависит от формы их представления, то есть одно и то же значение данных может быть представлено в разных формах.  
 
В большинстве случаев, говоря о кодировании, имеют в виду преобразование дискретных форм представления информации. 
В настоящее время наиболее удобной формой представления данных в ЭВМ принят двоичный способ кодирования. Для представления значений элементарных данных в памяти компьютера используется машинное слово - данные, содержащиеся в одной ячейке памяти компьютера, которая является совокупностью двоичных элементов {0,1}, обрабатываемых как единое целое в устройствах и памяти компьютера. Длина машинного слова зависит от разрядности процессора и может быть равной 16, 32 битам и т.д. Машинное слово кратно целому числу байт (в современных 32-х разрядных машинах машинное слово составляет 4 байта).  
 

Кодирование числовой информации

Системы счисления. Способ представления чисел определяется используемой системой счисления. Знание систем счисления полезно для понимания представления данных в памяти ЭВМ и операций над ними.  
 
Для записи чисел в различных системах счисления используется некоторое количество отличающихся друг от друга знаков – цифр. Система счисления – это правило записи чисел с помощью заданного набора специальных знаков – цифр. 
 
Унарная система счисления использует для записи чисел только один знак – «1». Значение целого числа определяется наиболее простым способом - количеством (суммой) содержащихся в записи числа знаков «1». Например, 111 – три.  
Непозиционная система счисления характеризуется тем, что значение цифр числа не зависят от их положения в записи числа. Например, в римской системе записи цифры 1 - один, V - пять, 
X - десять, L - пятьдесят, C - сто, D - пятьсот, M - тысяча. Все другие числа строятся комбинацией этих базовых знаков в соответствии с установленными правилами.  
 
Например, запись IX- девять, XIX- девятнадцать, MDXLIX – число 1549. 
 
Недостатками непозиционной системы являются громоздкость записи чисел и сложность операций вычисления. 
Позиционные системы счисления характеризуются тем, что значение каждой цифры в записи числа определяется ее положением в ряду цифр этого числа. Число знаков (цифр) используемых в позиционной системе счисления названо основанием системы счисления.  
 
Достоинством позиционной системы счисления являются возможность записи посредством конечного набора цифр неограниченного количества различных чисел и достаточно простое выполнение арифметических операций. 
 
Ниже приведена таблица , содержащая наименования некоторых позиционных систем счисления и перечень знаков (цифр), из которых образуются в них числа. 
 

В позиционной системе  счисления число AnAn–1An–2 ... A1A0 , A–1A–2 ... может быть представлено в виде суммы произведений коэффициентов на степени основания системы счисления: 
AnAn–1An–2 ... A1A0,A–1A–2 ... = ?Aj*Bj = 
= An*Bn + An–1*Bn–1 + ... + A1*B1 + A0*B0 ,+ A–1*B–1 + A–2*B–2 + ...  
(знак «запятая» отделяет целую часть числа от дробной; знак «звездочка» здесь и ниже используется для обозначения операции умножения).  
Наибольшее распространение получила десятичная система счисления в которой основание системы счисления р=10 и для записи числа используются цифры 0,1, ..9. В приведенных ниже примерах индекс внизу указывает основание системы счисления: 
 
23,43(10) = 2*101 + 3*100 + 4*10–1 + 3*10–2  
 
В приведенном примере знак «3» в одном случае (до запятой) означает число единиц, а в другом – число сотых долей единицы;  
692(10) = 6*102 + 9*101 + 2. 
 
«Шестьсот девяносто два» с формальной точки зрения представляется в виде «шесть умножить на десять в степени два, плюс девять умножить на десять в степени один, плюс два». 
Далее приведены примеры записи чисел в других системах счисления 
1101(2) = 1*23 + 1*22 + 0*21 + 1*20; 
112(3) = 1*32 + 1*31 + 2*30; 
341,5(8) = 3*82 + 4*81 + 1*80 + 5*8–1; 
A1F,4(16) = A*162 + 1*161 + F*160 + 4*16–1. 
5(10) = 11111(1) = 101(2)=5(8)=5(16) 
 
Пример. Х=13(10). B=2.  
13(10)=(1*23=8(10))+5(10) = 1*23+1*22+1(10) =1*23+1*22+0*21+1(10) = 1*23+1*22+0*21+1*20= 10101(2) 
 
0,375(10) = (2*0,375(10) )*2-1 = (0+0,75)*2-1 = 0* 2-1 + (2*0,75)*2-2 = 0*2-1 + (1+0,5)*2-2 =0*2-1 + 1*2-2 +(2*0,5)*2-3 =0*2-1 + 1*2-2 +(1+0,0)*2-3=0,011(2) 
 
Итак, при переводе чисел из десятичной системы счисления в систему с основанием В > 1 обычно используют следующий алгоритм: 
1. если переводится целая часть числа, то она делится на В, после чего запоминается остаток от деления. Полученное частное вновь делится на В, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на В выписываются в порядке, обратном их получению;  
2. если переводится дробная часть числа, то она умножается на В, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на В и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю или меньше заданной величины. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием В.  
 
Пример 1. Перевести данное число из десятичной системы счисления в двоичную (получить пять знаков после запятой в двоичном представлении). 
а) 464(10); б) 380,1875(10); в) 115,94(10) 
 
Решение:

а) 464(10)=111010000(2); б) 380,1875(10) = 101111100,0011(2) ; в) 115,94(10) = 1110011,11110(2)  
(в данном случае было получено шесть знаков после запятой, после чего результат был округлен.) 
 
При переводе чисел из системы счисления с основанием B в десятичную систему счисления необходимо пронумеровать положительными числами разряды целой части, начиная с нулевого справа от запятой, и разряды дробной части отрицательными числами начиная с номера -1 сразу после запятой. Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления. 
 
Пример 2. Перевести данное число в десятичную систему счисления:  
а) 1000001(2). 
1000001(2) = 1 * 26 + 0 * 25 + 0 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 = 64 + 1 = 65(10). 
 
Хотя данные в компьютере представляются только в двоичной системе счисления, с целью уменьшения количества записываемых на бумаге или вводимых с клавиатуры компьютера знаков часто бывает удобнее пользоваться восьмеричными или шестнадцатеричными числами, тем более что процедура взаимного перевода чисел из каждой из этих систем в двоичную очень проста.  
Для перевода целого двоичного числа в восьмеричное необходимо разбить его справа налево на группы по 3 цифры - «двоичные триады» с дополнением недостающих в крайней левой группе цифр нулями слева. Затем каждой «двоичной триаде» поставить в соответствие ее восьмеричный эквивалент. Например:  
11011001(2) ? 11’011’001(2) ? 331(8).  
 
Перевод целого двоичного числа в шестнадцатеричное производится путем разбиения данного числа на группы по 4 цифры – «двоичные тетрады»: 1100011011001(2) 1 1000 1101 1001(2) 18D9(16). 
 
Для перевода дробных частей двоичных чисел в восьмеричную или шестнадцатиричную системы аналогичное разбиение на триады или тетрады производится от запятой вправо с дополнением недостающих в крайней правой группе цифр нулями справа:  
 
0,1100011101(2)  0,110 001 110 100 0,6164(8),  
0,1100011101(2)  0,1100 0111 0100 0,С74(16).  
 
Перевод восьмеричных (шестнадцатеричных) чисел в двоичные производится обратным путем – сопоставлением каждому знаку числа соответствующей тройки (четверки) двоичных цифр.  
Преобразования чисел из двоичной в восьмеричную и шестнадцатеричную системы и наоборот столь просты (по сравнению с операциями между этими тремя системами и привычной нам десятичной) потому, что числа 8 и 16 являются целыми степенями числа 2. Этой простотой и объясняется популярность восьмеричной и шестнадцатеричной систем в вычислительной технике и программировании.  
 
Важными особенностями представления чисел в устройствах компьютера являются: 
1. числа записываются в двоичной системе счисления 
2. для записи и обработки чисел отводится конечное количество разрядов 
 
В связи с этим способы кодирования чисел и выполнения операций различаются в зависимости от используемого вида числовых множеств: 
• целые положительные (без знака) числа; 
• целые число со знаком; 
• вещественные числа; 
 
Кодирование и обработка целых чисел без знака.  
В зависимости от величины используемых в вычислениях чисел в ЭВМ используются машинные слова размером от 2 до 8 байт. Для определенности используемых в дальнейшем описании величин рассмотрим используемые в языке PASCAL целые числа без знака размером 2 байта, определенные как тип WORD. Наибольшее значение правильно представляемого в машинном слове числа соответствует наибольшим значениям в каждом разряде числа “1” и равно 1111111111111111(2) = 216 – 1 = 65535(10), Наименьшее число 0000000000000000(2) =0(10) . 
 
Арифметическими операциями с беззнаковыми целыми числами не изменяющими тип числа являются сложение и вычитание. 
Для выполнения арифметических операций в системе счисления с основанием B=2 следует использовать соответствующие таблицы сложения и умножения

 
В случае совпадения величин “1”  в одинаковых разрядах слагаемых  чисел результатом в соответствующей  ячейке суммы является “0”, и вместе с тем в старший разряд слагаемых чисел приписывается “1”, называемая битом переноса. Сложение содержимого этого старшего разряда слагаемых должно производится с учетом бита переноса. 
 
Арифметические действия с числами в восьмеричной и шестнадцатеричной системах счисления выполняются по аналогии с двоичной и десятичной системами. Для этого необходимо воспользоваться соответствующими таблицами.  
б) 223,2(8) + 427,54(8) = 652,74(8);

в) 3B3,6(16) + 38B,4(16) = 73E,A(16).

При сложении чисел сумма  может превысить допустимое наибольшее число. Это проявиться в виде бита переноса в старший разряд, отсутствующий в машинном слове. В зависимости от настройки алгоритма вычислений в программе ЭВМ это либо приведет к прекращению вычислений и выводу сообщения об ошибке, либо к автоматическому преобразованию типа целого числа, например в вещественный тип. 
 
Умножение двоичных чисел осуществляется операциями сдвига на один двоичный разряд влево и повторения первого сомножителя в тех разрядах, где второй сомножитель содержит 1, и сдвига без повторения в разрядах, где второй сомножитель содержит 0. То есть операция перемножения двоичных чисел представляет собой чередование операций сдвига и сложения двоичных чисел. 
 
Пример 5. Выполнить умножение: 
а) 13(10) * 5(10) = 65(10). Операции выполнить в двоичной системе счисления.

Кодирование и  обработка целых чисел со знаком.

Кодирование целых чисел  со знаком (“+” или “-“) в двоичной системе счисления можно осуществить  двумя способами. 
Первый вариант предусматривает использование старшего разряда машинного слова для кодирования знака, а оставшуюся часть машинного слова – для записи значения числа. Условились считать 0 в старшем разряде машинного слова соответствующим знаку “+”, 1 - соответствующей знаку “-”. Такое представление чисел названо прямым кодом.  
 
Прямой код целого числа может быть получен следующим образом: число переводится в двоичную систему счисления, а затем его двоичную запись слева дополняют таким количеством незначащих нулей, сколько требует тип данных, к которому принадлежит число. 
Например, если число 37(10) = 100101(2) объявлено величиной типа Integer, то его прямым кодом будет 0000000000100101, а если величиной типа LongInt, то его прямой код будет 00000000000000000000000000100101. Для более компактной записи чаще используют шестнадцатеричный код. Полученные коды можно переписать соответственно как 0025(16) и 00000025(16). 
Ввиду сложности выполнения операций с числами этот вариант кодирования чисел со знаками не нашел практического применения.  
 
Второй вариант предусматривает использование представление чисел в дополнительном коде. В основу использования дополнительного кода положены два наблюдения.  
Одно основано на переполнении разрядов машинного слова. Например, если используется четырехразрядное машинное слово, то наибольшее число равно  
1111(2)=24 - 1==15(10). При сложении двоичных чисел, сумма которых превысит 15(10), старший значащий разряд кода суммы выйдет за пределы машинного слова. Например, при сложении  
7(10) =0111(2) и 11(10) =1011(2) будет получено число 18(10) = (1)0010(2), . 
 
Второе наблюдение состоит в том, что представляемые машинным словом коды чисел можно разделить на две равные группы, одна из которых содержит в старшем разряде 0, а другая 1. Далее коды по одному из каждой группы можно попарно сгруппировать так, что одно из них представляет положительное число, а другое равное ему по модулю отрицательное число, Например, код 0001 отображает 1, а код 1001 отображает -1, код 0010 отображает 2, а код 1010 отображает -2, и так далее. 
 
Практически для записи модуля числа отводится количество разрядов, на единицу меньшее числа разрядов машинного слова. Дополнительный код двоичных целых чисел формируется по следующим правилам: 
• Дополнительный код целого положительного числа совпадает с его прямым кодом – самим числом. 
• Дополнительный код целого отрицательного числа формируется согласно следующему алгоритму:  
1. записать прямой код модуля числа;  
2. инвертировать его (заменить единицы нулями, нули - единицами);  
3. прибавить к инверсному коду единицу.  
 
Пример. 
Запись дополнительного кода числа -37(10) , интерпретируемого величиной типа LongInt: 
прямой код числа 37 есть 00000000000000000000000000100101;  
инверсный код 11111111111111111111111111011010;  
+1 
дополнительный код 11111111111111111111111111011011 или FFFFFFDB(16) .  
 

Для восстановления значения числа по его дополнительному  коду следует определить его знак.  
Если старший разряд кода содержит 0, то число положительное и следует перевести его код в десятичную систему счисления.  
В случае записи в старшем разряде 1, для восстановления отрицательного числа необходимо выполнить следующий алгоритм: 
1. инвертировать код;  
2. прибавить 1;  
3. определить модуль числа в десятичной системе счисления. 
4. Полученное число записать со знаком минус.

Кодирование символьной информации.

Чтобы определить необходимую  длину кода для представления  символьной информации определим количество знаков в первичном алфавите. Компьютерный алфавит символов должен включать: 
26*2 = 52 букв латинского алфавита (строчных и прописных)  
33*2 = 66 букв русского алфавита (строчных и прописных)  
10 цифр (0..9) 
20 знаков математических операций, знаков препинания, спецсимволов 
Общее число символов = 148. Требуемое число двоичных разрядов составляет  
log2148 > 7,21. Следовательно, для кодирования символов следует использовать не менее 8 бит, которые получили названия 1 байт. 8 бит позволяет записать 256 разных знаков алфавита, а значит использовать дополнительное количество кодов для обозначения новых знаков. Такой способ кодирования принят в компьютерных системах. Любому символу ставится в соответствие код из 8 двоичных разрядов. Эта последовательность хранится и обрабатывает как целое. Поэтому разрядность устройств компьютера стала кратна 8. Взаимосвязь вероятностного и объемного подходов к оценке количества информации выражается в том, что при равновероятном распределении знаков алфавита 1 байт соответствует количеству информации в одном знаке. 
 
Набор символов персональных ЭВМ IBM PC чаще всего является расширением кода ASCII (American Standard Code for Information Interchange – стандартного американского кода для обмена информацией). Он регламентирует коды первой половины таблицы кодов (номера кодов от 0 до 127, т.е. первый бит всех кодов равен 0). Эта группа отведена для прописных и строчных английских букв, цифр, знаков препинания и математических операций, а также для некоторых управляющих кодов (номера от 0 до 31), вырабатываемых при использовании клавиатуры. 
 
Вторая часть кодовой таблицы считается расширением основной части. Она содержит первый бит равным 1 и используется для представления знаков национальных алфавитов.

      Таблица кодов ASCII (расширенная)

В настоящее время  все более широкое применение получает стандарт международной кодировки Unicode, использующий 16-битное (2 байта) кодирование. Это позволяет закодировать 65536 знаков и создать единую для всех распространенных алфавитов кодовую таблицу.