Self-synchronizing code: Difference between revisions

Revision as of 02:14, 1 March 2019

Latest revision as of 00:00, 16 September 2024

(28 intermediate revisions by 15 users not shown)

Line 1:

{{Use American English|date = March 2019}}

{{Short description|Type of code in coding theory}}

{{Use mdydmy dates|date = March 2019|cs1-dates=y}}

{{Use list-defined references|date=August 2023}}

{{distinguish|self-clocking signal}}

{{Distinguish|Self-clocking signal|Self-similar process}}

In [[coding theory]], especially in [[telecommunication]]s, a '''self-synchronizing code'''<ref>US [[Federal Standard 1037C]]</ref> 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. 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.

In [[coding theory]], especially in [[telecommunicationtelecommunications]]s, a '''self-synchronizing code'''<ref>US [[Federal Standard 1037C]]</ref> is a [[uniquely decodable code]] in which the [[symbol (data)|symbol]] stream formed by a portion of one [[Code word (communication)|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=BPR137>Berstel et al (2010) p. 137</ref> or, ambiguously, '''comma-free code'''.<ref>Berstel & Perrin (1985) p. 377</ref> 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=BPR137>Berstel et al (2010) p. 137<"Brestel-Perrin-Reutenauer_2010"/ref> or, ambiguously, '''comma-free code'''.<ref>Berstel & Perrin (1985) p. 377<name="Brestel-Perrin_1985"/ref> 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]].

Importance of self-synchronizing codes is not limited to [[data transmission]]. Self-synchronization also facilitates some cases of [[data recovery]], for example of a [[character encoding|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''} &sube; ''X''^* }}.<ref name=BPR137/>{{clarify|date=February 2014}}

A prefix code is synchronized if and only if it has a synchronizing word.<ref name=BPR138>Berstel et al (2010) p. 138</ref>{{clarify|abab contains ba|date=February 2014}}

===Examples===

* The prefix code {''ab'',''ba''} has ''abba'' as a synchronizing word.<ref name=BPR138/>

* The prefix code ''b''^∗a has ''a'' as a synchronizing word.<ref name=BPR138/>

* 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). <br/>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==

* [[UTF-8]] is self-synchronizing because the leading byte (<code>11xxxxxx</code>) and subsequent bytes (<code>10xxxxxx</code>) of a multi-byte code point have different bit patterns.

* [[High- Level Data Link Control]] (HDLC)

* [[Advanced Data Communication Control Procedures]] (ADCCP)

* [[Fibonacci coding]]

* in [[UTF-8]], bit patterns <code>0xxxxxxx</code> and <code>11xxxxxx</code> are synchronizing words used to mark the beginning of the next valid character

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==

{{Reflist}}|refs=

<ref name="Glossary">{{Cite web |url=https://glossary.atis.org/glossary/self-synchronizing-code/?char=S&page_number=22&sort=ASC |title=Self-synchronizing code – Glossary}}</ref>

* {{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 }}

*<ref name="Brestel-Perrin_1985">{{cite book | author-last1=Berstel | author-first1=Jean | author-last2=Perrin | author-first2=Dominique | last3title=ReutenauerTheory |of first3=Christophe | title=Codes and automata | seriespublisher=Encyclopedia[[Academic of Mathematics and its ApplicationsPress]] | volumedate=1291985 | ___locationzbl=Cambridge0587.68066 | publisherseries=[[CambridgePure Universityand Press]]Applied | year=2010Mathematics | isbnvolume=978-0-521-88831-8117 | zblpage=1187.94001 377}}</ref>

<ref name="Brestel-Perrin-Reutenauer_2010">{{cite book |author-last1=Berstel |author-first1=Jean |author-last2=Perrin |author-first2=Dominique |author-last3=Reutenauer |author-first3=Christophe |title=Codes and automata |series=Encyclopedia of Mathematics and its Applications |volume=129 |___location=Cambridge, UK |publisher=[[Cambridge University Press]] |date=2010 |isbn=978-0-521-88831-8 |zbl=1187.94001 |page=137}}</ref>

* {{FS1037C MS188}}

}}

== Further reading ==

* {{cite book |title=Federal Standard 1037C: Telecommunications: Glossary of Telecommunication Terms |title-link=Federal Standard 1037C |chapter=self-synchronizing code |date=1996-08-06 |publisher=[[General Services Administration]] |chapter-url=https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm |url-status=dead |archive-url=https://web.archive.org/web/20220122224547/https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm |archive-date=2022-01-22}}

* [[MIL-STD-188]]

{{DEFAULTSORT:Self-Synchronizing Code}}

[[Category:Line codes]]

[[Category:Synchronization]]

{{telecomm-stub}}