Префиксный код
Тип кодовой системы

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

Например, код с кодом {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 к {\displaystyle 2^{k}}

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

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

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

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

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

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

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

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

Методы

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

Примечания

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

Ссылки

  • Коды, деревья и свойство префикса Коны Макфи
Получено с "https://en.wikipedia.org/w/index.php?title=Prefix_code&oldid=1248191728"