Uniquely Decodable Huffman Codes: What to Know

[hhhmortal]

Hi, I'm quite stuck in understanding a certain feature of the huffman code. Basically how do I know that the code is uniquely decodable?

For example if I'm given symbols with different code words for each symbol, which would be uniquely decodable?


Thanks.

 

[rcgldr]

Hi, I'm quite stuck in understanding a certain feature of the huffman code. Basically how do I know that the code is uniquely decodable?

This just means that a bit pattern doesn't represent more than one possible coding of data, that two or more different codes would produce the same bit pattern and therefore not be unique. One test would be to decode all bit combinantions of the longest code sequence plus a few bits. Normally the leading bit pattern, usually all 0 or or all 1 bits, determines the length of current code word.

 

[AUMathTutor]

The way it works is by having unique prefixes. What does that mean?

Let's say you have the following:
a :: 1
b :: 00
c :: 011
d :: 010

Now I give you a string of bits,

010100001111010101000101110100100101001010101001

How is this uniquely decodable? Well, we start reading from the left, and keep going to the right. We stop when the accumulated bits in the current string matches one of the entries in the table.

So here we go...
0
01
010 => becomes 'd'
1 => becomes 'a'
0
00 => becomes b
etc.

Basically, it's uniquely decodable because of the way the algorithm works, left to right, with prefix strings.

If you're asking whether or not things are uniquely encodable using Huffman's algorithm... they're not!

 

[hhhmortal]

The way it works is by having unique prefixes. What does that mean?

Let's say you have the following:
a :: 1
b :: 00
c :: 011
d :: 010

Now I give you a string of bits,

010100001111010101000101110100100101001010101001

How is this uniquely decodable? Well, we start reading from the left, and keep going to the right. We stop when the accumulated bits in the current string matches one of the entries in the table.

So here we go...
0
01
010 => becomes 'd'
1 => becomes 'a'
0
00 => becomes b
etc.

Basically, it's uniquely decodable because of the way the algorithm works, left to right, with prefix strings.

If you're asking whether or not things are uniquely encodable using Huffman's algorithm... they're not!

Oh right this makes perfect sense. Is there an easier way to determine if that alphabet you just mentioned is uniquely decodable or not? ..I've been trying to do it this way:

By adding a 1 or 0 at the end of the bit string of every symbol and seeing if they would match the others..If it does it wouldn't be unique?

 

[AUMathTutor]

As long as different characters have different prefixes, it will *always* be uniquely decodable. For instance, the following wouldn't work:

a :: 1
b :: 10
c :: 01
d :: 011

Why not? Because "a" is a prefix for "b". You wouldn't know whether to go with "a" when you reach it or keep going. Same for "c" and "d".

Under any scheme, if you start from the right and go left, for instance, you will get a different result than if you go left to right. In that sense, no scheme is uniquely decodable.

But making sure that no string is a prefix for another, and matching from left to right, it always works. Because you never have to ask, because once you can tell, it couldn't end up being something else.