Урок №6. Равномерные и неравномерные двоичные коды.
Если нам нужно записать в память компьютера какой-то текст на русском языке, его нужно представить в виде двоичного кода, т. е. перекодировать.
Например, перекодируем слово ГАГАРА в двоичный алфавит, считая, что в тексте есть только буквы «А», «Г» и «Р», т. е. алфавит состоит из трёх знаков. Присвоим каждой из этих букв двоичные коды — кодовые слова (рис. 2.5).
Закодируйте с помощью этого кода слово ГАГАРА.
Такой код называется равномерным, потому что длина всех кодовых слов одинакова.
Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину.
Теперь предположим, что по компьютерной сети передана цепочка
000010000100000010000100
Известно, что для кодирования использовалась таблица, показанная на рис. 2.5, и нам нужно узнать, какое сообщение было закодировано. Эта операция называется декодированием.
Декодирование — это восстановление исходного сообщения из кода.
Сообщение 000010000100000010000100 закодировано с помощью равномерного кода, приведённого на рис. 2.5. Определите, сколько знаков было в исходном сообщении. Как вы рассуждали? Декодируйте это сообщение.
Равномерный 5-битный двоичный код, разработанный в конце XIX века Жаном Морисом Бодо, использовался в телеграфных аппаратах. В современных компьютерных системах при передаче текстовых сообщений также часто применяют равномерный (8-битный или 16-битный) код.
Можно ли было для кодирования букв «А», «Г», «Р» использовать более короткий равномерный код? Определите наименьшую возможную длину кодовых слов.
Если для кодирования используется алфавит мощностью M, то с помощью кодовых слов длиной L можно закодировать ML различных знаков. Это число должно быть не меньше, чем мощность алфавита исходного сообщения M0, потому что иначе какие-то буквы обязательно получат одинаковые коды.
Длину кодовых слов L выбирают из условия ML>M0, где М0 — мощность алфавита исходного сообщения и М — мощность нового алфавита.
Как выбрать наименьшую возможную длину кодовых слов при равномерном кодировании?
В сообщении используются 33 русские прописные буквы и пробел. Определите наименьшую длину кодовых слов для равномерного кодирования этого сообщения в трёхбуквенном и четырёхбуквенном алфавитах.
Недостаток равномерного кода в том, что закодированные сообщения получаются довольно длинными, и на их передачу компьютерная система тратит много времени. Попробуем сократить длину сообщения, используя кодовые слова разной длины, например так (рис. 2.6).
Такой код называется неравномерным.
Неравномерный код — это код, в котором кодовые слова имеют различную длину.
Закодируйте с помощью этого кода слово ГАГАРА. При использовании равномерного или неравномерного кода закодированное сообщение получилось короче?
Декодируйте сообщение 010010, закодированное с помощью кода на рис. 2.6. Попробуйте построить разные варианты декодированного сообщения.
Сообщения, закодированные с помощью неравномерного кода, не всегда можно декодировать однозначно.
Есть ли такие неравномерные коды, сообщения в которых однозначно декодируются? Оказывается, есть. Например, такой код (рис. 2.7).
Закодируйте с помощью этого кода слово ГАГАРА. Сравните длины полученного закодированного сообщения и сообщений, которые вы построили ранее. Какое из них самое короткое? Самое длинное?
Декодируйте сообщение 01001011, закодированное с помощью кода на рис. 2.7. Попробуйте построить различные варианты декодирования.
Неравномерный код декодируется однозначно, если выполняется условие Фано: ни одно кодовое слово не совпадает с началом другого кодового слова.
Для кода на рис. 2.7 условие Фано выполняется: код буквы «А» (0) не совпадает с началом остальных кодовых слов, то же выполняется и для остальных букв.
Долгое время для передачи сообщений по телеграфу и радио применялся код Морзе (азбука Морзе), предложенный американским художником и изобретателем Самюэлем Морзе. В этом коде все буквы и цифры кодируются в виде различных последовательностей точек и тире.
Определите, к каким кодам относится код Морзе — к равномерным или неравномерным. Как вы рассуждали?
Как вы думаете, какие буквы должны иметь более короткие коды: те, которые в текстах встречаются чаще, или те, которые встречаются реже?
Чтобы узнать, как часто встречается каждая буква в текстах, Морзе посетил типографию и подсчитал количество используемых литер с изображениями разных букв. Поэтому английская буква «Е», которая встречается в текстах чаще всего, получила код •. Коды Морзе для русских букв совпадают с кодами похожих по звучанию английских букв, например коды букв «Л» и «L» одинаковы.
Проверьте, выполняется ли для кода Морзе условие Фано.
Чтобы отделить последовательности (коды букв) друг от друга, вводят ещё один знак — пробел (пауза). Если бы не было разбивки на буквы, текст было бы невозможно декодировать однозначно.
Давайте вспомним, как измеряется количество информации (данных) в компьютерных системах. Сообщение кодируется с помощью двоичного кода, и количество информации в битах определяется как длина полученной битовой цепочки.
Сколько бит информации содержится в сообщении 10100011?
Сколько знаков содержит алфавит двоичного кода?
Определите, сколько различных сообщений можно закодировать с помощью i бит.
На практике используются следующие единицы количества информации:
1 байт = 8 бит.
1 Кбайт = 1024 байта = 210 байта = 213 бит.
1 Мбайт = 1024 Кбайт = 220 байта = 223 бит.
1 Гбайт = 1024 Мбайт.
1 Тбайт = 1024 Гбайт.