Self-synchronizing code: Difference between revisions
imported>Kvng m avoid unnec redirect |
imported>Doczilla m Removing link(s) because Wikipedia:Articles for deletion/Code word (communication) closed as delete (XFDcloser) |
||
| Line 5: | Line 5: | ||
{{Distinguish|Self-clocking signal|Self-similar process}} | {{Distinguish|Self-clocking signal|Self-similar process}} | ||
In [[coding theory]], especially in [[telecommunications]], a '''self-synchronizing code''' is a [[uniquely decodable code]] in which the [[symbol (data)|symbol]] stream formed by a portion of one | In [[coding theory]], especially in [[telecommunications]], a '''self-synchronizing code''' is a [[uniquely decodable code]] in which the [[symbol (data)|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.<ref name="Glossary"/> 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'''<ref name="Brestel-Perrin-Reutenauer_2010"/> or, ambiguously, '''comma-free code'''.<ref name="Brestel-Perrin_1985"/> A self-synchronizing code permits the proper [[frame synchronization|framing]] of transmitted code words provided that no uncorrected errors occur in the [[data stream|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 [[data corruption|corrupted]]. | Other terms for self-synchronizing code are '''synchronized code'''<ref name="Brestel-Perrin-Reutenauer_2010"/> or, ambiguously, '''comma-free code'''.<ref name="Brestel-Perrin_1985"/> A self-synchronizing code permits the proper [[frame synchronization|framing]] of transmitted code words provided that no uncorrected errors occur in the [[data stream|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 [[data corruption|corrupted]]. | ||
Latest revision as of 06:37, 5 July 2026
Template:Use American English Template:Short description Script error: No such module "Unsubst". Template:Use list-defined references Script error: No such module "Distinguish".
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.
Examples
- 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 {00, 11} is not self-synchronizing; while 0, 1, 01 and 10 are not codes, 00 and 11 are.
- 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
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".
Further reading
- Script error: No such module "citation/CS1".
- MIL-STD-188