[Vorbis] Unused entries in code book

[xiphmont at xiph.org]

On 11/6/07, Tuomo Latto <djv at iki.fi> wrote:
> Vamsi Mohan Reddy Pulagam wrote:
> > I am trying to understand the building of Huffman codes from the code
> > lengths. In the Tremor code first I see that the codewords are being
> > generated by the function _make_words() and then sorted.
> >
> > After this I see some magic code and something related to unused
> > entries. Does the code generate code words for unused entries too? Are
> > these unused entry code words used during the decode process? If these
> > are used why do we call them unused entries?
>
> I think the Huffman codes used by Vorbis encoders are essentially
> a predetermined set, instead of the optimal ones that you usually create
> by using the statistics of the whole data.
>
> Someone correct me if I'm wrong.

This is something different...

The primary kind of VQ codebook in vorbis is a 'lattice book'; it is
simply an N-dimensional hypersquare grid.  Each entry is just one cell
in the grid.

Not all the cells in a grid actually appear in the codebook.  These
are 'unused entries'.  They are not codeable (they have no hufftree
entry) and it is also not possible to have a codeword decode to an
unused entry.

Monty