Self-synchronizing code

Short description: Type of code in coding theory

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.

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.

## Contents

* 1 Examples
* 2 See also
* 3 References
* 4 Further reading

## Examples

* The prefix code {00, 11} is self-synchronizing because 0, 1, 01 and 10 are not codes.[clarification needed]
* UTF-8 is self-synchronizing because the leading byte (`11xxxxxx`) and subsequent bytes (`10xxxxxx`) of a multi-byte code point have different bit patterns.
* High Level Data Link Control (HDLC)
* Advanced Data Communication Control Procedures (ADCCP)
* Fibonacci coding

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 a) because code word ba contains code word a.

## See also

* Bit slip
* Comma code
* Consistent overhead byte stuffing
* Dynkin sequence
* Kraus principle
* Kruskal's principle
* Overlapping instructions
* Pollard's lambda method
* Self-clocking signal
* Self-synchronizing block code

## References

1. ↑ "Self-synchronizing code – Glossary". https://glossary.atis.org/glossary/self-synchronizing-code/?char=S&page_number=22&sort=ASC.
2. ↑ Codes and automata. Encyclopedia of Mathematics and its Applications. 129. Cambridge, UK: Cambridge University Press. 2010. p. 137. ISBN 978-0-521-88831-8.
3. ↑ Theory of Codes. Pure and Applied Mathematics. 117. Academic Press. 1985. p. 377.

## Further reading

* "self-synchronizing code". Federal Standard 1037C: Telecommunications: Glossary of Telecommunication Terms. General Services Administration. 1996-08-06. https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm.
* MIL-STD-188

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Self-synchronizing code. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Self-synchronizing_code&oldid=307553"