doc/vorbis-spec-codebook.html

   1 <HTML><HEAD><TITLE>xiph.org: Ogg Vorbis documentation</TITLE>
   2 <BODY bgcolor="#ffffff" text="#202020" link="#006666" vlink="#000000">
   3 <nobr><img src="white-ogg.png"><img src="vorbisword2.png"></nobr><p>
   4
   5 <h1><font color=#000070>
   6 Ogg Vorbis I format specification: probability model and codebooks
   7 </font></h1>
   8
   9 <em>Last update to this document: August 8, 2002</em><br>
  10
  11 <h1>Overview</h1>
  12
  13 Unlike practically every other mainstream audio codec, Vorbis has no
  14 statically configured probability model, instead packing all entropy
  15 decoding configuration, VQ and Huffman, into the bitstream itself in
  16 the third header, the codec setup header.  This packed configuration
  17 consists of multiple 'codebooks', each containing a specific
  18 Huffman-equivalent representation for decoding compressed codewords as
  19 well as an optional lookup table of output vector values to which a
  20 decoded Huffman value is applied as an offset, generating the final
  21 decoded output corresponding to a given compressed codeword.
  22
  23 <h2>bitwise operation</h2>
  24
  25 The codebook mechanism is built on top of the <a
  26 href="vorbis-spec-bitpack.html">Vorbis bitpacker</a>; both the
  27 codebooks themselves and the codewords they decode are unrolled from a
  28 packet as a series of arbitrary-width values read from the stream
  29 according to the <a href="vorbis-spec-bitpack.html">Vorbis bitpacking
  30 convention</a>.
  31
  32 <h1>Packed Codebook Format</h1>
  33
  34 For purposes of the below examples, we assume that the storage
  35 system's native byte width is eight bits.  This is not universally
  36 true; see <a href="vorbis-spec-bitpack.html">the Vorbis bitpacking
  37 convention</a> document for discussion relating to non-eight-bit
  38 bytes.<p>
  39
  40 <h2>codebook decode</h2>
  41
  42 A codebook begins with a 24 bit sync pattern, 0x564342:
  43
  44 <pre>
  45 byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
  46 byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
  47 byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
  48 </pre>
  49
  50 16 bit <tt>[codebook_dimensions]</tt> and 24 bit <tt>[codebook_entries]</tt> fields:
  51
  52 <pre>
  53
  54 byte 3: [ X X X X X X X X ]
  55 byte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned)
  56
  57 byte 5: [ X X X X X X X X ]
  58 byte 6: [ X X X X X X X X ]
  59 byte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned)
  60
  61 </pre>
  62
  63 Next is the <tt>[ordered]</tt> bit flag:
  64
  65 <pre>
  66
  67 byte 8: [               X ] [ordered] (1 bit)
  68
  69 </pre>
  70
  71 Each entry, numbering a
  72 total of <tt>[codebook_entries]</tt>, is assigned a codeword length.
  73 We now read the list of codeword lengths and store these lengths in
  74 the array <tt>[codebook_codeword_lengths]</tt>. Decode of lengths is
  75 according to whether the <tt>[ordered]</tt> flag is set or unset.
  76
  77 <ul>
  78
  79   <li>If the <tt>[ordered]</tt> flag is unset, the codeword list is not
  80   length ordered and the decoder needs to read each codeword length
  81   one-by-one.<p> The decoder first reads one additional bit flag, the
  82   <tt>[sparse]</tt> flag.  This flag determines whether or not the
  83   codebook contains unused entries that are not to be included in the
  84   codeword decode tree:<p>
  85
  86 <pre>
  87 byte 8: [             X 1 ] [sparse] flag (1 bit)
  88 </pre>
  89
  90   The decoder now performs for each of the <tt>[codebook_entries]</tt> code book entries:
  91
  92 <pre>
  93
  94   1) if([sparse] is set){
  95
  96          2) [flag] = read one bit;
  97          3) if([flag] is set){
  98
  99               4) [length] = read a five bit unsigned integer;
 100               5) codeword length for this entry is [length]+1;
 101
 102             } else {
 103
 104               6) this entry is unused.  mark it as such.
 105
 106             }
 107
 108      } else the sparse flag is not set {
 109
 110         7) [length] = read a five bit unsigned integer;
 111         8) the codeword length for this entry is [length]+1;
 112
 113      }
 114
 115 </pre>
 116
 117   <li>If the <tt>[ordered]</tt> flag is set, the codeword list for this
 118   codebook is encoded in ascending length order.  Rather than reading
 119   a length for every codeword, the encoder reads the number of
 120   codewords per length.  That is, beginning at entry zero:
 121
 122 <pre>
 123   1) [current_entry] = 0;
 124   2) [current_length] = read a five bit unsigned integer and add 1;
 125   3) [number] = read <a
 126   href="helper.html#ilog">ilog</a>([codebook_entries] - [current_entry]) bits as an unsigned integer
 127   4) set the entries [current_entry] through [current_entry]+[number]-1, inclusive,
 128      of the [codebook_codeword_lengths] array to [current_length]
 129   5) set [current_entry] to [number] + [current_entry]
 130   6) increment [current_length] by 1
 131   7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION; the decoder will
 132      not be able to read this stream.
 133   8) if [current_entry] is less than [codebook_entries], repeat process starting at 3)
 134   9) done.
 135 </pre>
 136
 137 </ul>
 138
 139 After all codeword lengths have been decoded, the decoder reads the
 140 vector lookup table.  Vorbis I supports three lookup types:
 141 <ol><li>No lookup
 142 <li>Implicitly populated value mapping (lattice VQ)
 143 <li>Explicitly populated value mapping (tessellated or 'foam' VQ)
 144 </ol>
 145
 146 The lookup table type is read as a four bit unsigned integer:
 147 <pre>
 148   1) [codebook_lookup_type] = read four bits as an unsigned integer
 149 </pre>
 150
 151 Codebook decode precedes according to <tt>[codebook_lookup_type]</tt>:
 152 <ul>
 153 <li> Lookup type zero indicates no lookup to be read.  Proceed past
 154 lookup decode.
 155
 156 <li> Lookup types one and two are similar, differing only in the
 157 number of lookup values to be read.  Lookup type one reads a list of
 158 values that are permuted in a set pattern to build a list of vectors,
 159 each vector of order <tt>[codebook_dimensions]</tt> scalars.  Lookup
 160 type two builds the same vector list, but reads each scalar for each
 161 vector explicitly, rather than building vectors from a smaller list of
 162 possible scalar values.  Lookup decode proceeds as follows:
 163
 164 <pre>
 165   1) [codebook_minimum_value] = <a href="helper.html#float32_unpack">float32_unpack</a>( read 32 bits as an unsigned integer)
 166   2) [codebook_delta_value] = <a href="helper.html#float32_unpack">float32_unpack</a>( read 32 bits as an unsigned integer)
 167   3) [codebook_value_bits] = read 4 bits as an unsigned integer and add 1
 168   4) [codebook_sequence_p] = read 1 bit as a boolean flag
 169
 170   if ( [codebook_lookup_type] is 1 ) {
 171
 172      5) [codebook_lookup_values] = <a href="helper.html#lookup1_values">lookup1_values</a>( <tt>[codebook_entries]</tt>, <tt>[codebook_dimensions]</tt> )
 173
 174   } else {
 175
 176      6) [codebook_lookup_values] = <tt>[codebook_entries]</tt> * <tt>[codebook_dimensions]</tt>
 177
 178   }
 179
 180   7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each;
 181      store these in order in the array [codebook_multiplicands]
 182
 183 </pre>
 184 <li>A <tt>[codebook_lookup_type]</tt> of greater than two is reserved and indicates
 185 a stream that's not decodable by the specification in this document.
 186
 187 </ul>
 188
 189 An 'end of packet' during any read operation in the above steps is
 190 considered an error condition rendering the stream undecodable.<p>
 191
 192 <h2>Huffman decision tree representation</h2>
 193
 194 The <tt>[codebook_codeword_lengths]</tt> array and
 195 <tt>[codebook_entries]</tt> value uniquely define the Huffman decision
 196 tree used for entropy decoding.<p>
 197
 198 Briefly, each used codebook entry (recall that length-unordered
 199 codebooks support unused codeword entries) is assigned, in order, the
 200 lowest valued unused binary Huffman codeword possible.  Assume the
 201 following codeword length list:<p>
 202
 203 <pre>
 204 entry 0: length 2
 205 entry 1: length 4
 206 entry 2: length 4
 207 entry 3: length 4
 208 entry 4: length 4
 209 entry 5: length 2
 210 entry 6: length 3
 211 entry 7: length 3
 212 </pre>
 213
 214 Assigning codewords in order (lowest possible value of the appropriate
 215 length to highest) results in the following codeword list:<p>
 216
 217 <pre>
 218 entry 0: length 2 codeword 00
 219 entry 1: length 4 codeword 0100
 220 entry 2: length 4 codeword 0101
 221 entry 3: length 4 codeword 0110
 222 entry 4: length 4 codeword 0111
 223 entry 5: length 2 codeword 10
 224 entry 6: length 3 codeword 110
 225 entry 7: length 3 codeword 111
 226 </pre>
 227
 228 <em>note that unlike most binary numerical values in this document, we
 229 intend the above codewords to be read and used bit by bit from left to
 230 right, thus the codeword '001' is the bit string 'zero, zero, one'.
 231 When determining 'lowest possible value' in the assignment definition
 232 above, the leftmost bit is the MSb.</em><p>
 233
 234 It is clear that the codeword length list represents a Huffman
 235 decision tree with the entry numbers equivalent to the leaves numbered
 236 left-to-right:<p>
 237
 238 <img src="hufftree.png"><p>
 239
 240 As we assign codewords in order, we see that each choice constructs a
 241 new leaf in the leftmost possible position.<p>
 242
 243 Note that it's possible to underspecify or overspecify a Huffman tree
 244 via the length list.  In the above example, if codeword seven were
 245 eliminated, it's clear that the tree is unfinished:<p>
 246
 247 <img src="hufftree-under.png"><p>
 248
 249 Similarly, in the original codebook, it's clear that the tree is fully
 250 populated and a ninth codeword is impossible.  Both underspecified and
 251 overspecified trees are an error condition rendering the stream
 252 undecodable.<p>
 253
 254 Codebook entries marked 'unused' are simply skipped in the assigning
 255 process.  They have no codeword and do not appear in the decision
 256 tree, thus it's impossible for any bit pattern read from the stream to
 257 decode to that entry number.<p>
 258
 259 <h2>VQ lookup table vector representation</h2>
 260
 261 Unpacking the VQ lookup table vectors relies on the following values:
 262 <ul>
 263 <li> the <tt>[codebook_multiplicands]</tt> array
 264 <li> <tt>[codebook_minimum_value]</tt>
 265 <li> <tt>[codebook_delta_value]</tt>
 266 <li> <tt>[codebook_sequence_p]</tt>
 267 <li> <tt>[codebook_lookup_type]</tt>
 268 <li> <tt>[codebook_entries]</tt>
 269 <li> <tt>[codebook_dimensions]</tt>
 270 <li> <tt>[codebook_lookup_values]</tt>
 271 </tt>
 272 </ul>
 273
 274 Decoding [unpacking] a specific vector in the vector lookup table
 275 proceeds according to <tt>[codebook_lookup_type]</tt>.  The unpacked
 276 vector values are what a codebook would return during audio packet
 277 decode in a VQ context.<p>
 278
 279 <h3>Vector value decode: Lookup type 1</h3>
 280
 281 Lookup type one specifies a lattice VQ lookup table built
 282 algorithmically from a list of scalar values.  Calculate [unpack] the
 283 final values of a codebook entry vector from the entries in
 284 <tt>[codebook_multiplicands]</tt> as follows (<tt>[value_vector]</tt>
 285 is the output vector representing the vctor of values for entry number
 286 <tt>[lookup_offset]</tt> in this codebook):<p>
 287
 288 <pre>
 289   1) [last] = 0;
 290   2) [index_divisor] = 1;
 291   3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
 292
 293        4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer
 294           division ) integer modulo [codebook_lookup_values]
 295
 296        5) vector [value_vector] element [i] =
 297             ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
 298             [codebook_delta_value] + [codebook_minimum_value] + [last];
 299
 300        6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
 301
 302        7) [index_divisor] = [index_divisor] * [codebook_lookup_values]
 303
 304      }
 305
 306   8) vector calculation completed.
 307 </pre>
 308
 309 <h3>Vector value decode: Lookup type 2</h3>
 310
 311 Lookup type two specifies a VQ lookup table in which each scalar in
 312 each vector is explicitly set by the <tt>[codebook_multiplicands]</tt>
 313 array in a one-to-one mapping.  Calculate [unpack] the
 314 final values of a codebook entry vector from the entries in
 315 <tt>[codebook_multiplicands]</tt> as follows (<tt>[value_vector]</tt>
 316 is the output vector representing the vctor of values for entry number
 317 <tt>[lookup_offset]</tt> in this codebook):<p>
 318
 319 <pre>
 320   1) [last] = 0;
 321   2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions]
 322   3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) {
 323
 324        4) vector [value_vector] element [i] =
 325             ( [codebook_multiplicands] array element number [multiplicand_offset] ) *
 326             [codebook_delta_value] + [codebook_minimum_value] + [last];
 327
 328        5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i]
 329
 330        6) increment [multiplicand_offset]
 331
 332      }
 333
 334   7) vector calculation completed.
 335 </pre>
 336
 337 <h1>Use of the codebook abstraction</h1>
 338
 339 The decoder uses the codebook abstraction much as it does the
 340 bit-unpacking convention; a specific codebook reads a
 341 codeword from the bitstream, decoding it into an entry number, and then
 342 returns that entry number to the decoder (when used in a scalar
 343 entropy coding context), or uses that entry number as an offset into
 344 the VQ lookup table, returning a vector of values (when used in a context
 345 desiring a VQ value). Scalar or VQ context is always explicit; any call
 346 to the codebook mechanism requests either a scalar entry number or a
 347 lookup vector.<p>
 348
 349 Note that VQ lookup type zero indicates that there is no lookup table;
 350 requesting decode using a codebook of lookup type 0 in any context
 351 expecting a vector return value (even in a case where a vector of
 352 dimension one) is forbidden.  If decoder setup or decode requests such
 353 an action, that is an error condition rendering the packet
 354 undecodable.<p>
 355
 356 Using a codebook to read from the packet bitstream consists first of
 357 reading and decoding the next codeword in the bitstream. The decoder
 358 reads bits until the accumulated bits match a codeword in the
 359 codebook.  This process can be though of as logically walking the
 360 Huffman decode tree by reading one bit at a time from the bitstream,
 361 and using the bit as a decision boolean to take the 0 branch (left in
 362 the above examples) or the 1 branch (right in the above examples).
 363 Walking the tree finishes when the decode process hits a leaf in the
 364 decision tree; the result is the entry number corresponding to that
 365 leaf.  Reading past the end of a packet propagates the 'end-of-stream'
 366 condition to the decoder.<p>
 367
 368 When used in a scalar context, the resulting codeword entry is the
 369 desired return value.<p>
 370
 371 When used in a VQ context, the codeword entry number is used as an
 372 offset into the VQ lookup table.  The value returned to the decoder is
 373 the vector of scalars corresponding to this offset.<p>
 374
 375 <hr>
 376 <a href="http://www.xiph.org/">
 377 <img src="white-xifish.png" align=left border=0>
 378 </a>
 379 <font size=-2 color=#505050>
 380
 381 Ogg is a <a href="http://www.xiph.org">Xiph.org Foundation</a> effort
 382 to protect essential tenets of Internet multimedia from corporate
 383 hostage-taking; Open Source is the net's greatest tool to keep
 384 everyone honest. See <a href="http://www.xiph.org/about.html">About
 385 the Xiph.org Foundation</a> for details.
 386 <p>
 387
 388 Ogg Vorbis is the first Ogg audio CODEC.  Anyone may freely use and
 389 distribute the Ogg and Vorbis specification, whether in a private,
 390 public or corporate capacity.  However, the Xiph.org Foundation and
 391 the Ogg project (xiph.org) reserve the right to set the Ogg Vorbis
 392 specification and certify specification compliance.<p>
 393
 394 Xiph.org's Vorbis software CODEC implementation is distributed under a
 395 BSD-like license.  This does not restrict third parties from
 396 distributing independent implementations of Vorbis software under
 397 other licenses.<p>
 398
 399 Ogg, Vorbis, Xiph.org Foundation and their logos are trademarks (tm)
 400 of the <a href="http://www.xiph.org/">Xiph.org Foundation</a>.  These
 401 pages are copyright (C) 1994-2002 Xiph.org Foundation. All rights
 402 reserved.<p>
 403
 404 </body>
 405