§ 6. Кодирование

§6 Кодирование

 

Как показано в главе 1 и в § 5, для хранения и передачи информации нужно записать её, зафиксировать на некотором языке (с помощью какого-то алфавита), т. е. закодировать. Это особенно важно в наше время, когда данные в компьютерных системах передаются, хранятся и обрабатываются в закодированном виде.

 

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

 

В зависимости от конкретной задачи информация может кодироваться разными способами. Например, фраза «Привет, Вася!» может быть закодирована транслитом (так сокращённо называ­ют транслитерацию — русский текст, записанный латинскими буквами): «Privet, Vasya!». Такой метод используют в электрон­ных письмах, когда у одного собеседника (или у обоих) на ком­пьютере нет поддержки русского языка. То же самое сообщение можно просто перевести на английский (или какой-то другой) язык, если собеседник не знает русского языка. А можно даже зашифровать: «Рсйгжу-!Гбта»». Шифрование — это один из способов кодирования, при котором нужно скрыть смысл сообщения от посторонних1.

Для кодирования числовой информа-     

ции в разных ситуациях тоже используют разные способы. Например, число 21 мож­но записать как XXI (в римской системе счисления) или «двадцать один» (в финансовых документах).

Код Морзе

Долгое время для передачи сообщений по телеграфу и радио применялся код Морзе2 (азбука Морзе), предложенный американским художником и изобретателем Самюэлем  Морзе.  В  этом  коде  все буквы  и

цифры   кодируются   В  виде  различных  последовательностей точек и тире.

 р

 

 

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

Код Морзе для русских букв и цифр

 

 Код Морзе — неравномерный, т. е. коды символов могут быть разной длины. Для сокращения общего времени передачи буквы, которые встречаются чаще, имеют более короткие коды. Чтобы узнать, как часто встречается каждая буква в текстах, Морзе по­сетил типографию и подсчитал количество используемых литер с изображениями разных букв. Поэтому английская буква «Б», ко­торая встречается в текстах чаще всего, получила код •. Коды Морзе для русских букв совпадают с кодами похожих по звучанию английских букв, например коды букв *Л» и «L» одинаковы1.

Чтобы отделить последовательности (коды букв) друг от друга, вводят еще один символ — пробел (пауза). Например, имя «Вася», закодированное с помощью кода Морзе, выглядит так:

Если бы не было разбивки на буквы, текст перестал бы рас­
шифровываться однозначно. Например, сообщение •   •— мож­
но было бы прочитать как ВА, АК, ПТ или даже ЕМЕТ.

Поэтому код Морзе для русских букв менее эффективен.

 

Кодирование

 

Двоичное кодирование

 

Для передачи информации обязательно нужно, чтобы свойства носителя как-то изменялись. Самый простой используемый код должен содержать, по крайней мере, два разных знака. Такое кодирование называют двоичным (от слова «два»), оно использу­ется практически во всех современных компьютерах.Двоичное кодирование — это кодирование с помощью двух знаков.

 Например,   сообщение   АБАВГБ   мо; с помощью кодовой таблицы

закодировано

А

Б

В

г

 

00

01

10

11

следующим образом: 000100101101.

Кодирование чисел с помощью нулей и единиц впервые при­менил в своей (механической) вычислительной машине немецкий мыслитель Готфрид Вильгельм Лейбниц в конце XVII века. За­тем, уже в середине XX века, двоичное кодирование информации стало повсеместно применяться для электронных компьютеров.

Чаще всего используется равномер­ный код, когда все символы исходного сообщения кодируются с помощью одинакового количества двоичных знаков. Каждый знак соответствует выбору одного из двух вариантов (0 или 1), поэтому несёт 1 бит информации.

Длина кода определяется количеством вариантов, которые нужно закодировать. Поскольку алфавит двоичного кода содер­жит 2 символа, применяя общую формулу (см. § 3), получаем количество различных сообщений длиной N битов:

Q = 2N                                        Готфрид Вилы

 

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

 

