Talk:Self-synchronizing code

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Synchronizing word examples[edit]

The examples under this section were removed [1] with edit summary rm poorly formulated examples ({"ab","ba"} is not a prefix code unless "a" and "b" are not characters but something else). This comment seems wrong because (i) the examples were sourced to page 138 of Berstel, Perrin & Reutenauer (2010) which seems an unimpeachably reliable source (ii) the comment is simply wrong: a prefix code is one for which "there is no valid code word in the system that is a prefix (start) of any other valid code word" and this is clearly true for {"ab","ba"} and for {ba}. I have restored the examples in question. Deltahedron (talk) 17:08, 11 April 2013 (UTC)

Overall confusion[edit]

I am afraid that this article conflates two different sets of requirements. The first set, specified in the introduction, defines strict self-synchronisation, meaning that you can always detect when a part of transmitted data has been lost, and continue decoding without losing more words than those that were actually lost. The second set, taken from the book, defines statistically converging self-synchronisation, in that a transmission error causes several following parts to be corrupt but the decoder is expected to get back on track relatively quickly in most cases. The introduction says that both notions are equivalent.

In particular, the example {ab, ba} meets the second set but not the first one. Also note that a complete Huffman code, which is expected to meet the second set with almost surely, can never meet the first set.

--Yecril (talk) 22:02, 2 February 2014 (UTC)

It would help to give reliable sources for the definitions you mention ("the book" is rather ambiguous) since the introduction does mention slightly different concepts without clarifying the relationship between them. As far as the section Synchronizing word is concerned, where you added the requests for clarification, what is it that is unclear? Your edit summaries were this probably means that both words xw and wy are accepted, to which the answer is yes, and abab contains ba which needs, well, clarification. Deltahedron (talk) 22:45, 2 February 2014 (UTC)
"The book" refers to both books by Berstel (there are no other books mentioned in the article). The string 'abab' is a concatenation of two code words from the example that is declared self-synchronising; it contains another code word 'ba' inside it, which is prohibited by the definition in the introduction. Thank you for your consideration. --Yecril (talk) 11:34, 3 February 2014 (UTC)
Ah, I see. In other words, the code on {ab,ba} is synchronized (as abba is a synchronizing word) but not self-synchronizing (as abab contains ba). Deltahedron (talk) 17:38, 3 February 2014 (UTC)