Самосинхронизирующийся код
В теории кодирования , особенно в телекоммуникациях , самосинхронизирующийся код — это однозначно декодируемый код , в котором поток символов , сформированный частью одного кодового слова или перекрывающейся частью любых двух соседних кодовых слов, не является допустимым кодовым словом. . [1] Другими словами, набор строк (называемых «кодовыми словами») в алфавите называется самосинхронизирующимся кодом, если для каждой строки, полученной путем объединения двух кодовых слов, подстрока начинается со второго символа и заканчивается предпоследним символом. символ не содержит кодового слова в качестве подстроки. Каждый самосинхронизирующийся код является префиксным кодом , но не все префиксные коды являются самосинхронизирующими.
Другие термины для самосинхронизирующегося кода — синхронизированный код. [2] или, что неоднозначно, код без запятых . [3] Самосинхронизирующийся код позволяет правильно формировать передаваемые кодовые слова при условии, что в потоке символов не возникает неисправленных ошибок ; внешняя синхронизация не требуется. Самосинхронизирующиеся коды также позволяют выполнять восстановление после неисправленных ошибок в потоке; в большинстве префиксных кодов неисправленная ошибка в одном бите может распространить ошибки дальше в потоке и привести к повреждению последующих данных .
Важность самосинхронизирующихся кодов не ограничивается передачей данных . Самосинхронизация также облегчает некоторые случаи восстановления данных , например, текста, закодированного в цифровой форме .
Примеры [ править ]
- UTF-8 является самосинхронизирующимся, поскольку ведущий байт (
11xxxxxx) и последующие байты (10xxxxxx) многобайтовой кодовой точки имеют разные битовые комбинации. - Управление каналом передачи данных высокого уровня (HDLC)
- Процедуры расширенного управления передачей данных (ADCCP)
- Кодирование Фибоначчи
Контрпримеры:
- Префиксный код {00, 11} не является самосинхронизирующимся; 0, 1, 01 и 10 не являются кодами, а 00 и 11 — таковыми.
- Префиксный код { ab , ba } не является самосинхронизирующимся, поскольку abab содержит ba .
- Префиксный код b ∗ a (с использованием звезды Клини ) не является самосинхронизирующимся (даже если любое новое кодовое слово просто начинается после a ), поскольку кодовое слово ba содержит кодовое слово a .
См. также [ править ]
- Проскальзывание бита
- Код запятой
- Последовательное заполнение служебных байтов
- последовательность Дынкина
- Принцип Крауса
- Принцип Краскала
- Перекрывающиеся инструкции
- Лямбда-метод Полларда
- Сигнал самосинхронизации
- Самосинхронизирующийся блочный код
Ссылки [ править ]
- ^ «Самосинхронизирующийся код – Глоссарий» .
- ^ Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. Том. 129. Кембридж, Великобритания: Издательство Кембриджского университета . п. 137. ИСБН 978-0-521-88831-8 . Збл 1187.94001 .
- ^ Берстель, Жан; Перрен, Доминик (1985). Теория кодов . Чистая и прикладная математика. Том. 117. Академическая пресса . п. 377. Збл 0587.68066 .
Дальнейшее чтение [ править ]
- «самосинхронизирующийся код» . Федеральный стандарт 1037C: Телекоммуникации: Глоссарий телекоммуникационных терминов . Управление общего обслуживания . 06.08.1996. Архивировано из оригинала 22 января 2022 г.
- МИЛ-СТД-188