Код префикса

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

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

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

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

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

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

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

• 1 Методы
• 2 Понятия, связанные с данным
• 3 Префиксные коды, используемые сегодня
  • 3.1 Методы
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

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

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

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

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

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

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

A суффикс-код - это набор слов, ни одно из которых не является суффиксом другого; эквивалентно, набор слов, которые являются обратным префиксному коду. Как и в случае с префиксным кодом, представление строки как конкатенации таких слов уникально. Двойной код - это набор слов, который одновременно является префиксом и суффиксом. Оптимальный префиксный код - это префиксный код с минимальной средней длиной. То есть предположим, что для кода префикса C используется алфавит из n символов с вероятностями $p\; (A\; i)\; \{\backslash \; displaystyle\; p\; (A\_\; \{i\})\}$. Если C '- другой код префикса и $\lambda \; i\; \prime \; \{\backslash \; displaystyle\; \backslash \; lambda\; \text{'}\_\; \{i\}\}$- длины кодовых слов C', тогда $\sum \; i\; =\; 1\; n\; \lambda \; ip\; (A\; i)\; \le \; \sum \; я\; знак\; равно\; 1\; N\; \lambda \; я\; \text{'}п\; (A\; я)\; \{\backslash \; Displaystyle\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{n\}\; \{\backslash \; лямбда\; \_\; \{я\}\; р\; (A\_\; \{я\})\}\; \backslash \; Leq\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{n\}\; \{\backslash \; lambda\; \text{'}\_\; \{i\}\; p\; (A\_\; \{i\})\}\; \backslash !\}$.

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

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

Методы

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

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

• Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы. Энциклопедия математики и ее приложений. 129 . Кембридж: Cambridge University Press. 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