Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Например, код с кодовыми словами {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 битов может кодировать до исходных символов.

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

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

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

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

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

Понятия, связанные с данным [ править ]

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

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

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

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

Методы [ править ]

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

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

Заметки [ править ]

  1. ^ Федеральный стандарт США 1037C
  2. ^ АТИС Telecom Глоссарий 2007 , извлекаться декабря +4, 2010
  3. ^ Berstel, Жан; Перрен, Доминик (1985), Теория кодов , Academic Press
  4. ^ Голомб, SW ; Гордон, Бэзил ; Welch, LR (1958), "Comma-Free Codes" , Canadian Journal математики , 10 (2): 202-209, DOI : 10,4153 / CJM-1958-023-9
  5. ^ Le Boudec, Жан-Ив, Патрик Thiran и Рюдигер Urbanke. Введение в науку об информации: энтропия, сжатие, искажение и исправление ошибок. ППУР Прессы политехнические, 2015.
  6. ^ Berstelдр (2010) с.75
  7. ^ "Разработка триггерных и управляющих систем для CMS" Дж. А. Джонсом: "Синхронизация" стр. 70
  8. ^ Berstelдр (2010) стр.58
  9. ^ McGill COMP 423 Конспекты лекций
  10. ^ Пайк, Роб (2003-04-03). «История UTF-8» .
  11. ^ Шевчук, Ю. В. (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. 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