Кодирование информации
Кодирование информации — это представление сведений с помощью знаков некоторой знаковой системы по определённым правилам. В этой теме важно различать сообщение, знак, алфавит, кодирование и декодирование, а также уметь читать таблицы соответствий и подсчитывать количество возможных кодов.
Что такое кодирование
Информация существует для получателя в виде сообщения: текста, числа, изображения, звука или сигнала. Чтобы сохранить или передать сообщение, его представляют последовательностью знаков. Например, слово можно записать буквами, число — цифрами, дорожную ситуацию — условными знаками, а цвет светофора — одним из трёх сигналов.
Знак — элемент, который используется для обозначения объекта, свойства или действия. Знаковая система — множество знаков и правил их использования. Код — набор знаков и правил, по которым сообщение переводят в удобное представление. Кодирование — переход от исходного сообщения к его коду. Декодирование — восстановление исходного сообщения по коду.
Кодирование не обязательно означает перевод в нули и единицы. Двоичная запись — только один из вариантов. В азбуке Морзе используются точки и тире, в нотной записи — ноты и специальные обозначения, в химических формулах — символы химических элементов. Код должен быть понятен тому, кто знает правила данной системы.
Обычно в процессе участвуют источник информации, кодирующее устройство или человек, канал связи, декодирующее устройство и получатель информации. Если отправитель и получатель используют разные правила, сообщение может стать непонятным даже при безошибочной передаче.
Алфавит и таблица соответствий
Алфавит — конечное множество знаков, используемых для записи сообщений. Число знаков алфавита называют его мощностью и обозначают \(N\). Русский алфавит содержит 33 буквы, десятичный алфавит — 10 цифр, двоичный — 2 знака: 0 и 1. Пробел, знаки препинания и специальные символы также могут входить в используемый алфавит.
Таблица соответствий показывает, какой код поставлен в соответствие каждому исходному знаку. Например: А — 00, Б — 01, В — 10, Г — 11. Если каждому исходному знаку соответствует ровно один код, а разные знаки получают разные коды, таблица задаёт однозначное кодирование.
| Исходный знак | Код |
|---|---|
| А | 00 |
| Б | 01 |
| В | 10 |
| Г | 11 |
По таблице можно кодировать сообщение слева направо: для каждого знака находят его код и соединяют полученные блоки. Для декодирования строку разбивают на кодовые блоки и заменяют их исходными знаками. В равномерном коде все блоки имеют одинаковую длину; подробнее это рассматривается на странице равномерный код.
Длина кода и количество вариантов
Если код использует \(N\) различных знаков, а кодовое слово состоит из \(k\) позиций, то на каждой позиции можно выбрать один из \(N\) знаков. При независимом выборе число различных кодовых слов определяется правилом произведения.
При алфавите мощности \(N\) количество кодовых слов длины \(k\) равно \(N^k\). Если требуется закодировать не менее \(M\) различных сообщений, выбирают минимальное \(k\), для которого \(N^k\ge M\).
Для двоичного алфавита \(N=2\), поэтому количество последовательностей длины \(k\) равно \(2^k\). Так, четырёхразрядный двоичный код имеет \(2^4=16\) вариантов. Если код должен различать 10 знаков, четырёх разрядов достаточно, а трёх недостаточно, потому что \(2^3=8<10\).
Минимальную длину равномерного двоичного кода иногда находят через логарифм: \(k=\lceil\log_2 M\rceil\). Знак \(\lceil x\rceil\) означает округление вверх. Однако на экзамене часто быстрее проверить степени двойки.
Сколько различных кодовых слов длины 3 можно составить из алфавита из 4 знаков?
Разобранный пример: кодирование по таблице
Дана таблица: А — 00, Б — 01, В — 10, Г — 11. Закодируем слово «БАГ» и выполним обратную проверку.
Каждая буква заменяется своим двухразрядным кодом. Поскольку код равномерный, границы блоков легко определить: строку нужно разбить по два символа.
Ответ: код слова «БАГ» — 010011. Важно не переставлять блоки и не удалять начальные нули: запись 010011 содержит три двухразрядных кода, а запись 10011 — уже только пять символов и не сохраняет прежнюю структуру.
Равномерные и неравномерные коды
В равномерном коде длина каждого кодового слова одинакова. Такой код удобно разделять при декодировании: если длина блока равна \(k\), строку читают группами по \(k\) знаков. Пример — код А—00, Б—01, В—10, Г—11.
В неравномерном коде длины кодовых слов различаются. Например, А—0, Б—10, В—110. Такой код может быть короче, если одни знаки встречаются чаще других, но границы кодов нельзя всегда определить сразу. Для однозначного чтения желательно, чтобы ни одно кодовое слово не было началом другого. Подробные задачи рассматриваются на странице задачи на кодирование информации.
Код называют однозначно декодируемым, если любое полученное кодовое сообщение можно восстановить единственным способом. Для префиксного кода ни одно кодовое слово не является началом другого, поэтому последовательность можно читать слева направо без неоднозначности.
Коды могут быть избыточными: для некоторых сообщений используют больше знаков, чем необходимо теоретически. Избыточное кодирование иногда помогает обнаруживать или исправлять ошибки. В других случаях стремятся уменьшить размер данных, применяя кодирование без потерь или кодирование с потерями.
Как решать задачи на кодирование
- Определите, что именно кодируется: отдельные знаки, слова, числа или сообщения.
- Найдите мощность используемого алфавита и длину кодового слова.
- Если дана таблица, выпишите соответствия и сохраняйте порядок знаков.
- Для подсчёта вариантов примените \(N^k\); для минимальной длины найдите наименьшее \(k\), при котором \(N^k\ge M\).
- Проверьте ответ обратным декодированием или сравнением с условием.
1. Путают число знаков алфавита \(N\) с длиной кода \(k\). 2. Используют \(N\cdot k\) вместо \(N^k\) при подсчёте последовательностей. 3. Теряют начальные нули в двоичном коде. 4. Читают таблицу справа налево, хотя требуется кодирование, а не декодирование. 5. Забывают, что при неодинаковой длине кодов границы блоков могут быть неоднозначны. 6. Округляют \(\log_2 M\) вниз, хотя длина должна обеспечить не менее \(M\) вариантов.
Сначала запишите короткую модель: \(N\) — число знаков, \(k\) — позиций, \(M\) — число сообщений. Затем подставьте значения и только после этого выполняйте вычисления. В задачах с таблицей удобно ставить вертикальные черты между кодовыми блоками.
Связь с другими видами кодирования
Двоичное кодирование использует два знака и лежит в основе представления данных в компьютере. В логическом кодировании значения истинности также часто обозначают 0 и 1. При передаче данных важны кодирование и декодирование, а при наличии помех — помехоустойчивый код. Общая цель одна: представить сообщение так, чтобы его можно было сохранить, передать и восстановить по правилам.
Проверь себя
Главное
- Кодирование — перевод сообщения в представление с помощью знаков и правил; декодирование — обратный перевод.
- Алфавит состоит из знаков, его мощность обозначают \(N\), а длину кодового слова — \(k\).
- Число последовательностей длины \(k\) из алфавита мощности \(N\) равно \(N^k\).
- Для равномерного двоичного кода минимальная длина для \(M\) знаков удовлетворяет \(2^k\ge M\).
- Таблица соответствий позволяет кодировать и декодировать сообщения; порядок знаков и начальные нули сохраняют.
- Однозначное декодирование означает, что кодовое сообщение восстанавливается единственным способом.