Self-synchronizing code: Difference between revisions

Revision as of 11:56, 27 December 2023

Latest revision as of 00:00, 16 September 2024

(3 intermediate revisions by 3 users not shown)

Line 4:

{{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''' 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="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]].

Line 11 ⟶ 12:

==Examples==

* The prefix code {00, 11} is self-synchronizing because 0, 1, 01 and 10 are not codes.

* [[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)

Line 18:

Counterexamples:

* The prefix code {00, 11} is not self-synchronizing; becausewhile 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''.