2
$\begingroup$

A code is (statistically) self-synchronizing if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have occurred.

Do Huffman codes have this property in general? In case not, is there a criterion for testing if a Huffman code is self-synchronizing or, equivalently, is there a modified construction of a Huffman code which guarantees self-synchronization?

$\endgroup$
  • $\begingroup$ See this paper: ieeexplore.ieee.org/document/1056931. $\endgroup$ – Yuval Filmus Nov 24 '18 at 14:47
  • $\begingroup$ I suggest doing some literature search before asking a question here. Even if you can’t find what you’re after, you can at least explain what you did find, and how it differs from your question. $\endgroup$ – Yuval Filmus Nov 24 '18 at 14:49
2
$\begingroup$

Assume 256 symbols, each with probability 1/256. The Huffman code words will be all 256 possible eight-bit sequences, and there is no synchronisation at all.

To find if a Huffman code is self-synchronising:

Let S = {}
For each code c:
    For 1 ≤ m < length (c)
        Let s be the last m bits of c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in S
            Add s to S.

Loop:
    If S is empty the the code is self-synchronising.
    Let T = {}
    For each s' in S, and code c:
        Let s be s' concatenated with c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in T
            Add s to T.
    If T = S then the code is not self-synchronising
    Let S = T and loop.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.