Код переменной длины

В теории кодирования код переменной длиной является кодом , который отображает исходные символы в переменном количество бит.

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

Некоторые примеры стратегий кодирования хорошо известны переменной длины являются кодирования по алгоритму Хаффмана , Лемпеля-Зив кодирования , арифметическое кодирование и кодирование контекстно-адаптивное переменной длины .

Коды и их расширения [ править ]

Расширение кода - это отображение исходных последовательностей конечной длины в битовые строки конечной длины, которое получается путем конкатенации для каждого символа исходной последовательности соответствующего кодового слова, созданного исходным кодом.

Используя термины из теории формального языка , точное математическое определение выглядит следующим образом: Пусть и будет двумя конечными наборами, называемыми исходным и целевым алфавитами , соответственно. Код является полной функцией ^[1] отображение каждого символа из к последовательности символов более , и расширение до гомоморфизма из в , что , естественно , отображает каждую последовательность исходных символов в последовательность целевых символов, называют его расширение . ${\ displaystyle S}$ ${\ displaystyle T}$ $C:S\to T^{*}$ $S$ $T$ $C$ $S^{*}$ $T^{*}$

Классы кодов переменной длины [ править ]

Коды переменной длины могут быть строго вложены в порядке уменьшения общности как неособые коды, однозначно декодируемые коды и префиксные коды. Коды префиксов всегда однозначно декодируются, а они, в свою очередь, всегда неособые:

Неособые коды [ править ]

Код не является сингулярным, если каждый исходный символ отображается в другую непустую битовую строку, т. Е. Отображение исходных символов в битовые строки является инъективным .

Например, отображение является не несингулярным , потому что оба «а» и «б» карта для одной и той же битовой строки «0»; любое расширение этого сопоставления будет генерировать кодирование с потерями (без потерь). Такое сингулярное кодирование все еще может быть полезным, когда допустима некоторая потеря информации (например, когда такой код используется при сжатии аудио или видео, где кодирование с потерями становится эквивалентным квантованию источника ). $M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}$
Однако отображение неособое; его расширение будет генерировать кодирование без потерь, которое будет полезно для общей передачи данных (но эта функция не всегда требуется). Обратите внимание, что необязательно, чтобы неособый код был более компактным, чем исходный (и во многих приложениях полезен более крупный код, например, как способ обнаружения и / или восстановления после ошибок кодирования или передачи, или в приложения безопасности для защиты источника от несанкционированного доступа). $M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}$

Уникально декодируемые коды [ править ]

Код однозначно декодируем, если его расширение неособо (см. Выше). Можно ли решить, является ли данный код однозначно декодируемым, с помощью алгоритма Сардинаса – Паттерсона .

Отображение однозначно декодируется (это можно продемонстрировать, посмотрев на следующий набор после каждой целевой битовой строки на карте, потому что каждая битовая цепочка завершается, как только мы видим бит 0, который не может следовать за любым существующим кодом для создания более действительного код на карте, но однозначно запускает новый код). $M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}$
Снова рассмотрим код из предыдущего раздела. ^[1] Этот код нельзя однозначно декодировать, поскольку строку 011101110011 можно интерпретировать как последовательность кодовых слов 01110–1110–011 , но также как последовательность кодовых слов 011–1–011–10011 . Таким образом, cdb и babe дают два возможных декодирования этой закодированной строки. $M_{2}$ . Однако такой код полезен, когда набор всех возможных исходных символов полностью известен и конечен, или когда есть ограничения (например, формальный синтаксис), которые определяют, приемлемы ли исходные элементы этого расширения. Такие ограничения позволяют декодировать исходное сообщение, проверяя, какие из возможных исходных символов, сопоставленных с одним и тем же символом, действительны в соответствии с этими ограничениями.

Коды префиксов [ править ]

Код - это код префикса, если целевая битовая строка в отображении не является префиксом целевой битовой строки другого исходного символа в том же отображении. Это означает, что символы могут быть декодированы мгновенно после того, как будет получено их полное кодовое слово. Другие часто используемые названия этой концепции - это код без префиксов , мгновенный код или контекстно-свободный код .

Пример сопоставления в предыдущем абзаце не является префиксным кодом, потому что после чтения битовой строки «0» мы не знаем, кодирует ли она исходный символ «a» или является ли это префиксом кодировки «b». или символы "c". $M_{3}$
Пример кода префикса показан ниже.

Символ	Кодовое слово
а	0
б	10
c	110
d	111

Пример кодирования и декодирования:

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab

Частным случаем префиксных кодов являются блочные коды . Здесь все кодовые слова должны иметь одинаковую длину. Последние не очень полезны в контексте кодирования источника , но часто служат кодами с исправлением ошибок в контексте кодирования канала .

Другой частный случай префиксных кодов - это количественные коды переменной длины , которые кодируют произвольно большие целые числа как последовательность октетов, т. Е. Каждое кодовое слово кратно 8 битам.

Преимущества [ править ]

Преимущество кода переменной длины состоит в том, что маловероятным исходным символам могут быть назначены более длинные кодовые слова, а вероятным исходным символам могут быть назначены более короткие кодовые слова, что дает низкую ожидаемую длину кодового слова. Для приведенного выше примера, если бы вероятности (a, b, c, d) были равны , ожидаемое количество битов, используемых для представления исходного символа с использованием приведенного выше кода, было бы: $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

Поскольку энтропия этого источника составляет 1,7500 бит на символ, этот код максимально сжимает источник, чтобы его можно было восстановить с нулевой ошибкой.

Заметки [ править ]

^ a b Этот код основан на примере, найденном в Berstel et al. (2009), Пример 2.3.1, стр. 63.

Ссылки [ править ]

Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. 129 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-88831-8. Zbl 1187.94001 . Черновик доступен онлайн

[:0-1] Этот код основан на примере, найденном в Berstel et al. (2009), Пример 2.3.1, стр. 63.

[1]