Принципы кодирования информации
Кодирование — это представление информации с помощью знаков выбранного алфавита по определённым правилам. Чтобы сообщение можно было использовать, код должен не только однозначно описывать исходные данные, но и позволять выполнить обратное декодирование.
Зачем кодируют информацию
Человек и компьютер используют разные способы представления данных. Текст, число, изображение или звук сначала переводят в последовательность символов, удобную для хранения, обработки или передачи. Например, компьютер работает с двоичными сигналами, поэтому данные представляются последовательностями нулей и единиц.
Кодирование — это процесс преобразования сообщения из одной формы представления в другую с использованием заранее заданных правил. Исходное сообщение называют открытым, а полученную последовательность знаков — закодированным сообщением.
Кодирование применяют для трёх основных целей: уменьшить объём данных, передать данные по каналу связи или сделать их представление удобным для автоматической обработки. Важно отличать кодирование от шифрования: кодирование меняет форму сообщения по известным правилам, а шифрование скрывает содержание от тех, у кого нет ключа.
Алфавит и код
Алфавит — конечное множество различных знаков, используемых для записи сообщений. Число знаков алфавита обозначают \(N\) и называют мощностью алфавита. Например, у двоичного алфавита два знака: 0 и 1; у десятичного — десять цифр от 0 до 9.
Код — это система правил, по которым каждому символу, слову или элементу исходного сообщения ставят в соответствие кодовую комбинацию — последовательность знаков кодового алфавита.
При выборе алфавита учитывают назначение кода. Для сигналов «есть» и «нет» достаточно двух знаков. Для записи цифр удобно использовать десятичный алфавит, а для работы компьютера — двоичный. Один и тот же объект можно кодировать разными способами: букву можно представить числом, двоичной последовательностью или сигналом заданной длительности.
Если кодовый алфавит содержит \(K\) знаков, а длина кодовой комбинации равна \(L\), то число различных комбинаций фиксированной длины вычисляют так:
В коде длины \(L\) над алфавитом из \(K\) знаков можно получить \(K^L\) различных комбинаций, если каждый знак на каждой позиции выбирается независимо.
Для двоичного кода длины 3 возможно \(2^3=8\) комбинаций: 000, 001, 010, 011, 100, 101, 110 и 111. Поэтому таким кодом можно различить не более восьми объектов. Если объектов больше, нужно увеличить длину кода или использовать алфавит с большим числом знаков.
Построение и свойства кодов
При построении кода сначала составляют список объектов, которые требуется обозначить, затем выбирают кодовый алфавит и длину комбинаций. После этого каждой исходной единице назначают отдельный код. Полезна таблица кодирования: в одной колонке записывают исходные символы, в другой — соответствующие им комбинации.
Код бывает фиксированной или переменной длины. В коде фиксированной длины все комбинации имеют одинаковое число знаков. Такой код легко разбивать на группы и декодировать, но иногда он расходует больше места, чем необходимо. В коде переменной длины разные символы имеют комбинации разной длины; это может экономить объём, но требует дополнительных правил.
Код должен позволять восстановить единственное исходное сообщение для любой допустимой кодовой последовательности. Если одну и ту же последовательность можно разделить на кодовые слова по-разному, код неоднозначен.
Самый простой вариант однозначного декодирования — фиксированная длина: сообщение разбивают слева направо на группы по \(L\) знаков. Для переменной длины важно, чтобы границы кодовых слов можно было определить. Часто используют префиксный код: ни одно кодовое слово не является началом другого.
Сколько различных комбинаций можно составить из знаков 0 и 1, если длина каждой комбинации равна 4?
Декодирование сообщения
Декодирование — обратное преобразование закодированной последовательности в исходное сообщение. Сначала нужно определить алфавит, длину или границы кодовых слов и таблицу соответствий. Затем последовательность читают в установленном порядке и заменяют каждое кодовое слово исходным символом.
Для фиксированной длины алгоритм прост: отсчитать слева \(L\) знаков, найти такую комбинацию в таблице, записать соответствующий символ и перейти к следующей группе. Нельзя менять порядок групп или пропускать ведущие нули: комбинации 01 и 1 могут обозначать разные символы.
Дан двоичный код фиксированной длины 3. Таблица: А — 000, Б — 001, В — 010, Г — 011, Д — 100, Е — 101, Ж — 110, З — 111. Декодируем сообщение 001010111.
Если длина сообщения не делится на длину кодового слова, значит, либо последовательность записана с ошибкой, либо код использует другой способ разделения. В переменном коде читают слева направо и каждый раз выбирают кодовое слово, которое начинается с текущей позиции. Для префиксного кода такой выбор однозначен.
Количество информации и длина кода
При равновероятных вариантах количество информации в одном символе алфавита зависит от мощности алфавита. Если алфавит содержит \(N\) равновероятных символов, информационный вес одного символа равен:
Если сообщение состоит из \(L\) символов такого алфавита, его информационный объём равен \(I=L\log_2N\). Для двоичного алфавита \(N=2\), поэтому один знак содержит один бит. Подробные задачи на равновероятные события разобраны на странице количество информации при равновероятных событиях. Если вероятности различаются, используют другой подход — количество информации при неравновероятных событиях.
Для хранения одного символа из \(N\) вариантов требуется столько двоичных разрядов, чтобы кодовых комбинаций хватило для всех символов. При фиксированной длине \(L\) должно выполняться \(2^L\ge N\). Минимальное подходящее \(L\) находят перебором степеней двойки или округлением вверх числа \(\log_2N\).
1. Путают мощность исходного алфавита и кодового алфавита. В формуле \(K^L\) используется число знаков кодового алфавита. 2. Забывают ведущие нули в двоичных группах. 3. При декодировании читают комбинации справа налево или меняют их порядок. 4. Считают, что код всегда обязан быть двоичным: это неверно, кодовый алфавит может содержать любое удобное число знаков. 5. Используют формулу \(2^L\) для переменного кода без учёта его структуры.
Если в условии дана таблица и длинная строка, сначала подчеркните границы кодовых слов. Если длина фиксирована, поставьте разделители через каждые \(L\) знаков. Затем проверяйте каждую группу отдельно и только после этого записывайте итоговое сообщение.
Быстрая проверка
Проверьте понимание темы
Главное
- Кодирование переводит сообщение в другую форму с помощью выбранного алфавита и правил.
- Число комбинаций длины \(L\) над алфавитом из \(K\) знаков равно \(K^L\).
- Для однозначного декодирования каждой допустимой кодовой последовательности должно соответствовать единственное исходное сообщение.
- В фиксированном коде границы слов определяются длиной; в переменном коде нужны правила, например префиксность.
- Для \(N\) символов минимальная длина двоичного фиксированного кода определяется условием \(2^L\ge N\).