Samosynchronizační kód

Samosynchronizační kód je v teorii kódování a v telekomunikacích takový jednoznačně dekódovatelný kód, že žádná vlastní část kódového slova ani datový proud, v němž se části sousedních kódových slov překrývají, netvoří jiné nebo jinak umístěné kódové slovo.[1] Jinak řečeno, množina kódových slov nad určitou abecedou tvoří samosynchronizační kód, jestliže žádný vlastní podřetězec libovolného řetězce získaného zřetězením libovolných dvou kódových slov netvoří jiné nebo jinak umístěné kódové slovo. Každý samosynchronizační kód je prefixový kód, ale ne všechny prefixové kódy jsou samosynchronizační.

V angličtině se samosynchronizační kód nazývá self-synchronizing code, synchronized code nebo comma-free code[2][3]. Samosynchronizační kód umožňuje rámcovou synchronizaci přenášených kódových slov bez externí synchronizace za předpokladu, že se v proudu symbolů neobjeví žádné neopravené chyby. Samosynchronizační kódy také umožňuje zotavení z neopravených chyby v datovém proudu; u většiny prefixových kódů se neopravená chyba v jediném bitu může šířit do dalších symbolů v datovém proudu a poškozovat následující data.

Význam samosynchronizačních kódů není omezen na přenos dat. Samosynchronizace je použitelná také pro záchranu dat, například digitálně kódovaného textu.

Příklady

Protipříklady:

  • Prefixový kód {ab,ba} není samosynchronizační, protože abab obsahuje ba.
  • Prefixový kód b∗a (zapsaný pomocí Kleeneho hvězdičky) není samosynchronizační (přestože jakékoli nové kódové slovo jednoduše začíná po symbolu a) protože kódové slovo ba obsahuje kódové slovo a.

Poznámka

V kódování UTF-8 se používají bajty s bitovými vzorky 0xxxxxxx a 11xxxxxx pro označení začátku dalšího povoleného znaku.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Self-synchronizing code na anglické Wikipedii. Tento článek obsahuje volně šiřitelné materiály z dokumentu General Services Administration podle Federal Standard 1037C a MIL-STD-188.

  1. ↑ https://glossary.atis.org/glossary/self-synchronizing-code/?char=S&page_number=22&sort=ASC
  2. ↑ Berstel et al (2010) p. 137
  3. ↑ Berstel & Perrin (1985) p. 377

Literatura

  • BERSTEL, Jean; PERRIN, Dominique. Theory of Codes. [s.l.]: Academic Press, 1985. (Pure and Applied Mathematics). 
  • BERSTEL, Jean; PERRIN, Dominique; REUTENAUER, Christophe. Codes and automata. Cambridge: Cambridge University Press, 2010. (Encyclopedia of Mathematics and its Applications). ISBN 978-0-521-88831-8. 

Související články