1 <section id="vorbis-spec-codebook">
4 $Id: 03-codebook.xml,v 1.2 2002/10/14 23:47:54 giles Exp $
5 <emphasis>Last update to this document: August 8, 2002</emphasis>
8 <title>probability model and codebooks</title>
11 <title>Overview</title>
14 Unlike practically every other mainstream audio codec, Vorbis has no
15 statically configured probability model, instead packing all entropy
16 decoding configuration, VQ and Huffman, into the bitstream itself in
17 the third header, the codec setup header. This packed configuration
18 consists of multiple 'codebooks', each containing a specific
19 Huffman-equivalent representation for decoding compressed codewords as
20 well as an optional lookup table of output vector values to which a
21 decoded Huffman value is applied as an offset, generating the final
22 decoded output corresponding to a given compressed codeword.</para>
24 <section><title>bitwise operation</title>
26 The codebook mechanism is built on top of the vorbis bitpacker. Both
27 the codebooks themselves and the codewords they decode are unrolled
28 from a packet as a series of arbitrary-width values read from the
29 stream according to <xref linkend="vorbis-spec-bitpacking"/>.</para>
35 <title>Packed Codebook Format</title>
38 For purposes of the below examples, we assume that the storage
39 system's native byte width is eight bits. This is not universally
40 true; see <xref linkend="vorbis-spec-bitpacking"/> for discussion
41 relating to non-eight-bit bytes.</para>
43 <section><title>codebook decode</title>
46 A codebook begins with a 24 bit sync pattern, 0x564342:
49 byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
50 byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
51 byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
55 16 bit <varname>[codebook_dimensions]</varname> and 24 bit <varname>[codebook_entries]</varname> fields:
59 byte 3: [ X X X X X X X X ]
60 byte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned)
62 byte 5: [ X X X X X X X X ]
63 byte 6: [ X X X X X X X X ]
64 byte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned)
69 Next is the <varname>[ordered]</varname> bit flag:
73 byte 8: [ X ] [ordered] (1 bit)
78 Each entry, numbering a
79 total of <varname>[codebook_entries]</varname>, is assigned a codeword length.
80 We now read the list of codeword lengths and store these lengths in
81 the array <varname>[codebook_codeword_lengths]</varname>. Decode of lengths is
82 according to whether the <varname>[ordered]</varname> flag is set or unset.
86 <para>If the <varname>[ordered]</varname> flag is unset, the codeword list is not
87 length ordered and the decoder needs to read each codeword length
90 <para>The decoder first reads one additional bit flag, the
91 <varname>[sparse]</varname> flag. This flag determines whether or not the
92 codebook contains unused entries that are not to be included in the
96 byte 8: [ X 1 ] [sparse] flag (1 bit)
100 The decoder now performs for each of the <varname>[codebook_entries]</varname>
105 1) if([sparse] is set){
107 2) [flag] = read one bit;
108 3) if([flag] is set){
110 4) [length] = read a five bit unsigned integer;
111 5) codeword length for this entry is [length]+1;
115 6) this entry is unused. mark it as such.
119 } else the sparse flag is not set {
121 7) [length] = read a five bit unsigned integer;
122 8) the codeword length for this entry is [length]+1;
129 <para>If the <varname>[ordered]</varname> flag is set, the codeword list for this
130 codebook is encoded in ascending length order. Rather than reading
131 a length for every codeword, the encoder reads the number of
132 codewords per length. That is, beginning at entry zero:
135 1) [current_entry] = 0;
136 2) [current_length] = read a five bit unsigned integer and add 1;
137 3) [number] = read <link linkend="vorbis-spec-ilog">ilog</link>([codebook_entries] -
139 bits as an unsigned integer
140 4) set the entries [current_entry] through [current_entry]+[number]-1, inclusive,
141 of the [codebook_codeword_lengths] array to [current_length]
142 5) set [current_entry] to [number] + [current_entry]
143 6) increment [current_length] by 1
144 7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION; the decoder will
145 not be able to read this stream.
146 8) if [current_entry] is less than [codebook_entries], repeat process starting at 3)
152 After all codeword lengths have been decoded, the decoder reads the
153 vector lookup table. Vorbis I supports three lookup types:
156 <simpara>No lookup</simpara>
157 </listitem><listitem>
158 <simpara>Implicitly populated value mapping (lattice VQ)</simpara>
159 </listitem><listitem>
160 <simpara>Explicitly populated value mapping (tessellated or 'foam'
167 The lookup table type is read as a four bit unsigned integer:
169 1) [codebook_lookup_type] = read four bits as an unsigned integer
173 Codebook decode precedes according to <varname>[codebook_lookup_type]</varname>:
176 <para>Lookup type zero indicates no lookup to be read. Proceed past
177 lookup decode.</para>
178 </listitem><listitem>
179 <para>Lookup types one and two are similar, differing only in the
180 number of lookup values to be read. Lookup type one reads a list of
181 values that are permuted in a set pattern to build a list of vectors,
182 each vector of order <varname>[codebook_dimensions]</varname> scalars. Lookup
183 type two builds the same vector list, but reads each scalar for each
184 vector explicitly, rather than building vectors from a smaller list of
185 possible scalar values. Lookup decode proceeds as follows:
188 1) [codebook_minimum_value] = <link linkend="vorbis-spec-float32_unpack">float32_unpack</link>( read 32 bits as an unsigned integer)
189 2) [codebook_delta_value] = <link linkend="vorbis-spec-float32_unpack">float32_unpack</link>( read 32 bits as an unsigned integer)
190 3) [codebook_value_bits] = read 4 bits as an unsigned integer and add 1
191 4) [codebook_sequence_p] = read 1 bit as a boolean flag
193 if ( [codebook_lookup_type] is 1 ) {
195 5) [codebook_lookup_values] = <link linkend="vorbis-spec-lookup1_values">lookup1_values</link>(<varname>[codebook_entries]</varname>, <varname>[codebook_dimensions]</varname> )
199 6) [codebook_lookup_values] = <varname>[codebook_entries]</varname> * <varname>[codebook_dimensions]</varname>
203 7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each;
204 store these in order in the array [codebook_multiplicands]
207 </listitem><listitem>
208 <para>A <varname>[codebook_lookup_type]</varname> of greater than two is reserved
210 a stream that's not decodable by the specification in this
217 An 'end of packet' during any read operation in the above steps is
218 considered an error condition rendering the stream undecodable.</para>
220 <section><title>Huffman decision tree representation</title>
223 The <varname>[codebook_codeword_lengths]</varname> array and
224 <varname>[codebook_entries]</varname> value uniquely define the Huffman decision
225 tree used for entropy decoding.</para>
228 Briefly, each used codebook entry (recall that length-unordered
229 codebooks support unused codeword entries) is assigned, in order, the
230 lowest valued unused binary Huffman codeword possible. Assume the
231 following codeword length list:
245 Assigning codewords in order (lowest possible value of the appropriate
246 length to highest) results in the following codeword list:
249 entry 0: length 2 codeword 00
250 entry 1: length 4 codeword 0100
251 entry 2: length 4 codeword 0101
252 entry 3: length 4 codeword 0110
253 entry 4: length 4 codeword 0111
254 entry 5: length 2 codeword 10
255 entry 6: length 3 codeword 110
256 entry 7: length 3 codeword 111
262 Unlike most binary numerical values in this document, we
263 intend the above codewords to be read and used bit by bit from left to
264 right, thus the codeword '001' is the bit string 'zero, zero, one'.
265 When determining 'lowest possible value' in the assignment definition
266 above, the leftmost bit is the MSb.</para>
270 It is clear that the codeword length list represents a Huffman
271 decision tree with the entry numbers equivalent to the leaves numbered
276 <imagedata fileref="hufftree.png" format="PNG"/>
279 <phrase>[huffman tree illustration]</phrase>
285 As we assign codewords in order, we see that each choice constructs a
286 new leaf in the leftmost possible position.</para>
289 Note that it's possible to underspecify or overspecify a Huffman tree
290 via the length list. In the above example, if codeword seven were
291 eliminated, it's clear that the tree is unfinished:
295 <imagedata fileref="hufftree-under.png" format="PNG"/>
298 <phrase>[underspecified huffman tree illustration]</phrase>
304 Similarly, in the original codebook, it's clear that the tree is fully
305 populated and a ninth codeword is impossible. Both underspecified and
306 overspecified trees are an error condition rendering the stream
310 Codebook entries marked 'unused' are simply skipped in the assigning
311 process. They have no codeword and do not appear in the decision
312 tree, thus it's impossible for any bit pattern read from the stream to
313 decode to that entry number.</para>
317 <section><title>VQ lookup table vector representation</title>
320 Unpacking the VQ lookup table vectors relies on the following values:
322 the [codebook_multiplicands] array
323 [codebook_minimum_value]
324 [codebook_delta_value]
325 [codebook_sequence_p]
326 [codebook_lookup_type]
328 [codebook_dimensions]
329 [codebook_lookup_values]
334 Decoding (unpacking) a specific vector in the vector lookup table
335 proceeds according to <varname>[codebook_lookup_type]</varname>. The unpacked
336 vector values are what a codebook would return during audio packet
337 decode in a VQ context.</para>
339 <section><title>Vector value decode: Lookup type 1</title>
342 Lookup type one specifies a lattice VQ lookup table built
343 algorithmically from a list of scalar values. Calculate [unpack] the
344 final values of a codebook entry vector from the entries in
345 <varname>[codebook_multiplicands]</varname> as follows (<varname>[value_vector]</varname>
346 is the output vector representing the vctor of values for entry number
347 <varname>[lookup_offset]</varname> in this codebook):
351 2) [index_divisor] = 1;
352 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
354 4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer
355 division ) integer modulo [codebook_lookup_values]
357 5) vector [value_vector] element [i] =
358 ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
359 [codebook_delta_value] + [codebook_minimum_value] + [last];
361 6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
363 7) [index_divisor] = [index_divisor] * [codebook_lookup_values]
367 8) vector calculation completed.
372 <section><title>Vector value decode: Lookup type 2</title>
375 Lookup type two specifies a VQ lookup table in which each scalar in
376 each vector is explicitly set by the <varname>[codebook_multiplicands]</varname>
377 array in a one-to-one mapping. Calculate [unpack] the
378 final values of a codebook entry vector from the entries in
379 <varname>[codebook_multiplicands]</varname> as follows (<varname>[value_vector]</varname>
380 is the output vector representing the vctor of values for entry number
381 <varname>[lookup_offset]</varname> in this codebook):
385 2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
386 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
388 4) vector [value_vector] element [i] =
389 ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
390 [codebook_delta_value] + [codebook_minimum_value] + [last];
392 5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
394 6) increment [multiplicand_offset]
398 7) vector calculation completed.
410 <title>Use of the codebook abstraction</title>
413 The decoder uses the codebook abstraction much as it does the
414 bit-unpacking convention; a specific codebook reads a
415 codeword from the bitstream, decoding it into an entry number, and then
416 returns that entry number to the decoder (when used in a scalar
417 entropy coding context), or uses that entry number as an offset into
418 the VQ lookup table, returning a vector of values (when used in a context
419 desiring a VQ value). Scalar or VQ context is always explicit; any call
420 to the codebook mechanism requests either a scalar entry number or a
421 lookup vector.</para>
424 Note that VQ lookup type zero indicates that there is no lookup table;
425 requesting decode using a codebook of lookup type 0 in any context
426 expecting a vector return value (even in a case where a vector of
427 dimension one) is forbidden. If decoder setup or decode requests such
428 an action, that is an error condition rendering the packet
432 Using a codebook to read from the packet bitstream consists first of
433 reading and decoding the next codeword in the bitstream. The decoder
434 reads bits until the accumulated bits match a codeword in the
435 codebook. This process can be though of as logically walking the
436 Huffman decode tree by reading one bit at a time from the bitstream,
437 and using the bit as a decision boolean to take the 0 branch (left in
438 the above examples) or the 1 branch (right in the above examples).
439 Walking the tree finishes when the decode process hits a leaf in the
440 decision tree; the result is the entry number corresponding to that
441 leaf. Reading past the end of a packet propagates the 'end-of-stream'
442 condition to the decoder.</para>
445 When used in a scalar context, the resulting codeword entry is the
446 desired return value.</para>
449 When used in a VQ context, the codeword entry number is used as an
450 offset into the VQ lookup table. The value returned to the decoder is
451 the vector of scalars corresponding to this offset.</para>
457 <!-- end section of probablity model and codebooks -->