[Vorbis-dev] Reg. getting codewords from codelengths

[Sebastian Gesemann]

Shashank Khanvilkar wrote:

> Thanks.. in the below case, if tehre is one more line with codelenght
> "7", what would be the codeword assigned to it.
> 
>> ---------------------------
>> Entry len   |    Codeword |
>> ---------------------------
>> 1           |  0
>> 6           |  100000
>> 3           |  101
>> 7           |  1000010
>> 2           |  11
>> 5           |  10001
>> 4           |  1001
>> 7           |  1000011
> 
>   7              1000100  (conflicts with 5)
> or
>   7              1001000  (conflicts with 4)
> or
>   7              1100000

The last one uses code '11' for its prefix which is also illegal.
There simply can't be more codes because the binary decoding tree is
already "complete" (each non-leaf has exactly two chrildren). And you
can't append any other 'codes' to the tree 'cause then some already
present code (former leaf) will become prefix of the new one.

You should read some introductions to coding theory (Look up "prefix
codes", "Huffman", ...)


Sebi