Vorbis dev - Aug 2005 - Reg. getting codewords from codelengths

Hi,
I am a bit confused on how code-words are derived from the codeword 
lengths. I will appreciate if someone can point me in the correct direction.

I will take the example of an actual codebook that i found in a valid 
vorbis encoded file as shown below.

[SK] +------Codebook [0] --------
[SK] Codebook Dimensions = 1
[SK] Codebook Entries = 8
[SK] Unordered
[SK] 1, 6, 3, 7, 2, 5, 4, 7,
[SK] NO Mapping
[SK] +------Codebook [1] --------

What are the correspnding codewords? I have written below a few, but I 
think they might be wrong.

---------------------------
Entry len   |    Codeword |
---------------------------
1           |  0
6           |  100000
3           |  000
7           |  10000000
2           |
5           |
4           |
7           |

Shank

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 code is always the smallest (if interpreted as integer in binary)
> possible with that length so that there're no conflicts with the
already
> generated ones above (ie codes have to be prefix-free).
> 
> 
> Sebi

Hi
On Monday 08 August 2005 18:08, Shashank Khanvilkar
wrote:
> Hi,
> I am a bit confused on how code-words are derived from the codeword
> lengths. I will appreciate if someone can point me in the correct
> direction.
>
> I will take the example of an actual codebook that i found in a valid
> vorbis encoded file as shown below.
>
> [SK] +------Codebook [0] --------
> [SK] Codebook Dimensions = 1
> [SK] Codebook Entries = 8
> [SK] Unordered
> [SK] 1, 6, 3, 7, 2, 5, 4, 7,
> [SK] NO Mapping
> [SK] +------Codebook [1] --------
>
> What are the correspnding codewords? I have written below a few, but I
> think they might be wrong.
>
> ---------------------------
> Entry len   |    Codeword |
> ---------------------------
> 1           |  0
> 6           |  100000
> 3           |  000
> 7           |  10000000
> 2           |
> 5           |
> 4           |
> 7           |
If you have access to graphviz / dot you may try
dot -Tpng < foo.dot > foo.png
This is what my decoder has created.
Heres the debug output:
Node 0x804b050 @ 1 : Left = 0
Node 0x804b050 @ 1 : right subnode : 0x804b060
Node 0x804b060 @ 2 : left subnode : 0x804b070
Node 0x804b070 @ 3 : left subnode : 0x804b080
Node 0x804b080 @ 4 : left subnode : 0x804b090
Node 0x804b090 @ 5 : left subnode : 0x804b0a0
Node 0x804b0a0 @ 6 : Left = 1
Node 0x804b0a0 @ 6 : right subnode : 0x804b0b0
Node 0x804b0b0 @ 7 : Left = 3
Node 0x804b0b0 @ 7 : Right = 7
Node 0x804b090 @ 5 : Right = 5
Node 0x804b080 @ 4 : Right = 6
Node 0x804b070 @ 3 : Right = 2
Node 0x804b060 @ 2 : Right = 4
>
> Shank
>
> _______________________________________________
> Vorbis-dev mailing list
> Vorbis-dev@xiph.org
> http://lists.xiph.org/mailman/listinfo/vorbis-dev
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[label = "<f0> 0 | <f1> | <f2> 1"];
node4[label = "<f0> 0 | <f1> | <f2> 1"];
node5[label = "<f0> 0 | <f1> | <f2> 1"];
node6[label = "<f0> 0 | <f1> | <f2> 1"];
node7 [shape = ellipse, label = "1"];
node6:f0 -> node7;
node8[label = "<f0> 0 | <f1> | <f2> 1"];
node9 [shape = ellipse, label = "3"];
node8:f0 -> node9;
node10 [shape = ellipse, label = "7"];
node8:f2 -> node10;
node6:f2 -> node8:f1
node5:f0 -> node6:f1
node11 [shape = ellipse, label = "5"];
node5:f2 -> node11;
node4:f0 -> node5:f1
node12 [shape = ellipse, label = "6"];
node4:f2 -> node12;
node3:f0 -> node4:f1
node13 [shape = ellipse, label = "2"];
node3:f2 -> node13;
node2:f0 -> node3:f1
node14 [shape = ellipse, label = "4"];
node2:f2 -> node14;
node0:f2 -> node2:f1
}

Shashank Khanvilkar wrote:
> Hi,
> I am a bit confused on how code-words are derived from the codeword
> lengths. I will appreciate if someone can point me in the correct
> direction.
> 
> I will take the example of an actual codebook that i found in a valid
> vorbis encoded file as shown below.
> 
> [SK] +------Codebook [0] --------
> [SK] Codebook Dimensions = 1
> [SK] Codebook Entries = 8
> [SK] Unordered
> [SK] 1, 6, 3, 7, 2, 5, 4, 7,
> [SK] NO Mapping
> [SK] +------Codebook [1] --------
> 
> What are the correspnding codewords? I have written below a few, but I
> think they might be wrong.
> 
> ---------------------------
> Entry len   |    Codeword |
> ---------------------------
> 1           |  0
> 6           |  100000
> 3           |  000
> 7           |  10000000
> 2           |
> 5           |
> 4           |
> 7           |
> 
> Shank
The following assignment should be correct:

---------------------------
Entry len   |    Codeword |
---------------------------
1           |  0
6           |  100000
3           |  101
7           |  1000010
2           |  11
5           |  10001
4           |  1001
7           |  1000011

The code is always the smallest (if interpreted as integer in binary)
possible with that length so that there're no conflicts with the already
generated ones above (ie codes have to be prefix-free).


Sebi