Двоичная кодировка алфавита. Равномерное алфавитное двоичное кодирование. Байтовый код
При передаче сообщений по линиям связи всегда приходится пользоваться тем или иным кодом, т. е. представлением сообщения в виде ряда сигналов. Общеизвестным примером кода может служить принятая в телеграфии для передачи словесных сообщений азбука Морзе. С помощью этой азбуки любое сообщение представляется в виде комбинации элементарных сигналов: точка, тире, пауза (пробел между буквами), длинная пауза (пробел между словами).
Вообще кодированием называется отображение состояния одной физической системы с помощью состояния некоторой другой. Например, при телефонном разговоре звуковые сигналы кодируются в виде электромагнитных колебаний, а затем снова декодируются, превращаясь в звуковые сигналы на другом конце линии. Наиболее простым случаем кодирования является случай, когда обе системы и (отображаемая и отображающая) имеют конечное число возможных состояний. Так обстоит дело при передаче записанных буквами сообщений, например, при телеграфировании. Мы ограничимся рассмотрением этого простейшего случая кодирования.
Пусть имеется некоторая система (например, буква русского алфавита), которая может случайным образом принять одно из состояний . Мы хотим отобразить ее (закодировать) с помощью другой системы , возможные состояния которой . Если (число состояний системы меньше числа состояний системы ), то нельзя каждое состояние системы закодировать с помощью одного-единственного состояния системы . В таких случаях одно состояние системы приходится отображать с помощью определенной комбинации (последовательности) состояний системы . Так, в азбуке Морзе буквы отображаются различными комбинациями элементарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется «кодированием» в узком смысле слова.
Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, иными словами - по числу возможных состояний системы . В азбуке Морзе таких элементарных символов четыре (точка, тире, короткая пауза, длинная пауза). Передача сигналов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т. п. Код с двумя элементарными символами (0 и 1) называется двоичным. Двоичные коды широко применяются на практике, особенно при вводе информации в электронные цифровые вычислительные машины, работающие по двоичной системе счисления.
Одно и то же сообщение можно закодировать различными способами. Возникает вопрос об оптимальных (наивыгоднейших) способах кодирования. Естественно считать наивыгоднейшим такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (например 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов.
Предположим, что перед нами поставлена задача: закодировать двоичным кодом буквы русской азбуки так, чтобы каждой букве соответствовала определенная комбинация элементарных символов 0 и 1 и чтобы среднее число этих символов на букву текста было минимальным.
Рассмотрим 32 буквы русской азбуки: а, б, в, г, д, е, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я плюс промежуток между словами, который мы будем обозначать «–». Если, как принято в телеграфии, не различать букв ъ и ь (это не приводит к разночтениям), то получится 32 буквы: а, б, в, г, д, е, ж. з, и, й, к, л, м, н, о, п, р, с, т, у. ф, х, ц, ч, ш, щ, (ъ, ь). ы. э, ю, я, «–».
Первое, что приходит в голову - это, не меняя порядка букв, занумеровать их подряд, приписав им номера от 0 до 31, и затем перевести нумерацию в двоичную систему счисления. Двоичная система - это такая, в которой единицы разных разрядов представляют собой разные степени двух. Например, десятичное число 12 изобразится в виде
и в двоичной системе запишется как 1100.
Десятичное число 25 -
Запишется в двоичной системе как 11001.
Каждое из чисел может быть изображено пятизначным двоичным числом. Тогда получим следующий код:
В этом коде на изображение каждой буквы тратится ровно 5 элементарных символов. Возникает вопрос, является ли этот простейший код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символов?
Действительно, в нашем коде на изображение каждой буквы - часто встречающихся «а», «е», «о» или редко встречающихся «щ», «э», «ф» - тратится одно и то же число элементарных символов. Очевидно, разумнее было бы, чтобы часто встречающиеся буквы были закодированы меньшим числом символов, а реже встречающиеся - большим.
Чтобы составить такой код, очевидно, нужно знать частоты букв в русском тексте. Эти частоты приведены в таблице 18.8.1. Буквы в таблице расположены в порядке убывания частот.
Таблица 18.8.1.
Пользуясь такой таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1.
Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (дв. ед.). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Изложим здесь способ построения кода, удовлетворяющего поставленному условию; этот способ известен под названием «кода Шеннона - Фэно». Идея его состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы - 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится нуль; для второй подгруппы - единица и т. д.
Продемонстрируем принцип построения кода Шеннона - Фэно на материале русского алфавита (табл. 18.8.1). Отсчитаем первые шесть букв (от «-» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы (от «н» до «сф») придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «-» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «-» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы"- единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая и будет закодирована определенным двоичным числом. Механизм построения кода показан на таблице 18.8.2, а сам код приведен в таблице 18.8.3.
Таблица 18.8.2.
|
Двоичные знаки |
|||||||||
Таблица 18.8.3
|
Двоичное число |
Двоичное число |
Двоичное число |
Двоичное число |
||||
С помощью таблицы 18.8.3 можно закодировать и декодировать любое сообщение.
В виде примера запишем двоичным кодом фразу: «теория информации»
01110100001101000110110110000
0110100011111111100110100
1100001011111110101100110
Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно. В этом можно убедиться, декодируя с помощью таблицы 18.8.2 следующую фразу:
10011100110011001001111010000
1011100111001001101010000110101
010110000110110110
(«способ кодирования»).
Однако необходимо отметить, что любая ошибка при кодировании (случайное перепутывание знаков 0 и 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования может быть рекомендован только в случае, когда ошибки при кодировании и передаче сообщения практически исключены.
Возникает естественный вопрос: а является ли составленный нами код при отсутствии ошибок действительно оптимальным? Для того чтобы ответить на этот вопрос, найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна одной двоичной единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву:
,
где - вероятность того, что буква примет определенное состояние («-», о, е, а,…, ф).
Из табл. 18.8.1 имеем
(дв. единиц на букву текста).
По таблице 18.8.2 определяем среднее число элементарных символов на букву
Деля энтропию на , получаем информацию на один элементарный символ
(дв.
ед.).
Таким образом, информация на один символ весьма близка к своему верхнему пределу 1, а выбранный нами код весьма близок к оптимальному. Оставаясь в пределах задачи кодирования по буквам, мы ничего лучшего получить не сможем.
Заметим, что в случае кодирования просто двоичных номеров букв мы имели бы изображение каждой буквы пятью двоичными знаками и информация на один символ была бы
(дв.
ед.),
т. е. заметно меньше, чем при оптимальном буквенном кодировании.
Однако надо заметить, что кодирование «по буквам» вообще не является экономичным. Дело в том, что между соседними буквами любого осмысленного текста всегда имеется зависимость. Например, после гласной буквы в русском языке не может стоять «ъ» или «ь»; после шипящих не могут стоять «я» или «ю»; после нескольких согласных подряд увеличивается вероятность гласной и т. д.
Мы знаем, что при объединении зависимых систем суммарная энтропия меньше суммы энтропий отдельных систем; следовательно, информация, передаваемая отрезком связного текста, всегда меньше, чем информация на один символ, умноженная на число символов. С учетом этого обстоятельства более экономный код можно построить, если кодировать не каждую букву в отдельности, а целые «блоки» из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как «тся», «ает», «ние» и т. п. Кодируемые блоки располагаются в порядке убывания частот, как буквы в табл. 18.8.1, а двоичное кодирование осуществляется по тому же принципу.
В ряде случаев оказывается разумным кодировать даже не блоки из букв, а целые осмысленные куски текста. Например, для разгрузки телеграфа в предпраздничные дни целесообразно кодировать условными номерами целые стандартные тексты, вроде:
«поздравляю новым годом желаю здоровья успехов работе».
Не останавливаясь специально на методах кодирования блоками, ограничимся тем, что сформулируем относящуюся сюда теорему Шеннона.
Пусть имеется источник информации и приемник , связанные каналом связи (рис. 18.8.1).
Известна производительность источника информации , т. е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источникам в единицу времени). Пусть, кроме того, известна пропускная способность канала , т. е. максимальное количество информации (например, двоичных знаков 0 или 1), которое способен передать канал в ту же единицу времени. Возникает вопрос: какова должна быть пропускная способность канала, чтобы он «справлялся» со своей задачей, т. е. чтобы информация от источника к приемнику поступала без задержки?
Ответ на этот вопрос дает первая теорема Шеннона. Сформулируем ее здесь без доказательства.
1-я теорема Шеннона
Если пропускная способность канала связи больше энтропии источника информации в единицу времени
то всегда можно закодировать достаточно длинное сообщение так, чтобы оно передавалось каналом связи без задержки. Если же, напротив,
то передача информации без задержек невозможна.
Разрядность двоичного кода, Преобразование информации из непрерывной формы в дискретную, Универсальность двоичного кодирования, Равномерные и неравномерные коды, Информатика 7 класс Босова, Информатика 7 класс
1.5.1. Преобразование информации из непрерывной формы в дискретную
Для решения своих задач человеку часто приходится преобразовывать имеющуюся информацию из одной формы представления в другую. Например, при чтении вслух происходит преобразование информации из дискретной (текстовой) формы в непрерывную (звук). Во время диктанта на уроке русского языка, наоборот, происходит преобразование информации из непрерывной формы (голос учителя) в дискретную (записи учеников).
Информация, представленная в дискретной форме, значительно проще для передачи, хранения или автоматической обработки. Поэтому в компьютерной технике большое внимание уделяется методам преобразования информации из непрерывной формы в дискретную.
Дискретизация информации — процесс преобразования информации из непрерывной формы представления в дискретную.
Рассмотрим суть процесса дискретизации информации на примере.
На метеорологических станциях имеются самопишущие приборы для непрерывной записи атмосферного давления. Результатом их работы являются барограммы — кривые, показывающие, как изменялось давление в течение длительных промежутков времени. Одна из таких кривых, вычерченная прибором в течение семи часов проведения наблюдений, показана на рис. 1.9.
На основании полученной информации можно построить таблицу, содержащую показания прибора в начале измерений и на конец каждого часа наблюдений (рис. 1.10).
Полученная таблица даёт не совсем полную картину того, как изменялось давление за время наблюдений: например, не указано самое большое значение давления, имевшее место в течение четвёртого часа наблюдений. Но если занести в таблицу значения давления, наблюдаемые каждые полчаса или 15 минут, то новая таблица будет давать более полное представление о том, как изменялось давление.
Таким образом, информацию, представленную в непрерывной форме (барограмму, кривую), мы с некоторой потерей точности преобразовали в дискретную форму (таблицу).
В дальнейшем вы познакомитесь со способами дискретного представления звуковой и графической информации.
Соответственно, четырёхразрядйый двоичный позволяет получить 16 кодовых комбинаций, пятиразрядный — 32, шестиразрядный — 64 и т. д. Длину двоичной цепочки — количество символов в двоичном коде — называют разрядностью двоичного кода.
Обратите внимание, что:
4 = 2 * 2,
8 = 2 * 2 * 2,
16 = 2 * 2 * 2 * 2,
32 = 2 * 2 * 2 * 2 * 2 и т. д.
Здесь количество кодовых комбинаций представляет собой произведение некоторого количества одинаковых множителей, равного разрядности двоичного кода.
Если количество кодовых комбинаций обозначить буквой N, а разрядность двоичного кода — буквой i, то выявленная закономерность в общем виде будет записана так:
N = 2 * 2 * ... * 2.
i множителей
В математике такие произведения записывают в виде:
N = 2 i .
Запись 2 i читают так: «2 в i-й степени».
Задача. Вождь племени Мульти поручил своему министру разработать двоичный и перевести в него всю важную информацию. Двоичный какой разрядности потребуется, если алфавит, используемый племенем Мульти, содержит 16 символов? Выпишите все кодовые комбинации.
Решение. Так как алфавит племени Мульти состоит из 16 символов, то и кодовых комбинаций им нужно 16. В этом случае длина (разрядность) двоичного кода определяется из соотношения: 16 = 2 i . Отсюда i = 4.
Чтобы выписать все кодовые комбинации из четырёх 0 и 1, воспользуемся схемой на рис. 1.13: 0000, 0001, 0010, 0011, 0100, 0101, 0110,0111,1000,1001,1010,1011,1100,1101,1110,1111.
1.5.3. Универсальность двоичного кодирования
В начале этого параграфа вы узнали, что , представленная в непрерывной форме, может быть выражена с помощью символов некоторого естественного или формального языка. В свою очередь, символы произвольного алфавита могут быть преобразованы в двоичный . Таким образом, с помощью двоичного кода может быть представлена любая на естественных и формальных языках, а также изображения и звуки (рис. 1.14). Это и означает универсальность двоичного кодирования.
Двоичные коды широко используются в компьютерной технике, требуя только двух состояний электронной схемы — «включено» (это соответствует цифре 1) и «выключено» (это соответствует цифре 0).
Простота технической реализации — главное достоинство двоичного кодирования. Недостаток двоичного кодирования — большая длина получаемого кода.
1.5.4. Равномерные и неравномерные коды
Различают равномерные и неравномерные коды. Равномерные коды в кодовых комбинациях содержат одинаковое число символов, неравномерные — разное.
Выше мы рассмотрели равномерные двоичные коды.
Примером неравномерного кода может служить азбука Морзе, в которой для каждой буквы и цифры определена последовательность коротких и длинных сигналов. Так, букве Е соответствует короткий сигнал («точка»), а букве Ш — четыре длинных сигнала (четыре «тире»). Неравномерное позволяет повысить скорость передачи сообщений за счёт того, что наиболее часто встречающиеся в передаваемой информации символы имеют самые короткие кодовые комбинации.
В данном случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано однообразное количество инфы равное I ( А) = log 2 N. Сформировывать признак конца знака не требуется, потому для определения длины кода можно пользоваться формулой К(А ,2) > log 2 N. Приемное устройство просто отсчитывает обсужденное заблаговременно количество простых сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует), соотнося ее с таблицей кодов. Правда, при всем этом недопустимы сбои, к примеру, пропуск (непрочтение) 1-го простого сигнала приведет к сдвигу всей кодовой последовательности и неверной ее интерпретации; решается неувязка методом синхронизации передачи либо другими методами, о которых речь пойдет в гл. 5. С другой стороны, применение равномерного кода оказывается одним из средств контроля корректности передачи, так как факт поступления излишнего простого сигнала либо, напротив, поступление неполного кода сходу интерпретируется как ошибка.
Примером равномерного алфавитного кодировки является телеграфный код Бодо, пришедший на замену азбуке Морзе. Начальный алфавит должен содержать менее 32-х знаков; тогда К(А, 2) = log 2 32 = 5, т.е. каждый символ первичного алфавита содержит 5 бит инфы и кодируется цепочкой из 5 двоичных символов. Условие N ≤ 32, разумеется, производится для языков, основанных на латинском алфавите (Т = 27 = 26 + «пробел» ), но в российском алфавите 34 буковкы (с пробелом) — конкретно по этой причине пришлось «сжать» алфавит (как в коде Хаффмана) и соединить в один символ «е» и «ё», также «ь» и «ъ», что видно из табл. 3.1. После такового сжатия N = 32, но, не остается свободных кодов для символов препинания, потому в телеграммах они отсутствуют либо заменяются буквенными аббревиатурами; это не является приметным ограничением, так как, как указывалось выше, избыточность языка позволяет просто вернуть информационное содержание сообщения. Избыточность кода Бодо для российского языка Q(r ,2) = 0,148, для британского Q (e ,2) = 0,239.
Другим принципиальным для нас примером использования равномерного алфавитного кодировки является представление символьной (знаковой) инфы в компьютере. Чтоб найти длину кода, нужно начать с установления количество символов в первичном алфавите. Компьютерный алфавит должен включать:
- 26 х 2 = 52 букв латинского алфавита (с учетом строчных и строчных);
- 33 х 2 = 66 букв российского алфавита;
- числа 0.. .9 — всего 10;
- знаки математических операций, знаки препинания, спецсимволы ≈ 20.
Получаем, что общее число знаков N ≈ 148. Сейчас можно оценить длину кодовой цепочки: К(с, 2) ≥ log 2 148 ≥ 7,21. Так как длина кода выражается целым числом, разумеется, К(с, 2) = 8. Конкретно таковой метод кодировки принят в компьютерных системах: хоть какому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта последовательность сохраняется и обрабатывается как единое целое (т.е. отсутствует доступ к отдельному биту) — по этой причине разрядность устройств компьютера, созданных для хранения либо обработки инфы, кратна 8. Совокупа восьми связанных бит получила заглавие б, а представление таким образом знаков — байтовым кодировкой.
Б вместе с битом может употребляться как единица измерения количества инфы в сообщении. Один б соответствует количеству инфы в одном знаке алфавита при их равновероятном рассредотачивании. Этот метод измерения количества инфы именуется также большим. Пусть имеется некое сообщение (последовательность символов); оценка количества содержащейся в нем инфы согласно рассмотренному ранее вероятностному подходу (при помощи формулы Шеннона (2.17)) дает I вер, а большая мера пусть равна I об; соотношение меж этими величинами вытекает из (2.7):
Конкретно б принят в качестве единицы измерения количества инфы в интернациональной системе единиц СИ. 1 б = 8 бит. Вместе с б для измерения количества инфы употребляются более большие производные единицы:
Внедрение 8-битных цепочек позволяет закодировать 2 8 =256 знаков, что превосходит оцененное выше N и, как следует, дает возможность употребить оставшуюся часть кодовой таблицы для представления дополнительных знаков.
Но недостаточно только договориться об определенной длине кода. Ясно, что методов кодировки, т.е. вариантов сравнения знакам первичного алфавита восьмибитных цепочек, сильно много. По этой причине для сопоставимости технических устройств и обеспечения способности обмена информацией меж многими потребителями требуется согласование кодов. Схожее согласование осуществляется в форме стандартизации кодовых таблиц.
Первым таким интернациональным эталоном, который применялся на огромных вычислительных машинах, был EBCDIC (Extended Binary Coded Decimal Interchange Code) — «расширенная двоичная шифровка десятичного кода обмена». В компьютерах и телекоммуникационных системах применяется интернациональный байтовый код ASCII (American Standard Code for Information Interchange — «американский стандартный код обмена информацией»).
Он регламентирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, т.е. 1-ый бит всех кодов 0). В эту часть попадают коды строчных и строчных британских букв, числа, знаки препинания и математических операций, также некие управляющие коды (номера от 0 до 31), вырабатываемые при использовании клавиатуры. Ниже приведены некие ФSC -коды:
2-ая часть кодовой таблицы — она считается расширением основной — обхватывает коды в интервале от 128 до 255 (1-ый бит всех кодов 1). Она употребляется для представления знаков государственных алфавитов (к примеру, российского), также знаков псевдографики. Для этой части также имеются эталоны, к примеру, для знаков российского языка это КОИ-8, КОИ-7 и др.
Как в основной таблице, так и в ее расширении коды букв и цифр соответствуют их словарному порядку (т.е. порядку следования в алфавите ) — это обеспечивает возможность автоматизации обработки текстов и ускоряет ее.
В текущее время появился и находит все более обширное применение очередной интернациональный эталон шифровки — Unicode. Его особенность в том, что в нем применено 16-битное кодирование, т.е. для представления каждого знака отводится 2 б. Такая длина кода обеспечивает включения в первичный алфавит 65536 символов. Это, в свою очередь, позволяет сделать и использовать единую для всех всераспространенных алфавитов кодовую таблицу.