Если заданное количество вариантов не равно степени чис­ла 2, выбирают длину кода с запасом. Например, для кодирова­ния номера спортсмена в интервале от 1 до 200 нужно использо­вать не меньше, чем 8 битов, поскольку

27=128<200<28 = 256.

Если нужно передать информацию о номерах первых 20 спорт­сменов, пришедших к финишу, информационный объём такого сообщения будет равен 8 ■ 20 = 160 битов - 20 байтов.

 

Вопросы и задания

Что такое кодирование?
Зачем кодируют информацию?
Что такое код?
Какой алфавит используется в коде Морзе?
Какие буквы в коде Морзе имеют самые короткие коды? Почему?
Предложите, как можно изменить азбуку Морзе, чтобы сообщения
нерусском языке стали более короткими.
Запишите своё имя с помощью кода Морзе.
Почему в коде Морзе необходим символ-разделитель (пауза)?
В каком случае применяется транслитерация?

 

Где   сейчас   используются   числа,   записанные   в   римской   системе
Как вы думаете, зачем в финансовых документах денежные суммы
пишут прописью?
Какое кодирование называют двоичным?
Можно ли при двоичном кодировании использовать не 0 и 1, а дру­
гие знаки (например, буквы А и Б)?
Объясните, как при двоичном кодировании связаны длина сообще­
ния и количество информации в нём.

Подготовьте сообщение

а)«Код Морзе»

б)«История двоичного кодирован

в)«Код Грея*

г)«Шрифт Брайля»

 

Задачи

 

Сколько существует в коде Морзе различных последовательностей
из точек и тире, длина которых равна 4 символа? 6 символов?
Сколько различных пятизначных чисел можно записать с помощью
цифр 4 и 2?
В  алфавите  языка   племени   «тамба-амба»   две  буквы:   Й  и  Ы.
Сколько различных 11-буквенных слов можно образовать в этом
Алфавит языка «амба-карамба» состоит из 5 букв. Сколько различ­
ных четырехбуквенных слов можно образовать в этом языке?
В языке племени «тумба-юмба» разрешены только четырёхбуквен­
ные слова, которые можно образовывать из букв алфавита в любых
комбинациях.   Известно,   что  словарный  запас  языка  составляет
81 слово. Какова мощность алфавита?
Некоторый язык содержит только трёхбуквенные слова, которые

>варный запас языка составляет 216 слов. Каковав алфавите, чтобы остоящих из сим-е менее 9 различ-

ных сообщений?

Световое табло состоит из лампочек. Каждая лампочка может нахо­
диться в одном из трех состояний («включено», «выключено* или
• мигает»). Какое наименьшее количество лампочек должно нахо­
диться на табло, чтобы с его помощью можно было передать 18 раз­
личных сообщений?
Некоторое сигнальное устройство за одну секунду передаёт один из
трёх сигналов. Сколько различных сообщений длиной в четыре се­
кунды можно передать с помощью этого устройства? различ  оящего

11. Для

 передачи сигналов

важна). Какое количество корабль с помощью пят ются флаги четырёх раз ниченное количество)?

12. Вася и Петя передают друг другу сообщения, используя синий, красный и зелёный фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последова-

тельноети.  Количество вспышек в одном сообщении — 3 или 4, между сообщениями — паузы. Сколько различных сообщений мо­гут передавать мальчики?

13. Для  кодирования  300  различных  сообщений  используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности , , для каждой вспышки используется одна лампочка определённого цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)? *

14. Некоторый  алфавит  содержит  4   различных  символа.  Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове не могут повторяться?

*15. В текстовом процессоре есть 5 кнопок, с помощью которых можно  включать и выключать следующие режимы: жирный шрифт , курсив, подчеркивание, верхний индекс, нижний  индекс. Сколько различных стилей оформления текста можно использовать?

16. Используя кодовую таблицу

-

А

Б

В

г

00

01

10

11

Закодируйте  сообщение  ГАВВАБ.

