Self-synchronizing code

In coding theory, especially in telecommunications, a self-synchronizing code is a uniquely decodable code in which the symbol stream formed by a portion of one code word, or by the overlapped portion of any two adjacent code words, is not a valid code word.[1] Put another way, a set of strings (called "code words") over an alphabet is called a self-synchronizing code if for each string obtained by concatenating two code words, the substring starting at the second symbol and ending at the second-last symbol does not contain any code word as substring. Every self-synchronizing code is a prefix code, but not all prefix codes are self-synchronizing.

Not to be confused with self-clocking signal.

Other terms for self-synchronizing code are synchronized code[2] or, ambiguously, comma-free code.[3] A self-synchronizing code permits the proper framing of transmitted code words provided that no uncorrected errors occur in the symbol stream; external synchronization is not required. Self-synchronizing codes also allow recovery from uncorrected errors in the stream; with most prefix codes, an uncorrected error in a single bit may propagate errors further in the stream and make the subsequent data corrupted.

Importance of self-synchronizing codes is not limited to data transmission. Self-synchronization also facilitates some cases of data recovery, for example of a digitally encoded text.

Examples

Counterexamples:

  • The prefix code {ab,ba} is not self-synchronizing because abab contains ba.
  • The prefix code b∗a (using the Kleene star) is not self-synchronizing (even though any new code word simply starts after een a) because code word ba contains code word a.

Note

In UTF-8, bit patterns 0xxxxxxx and 11xxxxxx are used to mark the beginning of the next valid character

gollark: I see. Hmm.
gollark: How is that relevant?
gollark: YET.
gollark: But palaiologos is not always on voice VC chat.
gollark: I mean, if we knew it was exactly a second you could just do that, but it might be NOT a second.

See also

References
  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
  • Berstel, Jean; Perrin, Dominique (1985), Theory of Codes, Pure and Applied Mathematics, 117, Academic Press, Zbl 0587.68066
  • Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.
  •  This article incorporates public domain material from the General Services Administration document: "Federal Standard 1037C". (in support of MIL-STD-188)


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.