Shashank Khanvilkar
2005-Aug-08 09:07 UTC
[Vorbis-dev] 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
Shashank Khanvilkar
2005-Aug-08 10:45 UTC
[Vorbis-dev] Reg. getting codewords from codelengths
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 | 10000117 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-devDominik -------------- 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 }
Sebastian Gesemann
2005-Aug-09 07:00 UTC
[Vorbis-dev] Reg. getting codewords from codelengths
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 | > > ShankThe 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