In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
, especially in
telecommunication
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that ...
s, a self-synchronizing code is a
uniquely decodable code in which the
symbol
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different conc ...
stream formed by a portion of one
code word
In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...
, 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
[Berstel et al (2010) p. 137] or, ambiguously, comma-free code.
[Berstel & Perrin (1985) p. 377] A self-synchronizing code permits the proper
framing of transmitted code words provided that no uncorrected errors occur in the
symbol stream; external
synchronization
Synchronization is the coordination of events to operate a system in unison. For example, the conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are said to be synchronou ...
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
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
may propagate errors further in the stream and make the subsequent data
corrupted.
Importance of self-synchronizing codes is not limited to
data transmission
Data transmission and data reception or, more broadly, data communication or digital communications is the transfer and reception of data in the form of a digital bitstream or a digitized analog signal transmitted over a point-to-point or ...
. Self-synchronization also facilitates some cases of
data recovery
In computing, data recovery is a process of retrieving deleted, inaccessible, lost, corrupted, damaged, or formatted data from secondary storage, removable media or files, when the data stored in them cannot be accessed in a usual way. The dat ...
, for example of a
digitally encoded text.
Examples
* The prefix code is self-synchronizing because 0, 1, 01 and 10 are not codes.
*
UTF-8
UTF-8 is a variable-length character encoding used for electronic communication. Defined by the Unicode Standard, the name is derived from ''Unicode'' (or ''Universal Coded Character Set'') ''Transformation Format 8-bit''.
UTF-8 is capable of e ...
is self-synchronizing because its leading (
11xxxxxx) and trailing (
10xxxxxx) bytes have different bit patterns.
*
High-Level Data Link Control
High-Level Data Link Control (HDLC) is a bit-oriented code-transparent synchronous data link layer protocol developed by the International Organization for Standardization (ISO). The standard for HDLC is ISO/IEC 13239:2002.
HDLC provides both c ...
(HDLC)
*
Advanced Data Communication Control Procedures In telecommunication, Advanced Data Communication Control Procedures (or Protocol) (ADCCP) is a bit-oriented data link layer protocol developed by the American National Standards Institute. It is functionally equivalent to the ISO High-Level Data ...
(ADCCP)
*
Fibonacci coding
Counterexamples:
* The prefix code is not self-synchronizing because ''abab'' contains ''ba''.
* The prefix code ''b''
∗a (using the
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
) 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
In digital transmission, bit slip is the loss or gain of a bit or bits, caused by clock drift – variations in the respective clock rates of the transmitting and receiving devices.
One cause of bit slippage is overflow of a receive buffer that ...
*
Comma code A comma code is a type of prefix-free code in which a comma, a particular symbol or sequence of symbols, occurs at the end of a code word and never occurs otherwise. This is an intuitive way to express arrays.
For example, Fibonacci coding is a com ...
*
Self-clocking signal
*
Consistent Overhead Byte Stuffing Consistent Overhead Byte Stuffing (COBS) is an algorithm for encoding data bytes that results in efficient, reliable, unambiguous packet framing regardless of packet content, thus making it easy for receiving applications to recover from malformed ...
References
*
*
*
Line codes
Synchronization
{{telecomm-stub