Код префикса - Prefix code

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

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

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

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

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

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

Методы

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

• Дельта-кодирование Элиаса
• Гамма-кодирование Элиаса
• Кодирование Элиаса Омеги
• Кодирование Фибоначчи
• Кодирование Левенштейна
• Унарное кодирование
• Код Голомба Риса
• Скользящая шахматная доска (простой метод криптографии, который производит префиксные коды)
• Двоичное кодирование

Заметки

Рекомендации

• Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. 129 . Кембридж: Издательство Кембриджского университета . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Элиас, Питер (1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Trans. Инф. Теория . 21 (2): 194–203. DOI : 10,1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   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» .

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

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