World Library  
Flag as Inappropriate
Email this Article

Self-synchronizing code

Article Id: WHEBN0000041687
Reproduction Date:

Title: Self-synchronizing code  
Author: World Heritage Encyclopedia
Language: English
Subject: UTF-8, Prefix code, Comma-free code, Code point, Syncword
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Self-synchronizing code

In coding theory, especially in telecommunications, a self-synchronizing code[1] is a uniquely decodable code in which the 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.

Other terms for self-synchronizing code are synchronized code[2] or, ambiguously, comma-free code.[3] A self-synchronizing code permits the proper framing of transmitted code words provided that no uncorrected errors occur in the 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 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 digitally encoded text.

Contents

  • Synchronizing word 1
    • Examples 1.1
  • Examples 2
  • See also 3
  • References 4

Synchronizing word

A code X over an alphabet A has a synchronizing word w in A+ if

x w yX * ⇒ {x w, w y} ⊆ X *.[2]

A prefix code is synchronized if and only if it has a synchronizing word.[4]

Examples

  • The prefix code {ab,ba} has abba as a synchronizing word.[4]
  • The prefix code ba has a as a synchronizing word.[4]
  • 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).
    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

See also

References

  1. ^ US Federal Standard 1037C
  2. ^ a b Berstel et al (2010) p. 137
  3. ^ Berstel & Perrin (1985) p. 377
  4. ^ a b c Berstel et al (2010) p. 138
  • Berstel, Jean; Perrin, Dominique (1985), Theory of Codes, Pure and Applied Mathematics 117, Academic Press,  
  • Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge:  
  •  This article incorporates public domain material from the General Services Administration document "Federal Standard 1037C" (in support of MIL-STD-188).


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.