Префиксный код

Префиксный код - это тип кодовой системы, отличающийся наличием «свойства префикса», которое требует, чтобы не было целого кодового слова в системе , которое было бы префиксом (начальным сегментом) любого другого кодового слова в системе. Это тривиально верно для кодов фиксированной длины, поэтому следует учитывать только коды переменной длины .

Например, код с кодовыми словами {9, 55} имеет свойство префикса; код, состоящий из {9, 5, 59, 55}, этого не делает, поскольку «5» является префиксом «59», а также «55». Префиксный код — это однозначно декодируемый код : при наличии полной и точной последовательности получатель может идентифицировать каждое слово, не требуя специального маркера между словами. Однако существуют однозначно декодируемые коды, которые не являются префиксными кодами; например, обратная сторона префиксного кода по-прежнему однозначно декодируется (это суффиксный код), но это не обязательно префиксный код.

Префиксные коды также известны как коды без префиксов , коды условий с префиксами и мгновенные коды . Хотя кодирование Хаффмана является лишь одним из многих алгоритмов получения префиксных кодов, префиксные коды также широко называют «кодами Хаффмана», даже если код не был создан с помощью алгоритма Хаффмана. Термин «код без запятых» иногда также применяется как синоним кодов без префиксов. ^[1]^[2] но в большинстве математических книг и статей (например, ^[3]^[4]) код без запятой используется для обозначения самосинхронизирующегося кода , подкласса префиксных кодов.

Используя префиксные коды, сообщение может передаваться как последовательность объединенных кодовых слов без каких-либо внеполосных маркеров или (альтернативно) специальных маркеров между словами для обрамления слов в сообщении. Получатель может однозначно декодировать сообщение, неоднократно находя и удаляя последовательности, образующие действительные кодовые слова. Обычно это невозможно с кодами, у которых отсутствует свойство префикса, например {0, 1, 10, 11}: получатель, читающий «1» в начале кодового слова, не будет знать, было ли это полное кодовое слово». 1» или просто префикс кодового слова «10» или «11»; поэтому строку «10» можно интерпретировать либо как одно кодовое слово, либо как объединение слов «1», а затем «0».

переменной длины Коды Хаффмана , телефонные коды страны страны и издателя , части ISBN , вторичные коды синхронизации, используемые в стандарте беспроводной связи UMTS W-CDMA 3G, а также наборы команд (машинный язык) большинства компьютерных микроархитектур являются префиксными кодами.

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

Для любого однозначно декодируемого кода существует префиксный код, имеющий ту же длину кодового слова. ^[5] Неравенство Крафта характеризует наборы длин кодовых слов, которые возможны в однозначно декодируемом коде. ^[6]

Техники

Если все слова в коде имеют одинаковую длину, код называется кодом фиксированной длины или блочным кодом (хотя термин «блочный код» также используется для кодов исправления ошибок фиксированного размера в канальном кодировании ). Например, буквы ISO 8859-15 всегда имеют длину 8 бит. UTF-32/UCS-4 Буквы всегда имеют длину 32 бита. Ячейки ATM всегда имеют длину 424 бита (53 байта). Код фиксированной длины из k бит фиксированной длины может кодировать до $2^{k}$ исходные символы.

Код фиксированной длины обязательно является префиксным кодом. Любой код можно превратить в код фиксированной длины, добавив фиксированные символы к более коротким префиксам, чтобы обеспечить длину самых длинных префиксов. Альтернативно, такие коды заполнения могут использоваться для введения избыточности, которая обеспечивает автокоррекцию и/или синхронизацию. Однако кодирование фиксированной длины неэффективно в ситуациях, когда вероятность передачи одних слов гораздо выше, чем других.

Усеченное двоичное кодирование — это прямое обобщение кодов фиксированной длины для случаев, когда количество символов n не является степенью двойки. Исходным символам присваиваются кодовые слова длины k и k +1, где k выбирается так, чтобы 2 ^к < п ≤ 2 ^к+1.

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

Некоторые коды отмечают конец кодового слова специальным символом «запятая» (также называемым значением Sentinel ), отличным от обычных данных. ^[7] Это в некоторой степени аналогично пробелам между словами в предложении; они отмечают, где заканчивается одно слово и начинается другое. Если каждое кодовое слово заканчивается запятой и запятая не встречается где-либо еще в кодовом слове, код автоматически не содержит префиксов. Однако резервирование целого символа только для использования в качестве запятой может быть неэффективным, особенно для языков с небольшим количеством символов. Код Морзе — это повседневный пример кода переменной длины с запятой. Длинные паузы между буквами и еще более длинные паузы между словами помогают людям распознавать, где заканчивается одна буква (или слово) и начинается следующая. Точно так же кодирование Фибоначчи использует цифру «11» для обозначения конца каждого кодового слова.

Самосинхронизирующиеся коды — это префиксные коды, которые позволяют синхронизировать кадры .

Связанные понятия

Суффиксный код — это набор слов, ни одно из которых не является суффиксом другого; эквивалентно, набор слов, которые являются обратными префиксному коду. Как и в случае с префиксным кодом, представление строки в виде конкатенации таких слов является уникальным. Бификсный код — это набор слов, который является одновременно префиксным и суффиксным кодом. ^[8]Оптимальный префиксный код — это префиксный код с минимальной средней длиной. То есть предположим, что алфавит из $n$ символов с вероятностями $p(A_{i})$ для префиксного $C.$ кода Если $C'$ — другой префиксный код и $\lambda '_{i}$ — длины кодовых слов $C'$ , тогда $\sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!$ . ^[9]