17. Шрифт Брайля —■ это специальный шрифт, с помощью которого незрячие люди могут читать. Для кодирования используются 6 точек, расположенных в два столбца. В каждой из них может быть выпуклость, которую человек  воспринимает на ощупь. Коды Брайля первых букв русского алфавита (чёрная точка обозначает вы-

 

 

а

о

 

 

о

 

о •

 

 

•

 

•

•

о

о

 

•

о

 

• •

 

•

•

 

о

•

о

о

 

о

о

 

о •

 

о

о

 

о

о

Сколько различных символов можно закодировать с помощью кода Брайля?

Предложите какой-нибудь способ  перехода от шрифта Брайля к двоичному кодированию.
В чём преимущества использования двоичного кодирования информации в современных компьютерах?
Сколько существует различных последовательностей из символов :
«плюс» и «минус* длиной ровно в пять символов?-

На хранение целого числа отвели 12 битов. Сколько различных чисел можно закодировать таким образом?
Разведчик кодирует секретные сообщения, расставляя крестики и
нолики в ячейки таблицы. Всего он может закодировать 512 сообщений. Сколько ячеек в таблице у разведчика?
Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество битов потребуется для кодирования координат одной шахматной фигуры?
Какое минимальное количество битов потребуется для кодирования
одного из натуральных чисел, меньших 60?
Для кодирования значений температуры воздуха (целое число в интервале от -50 до 40) используется двоичный код. Какова минимальная длина двоичного кода?
В сельскохозяйственном институте изучают всхожесть семян растений. Результатом одного измерения является целое число от 0 до 100%, которое записывается с помощью минимально возможного
количества битов. Всего исследовано 60 партий семян. Определите
информационный объём результатов наблюдений.
Обычный дорожный светофор без дополнительных секций подаёт
шесть видов сигналов (непрерывные красный, жёлтый и зелёный,
мигающие жёлтый и зелёный, мигающие красный и жёлтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы.  Подряд записано
100 сигналов светофора. Определите информационный объём этого
сообщения.
В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего использует 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 32 автомобильных номеров.

В базе данных хранятся записи, содержащие информацию о датах.
Каждая запись содержит три поля: год (число от 1 до 2100), номер
месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 31).
Каждое поле записывается отдельно от других полей с помощью
минимально возможного числа битов. Определите минимальное количество битов, необходимое для кодирования одной записи.
В соревнованиях по ориентированию участвуют 768 спортсменов.
Специальное устройство регистрирует финиш каждого из участников, записывая его номер с использованием минимально возможного количества битов, одинакового для каждого спортсмена. Каков будет информационный объём сообщения (в байтах), записанного устройством, после того как финишируют 200 спортсменов?

 

Декодирование

 

 

Декодирование — это восстановление информационного

сообщения из последовательности кодов.

Например, закодированное сообщение

можно восстановить, используя код Морзе «в обратную сторону»: в этой строке закодирована фамилия «Петров».

В некоторых случаях даже при использовании неравномерно­го кода не требуется вводить символ-разделитель. Для этого до­статочно выполнение условия Фано: ни одно кодовое слово не совпадает с началом другого кодового слова. Такой код называют префиксным.

Пример 1. Пусть для кодирования первых 5 букв русского алфавита используется таблица:

 

А

Б

В

Г

Д

000

10

01

110

001

Это неравномерный код, поскольку в нём есть двух- и трёхсимвольные кодовые слова. Построим для этой кодовой таблицы дерево, в котором от каждого узла (кроме листьев) отходят два ребра, помеченные цифрами 0 и 1. Чтобы найти код символа, нужно пройти по стрелкам от корня дерева к нужному листу, вы­писывая метки стрелок, по которым мы переходим

 

 

 

Заметим, что ни один символ не лежит на пути от корня к другому символу. Это значит, что условие Фано выполняется и любую правильную кодовую последовательность можно однозначно декодировать. Например, рассмотрим цепочку 1100000100110. Букв с кодами 1 и 11 в таблице нет, поэтому сообщение начинается с буквы Г — она имеет код 110:

Следующий (единственно возможный) код — 000, это буква А:

000      ! 0100110

Аналогично декодируем все сообщение:

в                                  д

01      |     001

000

Пример. 2. Рассмотрим другую кодовую таблицу:

 

А

Б

В

г

д

000

01

10

011

100

Здесь условие Фано не выполняется, поскольку код буквы Б (01) является началом кода буквы Г (011), а код буквы Д (100) на­чинается с кода буквы В (10). Дерево для этой кодовой таблицы выглядит так (рис. 2.4).

Корень

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

Тем не менее можно заметить, что выполнено «обратное* условие Фано: ни одно кодовое слово не совпадает с окончанием другого кодового слова {такой код называют постфиксным). По­этому закодированное сообщение можно однозначно декодировать с конца. Например, рассмотрим цепочку 011000110110. Последней буквой в этом сообщении может быть только В (код 10):

0110001101 j      10 Вторая буква с конца — Б (код 01):

01100011         01

И так далее:

Д         Г

100     |     011

Б 01В общем случае (если код не является ни префиксным, ни постфиксным) декодировать сообщение удаётся только перебором вариантов.

Пример 3. Декодируем сообщение 010100111101, закодиро­ванное с помощью кодовой таблицы:

 

А

Б

В

г

д

01

010

011

11

101

Здесь не выполняется ни “прямое”, ни «обратное» условие Фано, поэтому декодировать сообщение однозначно, возможно, не удастся. На первом месте может быть , буква А или буква Б. Сначала предположим ,что это буква А:

 

А0100111101

Тогда второй буквой также может быть буква А: АА00111101.

Дальше декодировать не получается, потому что в таблице нет кодов 0, 00 и 001. Поэтому проверяем второй вариант: вторая буква - Б:

АБ0111101. Третьей буквой может быть А:

АБА11101,

Тогда четвёртая и пятая буквы определяются однозначно — это буквы Г и Д. Таким образом, один из подходящих вариантов — АБАГД.

Посмотрим, есть ли другие варианты. После сочетания АБ мо­жет стоять буква В:

АБВ1101,

тогда оставшиеся буквы — это ГА, а полное сообщение — АБВГА. Этот вариант тоже подходит.

Кроме того, на первом месте может стоять буква Б:

Б100111101,

но дальше декодировать не удается, потому что в таблице нет ко­дов 1, 10 и 100. Таким образом, сообщение может быть декодиро­вано двумя способами: АБАГД и АБВГА.

Пример 3 показывает, что неоднозначное декодирование воз­можно тогда, когда начало кода одной буквы совпадает с концом кода другой и можно переместить границу между кодами букв в сообщении. Например, последовательность 01011 может быть декодирована как АВ (01011) и БГ (01011). Следовательно, нужно обратить внимание на те цепочки, которые встречаются как в начале, так и в конце кодовых слов.

Покажем, как найти сообщения, которые декодируются неоднозначно. Для таблицы из примера 3 построим граф Ал. А. Маркова следующим образом.

1. Определим все последовательности, которые совпадают с нача­лом какого-то кодового слова и одновременно с концом како­го-то кодового слова; в данном случае это две последователь-

0 (начало кода буквы А и конец кода буквы Б) и 1 (начало кода буквы Г и конец кода буквы Д). Последовательности 01 и 11 не учитываем, потому что они со­впадают с кодами букв А и Г.

0 ©     0

!. 2.5

Добавим   к  этому  множеству  (0,   1}  пустую
строку, которую обычно обозначают буквой Л
(прописная греческая буква  «лямбда»); эле­
менты полученного множества (Л, О, 1} ста­
новятся узлами графа (рис. 2.5).
Соединим     узлы     дугами     (направленными
рёбрами) по такому правилу: два узла X и У
соединяются дугой,  если последовательная запись кода узла
X, кода некоторой буквы (или нескольких букв) и кода узла У
даёт код ещё одной буквы (рис. 2.6).

Например, последовательная запись пустой строки (Л), кода буквы А (01) и цепочки 0 даёт цепочку 010, которая совпада­ет с кодом буквы Б; поэтому рисуем дугу из вершины Л в вер­шину 0; у этой дуги пишем А -> Б, и т. д. Поскольку код бук­вы Г можно записать как 11 = 1Л1, у вершины 1 появляется петля Л -> Г.

Любое сообщение декодируется однозначно тогда и только тогда, когда в полученном таким образом графе нет циклов, включающих вершину «л».

В нашем графе есть несколько таких циклов, например:

■  цикл ЛОЛ, соответствующий сообщению ЛАОГЛ ■ 01011; это

сообщение может быть расшифровано как АВ и как БГ; -  цикл  Л1Л,  соответствующий  сообщению  ЛА1АЛ  =  01101;

это сообщение может быть расшифровано как АД и как ВА;

цикл Л01Л, соответствующий сообщению ЛА01АЛ = 010101; это сообщение может быть расшифровано как ААА и как БД.

Кроме того, из-за петли у вершины 1 неоднозначно декодиру­ется любая последовательность вида 01...101, где многоточие обо­значает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА (см. пример 3).

Пример 4. Существуют коды, для которых условия Фано не выполняются, но все сообщения однозначно декодируются. В ко­довой таблице

 

А

Б

В

0

11

010

код буквы А совпадает как с началом, так и с окончанием кода буквы В, т. е. этот код не является ни префиксным, ни постфиксным.

Проверим, можно ли однозначно декодировать сообщения, по­строенные с помощью такого кода. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состо­ит из пустой строки и единицы: (Л, 1}. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю (рис. 2.7).

В этом графе нет цикла, содержащего вершину Л, поэтому любое сооб­щение, записанное с помощью такого кода, декодируется однозначно. Это можно показать и простыми рассуждениями: 1)все цепочки 11 в сообщении ■— это коды букв Б, иначе они не

