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: ```print "Hacked with Python 2 or Lua"```
gollark: (produced by the common Unix tool `haxxdump`)
gollark: 011d3b0 ecda fe42 f33d d112 2b8c 7e1d 24d2 11e5011d3c0 2475 ae6a bb0f 0c59 592b 3e75 6074 5f61011d3d0 ff42 a907 c773 c81f 3095 97ba 7fe2 5270011d3e0 c021 d886 1dfc 01eb f22a 0174 38cb ab3e011d3f0 2476 6efa 2bb0 6dde cd92 0222 5467 7221011d400 bb13 2647 77f7 8c51 6206 e40d 3c85 117c011d410 86bb 928f 2234 bb31 298e dd89 7209 6a00011d420 49b1 182b 52fc 6659 f720 c14c 7064 213c011d430 be13 5b7f 36db 9228 232a be39 1c9e 4065011d440 3e92 3fa8 a538 8a60 c599 7c88 9f72 9748011d450 8a5d fc83 b21b e48d 666a 8670 3d61 0225
gollark: I have made many a useless side project.
gollark: I mean, there's a difference between programming and, say, sysadmin stuff, but yes.

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.