Коды префиксов, используемые сегодня

Примеры префиксных кодов включают:

переменной длины коды Хаффмана
телефонные коды страны
Кодирование Чена – Хо
страны и издателя часть ISBN
Вторичные коды синхронизации, используемые в UMTS W-CDMA 3G. стандарте беспроводной связи
Коды видеомагнитофона Plus+
Формат преобразования Unicode , в частности система UTF-8 для кодирования символов Unicode , которая представляет собой одновременно код без префиксов и самосинхронизирующийся код. ^[10]
количество переменной длины

Техники

Обычно используемые методы построения префиксных кодов включают коды Хаффмана и более ранние коды Шеннона-Фано , а также универсальные коды, такие как:

Дельта-кодирование Элиаса
Гамма-кодирование Элиаса
Элиас омега-кодирование
Кодирование Фибоначчи
Кодирование Левенштейна
Унарное кодирование
Код Голомба Райса
Перемежающаяся шахматная доска (простая техника криптографии, создающая префиксные коды)
двоичное кодирование ^[11]

Примечания

^ Федеральный стандарт США 1037C
^ ATIS Telecom Glossary 2007 , заархивировано из оригинала 8 июля 2010 г. , получено 4 декабря 2010 г.
^ Берстель, Жан; Перрен, Доминик (1985), Теория кодов , Academic Press
^ Голомб, SW ; Гордон, Бэзил ; Уэлч, Л.Р. (1958), «Коды без запятых» , Canadian Journal of Mathematics , 10 (2): 202–209, doi : 10.4153/CJM-1958-023-9 , S2CID 124092269
^ Ле Будек, Жан-Ив, Патрик Тиран и Рюдигер Урбанке. Введение в информатику: энтропия, сжатие, шифрование и исправление ошибок. ППУР Прессы политехника, 2015.
^ Берстель и др. (2010) стр.75
^ А. Джонс, Дж. «Разработка систем запуска и управления для CMS» (PDF) . Физика высоких энергий, Лаборатория Блэкетта, Имперский колледж, Лондон. п. 70. Архивировано из оригинала (PDF) 13 июня 2011 г.
^ Берстель и др. (2010) стр.58
^ McGill COMP 423 Конспекты лекций
^ Пайк, Роб (3 апреля 2003 г.). «История UTF-8» .
^ Шевчук, Ю.В. (2018), «Vbinary: новый взгляд на целочисленное кодирование переменной длины» (PDF) , Программные системы: теория и приложения , 9 (4): 239–252, doi : 10.25209/2079-3316-2018-9-4- 239-252

Ссылки

Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. Том. 129. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-88831-8 . Збл 1187.94001 .
Элиас, Питер (1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Транс. Инф. Теория . 21 (2): 194–203. дои : 10.1109/тит.1975.1055349 . ISSN 0018-9448 . Збл 0298.94011 .
Д. А. Хаффман, «Метод построения кодов с минимальной избыточностью», Труды IRE, сентябрь 1952 г., стр. 1098–1102 (оригинальная статья Хаффмана).
Профиль: Дэвид А. Хаффман , Scientific American , сентябрь 1991 г., стр. 54–58 (предыстория).
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 16.3, стр. 385–392.
В этой статье использованы общедоступные материалы из Федеральный стандарт 1037C . Управление общего обслуживания . Архивировано из оригинала 22 января 2022 г.

Внешние ссылки

Коды, деревья и свойство префикса от Kona Macphee

[1] Федеральный стандарт США 1037C

[2] ATIS Telecom Glossary 2007 , заархивировано из оригинала 8 июля 2010 г. , получено 4 декабря 2010 г.

[3] Берстель, Жан; Перрен, Доминик (1985), Теория кодов , Academic Press

[4] Голомб, SW ; Гордон, Бэзил ; Уэлч, Л.Р. (1958), «Коды без запятых» , Canadian Journal of Mathematics , 10 (2): 202–209, doi : 10.4153/CJM-1958-023-9 , S2CID 124092269

[LTU2015-5] Ле Будек, Жан-Ив, Патрик Тиран и Рюдигер Урбанке. Введение в информатику: энтропия, сжатие, шифрование и исправление ошибок. ППУР Прессы политехника, 2015.

[BRS75-6] Берстель и др. (2010) стр.75

[7] А. Джонс, Дж. «Разработка систем запуска и управления для CMS» (PDF) . Физика высоких энергий, Лаборатория Блэкетта, Имперский колледж, Лондон. п. 70. Архивировано из оригинала (PDF) 13 июня 2011 г.

[BPR58-8] Берстель и др. (2010) стр.58

[9] McGill COMP 423 Конспекты лекций

[10] Пайк, Роб (3 апреля 2003 г.). «История UTF-8» .

[11] Шевчук, Ю.В. (2018), «Vbinary: новый взгляд на целочисленное кодирование переменной длины» (PDF) , Программные системы: теория и приложения , 9 (4): 239–252, doi : 10.25209/2079-3316-2018-9-4- 239-252

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]