Self-synchronizing code: Difference between revisions

Revision as of 21:40, 30 June 2013

Latest revision as of 00:00, 16 September 2024

(42 intermediate revisions by 25 users not shown)

Line 1:

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

{{distinguish|self-clocking signal}}

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

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.

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

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

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

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]].

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''' {{mvar|w}} in {{math|''A''⁺}} if

:{{math|size=120%| ''x w y'' ∈ ''X''^* ⇒ ''x w'', ''w y'' ∈ ''X''^* }}.<ref name=BPR137/>

A prefix code is synchronized if and only if it has a synchronizing word.<ref name=BPR138>Berstel et al (2010) p. 138</ref>

===Examples===

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

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

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

* [[simple: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}}

[[simple:Self-synchronizing code]]