Jump to content

Префиксный код

(Перенаправлено с кода фиксированной длины )

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

Например, код с кодовыми словами {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 к < п ≤ 2 к+1 .

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

Примечания

[ редактировать ]
  1. ^ Федеральный стандарт США 1037C
  2. ^ ATIS Telecom Glossary 2007 , архивировано из оригинала 8 июля 2010 г. , получено 4 декабря 2010 г.
  3. ^ Берстель, Жан; Перрен, Доминик (1985), Теория кодов , Academic Press
  4. ^ Голомб, SW ; Гордон, Бэзил ; Уэлч, Л.Р. (1958), «Коды без запятых» , Canadian Journal of Mathematics , 10 (2): 202–209, doi : 10.4153/CJM-1958-023-9 , S2CID   124092269
  5. ^ Ле Будек, Жан-Ив, Патрик Тиран и Рюдигер Урбанке. Введение в информатику: энтропия, сжатие, шифрование и исправление ошибок. ППУР Прессы политехника, 2015.
  6. ^ Берстель и др. (2010) стр.75
  7. ^ А. Джонс, Дж. «Разработка систем запуска и управления для CMS» (PDF) . Физика высоких энергий, Лаборатория Блэкетта, Имперский колледж, Лондон. п. 70. Архивировано из оригинала (PDF) 13 июня 2011 г.
  8. ^ Берстель и др. (2010) стр.58
  9. ^ McGill COMP 423 Конспекты лекций
  10. ^ Пайк, Роб (3 апреля 2003 г.). «История UTF-8» .
  11. ^ Шевчук, Ю.В. (2018), «Vbinary: новый взгляд на целочисленное кодирование переменной длины» (PDF) , Программные системы: теория и приложения , 9 (4): 239–252, doi : 10.25209/2079-3316-2018-9-4- 239-252
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: fb4f329e4181b9292560ea0fe7280d36__1718887440
URL1:https://arc.ask3.ru/arc/aa/fb/36/fb4f329e4181b9292560ea0fe7280d36.html
Заголовок, (Title) документа по адресу, URL1:
Prefix code - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)