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 computer data storage, data sto ...
, especially in
telecommunications
Telecommunication, often used in its plural form or abbreviated as telecom, is the transmission of information over a distance using electronic means, typically through cables, radio waves, or other communication technologies. These means of ...
, a self-synchronizing code is a
uniquely decodable code
In coding theory, a variable-length code is a code which maps source symbols to a ''variable'' number of bits. The equivalent concept in computer science is ''bit string''.
Variable-length codes can allow sources to be compressed and decompres ...
in which the
symbol
A symbol is a mark, Sign (semiotics), sign, or word that indicates, signifies, or is understood as representing an idea, physical object, object, or wikt:relationship, relationship. Symbols allow people to go beyond what is known or seen by cr ...
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
A prefix code is a type of code system distinguished by its possession of the prefix property, which requires that there is no whole Code word (communication), code word in the system that is a prefix (computer science), prefix (initial segment) of ...
, but not all prefix codes are self-synchronizing.
Other terms for self-synchronizing code are synchronized code
or, ambiguously, comma-free code.
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 (music), conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are sa ...
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 communication. 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 represented as ...
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 communication, including data transmission and data reception, is the transfer of data, signal transmission, transmitted and received over a Point-to-point (telecommunications), point-to-point or point-to-multipoint communication chann ...
. Self-synchronization also facilitates some cases of
data recovery
In computing, data recovery is a process of retrieving deleted, inaccessible, lost, corrupted, damaged, overwritten or formatted data from computer data storage#Secondary storage, secondary storage, removable media or Computer file, files, when ...
, for example of a
digitally encoded text.
Examples
*
UTF-8
UTF-8 is a character encoding standard used for electronic communication. Defined by the Unicode Standard, the name is derived from ''Unicode Transformation Format 8-bit''. Almost every webpage is transmitted as UTF-8.
UTF-8 supports all 1,112,0 ...
is self-synchronizing because the leading byte (
11xxxxxx) and subsequent bytes (
10xxxxxx) of a multi-byte code point have different bit patterns.
*
High Level Data Link Control (HDLC)
*
Advanced Data Communication Control Procedures
In telecommunications, 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 D ...
(ADCCP)
*
Fibonacci coding
In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains n ...
Counterexamples:
* The prefix code is not self-synchronizing; while 0, 1, 01 and 10 are not codes, 00 and 11 are.
* The prefix code is not self-synchronizing because ''abab'' contains ''ba''.
* The prefix code ''b''
∗a (using the
Kleene star
In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...
) 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 driftvariations in the respective clock rates of the transmitting and receiving devices.
One cause of bit slip is overflow of a receive buffer that occu ...
*
Comma code
*
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 ...
*
Dynkin sequence
*
Kraus principle
*
Kruskal's principle
The Kruskal count (also known as Kruskal's principle, Dynkin–Kruskal count, Dynkin's counting trick, Dynkin's card trick, coupling card trick or shift coupling) is a probabilistic concept originally demonstrated by the Russian mathematician E ...
*
Overlapping instructions
In computer programming, machine code is computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). For conventional binary computers, machine code is the binaryOn nonb ...
*
Pollard's lambda method
*
Self-clocking signal
In telecommunications and electronics, a self-clocking signal is one that can be decoded without the need for a separate clock signal or other source of Synchronization (computer science), synchronization. This is usually done by including embedd ...
*
Self-synchronizing block code
A comma-free code is block code in which no concatenation of two code words contains a valid code word that overlaps both.
Comma-free codes are also known as ''self-synchronizing block codes'' because no synchronization is required to find the be ...
References
Further reading
*
*
MIL-STD-188
MIL-STD-188 is a series of U.S. military standards relating to telecommunications.
Purpose
Faced with "past technical deficiencies in telecommunications systems and equipment and software…that were traced to basic inadequacies in the appl ...
{{DEFAULTSORT:Self-Synchronizing Code
Line codes
Synchronization