могут образоваться;

все цепочки 010 — это коды букв В;
остальные символы сообщения могут быть только нулями —
это коды букв А.

Иногда при кодировании и декодировании происходит иска­жение сообщения. Например, известно, что перевод художественных текстов (особенно стихов) на другой язык и затем обратный перевод могут изменить их до неузнаваемости.

Вопросы и задания

Что такое декодирование?
Всегда ли удаётся однозначно декодировать сообщи
чаях это может быть не так?
Перечислите достаточные условия, при которых м
декодировать сообщение с неравномерным кодом.
В каких случаях для декодирования приходится и
бор вариантов?

Задачи

Расшифруйте сообщение, записанное с помощью кода Морзе, ко1 рое используется как международный сигнал бедствия:
Покажите с помощью дерева, '
удовлетворяет «обратному» услс

Для кодирования сообщения иы

1 кодовая таблица из примера 2 ю Фано. [ьзуется таблица

А

Б

В

Г

д

10

11

001

010

011

Найдите все способы декодирования сообщения 1111001011. 4. Для кодирования сообщения используется таблица

 

А

Б

В

г

д

01

11

1000

010

110

Найдите все способы декодирования сообщения 1111001001100. 5. Для кодирования сообщения используется таблица

 

А

Б

В

г

д

0

11

101

110

111

Найдите все способы декодирования сообщения 1111001010.6. Для кодирования сообщения используется таблица

 

А

Б

В

г

д

0

10

1

110

111

Найдите все способы декодирования сообщения 01110011. 7. Для кодирования сообщения используется таблица

 

А

В

С

D

Е

000

01

100

10

011

Декодируйте сообщение 0110100011000.

8. Для кодирования сообщения, состоящего только из букв А, В, С, D и Е, используется неравномерный двоичный код:

 

А

в

с

D

Е

000

11

01

001

10

Какие из сообщений были переданы без ошибок: 1)110000010011110 2)110000011011110 3)110001001001110 4)110000001011110

*9. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 10, В - 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы

*10. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодиро­ванного сообщения на буквы?

*11. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 01, Б = 1, В = 001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодиро­ванного сообщения на буквы?

*12. Для передачи по каналу связи сообщения, состоящего р. 

букв А, Б, В, Г, решили использовать неравномерный код: А = О, Б = 100, В =110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение ко­дированного сообщения на буквы?

*13. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: А = 00, Б = 11, В = 100 и Г = 10. Определите, допускает ли такой код однозначное декодирование сообщения. Выполняется ли для него условие  Фано?

Возврат к главе