“Self-synchronizing code”的意思、由来-开放百科全书

词条 Self-synchronizing code

释义

Synchronizing word
Examples
Examples
See also
References

{{Use American English|date = March 2019}}{{Short description|Type of code in coding theory}}{{Use mdy dates|date = March 2019}}{{distinguish|self-clocking signal}}

In coding theory, especially in telecommunications, a self-synchronizing code^[1] 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. 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.

Synchronizing word

A code {{mvar|X}} over an alphabet {{mvar|A}} has a synchronizing word (aka "syncword") {{mvar|w}} in {{math|A⁺}} if

{{math|size=120%| x w y ∈ X^* ⇒ {{ns:0| this probably means that both words xw and wy are accepted}} {x w, w y} ⊆ X^* }}.^[2]{{clarify|date=February 2014}}

A prefix code is synchronized if and only if it has a synchronizing word.^[4]{{clarify|abab contains ba|date=February 2014}}

Examples

The prefix code {ab,ba} has abba as a synchronizing word.^[4]
The prefix code b^∗a has a as a synchronizing word.^[4]
The code 1100001100 produced by the words {11, 00}. The code can be represented by 11 00 00 11 00, with spaces added to show the different words (they are not really in the code).
Let's now assume that four letters (two code words) are read. The code 1000 is not a valid code, because 10 is not one of the two code words defined. Similarly, 0001. Even though 00 is a valid word, 01 is not. The only valid way to read two valid words from the example given is by starting at the very beginning, or just after one of the spaces (which have been inserted for clarity only).

Examples

High-Level Data Link Control (HDLC)
Advanced Data Communication Control Procedures (ADCCP)
in UTF-8, bit patterns 0xxxxxxx and 11xxxxxx are synchronizing words used to mark the beginning of the next valid character

References

1. ^US Federal Standard 1037C
2. ^¹Berstel et al (2010) p. 137
3. ^Berstel & Perrin (1985) p. 377
4. ^¹²Berstel et al (2010) p. 138

{{citation | last1=Berstel | first1=Jean | last2=Perrin | first2=Dominique | title=Theory of Codes | publisher=Academic Press | year=1985 | zbl=0587.68066 | series=Pure and Applied Mathematics | volume=117 }}
{{cite book | last1=Berstel | first1=Jean | last2=Perrin | first2=Dominique | last3=Reutenauer | first3=Christophe | title=Codes and automata | series=Encyclopedia of Mathematics and its Applications | volume=129 | location=Cambridge | publisher=Cambridge University Press | year=2010 | isbn=978-0-521-88831-8 | zbl=1187.94001 }}
{{FS1037C MS188}}

2 : Line codes|Synchronization

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Synchronizing word

Examples

Examples

See also

References