WikiDer > Код префикса

Prefix code

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

Например, код с кодовыми словами {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 и наборы инструкций (машинный язык) большинства компьютерных микроархитектур - это префиксные коды.

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

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

Методы

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

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

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

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

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

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

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

А суффиксный код это набор слов, ни одно из которых не является суффиксом другого; эквивалентно, набор слов, противоположных префиксному коду. Как и в случае с префиксным кодом, представление строки как конкатенации таких слов уникально. А бификс-код представляет собой набор слов, который является одновременно префиксом и суффиксным кодом.[8]An оптимальный префиксный код - это префиксный код с минимальной средней длиной. То есть предположим, что в алфавите п символы с вероятностями для кода префикса C. Если C ' это еще один префиксный код и длины кодовых слов C ', тогда .[9]

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

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

Методы

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

Заметки

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

использованная литература

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