[Vorbis-dev] nodebytes,leafwords

[Dominik Kuhlen]

On Monday 28 November 2005 12:12, Ashok wrote:
> hello all,
>
> we are developing and porting vorbis1decoder on a 24 bit
> platform. in the process we came across somedoubts about
> node bytes and leaf words.
>
> from the specification we got that we are arranging
> the huffman codeword tree into an array. the nodebytes are the
I think it is just the opposite way: you read a list (array) of 
codeword-lengths and create a huffman-tree from this list.
> number of bytes that are required to represent a node and
> leafwords are the no. of bytes required to represent the leaf
> i.e the actual codeword.
I'm not sure if I understand you correctly. Here's my interpretation:
You get (extract) a list of codeword lengths.
The indices of this list are the values that are to be coded by the 
huffmantree. Heres an example:
let the codeword-length-list be: {1, 2, 3, 5, 4, 7, 5, 7 }
This means: 
value 0 is encoded with 1 bit.
value 1 is encoded with 2 bit.
.....
value 5 is encoded with 7 bit.

If you have 'dot' (graphviz) on your system you can generate a picture with 
the attached file:
dot -Tpng -o CB06.png < Codebook06.gwdot
>
> is this interpretation correct? if i am wrong please explain
> me what exactly the nodebytes and leafwords represent and their
> significance in the huffman codeword tree arrangement.
I'm not sure what you mean with 'nodebytes' and 'leafwords'
>
> we downloaded 250 test vectors. when we are deocding we got the
> maximum codeword length as 22 bits. practically, what is the maximum
> codeword length that is possible?
This may happen, I just tested a vorbis file and the maximum codeword length
was: 20 bit (minimum length: 1 bit)
>
> looking forward for your suggestions..
>
> regards
> ashok.
> _______________________________________________
> Vorbis-dev mailing list
> Vorbis-dev at xiph.org
> http://lists.xiph.org/mailman/listinfo/vorbis-dev

hope I could help you a little,
Dominik
-------------- next part --------------
/* Warning! This file has been created automagically by huffmantree.cpp */
digraph Codebook {
node [shape = record, height = 0.1];
node0[label = "<f0> 0 | <f1> | <f2> 1"];
node1 [shape = ellipse, label = "0"];
node0:f0 -> node1;
node2[label = "<f0> 0 | <f1> | <f2> 1"];
node3 [shape = ellipse, label = "1"];
node2:f0 -> node3;
node4[label = "<f0> 0 | <f1> | <f2> 1"];
node5 [shape = ellipse, label = "2"];
node4:f0 -> node5;
node6[label = "<f0> 0 | <f1> | <f2> 1"];
node7[label = "<f0> 0 | <f1> | <f2> 1"];
node8[label = "<f0> 0 | <f1> | <f2> 1"];
node9 [shape = ellipse, label = "3"];
node8:f0 -> node9;
node10[label = "<f0> 0 | <f1> | <f2> 1"];
node11 [shape = ellipse, label = "5"];
node10:f0 -> node11;
node12 [shape = ellipse, label = "7"];
node10:f2 -> node12;
node8:f2 -> node10:f1
node7:f0 -> node8:f1
node13 [shape = ellipse, label = "6"];
node7:f2 -> node13;
node6:f0 -> node7:f1
node14 [shape = ellipse, label = "4"];
node6:f2 -> node14;
node4:f2 -> node6:f1
node2:f2 -> node4:f1
node0:f2 -> node2:f1
}